Partial-matching Meet-in-the-Middle attack

Partial-matching is a technique that can be used with a MITM attack. Partial-matching is where the intermediate values of the MITM attack, $i$ and $j$ , computed from the plaintext and ciphertext, are matched on only a few select bits, instead of on the complete state.

Uses

A limitation with MITM attacks is the amount of intermediate values that needs to be stored. In order to compare the intermediate values $i$ and $j$ , all $i$ 's need to be computed and stored first, before each computed $j$ can be compared against them. If the two subciphers identified by the MITM attack both has a sufficiently large subkey, then an unfeasible amount of intermediate values need to be stored. While there are techniques such as cycle detection algorithms^[1] that allows one to perform a MITM attack without storing either all values of $i$ or $j$ , these techniques requires that the subciphers of the MITM attack are symmetric. Thus it is a solution that allows one to perform a MITM attack in a situation, where the subkeys are of a cardinality just large enough to make the amount of temporary values that need to be stored infeasible. While this allows one to store more temporary values, its use is still limited, as it only allows one to perform a MITM attack on a subcipher with a few more bits. As an example: If only 1/8 of the intermediate value is stored, then the subkey needs only be 3 bits larger, before the same amount of memory is required anyway, since $2^{-3}=1/8$

A in most cases far more useful feature provided by partial-matching in MITM attacks, is the ability to compare intermediate values computed at different rounds in the attacked cipher. If the diffusion in each round of the cipher is low enough, it might be possible over a span of rounds to find bits in the intermediate states that has not changed with a probability of 1. These bits in the intermediate states can still be compared.

The disadvantage for both of these uses, is that there will be more false positives for key candidates, which needs to be tested. As a rule, the chance for a false positive is given by the probability $2^{-|i|}$ , where $|i|$ is the amount of matched bits.

Example

For a step-by-step example of the complete attack on KTANTAN,^[2] see the example on the 3-subset MITM page. This example only deals with the part that needs partial-matching. What is useful to know is that KTANTAN is a 254-round blockcipher, where each round uses 2 bits from the 80-bit key.

In the 3-subset attack on the KTANTAN family of ciphers, it was necessary to utilize partial-matching in order to stage the attack. Partial-matching was needed, because the intermediate values of the plain- and ciphertext in the MITM attack, were computed at the end of round 111 and at the start of round 131, respectively. Since they had a span of 20 rounds between them, they could not be compared directly.

The authors of the attack, however, identified some useful characteristics of KTANTAN that held with a probability of 1. Due to the low diffusion per round in KTANTAN (the security is in the number of rounds), they found out by computing forwards from round 111 and backwards from round 131 that at round 127, 8 bits from both intermediate states would remain unchanged. (It was 8 bits at round 127 for KTANTAN32. It was 10 bits at round 123 and 47 bits at round 131 for KTANTAN48 and KTANTAN64, respectively). by only comparing the 8 bits of each intermediate value, the authors was able to orchestrate a MITM attack on the cipher, despite there being 20 rounds between the two subciphers.

Using partial-matching increased the amount of false positives, but nothing that noticeably increased the complexity of the attack.

Notes

↑ Cycle detection
↑ Andrey Bogdanov and Christian Rechberger. "A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN"

Block ciphers (security summary)
Common algorithms	AES Blowfish DES (Internal Mechanics, Triple DES) Serpent Twofish
Less common algorithms	Camellia CAST-128 IDEA RC2 RC5 RC6 SEED ARIA Skipjack TEA XTEA
Other algorithms	3-Way Akelarre Anubis BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES GOST Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi Kalyna KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Kuznyechik Ladder-DES Libelle LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Prince Q RC6 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon SM4 Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES Xenon xmx XXTEA Zodiac
Design	Feistel network Key schedule Lai–Massey scheme Product cipher S-box P-box SPN Avalanche effect Block size Key size Key whitening (Whitening transformation)
Attack (cryptanalysis)	Brute-force (EFF DES cracker) MITM Biclique attack 3-subset MITM attack Linear (Piling-up lemma) Differential Impossible Truncated Higher-order Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Side-channel Timing Power-monitoring Electromagnetic Acoustic Differential-fault XSL Interpolation Partitioning Rubber-hose Black-bag Davies' Rebound Weak key Tau Chi-square Time/memory/data tradeoff
Standardization	AES process CRYPTREC NESSIE
Utilization	Initialization vector Mode of operation Padding

Cryptography
History of cryptography Cryptanalysis Outline of cryptography
Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography
Category Portal WikiProject

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.