Known Plaintext Attack against 3-round SPECK48/96

Question

I am attempting to break 3-round SPECK48/96 using a known-plaintext attack, provided with 10 PT-CT pairs. Here is a diagram:

I have seemed to almost figure this out, but I cannot figure out how the right side affects the state of the text, due to the left rotation. Say I am trying to attack the first set of 8 bits on the left side (24...31). That means I will perform the rotr 8 and addition, then make my $sk_0$ guess on the 16...23 bits. I then XOR with the right side.

$sk_1$ will then be guessing bits 8...15 as those are the bits that were affect by $sk_0$ (due to rotr 8). However, this rotl 3 will cause the bits that were affected by the subkey to move in the other direction, so now each round's subkey guess will be affecting different parts of the plaintext (as opposed to on the left side, where I can trace the movement of these bits).

I may have not been clear but I was trying to explain my thought process...I just cannot seem to figure out how to approach this.

Answer 1

Here is how I would approach this:

• First off, strip off the unkeyed parts of the cipher at the beginning and the end. That is, process the plaintexts with the 'rotr 8/add/rotl 3' at the beginning, and process the ciphertexts with the 'xor/rotr 3' at the end (rotr because we're working the inverse direction).

• Next, we focus in on only the right side ciphertext output; this allows us to skip the entire third round (!)

With these two simplifications, the remaining cipher has only one nonlinear step (the addition in round 2). We proceed to attack that.

The obvious way to start is looking at bit 0 of the addition (we start at the lsbit because there's no carry from unknown bits; if we were doing a differential attack, we'd start at the msbit, as a differential in the msbit propagates with probability 1); the addend on the vertical path is the xor of 1 known bit and 1 key bit; the addend from the right side is the xor of 2 known bits and 1 key bit; we can deduce the lsbit of the sum from xor of 2 known plaintext bits, 1 known ciphertext bit, and 2 key bits (one from subkey 1, the other from subkey 2). We know that the two addends are consistent with the sum, so we go through all 5 possibilities of the key bits, and see which settings are consistent with all known plaintext/ciphertext pairs.

Now, it turns out that addition in the lsbit is actually linear, and so there will be 16 possible settings for the key bits that'll be consistent, but that's OK.

Now, we extend the attack to bits 0 and 1 of the addition; the addends and the sum are also functions of a known plaintext/ciphertext bits, and a handful of key bits, and so we go through those possibilities, and eliminate those which aren't consistent with the known plaintext/ciphertext pairs (and now that there's real nonlinearity, they'll be some considerable pruning).

I could go on, but it should be fairly obvious where to go from here...