After the recent discovery of a potential back-door in a NIST approved random number generator, I thought it would be timely to state clearly that we do not use the generator scheme involved, but a more straightforward AES based random number generator, which does not fall prey to the suspicious curves.
Why do we care about random number generators anyway?
For the encryption newbie: Quick Summary of key exchange to set up a secure session, using random number, and asymmetric encryption:
If the attacker can guess what big random number you created at step 1, they can jump straight in to read everything at step 5.
The vulnerability in the news story above is that whoever knows the secrets to the elliptic curves that underpin that particular random number generator might be able to guess the sequence of random numbers it will generate more easily (mathematically quicker) than should be possible for a normal attacker.
This posting will not say anything more about that specific (possibly deliberate) vulnerability, but instead look at situations where developers inadvertently put much worse weaknesses in their security systems which allow attackers to beat your system as if they had a similar back door, which you accidentally left wide open, accompanied by big flashing neon signs that say "hackers enter here".
The Random Issue
All cryptography relies on a good source of randomness, and it is very important for system designers and security evaluators to understand that although they may have thought hard about how many bits long their keys are, all of their fancy cryptography is worth nothing if they haven't built it on top of a good random number.
WAKEUP CALL: If you build a 128 bit key from 8 bits of un-guessable randomness, you have a system with an effective security key strength of only 8 bits.
Pseudo Random Number Generators
Just having an approved Secure Random Number Generator is not enough, you need to seed (initialise) the generator with some real randomness (entropy) otherwise the secure random will be predictable. This is because all secure random number generators are actually PSEUDO-random number generators, and will produce exactly the same sequence of numbers from an identical seed. They have to work this way so that they can be properly tested and profiled to avoid generating patterns in the sequence output that could reveal something about the source seed (that is, that they are one way functions which don't create repeating patterns). In layman's terms, it means that the seed must be from something really random, and then your pseudo random number generator can get on with producing a nice continuous stream of apparently random numbers, suitable for cryptography.
What's a good seed?
One of the common forms of cryptographic attack (after fooling people) is "side channel attack" where an attacker observers some external aspect of the client system and uses that to guess the keys or data. In this case they can ignore the algorithms in use, and just second guess the seeding of the random number generator (RNG), which then gives them the session key.
It's easy to see why - the default Java implementation of secure random "seeds" it's RNG from the system time when it was started - so to guess the session key in use during an encrypted session, you simply guess (roughly) when that program's RNG was started (usually a few hundred milliseconds before the first network connection) and throw all the times around that through an identical RNG algorithm until one of the generated keys works. This would allow you to guess a 256 bit key in only 9 bits worth of attempts (effectively reducing the key strength to 9 bits, therefore easily brute-forcible). It turns out that since Java 5 the default seed implementation also adds a counter to the current system time, but that doesn't really represent a real attacker-defeating source of entropy!
Q: "We run a maths loop thousands of times and take the processing time and free memory differences from that to make the random seed, will that do?"
"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.'' von Neumann
On mobile you cannot run a "futile cycle" to generate random times and memory usage like you do on a PC, as many handset operating systems are so simple that they run completely uniformly (the same every time) in most cases.
We profiled all common phones during thousands of program startup cycles, and found that on some Nokias, for example, you could load a hundred images and do all sorts of other things in memory and it would take the same number of milliseconds, (+/- 10ms) every time, so even if you "stirred" your RNG with the timing, memory, or results of your startup, it would be something that an attacker could also copy, and just use that as a known quantity in their "guessing". On top-end Symbian handsets you can get better access to microphone, screen coordinates, less uniform performance from the multi-tasking OS etc, but on standard MIDP phones it is all far too predictable to be a reliable source of entropy.
Side Note: Reverse Compiling Java:
Mobile Java is very straightforward to reverse-compile (getting the original source), so you have to start your analysis by assuming that a committed attacker can completely understand, and make use of your own code against you. All of the worst case scenarios that we are guarding against assume that the attacker has full knowledge of what the developer is doing, and could perform quite advanced profiling of how it performs on each handset, or just target a particularly vulnerable handset.
This may sound like a very long winded process, but the attacker may have been quite highly funded by criminal gangs or antagonistic Government agencies to break your security, or worse, they might just be a bored academic that likes a challenge.
Solution:
You have to rely on the USER for a true source of randomness.
Some PC security programs get the user to wiggle a mouse or speak into a microphone before they generate your keys - this is all about seeding. Get the mobile user to press buttons, or interact in some way, such as playing a game. This is the only way to get a good seed on many handsets.
The exact times of keypresses are one good source of some randomness. But you must first figure out how much true entropy you get on each handset from this. More handset profiling is required.
Clock Granularity - why the mobile cryptographer would care:
Many handsets give time in milliseconds, but only have a clock granularity (minimum reported time difference) of around 25ms. If someone is banging random keys, an attacker may guess the presses are occurring roughly each second, so the variation that they can't guess is going to be less than about half a second, varying by say 15 actual reported clock intervals (375ms). So we might only get 4 bits of randomness in the time. If they are hitting random buttons, on a 10 button keypad, the value of the key pressed is another 3 bits, and the key release time about another 1 bit of uncertainly. You can throw in the free memory at the time of keypress too if you like, which in the worst case may vary in a fixed way according to the timing of keypresses, so I'll not give myself any new uncertainty for that as you have to always consider the worst case.
So if I want to generate a 128 bit random key, and I get roughly 8 bits of un-guessable entropy from each user keystroke (if they are banging the keys to give me randomness) then they will have to hit at least 16 keys to be sure. (and there will be plenty of people that will argue for less bits of entropy per keystroke, and demand 20 keys hit, so we usually go for 20 as our minimum).
On newer phones you could get entropy from the tilt sensor, or record sounds and background noise from the microphone, but we have to make sure that there's a workable solution for even the most basic MIDP1 phones that only provide user keyboard input.
Some developers use the IMEI or other phone properties as an extra bit of information to throw into the random seed - by all means add this, but don't assume that this would be impossible for an attacker to find either from a browser HTTP header (Nokia S60 phones add the IMEI here) or by installing a second application that simply asks for the same properties (similar to the attacks on XP and BSD random seed pools); adding this doesn't increase your worst case entropy count.
Good Examples:
Bad Examples:
There are plenty of "Secure" mobile applications that don't practice safe seeding, and are open to RNG guessing attacks. It could be that they have some other hidden source of randomness that none of the rest of the computer scientists in the world have thought of, but I doubt it.
If you are using a secure mobile app, especially on MIDP1, and you get a secure connection without pressing at least 16 buttons first, then chances are your connection is vulnerable to attack, and someone getting into your session in under 1000 guesses.
It's also a first sign that the application developer may not have had anyone skilled and independent truly analyse their security, because it would be the first thing spotted by a security professional or white-hat hacker, simply by looking at the finished product, and before viewing a single line of code.... there could be other mistakes too.
Another Bad (and common) approach:
No Random Number Generation, No Key Exchange
It is difficult to build both an Asymmetric and Symmetric encryption systems small and fast enough to use on mobile devices, and we've noticed that some secure mobile products don't bother with it at all, and just implement a Symmetric cipher alone, like RC4, 3DES or AES, and pre-share a symmetric encryption key through some other corner cutting technique.
Common bad key-sharing tricks: (we've seen these in live systems)
So, after all that, we're not really scared that the US Government has a back door implanted into the publicly known and widely investigated algorithms that we use; but more importantly I hope we've looked carefully enough at our handling of random numbers and key exchange to make sure that we haven't inadvertently left another back door open for the attentive hacker to exploit.
However, it does seem that some vendors are still leaving these vulnerabilities in their systems by design - I hope that this all gets brought into line soon so that as an industry we don't make mistakes that could earn mobile commerce a bad reputation with the public before we've even truly got started!