Cryptography/Meet In The Middle Attack

From Wikibooks, open books for an open world
Jump to: navigation, search

An extremely specialized attack, meet in the middle is a known plaintext attack that only affects a specific class of encryption methods - those which achieve increased security by using one or more "rounds" of an otherwise normal symmetrical encryption algorithm. An example of such a compound system is 3DES.

However, to explain this attack let us begin with a simpler system defined as follows: Two cryptographic systems denoted and (with inverse functions and respectively) are combined simply (by applying one then the other) to give a composite cryptosystem. each accepts a 64 bit key (for values from 0 to 18446744073709551615) which we can call or as appropriate.

So for a given plaintext, we can calculate a cryptotext as

and correspondingly

Now, given that each has a 64 bit key, the amount of key needed to encrypt or decrypt is 128 bits, so a simple analysis would assume this is the same as a 128 bit cypher.

However, given sufficient storage, you can reduce the effective key strength of this to a few bits larger than the largest of the two keys employed, as follows.

  1. Given a plaintext/cyphertext pair, apply to the plaintext with each possible key in turn, generating intermediate cryptotexts where
  2. Store each of the cryptotexts in a hash table so that each can be referenced by its cryptotext, and give the key used to generate that cryptotext
  3. Apply to the ciphertext for each possible key in turn, comparing the intermediate plaintext to the hash table calculated earlier. this gives a pair of keys (one for each of the two algorithms employed, and )
  4. Taking the two keys from stage 3, test each against a second plaintext/cryptotext pair. if this also matches, odds are extremely high you have a valid keypair for the message - not in operations, but a "mere" operations (which nonetheless are significantly longer due to the hash table operations, but not so much as to add more than a couple of extra bits worth of time to the complexity of the task)

The downside to this approach is storage. Assuming you have a 64 bit key, then you will need at least units of storage - where each unit is the amount of space used by a single hash record. Even given a minimal implementation (say, 64 bits for the key plus four bits hash collision overhead), if you implemented such a system using 160GB hard drives, you would need close to one billion of them to store the hash table alone.