anoadragon453/correlation-attacks

Correlation attack on simple LSFR-based key sequence generator

Correlation Attacks

Given the layout of a 3-LFSR (Linear Feedback Shift Register) key sequence generator, and the combination function being that which picks the majority output bit from the 3 LFSRs, and finally a output stream, compute the keystream.

This can be done using a correlation attack given some number of plaintext and ciphertext outputs, and finding a correlation between output and one (or more) of the LFSRs.

---

Given the following keystream sequence:

01100110100110100101011111011111001001011111110001 10011101110111110110101010100100110011110001011011 11100110100110010100101111110011110100100000011110 1000101100011000111000111111101011111100110

Find key K, where K = tuple (k1, k2, k3), where ki is the initial state of each of the three LFSRs that comprise the sequence generator.

We are also given the polynomials representing these LFSRs:

L1 = 13, C1(D) = 1 + D + D^2 + D^4 + D^6 + D^7 + D^10 + D^11 + D^13 L2 = 15, C2(D) = 1 + D^2 + D^4 + D^6 + D^7 + D^10 + D^11 + D^13 + D^15 L3 = 17, C3(D) = 1 + D^2 + D^4 + D^5 + D^8 + D^10 + D^13 + D^16 + D^17

For a successful correlation attack, Pr(ui = zi) != 0.5 where ui is the bit generated by a single LFSR, and zi is a single bit of the keystream sequence, at least when in a finite field of 2.

This essentially means that there must be some correlation between ui and zi.

Quick refresher: The Hamming distance between two binary vectors x and y is defined to be the number of coordinates in which x and y differ. So if x = [0, 0, 1] and y = [1, 1, 1], then H(x, y) = 2.

Knowing that, consider the following definition:

probability p**\ = 1 - (H(u, z))/N where N is the length of each sequence

If the guessed initial state, u, is correct, p* === p, otherwise p* = 0.5

Thus, we can derive the following algorithm:

1. For each possible initial state, calculate p*.
2. Output the initial state for which p* most deviates from 1/2.

TODO: We will also plot each combinational pair of state vs. p* value on a graph. What we should notice is one point being significantly separated from the others. This outlier is the correct initial state.