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 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, 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.