Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've come across an implementation of DH in Java that uses the Random class to generate the secret integer value $a$, as shown in in Wikipedia's description of the algorithm. As such, the seed of the RNG is only 32 bits and the output may be predictable.

By observing DH exchanges only, would it be possible to predict or compute the shared secret?

share|improve this question
add comment

1 Answer

An attack would be trivial if the seed of the RNG was only 32 bits; just enumerate the seeds, and test which matches the intercepted messages. That's easy.

However the default Java Random class uses a 48-bit state and seed (which would still be attackable, though $2^{16}$ times less easily), and there are safe subclasses, thus use of Random does not imply an (insecure) 48-bit state, if the object really is a SecureRandom. See this Java 1.4.2 doc or this Java (1.)7.x one.

Update: While it seems the seed of the default Java Random class is 48-bit, its default seed indeed is 32-bit on some old Java platforms, and predictable to some degree on top of that; it is 48-bit on the latest Java platforms, and seems less predictable (though it could still be predictable/repeatable in a virtualized context).

share|improve this answer
    
@HenrickHellström According to the docs, it looks like the setSeed method (as called by the constructor) uses all 48 bits. However, the default seed in pre-Java7 is simply the current time as a millisecond-resolution value. –  Polynomial Mar 26 '13 at 14:11
    
@HenrickHellström: the initialization for the default RNG was improved, and is now using seedUniquifier() ^ System.nanoTime(); search for that. –  fgrieu Mar 26 '13 at 14:12
    
Correction: the seed was the system time in milliseconds on Java 1.4.2 and earlier. –  Polynomial Mar 26 '13 at 14:17
1  
There are at least three different implementations of the default seed for the default Java Random class; one use an at-most-32-bit seed derived from the system time in millisecond (OR MORE); another use an at-most-48-bit seed of ++seedUniquifier + System.nanoTime() where seedUniquifier is some shared global initialized from a public constant; the third uses seedUniquifier()^System.nanoTime() where seedUniquifier() uses a shared global atomically updated per a multiplicative RNG with public seed and multiplier. Neither method is meant to be used for crypto. –  fgrieu Mar 27 '13 at 12:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.