# Uncrackable keys require hardware RNGs

Post a comment

As wireless network connectivity becomes almost ubiquitous in both private and public sectors, it has also become immensely profitable for criminals to use those networks to invade computers to steal or manipulate information. Identity theft, in particular, has become big business. And hackers now either own or have access to sophisticated equipment that enables them to eavesdrop on wireless systems and carry out analytical operations that until just a few years ago could only be done on systems in big corporations or universities.

For that reason, assuring the security of wireless network communications has become a crucial priority, and the past few years have seen massive efforts to implement standards and protocols to accomplish improved security. Regardless of the protocol used, random numbers are the fundamental building blocks of any cryptographic system. All authentication and identification "keys" are based on them.

Random numbers inject non-deterministic data into cryptographic algorithms to make the resulting output unpredictable. If a cryptographic key is based on a random number that is unpredictable, it cannot be guessed. But if there is any degree of predictability in a sequence of numbers generated in this way, the key can be broken. Thus, any cryptographic system is only as good as the random number generator (RNG) it is based on.

Whether an RNG is hardware- or software-based makes a crucial difference in how it generates random numbers.

Software random generators

Software RNGs use mathematical algorithms to generate random numbers, initializing the algorithm with a "seed" value derived from some repetitive operation in the computer, such as keystrokes, running processes, the computer's clock, or mouse movements. However, it is extremely difficult to come up with a completely unguessable seed value, since most such operations only provide seeds with a small range of values. The challenge of software RNGs is that the sequence of numbers based on the seed value is completely deterministic, since their creation is accomplished with a software algorithm. So even if the seed value is truly random, the numbers the RNG creates are predictable if someone can figure out the algorithm used to produce them. Thus the numbers generated by software RNGs are not considered truly random, but pseudo-random, and the software RNGs that generate them are known as Pseudo-Random Number Generators (PRNGs).

PRNGs produce acceptable output for non-cryptographic applications such as games and simulation. For example, in an on-line simulation of a black jack game millions of numbers are needed every second, since every hand dealt needs new numbers and there may be thousands of people playing at any given time. Numbers need to be generated with lightning speed, but the fact that the sequence repeats doesn't matter since because of the volume and the speed there is no way anyone could crack a key fast enough to use it to win a game. However, pseudo-random numbers cannot give the level of cryptographic protection that only truly random numbers can provide.

Vulnerabilities of PRNGs

Modern cryptographic algorithms are virtually uncrackable if the applications based on them are correctly designed and implemented. The U.S. government's Advanced Encryption Standard (AES) requires that keys be 128 bits, which makes them much harder to crack than the earlier Data Encryption Standard (DES) 56-bit standard.

"...correctly designed and implemented" is just as important as the bit-length in hampering attempts to crack PRNG encryption keys, because there are a number of ways that weaknesses can be built into an application that enable a hacker to guess the seed, the key itself, and the algorithm used to generate the keys. Hackers know exactly where these weaknesses lie and concentrate their efforts on the programming errors that create them. The careless or lazy programmer is the hacker's best friend.

Seeding

The most common programming error in PRNG applications is to use a seeding method that is easily guessed or that is not truly random. There are a wide variety of schemes for getting random number seeds based on unpredictable external real-world events such as the time between keystrokes, the air temperature, or how often network packets arrive. But there are problems with each of these schemes that are easy to overlook.

For example, when a computer is first booted up, cryptographic protection needs to be in place before anything comes through the network connection, yet if the software PRNG uses a seeding scheme that is based on timing the arrival of network packets, it can't get that information until the software loads; in the meantime an invasion or attack may already be under way. The same problem pertains to any scheme that uses external information to seed the encryption. That is, if the seeding scheme depends on keyboard strokes, no data is available until someone strikes two keys in succession. And so on.

Software that collects randomness from the outside world is time-consuming and difficult to write and debug. Random information such as the timing of keystrokes and the arrival of network packets is deep within the OS and not easy to get to. The programmer must have an extremely high level of expertise to code this function efficiently. It is tempting to save time and trouble by by-passing this degree of coding and use a seed from an easier-to-reach source.

Another factor that may be overlooked is that a technique to seed a software RNG that works in one environment may not work in another. In an embedded application, for example, there isn't a lot of external information available to generate a random number. In a router or wireless access point, there's no keyboard.

