Jorge Nakahara Jr A Linear Analysis of Blowfish an

A Linear Analysis of Blowfish and Khufu: 

A Linear Analysis of Blowfish and Khufu Jorge Nakahara Jr Unisantos, Brazil jorge_nakahara@yahoo.com.br

Outline: 

Outline The Khufu and Blowfish Block Ciphers Linear Cryptanalysis Linear Attacks on Blowfish Linear Attacks on Khufu Conclusions

The Khufu Block Cipher: 

The Khufu Block Cipher Block cipher with Feistel Network structure Designed by R.C.Merkle in 1989 64-bit blocks (plaintext/ciphertext) Variable-length key: up to 512 bits 8r rounds (1≤ r ≤ 8), where r is called octet (originally r = 2 was suggested) One key-dependent 8x32-bit S-box per octet

The Khufu Block Cipher: 

The Khufu Block Cipher

The Blowfish Block Cipher: 

The Blowfish Block Cipher Cipher with Feistel Network structure Designed by B. Schneier in 1993 64-bit blocks (plaintext/ciphertext) Variable-length key: 32 bits up to 448 bits 16 rounds Key-dependent 8x32-bit S-boxes and a P-table

The Blowfish Block Cipher: 

The Blowfish Block Cipher

Linear Cryptanalysis: 

Linear Cryptanalysis Developed by Mitsuru Matsui (Mitsubishi Corp.) Initially applied against DES (1990), FEAL-4 and FEAL-8 (1989) Known-plaintext (KP) attack setting Distinguisher tool: linear relation involving plaintext, key and ciphertext bits with non-uniform parity (away from ½) (nonzero) bias of linear relations

Linear Cryptanalysis: 

Linear Cryptanalysis number of known-plaintexts for high success rate attack is proportional to bias-2 general attack technique (applied to block and stream ciphers) variant techniques: differential-linear, multiple linear relations, linear hulls

Linear Attacks on Blowfish: 

Linear Attacks on Blowfish - unlike previous DC, our LC attacks do not require the S-boxes to be non-injective mappings - 8x32-bit S-boxes are key-dependent, but always non-surjective mappings we exploit linear relations of the form 0 across the S-boxes, where  is a non-zero bit mask. we choose  = 1 due to mixing of modular addition and exclusive-or in the round function,

Linear Attacks on Blowfish: 

Linear Attacks on Blowfish exploit the least significant bit positions (to avoid decreasing the bias due to carry and borrow bits) extend linear relations to full rounds, and to multiple rounds: iterative linear relations we have found 2-round iterative linear relations construction of the linear distinguishers was heavily influenced by the design of Blowfish

Linear Attacks on Blowfish: 

Linear Attacks on Blowfish we derive one-bit of information on the key-dependent P-table: (L0 + L2t).1 = (P1 + P2 + ...+ P2t+1).1 (R0 + R2t).1 = (P2 + P4 + ...+ P2t).1 where (Li, Ri) are the left and right halves of the i-th round block, and + is xor.

Linear Attacks on Blowfish: 

Linear Attacks on Blowfish the bias of linear relations depends on the key since the four S-boxes are key-dependent: weak (user) keys

Linear Attacks on Khufu: 

Linear Attacks on Khufu 8x32-bit key-dependent S-boxes again, S-boxes are non-surjective: the bit mask has the form 0, with  non-zero bit-rotation in each round is by a multiple of 8 bits this fact inspired rotation-invariant bit masks:  <<< 8t = 

Linear Attacks on Khufu: 

Linear Attacks on Khufu thus, the masks do not change if they are rotated by 8-bit amounts (in either direction) more precisely,  = mmmm, m  *256 we have looked for iterative linear relations we have found 2-round and 8-round iterative linear relations for rotation-symmetric masks

Linear Attacks on Khufu: 

Linear Attacks on Khufu

Linear Attacks on Khufu: 

Linear Attacks on Khufu ciphertext-only (CO) attacks: exploit linear relations of the form 80000000x, 00800000x, .... 80808080x and assuming the plaintext is ASCII text. CO attack is possible because of exclusive-or (diffusion is poor!)

Conclusions: 

Conclusions linear attacks on Blowfish and Khufu weak-key assumption (distinct from DC attack assumption) old, known attack technique on old ciphers, but new and better (known-plaintext and ciphertext-only) results, compared to previous attacks (DC, ID) that worked in a chosen-plaintext setting.

Conclusions: 

Conclusions