Key Schedule Weakness in SAFER+

J. Kelsey, B. Schneier, and D. Wagner

Second AES Candidate Conference, April 1999.

ABSTRACT: We analyze the key schedule of the SAFER+ block cipher, focusing on the poor diffusion of key material through the cipher when using SAFER+ with 256-bit keys. We develop a meet-in-the-middle attack on 256-bit SAFER+ requiring 12 x 224 bytes of memory, 3 known plaintext/ciphertext pairs, and work approximately equivalent to 2240 SAFER+ encryptions. We also develop a related-key attack on 256-bit SAFER+ requiring 3 x 232 chosen plaintexts under two keys with a chosen XOR relationship, and work approximately equivalent to 2200 SAFER+ encryptions. We consider a number of other key-schedule properties, such as equivalent keys, DES-style weak and semiweak keys, and key-dependent linear and differential characteristics. We fail to find any such properties, and offer some arguments why some of these are unlikely to exist. Finally, we propose an improvement to the SAFER+ key schedule which defends against our attacks, while causing no apparent weakening of the cipher to other attacks.

[full text – PDF (Acrobat)] [full text – Postscript]

Categories: Algorithm Analyses

Sidebar photo of Bruce Schneier by Joe MacInnis.