# LeakWatch

## 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 f_{a}, f_{b} and f_{c} 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 f_{c}. 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 f_{c} 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 f_{c}'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 f_{c} 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.

### References

- [GvVW09] Roel Verdult, Flavio D. Garcia and Josep Balasch. "Gone in 360 Seconds: Hijacking with Hitag2". 30th IEEE Symposium on Security and Privacy. 2009.
- [W06] I. C. Wiener. "Software optimized 48-bit Philips/NXP Mifare Hitag2 PCF7936/46/47/52 stream cipher algorithm". 2006-7.