Saturday, January 9, 2010

PRNG Vulnerability of Z-Stack ZigBee SEP ECC

by Travis Goodspeed <travis at radiantmachines.com>
with neighborly thanks to Nick DePetrillo,
concerning version 2.2.2-1.30 of TI Z-Stack
and a ZigBee Smart Energy Profile ECC vulnerability.

Not Quite Random

In past articles, I've presented a variety of local attacks against microcontrollers and ZigBee radios. While I maintain that local vulnerabilities are still very relevant to ZigBee devices, this article presents a remotely exploitable vulnerability in the way that random keys are generated by TI's Z-Stack ZCL implementation of the ZigBee Cluster Library. Randomly generated numbers--those fed into the Certicom ECC crypto library--are predictable, repeated in one of two 32kB cycles. Details follow, with links to source code and a complete list of random numbers.

Dumping Random Bytes


I dumped byte sequences from the CC2430 using the GoodFET to debug a live chip. The chip runs a program which populates IRAM with PRNG bytes, then halts with a soft breakpoint (Opcode 0xA5) for the debugger to grab all sampled values. The main loop looks something like this:
Chipcon RNG Dumper
The firmware was compiled with the Small Device C Compiler, flashed by the GoodFET. A quick Python script then used the GoodFET library to debug the target, dumping random values through the same interface that programmed the chip.
Chipcon Byte Dumper

Short PRNG Period


Page 18 of the CC2530 Datasheet describes the random number generator peripheral, which is shared by all other 8051-based ZigBee SoC devices in the series.
The random-number generator uses a 16-bit LFSR to generate pseudorandom numbers, which can be read by the CPU or used directly by the command strobe processor. The random numbers can, e.g., be used to generate random keys used for security.

The state of this RNG is initialized in the hardware abstraction library by feeding 32 bytes from the ADCTSTH special function register into RNDH register. Bytes read from ADCTSTH are physically random, but poorly distributed. RNDH and RNDL are the High and Low bytes of a 16-bit CRC Linear Feedback Shift Register, the state of which can be advanced by writing to RNDH or overwritten by writing to RNDL. In between reading or writing from RND, the state is advanced by setting the fourth bit of ADCCON1. Detailed descriptions of these registers can also be found within the datasheet.

CC2430 examples randomize the seed by mixing 32 values into the RNG,
for(i=0;i<32;i++){
RNDH=ADCTSTH;
ADCCON1|=0x04;
}

Because these numbers are not evenly distributed, Z-Stack prefers to sample just the least significant bit of the RF random number generator sixteen times, then write them in directly as the state without mixing them. Further, it checks to ensure that the state is not a dead-end, substituting another if it is. This method is also advocated within the CC2530 programming guides.
for(i=0; i<16; i++)
rndSeed = (rndSeed << 1) | (RFRND & 0x01);
if (rndSeed == 0x0000 || rndSeed == 0x0380)
rndSeed = 0xBABE;
RNDL = rndSeed & 0xFF;
RNDL = rndSeed >> 8;


Once the RNG has been seeded, it has an initially random 16-bit state. From then on, however, it produces random bytes in a predictable sequence. Only the starting point is random, as ADCTSTH is never used for future reseeding. As shown in the screenshot above, if the sequence "7c e1 e8 4e f4 87" is observed, the probability of the next bytes being "62 49 56 fe 80 00 60" is 100 percent. Further, because the domain is so small, it can be exhaustively searched for keys in little time.

Not Quite Random

Code for dumping these values through the GoodFET debugger can be found by svn, along with a complete dump of the PRNG sequence.
svn co https://goodfet.svn.sourceforge.net/svnroot/goodfet/contrib/ccrandtest

Seed Values


Seed Histogram

The plot above shows the histogram of radio ADCTSTL values used to seed the PRNG. These are far from random, but when sampled slowly enough, their least significant bit is probably good enough for key generation. There are, however, two things of interest with this.

First, if the crypto library is used infrequently, it would make sense to use this source of entropy instead of the inadequately random PRNG output. There would be a cost in power consumption, as ADCTSTL is only random while the radio is operating, but the resulting increase to security is necessary.

Second, if the peaks on the histogram come from a measurement of the radio, it might be possible to generate a radio signal that forces even the least significant bit to be a predictable value. Steps such as AES whitening should be taken to avoid such an attack.

ZigBee SEP, ECC


A less than perfect random number generator is not much of an issue when symmetric keys are pre-shared, but because pre-shared keys are vulnerable to local attacks, the ZigBee Smart Energy profile recommends the use of session keys signed by elliptic curve cryptography. See the USAF paper Cryptanalysis of an elliptic curve cryptosystem for wireless sensor networks for a prior break of ECC with a poor RNG.

As will be shown in the next section, Chipcon's ZStack makes use of poorly random PRNG data as key material, allowing for a key domain of only 16 bits. This is small enough to be exhaustively searched, either by a PC or by a "Chinese Lottery" of previously compromised wireless sensors.

ZStack Usage


ZStack 2.2.2-1.30 for the CC2530 makes use of the PRNG to implement the Smart Energy Profile's asymmetric cryptography. The Windows installer works perfectly under Wine, leaving ZStack installed to an awkward directory. I symlink it to /opt/zstack for convenience.
CC2530 in Wine

Once installed, the following Functions are of interest.

