RSA Cryptanalysis
Michael Walker
RSA Implementation
We implemented a version of the RSA algorithm as part of our project. RSA is a popular asymmetric block encryption method. The encryption method of RSA is based on properties of modular arithmetic, and the encryption strength is based on the difficult of factoring large primes.
In our implementation, we used a BigInt class to represent integers of arbitrary length as strings with overloaded operators. We used 64-bit blocks, which is typical for RSA encryption methods. Also, we chose typical prime digit lengths of 24-33 decimal digits, which resulted in n values of 48-66 digits. The n value is the product of two prime numbers, and is used in the public and private keys of RSA.
Breaking RSA Implementation
After completing our RSA implementation, we proposed a challenge to break messages encrypted with RSA. The paramemters of the challenge were simple. One team encrypts a secret message using our RSA implementation, and sends the message via email. A seperate team "intercepts" the message, and must decrypt the message.
The email message looked like this:
Date: Tue, 27 Mar 2001 22:05:41 -0500 (EST)
From: Shaun C. Arnold sca7m@cs.virginia.edu
As part of the game, we assume that the code-breakers have access to this email message, which includes the ciphertext and a timestamp. They also have access to our RSA implementation. You can find our implementation here. How would you break it?
Even with a smaller n size than normal, this message was not easily suceptable to cryptanalysis at first glance. Our cryptanalysis tools developed for simpler ciphers were not useful for this text, since it was not alphabetic.
RSA Attack Strategy
We chose to implment a type of timing attack on the RSA-encrypted message. The attack exploits a security hole in the prime number generation in our RSA implementation. This hole was pointed out by Gary McGrath during a talk he gave in our security class, and takes advantage of the predictibility in pseudo-random number generation.
The following code is a pseudocode version of our prime number generation:
main(){
BigInt P = GetPrime();
BigInt Q = GetPrime();
[
GetPrime( ) {
srand48( (unsigned int) time(0) );
BigInt N = rand_int( 1024, 1033 );
if( n % 2 == 0) { n = n + 1; }
while(!is_prime( N )) { N += 2; }
return N;
}
The random number generator is twice seeded by the time of day -- once for each prime P and Q. Given the timestamp of the email message and a few assumptions about the time the program was run, we can determine a rough estimate of the times at which the random number generator was seeded. From this set of times, we can brute-force search through them for the correct P and Q to generate the correct key.
The cracking team assumed that the program was run within 5 mintes of the email sending time. After some timing benchmarks, we determined that each prime number generation took between 14-82 seconds. This determined the approximate gap between random number seedings. We overestimated that the difference in times would be from 12-110 seconds, giving a range of about 100 seconds. Combining with the 5 minutes of possible start times (about 300 seconds), that generates a search space of 30,000 seeding combinations.
Although the 30,000 time seeding combinations is a relatively small search space to traverse, the actual time to produce the prime numbers significantly slowed our searching efforts. An average run to produce P and Q for a given set of seeding times could take up to 2 minutes on an average department machine. This meant that searching the entire search space would take approximately 42 days.
We realized that the RSA cracking procedure was highly parallizable. We used the Legion grid system testbed, Centurion , to run our cracking program in parallel. Centurion is a heterogeneous cluster of ~256 Intel and Alpha machines. We used 103 400-Mhz Intel Pentium IIs to run the cracking program in parallel. The parallel execution cut the running time from 42 days, to ~12 hours.
Results
After examining the crack program output, the decrypted text was plain to see:
Start: 985748522 Second: 985748581
>c`bW+^E^R#(SbM^]1Z^E^Bi=@=!;^LV\BQRY^G^P^PN0Uz^CY<}b^Vc)@R`+LT#^P,]^c>{^^YH+*^M85-^W#&[$K*^BS^E
Start: 985748522 Second: 985748582
Anyone who attempts to generate random numbers by
deterministic means is of course living in a state
of sin
John von Neumann
Start: 985748522 Second: 985748583
,*!F^E&/^F.>Y.^EUM^X^DAaO^C^AXT^[L/0>^PaSGy@^X^S5^PM5B^Rna^B^X?^V{DE^\C^T^QA WS^O7a'^Y0*
Conclusion
We have shown that the strength of powerful encryption methods like RSA depend heavily on the soundness of implementation. Complicated encryption techniques like RSA and 3-DES are especially suceptable to implementation errors, as we found. These errors can significantly reduce the complexity of the encryption method, and make them suceptable to attack.
