Cryptanalysis and Attacks

Cryptanalysis is the science of cracking codes and decoding secrets. It is used to violate authentication schemes, to break cryptographic protocols, and, more benignly, to find and correct weaknesses in encryption algorithms.

It may be used in information warfare applications - for example, forging an encrypted signal to be accepted as authentic. Competitors who have been able to discover the key will now want to use it to their advantage, therefore they will want to send bogus encrypted messages to the source in order to gain information or gain an advantage. It could also be used to pretend to be the source in order to send bogus information to others, who now will think that it came from the official source.

According to Diffie and Hellman

Skill in the production of cryptanalysis has always been heavily on the side of the professionals, but innovation, particularly in the design of new types of cryptographic systems, has come primarily from amateurs.

Among the types of attacks are:


There are also a number of other technical and non-technical cryptography attacks to which systems can fall victim. Cryptanalytic attacks can be mounted not only against encryption algorithms, but also against digital signature algorithms, MACing algorithms and pseudo-random number generators.

Ciphertext Only Attack

A ciphertext only attack (COA) is a case in which only the encrypted message is available for attack, but because the language is known a frequency analysis could be attempted. In this situation the attacker does not know anything about the contents of the message, and must work from ciphertext only.

Known Plaintext Attack

In a known plaintext attack (KPA) both the plaintext and matching ciphertext are available for use in discovering the key.

The attacker knows or can guess the plaintext for some parts of the ciphertext. For example, maybe all secure login sessions begin with the characters LOGIN, and the next transmission may be PASSWORD. The task is to decrypt the rest of the ciphertext blocks using this information. This may be done by determining the key used to encrypt the data, or via some shortcut.

Chosen Plaintext Attack

A chosen plaintext attack (CPA) occurs when the attacker gains access to the target encryption device - if, for example, it is left unattended. The attacker then runs various pieces of plaintext though the device for encryption. This is compared to the plaintext to attempt to derive the key.

In an adaptive chosen plaintext attack (ACPA), the attacker not only has access to the plaintext and its encryption, but can adapt or modify the chosen plaintext as needed based on results of the previous encryptions.

Chosen Ciphertext Attack

In a chosen ciphertext attack (CCA), the cryptanalyst can choose different ciphertexts to be decrypted and has access to the decrypted plaintext.

This type of attack is generally applicable to attacks against public key cryptosystems.

An adaptive chosen ciphertext attack involves the attacker selecting certain ciphertexts to be decrypted, then using the results of these decryptions to select subsequent ciphertexts. The modifications in the ciphertext help in deciphering the key from the decryptions.

Man-in-the-Middle Attack

Cryptographic communications and key exchange protocols are susceptible to an attack in which the attacker is able to place himself on the communication line between two parties.

In this "man-in-the-middle attack" the attacker is able to position himself to intercept the key exchange between two parties. He performs his own key exchange with each. Then, with both parties thinking they have set up a secure channel, the attacker decrypts any communications with the proper key, and encrypts them with the other key for sending to the other party. The parties think that they are communicating securely, but in fact the adversary is reading everything.

Preventing a man-in-the-middle attacks is possible if both sides compute a cryptographic hash function of the key exchange, sign it using a digital signature algorithm, and send the signature to the other side. The recipient then verifies that the hash matches the locally computed hash and the signature came from the desired other party.

Side Channel Attacks

Side channel attacks are a type of attacks based on implementation details such as timing, power, and radiation emissions.

