root labs rdist

January 11, 2010

Smart meter crypto flaw worse than thought

Filed under: Crypto, Embedded, Hacking, Hardware, RFID, Security — Nate Lawson @ 1:08 pm

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.

July 14, 2009

NaCl: DJB’s new crypto library

Filed under: Crypto, Network, Protocols, Security, python — Nate Lawson @ 11:53 am

NaCl is a new crypto library, courtesy of Dan Bernstein of qmail fame and Tanja Lange. After my series of posts on why crypto libraries have seriously hurt web security by offering an API that is too low-level, I was pleased to find NaCl’s main interface is high-level. In addition to the kind of fanatical attention to security you can expect from DJB, it also has his unique (some would say quirky) viewpoint.

On a related note, I’m sorry to say I have to withdraw my recommendation of Google Keyczar. It has had another vulnerability announced, this time in the random source for the python library. This is exactly the same attack against DSA I described previously. I may reconsider this decision as it matures.

There’s a lot Keyczar gets right. Its high-level API and key management make a lot of sense. Up until recently, there haven’t been many high-level libraries I could recommend. Gutmann’s cryptlib is probably the best one. It has been around a while and is implemented in C with multiple language bindings. It is covered by the Sleepycat license, so it works like the GPL or you can pay for closed-source use. GPGME provides well-reviewed crypto with the simple PGP usage model. However, it only offers a C API. It also works by forking the command-line gpg underneath, something that may bother some developers. It is covered by the LGPL license.

While cryptlib and GPGME have been around a while, I have not personally reviewed either of them and can’t vouch for their implementation security. When I found the timing attack in Keyczar’s HMAC verification, I took a brief look around. It seemed ok overall, but I did not do a thorough review. I was so glad to see another high-level library that I included Keyczar along with cryptlib and GPGME as a good alternative to implementing your own crypto in a recent talk. I should have emphasized that while these libraries are taking the right approach, we need much more thorough reviews by cryptographers before standardizing on them. Keyczar, as the newest library of those three, deserved a note that it especially needed review.

NaCl is the latest entry on the scene and it shows a lot of promise. Take a moment to read its design features. The code is public domain. It offers a set of high-level functions such as:

There are some good things to be excited about here. The design is extremely high-speed, although that isn’t my personal priority. The high-level APIs are good but not perfect. For example, the caller is expected to specify a nonce and set certain bytes to zero for crypto_box. This is a little too much control for a high-level API. It might be better if NaCl created its own nonce using its PRNG (/dev/urandom, actually), and then focused on making sure it was seeded well.

The design and implementation security, as expected for DJB, is excellent. (Note that I have not done a thorough review and thus cannot yet recommend it.) For example, he focuses on side channel resistance, creating a non-branching scalar multiplication routine and an API for comparing secrets that resists timing attacks. Also, his design choice of using ECDH, a stream cipher, and a MAC algorithm to implement crypto_box fit together well.

However, that’s where the quirkiness comes in. As with qmail, DJB has a really unique way of doing things. The default ECDH implementation uses Curve25519, the stream cipher is Salsa20, and the authenticator is Poly1305. All of these are primitives designed by DJB in the past four years. If it wasn’t DJB, you’d think I was crazy to even consider a library that implements all new ciphers and constructions. Even though I respect him and these may turn out to be good choices, four years is not enough time to review all of these to be certain they are sound. This will limit NaCl’s appeal until more standard ciphers are available.

While NaCl is a good start, here’s what is missing before it can be more widely adopted:

  • Language bindings: NaCl is C-only for now and needs at least Java, python, and C# bindings
  • More standard crypto primitives: NIST P-256 or other curves, AES, and SHA2-HMAC
  • Signature API: ability to do public-key signatures

Since all these items are marked TODO, it’s clear that Dan recognizes the need for them as well. Perhaps NaCl will mature into the library of choice in the future. If you’re a cryptographer and have a chance to review it, please publish your findings. If you’re a developer, how about contributing language bindings?

On a side note, I’m convinced that the right way to create a crypto library is to do a single implementation in C with architecture awareness (e.g., cache layout, some assembly language) and then offer language bindings. This is the route NaCl and cryptlib took. It’s nearly impossible to prevent side channel attacks when your crypto is implemented in a high-level language.

