Page138

Chosen Ciphertext and Adaptive Chosen Ciphertext

Chosen ciphertext attacks mirror chosen plaintext attacks: the difference is that the cryptanalyst chooses the ciphertext to be decrypted. This attack is usually launched against asymmetric cryptosystems, where the cryptanalyst may choose public documents to decrypt that are signed (encrypted) with a user’s public key.

Adaptive-chosen ciphertext also mirrors its plaintext cousin: it begins with a chosen ciphertext attack in round 1. The cryptanalyst then “adapts” further rounds of decryption based on the previous round.

Meet-in-the-Middle Attack

A meet-in-the-middle attack encrypts on one side, decrypts on the other side, and meets in the middle. The most common attack is against “double DES,” which encrypts with two keys in “encrypt, encrypt” order. The attack is a known plaintext attack: the attacker has a copy of a matching plaintext and ciphertext and seeks to recover the two keys used to encrypt.

The attacker generates every possible value for key 1 and uses each to encrypt the plaintext, saving the intermediate (half-encrypted) ciphertext results. DES has a 56-bit key, so this will take 2^56^ encryptions.

The attacker then generates every possible value for key 2, and uses each to decrypt the ciphertext. Once decrypted, the attacker looks up the intermediate ciphertext, looking for a match. If there is a match, the attacker has found both key 1 and key 2. The decryption step will take 2^56^ attempts at most, for a total of 2^57^ attempts (2^56^ encryptions + up to 2^56^ decryptions = 2^57^).

In other words, despite 112 bits of key length, breaking double DES is only twice as hard as breaking 56-bit single DES. This is far too easy, so double DES is not recommended. 3TDES has a key length of 168 bits, but an effective strength of 112 bits due to the meet-in-the-middle attack: 3TDES has three keys and two “middles,” one can be used for a meet-in-the-middle attack, bypassing roughly one-third of the work.

Known Key

The term “known key attack” is misleading: if the cryptanalyst knows the key, the attack is over. Known key means the cryptanalyst knows something about the key, to reduce the efforts used to attack it. If the cryptanalyst knows that the key is an uppercase letter and a number only, other characters may be omitted in the attack.

Differential Cryptanalysis

Differential cryptanalysis seeks to find the “difference” between related plaintexts that are encrypted. The plaintexts may differ by a few bits. It is usually launched as an adaptive chosen plaintext attack: the attacker chooses the plaintext to be encrypted (but does not know the key), and then encrypts related plaintexts.

The cryptanalyst then uses statistical analysis to search for signs of non-randomness in the ciphertexts, zeroing in on areas where the plaintexts differed. Every bit of the related ciphertexts should have a 50/50 chance of flipping; the cryptanalyst searches for areas where this is not true. Any such underlying order is a clue to recover the key.

Linear Cryptanalysis

Linear cryptanalysis is a known plaintext attack where the cryptanalyst finds large amounts of plaintext/ciphertext pairs created with the same key. The pairs are studied to derive information about the key used to create them.

Both differential and linear analysis can be combined as differential linear analysis.