Consider the following generic type of secret key cryptosystem: An n-bit plaintext is first modified by a layer S_1 of different and unknown k-bit S-boxes, then by an unknown nxn affine transformation A_1 over GF(2), then by another layer S_2 of new unknown k-bit S-boxes, then by a different unknown affine transformation A_2, and finally by another layer S_3 of new unknown k-bit S-boxes. The only information available to the attacker is that the cryptosystem has this SASAS structure.

For n=128 and k=8, the effective key length of the 48 unknown S-boxes and the two affine mappings is over 100,000 bits, but in this talk we show how to break it in about $2^{29}$ time using about $2^{16}$ messages. The attack was verified with an actual implementation, which required less than a minute on a single PC.