By carefully measuring the amount of time required to perform private key operations, attackers may be able to find fixed Diffie-Hellman exponents, factor RSA keys, and break other cryptosystems. Against a vulnerable system, the attack is computationally inexpensive and often requires only known ciphertext. Actual systems are potentially at risk, including cryptographic tokens, network-based cryptosystems, and other applications where attackers can make reasonably accurate timing measurements.
(For additional information see http://www.cryptography.com/public/pdf/TimingAttacks.pdf)

Differential power analysis (DPA) describes a new class of attacks against smart cards and secure cryptographic tokens. Discovered by researchers at Cryptography Research in San Francisco, DPA attacks exploit characteristic behaviors of transistor logic gates and software running on today's smart cards and other cryptographic devices. The attacks are performed by monitoring the electrical activity of a device, then using advanced statistical methods to determine secret information (such as secret keys and user PINs) in the device.
(For additional information, see http://www.cryptography.com/technology/dpa.html)

Brute Force Attack

A brute force attack involves trying all possible keys until hitting on the one that results in plaintext. This can involve significant costs related to the amount of processing required to try quadrillions (in the case of DES) of keys. The time required is a factor of how many keys can be tried per unit of time, which is a factor of how many computers can be assigned to the task in parallel.

Because computers are getting faster all the time. The unit of measure for comparison purposes is million-instructions-per-second (MIPS) per year (MY). It is the number of instructions a million-instructions-per-second (MIPS) computer can execute in one year.

Moore's Law (Gordon Moore, founder of Intel) states that processing speed doubles every 18 months. As a result, advances in technology and computing performance will always make brute force an increasingly practical attack on keys of a fixed length.

This table shows the times required for a brute force attack on various key lengths using "Deep Crack" technology.


Deep Crack technology was developed in 1998 by the EFF (Electronic Frontier Foundation). They built a machine called the Deep Crack capable of trying a million DES keys per microsecond against a readable ASCII string hours to try all possible keys. In theory, its success in cracking DES makes DES worthless. In practice, however, by using cipher block chaining, doing any initial scrambling of the data and/or doing it three times in a row (triple DES), it can still be fairly difficult to crack.

The only hope against a brute force attack is to have so many possible keys that it is not feasible to try them all in a reasonable amount of time. Obviously, as the key length grows beyond 100 or so, the number of keys quickly becomes astronomical. The new AES standard, Rijndael, which is supposed to replace DES, supports 128 and 256 bit keys. Even taking into account the staggering advances in computing power and cryptanalysis, 256 bit keys should be pretty safe for the next 100 years or so.

Birthday Attack

 A birthday attack is a class of brute force attack used against hashing functions. It is based on the "birthday paradox." This states that in a group of 23 people, there is at least a 50% probability that at least two people will share the same birthday. In a group of 60 people, the probability is over 99%.

A hash function gives a set value for a message. It can be easier for an attacker to find two messages with the same digest value than it is to match a specific value.

It would seem that a 128-bit hash function would force the attacker to try 2 128 inputs to find a match to a specific source document. But the birthday paradox applies, so the attacker can find two arbitrary documents that hash to the same value in only 2 64 steps for a 128-bit hash function.

A strong hash function needs to resist the birthday attack.

Attacks on Symmetric Block Ciphers

 Four types of attacks are normally used against symmetric block ciphers such as DES and RC5:


Differential cryptanalysis is a chosen plaintext attack that relies on analysis of the differences between two related plaintexts as they are encrypted with the same key. The correct key is identified by examining probabilities of each key.

Linear cryptanalysis, a known plaintext attack, uses linear approximation to describe behavior of the block cipher. Given sufficient pairs of plaintext and corresponding ciphertext, bits of information about the key can be obtained.

Differential linear cryptanalysis is a combination of differential and linear cryptanalysis.

Algebraic attacks analyze vulnerabilities in the mathematics of the algorithm.

Other Types of Cryptographic Attacks

 Other types of cryptographic attacks include analytic, statistical and implementation.

Analytic attacks use algorithm and algebraic manipulation weakness to reduce complexity. Two examples are an RSA factoring attack and a Double DES attack.

Statistical attacks involve using statistical weakness in design, such as more 1s than 0s in the keystream.

Implementation attacks exploit weakness in the implementation of the encryption protocol. An example is the 1995 attack on the Netscape key, which had deficient key randomization. Static WEP (wireless equivalent privacy) is similarly subject to attack because of the relatively short initialization vectors that may be reused.

To protect against such attacks, the algorithm must be very strong (some vendor algorithms are not), the key needs to be very random without any bias (no patterns), and the implementation must be in accordance with good cryptographic concepts.

Non-Technical Cryptographic Attacks

Not all system attacks involve sophisticated cryptanalysis or major computing power. The people who use and run systems are themselves subject to attack - and these are often the most successful.

"Purchase key" attack is another term for bribery.

"Rubber hose cryptanalysis" means gaining access to a system through a physical assault on a user.

Social engineering involves convincing someone, usually through subterfuge, to divulge their password or other persona or confidential information.

Summary

Cryptanalysis is the science of cracking codes and decoding secrets. It is used to violate authentication schemes, to break cryptographic protocols, and, more benignly, to find and correct weaknesses in encryption algorithms.

The major categories of cryptanalysis include ciphertext only, known plaintext, chosen plaintext, and chosen ciphertext. These involve deriving the key from analysis of the pieces provided.

In a man-in-the-middle attack, the attacker intercepts the key exchange between the parties. This allows him to decrypt a message from one party, read it, then re-encrypt it with the sender's key before transmitting it on to the intended recipient. The sender and recipient have no way of knowing that their supposedly confidential communication has been intercepted.

To prevent this, both sides can compute a cryptographic hash function of the key exchange, sign it using a digital signature algorithm, and send the signature to the other side. The recipient then verifies that the hash matches the locally computed hash and the signature came from the desired other party.

A brute force attack involves trying all possible keys until hitting on the one that results in plaintext. The defense is to make the attack too time consuming or expensive. The larger the key length that is supported by an algorithm the larger its key space. Therefore, the more unique keys available, the longer it would take for a successful brute force attack.

Other types of attacks look for weaknesses in the algorithm, in the implementation. But the most successful attacks on systems are attacks on the system administrators or users, where attackers gain access through subterfuge, susceptibility to greed, or through physical violence or threat of violence.