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.

47 comments:

Alex Taradov 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.

Alex Taradov 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.

Anonymous 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

Alex 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.

Alex 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.

nymble 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

SFCable said...

Very nice and helpful information has been given in this article. I like the way you explain the things. Keep posting. Thanks.. Power Cord

Roman reigns said...

It’s fantastic that you are getting ideas from this post as well
as from our discussion made at this place.

Interference Analysis in UK
Interference Analysis in India

CRMJetty said...

I appreciate to blogger for wonderful post. will definitely share this blog to my group.

customer portal services

Brandz Hub said...

Get best discounted price clothes and other accessories for men, women and kids at Brandz Hub. It is the most popular online shopping store located in Lahore, Pakistan. Do online clothes shopping in Pakistan ​with BrandzHub and get the best deals at maximum discount prices.

Andrew said...

The breaker is giving isn't adequate to the forced air system and subsequently it neglects to stay in help and henceforth fan isn't working. raw steroids supplier

Jean Wilson said...

Very interesting, to see the discussion. We don't know about a new concept until we go test it. I went on the internet and searched on how to give car on rent to companies in pakistan. When I got my first payment, I realized it was a reality, before that I thought it was a scam. I understood that the contract has also legally binding if there are prepared by a professional lawyer.

Mn Kids Store said...

Mn kids store is an online kids store to provide imported kids products ​at low prices. Offering cash on delivery in Pakistan.

Mark Coli said...


A Canon all-in-one printer is ideal for both the home and office. Additionally, all Canon printers are compatible with nearly every major operating system, including Windows, Android, and Apple iOS. A Canon printer will also give you the best quality and speed when printing documents. Printing tasks can be completed quickly and easily with ij.start.cannon .

Jack Mosan said...

quickbooks error -6147 is a common error that many QB customers run across when restoring or accessing their corporate files over a network.fro all the details regarding this error go to the mentioned site

QB premiersupport said...

All set to download, setup, or update QuickBooks database server manager? But, hang on! Do you know what all it takes to download, setup and update it? Need not to panic, we have got you covered. quickbooks database manager is also named as Intuit personal database manager tool.

Also read :- quickbooks data extraction tools OR quickbooks error 324

Eric Jones said...


Thanks for the blog its really informatic and helpfull quickbooks error h505 appear when the user tries to get the company files or data on another computer & that computer does not have proper establishment setup or the computer require additional installation or setup. The H series errors are related to the hosting settings problems.And there Have lots of Quickbooks error solution Like quickbooks database server manager Or quickbooks error 1712 You have also the problem please click the links.

Daniel Lisa said...

Quickbooks error 1723 is most likely to display On the screen When there is a problem with the Windows installer package, the error appears on your computer screen. The installation procedure also necessitates the use of a DLL file; if this file is faulty, issues may occur.When attempting to uninstall QuickBooks Desktop, the error code 1723 will appear. Damaged Microsoft components could be the source of such issues.

John Trump said...

QuickBooks Error 15215: Unable to verify digital signature. This error is generally caused by a conflict with another application running in the background when you try to download a payroll update.

Asquare Cloud Hosting said...

Awesome blog!! Thank for providing excellent information. if you have any issues with QuickBooks Online Error Code 101, you can go through the detailed steps mentioned in this article.

John Trump said...

Can you merge QuickBooks company files? The QuickBooks users can merge their company files using different ways. These different ways are manual and automatic. Both ways work well, but it is recommended to go with the automatic solution by using the combined reports feature of QuickBooks software.

John Trump said...

Quicken an unknown error occurred one error generally occurs due to a bad internet connection or when you enter the wrong credentials to log in to Quicken.

QbEnterpriseSupport said...

In this article we provide complete details on how to unvoid a check in QuickBooks to help yourself out.If you need support please contact our quickbooks 24-7 support team

QAsolved said...

When there are multiple users set up for the file the Login prompt asks for both a user name for a password: In both cases, the special Admin user name is very likely “Admin”, unless someone when to the trouble of QB Admin Password crack. My Computer Guy uses brute force techniques to find out the password for QuickBooks admin. A number of methods are used to determine possible passwords and then the program attempts them. The guessing takes about 5-10 minutes depending on how many letters and characters you want to include in your password.

My Computer Guy uses brute force techniques to find out the password for QuickBooks Admin Password crack. A number of methods are used to determine possible passwords and then the program attempts them. The guessing takes about 5-10 minutes depending on how many letters and characters you want to include in your password.

Crack QuickBooks Admin Password is a small tool to help you change the password of the QuickBooks administrator. For best results: 1) Select the Admin user (if there are multiple users). 2) Run the application and enter your old password. 3) Enter a new password that meets the requirements. 4) Click CHANGE PASSWORD.

Josh Holtan said...

QuickBooks error 6176 is the error which occurs while you are opening the company file and most of the time the company file is located in the server computer. The reason for error code 6176 is your hosting configuration is incorrect or you trying to open damaged company file. Therefore we have shared some tips and tricks to mend the QuickBooks error code 6176 with ease for more you can also contact us at 800-579-9430.

Zepth Construction Project Management Software said...

Project management is a very tedious task in the construction sector because there are many aspects that need to be managed. Zepth is an effective construction project management software that provides a complete solution for project management.

Axpert Accounting said...

