I just got back from vacation in time to see the brouhaha over S-1. My, my. So I'll describe an attack on S-1 which takes 2^32 known plaintexts and 2^64 operations, assuming that F, G, clear_family, and cipher_family are known (but arbitrary). Tradeoffs are possible: a similar attack breaks S-1 with 2^48 known plaintexts and 2^48 operations. This adds weight to the hypothesis that S-1 is a hoax (assuming that the NSA was trying to design a strong cipher!)... I should point out that this attack works for an arbitrary number of rounds. It shows that increasing the number of rounds will never make S-1 secure. To fix S-1, the key schedule must be repaired. Anyhow, here's the attack. Several people have noted that the S-1 round keys repeat every 5 rounds. I'll take advantage of this with an attack reminiscent of related-key techniques (but I don't need any related-keys, Mind you!). If P is a known plaintext, let P_i denote the intermediate block after i rounds. I'm going to look for a pair of matching plaintexts P,Q: a pair for which P_5 = Q_0. Then we'll have P_{5+j} = Q_j for all j. Pictorially: P_0 P_1 P_2 P_3 P_4 P_5 Q_0 P_6 Q_1 ... ... P_31 Q_26 P_32 Q_27 Q_28 Q_29 Q_30 Q_31 Q_32 The birthday paradox says that with 2^32 known plaintexts, there should be at a matching pair P,Q. If I can recognize it, I can exploit it as follows. Note that (P_0,Q_0) and (P_32,Q_32) are two known plaintext-ciphertext pairs for 5-round S-1. These two known plaintexts for 5-round S-1 are enough to find the 5 round subkeys by standard methods (since we know the inputs and outputs to almost all the F boxes in these two examples). Thus, each pair P,Q will suggest one key value, and the right (matching) pair will suggest the correct key value (which can be easily recognized with one trial decryption). I don't know how to recognize matching pairs directly, but I can try all 2^32 * 2^32 possible pairs, and I'm guaranteed to find the matching plaintext pair if there is one after 2^64 trial decryptions. That's the basic attack. Here's a sketch of how to trade off known plaintexts for time. I'd really like to be able to detect matching pairs easily, because then I'd be able to use a hash table (or sorted list) to find a matching pair more efficiently. So I'll note that I can detect matching pairs pretty accurately if P,Q are in a particular form. I'll construct an oracle which can quickly tell if two plaintext-ciphertext pairs (X,Y) (X',Y') for 5-round S-1 were enciphered with the same key, if they're in a special form. Let A,A' be the 32 bits from X,X' entering the F boxes in round 2; let B,B' be the 16 bits output from the F boxes in round 2; let C,D,C',D' be the 16 bits affected by the F boxes in round 2 from X,Y,X',Y' -- so that D = C ^ B = C ^ f(A ^ K_2) D' = C' ^ B' = C' ^ f(A' ^ K'_2). If K_2 = K'_2 and A = A', then D ^ C should equal D' ^ C'. So this is how I'll construct the oracle: it insists that (X,Y) (X',Y') be of a form so that A = A', and it reports that (X,Y) (X',Y') were enciphered with the same key when D ^ C = D' ^ C'. The oracle will always answer correctly if they were enciphered with the same key, and will answer incorrectly 2^{-16} of the time when the were enciphered with different keys. So now we are considering (X,Y) = (P_0,P_5) = (P_0,Q_0) and (X',Y') = (Q_27,Q_32) = (P_32,Q_32). The oracle's precondition means that 32 bits of P_0 equal a corresponding 32 bits of P_32. The tradeoff attack follows from this. Get 2^48 known plaintexts. Consider only those known plaintext-ciphertext pairs (P_0,P_32) which meet the 32 bit oracle precondition as possibilities for P. There will be 2^16 possibilities for P. Let Q range over all 2^48 possibilities. Then we expect there to be some right matching pair P,Q: the oracle is guaranteed to detect it, and also another 2^48 wrong pairs. Each possible pair P,Q will suggest a key value, so the wrong pairs can be filtered out with a total of 2^48 trial encryptions, leaving only the right pair and the right key value. This would seem to require 2^16 * 2^48 oracle computations since there are 2^16 values for P and 2^48 possibilities for Q. But wait: the oracle can be implemented more efficiently as a table lookup. Store all 2^16 possibilities for P in a lookup table, keyed on the 16 bit value D^C used by the oracle. For each Q, calculate the 16 bit value D' ^ C' and search in the table for a matching D ^ C value (which gives you a possible matching pair P,Q). This technique requires a total of 2^48 table lookups, 2^48 trial decryptions, 2^16 space, and 2^48 known plaintexts. Further tradeoffs between # of known plaintexts and time appear to be possible... I've ignored the issue of the G box throughout. Actually, it does change the number a little bit -- but just by random luck, the two G box outputs should match 1 in 2^2 times, so we only need to increase the complexity of this attack by about 2^2 to account for the G box. The G box didn't add much strength. ------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu