---------- Forwarded message ---------- Subject: [ISN] Academic Attacks on SAFER+ Forwarded From: "Jay D. Dyson" <jdyson@techreports.jpl.nasa.gov> Originally From: John Kelsey <kelsey@plnet.net> I believe I have found two attacks on the SAFER+ version with 256-bit keys. While these attacks aren't practical, they demonstrate a weakness in the SAFER+ key schedule design, and may lead to more practical attacks in the future. The first attack is a modified meet-in-the-middle attack, requiring 2 known plaintexts and their corresponding ciphertexts, 2^{37} bytes of memory, and work equivalent to about 2^{241} SAFER+ encryptions. I have discussed this attack with Massey, and am fairly confident it really works. The second attack is a related-key attack, requiring 256 chosen plaintexts and their corresponding plaintexts encrypted under two related keys, and work equivalent to about 2^{216} SAFER+ encryptions. This is a much newer attack (about two days old), and I am less certain of it, but I believe it works. I will be writing these attacks up for publication fairly soon, but I wanted to announce them here to get the word out, and to see if anyone can either improve on them or find problems with them. Both attacks exploit two useful properties of SAFER+. First, I will describe the two useful properties, then I will describe the two attacks very briefly. The rest of this note assumes familiarity with SAFER+. 1.0. The Two Useful Properties of SAFER+ Consider SAFER+ with a 256-bit key. The key schedule is quite simple: We extend the key by a parity byte, getting a 33 byte extended key. We then use the 33 byte extended key to generate the entire sequence of subkeys. Each subkey byte is determined by only one key byte. If you know a given key byte, you know all the subkey bytes it determines; if you know a subkey byte, you know the key byte from which it was derived. SAFER+ rounds use 32 bytes of subkey each, in two blocks of 16 bytes. If the key bytes are k[0..32], then we have First Round: k[0..15] k[1..16] Second Round: k[2..17] k[3..18] Third Round: k[4..19] k[5..20] etc. This means that it takes quite a while in the encryption process for the last couple key bytes to affect the encryption. SAFER+ with a 256 bit key has 16 rounds and an output transformation. The output transformation uses only sixteen key bytes. Now, consider how many key bytes have affected the encryption at all after each round: After the first round (round 0), 17 key bytes have been used. After the second round, 19 key bytes have been used. After the third, 21. Continuing, we can see that it takes 9 (out of 16) rounds before SAFER+ has used all 32 key bytes. This allows both of my attacks. 0 17 1 19 2 21 3 23 4 25 5 27 6 29 7 31 8 all The other useful property is that we don't have to know all the key bytes to be able to recognize an output from a round of SAFER+ as being correct. Consider the situation where we know all but the last byte of the key of some round, and we know its input block. Each SAFER+ round consists of the keyed byte substitution layer, and the mixing layer. If we know k[0..14], but not k[15..16], then we end up knowing all but two bytes of the input into the mixing layer. The result is that we end up knowing *none* of the bytes of the output. However, we still know relationships between the bytes of the output. The matrix that describes the mixing layer makes it easy to see how to combine the output bytes into values that are not dependent on the unknown bytes of input. Now, consider a situation where we know all but the last two key bytes for round 0, and all but the first two key bytes for round 1. We can go backward through the mixing layer of round 1 (it's unkeyed), and then go back through the keyed byte substitution layer, learning all but two bytes of the output from round 0. We then make use of the trick described above. We will know relationships between the remaining known bytes of output from round 0, regardless of the unknown key bytes. 2.0. The Meet-in-the-Middle Attack The real insight that makes the low-memory attack work is that we can do meet-in-the-middle with two rounds whose key material we don't know all of. That is, we guess the keys for rounds 1-7 (numbering from one), which gives us all but two of the bytes for round 8. That's 29 key bytes guessed. We then compute some expressions in the output bytes of round 8 that don't rely on knowing the two unknown bytes of key, and that don't rely on knowing the two bytes of round 8's output that will depend on the two unknown key bytes when doing the guess on the other side. We guess the keys for the output transformation (16 bytes), plus the keys for rounds 10-16. That means 30 bytes of key guessed, and it also gives us enough information to get knowledge of all but two bytes of the output of round 8. We then compute those same expressions in those bytes. The result is that we can do the meet-in-the-middle at the output from round 8, despite not knowing all the key bytes used in round 8 or 9. Round | Key Bytes Guessed 1 17 2 19 3 21 4 23 5 25 6 27 7 29 8 29 (two unknown key bytes) - - -------------- (this is where the meet-in-the-middle happens) 9 30 (two unknown key bytes) 10 30 11 28 12 26 13 24 14 22 15 20 16 18 OX 16 That is, we can compute a set of bytes that are dependent only on the 29 bytes of key guessed from the top, or the 30 guessed from the bottom. Now, this would seem to take up a lot of memory to do this meet-in-the-middle attack. Fortunately, however, most of the key bytes guessed from the top are also guessed from the bottom. We thus mount the attack by first guessing all key values in common from the top and the bottom. We then do the meet-in-the-middle by trying all possible 2^{24} values from one side, and all possible 2^{32} values from the other. We compute this intermediate value that doesn't need any other key material from both sides, store our results in a sorted list, and look for duplicates from the top and bottom. With two plaintexts, it's easy to get more than 32 bytes of intermediate values, meaning that we don't expect to see any matches from incorrect guesses. 3.0. The Related-Key Attack The related-key attack works on a similar principle. My current attack is very simple: We choose a pair of keys, K,K^*, such that the keys differ only in the first two bytes; in these two bytes, we have a difference of 0x80. Under K we encrypt 256 plaintexts, P[i], each identical except with a different leftmost byte. Under K^* we encrypt 256 plaintexts, P[i]^*, with some fixed difference D<>0x80 from P[i] in the leftmost byte, and with fixed difference 0x80 in the next byte over. With probability about 1/2, we get at least one pair of plaintexts P[i],P[i]^*, whose values after two rounds are identical under the different keys. When this happens, their values are also identical after nine rounds. Now, we do our trick from the meet-in-the-middle attack, again, and guess the last 26 bytes of relevant key material. This lets us peel off the output transformation and the last five rounds, leaving us with access to the output from the eleventh round. We can peel off the PHT layer, since we know it and its inverse. We can then learn all but two of the bytes input to the eleventh round. We now know all but two bytes of the output from the tenth round, and we know a pair of texts for which only the last two bytes of the input to the tenth tound had changed. We can check to see if the values we've computed as being the outputs from the tenth round are consistent with this situation, and thus are consistent with this being a right pair. We expect to have to check 256 different pairs of texts in this way, each with work equivalent to 2^{208} SAFER+ encryptions. This leaves us with work equivalent to about 2^{216} encryptions, total, to learn 208/256 of the SAFER+ key bits. The remaining 48 bits can be brute-forced after these are known. We thus break SAFER+ with a differential related-key attack, using 2 related keys, 512 plaintexts encrypted under each key, and 2^{216} work. Comments? - - --John Kelsey, kelsey@counterpane.com / kelsey@plnet.net NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF -o- Subscribe: mail majordomo@repsec.com with "subscribe isn". Today's ISN Sponsor: Internet Security Institute [www.isi-sec.com]