This extraordinary software is loaded with some amazing features, and during the process of exploration of these features, QB users stumble upon a few glitches. One such error is QuickBooks Web connector error QBWC1085. If you have also stuck on any such error, then this post is a must-read for you. An instant solution to the same can be, getting in touch with QuickBooks technical support experts at +1-844-405-0906

update QuickBooks to the latest version
Fix QuickBooks Error Code 9584

Paul Vish said...

We will illuminate you pretty much every one of the causes and investigating steps to determine the QuickBooks Error Code C=272. As we as a whole realize that QuickBooks is the most refined and downloaded monetary administration programming out there to manage organization information in a coordinated way of behaving.

You may also read: Resolve QuickBooks Payroll Error 30114

IELTS AOLCC said...

There are plenty of great reasons to choose the AOLCC Mississauga campus to reach your academic and career goals. AOL College offer accelerated diploma programs in Accounting, Business, Health Care and Law that can be completed in under a year, meaning you can fast-track into a rewarding career that you really love. With small class sizes and experienced instructors, you’ll get the personalized instruction you deserve in a supportive learning environment.

Our caring advisors will help you choose the program and financing options that align with your goals. We have continuous enrolment, so you don’t have to wait for a semester to begin. You can start as soon as you’re ready.

QBS Enterprise Support said...

There can be a couple of factors causing the QuickBooks error code 6123, 0 issue that are discussed later in this post. Thus, make sure you read this post carefully till the end. Moreover, you can ring up to our professionals and let them fix the error for you. Moreover, if you feel the need of technical assistance at any point of time, then we recommend you to get in touch with our QuickBooks enterprise technical support professionals at 1.800.761.1787. Our experts will be happy to help you.

IELTS AOLCC said...

The world's most popular English language test for higher education and global migration. If you are looking for IELTS Test Center in Ontario - IELTS AOLCC is one of the best options for you. Our IELTS Test Centres are available in Mississauga, Kingston & Brampton.

Lily Evans said...

In this post, you explained everything in an easy manner. Thanks for sharing it.
I hope you will find my recent article helpful. Have a look- Record Opening Balance in QuickBooks

Alex Poter said...

Are you having problems with Quickbooks Update Error 1603 and need professional help? If this is the case, please don't feel free to contact me for assistance. As a representative of the QB support team, I can provide you with the best assistance possible.

QAsolved said...

This blog is more informative and user friendly Thank you. QuickBooks desktop freezing error generates a few off screen window running in the backup, which do not close when you try to shut them. This not freezes the QuickBooks software, but also risks the unsaved data. There can be various factors leading to such an error.

MTB-Bikes said...


Electric transportation

Jhon said...

I’m a first-timer and can’t WAIT to get started on this! It sounds amazing!!!
You can see my latest blog also-
quickbooks error 6069 and quickbooks desktop font size too small

lillianmartin422 said...

We hope that you find this article accommodating enough to Update QuickBooks Desktop to the latest release. And you are able to make the most of QB accounting software with the new updates and features.

Mobile app development company said...

Great article! I found your insights really informative. I would like to share information about the company. Introducing our cutting-edge Grocery App Development Company, where innovation meets convenience! Elevate your grocery shopping experience with our custom-built mobile applications that seamlessly blend technology and user-friendly interfaces.

Jewel Galore said...

Jewelgalore offers a range of stylish ring for men . Explore our collection of elegantly crafted pieces, each designed to add a touch of sophistication and charm to men's fashion.

OSH UNIVERSITY said...

Elevate your expertise with Osh University's postgraduate degree programs. As a leader in education, Osh offers a transformative learning experience, empowering individuals to excel in their chosen fields.

Shalamar Hospital said...

Shalamar Hospital, with the best skin specialist in Lahore , is committed to delivering top-quality dermatological care, prioritizing your skin's health and well-being.

Fix QuickBooks Error said...

QuickBooks Error 12007 is a problem that occurs when QuickBooks software can't connect to the internet to download updates. It might happen due to issues with your internet connection, firewall settings, or other network configurations.

How to fix QuickBooks Error 12007
QuickBooks Error 6123
QuickBooks Error 179

Blue Yonder Corp said...

Chiropractic credit card processing simplifies financial transactions for chiropractors, providing a convenient and secure way for patients to make payments for services rendered. This system seamlessly integrates with chiropractic software, making billing processes smoother and reducing administrative tasks. It guarantees adherence to industry regulations and safeguards sensitive patient data through encryption and secure payment gateways. Chiropractors have the flexibility to accept major credit cards, thereby enhancing convenience for their clients.

Moreover, the system offers customizable reporting features that enable practitioners to efficiently track financial metrics. By incorporating Chiropractic credit card processing, professionals in this field can enhance patient satisfaction, improve financial management, and establish a more streamlined and modernized practice.

Fix QuickBooks Error said...

QuickBooks Error 6129 is a common issue that users encounter while working with the QuickBooks accounting software.

How to fix QuickBooks Error 6129
Quickbooks Error H202
QuickBooks Error 179

How to Fix QuickBooks Error said...

QuickBooks is a powerful accounting software that streamlines financial management for businesses of all sizes. However, like any software, it may encounter occasional errors that can disrupt your workflow. One such error is QuickBooks Error 15241, which often leaves users perplexed. In this blog post, we will explore the causes behind Error 15241 and provide step-by-step solutions to help you get back to smooth financial operations.

Read also:

QuickBooks Error 15311