Linear Cryptanalysis

One bit cipher: Solo

This block cipher takes any one bit input blocks and outputs encrypted blocks using a one bit key. An unlimited number of blocks can be encrypted and decrypted with a one bit key using Solo. But the more blocks that are seen by an adversary, the easier it is to find the key. The Solo algorithm adds the key to the plaintext to get the ciphertext. Decryption subtracts the key from the ciphertext to get the plaintext. Only one round is done. This is the simplest type of encryption and the cryptanalysis is easy because of this simplicity.

Example :

plaintext p=0
key k=1
rounds r =1
cipher text c=p + k = 1

decrypt p= c - k

1 - 1 = 0 = p

The algorithm adds the key and plaintext so if their sum overflows to c=2, the ciphertext block size can be 2 bits.

The only known way to break this Solo cipher is to recognize a meaningful output after trying all possible keys. Linear cryptanalysis is also useful. The algorithm uses a forward function (+) and its inverse (-). Many other functions could have been used, but the inverse is not always needed.

Next week, the two bit block cipher will be defined as a split Feistel network, like DES, so that inverse functions are not needed.  Then a three bit cipher will be shown. As the days go by, wider blocks will be done and details will be shown for linear and differential cryptanalysis.

Quiz in 3 parts:
1 If the cipher text is 0, what is the key or the plaintext?
2 Show how linear cryptanalysis is done for Solo.
3 How many pairs of plaintext-ciphertext are available for each key?


Linear Cryptanalysis of Solo

The goal is to create a linear equation that gives the key when there are plenty of plaintext and ciphertext pairs. The Solo algorithm is known, so it is easy to get the right answer quickly. It is normal for the algorithm of a cipher to be public and the key to be secret. Knowledge of the algorithm is used to make up linear equations using the XOR function as the addition and subtraction function for single bits, with no carry.

Here are plaintext and ciphertext block pairs that the cryptanalyst knows from traffic:

p c
0 1
1 2

The XOR function has the symbol ^ in the following work. Even though the Solo algorithm uses + and - with carry, the XOR will be used to create a linear approximation and a reside number system is used so the result is calculated modulo 1 so the result has only one bit. The Solo algorithm is not equal to these linear equations, but that is not needed because this cryptanalysis is an approximation. This inexact method is used while a confidence level is developed based on how much agreement is seen in several simultaneous equations.

k = p1 ^ c1 = 0^1 mod 1 = 1
k = p2 ^ c2 =  1^2  mod 1= 1

These two simultaneous equations result in the key being this:
key = 1

Confidence is high because both equations agree.


February 26, 2012