DeepSec 2018 Talk: Cracking HiTag2 Crypto – Weaponising Academic Attacks for Breaking and Entering – Kevin Sheldrake
HiTag2 is an Radio-Frequency Identification (RFID) technology operating at 125KHz. It is distinguished from many others in the same field by its use of 2-way communications for authentication and its use of encryption to protect the data transmissions – the majority of RFID technologies at 125KHz feature no authentication or encryption at all. As a result it has been widely used to provide secure building access and has also been used as the technology that implements car immobilisers.
In 2012, academic researchers Roel Verdult, Flavio D. Garcia and Josep Balasch published the seminal paper, ‘Gone in 360 Seconds: Hijacking with Hitag2’ that presented three attacks on the encryption system used in HiTag2; in 2016 Garcia et al presented a further attack in ‘Lock It and Still Lose It’. They implemented their attacks on the Proxmark 3 device (an RFID research and hacking tool) and gave several high-profile demonstrations, but didn’t release any of their code or tools. Since then, the forums supporting Proxmark 3 and RFIDler (another RFID hacking tool) have received many requests for implementations of these attacks, but until recently none had been forthcoming.
In my talk I explain how HiTag2 RFID works in detail, including the PRNG and the authentication and encryption protocols, and will present my own implementations of the attacks, written for RFIDler and supported by desktop computers. The first attack uses a nonce replay to misuse the integrity protection of the comms in order to allow access to the readable RFID tag pages without needing to know the key. The second, third and fourth attacks use time/memory trade-off brute force, cryptanalytic attacks and a fast correlation attack to recover the key, such that the contents of the read-protected pages can also be accessed. The attacks are weaponised and permit cloning of tags, and are available on the RFIDler github: https://github.com/ApertureLabsLtd/RFIDler
In order to implement these attacks I first had to understand them; a large part of my talk will be focused on explaining how the pseudo-random number generator (PRNG) and system initialisation works. The PRNG is based on a 48 bit linear feedback shift register (LFSR) which is tapped at 16 points to generate the feedback bit that is inserted when the register shifts; and is further tapped at 20 points and fed through a few functions to generate the output bit for each state. Each tag within a system and each reader within the same system will contain the same shared secrets – there is insufficient power (and probably a lack of will) to perform asymmetric crypto verification, such as Diffie-Hellman or RSA, hence symmetric encryption and therefore shared secrets. As such breaking any one component of a system will reveal the shared secrets that apply to the whole system.
The tag and the reader communicate when introduced in order to initialise their PRNGs to the same point. This is based on an initialisation process involving the tag’s unique ID, the shared secrets and a nonce, randomly generated by the reader. The reader encrypts the nonce and transmits it to the tag, that simultaneously decrypts it and further randomises its PRNG state. From this point onwards, when one party wishes to send encrypted data to the other, they simply extract a series of random bits from their PRNG (equal to the length of the data to send) and XOR this with the data to encrypt it. The receiving party extracts the same number of bits from its PRNG (equal to amount of encrypted data received) and XORs this with the encrypted data to decrypt it. This is essentially a stream cipher and only works because the PRNGs were initialised to the same state and remain in-step throughout the communication.
Unfortunately, as is the case with the vast majority of crypto systems, this system has a number of flaws. The first is that all the entropy within a communication comes from the reader in the form of the encrypted nonce. By eavesdropping on a communication and then emulating the reader it is possible to repeatedly initialise a tag to the same configuration by replaying the same encrypted nonce. Coupled with abuse of an integrity protection, this allows the generated key stream for the session to be extracted and then used to encrypt and decrypt communications with the tag.
Taking this further, the same process can be used to generate a large amount of key stream (2048 bits, for example). By generating a large table of PRNG states and the key stream they would generate (1.5TB in size) it is possible to look up the key stream in the table and find the matching PRNG state. From here it is then possible to roll the PRNG backwards and recover the secrets that were used to initialise it.
A problem related to the distribution of the taps for the output bits allows an attacker to reduce the complexity of the problem of brute forcing the secrets from 2^48 down to 2^35, making the problem achievable in ~16 minutes. This approach uses a correlation whereby earlier bits of the decrypted nonce affect the decryption of the later bits of it; tables of potential partial keys can be generated and enumerated quickly. This approach only attacks the reader without requiring a valid tag from the system, as long as the reader will respond to an attacker supplied tag (e.g. isn’t white-listed on tag UID).
Garcia et al’s later ‘fast correlation’ attack uses probability to guess the most likely partial PRNG states to generate the known output during the initialisation phase. This process starts with all guesses for the first 16 bits of the key and then expands each guess with a 0 and with a 1. All the guesses are ranked for how well they produce the expected output and are sorted such. Each is then expanded and the process repeated. When the number of guesses in the system exceeds a chosen limit (say 500,000) only the best guesses remain (250,000 in this case), each to be expanded into two new guesses for the next round. This approach uses far fewer traces of eavesdropped tokens and achieves its results in around 1 minute. Where it fails (as all probabilistic approaches will at times) the attack can be rerun with either more tokens (to provide better information for the engine) or with a larger table (so that more guesses remain in the system for longer).
While the above described attacks are all available on the RFIDler github, there are two further attacks that are worth a mention. Immler’s Breaking HiTag2 Revisited (2012) described a GPU brute force that can be implemented with relative ease. Almost the entire OpenCL kernel is provided in the annex so the attacker/researcher only needs to develop the kernel despatch code and fill in the obvious gaps in the kernel. In 2017, Benadjila et al converted Immler’s single-GPU on a single host approach into a multiple-GPU on multiple hosts approach and reduced the running time from 11 hours to 15 minutes, using Amazon’s EC2 infrastructure.
There are lots of interesting crypto attacks in the academic world and we would do well to understand them.
Kevin Sheldrake is a penetration tester and researcher who started working in the technical security field in 1997. Over the years, Kev has been a developer and system administrator of ‘secure’ systems, an infosec policy consultant, a penetration tester, a reverse engineer and an entrepreneur who founded and ran his own security consulting company. His current interests lies in tool development for better penetration testing, and he has specialised in IoT and crypto for a number of years.
He has a Masters degree, is a Chartered Engineer and, in the past, has been a CHECK Team Leader, a CISSP and held CLAS.
Kev has presented at 44CON, Troopers, DEFCON 4420, 441452 and 441392 on RFID crypto (Cracking HiTag2 Crypto); EMF Camp, DEFCON 4420 and 441452 on hacking embedded devices (Inside our Toys); presented on building debuggers for embedded devices at Securi-Tay (Phun with Ptrace()); and also presented a lengthy take down on the use of NLP in Social Engineering at DEFCON 4420 (Social Engineering LIES!). He has also presented regularly at his employer’s internal security conference, winning best talk in 2014 for ‘Embedded Nonsense’, a talk about hacking an IoT device and reversing its crypto, which he subsequently presented at Cyber Security Challenge.