CERBERUS

Vulnerabilities Threats Countermeasures

Document Security

FIPS PUB 140-1
DOD 5220.22-M
NCSC TG-25
FIPS PUB 81
FIPS PUB 180-1
DOD 5200.28-STD

INFOSEC
Cryptosystems
Passphrases
Windows® Leaks
System Settings

QUESTIONS?

By definition, a cryptosystem is the combination of three elements: an encryption engine, keying information, and operational procedures for their secure use.

In order to cryptographically secure high-value data on a hard disk (or on back-up media), it is necessary to employ a high-grade cryptosystem: one which even an attacker possessing both a copy of your encryption engine and knowledge of your operating procedures cannot break without your keying information.

NOTE: A low-grade cryptosystem is one which an attacker can break by means of purely cryptanalytic attacks on the ciphertext it produces, but which may delay him long enough for the period of time during which the corresponding plaintext that it encrypted has value. A medium-grade cryptosystem is one which cannot be broken in a useful time without the attacker possessing a copy of the encryption engine, which he can use in chosen plaintext attacks to help recover your key. Both are useful in COMmunications SECurity, but they are of limited value in protecting data which must be stored in encrypted form, perhaps for years.

High-grade encryption has no "short cuts" to breaking it with less expense than would be required to repeatedly try decryption with different key values until one works. Its strength hinges on the degree to which an attacker cannot predict that certain values are more probable than others through knowledge of the key generation process.

CODES AND CIPHERS

A code is a system of symbolic replacements for phrases, words and letters. Its security can require maintaining the confidentiality of a large amount of data (e.g., a code-book). If the lexical elements replaced are individual characters of an alphabet, rather than entire words, that burden is reduced. A letter-by-letter code is a cipher.

Julius Caesar encrypted his military field reports by replacing each letter of the Latin alphabet with the letter three characters farther down the list, "wrapped-around" by repeating after letter 'Z'. ASCII text data is represented with an alphabet of sequential bytes. Thus, in terms of the modern Roman alphabet, encryption in this Caesar cipher is merely the wrap-around (modulo-26) adding of three to each byte of plaintext data.

It's "key" is three, the modulo-26 list-number of the letter 'D'. This can be generalized by using any number from 0 to 25 ('A' to 'Z'). Decryption is modulo-26 adding of 26-minus-the-key to each letter; this is the same as modulo-26 subtracting the key.

This simple monoalphabetic substitution cipher can be broken by "brute forcing" its 5-bit key; i.e. creating up to 26 different shifted messages until one makes sense.

To strengthen it against such exhaustive keysearch attacks, you could allow use of any scrambling (permutation) of the 26 letters as a substitution alphabet, not limiting yourself to the 26 shifted alphabets. This many possible alphabets enlarges the key to an 89-bit number (26-factorial). However, it can't defeat cryptanalytic attacks.

Any monoalphabetic substitution cipher can be broken by comparing the relative frequencies of occurrence of the letters in intercepted ciphertext samples with the corresponding statistics for letters in plaintext examples of related writings.

The fact that such cryptanalysis can break any monoalphabetic substitution cipher with much less effort than exhaustive keysearch attacks means that monoalphabetic substitution ciphers can never provide high-grade encryption.

MODERN CIPHERS

You could sequentially use the letters of a key word as key letters for monoalphabetic substitution of sequential plaintext letters from separate substitution alphabets, equal in number to the number of letters in the key. This polyalphabetic substitution cipher blurs the statistics of the letter frequencies to an almost flat probability distribution.

Its modern version is the byte-by-byte addition of a keystream to the plaintext - a Vernam cipher. For all its apparent complexity, however, if you sample its ciphertext at letter intervals equal to the length of the key, the old statistics jump out at you. Friedman's brilliant index of coincidence statistic will betray that key length.

NOTE: An excellent souce for understanding how many ways have been devised to break apparently clever ciphers is US Army Field Manual FM-34-40-2, Basic Cryptanalysis, the successor to TM 32-220. It will quickly show you why professional creation of ciphers is restricted to those with proven experience in breaking the codes and ciphers of others.

