4 Principles of encryption
4.5 Vulnerability to attack
All the symmetric and public key algorithms listed in Table 2 and Table 3share the fundamental property that their secrecy lies in the key and not in the algorithm. (This is generally known as Kerchoff's principle after the Dutchman who first proposed it in the nineteenth century.) This means that the security of any system using encryption should not be compromised by knowledge of the algorithm used. In fact, the use of a well-known and well-tested algorithm is preferred, since such methods have been subjected to intense scrutiny by practitioners in the field. If practitioners with detailed knowledge of an algorithm have not found messages encrypted with it vulnerable to attack and have been unable to break it, then it is safe to assume that others, without that knowledge, will also be unable to do so. However, the strength of a cryptographic algorithm is difficult if not impossible to prove, as it can only be shown that the algorithm has resisted specific known attacks. (An attack in this context is an attempt to discover the plaintext of an encrypted message without knowledge of the decryption key.) New and more sophisticated mathematical tools may emerge that substantially weaken algorithms previously considered to be immune from attack.
Cryptanalysis is the science of breaking a cipher without knowledge of the key (and often the algorithm) used. Its goal is either to recover the plaintext of the message or to deduce the decryption key so that other messages encrypted with the same key can be decrypted.
One of the more obvious attacks is to try every possible key (i.e. the finite set of possible keys, known as the keyspace) until the result yields some intelligible data. This kind of attack is known as a brute force attack. Clearly, the greater the keyspace, the greater the immunity to a brute force attack.
SAQ 7
Assuming you could process 1012 key attempts per second, calculate how long it would take to search the keyspace of a 56-bit key. Compare this with the time needed to search the keyspace of a 128-bit key.
A keyspace of 56 bits provides 256≈7.2×1016 possible keys. At a rate of 1012 keys per second it would take approximately 7.2×104 seconds or about 20 hours to try every key. A keyspace of 128 bits provides 2128≈3.4×1038 possible keys. This would take approximately 3.4×1026 seconds or about 1019 years. (Note: the lifetime to date of the universe is thought to be of the order of 1010 years.)
In practice it is unlikely that an attacker would need to try every possible key before finding the correct one. The correct key could be found to a 50 per cent probability by searching only half of the keyspace. Even allowing for this, the time taken to break a 128-bit key is still impossibly long.
From the answer to SAQ 7 you may conclude that all that is needed for true data security is to apply an encryption system with an appropriate length key. Unfortunately, key length is only one of the factors that determine the effectiveness of a cipher. Cryptanalysts have a variety of tools, which they select according to the amount of information they have about a cryptosystem. In each of the cases below, a knowledge of the encryption algorithm but not the key is assumed:
- Ciphertext only. The attacker has only a sample of ciphertext. The speed and success of such an attack increases as the size of the ciphertext sample increases, provided that each portion of the sample has been encrypted with the same algorithm and key.
- Known plaintext. The attacker has a sample of plaintext and a corresponding sample of ciphertext. The purpose of this attack is to deduce the encryption key so that it can be used to decrypt other portions of ciphertext encrypted with the same algorithm and key.
- Chosen text. The attacker usually has a sample of chosen plaintext and a corresponding sample of ciphertext. This attack is more effective than known plaintext attacks since the attacker can select particular blocks of plaintext that can yield more information about the key. The term may also refer to cases where the attacker has a stream of chosen ciphertext and a corresponding stream of plaintext.
Activity 6
From the list above how would you classify a brute force attack?
To mount a brute force attack, the attacker would need a sample of ciphertext and knowledge of the algorithm used, so this would be classified as a ciphertext-only attack.
A ciphertext-only attack is one of the most difficult to mount successfully (and therefore the easiest to defend against) because the attacker possesses such limited information. In some cases even the encryption algorithm is also unknown. However, the attacker may still be able to use statistical analysis to reveal patterns in the ciphertext, which can be used to identify naturally occurring language patterns in the corresponding plaintext. This method relies on exploiting the relative frequencies of letters. In the English language, for example, E is the most frequently occurring letter with a probability of about 0.12. This is followed by the letter T (probability 0.06) then A, O, I, N, S and R. Common letter sequences in natural language (e.g. TH, HE, IN, ER and THE, ING, AND and HER) may also be detected in the corresponding ciphertext.
These letters and their ordering may differ slightly according to the type and length of the sampled text. All authors have their own style and vocabulary and this can lead to statistical differences, as can the subject matter and spelling, e.g. English or American.
The only truly secure encryption scheme is one known as a one-time pad, introduced in 1918 by Gilbert Vernam, an AT&T engineer. Vernam's cipher used for its key a truly random and non-repeating stream of bits, each bit being used only once in the encryption process. Each bit in the plaintext message is XORed with each bit of the keystream to produce the ciphertext. After encryption the key is destroyed. Because of the random properties of the keystream, the resulting ciphertext bears no statistical relationship with the plaintext and so is truly unbreakable. The disadvantage of such a scheme, however, is that it requires the key to be at least the same length as the message and each key can be used only once (hence the name one-time pad). Since both sender and recipient require a copy of the key and a fresh key is needed for each message, this presents somewhat of a problem for key management. Despite these practical difficulties, use of the one-time pad has proved effective for high-level government and military security applications.