Example: Crypto-1 Stream Cipher Design Weaknesses

Crypto-1 is a stream cipher used in several commercial RFID tags. At its heart is a 48-bit linear feedback shift register (LFSR), whose initial state is a secret, and three Boolean functions fa, fb and fc combined in such a way that they consume 20 tapped bits from the LFSR and produce 1 bit of output that is used to compute the cipher's keystream. Full details of the design of Crypto-1 can be found in [GvVW09]; a simple overview is also available on Wikipedia.

Crypto-1 is a proprietary cipher, and before it was reverse-engineered as part of [GvVW09], its design was a secret. Nevertheless, it is possible to learn information about its structure simply by loading different initial states into the LFSR and observing the output from the Boolean functions.

This example investigates how much information one learns about a particular bit of the LFSR's initial state by observing the output from fc. It contains a Java reimplementation of the parts of Crypto-1 described above. An LFSR is created with a randomly-generated initial state, and the first bit of the output from fc is computed. Another LFSR is created with the same initial state as before, but with the value of the bit at a specific index (specified as a command-line argument to the program) flipped with probability 0.5. The first bit of fc's output from this second cipher is then computed.

By executing LeakWatch 48 times and changing the index of the bit that might be flipped on each execution, we learn which indices of the LFSR are tapped and passed as input to the Boolean functions. The graph below shows each of the indices of the LFSR state on the x-axis, and the amount of information shared between that bit being flipped and both outputs from fc on the y-axis; informally, this can be seen as the "effect" the bit at each index has on the cipher's keystream. (Points that fall below the dashed green line are within the bounds for representing zero leakage; there is therefore no evidence of an information leak occurring for these indices.)

By reading off the indices on the x-axis where an information leak is detected (i.e., those whose points fall above the dashed green line — 9, 11, 13, 15, 17, etc), we recover the polynomial used by Crypto-1's 48-bit LFSR; that is, we learn which bits are tapped to produce the cipher's keystream.