Crack me if you can: hardware acceleration bridging the gap between practical and theoretical cryptanalysis?: a Survey

ABSTRACT

Cryptanalysis is an essential part of cryptology. Not just is it useful to break ciphers for malicious applications, but it is also the basis for building secure ones. In fact almost all the ciphers still in use are trusted to be secure mainly due to the fact that many cryptanalysts are trying hard to break them publicly and failing. However, most of the time successful cryptanalytic results end up violating the cipher designers claims, but the attack itself remains theoretical due to the lack of enough resources/algorithms to efficiently implement it. For example, while the first practical SHA-1 collision was found in 2017, most of the ideas and vulnerabilities behind the attack had been discovered in 2005. The internet and IT industries didn't give much attention to the early theoretical results and it wasn't until 2016 that internet browsers starting getting rid of SHA-1. The leap from 2005 to 2017 was due to advancements in the attack algorithms, implementation techniques and hardware fabrication technologies. While hardware fabrication so far keeps on improving according to Moore's law, the other two aspects require a lot of research effort. In this survey, we touch on several examples of these efforts over the years. The survey is divided into three parts, cryptanalytic attacks designed with specific implementation requirements, previous cryptanalytic machines and quantum computers, the technology that promises to change how we think about cryptography and cryptanalysis.

References