mac_mcu.c contains macMcuRandomByte() and macMcuRandomWord(). As the two are largely the same, take the former for an example. First the PRNG is clocked, then the high byte is sampled.
ZStack macMcuRandomByte()

zcl_key_establish.c is used to generate keys by the ZigBee Cluster Library specification, available for free by form from ZigBee.org. The code fragment below takes the low bytes of macMcuRandomWord(), redefined as osal_rand(), to populate a session key before signature.
ZCL KeyEstablishment GetRandom

The ultimate function for ECC key generation is ZSE_ECCGenerateKey(), which is defined in eccapi.h but whose source is missing. Reading ecc.r51 yields a few filenames as part of stored compiler warnings. The developer's filename was "C:\SVN-ZStack-2.2.0\Components\stack\sec\eccapi.c", but it is only a stand-in for the Certicom Security Builder MCE library that is not shipped with the development kit. In any case, the vulnerability here lies in ZStack and not in Security Builder.

Conclusions


This article has shown that the Chipcon ZStack library, as of version 2.2.2-1.30 for CC2530, uses an insufficiently random PRNG for cryptographic signatures and session keys. PRNG data repeat every 32,767 samples, and there are at most 16 bits of entropy in any key. Searching the entire key space ought to be possible in very little time. Contrary to the CC2530's documentation, these random numbers must not be used to generate random keys used for security.

All users of this library, particularly those using it for Smart Grid devices and other industrial applications, are recommended to re-implement macMcuRandomWord() and to ensure that nothing requiring cryptographic security operates from the PRNG alone. Users of other libraries for the Chipcon devices should ensure that those libraries are not using the PRNG data.

Competing devices and libraries should also be checked for similar vulnerabilities, as well as commercial products such as Smart Meters that might have forked the ZStack code or followed the datasheet's recommendation of using the PRNG for key generation.

9 comments:

alexru said...

That's not entirely true.
Key function in Certicom library is ZSE_ECCKeyBitGenerate() which generates keyBits (shared secret) based on which link keys are generated (as a hash of keyBits and some other data concatenated).

ZSE_ECCKeyBitGenerate() takes privateKey parameter (others may be considered known due to mentioned issue).

privateKey is the static private key of the local entity which is programmed during device manufacture and generally unknown outside the device.

So there is no real way of exploiting vulnerability.

alexru said...

Also you'll need remoteCertificate (which is exchanged in plain text in the air) which depends on device MAC address and privateKey of device. This certificate officially issued by Certicom for every single device.

接觸 said...
This comment has been removed by a blog administrator.
Travis Goodspeed said...

Alex,

The ECMQV key exchange depends upon an attacker not knowing the defender's ephemeral private key. So the attack would work something like this:

Mallory can be assumed to have a single valid certificate, as these are easily extracted by erasing a CC2530's flash memory then extracting RAM with a debugger. She wishes to non-destructively acquire a second static private key from Alice.

During a key exchange,
1) Alice and Mallory generate ephemeral key pairs. Mallory's is chosen, rather than random. Alice's is poorly random.
2) They exchange these pairs.
3) Mallory knows her own key, and can look up Mallory's private ephemeral key from a table by the matching public key.
4) Alice and Mallory each construct parts of a shared secret. Mallory knows her own, as well as the product of Alice's with the ellyptic point P, which is constructed from Alice's ephemeral and static private keys.
5) Alice has constructed her portion locally by her ephemeral public and private keys, as well as her static private key. Mallory is not supposed to know either private key, but in point of fact she knows one of them.
6) Mallory can solve for the missing private key in this combination of sa and sb.

The attack can be made faster if Mallory forces Alice to a particular starting point. (It would take a long time with key exchanges, but packet collisions might advance the counter faster.)

See Analysis of the Insecurity of ECMQV with Partially Known Nonces for an attack against the key exchange of 160 bit keys when only the most significant 4 bits of the private key are known.

--Travis

Alexander Taradov said...

Yes, your reasoning is correct. I think we need to define goal and means of attack.

1. For an external attacker: device used for attack is brand new and never was in network. In this case this device must be in ESP's (Trust Center's actually, but smart energy specification makes no difference) permission table and must have installation link key configured properly on TC. Rather unlikely situation. Also all key establishment will be done encrypted with network key (which is also unknown to the attacker).

2. Internal attacker (cheating with prices or whatever). In this case attacker has full access to the network. But it won't help since only ESP is responsible for all money-related operations. So you'll have to hack ESP. Which is still possible (with debugger, a lot of time and some luck), but is out of discussed encryption scheme scope.

So while vulnerability is raises chances for attacker they are still pretty virtual.

Alexander Taradov said...

This is still me, alexru :)

DoubleO said...

"Mallory can be assumed to have a single valid certificate, as these are easily extracted by erasing a CC2530's flash memory then extracting RAM with a debugger."

-- This is being addressed by storing the cert and root key in flash and only accessing them from the created partitions. The debug lock bit will then protect any access through the debug interface.

nymious said...

Hi Travis,

Zigbee may have some issues with it's usage of the AES-CCM* mode. Where this mode is used, thre always needs to be a unique key/nonce pair or the keystream gets reused. I suspect just reseting the device might make it start it's sequence counter over ...

Regards,

nymble

priyanka royal said...

Thank you for sharing your Useful information. I hope you will post again soon.You can also refer to us Stacker Manufacturer in India