-----BEGIN PGP SIGNED MESSAGE-----
[ To: AES SAFER+ Forum, sci.crypt, Perry's Crypto List ##
Date: 12/29/98 ##
Subject: Academic Attacks on SAFER+ ]
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, [EMAIL PROTECTED] / [EMAIL PROTECTED]
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBNok1riZv+/Ry/LrBAQHq/QP/bNhFMT1ZWxDUdybsamXK9hiwf01SIQWK
NQ7BznqPZZaDzyGC8I0EOZ4Pw1LNvkE34KUnE26/r95A0noLLbf9X2qcGgvK9AVp
4wRa3MXXbq59hQe11P2mBrGcoppV1ZA+HQmAysZ6dYM4lNXrxPaDohXJ5pSMflVS
s3z/iOgfZKc=
=ILee
-----END PGP SIGNATURE-----