1. Elaine Barker. 2016. Recommendation for key management part 1: General. NIST special publication (2016).
2. Sam Biddle. 2017. NYU ACCIDENTALLY EXPOSED MILITARY CODE-BREAKING COMPUTER PROJECT TO ENTIRE INTERNET. URL https://theintercept.com/2017/05/11/nyu-accidentally-exposed-military-code-braking-computer-project-to-entire-internet/ (2017).
3. Eli Biham and Rafi Chen. 2004. Near-collisions of SHA-0. In Annual International Cryptology Conference. Springer, 290--305.
4. Eli Biham, Rafi Chen, and Antoine Joux. 2015. Cryptanalysis of SHA-0 and Reduced SHA-1. Journal of Cryptology 28, 1 (2015), 110--160.
5. Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, and William Jalby. 2005. Collisions of SHA-0 and Reduced SHA-1. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 36--57.
6. Dan Boneh, Christopher Dunworth, and Richard J Lipton. 1995. Breaking DES Using a Molecular Computer. Proceedings of DIMACS workshop on DNA computing (1995).
7. Frank Carter. 2008. The Turing Bombe. Bletchley Park Trust.
8. Florent Chabaud and Antoine Joux. 1998. Differential collisions in SHA-0. In Annual International Cryptology Conference. Springer, 56--71.
9. Rafael Chen and Eli Biham. 2011. New Techniques for Cryptanalysis of Cryptographic Hash Functions. Ph.D. Dissertation. Computer Science Department, Technion.
10. Martin Cochran et al. 2007. Notes on the Wang et al. 263 SHA-1 Differential Path. IACR Cryptology ePrint Archive 2007 (2007), 474.
11. Christophe De Canniere, Florian Mendel, and Christian Rechberger. 2007. Collisions for 70-Step SHA-1: on the full cost of collision search. In International Workshop on Selected Areas in Cryptography. Springer, 56--73.
12. Christophe De Canniere and Christian Rechberger. 2006. Finding SHA-1 characteristics: General results and applications. In International Conference on the Theory and Application ofCryptology and Information Security. Springer, 1--20.
13. Whitfield Diffie and Martin E Hellman. 1977. Special feature exhaustive cryptanalysis of the NBS data encryption standard. Computer 10, 6 (1977), 74--84.
14. John Gilmore. 1998. Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design.
15. Evgeny A Grechnikov. 2010. Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics. IACR Cryptology ePrint Archive 2010 (2010), 413.
16. Tim Güneysu, Timo Kasper, Martin Novotnỳ, Christof Paar, and Andy Rupp. 2008. Cryptanalysis with COPACOBANA. IEEE Trans. Comput. 57, 11 (2008), 1498--1513.
17. Muhammad Hassan, Ayesha Khalid, Anupam Chattopadhyay, Christian Rechberger, Tim Güneysu, and Christof Paar. 2015. New asic/fpga cost estimates for sha-1 collisions. In Digital System Design (DSD), 2015 Euromicro Conference on. IEEE, 669--676.
18. Martin Hellman. 1980. A cryptanalytic time-memory trade-off. IEEE transactions on Information Theory 26, 4 (1980), 401--406.
19. Antoine Joux. 2009. Algorithmic cryptanalysis. CRC Press.
20. Antoine Joux and Thomas Peyrin. 2007. Hash functions and the (amplified) boomerang attack. In Annual International Cryptology Conference. Springer, 244--263.
21. Charanjit S Jutla and Anindya C Patthak. 2005. A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code. IACR Cryptology ePrint Archive 2005 (2005), 266.
22. Pierre Karpman. 2016. Analyse de primitives symétriques. Ph.D. Dissertation. Université Paris-Saclay.
23. Pierre Karpman, Thomas Peyrin, and Marc Stevens. 2015. Practical free-start collision attacks on 76-step SHA-1. In Annual Cryptology Conference. Springer, 623--642.
24. J Keller and B Seitz. 2012. A Hardware-Based Attack on the A5/1 Stream Cipher (2001). URL http://pv.fernuni-hagen.de/docs/apc2001-final.pdf. Accessed April (2012).
25. Sandeep Kumar, Christof Paar, Jan Pelzl, Gerd Pfeiffer, and Manfred Schimmler. 2006. Breaking ciphers with COPACOBANA-a cost-optimized parallel code breaker. In International Workshop on Cryptographic Hardware and Embedded Systems. Springer, 101--118.
26. Bjoern Lekitsch, Sebastian Weidt, Austin G Fowler, Klaus Mølmer, Simon J Devitt, Christof Wunderlich, and Winfried K Hensinger. 2017. Blueprint for a microwave trapped ion quantum computer. In Science Advances, Vol. 3. American Association for the Advancement of Science, e1601540.
27. Stéphane Manuel. 2008. Classification and generation of disturbance vectors for collision attacks against SHA-1. (2008).
28. Stéphane Manuel. 2011. Classification and generation of disturbance vectors for collision attacks against SHA-1. Designs, Codes and Cryptography 59, 1--3 (2011), 247--263.
29. Stéphane Manuel and Thomas Peyrin. 2008. Collisions on SHA-0 in one hour. In International Workshop on Fast Software Encryption. Springer, 16--35.
30. Nick Marinoff. 2018. Samsung Is Building ASIC Chips for Halong Mining. URL https://bitcoinmagazine.com/articles/samsung-building-asic-chips-halong-mining/ (2018).
31. Krystian Matusiewicz and Josef Pieprzyk. 2006. Finding good differential patterns for attacks on SHA-1. In Coding and Cryptography. Springer, 164--177.
32. Cameron McDonald, Philip Hawkes, and Josef Pieprzyk. 2009. Differential Path for SHA-1 with complexity O (252). IACR Cryptology ePrint Archive 2009 (2009), 259.
33. Florian Mendel, Norbert Pramstaller, Christian Rechberger, and Vincent Rijmen. 2006. The impact of carries on the complexity of collision attacks on SHA-1. In International Workshop on Fast Software Encryption. Springer, 278--292.
34. Florian Mendel, Christian Rechberger, and Vincent Rijmen. 2007. Update on SHA-1. rump session of CRYPTO 2007 (2007).
35. Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, Noboru Kunihiro, and Kazuo Ohta. 2006. Improved collision search for SHA-0. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 21--36.
36. Thomas Peyrin. 2008. Analyse de fonctions de hachage cryptographiques. Ph.D. Dissertation. PhD thesis, University of Versailles.
37. John M Pollard. 1978. Monte Carlo methods for index computation (ðİðžðİŚİJðİŚŚðİŚİ). Mathematics of computation 32, 143 (1978), 918--924.
38. Norbert Pramstaller, Christian Rechberger, and Vincent Rijmen. 2005. Exploiting coding theory for collision attacks on SHA-1. In IMA International Conference on Cryptography and Coding. Springer, 78--95.
39. Brian Randell. 1982. Colossus: Godfather of the computer. In The Origins of Digital Computers. Springer, 349--354.
40. Vincent Rijmen and Elisabeth Oswald. 2005. Update on SHA-1. In CryptographersâĂŽ Track at the RSA Conference. Springer, 58--71.
41. Mikolos Santha. 2018. Quantum cryptanalysis: How to break some classical cryptosystems with quantum computers?. In FWS01 Quantum Cryptography. Centre for Quantum Technologies, NUS Singapore and CNRS IRIF, Universite Paris Diderot France.
42. Mark Stamp and Richard M Low. 2007. Applied cryptanalysis: breaking ciphers in the real world. John Wiley & Sons.
43. Marc Stevens. 2013. New collision attacks on SHA-1 based on optimal joint local-collision analysis. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 245--261.
44. Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov. 2017. The first collision for full SHA-1. In Annual International Cryptology Conference. Springer, 570--596.
45. Marc Stevens, Pierre Karpman, and Thomas Peyrin. 2016. Freestart collision for full SHA-1. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 459--483.
46. Marc Martinus Jacobus Stevens et al. 2012. Attacks on hash functions and applications. Mathematical Institute, Faculty of Science, Leiden University.
47. Vikram Suresh, Sudhir Satpathy, and Sanu Mathew. 2018. Bitcoin mining hardware accelerator with optimized message digest and message scheduler datapath. US Patent App. 15/274,200.
48. Christopher Swenson. 2008. Modern cryptanalysis: techniques for advanced code breaking. John Wiley & Sons.
49. Eran Tromer. 2007. Hardware-based cryptanalysis.
50. Paul C Van Oorschot and Michael J Wiener. 1999. Parallel collision search with cryptanalytic applications. Journal of cryptology 12, 1 (1999), 1--28.
51. Xiaoyun Wang. 2006. Cryptanalysis of hash functions and potential dangers. In Invited Talk at the Cryptographer's Track at RSA Conference 2006.
52. Xiaoyun Wang, Andrew C Yao, and Frances Yao. 2005. Cryptanalysis on SHA-1. In Cryptographic Hash Workshop hosted by NIST.
53. Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. 2005. Finding collisions in the full SHA-1. In Annual international cryptology conference. Springer, 17--36.
54. Xiaoyun Wang, Hongbo Yu, and Yiqun Lisa Yin. 2005. Efficient collision search attacks on SHA-0. In Annual International Cryptology Conference. Springer, 1--16.
55. Jun Yajima, Terutoshi Iwasaki, Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Noboru Kunihiro, and Kazuo Ohta. 2008. A strict evaluation method on the number of conditions for the SHA-1 collision search. In Proceedings of the 2008 ACM symposium on Information, computer and communications security. ACM, 10--20.
56. Jun Yajima, Yu Sasaki, Yusuke Naito, Terutoshi Iwasaki, Takeshi Shimoyama, Noboru Kunihiro, and Kazuo Ohta. 2007. A new strategy for finding a differential path of SHA-1. In Australasian Conference on Information Security and Privacy. Springer, 45--58.

• Information systems

  • Data management systems

    • Data structures

      • Data layout

• Security and privacy

• Theory of computation