{"id":12035,"date":"2007-12-19T11:44:00","date_gmt":"2007-12-19T11:44:00","guid":{"rendered":"https:\/\/masabidev.wpengine.com\/news\/did-the-nsa-put-a-back-door-in-our-mobile-security-and-more-about-bad-random-number-generators\/"},"modified":"2014-11-25T15:23:03","modified_gmt":"2014-11-25T15:23:03","slug":"did-the-nsa-put-a-back-door-in-our-mobile-security-and-more-about-bad-random-number-generators","status":"publish","type":"post","link":"https:\/\/www.masabi.com\/es\/news\/did-the-nsa-put-a-back-door-in-our-mobile-security-and-more-about-bad-random-number-generators\/","title":{"rendered":"Did the NSA put a back door in our Mobile Security? (and more about bad random number generators)"},"content":{"rendered":"
After the recent discovery of a potential back-door<\/a> in a NIST<\/span><\/a> approved random number generator, I thought it would be timely to state clearly that we do not<\/span> use the generator scheme involved, but a more straightforward AES<\/span> based random number generator<\/a>, which does not fall prey to the suspicious curves<\/a>.<\/p>\n

Why do we care about random number generators anyway?<\/span><\/p>\n

For the encryption newbie: Quick Summary of key exchange to set up a secure session, using random number, and asymmetric encryption:<\/p>\n

    \n
  1. Generate a Big Random Number on the phone, that becomes your symmetric session key\n<\/li>\n
  2. Encrypt that secret session key using slow Asymmetric Encryption like RSA<\/span> (using the server’s public key that the mobile application already has, and we are quite happy for the attacker to know too)\n<\/li>\n
  3. Send the asymmetric encrypted session key over the public network to the server\n<\/li>\n
  4. Only the server with the private asymmetric server key can decrypt the data and read the secret session key\n<\/li>\n
  5. Secure session continues with fast symmetric encryption like AES<\/span> using the shared secret session key in both directions.<\/li>\n<\/ol>\n

    If the attacker can guess what big random number you created at step 1<\/span>, they can jump straight in to read everything at step 5<\/span>.<\/p>\n

    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.<\/p>\n

    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<\/span> that say \u00abhackers enter here\u00bb.<\/p>\n

    The Random Issue<\/span><\/p>\n

    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.<\/p>\n

    WAKEUP<\/span> CALL: <\/span>If you build a 128 bit key from 8 bits of un<\/span>-guessable randomness, you have a system with an effective security key strength<\/a> of only 8 bits.<\/p>\n

    <\/span>Pseudo Random Number Generators<\/span>
    Just having an approved Secure Random Number Generator is not enough, you need to     seed<\/a> (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.<\/p>\n

    What’s a good seed?<\/span>
    One of the common forms of cryptographic attack (after fooling people) is \u00ab    side channel attack<\/a>\u00bb 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<\/a> of the random number generator (RNG<\/span>), which then gives them the session key.<\/p>\n

    It’s easy to see why – the default Java implementation of secure random \u00abseeds\u00bb it’s RNG<\/span> 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<\/span> was started (usually a few hundred milliseconds before the first network connection) and throw all the times around that through an identical RNG<\/span> 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,<\/a> but that doesn’t really represent a real attacker-defeating source of entropy!<\/p>\n

    Q: \u00abWe 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?\u00bb<\/p>\n

    <\/span>\u00abAny one who considers arithmetical methods of producing random digits is, of course, in a state of sin.\u00bb<\/span> <\/span>von<\/span> Neumann<\/span><\/p>\n

    On mobile you cannot run a \u00abfutile cycle\u00bb 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<\/span> cycles, and found that on some Nokias<\/span>, 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 \u00abstirred\u00bb your RNG<\/span> with the timing, memory, or results of your startup<\/span>, it would be something that an attacker could also copy, and just use that as a known quantity in their \u00abguessing\u00bb. On top-end Symbian<\/span> handsets you can get better access to microphone, screen coordinates, less uniform performance from the multi-tasking OS etc, but on standard MIDP<\/span> phones it is all far too predictable to be a reliable source of entropy.<\/p>\n

    Side Note: Reverse Compiling Java:<\/span>
    Mobile Java is very straightforward to     reverse-compile<\/a> (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.<\/p>\n

    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 <\/a>that likes a challenge.<\/p>\n

    Solution:<\/span>
    You have to rely on the USER for a true source of randomness.<\/p>\n

    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.<\/p>\n

    The exact times of keypresses<\/span> 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.<\/p>\n

    Clock Granularity – why the mobile cryptographer would care:<\/span>
    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<\/span> too if you like, which in the worst case may vary in a fixed way according to the timing of keypresses<\/span>, so I’ll not give myself any new uncertainty for that as you have to always consider the worst case.<\/p>\n

    So if I want to generate a 128 bit random key, and I get roughly 8 bits of un<\/span>-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).<\/p>\n

    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 MIDP<\/span>1 phones that only provide user keyboard input.<\/p>\n

    Some developers use the IMEI<\/span> 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<\/span> S60 phones add the IMEI<\/span> here) or by installing a second application that simply asks for the same properties (similar to the attacks on XP<\/span><\/a> and BSD random seed pools<\/a>); adding this doesn’t increase your worst case entropy count.<\/p>\n

    Good Examples:<\/span><\/p>\n