Example: Hitag-2 Stream Cipher Design Weaknesses

Hitag-2 is a stream cipher used in several commercial RFID tags, including those embedded in many contactless car keys. It is structurally similar to its predecessor, Crypto-1 (which we analyse in another example). Hitag-2 consists of 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 Hitag-2 can be found in [VGB12]; a diagrammatical overview was also published by the pseudonymous person who first reverse-engineered the cipher [W06].

Like Crypto-1, Hitag-2 is a proprietary cipher, and before it was reverse-engineered, its design was a secret; however, 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 Hitag-2 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.)

As in the Crypto-1 example, 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 — 2, 3, 5, 6, 8, etc), we recover the polynomial used by Hitag-2's 48-bit LFSR; that is, we learn which bits are tapped to produce the cipher's keystream.