Category: Crypto

The Debian PGP disaster that almost was

~ Nate Lawson ~ 3 Comments

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.

Preventing branch prediction timing attacks

~ Nate Lawson

A few years ago, Aciicmez et al published a new timing attack (1, 2, 3) exploiting the branch prediction feature of x86 processors. They explained how to extract the RSA private key in one process by monitoring the behavior of the branch prediction unit in a concurrent spy process. This is an extension of the previous work on improving cache timing attacks (see also Percival and Bernstein).

These kinds of attacks all target microarchitectural features of the processor where a shared resource (I or D-cache, branch prediction buffer) is maintained by the processor across context switches. Any resource that is instruction or data-dependent and can be measured outside the security boundary can potentially be used for side-channel attacks.

Most developers don’t get the security boundary right. Usually, they will consider the whole machine as the boundary. But of course, even this simple concept can be more complicated in practice (say, host vs. guest VM environments). Others consider the OS process boundary as their security boundary. But consider a web server process with built-in SSL. After the SSL decryption, any changes in the performance of the general webserver code due to the cache state of the SSL decryption may reveal information about the private key. Thus, it is important to first draw the security boundary as narrowly as possible.

In a branch prediction attack, the attacker typically runs a spy process concurrently with the cipher. It repeatedly does the following:

  1. Execute a set of branches
  2. Measure the overall execution time of all its branches

Since an RSA decryption happens over a relatively long period of time, the cache and BTB state can be measured multiple times by the spy process during a single decryption. Public key algorithms take longer because they are doing a multi-word computation, and there are often conditional branches based on the private key. Also, the spy process can do various things to try to force the crypto process to context-switch more often.

Last year, I wrote about the patch Intel submitted to mitigate cache timing attacks. The OpenSSL patch they submitted for dealing with branch prediction attacks (“Smooth CRT-RSA”) is also interesting. They created new big number functions BN_mod_inverse_no_branch() and BN_div_no_branch(), which remove any conditional branches based on information related to the private key. See section 5.3 of their paper for details or just read the comments in the diff above.

The key insight behind these functions is that the extra reduction step can be eliminated if the domain for the value returned by Montgomery-Multiply can be extended. The modulus n in RSA is composed of two primes, p and q. The MMUL algorithm returns a value from [p, 2p). This means the naive implementation performs an optional extra reduction to fit the value into the range [0, p). The patch avoids this reduction by adding an extra word to the parameters passed to MMUL, effectively zero-padding them. Additionally, the Montgomery parameters are increased by n/2 to account for this modified range.

The lesson from all this is that it’s very hard to eliminate side channels, and you have to be careful when defining the security boundary. Even if you used this branchless CRT implementation, you might still be vulnerable to timing attacks if you used a naive algorithm for loading the private key from a file and converting it to binary format in memory (e.g., for loop with atoi()).

Felten on fingerprinting blank paper

~ Nate Lawson

Ed Felten posted last week about his upcoming publication on fingerprinting techniques for blank paper. This is a great paper with practical applications. It reminded me to discuss some of the fundamental issues with fingerprinting and the potential problems when it comes to real-world forgery.

Long ago, some copy protections for floppy disks used a method known as “weak bits”. The mastering equipment would write a long string of zeros to the disk. This would cause the read head to return a varying string of bits with some pattern to it. The software would check that this region returned different values each time it was read to make sure it wasn’t a copy.

Similar techniques have also been applied to magstripe media for credit cards. Magtek makes a reader that attempts to measure physical characteristics of the magnetic stripe and submit this as a fingerprint for a given card. The general idea is that while the data on a card can be easily duplicated with a reader, the manufacturing process for the physical media leaves behind certain random “noise” that is difficult to reproduce.

This is similar to the Felten paper. They attempt to create a unique fingerprint for a piece of paper based on the variations in fibers that are visible with a high-resolution scan. They take multiple scans from different angles as well.

All of these techniques have something in common. The characteristic being measured must actually have some uniqueness. There must be a cost-effective way to measure that characteristic. There must be a sampling mechanism that chooses different areas to examine. The fingerprint algorithm must combine the samples in a way that is resilient to natural errors (i.e., no false positives). Yet it also must be difficult for a forger to create a copy that is close enough to the original to be accepted by the verifier (i.e., no false negatives).

Both magstripes and paper appear to have enough inherent uniqueness. The manufacturing techniques of both do create a lot of low-level variation. But once this requirement is satisfied, the fingerprint approach itself is still subject to fundamental limitations. No fingerprinting method can avoid them. It needs to be resilient not only in the face of regular use (e.g., crumpling the paper) but also with intentionally malicious manipulation. The conflicting requirements to avoid false positives and yet also be difficult to clone are always the most difficult part of any kind of fingerprinting scheme. This is a fundamental problem with any kind of statistical decision process.

