According to Frank Gifford this 35-character password, FI7CTQsBDvsMwbQNyY6qxV2FunWIUpXpcZm, is surprisingly weak.
Java’s util.Random class uses a pseudo-random number generator (PRNG) which creates a deterministic sequence of numbers. When one needs statistically random numbers, such as for Monte Carlo simulations, this is a great choice. It’s fast – and if a model needs to be tweaked, the PRNG can be restarted so that the exact same sequence of numbers is generated as before. Unfortunately, this predictability isn’t beneficial when we want cryptographically-secure random numbers such as passwords, session keys or web certificates.
Suppose we generate a very long sequence of bits. For most cases where we want to use ordinary pseudorandomness (e.g. unpredictability in videogames), we only need this sequence to look random to a human. For example, if we alternately placed bits generated to this standard in two buckets, we’d expect the buckets to both end up with about the same numbers of 1s and 0s.
For pseudorandom numbers used in cryptography, however, the standard is higher. This time, you already have a huge sample of generated bits, and have to guess whether the next one will be a 1 or a 0. Even though all the bits before the missing bit are known, we can only say the sequence is truly random if there is no way to determine the value of the next bit. This distinction between “normal” pseudorandomness and cryptographically secure pseudorandomness is tricky, and it’s further complicated by languages such as Java using the word “random” to describe both.
In Java’s case, the PRNG accepts a current 48-bit value (called a “seed”) and determines the next seed by:
- Multiply the current seed by a language-constant value
- Add the multiplication result with another constant
- Keep the lowest 48 bits – this is the next seed in the sequence
The Java PRNG uses a well-studied mechanism called a Linear Congruential Generator which is known to behave in a statistically random manner.
During a recent client engagement, Gifford was reviewing some Java code which generated a random password for a service account. It used upper and lowercase characters and digits to create the password – which was between 20 and 40 characters in length. The encapsulating class even included the word “Secure” in the name. The call looked something like this:
password = SecureString.RandomAlphanumericString();
When examining a resulting 35-character password, it looked beautiful. Diving further into their class, Gifford noticed the use of Java’s util.Random class, which immediately got his attention. That code ultimately was a simple loop to pick a “random” value from an alphabet of possible characters to create the password. Given a password, it should be possible to work backwards to recover the initial value.
With a bit of searching, Gifford found Sergey Soldatov’s JavaCG (https://github.com/votadlos/JavaCG) which would take a sequence of integers and determine the starting value used to generate them. He wrote a wrapper script to accept a generated password and pass it to the JavaCG program. For completeness, he wrote a stand-alone Java program which – when given a character-set, seed value, and string length – generates the resulting password.
Gifford released the sources for the tools (https://github.com/frank-gifford/Java_PRNG) believing that broken programs should be demonstrated as broken when possible. There’s something powerful about watching how quickly such a program can run. In an effort to stop people from using util.Random in this manner anymore, he’s included comments and easy to understand mechanisms in the code so it may be easily tweaked for your use.
As an example, Gifford tells the script the alphabet and the password he’s using. It converts the password to a sequence of numbers which get passed to the JavaCG program. In about one second, the program finds the seed:
Found seed: 89560454678953
It’s a quick check to verify the seed creates that password:
kali# java generate_password ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghij
klmnopqrstuvwxyz0123456789 89560454678953 35
Essentially, any randomness generated by Java’s util.Random is determined by the 48-bit seed. Often, this is based on the system time so it’s not as random as expected. If an attacker can guess when a password was generated, they can make a list of all seed values that might be valid and try each of the resulting passwords. This is a much smaller list to brute-force than attempting to crack the 35-character password directly. As to the specific recommendation we made, it was for the client to the java.security.SecureRandom class which is designed to create random numbers which are cryptographically sound.
A common pitfall for developers is to create a quick-and-dirty solution, such as using a PRNG, during development with the intention of returning and implementing things “correctly” in the future. With the never-ending rush to get a product out the door before the competition, it’s easy to forget to do a proper cleanup. The inaccurate class naming pointed out earlier leads other developers to believe that the password generated is cryptographically secure. They’d be further drawn to this conclusion after creating several passwords and visually inspecting them (since theyappear to be random). Security is tricky to get right. It takes careful planning and verification. On the surface, bad security can look just like good security.
Original post from NCCGroup