Cryptanalysis of the Full AES Using GPU-Like Special-Purpose Hardware

• Autorzy: Biryukov, A. , Großschädl, J.
• Języki publikacji: EN

Abstrakty

EN

The block cipher Rijndael has undergone more than ten years of extensive cryptanalysis since its submission as a candidate for the Advanced Encryption Standard (AES) in April 1998. To date, most of the publicly-known cryptanalytic results are based on reduced-round variants of the AES (respectively Rijndael) algorithm. Among the few exceptions that target the full AES are the Related-Key Cryptanalysis (RKC) introduced at ASIACRYPT 2009 and attacks exploiting Time- Memory-Key (TMK) trade-offs such as demonstrated at SAC 2005. However, all these attacks are generally considered infeasible in practice due to their high complexity (i.e. 2^99.5 AES operations for RKC, 2^80 for TMK). In this paper, we evaluate the cost of cryptanalytic attacks on the full AES when using special-purpose hardware in the form of multi-core AES processors that are designed in a similar way as modern Graphics Processing Units (GPUs) such as the NVIDIA GT200b. Using today's VLSI technology would allow for the implementation of a GPU-like processor reaching a throughput of up to 10^12 AES operations per second. An organization able to spend one trillion US$ for designing and building a supercomputer based on such processors could theoretically break the full AES in a time frame of as little as one year when using RKC, or in merely one month when performing a TMK attack. We also analyze different time-cost trade-offs and assess the implications of progress in VLSI technology under the assumption that Moore’s law will continue to hold for the next ten years. These assessments raise some concerns about the long-term security of the AES.

Słowa kluczowe

EN

advanced encryption standard; cryptanalysis; cryptanalytic hardware; graphics processing unit; performance and energy evaluation

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 3/4
• Strony: 221-237
• Opis fizyczny: Bibliogr. 45 poz.

Twórcy

autor

Biryukov, A.

autor

Großschädl, J.

• Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, 6, rue Richard Coudenhove-Kalergi, L–1359 Luxembourg, Luxembourg,

Bibliografia

