Travis Goodspeed has continued finding flaws in TI microcontrollers, branching out from the MSP430 to ZigBee radio chipsets. A few days ago, he posted a flaw in the random number generator. Why is this important? Because the MSP430 and ZigBee are found in many wireless sensor systems, including most Smart Meters.
Travis describes two flaws: the PRNG is a 16-bit LFSR and it is not seeded with very much entropy. However, the datasheet recommends this random number generator be used to create cryptographic keys. It’s extremely scary to find such a poor understanding of crypto in a device capable of forging billing records or turning off the power to your house.
The first flaw is that the PRNG is not cryptographically secure. The entropy pool is extremely small (16 bits), which can be attacked with a brute-force search in a fraction of a second, even if used with a secure PRNG such as Yarrow. Also, the PRNG is never re-seeded, which could have helped if implemented properly.
Even if the entropy pool was much larger, it would still be vulnerable because an LFSR is not a cryptographically-secure PRNG. An attacker who has seen some subset of the output can recreate the LFSR taps (even if they’re secret) and then generate any future sequence from it.
The second problem is that it is seeded from a random source that has very little entropy. Travis produced a frequency count graph for the range of values returned by the random source, ADCTSTL, a radio register. As you can see from that graph, a few 8-bit values are returned many times (clustered around 0 and 100) and some are not returned at all. This bias could be exploited even if it was used with a cryptographically-secure PRNG.
These problems are each enough to make the system trivially insecure to a simple brute-force attack, as Travis points out. However, it gets worse because the insecure PRNG is used with public-key crypto. The Z-Stack library includes ECC code written by Certicom. I have not reviewed that code, but it seems reasonable to use a library from a company that employs cryptographers. But the ECC code makes the critical mistake of leaving implementation of primitives such as the PRNG up to the developer. Other libraries (such as OpenSSL, Mozilla’s NSS, and Microsoft’s Crypto API) all have their own PRNG, even if seeding it has to be left up to the developer. That at least reduces the risk of PRNG flaws.
ECC, like other public key crypto, falls on its face when the design spec is violated. In particular, ECDSA keys are completely exposed if even a few bits of the random nonce are predictable. Even if the keys were securely generated in the factory during the manufacturing process, a predictable PRNG completely exposes them in the field. Since this kind of attack is based on poor entropy, it would still be possible even if TI replaced their PRNG with one that is cryptographically secure.
Given that these chips are used in critical infrastructure such as smart meters and this attack can be mounted from remote, it is important that it be fixed carefully. This will be difficult to fix since it will require hardware changes to the random source of entropy, and there is already an unknown number of devices in the field. Once again, crypto proves fragile and thorough review is vital.
rdist 
Thanks for this write up. I read Goodspeed’s original post and could not extract the salient points.
Thanks. I too had problems parsing it at first. My main confusion was which parts of the advisory were software bugs and which were hardware.
ECMQV uses static and ephemeral key pairs. It’s worth pointing out that the static key pair is not necessarily (indeed unlikely to be) generated by this means therefore the static private key itself is not vulnerable to this attack. Replacing the PRNG will improve the security as it will increase the entropy for the ephemeral key pair and thus derived (symmetric) keys. Periodically reseeding with a true random base and whitening should be sufficient to significantly improve the entropy of the RNG.
Good points, but are you familiar enough with the smart meter industry to be certain of this? The vendor is providing a toolkit, from which the customer can create any number of implementations with variations on use of crypto. Feel free to give more details if you have them.
ECQMV is vulnerable to an attack against the static private key when the top 4 bits of the ephemeral private key are known. The static key pair is exposed even though it is generated off-meter with a presumably good RNG.
Right, and this is a general problem with other public key crypto as well. For example, (EC)DSA can be compromised if you know a small fraction of the random nonce (not key!) bits.
The moral is: randomness is very important in public key crypto and you can’t just hand-wave and say a fix is “good enough.”
I can assure you I am very familiar with the crypto specification and typical implementations for these meters. The ECC library has fixed functions for the ZigBee Smart Energy security cluster. The library requires two user-provided callback functions:
1) A random number generator
2) AES-MMO cryptographic hash
(2) is a callback as many chips have an internal AES-128 block cipher accelerator, thus the soft (and comparatively large) AES-128 block cipher also included in the library can normally be elided. Because this has a very fixed function, it is not really open to abuse.
(1) is a callback because many chips/stacks provide their own RNG. The aim here is to make the library as small as possible due to the constrained resources of the chips this is targeted at. Therefore, if reuse can be done, it should be.
Therefore, the customer cannot “create any number of implementatins with variations on use of crypto”.
Of course, if an implementer decides to use a PRNG with low entropy for the RNG (which the ZigBee Specification says should be FIPS 140-2 compliant) then it will cause potential problems as has been discovered.
I’m questioning two points that you seem confident in but could warrant further review:
1. That static key pairs are “unlikely to be generated” using the Z-Stack insecure PRNG
2. That the ADCTSTL register provides enough entropy, even with a secure PRNG
I’m guessing your criteria for #1 is that key generation is probably done on a general purpose computer before production, and thus is unlikely to share an implementation with Z-Stack. Is this the case? How likely is it that they reused code from Z-Stack?
Evidence points to #2 being a problem, even with a secure PRNG. Careful modeling of the entropy obtained from ADCTSTL is needed before making claims about it. Unfortunately, the latest version of Z-Stack moved this function out of the library, so it’s not easy to review exactly how it’s used (reseeding rate).
In Z-stack 2.3, the least significant bit of the ADC register (which is very noisy) is used to construct the seed values. It is read multiple times and those bits are used to construct the initial seed of the desired length. Chapter 19.12 in the CC2530 user’s guide explains the random number generator of the CC2530, including plots of random data from 20 million samples: http://focus.ti.com/lit/ug/swru191/swru191.pdf
Thanks for the nice reply. It’s good you’ve done some analysis, but more in-depth review of a cryptographic random source should be performed. Here’s one that I consider a good example review (disclaimer: I worked on some of it)
Click to access VIA_rng.pdf