There are two kinds of forgery attacks: second pre-image and collision. The former is the most obvious one, where an attacker creates a copy that matches some existing original. The latter is much harder to prevent. To create a collision, that attacker can pre-process two pieces of paper in order to create two documents that the fingerprint algorithm judges as close enough to be identical. For example, the attacker can write a sequence of small dots to both pages in a similar pattern before printing the text. He can repeat this multiple times while varying the pattern until the verifier judges the papers as close enough. Depending on the sampling algorithm and the attacker’s printing capabilities, this may be more difficult. Section 6 of the paper discusses this kind of attack but it mostly focuses on preventing a second pre-image attack and most of the analysis is left for the future.

The key thing to remember is that the attacker does not need to make the papers actually identical by reproducing the exact pattern of fibers on the paper. The attacker doesn’t even have to have a particularly fine dot resolution, as long as the position of the dots can be controlled. The idea is that the printed pattern overwhelms the fine characteristics measured by the scanner and thus two documents are judged to be close enough by the verifier. It also would be interesting to see how the fingerprint technique does against darker colored paper.

This attack illustrates the fundamental limitation of this kind of fingerprint method. The verifier has to allow for some variation to prevent false positives. But an attacker can repeatedly try to exploit that rejection region by creating various pairs of documents until they pass.

All of this is based on a preliminary read of the paper, so I’m interested in what the Felten team plans to do to address this kind of problem.

SSL is not table salt

~ Nate Lawson ~ 4 Comments

While I haven’t written an article in a while, I’m still alive. I just got buried with work, tax prep, and using every spare moment to try to finish up the xum1541. Last week, I attended the iSec Forum and saw a talk about cookie forcing based on work by Chris Evans and Michael Zalewski. This attack involves overwriting SSL-only cookies with a cookie injected into a non-SSL connection. In other words, browsers prevent disclosure of SSL-only cookies, but not deletion or replacement by cookies from an insecure session.

I don’t follow network security closely so this may be an older attack. However, it reminds me how the web application and browser designers treat SSL like table salt — sprinkle a little bit here and there, but be careful not to overuse it. That’s completely the wrong mentality.

WordPress recently notified their users how to enable SSL for the admin interface. While it’s admirable that they are providing more security, the attitude behind the post is a great example of this dangerous mentality. They claim SSL is only recommended when blogging from a public network, even going so far as to suggest it be disabled again when back on a “secure network”. It’s hard to believe performance is the issue, given the CPU gains in the past 13 years.

Attention: if you’re using a web application on a shared network (say, the Internet), you’re not on a secure network. This whole idea that users should pick and choose SSL based on some ephemeral security assessment of the local network is insane. How can you expect anyone, let alone regular users, to perform a security assessment before disabling SSL and then remember to re-enable it before traveling to an insecure network? (You can’t log into your blog and re-enable SSL from the insecure network because you would get compromised doing so.)

Likewise, sites such as Yahoo Mail use SSL for submitting the login password, but then provide a session cookie over plain HTTP. A session cookie is almost as good as a password. As long as the attacker refreshes their own session periodically, the cookie stays valid. (Do any web services implement an absolute session limit?) Even if the user clicks “log out”, the attacker can feed a fake logout page to them and keep the cookie active.

All cookies should definitely have their own cryptographic integrity protection and encryption, independent of SSL. But it is clear that the entire attitude toward SSL is wrong, and we will all eventually have to change it. Open wireless networks have helped session hijacking proliferate, no ARP spoofing needed. Soon, malware may contain a MITM kit to compromise any user accessing a website who shares an access point with a rooted system. As this attack becomes more common, perhaps we’ll see the end of SSL as an accessory, and it will be mandated for the entirety of every authenticated session. The prevailing attitude will have to change first.

Forged CA cert talk at 25C3

~ Nate Lawson ~ 3 Comments

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

More dangers of amateur crypto

~ Nate Lawson ~ 1 Comment

The Good Math blog continues to inadvertently provide examples of how subtle mistakes in cryptography are often fatal. I previously wrote about how slightly incorrect crypto examples on a reputable blog can lead engineers astray. The latest post about RSA is no exception, but I’ll have to write about it here since my comment was deleted. The comments by Oscar on that post are a good criticism.

The most important error in Mark’s description of RSA is that his example for encryption uses the private key D, instead of the public key E. The result of the RSA private key operation with D is called the “CipherText”. The decryption process is described using the public key E.

At first glance, this seems like an awkward description but still sound, right? If you wanted to exchange RSA-encrypted messages between two systems, couldn’t you just generate an RSA key pair and keep both keys secret? The surprising result is that this is completely insecure, and it is impossible to keep an RSA public key secret, even if the key (E, N) is never revealed.

I previously wrote a series of posts about a system that made this exact mistake. The manufacturer had burned an RSA public key (E, N) into a chip in order to verify a signature on code updates. This is perfectly fine, assuming the implementation was correct. However, they additionally wanted to use the same public key parameters to decrypt the message, keeping E and N secret. In the first article, I described this system and in the second, I discussed how to attack it given that the attacker has seen only two encrypted/signed updates. In summary, the modulus N is partially revealed by each message you see “encrypted” with (D, N) and the GCD quickly computes it.

Subtle details matter, especially in public key crypto. The two keys in an RSA pair are indeed asymmetric, and have very different properties. They cannot be substituted for each other. You cannot securely encrypt a message using the private key (D, N). Such a system would be completely insecure.