General Cryptanalytic Methods - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 131

To date, the two best collision attacks against SHA-1 [13] can generate collisions in less than 2 69 operations
(with an improvement to 2 63 ), and a recent (2006) attack produced a collision with approximately 2 35 time [4]
(with the expected run time at the time the paper was written, in 2006, of 18 hours). Both attacks are better than
the 2 80 operations needed for the birthday attack.
For MD5, the current best collision attack known can produce a collision in less than a minute on a modest
2006-era PC [9].
In light of the ever-raging battle between hash algorithm maker and hash algorithm breaker, we wish to em-
phasize the following point.
Principle of Multi-Hash Security: Computing cycles and storage space are getting cheaper. Using multiple
hashing functions can exponentially increase the security. Therefore, when possible, store several hashes and
redundancy checks of data.
This principle takes advantage of one feature that is not present if one simply increases the length of the
returned hash function: Using different hash functions with different design philosophies means that, with any
luck, vulnerabilities found in one hash function (such as the ability to generate texts with the same hash) won't
work on more than one hash at a time; hence, only one of the hashes used will be compromised. If a hash is
simply extended to more bits, it's possible that the underlying structure is still weak, and the hash can still be
compromised.
5.6 Cryptanalysis of Random Number
Generators
A primary reason for cryptanalyzing random number generators is to try to determine information about a key
used in a standard cipher.
For example, in a classroom experiment that I led, students in the class all had accounts to trade goods in
a virtual economy. During various discussions, the students cleverly asked me how the account numbers (10
decimal digits) and RSA keys (hundreds of decimal digits) were generated. I told them that I had just used the
standard Java random number generator, and informed them of a rough guess of the time at which they were
generated.
The standard Java method at the time 3 wastousealinear congruential random number generator seeded with
the current time in milliseconds to generate numbers. Considering that they had a good guess at the time, they
could try various values for the system clock at the time and try to find the seed by seeing if their own account
numbers appeared in the output.
Assuming a class size of 100 students, with about 14 digits per account number (there was also a 4-digit
password generated), and 3,600,000 milliseconds per hour, there are
digits to generate and check to account for all of the possible seeds that could occur in 1 hour.
With a few processors, it is very possible to chew through a few hours of the possible random numbers in
just a few days at most.
This example illustrates one of the methods for breaking linear congruential random number generators:
guessing the seed. Finding out the way in which the seed is generated and attempting to re-create it will work
on this as well as on any other types of ciphers that rely on a seed.