To counter this attack, you must have a secret keystream as long as the message. If it is used twice on messages of the same length, adding the two ciphertext streams will cancel it out, leaving non-uniformly distributed letters for statistical cryptanalysis.

To be unbreakable, the keystream must come from a onetime pad of length equal to that of all the data bytes encrypted. All this keying material must be kept secret.

This horrendous keying materials management problem for the only proven unbreakable cipher has led to searches for keying material generators which can substitute. However, all such schemes are based on algorithms, and must therefore leave patterns in the keystreams for statistical analyses that can break them.

Their cryptographic strength is therefore a matter of degree (the cryptanalyst's workfactor), not an absolute. However, that strength can still be formidable.

One technique for achieving it is the use of Feistal networks, that generate blocks of keystream from blocks of the message itself, through multiple rounds of groups of permutations and substitutions, each dependent on transformations of a key. If they are specifically structured to thwart all the known statistical cryptanalysis methods, their cryptanalytic workfactor can be made as large as that for exhaustive keysearch.

DATA ENCRYPTION STANDARD

FIPS PUB 46-2, the Data Encryption Standard (DES) specifies and mandates the use of the standard cipher for encrypting SBU information on all US Government AISs. Its approved modes of use in encryption engines are specified in FIPS PUB 81, and its validation tests in Special Publication 500-20. It is a 16-round, Feistal network cipher.

The DES cipher was reviewed for NIST (then the National Bureau of Standards) by the NSA, in its COMSEC role (as opposed to its code-breaking COMINT role). The values of the constants in the DES S-box substitution tables were specifically chosen to resist then-known-by-NSA cryptanalytic attacks, including the then-highly-classified concept of differential cryptanalysis. Its key size was chosen to be secure for at least a decade, while allowing implementations in 1970s integrated circuit technology.

This 64-bit block cipher has successfully withstood public cryptanalysis for more than 20 years, a record matched by no other. In that time, however, the cost of special-purpose key-search machines capable of brute force attacks on its 56-bit keyspace has dropped below levels feasible for most governments (and some corporations).

NOTE: A thousand cooperating million-DES-encryptions-per-second machines, an array affordable by many governments and corporations, could perform the 2-to-the-55th-power trial encryptions required to search half the 56-bit keyspace of DES (the amount necessary, on average) in a year. Ten thousand of them could do such an exhaustive keysearch in little more than a month. With the speed-per-dollar of such machines doubling every year or so, DES can hardly be considered secure for long-term use.

Over two decades of unsuccessful cryptanalysis have shown the DES cipher's cryptographic strength to be, in practical terms, equivalent to the size of its key. Thus, an obvious place to look for its replacement is a version with a larger key.

TRIPLE-DES CIPHER

Unlike the available alternative block ciphers, the DES cipher has been proven mathematically to not be an algebraic Group. Consequently, unlike those alternatives, three-pass encryption with DES yields a product cipher with a keyspace dimension equivalent to the sum of the sizes of the independent keys used in those passes. (Two-pass use of any block cipher is vulnerable to meet-in-the-middle attacks.)

Each additional key-bit doubles the size of the keyspace. This is a crude, but extremely effective approach to defeating exhaustive key-search attacks through many years of increased computing power evolution.

NOTE: This type of product cipher can be attacked by two different types of key-search methods:

(1) the obvious one of searching a 168-bit (3x56 bits) key-space, requiring an average of 2-to-the-167th-power triple-DES encryptions to crack the key used for a particular ciphertext (half the keyspace); or
(2) pre-computing 2-to-the-56th-power DES decryptions and checking the stored table of results against an average of 2-to-the-111th-power double-DES encryptions.

The former attack requires a thousand million-DES-encryptions-per-second machines to run for 10-to-the-31st-power millennia; the latter "only" requires them to run for 64 million-million millennia, if all one thousand machines can access the lookup table (which requires 500 million gigabytes of storage). Neither attack is taken very seriously by professionals, who would attack the key (and all your other keys at the same time) by exploiting cryptosystem implementation weaknesses or operator mistakes.

EXPORT CONTROLS

The financial services and banking industry uses the DES cipher to secure trillions of dollars of transactions. It has been moving toward standardizing on 112-bit (2-key) triple-DES as its successor for the next century. (In 2-key triple-DES, the same key is used for the first and third encryptions, requiring less keying material generation.)

However, the US Government has thus far refused to provide the required export approvals, instead suggesting the use of its Escrowed Encryption Standard (FIPS PUB 185). This mandates use of the now-declassified Skipjack cipher with an 80-bit key (16 million times the size of the 56-bit DES keyspace), and a Law Enforcement Access Field (LEAF) permitting key recovery without the user's cooperation.

NOTE: The Skipjack cipher is used in the Fortezza and Fortezza Plus encryption engines for all SBU information in NSA's Multi-level Information System Security Initiative (MISSI) system. NSA apparently considers this 64-bit block, 32-round, Feistal network's 80-bit key size to be adequate for fulfilling its SBU INFOSEC mission for the next decade or two.

Our software cryptosystems employ a full 168-bit (3-key) triple-DES algorithm in cipher block chaining (CBC) mode. They incorporate neither a LEAF mechanism nor covert channels for key recovery. (The Professional versions do, however, provide you with the ability to generate secure split key shares that enable you to offer emergency access to your encrypted data by multiple trusted parties acting in concert.)

Since the Bureau of Export Administration will not grant export licenses for such cryptosystems, our products can only be made lawfully available within the United States (to US citizens or Resident Aliens) or Canada, per 15 CFR 730-774.

KEY-GENERATION

Use of a strong encryption algorithm, such as 168-bit triple-DES (and using this cipher in outer CBC mode, rather than in a cryptanalytically weaker mode to implement the cryptographic engine) makes the strength of the cryptosystem the strength of the keys. It maximizes that strength by minimizing the amount of cyphertext generated with each key. What never exists can't be cryptanalyzed.

NOTE: Our software cryptosystems generate one-time keys for each encryption with a DES-based ANSI X9.17 key generator, automatically rejecting both weak and semi-weak keys. Each time, the generator is seeded by an SHA-1 secure hash of the least-significant bytes of all the millisecond time intervals between your keystrokes in each passphrase challenge dialog. Your master key only encrypts one-time keys, and is generated from a secure hash on all the characters entered, iteratively triple-DES-encrypted to add further workfactor to dictionary attacks. In both cases, both your name and passphrase are included in the hashes, making your master key different from that of another user using the same passphrase, and maximizing the entropy of the key generator seed.

High-grade encryption eliminates your need to protect the security of a large number of bytes of high-value data scattered in a number of different files. However, it replaces that need with the responsibility to protect a much smaller number of extremely high-value bytes: your keying information.

Three-key, triple-DES encryption requires 168 bits of keying information. It is often presented as 24 bytes, each containing a 7-bit value and an optional odd-parity bit. The strength of the encryption hinges on the uniformity of the probability distribution of the possible values. Since the parity bits are not independently random, the key size is not the entire 192 bits of the 24 bytes. Any biases in the method of selecting key values will similarly reduce the number of bits of encryption-breaking workfactor.

However, 24-byte binary numbers (or 48-digit hexadecimal numbers) are not easy for human beings to remember. If such a key were written on a piece of paper, the entire strength of the encryption would rest on an attacker's difficulty in obtaining that piece of paper. Consequently, master keys are usually computed from a more memorable "secret," such as a password. Unfortunately, the number of bits of workfactor required to guess memorable passwords is only a tiny fraction of the size of the keyspace.

In order to make strings of bytes memorable, they are restricted to values that are ASCII text characters. The total of all upper-case and lower-case characters from the Roman alphabet, plus 10 decimal digits, is only 62. Including a hyphen and a space still only brings the number of permissible values for each 8-bit byte to 64, or 6 bits of entropy. To enhance memorability, further restrictions are placed on the characters that may fill subsequent slots in the password based on which characters have been selected for earlier slots. This reduces the number of bits of workfactor still further.