Challenge: break TOY-FEISTEL

Can you recover the key? TOY-FEISTEL is a tiny cipher built from the PRESENT S-box. It is deliberately weak: each level has a neat shortcut that beats brute force. Everything runs in your browser.

~/challenge/toy-feistel.txt The cipher

block    32 bits  =  L || R            (two 16-bit halves)
round i  (L, R)  ->  (R,  L xor F(R, K_i))
F(x, k)  =  rotl16( S(x xor k), 5 )     (rotate left by 5)
S        PRESENT S-box on each 4-bit nibble:
         x    : 0 1 2 3 4 5 6 7 8 9 A B C D E F
         S(x) : C 5 6 B 9 0 A D 3 E F 8 4 7 1 2
output   (L_r, R_r) after the last round   (no final swap)
key      K1 K2 ... K_r, each 16 bits; ciphertexts are written in hex

Prefer code? Open your browser console: toy.encrypt(0x24D13340, [0x1234, 0xABCD]), plus toy.F, toy.S, toy.Sinv, toy.rotl, toy.rotr.

Level 1 · 2 rounds, 32-bit key

One known plaintext/ciphertext pair. Brute force would try 2³² keys… but you will not need to.

#	plaintext	ciphertext
1	`24D13340`	`A3810A97`

Hints

Write out what each ciphertext half equals after two rounds, in terms of L₀, R₀, K1, K2.
The left half is L₂ = L₀ xor F(R₀, K1). You know everything here except K1, and F can be undone.
K1 = S^-1(rotr(L₂ xor L₀, 5)) xor R₀. Do the same for K2 using the right half.

Level 2 · 3 rounds, 48-bit key

Three known pairs. Brute force needs 2⁴⁸ tries. Find the key with about 2¹⁶ work.

#	plaintext	ciphertext
1	`FDF19870`	`43ADEB42`
2	`D4AB1877`	`A8879ED5`
3	`4E16BDF7`	`A445CECF`

Hints

If you knew K1, what would you know about the state after the first round?
With K1 fixed, the last two rounds are exactly Level 1: K2 and K3 follow from one pair.
Loop over all 2¹⁶ values of K1, derive K2 and K3 from pair 1, and keep the guess that also fits pairs 2 and 3. This is a guess-and-determine attack.

Hall of Fame

No one yet. Be the first!