| Home Page |
Research projects on applications of parallel computing in cryptography:
Conference sessions on applications of parallel computing in cryptography:
Research in cryptography is starting to expand in a new direction.
Hitherto, most cryptanalytic research has consisted of identifying theoretical attacks on block ciphers, stream ciphers, and one-way hash functions. The attacks have been only theoretical, and cannot actually be carried out, because the computational requirements preclude obtaining the answer in a practical amount of time. For example, a generic brute force attack on a cipher requires O(2^{n}) operations to recover the encryption key, where n is the key size in bits; modern ciphers, such as the Advanced Encryption Standard (AES) [1], have key sizes of 128 bits or larger. A generic brute force collision search on a hash function requires O(2^{n/2}) operations to find a collision, where n is the hash size in bits; modern hash algorithms, such as SHA-1 and SHA-2 [2], have hash sizes of 160 bits or larger. A generic attack requiring 2^{80} or 2^{128} operations would take too long to be practical.
Since generic attacks take too long, much cryptographic research is devoted to finding specific attacks that take less time than brute force. For example, attacks on AES have been published that find the key with 2^{176} operations for a 192-bit key and 2^{119} operations for a 256-bit key [3]. A SHA-1 attack was published that finds a collision with 2^{69} operations for a 160-bit hash size [4]; the attack was later improved to require 2^{52} operations [5]. In addition, researchers seek attacks on reduced-strength versions of ciphers and hash functions. For example, attacks on reduced-strength versions of AES have been published that find the 256-bit key with 2^{39} operations for AES reduced to 9 mixing rounds and 2^{45} operations for AES reduced to 10 mixing rounds (the full-strength version has 14 mixing rounds) [6].
Two trends are in effect. As newer and more powerful cryptanalytic attacks are discovered, the number of operations required to carry out the attacks is decreasing. At the same time, our machines' computational capabilities are increasing. The latter trend is especially apparent with parallel computers, which allow multiple processors to carry out different portions of a computation at the same time. We have now reached the point where the two trends are starting to intersect, such that cryptanalytic attacks that were formerly only theoretical are now practical. For example, my student Benjamin Bloom and I recently concluded a study where we did more than 2^{45} evaluations of the CubeHash one-way hash function on a parallel computer [7], and other large-scale parallel cryptographic computations have been published [8, 9, 10].
Accordingly, there is increasing interest in empirical cryptographic research using parallel computers, in additional to theoretical cryptographic research. However, this research area is just beginning, and not much has been published yet. My goal is to make RIT a center of innovation and excellence in what I call "Parallel Crypto" -- the emerging research area of applying parallel computing to solve large-scale cryptographic problems.
[1] | Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197. November 26, 2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf |
[2] | Secure Hash Standard. Federal Information Processing Standards Publication 180-2. August 1, 2002. http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf |
[3] | A. Biryukov and D. Khovratovich. Related-key cryptanalysis of the full AES-192 and AES-256. May 29, 2009. https://www.cryptolux.org/mediawiki/uploads/1/1a/Aes-192-256.pdf |
[4] | X. Wang, Y. Yin, and H. Yu. Finding collisions in the full SHA-1. In Advances in Cryptology -- CRYPTO 2005, 2005. |
[5] | C. McDonald, P. Hawkes, and J. Pieprzyk. Differential path for SHA-1 with complexity O(2^{52}). Cryptology ePrint Archive, Report 2009/259, June 1, 2009. http://eprint.iacr.org/2009/259 |
[6] | A. Biryukov, O. Dunkelman, N. Keller, D. Khovratovich, and A. Shamir. Key recovery attacks of practical complexity on AES variants with up to 10 rounds. 2009. https://www.cryptolux.org/mediawiki/uploads/3/38/Fast_attack_on_reduced_AES-256.pdf |
[7] | B. Bloom and A. Kaminsky. Single block attacks and statistical tests on CubeHash. Cryptology ePrint Archive, Report 2009/407, August 21, 2009. http://eprint.iacr.org/2009/407 |
[8] | M. Stevens, A. Lenstra, and B. de Weger. Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. In Advances in Cryptology -- EUROCRYPT 2007, pages 1-22, 2007. |
[9] | M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D. Osvik, and B. de Weger. Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate. In Advances in Cryptology -- CRYPTO 2009, pages 55-69, 2009. |
[10] | D. Bernstein, T. Lange, C. Peters, R. Niederhagen, and P. Schwabe. FSBday: Implementing Wagner's generalized birthday attack against the SHA-3 candidate FSB. Cryptology ePrint Archive, Report 2009/292, June 17, 2009. http://eprint.iacr.org/2009/292 |
| Home Page |