PDA

View Full Version : Beginners question

Morin
November 15th, 2001, 16:05
Hello everybody!

I have a small beginners question I was hoping someone might be able to help me out on. I've started looking into cryptography a bit and have been finding it very interesting. The concepts and math behind the algorithms are initially difficult but I'm getting there slowly, and more importantly enjoying it.

My question though pertains to breaking implementations of various algorithms. I've seen many places where people talk about an implementation being broken due to a weak random number generator. It may be my own lack of knowledge thats preventing me from understanding this but I can't for the life of me figure out how you could utilize the fact that a weak generator was used to break an implementation. Even more then that, how would one go about realizing that the number generator used in the first place was weak? Any insight you guys could give about this kind of stuff would be of great help.

Thanks!

Kythen
November 15th, 2001, 19:08
Well, a good many algorithms use random number generators for getting prime numbers or other values used inside the algorithm. If you have a RNG that has a limited range for it's outputs, you can exploit that fact when brute forcing a key or value in the algorithm you're trying to break. For example, say you have some RSA implementation you're trying to break. Many times N will be too big to do any practical brute-forcing. But say the programmer used the normal C/C++ rand() function when making the primes. rand() outputs a 32-bit number. So now, all you have to do is brute force all the possible outputs of that rand() function and run them through the prime generator until you get the correct one(s). Real scenarios that you run into will vary of course, but this should give you an idea of why RNG's are a prime target for crypto breaking

mike
November 15th, 2001, 22:56
Dave Wagner and Ian broke Netscape's SSL because they initialized the RNG with the timer, and the time was stamped on the packet. Quickbooks uses DES to encrypt the data, but stores the key in the file. I broke Winzip because they encrypted twice with a stream cipher under the same key and leaked info about the rng state. Lots of ways to screw up crypto implementations.

Unregistered
November 15th, 2001, 23:37
Didn't know Winzip used a RNG system??