May 17, 2009

The Debian PGP disaster that almost was

Filed under: Crypto, Hacking, Network, Protocols, Security — Nate Lawson @ 5:23 pm

A year ago, I wrote about the Debian OpenSSL PRNG bug that reduced the entropy of its random seed to 15 bits. There was a little-noticed part of the advisory that said all DSA keys used on the affected systems should be considered compromised. In the rush to find and replace SSL certs and SSH keys generated on Debian or Ubuntu systems, very few people grasped the significance of this other warning. This is important because an attacker can retroactively seek out DSA signatures generated during the vulnerable period and use them to recover your private key.

DSA is a public-key signature algorithm. Unlike RSA, it isn’t useful for encryption or key exchange. Like other public key algorithms, it is extremely sensitive to the choice of parameters. I’ve written about RSA signature flaws (1, 2, 3) that resulted from too much ambiguity in how a signature verify operation was interpreted.

With DSA, the entropy of the random signature value k is critical. It is so critical that knowledge of only a few bits of k can reveal your entire private key to an attacker. Interestingly enough, the Wikipedia article on DSA doesn’t mention this concern. This is why it’s so important to get your crypto reviewed by an expert. Small, obscure flaws can cause immense damage.

To generate a DSA signature, the signer calculates (r, s) as follows:

r = gk mod p mod q
s = k-1 (H(m) + x*r) mod q

The message to be signed is m, H(m) is the SHA hash function, and p and q are primes. The value k is a random nonce and x is the signer’s private key. If an attacker knows k and has a single signature (r, s), he can recover the signer’s private key with a simple calculation. In the case of the vulnerable PRNG, he can just repeat this process for all 32,767 possible values. Remember that the message m is not secret, so neither is the SHA-1 hash H(m). The attacker calculates x as follows:

x = ((s * k) – H(m)) * r-1 mod q

The impact of this attack is that every signature generated on a vulnerable system reveals the signer’s private key. An attacker can find old signatures by crawling your website, examining signed email, analyzing saved packet captures of an SSL exchange, etc. The associated DSA key has to be revoked, regenerated and redistributed. Luckily for Debian, their packages are signed using GnuPG, which did not use the OpenSSL PRNG. But for anyone using other software based on OpenSSL, you need to revoke all DSA keys used to sign data on vulnerable Debian or Ubuntu systems. Even if the key was generated securely, a single insecure signature reveals the entire private key. It’s that bad.

I hope a year has been enough time for people to revoke their DSA keys, even though the warning was somewhat obscure. Thanks to Peter Pearson for interesting discussions about this issue.

December 30, 2008

Forged CA cert talk at 25C3

Filed under: Crypto, Hacking, Network, Security — Nate Lawson @ 10:29 am

A talk entitled “MD5 considered harmful today” (slides) is being presented at 25C3. The authors describe forging a CA cert that will be accepted by all browsers by exploiting the fact that several trusted root CAs sign certs with MD5. This allows them to spoof their identity as any SSL-enabled website on the Internet, and it will look perfectly valid to the user.

The growth of trusted root CAs included in standard browsers has been an issue for a while. Every root CA is equal in the eyes of the browser, thus the end-user’s security is equivalent to the security of the weakest root CA. The default Firefox install will accept a Yahoo cert signed by “TurkTrust”, or any other of more than 100 root certs. I don’t know how good each of those companies are at securing their keys, implementing strict cert chain validation, and checking the identity of every submitter. So, it’s a good bet that putting crypto authority in the hands of that many people will result in some failures, repeatedly.

The attack is interesting since they take advantage of more than one flaw in a CA. First, they find a CA that still uses MD5 for signing certs. MD5 has been broken for years, and no CA should have been doing this. Next, they prepared an innocent-looking cert request containing the “magic values” necessary to cause an MD5 collision. They were able to do this because of a second flaw. The CA in question used an incrementing serial number instead of a random one. Since the serial is part of the signed data, it is a cheap way to get some randomness. This would have thwarted this particular attack until a pre-image vulnerability was found in MD5. Don’t count on this for security! MD4 fell to a second pre-image attack a few years after the first collision attacks, and attacks only get better over time.

