[ISN] Academic Attacks on SAFER+

From: mea culpa (jerichoat_private)
Date: Wed Dec 30 1998 - 00:41:59 PST

  • Next message: mea culpa: "[ISN] Call for papers: The Black Hat Briefings '99"

    Forwarded From: "Jay D. Dyson" <jdysonat_private>
    Originally From: John Kelsey <kelseyat_private>
    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
    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
    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:
    Second Round:
    Third Round:
    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. 
    - - --John Kelsey, kelseyat_private / kelseyat_private
    NEW PGP print =  5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
    Subscribe: mail majordomoat_private with "subscribe isn".
    Today's ISN Sponsor: Internet Security Institute [www.isi-sec.com]

    This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 13:14:50 PDT