• [1] ARS Technica: Researchers add a dash of salt to hard drives for capacities up to 18TB, Available online at http://arstechnica.com/gadgets/news/2011/10/researchers-increase-hard-drive-densitysixfold-with-salt.ars, 2011.
• [2] BBC News: US deficit hits record $1.4tn, Available online at http://news.bbc.co.uk/2/hi/8296079.stm, 2009.
• [3] Bernstein, D. J., Chen, H.-C., Chen, M.-S., Cheng, C.-M., Hsiao, C.-H., Lange, T., Lin, Z.-C., Yang, B.-Y.: The Billion-Mulmod-Per-Second PC, SHARCS '09: Special-Purpose Hardware for Attacking Cryptographic Systems, Lausanne, Switzerland, September 2009.
• [4] Bernstein, D. J., Chen, T.-R., Cheng, C.-M., Lange, T., Yang, B.-Y.: ECM on Graphics Cards, Advances in Cryptology - EUROCRYPT 2009 (A. Joux, Ed.), 5479, Springer Verlag, 2009, ISBN 978-3-642-01000-2.
• [5] Biham, E., Dunkelman, O., Keller, N.: Related-Key Boomerang and Rectangle Attacks, Advances in Cryptology - EUROCRYPT 2005 (R. Cramer, Ed.), 3494, Springer Verlag, 2005, ISBN 3-540-25910-4.
• [6] Biryukov, A.: The Boomerang Attack on 5 and 6-Round Reduced AES, Advanced Encryption Standard - AES 2004 (H. Dobbertin, V. Rijmen, A. Sowa, Eds.), 3373, Springer Verlag, 2005, ISBN 3-540-26557-0.
• [7] Biryukov, A., Khovratovich, D.: Related-Key Cryptanalysis of the Full AES-192 and AES-256, Advances in Cryptology - ASIACRYPT 2009 (M. Matsui, Ed.), 5912, Springer Verlag, 2009, ISBN 978-3-642-10365-0.
• [8] Biryukov, A., Khovratovich, D., Nikolic, I.: Distinguisher and Related-Key Attack on the Full AES-256, Advances in Cryptology - CRYPTO 2009 (S. Halevi, Ed.), 5677, Springer Verlag, 2009, ISBN 3-642-03355-1.
• [9] Biryukov, A., Mukhopadhyay, S., Sarkar, P.: Improved Time-Memory Trade-Offs with Multiple Data, Selected Areas in Cryptography - SAC 2005 (B. Preneel, S. E. Tavares, Eds.), 3897, Springer Verlag, 2006, ISBN 3-540-33108-5.
• [10] Biryukov, A., Nikolic, I.: Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others, Advances in Cryptology-EUROCRYPT 2010 (H. Gilbert, Ed.), 6110, Springer Verlag, 2010, ISBN 978-3-642-13189-9.
• [11] Biryukov, A., Shamir, A.: Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers, Advances in Cryptology - ASIACRYPT 2000 (T. Okamoto, Ed.), 1976, Springer Verlag, 2000, ISBN 3-540-41404-5.
• [12] Bos, J. W., Kleinjung, T., Niederhagen, R., Schwabe, P.: ECC2K-130 on Cell CPUs, Progress in Cryptology - AFRICACRYPT 2010 (D. J. Bernstein, T. Lange, Eds.), 6055, Springer Verlag, 2010, ISBN 978-3-642-12677-2.
• [13] Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption Standard, Springer Verlag, 2002, ISBN 3-540-42580-2.
• [14] Electronic Frontier Foundation: Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design, O'Reilly Media, 1998, ISBN 1-56592-520-3.
• [15] Ferguson, N., Kelsey, J., Lucks, S., Schneier, B., Stay, M.,Wagner, D.,Whiting, D.: Improved Cryptanalysis of Rijndael, Fast Software Encryption - FSE 2000 (B. Schneier, Ed.), 1978, Springer Verlag, 2001, ISBN 3-540-41728-1.
• [16] Geiselmann,W., Januszewski, F., K¨opfer, H., Pelzl, J., Steinwandt, R.: A Simpler SievingDevice: Combining ECM and TWIRL, Information Security and Cryptology - ICISC 2006 (M. S. Rhee, B. Lee, Eds.), 4296, Springer Verlag, 2007, ISBN 3-540-49112-0.
• [17] Geiselmann,W., Steinwandt, R.: Non-Wafer-Scale Sieving Hardware for the NFS: Another Attempt to Cope with 1024-Bit, Advances in Cryptology - EUROCRYPT 2007 (M. Naor, Ed.), 4515, Springer Verlag, 2007, ISBN 3-540-72539-8.
• [18] Gilbert, H., Minier, M.: A Collision Attack on 7 Rounds of Rijndael, Proceedings of the 3rd Advanced Encryption Standard Candidate Conference, National Institute of Standards and Technology, 2000.
• [19] Gorski, M., Lucks, S.: New Related-Key Boomerang Attacks on AES, Progress in Cryptology - INDOCRYPT 2008 (D. Roy Chowdhury, V. Rijmen, A. Das, Eds.), 5365, Springer Verlag, 2008, ISBN 978-3-540-89753-8.
• [20] Graves, R. E.: High Performance Password Cracking by Implementing Rainbow Tables on NVIDIA Graphics Cards (IseCrack), M.Sc. Thesis, Iowa State University, Ames, IA, USA, 2008.
• [21] Güneysu, T., Kasper, T., Novotny, M., Paar, C., Rupp, A.: Cryptanalysis with COPACOBANA, IEEE Transactions on Computers, 57(11), November 2008, 1498-1513.
• [22] Hellman, M. E.: A Cryptanalytic Time-Memory Tradeoff, IEEE Transactions on Information Theory, 26(4), July 1980, 401-406.
• [23] Hodjat, A., Verbauwhede, I.: Speed-Area Trade-Off for 10 to 100 Gbits/s Throughput AES Processor, Proceedings of the 37th Asilomar Conference on Signals, Systems, and Computers (ACSSC 2003), 2, IEEE, November 2003.
• [24] Hodjat, A., Verbauwhede, I.: Area-throughput trade-offs for fully pipelined 30 to 70 Gbits/s AES processors, IEEE Transactions on Computers, 55(4), April 2006, 366-372.
• [25] Kahn, D.: The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet, Rev. sub. edition, Scribner, 1996, ISBN 0-684-83130-9.
• [26] Kim, J., Hong, S., Preneel, B.: Related-Key Rectangle Attacks on Reduced AES-192 and AES-256, Fast Software Encryption- FSE 2007 (A. Biryukov, Ed.), 4593, Springer Verlag, 2007, ISBN 978-3-540-74617-1.
• [27] Kumar, S., Paar, C., Pelzl, J., Pfeiffer, G., Schimmler, M.: Breaking Ciphers with COPACOBANA - A Cost-Optimized Parallel Code Breaker, Cryptographic Hardware and Embedded Systems - CHES 2006 (L. Goubin,M. Matsui, Eds.), 4249, Springer Verlag, 2006, ISBN 3-540-46559-6.
• [28] Kwong, R.: TSMC warns Moore's law may have 10 years left, Fiancial Times Tech Blog, available online at http://blogs.ft.com/techblog/2010/04/tsmc-warns-moores-law-may-have-10-years-left, April 2010.
• [29] Lu, J., Dunkelman, O., Keller, N., Kim, J.: New Impossible Differential Attacks on AES, Progress in Cryptology - INDOCRYPT 2008 (D. Roy Chowdhury, V. Rijmen, A. Das, Eds.), 5365, Springer Verlag, 2008, ISBN 978-3-540-89753-8.
• [30] Mentens, N., Batina, L., Preneel, B., Verbauwhede, I. M.: Time-Memory Trade-Off Attack on FPGA Platforms: UNIX Password Cracking, Reconfigurable Computing: Architectures and Applications - ARC 2006 (K. Bertels, J. M. Cardoso, S. Vassiliadis, Eds.), 3985, Springer Verlag, 2006.
• [31] Meurice de Dormale, G., Bulens, P., Quisquater, J.-J.: Collision Search for Elliptic Curve Discrete Logarithm over GF(2m) with FPGA, Cryptographic Hardware and Embedded Systems - CHES 2007 (P. Paillier, I. Verbauwhede, Eds.), 4727, Springer Verlag, 2007.
• [32] Nohl, K., Tews, E.,Weinmann, R.-P.: Cryptanalysis of the DECT Standard Cipher, Fast Software Encryption - FSE 2010 (S. Hong, T. Iwata, Eds.), 6147, Springer Verlag, 2010, ISBN 978-3-642-13857-7.
• [33] NVIDIA Corporation: GeForce GTX 285: A Powerful Single GPU for Gaming and Beyond, Specification, available online at http://www.nvidia.com/object/product_geforce_gtx_285_us.html, 2010.
• [34] NVIDIA Corporation: GeForce GTX 295: A Powerful Dual Chip Graphics Card for Gaming and Beyond, Specification, available online at http://www.nvidia.com/object/product_geforce_gtx_295_us.html, 2010.
• [35] Pomerance, C. B., Smith, J. W., Tuler, R. S.: A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Algorithm, SIAM Journal on Computing, 17(2), April 1988, 387-403.
• [36] Samsung Electronics Co. Ltd.: Samsung and Siltronic Start Joint Production of 300mmWafers in Singapore, Press release, available online at http://www.samsung.com/us/aboutsamsung/news/newsIrRead.do?news_ctgry=irnewsrelease&news_seq=9345, 2008.
• [37] Scientific American: Warm water flowed through supercomputers to cool down their heat, Available online at http://www.scientificamerican.com/article.cfm?id=microchannel-warm-liquid-cooling, 2010.
• [38] Shamir, A.: Factoring Large Numbers with the TWINKLE Device (Extended Abstract), Cryptographic Hardware and Embedded Systems - CHES '99 (C¸ . K. Koc¸, C. Paar, Eds.), 1717, Springer Verlag, 1999, ISBN 3-540-66646-X.
• [39] Shamir, A., Tromer, E.: Factoring Large Numbers with the TWIRL Device, Advances in Cryptology - CRYPTO 2003 (D. Boneh, Ed.), 2729, Springer Verlag, 2003, ISBN 3-540-40674-3.
• [40] Singh, S.: The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Anchor Books, 2000, ISBN 0-385-49532-3.
• [41] Western Digital Corporation: WD Caviar Black Desktop Hard Drives, Specification sheet, available for download at http://www.wdc.com/wdproducts/library/SpecSheet/ENG/2879-701276.pdf, 2011.
• [42] Wikipedia: Military Budget of the United States, Available online at http://en.wikipedia.org/wiki/Military_budget_of_the_United_States, 2010.
• [43] Wikipedia: Orders of Magnitude (Power), Available online at http://en.wikipedia.org/wiki/Orders_of_magnitude_(power), 2010.
• [44] Wilcox, J. E.: Solving the Enigma: History of the Cryptanalytic Bombe, Center for Cryptologic History, National Security Agency, 2001,
• [45] Wood, R.,Williams,M., Kavcic, A.,Miles, J.: The feasibility of magnetic recording at 10 Terabits per square inch on conventional media, IEEE Transactions on Magnetics, 45(2), February 2009, 917-923