Hitag 2 hell - brutally optimizing guess-and-determine attacks
Abstract
Cryptographic guess-and-determine (GD) attacks are occasionally mentioned in the literature, but most articles describe conceptual attack optimization while implementation details are seldom discussed. Therefore, we present in this paper not only a conceptual attack optimization, but also a fully detailed design strategy to optimize a general bit-sliced exhaustive search implementation. To demonstrate the applicability of our contribution we present a highly optimized practical brute-force attack on the Hitag2 stream cipher using a guess-and-determine approach. Our implementation explores the full 48-bit search space on a consumer desktop PC with one GPU in approximately 1 minute. The work is specifically effective to recover secret keys from the widely deployed Hitag2 Remote Keyless Entry (RKE) system. Compared to the most practical Hitag2 RKE attack published in the literature, our implementation is more than 500 times faster. Furthermore, our approach has a 100% success rate with only two captured RF frames and is extremely practical compared to previously published unrealistic sat-solver, cube cryptanalysis and correlation attacks which require hundreds of traces or truly random nonces. We fully release our source code as reference material for related research in the future.
References
[1]
Ross J Anderson. Tree functions and cipher systems. Cryptologia, 15(3):194-202, 1991.
[2]
Ryad Benadjila, Mathieu Renard, José Lopes-Esteves, and Chaouki Kasmi. One car, two frames: Attacks on Hitag-2 remote keyless entry systems revisited. In 11th USENIX Workshop on Offensive Technologies (WOOT 17), Vancouver, BC, 2017. USENIX Association.
[3]
Eli Biham. A fast new DES implementation in software. In 4th International Workshop on Fast Software Encryption (FSE 1997), volume 1267 of Lecture Notes in Computer Science, pages 260-272. Springer-Verlag, 1997.
[4]
Andrey Bogdanov. Attacks on the KeeLoq block cipher and authentication systems. In 3rd Conference on RFID Security (RFIDSec 2007), volume 2007, 2007.
[5]
Vadim Bulavintsev, Alexander Semenov, and Oleg Zaikin. Implementation of a brute force attack on the a5/1 keystream generator in a GPU-based volunteer computing project. In Proceedings of the Third International Conference on BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017), volume 3, pages 94-101, 2017.
[6]
Vadim Bulavintsev, Alexander Semenov, Oleg Zaikin, and Stepan Kochemazov. A bitslice implementation of andersons attack on A5/1. Open Engineering, 8(1):7-16, 2018.
[7]
Nicolas T. Courtois, Sean O'Neil, and Jean-Jacques Quisquater. Practical algebraic attacks on the Hitag2 stream cipher. In 12th Information Security Conference (ISC 2009), volume 5735 of Lecture Notes in Computer Science, pages 167-176. Springer-Verlag, 2009.
[8]
Benedikt Driessen, Ralf Hund, Carsten Willems, Carsten Paar, and Thorsten Holz. Don't trust satellite phones: A security analysis of two satphone standards. In 33rd IEEE Symposium on Security and Privacy (S&P 2012), pages 128-142. IEEE Computer Society, 2012.
[9]
Xiutao Feng, Jun Liu, Zhaocun Zhou, Chuankun Wu, and Dengguo Feng. A byte-based guess and determine attack on SOSEMANUK. In 16th International Conference on the Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT 2010), volume 6477 of Lecture Notes in Computer Science, pages 146-157. Springer-Verlag, 2010.
[10]
Flavio D. Garcia, Gerhard de Koning Gans, Ruben Muijrers, Peter van Rossum, Roel Verdult, Ronny Wichers Schreur, and Bart Jacobs. Dismantling MIFARE Classic. In 13th European Symposium on Research in Computer Security (ESORICS 2008), volume 5283 of Lecture Notes in Computer Science, pages 97-114. Springer-Verlag, 2008.
[11]
Flavio D. Garcia, Gerhard de Koning Gans, Roel Verdult, and Milosch Meriac. Dismantling iClass and iClass Elite. In 17th European Symposium on Research in Computer Security (ESORICS 2012), volume 7459 of Lecture Notes in Computer Science, pages 697-715. Springer-Verlag, 2012.
[12]
Flavio D. Garcia, David Oswald, Timo Kasper, and Pierre Pavlidès. Lock it and still lose it - on the (in)security of automotive remote keyless entry systems. In 25th USENIX Security Symposium (USENIX Security 2016), pages 929-944. USENIX Association, 2016.
[13]
Praveen S Gauravaram and William L Millan. Improved attack on the cellular authentication and voice encryption algorithm (CAVE). In Cryptographic Algorithms and their Uses (CAU 2004), pages 1-13. Queensland University of Technology, 2004.
[14]
Jovan Dj Golić. On the security of nonlinear filter generators. In 3rd International Workshop on Fast Software Encryption (FSE 1996), volume 1039 of Lecture Notes in Computer Science, pages 173-188. Springer-Verlag, 1996.
[15]
Jovan Dj. Golić. Cryptanalysis of alleged A5 stream cipher. In 16th International Conference on the Theory and Application of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT 1997), volume 1233 of Lecture Notes in Computer Science, pages 239-255. Springer-Verlag, 1997.
[16]
S.W. Golomb. Shift Register Sequences. Holden-Day Series in Information Systems. Holden-Day, 1967.
[17]
El Groth. Generation of binary sequences with controllable complexity. IEEE Transactions on Information Theory, 17(3):288-296, 1971.
[18]
Philip Hawkes and Gregory G Rose. Exploiting multiples of the connection polynomial in word-oriented stream ciphers. In 6th International Conference on the Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT 2000), volume 1976 of Lecture Notes in Computer Science, pages 303-316. Springer-Verlag, 2000.
[19]
Philip Hawkes and Gregory G Rose. Guess-and-determine attacks on SNOW. In 9th International Workshop on Selected Areas in Cryptography (SAC 2002), volume 2595 of Lecture Notes in Computer Science, pages 37-46. Springer-Verlag, 2003.
[20]
Vincent Immler. Breaking hitag 2 revisited. In 2nd International Conference on Security, Privacy, and Applied Cryptography Engineering (SPACE 2012), volume 7644 of Lecture Notes in Computer Science, pages 126-143. Springer-Verlag, 2012.
[21]
Edwin Key. An analysis of the structure and complexity of nonlinear binary sequence generators. IEEE Transactions on Information Theory, 22(6):732-736, 1976.
[22]
GJ Kuhn. Algorithms for self-synchronizing ciphers. In 1st Southern African Conference on Communications and Signal Processing (COMSIG 1988), pages 159-164. IEEE, 1988.
[23]
Charles Eric LaForest. High-speed soft-processor architecture for FPGA overlays. PhD thesis, University of Toronto (Canada), 2015.
[24]
Mitsuru Matsui and Junko Nakajima. On the power of bitslice implementation on intel core2 processor. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 121-134. Springer, 2007.
[25]
Karsten Nohl, Erik Tews, and Ralf-Philipp Weinmann. Cryptanalysis of the DECT standard cipher. In 17th International Workshop on Fast Software Encryption (FSE 2010), volume 6147 of Lecture Notes in Computer Science, pages 1-18. Springer-Verlag, 2010.
[26]
Enes Pasalic. On guess and determine cryptanalysis of LFSR-based stream ciphers. IEEE Transactions on Information Theory, 55(7):3398-3406, 2009.
[27]
Vera S Pless. Encryption schemes for computer confidentiality. IEEE Transactions on Computers, 100(11):1133-1136, 1977.
[28]
Bruce Schneier. Applied Cryptography (2Nd Ed.): Protocols, Algorithms, and Source Code in C. John Wiley & Sons, Inc., New York, NY, USA, 1995.
[29]
Mate Soos, Karsten Nohl, and Claude Castelluccia. Extending SAT solvers to cryptographic problems. In 12th International Conference on Theory and Applications of Satisfiability Testing (SAT 2009), volume 5584 of Lecture Notes in Computer Science, pages 244-257. Springer-Verlag, 2009.
[30]
Siwei Sun, Lei Hu, Yonghong Xie, and Xiangyong Zeng. Cube cryptanalysis of Hitag2 stream cipher. In 10th International Conference on Cryptology and Network Security (CANS 2011), volume 7092 of Lecture Notes in Computer Science, pages 15-25. Springer-Verlag, 2011.
[31]
Roel Verdult. The (in)security of proprietary cryptography. PhD thesis, Radboud University, The Netherlands and KU Leuven, Belgium, April 2015.
[32]
Roel Verdult, Flavio D. Garcia, and Josep Balasch. Gone in 360 seconds: Hijacking with Hitag2. In 21st USENIX Security Symposium (USENIX Security 2012), pages 237-252. USENIX Association, 2012.
[33]
Roel Verdult, Flavio D. Garcia, and Bariş Ege. Dismantling megamos crypto: Wirelessly lockpicking a vehicle immobilizer. In 22nd USENIX Security Symposium (USENIX Security 2013), pages 703-718. USENIX Association, 2015.
[34]
Petr Štembera and Martin Novotny. Breaking Hitag2 with reconfigurable hardware. In 14th Euromicro Conference on Digital System Design (DSD 2011), pages 558-563. IEEE Computer Society, 2011.
[35]
David Wagner, Leone Simpson, Ed Dawson, John Kelsey, William Millan, and Bruce Schneier. Cryptanalysis of ORYX. In 5th International Workshop on Selected Areas in Cryptography (SAC 1998), volume 1556 of Lecture Notes in Computer Science, pages 631-631. Springer-Verlag, 1999.
[36]
Bin Zhang and Dengguo Feng. New guess-and-determine attack on the self-shrinking generator. In 12th International Conference on the Theory and Application of Cryptology and Information Security, Advances in Cryptology (ASIACRYPT 2006), volume 4284 of Lecture Notes in Computer Science, pages 54-68. Springer-Verlag, 2006.
Recommendations
Guess and Determine Attack on Trivium Family
EUC '10: Proceedings of the 2010 IEEE/IFIP International Conference on Embedded and Ubiquitous ComputingTrivium is a hardware profile finalist of eSTREAM project. It is a synchronous bit-oriented stream cipher. The cipher’s internal state has 288 bits. Bivium is a simplified version of Trivium with a smaller internal state. Both algorithms provide the ...
Preimage Attacks on Reduced Tiger and SHA-2
Fast Software EncryptionThis paper shows new preimage attacks on reduced Tiger and SHA-2. Indesteege and Preneel presented a preimage attack on Tiger reduced to 13 rounds (out of 24) with a complexity of 2128.5. Our new preimage attack finds a one-block preimage of Tiger ...
Guess and Determine Attacks on Filter Generators—Revisited
Although there are many different approaches used in cryptanalysis of nonlinear filter generators, the selection of tap positions has not received enough attention yet. In this paper we examine the security of nonlinear filter generators that output ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
USENIX Association
United States
Publication History
Published: 13 August 2018
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Jan 2025