One of the most famous cases of cracking that was enabled because of a poor seeding scheme involved Netscape's 1995 introduction of the Secure Sockets Layer (SSL) protocol. SSL is commonly used to encrypt messages transmitted over the Internet. Netscape introduced SSL as part of their browser in the mid-90s, but instead of using truly random information for seeding the PRNG, Netscape's programmers used a combination of the current time of day, the process ID (PID) of the running Netscape program, and the parent process ID (PPID). All three are easy numbers for a hacker to determine, and two students at the University of California at Berkeley were able to break the code in a matter of seconds using a standard computer work station.

128-bit keys

Although the security world is moving to 128-bit keys, most legacy RNGs generate 32-bit numbers, and a common mistake is that less-experienced programmers think they can avoid the expense of a new RNG by adding together four 32-bit numbers to create a 128-bit key. The trouble with this method is that the resulting number is not a 128-bit number at all, but remains a sequence of the four 32-bit numbers. The first of the 32-bit numbers acts as a key and the three other numbers are determined by it. Thus, if a hacker can figure out the first 32-bit number, he can find the next three numbers because they are completely deterministic.

If the programmer is using the time between keystrokes for a seeding source, it is easy to set parameters so that the seed does not have enough bits. For example, suppose the programmer assumes that the number of milliseconds between keystrokes will be a number between 100 and 4000. This range assumes that no one is going to type faster than a hundred keystrokes a second, which equates to 100 milliseconds between each keystroke. It also assumes that no one is going to type more slowly than one keystroke every four seconds, which equates to 4000 milliseconds between keystrokes. The logic of this thinking is fine, but any number that is between 100 and 4000 will be no more than a 12-bit number.

Hardware generators

A hardware random number generator is an electronic device that generates random numbers using data it extracts from various kinds of noise within a computer's circuitry. Every electronic circuit is subject to noise, which can be thermal noise based on the temperature of the circuit, air turbulence, or random variations in voltage caused by interference from nearby circuits and other influences.

All these types of noise are completely random, and therefore the numbers the RNG generates based on this data are also random and unpredictable - that, non-deterministic.

Hardware RNGs do not require seeds because hardware random numbers are not computed values; they are not derived through a repeatable algorithm. Rather, hardware-generated random numbers are digitized snapshots of naturally occurring noise. Because there is no algorithm and no repeating sequences of numbers, even if a hacker could determine one key, he would not be able to use it to predict any future keys. For this reason, hardware RNGs are known as Truly Random Number Generators, or TRNGs.

A hardware RNG is a relatively simple device. Ubicom's IP3023 Wireless Network Processor has only four components: three noise sensors and a linear feedback shift register. Each of the three sensors samples the noise on the chip at a particular instant in time and turns it into a single bit -- either a 0 or a 1. The sensors are tuned to different noise patterns, so each produces a different, unpredictable sequence of 0s and 1s. The randomness is in that instant when the bits switch from 1s to 0s or 0s to 1s, and the time intervals at which this happens will vary. This means that out of ten consecutive bits generated by a noise sensor there might be only one truly random bit, so to get 32 truly random bits, the sensor requires 10 times 32 bits in order to accumulate that randomness.

The 32-bit linear feedback shift register (LFSR) accumulates these random bits, and provides a succession of 32-bit truly random numbers. The software reads the LFSR to build a 128-bit key. It must wait between reads for a full 32 bits of randomness to accumulate.

The LFSR, by itself, is a good pseudo-random number generator, and guarantees that the generated values will have a uniform distribution. The noise sensors guarantee that the results are not just statistically random, but also are unpredictable.

Hardware RNGs are so small that the amount of real estate they take up on the die is negligible. Ubicom's IP3023 has about 500 gates and approximately 5000 transistors on a chip that has 20 million transistors - that's a minute percentage of the real estate. So design time and real estate are not considerable cost factors.

The only cost of any significance is the testing. Ordinarily, a chip is tested by running a set of vectors to see if it does what it is supposed to do. But by definition an RNG generates numbers that are unexpected, so the only way you can test it is by incorporating a test mode into the RNG itself that separates the noise sensor from the LFSR and then tests the LFSR separately. The LFSR is a deterministic circuit, and the noise sensor also has some individual components that can be tested in isolation. But this test only has to be done once, and once it is done there is no potential for error.