rdist

November 19, 2010

DSA requirements for random k value

Filed under: Crypto,Protocols,Security — Nate Lawson @ 2:33 pm

Most public key systems fail catastrophically if you ignore any of their requirements. You can decrypt RSA messages if the padding is not random, for example. With DSA, many implementation mistakes expose the signer’s private key.

Many crypto protocols use a nonce. The traditional requirements of a nonce is that it never be repeated. So a simple counter can suffice, as long as it is safely persisted. Using a timestamp is problematic if the clock ever goes backwards (say, NTP) or you need to generate two messages in a short interval.

In DSA, the k value is not a nonce. In addition to being unique, the value must be unpredictable and secret. This makes it more like a random session key than a nonce. When an implementer gets this wrong, they expose the private key, often with only one or two signatures.

If k is predictable, there is a way to recover the private key from a single signature with straightforward algebra. Since a past weakness in the Debian PRNG resulted in only 32767 possible outputs, an attacker could recover any DSA private key where a single signature was generated on a vulnerable Debian system. The key could have been generated securely on a system without this flaw, but that single signature would compromise it.

But what about the requirement that k be unique? Assume there’s an email signing system that has a secure PRNG but it is rate-limited so two requests that come in quickly from the same process produce the same output. As an attacker, you can’t predict k but you suspect the signing system may have this weakness.

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

If you see a repeated r value, then you know k has been repeated. Build a web crawler to find DSA signatures. Dump its output into a parser for a bunch of formats (X509v3, PGP, PKCS#7, etc.) From each signature file, insert each r value into a key-value database and look for a match. If you find any two matching r values, you can recover the signer’s private key.

The algebra to do so is pretty straightforward. Given two signatures for messages MA and MB, we want to solve for k.

SA = k-1 (H(MA) + x*r) mod q
SB = k-1 (H(MB) + x*r) mod q

Subtract the two signatures. (The modular reduction step is implicit from here on for readability.)

SA – SB = k-1 (HA + x*r) – k-1 (HB + x*r)

Redistribute. Since the k’s are identical, their inverse is also.

SA – SB = k-1 (HA + x*r – HB – x*r)

The x*r values cancel out.

SA – SB = k-1 (HA – HB)

Redistribute.

k = (HA – HB) / (SA – SB)

Once you have k, you can solve for x directly as in the previous post. There is a more complicated technique for solving for x if only a few bits of k are known, requiring more signatures.

It is extremely important that all bits of k be unique, unpredictable, and secret. With two DSA signatures on separate messages with the same k, you can recover the signer’s private key.

September 20, 2011

Recovering a private key with only a fraction of the bits

Filed under: Crypto,Security — Nate Lawson @ 10:43 am

Ever since my first post on breaking DSA, I’ve been meaning to write a clear description of how to recover a private key if you only have a fraction of the bits. For example, power analysis attacks may allow you to derive a few bits of the random k value on each measurement. It turns out you can combine multiple measurements to get a single k value and then recover the DSA private key. Of course, all this also applies to ECDSA.

Since I haven’t had time to put together a good summary article, here are some references for learning this on your own. The first paper in this area was Boneh and Venkatesan (1996). They described the basic Hidden Number Problem.

The next important paper was by Howgrave-Graham and Smart (1999) [1]. They used Babai’s algorithm[2] and LLL lattice reduction to solve for DSA private nonces. This was improved by Nguyen and Shparlinski (2000) [3] to solve for just the k values.

This attack applies any time the DSA nonce isn’t fully random and used only one time. It applies if a few of the bits are constant, if the RNG is biased towards certain values, or if you can recover part of the values by side channel attacks. These references should allow you to implement this attack yourself. It has been repeatedly used in private work, but I haven’t seen much public discussion about applying this to real-world systems.

[1] Howgrave-Grahm and Smart. “Lattice attacks on Digital Signature Schemes.” HP internal publication, 1999.
[2] Laszlo Babai. “On Lovász lattice reduction and the nearest lattice point problem.” Combinatorica 6. No online reference found.
[3] Nguyen and Shparlinski. “The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces.” Journal of Cryptology, volume 15, pp. 151-176, 2000.

Addendum: I found the following references to improve this list.

August 18, 2010

Crypto 2010 rump session

Filed under: Crypto,Security — Nate Lawson @ 2:59 pm

One of the leading indicators of upcoming advances in cryptography is the rump session at the CRYPTO conference. Speakers are given 3 minutes to introduce works in progress or crack jokes. For example, I remember Paul Kocher’s groundbreaking presentation on extremely low exponent RSA (e=1). Here is more history of this casual, but important, event each year.

This year’s session had some interesting talks, mostly about SHA-3 hash candidates. Dinur and Shamir announced an algebraic attack on Hamsi-256, which has had other attacks announced previously. They also attacked the Grain-128 stream cipher. Leurent spoke about distinguishing attacks and whether a hash function can remain secure even when the underlying compression function has efficient distinguishers.

Cohn and Heninger presented a survey of applications of Coppersmith’s theorem, which has many uses beyond cryptanalysis of public key systems. There was a lot of interest in making public key systems resilient in the face of leakage (e.g., via side channels). This is good since traditional (EC)DSA falls apart if the nonce is even partially predictable. A presentation on noisy Diffie-Hellman looked interesting, although the applications are unclear to me.

On the implementation front, Mroczkowski described a fast implementation of Trivium in Python. It used the CorePy library to generate SSE3 instructions. This was to optimize the cube attack previously announced by Dinur and Shamir in 2008.

And finally, the humorous CFP for the Journal of Craptology was a great way to end. What were your favorite rump session talks?

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,python,Security — 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.

Next Page »

Blog at WordPress.com.