Linear Cryptanalysis Challenge

Linear Cryptanalysis was invented by Matsui and Yamagishi. It’s a known plaintext method for breaking block ciphers with general applicability. However Matsui and Yamagishi invented it initially as a means of breaking the block cipher known as FEAL. Their original cryptanalysis can be found here.

The challenge is to break FEAL-4. Some useful additional lecture notes can be found here in MS Word format, or here in Postscript.

An executable findkey.exe implemented FEAL-4 using a secret internal key. It was used to generate the 200 random plaintexts/ciphertexts to be found in the file known.txt. Your job is to find the key. The key consists of K1, K2, K3, K4, K5 and K6, as described in the lecture notes.

The file findkey.c is the source code for this executable, BUT with the secret key generation code removed. However there is some code in there to get you started….

When compiled and run the program works something like this:-

H:> findkey 12 34 56 78 9c 6a 10 98

Plaintext= 12 34 56 78 9c 6a 10 98

Ciphertext= 91 e9 90 4a 60 af 28 91

Plaintext= 12 34 56 78 9c 6a 10 98

The input/output is in Hex.

Here 123456789c6a1098 is the plaintext. The high half Ph=12345678, the low half Pl=9c6a1098. The ciphertext is 91e9904a60af2891, with Ch=91e9904a and Cl= 60af2891