# Cryptography/Meet In The Middle Attack

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 $encrypt_\alpha$ and $encrypt_\beta$ (with inverse functions $decrypt_\alpha$ and $decrypt_\beta$ 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 $key_\alpha$ or $key_\beta$ as appropriate.

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

$cryptotext=encrypt_\beta( key_\beta , encrypt_\alpha(key_\alpha,plaintext))$

and correspondingly

$plaintext=decrypt_\alpha( key_\alpha , decrypt_\beta(key_\beta,cryptotext))$

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 $encrypt_\alpha$ to the plaintext with each possible key in turn, generating $2^{64}$intermediate cryptotexts $cryptotext_1$$\rightarrow$$cryptotext_n$ where $n=2^{64}$
2. Store each of the $n$ 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 $decrypt_\beta$ 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, $\alpha$ and $\beta$)
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 $2^{128}$ operations, but a "mere" $2x2^{64}$ 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 $2^{64}$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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 21, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9232715964317322, "perplexity_flag": "middle"}