Yesterday we had the Rump Session here at the Early Symmetric Cryptography Seminar of 2010. I gave a brief update about some experiments we ran against KTANTAN32. KTANTAN32 is a 32-bit blocksize block cipher which takes an 80-bit key. Its structure is quite simple, only two bits are updated in the internal state per round. The cipher has 254 rounds in total. We can break up to 65 rounds using 32 chosen plaintexts by applying the “correlated message” technique by Jean-Charles Faugère and Ludovic Perret with a SAT solver. We can break up to 113 rounds uing $\approx 2^{31}$ chosen plaintext-ciphertext pairs by applying Attack-A with a SAT solver. All this is not very exciting since we don’t even break half the number of rounds. Well, it’s a rump session presentation.

Update: I should add, what makes these attacks slightly interesting. The KTANTAN32 designers point out in their proposal that after 32 rounds every state bit has degree at least two. After another 16 rounds we can expect at least degree four. Yet, we are able to solve 62 rounds with a degree bound of two by using 32 plaintexts, i.e. we add pairs and reduce the degree (using a SAT solver we can go up to 65 rounds). For the differential-style attack, the interesting figure is not 113 but the fact that we use a 71 round characteristic, i.e. we mount a 113-71 = 42R attack. Of course, roughly speaking 16 rounds of KTANTAN32 are equivalent to one “traditional” block cipher round.