This talk definitely points out that crypto attacks are not being addressed quickly enough in the real world. While it is difficult to roll out a new root CA cert, it’s better to do so over the years we have known MD5 to be insecure than in a rush after an attack has already occurred. Another excellent talk at 25C3 on the iPhone described how the baseband processor was compromised via the lack of validation of RSA signature padding. What’s intriguing is that Apple’s own RSA implementation in their CDSA code was not vulnerable to this flaw, but apparently a different vendor supplied the baseband code.

To paraphrase Gibson, “Crypto security is available already, it just isn’t equally distributed.”

December 17, 2007

SSL design principles talk

Filed under: Crypto, Network, Security — Nate Lawson @ 11:12 am

I recently gave a talk to a networking class at Cal Poly on the design principles behind SSL. The talk was a bit basic because I had to assume the class had little security experience. My approach was to discuss how it works and stop at each phase of the protocol, asking what security flaws might be introduced by changing or removing elements. This worked well to get them thinking about why SSL has certain components that appear weird at first glance but make sense after closer inspection.

Others have told me that they use a similar technique when learning a new crypto algorithm by starting with the simplest primitive, identifying attacks, and then adding subsequent elements until the whole algorithm is present. If attacks still exist, the algorithm is flawed.

For example, consider DSA, one of the more complex signature schemes. Use the random value k directly (instead of calculating r = (gk mod p) mod q) and the signature operation is simply:

s = k-1(H(m)) + x mod q

This introduces a fatal flaw. k-1 can be calculated from k via the extended Euclidean algorithm. The message is usually known, and thus H(m) is also. Thus, this would directly reveal the private key x to any recipient!

The references section at the end of the talk gives a good intro to the design principles behind SSL, especially the Wagner et al paper. My next articles will explain some SSL attacks in more detail.

March 29, 2007

Chain, defense-in-depth, and mesh models again

Filed under: Crypto, Network, Security, Software protection — Nate Lawson @ 2:50 pm

Richard Bejtlich recently discussed my posts on the mesh design model. Thomas Ptacek added a post comparing the three terms I’ve described. Since there is still some confusion, let me try to summarize.

Chain: break one of N mechanisms, all equally compromise your system. Example: SSL load-balancers that terminate and then re-encrypt a session. Attack: extract the private key from the load balancer OR the backend server, whichever is easier.

Defense-in-depth: break all N mechanisms (often in order: 1, 2, 3, …) to compromise the system. Example: multiple separately-configure firewalls (i.e. DMZ). Attack: traverse firewall 1, then firewall 2, then access database server.

Mesh: break all N mechanisms at exactly the same time. Sequential, incremental compromise is not possible as it is with a purely defense-in-depth approach. Example: cryptographic key where each bit is independent of all the others. Attack: guess all bits correctly (i.e. brute force).

Each of these models has its strengths and weaknesses and should be used where appropriate. SSH public key authentication is a chain model. The server trusts your public key signature which was generated from a key that you decrypted using your passphrase. This is a useful chain since it’s much easier to remember a passphrase than a 256-byte random string. But it also means the server is equally compromised if you type in your passphrase from a public terminal, use a weak passphrase and the attacker does a dictionary attack on your private key file, or the private key is hijacked from RAM of a persistent SSH connection. That’s a series of risks that I understand and am willing to accept in order to avoid memorizing my DSA key.

Also, defense-in-depth can be used to provide multiple layers of mesh when each layer cannot be interlinked with the others to form a single mesh. For example, the mesh model can be applied to a set of self-checks that my network game client performs on itself to make sure it hasn’t been trojaned. And my server can implement extra interleaved protocol steps (another mesh) to verify that it’s talking to my self-checking game client, and not a generic one that has been swapped in by a cheater. The combination of applying the mesh model in both places is defense-in-depth since both can be attacked independently.

All this semantics isn’t useful without concrete examples. Next, I’ll be providing examples of applying the mesh model to solving common security problems.

Blog at WordPress.com.