A Few Thoughts on Cryptographic Engineering

Some random thoughts about crypto. Notes from a course I teach. Pictures of my dachshunds.

[matthewdgreen]

Noodling about IM protocols

The last couple of months have been a bit slow in the blogging department. It's hard to blog when there are exciting things going on. But also: I've been a bit blocked. I have two or three posts half-written, none of which I can quite get out the door.

Instead of writing and re-writing the same posts again, I figured I might break the impasse by changing the subject. Usually the easiest way to do this is to pick some random protocol and poke at it for a while to see what we learn. 

The protocols I'm going to look at today aren't particularly 'random' -- they're both popular encrypted instant messaging protocols. The first is OTR (Off the Record Messaging). The second is Cryptocat's group chat protocol. Each of these protocols has a similar end-goal, but they get there in slightly different ways.

I want to be clear from the start that this post has absolutely no destination. If you're looking for exciting vulnerabilities in protocols, go check out someone else's blog. This is pure noodling.

The OTR protocol

OTR is probably the most widely-used protocol for encrypting instant messages. If you use IM clients like Adium, Pidgin or ChatSecure, you already have OTR support. You can enable it in some other clients through plugins and overlays.

OTR was originally developed by Borisov, Goldberg and Brewer and has rapidly come to dominate its niche. Mostly this is because Borisov et al. are smart researchers who know what they’re doing. Also: they picked a cool name and released working code.

OTR works within the technical and usage constraints of your typical IM system. Roughly speaking, these are:

Messages must be ASCII-formatted and have some (short) maximum length.

Users won't bother to exchange keys, so authentication should be "lazy" (i.e., you can authenticate your partners after the fact).

Your chat partners are all FBI informants so your chat transcripts must be plausibly deniable -- so as to keep them from being used as evidence against you in a court of law.

Coming to this problem fresh, you might find goal (3) a bit odd. In fact, to the best of my knowledge no court in the history of law has ever used a cryptographic transcript as evidence that a conversation occurred. However it must be noted that this requirement makes the problem a bit more sexy. So let's go with it!

"Dammit, they used a deniable key exchange protocol" said no Federal prosecutor ever.

The OTR (version 2/3) handshake is based on the SIGMA key exchange protocol. Briefly, it assumes that both parties generate long-term DSA public keys which we'll denote by (pubA, pubB). Next the parties interact as follows:

The OTRv2/v3 AKE. Diagram by Bonneau and Morrison, all colorful stuff added. There's also an OTRv1 protocol that's too horrible to talk about here.

There are four elements to this protocol:

Hash commitment. First, Bob commits to his share of a Diffie-Hellman key exchange (g^x) by encrypting it under a random AES key r and sending the ciphertext and a hash of g^x over to Alice.  

Diffie-Hellman Key Exchange. Next, Alice sends her half of the key exchange protocol (g^y). Bob can now 'open' his share to Alice by sending the AES key r that he used to encrypt it in the previous step. Alice can decrypt this value and check that it matches the hash Bob sent in the first message. Now that both sides have the shares (g^x, g^y) they each use their secrets to compute a shared secret g^{xy} and hash the value several ways to establish shared encryption keys (c', Km2, Km'2) for subsequent messages. In addition, each party hashes g^{xy} to obtain a short "session ID". The sole purpose of the commitment phase (step 1) is to prevent either Alice or Bob from controlling the value of the shared secret g^{xy}. Since the session ID value is derived by hashing the Diffie-Hellman shared secret, it's possible to use a relatively short session ID value to authenticate the channel, since neither Alice nor Bob will be able to force this ID to a specific value.  

Exchange of long-term keys and signatures. So far Alice and Bob have not actually authenticated that they're talking to each other, hence their Diffie-Hellman exchange could have been intercepted by a man-in-the-middle attacker. Using the encrypted channel they've previously established, they now set about to fix this. Alice and Bob each send their long-term DSA public key (pubA, pubB) and key identifiers, as well as a signature on (a MAC of) the specific elements of the Diffie-Hellman message (g^x, g^y) and their view of which party they're communicating with. They can each verify these signatures and abort the connection if something's amiss.**  

Revealing MAC keys. After sending a MAC, each party waits for an authenticated response from its partner. It then reveals the MAC keys for the previous messages.  

Lazy authentication. Of course if Alice and Bob never exchange public keys, this whole protocol execution is still vulnerable to a man-in-the-middle (MITM) attack. To verify that nothing's amiss, both Alice and Bob should eventually authenticate each other. OTR provides three mechanisms for doing this: parties may exchange fingerprints (essentially hashes) of (pubA, pubB) via a second channel. Alternatively, they can exchange the "session ID" calculated in the second phase of the protocol. A final approach is to use the Socialist Millionaires' Problem to prove that both parties share the same secret.

The OTR key exchange provides the following properties: Protecting user identities. No user-identifying information (e.g., long-term public keys) is sent until the parties have first established a secure channel using Diffie-Hellman. The upshot is that a purely passive attacker doesn't learn the identity of the communicating partners -- beyond what's revealed by the higher-level IM transport protocol.* Unfortunately this protection fails against an active attacker, who can easily smash an existing OTR connection to force a new key agreement and run an MITM on the Diffie-Hellman used during the next key agreement. This does not allow the attacker to intercept actual message content -- she'll get caught when the signatures don't check out -- but she can view the public keys being exchanged. From the client point of view the likely symptoms are a mysterious OTR error, followed immediately by a successful handshake. One consequence of this is that an attacker could conceivably determine which of several clients you're using to initiate a connection. Weak deniability. The main goal of the OTR designers is plausible deniability. Roughly, this means that when you and I communicate there should be no binding evidence that we really had the conversation. This rules out obvious solutions like GPG-based chats, where individual messages would be digitally signed, making them non-repudiable. Properly defining deniability is a bit complex. The standard approach is to show the existence of an efficient 'simulator' -- in plain English, an algorithm for making fake transcripts. The theory is simple: if it's trivial to make fake transcripts, then a transcript can hardly be viewed as evidence that a conversation really occurred. OTR's handshake doesn't quite achieve 'strong' deniability -- meaning that anyone can fake a transcript between any two parties -- mainly because it uses signatures. As signatures are non-repudiable, there's no way to fake one without actually knowing your public key. This reveals that we did, in fact, communicate at some point. Moreover, it's possible to create an evidence trail that I communicated with you, e.g., by encoding my identity into my Diffie-Hellman share (g^x). At very least I can show that at some point you were online and we did have contact. But proving contact is not the same thing as proving that a specific conversation occurred. And this is what OTR works to prevent. The guarantee OTR provides is that if the target was online at some point and you could contact them, there's an algorithm that can fake just about any conversation with the individual. Since OTR clients are, by design, willing to initiate a key exchange with just about anyone, merely putting your client online makes it easy for people to fake such transcripts.*** Towards strong deniability. The 'weak' deniability of OTR requires at least tacit participation of the user (Bob) for which we're faking the transcript. This isn't a bad property, but in practice it means that fake transcripts can only be produced by either Bob himself, or someone interacting online with Bob. This certainly cuts down on your degree of deniability. A related concept is 'strong deniability', which ensures that any party can fake a transcript using only public information (e.g., your public keys).

OTR doesn't try achieve strong deniability -- but it does try for something in between. The OTR version of deniability holds that an attacker who obtains the network traffic of a real conversation -- even if they aren't one of the participants -- should be able alter the conversation to say anything he wants. Sort of. The rough outline of the OTR deniability process is to generate a new message authentication key for each message (using Diffie-Hellman) and then reveal those keys once they've been used up. In theory, a third party can obtain this transcript and -- if they know the original message content -- they can 'maul' the AES-CTR encrypted messages into messages of their choice, then they can forge their own MACs on the new messages.

OTR message transport (source: Bonneau and Morrison, all colored stuff added).

Thus our hypothetical transcript forger can take an old transcript that says "would you like a Pizza" and turn it into a valid transcript that says, for example, "would you like to hack STRATFOR"... Except that they probably can't, since the first message is too short and... oh lord, this whole thing is a stupid idea -- let's stop talking about it. The OTRv1 handshake. Oh yes, there's also an OTRv1 protocol that has a few issues and isn't really deniable. Even better, an MITM attacker can force two clients to downgrade to it, provided both support that version. Yuck. So that's the OTR protocol. While I've pointed out a few minor issues above, the truth is that the protocol is generally an excellent way to communicate. In fact it's such a good idea that if you really care about secrecy it's probably one of the best options out there. Cryptocat Since we're looking at IM protocols I thought it might be nice to contrast with another fairly popular chat protocol: Cryptocat's group chat. Cryptocat is a web-based encrypted chat app that now runs on iOS (and also in Thomas Ptacek's darkest nightmares). Cryptocat implements OTR for 'private' two-party conversations. However OTR is not the default. If you use Cryptocat in its default configuration, you'll be using its hand-rolled protocol for group chats. The Cryptocat group chat specification can be found here, and it's remarkably simple. There are no "long-term" keys in Cryptocat. Diffie-Hellman keys are generated at the beginning of each session and re-used for all conversations until the app quits. Here's the handshake between two parties:

Cryptocat group chat handshake (current revision). Setting is Curve25519. Keys are generated when the application launches, and re-used through the session.

If multiple people join the room, every pair of users repeats this handshake to derive a shared secret between every pair of users. Individuals are expected to verify each others' keys by checking fingerprints and/or running the Socialist Millionaire protocol. Unlike OTR, the Cryptocat handshake includes no key confirmation messages, nor does it attempt to bind users to their identity or chat room. One implication of this is that I can transmit someone else's public key as if it were my own -- and the recipients of this transmission will believe that the person is actually part of the chat. Moreover, since public keys aren't bound to the user's identity or the chat room, you could potentially route messages between a different user (even a user in a different chat room) while making it look like they're talking to you. Since Cryptocat is a group chat protocol, there might be some interesting things you could do to manipulate the conversation in this setting.****

Does any of this matter? Probably not that much, but it would be relatively easy (and good) to fix these issues. Message transmission and consistency. The next interesting aspect of Cryptocat is the way it transmits encrypted chat messages. One of the core goals of Cryptocat is to ensure that messages are consistent between individual users. This means that all users should be able to verify that the other user is receiving the same data as it is. Cryptocat uses a slightly complex mechanism to achieve this. For each pair of users in the chat, Cryptocat derives an AES key and an MAC key from the Diffie-Hellman shared secret. To send a message, the client:

Pads the message by appending 64 bytes of random padding.

Generates a random 12-byte Initialization Vector for each of the N users in the chat.

Encrypts the message using AES-CTR under the shared encryption key for each user.

Concatenates all of the N resulting ciphertexts/IVs and computes an HMAC of the whole blob under each recipient's key.

Calculates a 'tag' for the message by hashing the following data: padded plaintext || HMAC-SHA512alice || HMAC-SHA512bob || HMAC-SHA512carol || ...

Broadcasts the N ciphertexts, IVs, MACs and the single 'tag' value to all users in the conversation.

When a recipient receives a message from another user, it verifies that:

The message contains a valid HMAC under its shared key.

This IV has not been received before from this sender.

The decrypted plaintext is consistent with the 'tag'.

Roughly speaking, the idea here is to make sure that every user receives the same message. The use of a hashed plaintext is a bit ugly, but the argument here is that the random padding protects the message from guessing attacks. Make what you will of this. Anti-replay. Cryptocat also seeks to prevent replay attacks, e.g., where an attacker manipulates a conversation by simply replaying (or reflecting) messages between users, so that users appear to be repeating statements. For example, consider the following chat transcripts:

Replays and reflection attacks. 

Replay attacks are prevented through the use of a global 'IV array' that stores all previously received and sent IVs to/from all users. If a duplicate IV arrives, Cryptocat will reject the message. This is unwieldy but it generally seems ok to prevent replays and reflection. A limitation of this approach is that the IV array does not live forever. In fact, from time to time Cryptocat will reset the IV array without regenerating the client key. This means that if Alice and Bob both stay online, they can repeat the key exchange and wind up using the same key again -- which makes them both vulnerable to subsequent replays and reflections. (Update: This issue has since been fixed). In general the solution to these issues is threefold:

Keys shouldn't be long-term, but should be regenerated using new random components for each key exchange.

Different keys should be derived for the Alice->Bob and Bob->Alice direction

It would be be more elegant to use a message counter than to use this big, unwieldy key array.

The good news is that the Cryptocat developers are working on a totally new version of the multi-party chat protocol that should be enormously better.

In conclusion

I said this would be a post that goes nowhere, and I delivered! But I have to admit, it helps to push it out of my system.

None of the issues I note above are the biggest deal in the world. They're all subtle issues, which illustrates two things: first, that crypto is hard to get right. But also: that crypto rarely fails catastrophically. The exciting crypto bugs that cause you real pain are still few and far between.

Notes:

* In practice, you might argue that the higher-level IM protocol already leaks user identities (e.g., Jabber nicknames). However this is very much an implementation choice. Moreover, even when using Jabber with known nicknames, you might access the Jabber server using one of several different clients (your computer, phone, etc.). Assuming you use Tor, the only indication of this might be the public key you use during OTR. So there's certainly useful information in this protocol. ** Notice that OTR signs a MAC instead of a hash of the user identity information. This happens to be a safe choice given that the MAC used is based on HMAC-SHA2, but it's not generally a safe choice. Swapping the HMAC out for a different MAC function (e.g., CBC-MAC) would be catastrophic. *** To get specific, imagine I wanted to produce a simulated transcript for some conversation with Bob. Provided that Bob's client is online, I can send Bob any g^x value I want. It doesn't matter if he really wants to talk to me -- by default, his client will cheerfully send me back his own g^y and a signature on (g^x, g^y, pub_B, keyid_B) which, notably, does not include my identity. From this point on all future authentication is performed using MACs and encrypted under keys that are known to both of us. There's nothing stopping me from faking the rest of the conversation. **** Incidentally, a similar problem exists in the OTRv1 protocol. 

[matthewdgreen]

Attack of the Week: Triple Handshakes (3Shake)

3Shake logo designed by @Raed667

The other day Apple released a major security update that fixes a number of terrifying things that can happen to your OS/X and iOS devices. You should install it. Not only does this fix a possible remote code execution vulnerability in the JPEG parser (!), it also patches a TLS/SSL protocol bug known as the "Triple Handshake" vulnerability. And this is great timing, since Triple Handshakes are something I've been meaning (and failing) to write about for over a month now. But before we get there: a few points of order. First, if Heartbleed taught us one thing, it's that when it comes to TLS vulnerabilities, branding is key. Henceforth, and with apologies to Bhargavan, Delignat-Lavaud, Pironti,  Fournet and Strub (who actually discovered the attack*), for the rest of this post I will be referring to the vulnerability simply as "3Shake". I've also taken the liberty of commissioning a logo. I hope you like it. On a more serious note, 3Shake is not Heartbleed. That's both good and bad. It's good because Heartbleed was nasty and 3Shake really isn't anywhere near as dangerous. It's bad since, awful as it was, Heartbleed was only an implementation vulnerability -- and one in a single TLS library to boot. 3Shake represents a novel and fundamental bug in the TLS protocol. The final thing you should know about 3Shake is that, according to the cryptographic literature, it shouldn't exist. You see, in the last few years there have been at least three four major crypto papers purporting to prove the TLS protocol secure. The existence of 3Shake doesn't make those results wrong. It may, however, indicate that cryptographers need to think a bit more about what 'secure' and 'TLS' actually mean. For me, that's the most fascinating implication of this new attack. I'll proceed with the usual 'fun' question-and-answer format I save for this sort of thing. What is TLS and why should you care? Since you're reading this blog, you probably already know something about TLS. You might even realize how much of our infrastructure is protected by this crazy protocol. In case you don't: TLS is a secure transport protocol that's designed to establish communications between two parties, who we'll refer to as the Client and the Server. The protocol consists of two sub-protocols called the handshake protocol and the record protocol. The handshake is intended to authenticate the two communicating parties and establish shared encryption keys between them. The record protocol uses those keys to exchange data securely. For the purposes of this blog post, we're going to focus primarily on the handshake protocol, which has (at least) two major variants: the RSA handshake and the Diffie-Hellman handshake (ECDHE/DHE). These are illustrated below.

Simplified description of the TLS handshakes. Top: RSA handshake. Bottom: Diffie-Hellman handshake.

As much as I love TLS, the protocol is a hot mess. For one thing, it inherits a lot of awful cryptography from its ancient predecessors (SSLv1-3). For another, it's only really beginning to be subjected to rigorous, formal analysis. All this means we're just now starting to uncover some of the bugs that have been present in the protocol since it was first designed. And we're likely to discover more! That's partly because this analysis is at a very early stage. It's also partly because, from an analysts' point of view, we're still trying to figure out exactly what the TLS handshake is supposed to do. Well, what is the TLS handshake supposed to do? Up until this result, we thought we had a reasonable understanding of the purpose of the TLS handshake. It was intended to authenticate one or both sides of the connection, then establish a shared cryptographic secret (called the Master Secret) that could be used to derive cryptographic keys for encrypting application data. The first problem with this understanding is that it's a bit too simple. There isn't just one TLS handshake, there are several variants of it. Worse, multiple different handshake types can be used within a single connection. The standard handshake flow is illustrated -- without crypto -- in the diagram below. In virtually every TLS connection, the server authenticates to the client by sending a public key embedded in a certificate. The client, for its part, can optionally authenticate itself by sending a corresponding certificate and proving it has the signing key. However this client authentication is by no means common. Many TLS connections are authenticated only in one direction.

Common TLS handshakes. Left: only server authenticates. Right: client and server both authenticate with certificates.

TLS also supports a "renegotiation" handshake that can switch an open connection from one mode to the other. This is typically used to change a connection that was authenticated only in one direction (Server->Client) into a connection that's authenticated in both directions. The server usually initiates renegotiation when the client has e.g., asked for a protected resource.

Renegotiating a session. A new handshake causes the existing connection to be mutually authenticated.

Renegotiation has had problems before. Back in 2009, Ray and Dispensa showed that a man-in-the-middle attacker could actually establish a (non-authenticated) connection with some server; inject some data; and when the server asks for authentication, the attacker could then "splice" on a real connection with an authorized client by simply forwarding the new handshake messages to the legitimate client. From the server's point of view, both communications would seem to be coming from the same (now authenticated) person:

Ray/Dispensa attack from 2009. The attacker first establishes an unauthenticated connection and injects some traffic ("drop table *"). When the server initiates a renegotiation for client authentication, the attacker forwards the new handshake messages to an honest client Alice who then sends real traffic. Since the handshakes are not bound together, Bob views this as a single connection to one party.

To fix this, a "secure renegotiation" band-aid to TLS was proposed. The rough idea of this extension was to 'bind' the renegotiation handshake to the previous handshake, by having the client present the "Finished" message of the previous handshake. Since the Finished value is (essentially) a hash of the Master Secret and the (hash of) the previous handshake messages, this allows the client to prove that it -- not an attacker -- truly negotiated the previous connection. All of this brings us back to the question of what the TLS handshake is supposed to do. You see, the renegotiation band-aid now adds some pretty interesting new requirements to the TLS handshake. For one thing, the security of this extension depends on the idea that (1) no two distinct handshakes will happen to use the same Master Secret, and (2) that no two handshakes will have the same handshake messages, ergo (3) no two handshakes will have the same Finished message. Intuitively, this seemed like a pretty safe thing to assume -- and indeed, many other systems that do 'channel binding' on TLS connections also make this assumption. The 3Shake attack shows that this is not safe to assume at all. So what's the problem here? It turns out that TLS does a pretty good job of establishing keys with people you've authenticated. Unfortunately there's a caveat. It doesn't truly guarantee the established key will be unique to your connection. This is a pretty big violation of the assumptions that underlie the "secure renegotiation" fix described above. For example: imagine that Alice is (knowingly) establishing a TLS connection to a server Mallory. It turns out that Mallory can simultaneously -- and unknown to Alice -- establish a different connection to a second server Bob. Moreover, if Mallory is clever, she can force both connections to use the same "Master Secret" (MS).

Mallory creates two connections that use the same Master Secret.

The first observation of the 3Shake attack is that this trick can be played if Alice supports either of the or RSA and DHE handshakes -- or both (it does not seem to work on ECDHE). Here's the RSA version:**

RSA protocol flow from the triple handshake attack (source). The attacker is in the middle, while the client and server are on the left/right respectively. MS is computed as a function of (pms, cr, sr) which are identical in both handshakes. 

So already we have a flaw in the logic undergirding secure renegotiation. The Master Secret (MS) values are not necessarily distinct between different handshakes. Fortunately, the above attack does not let us resurrect the Ray/Dispensa injection attack. While the attacker has tricked the client into using a specific MS value, the handshake Finished messages -- which the client will attach to the renegotiation handshake -- will not be the same in both handshakes. That's because (among other things) the certificates sent on each connection were very different, hence the handshake hashes are not identical. In theory we're safe. But here is where TLS gets awesome. You see, there is yet another handshake I haven't told you about. It's called the "session resumption handshake", and it allows two parties who've previously established a master secret (and still remember it) to resume their session with new encryption keys. The advantage of resumption is that it uses no public-key cryptography or certificates at all, which is supposed to make it faster.

It turns out that if an attacker knows the previous MS and has caused it to be the same on both sides, it can now wait until the client initiates a session resumption. Then it can replay messages between the client and server in order to update both connections with new keys:

An attacker replays the session resumption handshake to ensure the same key on both sides. Note that the handshake messages are identical in both connections. (authors of source)

Which brings us to the neat thing about this handshake. Not only is the MS the same on both connections, but both connections now see exactly the same (resumption) handshake messages. Hence the hash of these handshakes will be identical, which means in turn that their "Finished" message will be identical. By combining all of these tricks, a clever attacker can pull off the following -- and absolutely insane -- "triple handshake" injection attack:

Triple handshake attack. The attacker mediates two handshakes that give MS on both sides, but two different handshake hashes. The resumption handshake leaves the same MS and an identical handshake hash on both sides. This means that the Finished message from the resumption handshake will be the same for the connections on either side of the attacker. Now he can hook up the two without anyone noticing that he previously injected traffic.

In the above scenario, an attacker first runs a (standard) handshake to force both sides of the connection to use the same MS. It then causes both sides to perform session resumption, which results in both sides using the same MS and having the same handshake hash and Finished messages on both sides. When the server initiates renegotiation, the attacker can forward the third (renegotiation) handshake on to the legitimate client as in the Ray/Dispensa attack -- secure in the knowledge that both client and server will expect the same Finished token. And that's the ballgame. What's the fix? There are several, and you can read about them here. One proposed fix is to change the derivation of the Master Secret such that it includes the handshake hash. This should wipe out most of the attacks above. Another fix is to bind the "session resumption" handshake to the original handshake that led to it. Wait, why should I care about injection attacks? You probably don't, unless you happen to be one of the critical applications that relies on the client authentication and renegotiation features of TLS. In that case, like most applications, you probably assumed that a TLS connection opened with a remote user was actually from that user the whole time, and not from two different users. If you -- like most applications -- made that assumption, you might also forget to treat the early part of the connection (prior to client authentication) as a completely untrusted bunch of crap. And then you'd be in a world of hurt. But don't take my word for it. There's video! (See here for the source, background and details):

What does this have to do with the provable security of TLS? Of all the questions 3Shake raises, this one is the most interesting. As I mentioned earlier, there have been several recent works that purport to prove things about the security of TLS. They're all quite good, so don't take any of this as criticism. However, they (with one exception, the miTLS project) didn't find this attack. Why is that? The first reason is simple: many of these works analyze only the basic TLS handshake, or they omit at least one of the possible handshakes (e.g., resumption). This means they don't catch the subtle interactions between the resumption handshake, the renegotiation handshake, and extensions -- all of which are the exact ingredients that make most TLS attacks possible. The second problem is that we don't quite know what standard we're holding TLS to. For example, the common definition of security for TLS is called "Authenticated and Confidential Channel Establishment" (ACCE). Roughly speaking this ensures that two parties can establish a channel and that nobody will be able to determine what data is being sent over said channel. The problem with ACCE is that it's a definition that was developed specifically so that TLS could satisfy it. As a result, it's necessarily weak. For example, ACCE does not actually require that each handshake produces a unique Master Secret -- one of the flaws that enables this attack -- because such a definition was not possible to achieve with the existing TLS protocol. In general this is what happens when you design a protocol first and prove things about it later. What's the future for TLS? Can't we throw the whole thing out and start over again? Sure, go ahead and make TLS Rev 2. It can strip out all of this nonsense and start fresh. But before you get cocky, remember -- all these crazy features in TLS were put there for a reason. Someone wanted and demanded them. And sadly, this is the difference between a successful, widely-used protocol and your protocol. Your new replacement for TLS might be simple and wonderful today, but that's only because nobody uses it. Get it out into the wild and before long it too will be every bit as crazy as TLS. Notes: * An earlier version of this post incorrectly identified the researchers who discovered the attack. ** The Diffie-Hellman (DHE) version is somewhat more clever. It relies on the attacker manipulating the D-H parameters such that they will force the client to use a particular key. Since DHE parameters sent down from the server are usually 'trusted' by TLS implementations, this trick is relatively easy to pull off.

[matthewdgreen]

Attack of the week: OpenSSL Heartbleed

Ouch. (Logo from heartbleed.com)

I start every lecture in my security class by asking the students to give us any interesting security or crypto news they've seen recently, preferably with a focus on vulnerabilities. The start of my last class was pretty lame, which meant either (1) we'd finally learned how to make our crypto software secure, or (2) something terrible was about to happen. I'll let you take a guess which one it was. The news today is all about the Heartbleed bug in OpenSSL (nb: a truly awful name that makes me glad there are no other vital organs referenced in the TLS code). Unlike all the fancy crypto-related attacks we've seen recently -- BEAST, CRIME, Lucky13, etc. -- Heartbleed doesn't require any interesting crypto. In fact it's the result of a relatively mundane coding error. And predictably, this makes it more devastating than all of those fancy attacks put together. I'm going to talk about Heartbleed using the 'fun' question/answer format I save for this kind of post. What's Heartbleed and why should I care about OpenSSL? In case you haven't read the Heartbleed website, go do that. Here I'll just give a quick overview.

Heartbleed is a surprisingly small bug in a piece of logic that relates to OpenSSL's implementation of the TLS 'heartbeat' mechanism. The bug is present in OpenSSL versions 1.0.1 through 1.0.1f (and not in other versions). Sadly, these versions have seen a great deal of adoption lately, because security professionals have been urging developers to implement more recent versions of TLS (1.1 and 1.2). Deployment of TLS 1.2 currently stands at about 30% of the SSL Pulse data set. Many of those servers are likely vulnerable. The problem is fairly simple: there's a tiny vulnerability -- a simple missing bounds check -- in the code that handles TLS 'heartbeat' messages. By abusing this mechanism, an attacker can request that a running TLS server hand over a relatively large slice (up to 64KB) of its private memory space. Since this is the same memory space where OpenSSL also stores the server's private key material, an attacker can potentially obtain (a) long-term server private keys, (b) TLS session keys, (c) confidential data like passwords, (d) session ticket keys.

Alleged Yahoo user credentials visible due to Heartbleed (source: Mark Loman).

Any of the above may allow an attacker to decrypt ongoing TLS sessions or steal useful information. However item (a) above is by far the worst, since an attacker who obtains the server's main private keys can potentially decrypt past sessions (if made using the non-PFS RSA handshake) or impersonate the server going forward. Worst of all, the exploit leaves no trace. You should care about this because -- whether you realize it or not -- a hell of a lot of the security infrastructure you rely on is dependent in some way on OpenSSL. This includes many of the websites that store your personal information. And for better or for worse, industry's reliance on OpenSSL is only increasing. What's the remedy? Unfortunately it's pretty nasty. You can test if a given server is vulnerable using one of these tools (note: use at your own risk). Having identified a problem, the first step is to patch OpenSSL. Fortunately this is relatively easy. The 1.0.1g version is not vulnerable, and Debian has a patch. You can also recompile OpenSSL with the -DOPENSSL_NO_HEARTBEATS option. Sadly, this is only the beginning. Since there's no way to tell whether a server has been exploited (and exploit code is now in the wild) you need to assume that it is. This means the safe move is to revoke your certificate and get a new one. Have fun. What's the bug? The TLS Heartbeat mechanism is designed to keep connections alive even when no data is being transmitted. Heartbeat messages sent by one peer contain random data and a payload length. The other peer is suppose to respond with a mirror of exactly the same data.

When a HeartbeatRequest message is received and sending a HeartbeatResponse is not prohibited as described elsewhere in this document, the receiver MUST send a corresponding HeartbeatResponse message carrying an exact copy of the payload of the received HeartbeatRequest.

The data structure of the request looks like this. Note the two-byte payload length:

struct { HeartbeatMessageType type; uint16 payload_length; opaque payload[HeartbeatMessage.payload_length]; opaque padding[padding_length]; 

   } HeartbeatMessage; Which brings us to the bug. The original bug was introduced in this Git commit. The code appears in different files (for DTLS and TLS). Here we'll look at the file t1_lib.c:

2412         /* Read type and payload length first */

2413         hbtype = *p++;

2414         n2s(p, payload);

2415         pl = p;

2416

2417         if (s->msg_callback)

2418                 s->msg_callback(0, s->version, TLS1_RT_HEARTBEAT,

2419                         &s->s3->rrec.data[0], s->s3->rrec.length,

2420                         s, s->msg_callback_arg);

2421

2422         if (hbtype == TLS1_HB_REQUEST)

2423                 {

2424                 unsigned char *buffer, *bp;

2425                 int r;

2426

2427                 /* Allocate memory for the response, size is 1 bytes

2428                  * message type, plus 2 bytes payload length, plus

2429                  * payload, plus padding

2430                  */

2431                 buffer = OPENSSL_malloc(1 + 2 + payload + padding);

2432                 bp = buffer;

2433                 

2434                 /* Enter response type, length and copy payload */

2435                 *bp++ = TLS1_HB_RESPONSE;

2436                 s2n(payload, bp);

2437                 memcpy(bp, pl, payload);

2438                 

2439                 r = ssl3_write_bytes(s, TLS1_RT_HEARTBEAT, buffer, 3 + payload + padding);

As you can see, the incoming (adversarially-generated) data contains a payload length ("payload") which is trusted without bounds checks. OpenSSL then allocates a buffer for its response, and copies "payload" data bytes from the pointer "pl" into it. Unfortunately, there's no check to make sure that there are actually "payload" bytes in data, or that this is in bounds. Hence the attacker gets a slice of data from main memory -- one that's up to 64KB in length.

The fix is equally simple. Just add a bounds check:

+ /* Read type and payload length first */ + if (1 + 2 + 16 > s->s3->rrec.length) + return 0; /* silently discard */ + hbtype = *p++; + n2s(p, payload); + if (1 + 2 + payload + 16 > s->s3->rrec.length) + return 0; /* silently discard per RFC 6520 sec. 4 */ + pl = p; +

Wasn't that dull? Come on guys, next time please: use a cache timing weakness in AES-GCM encryption. This whole 'effectively breaking OpenSSL by finding simple C coding bugs' isn't even challenging. Should we rail against the OpenSSL developers for this? Don't even think about it. The OpenSSL team, which is surprisingly small, has been given the task of maintaining the world's most popular TLS library. It's a hard job with essentially no pay. It involves taking other folks' code (as in the case of Heartbeat) and doing a best-possible job of reviewing it. Then you hope others will notice it and disclose it responsibly before disasters happen. The OpenSSL developers have a pretty amazing record considering the amount of use this library gets and the quantity of legacy cruft and the number of platforms (over eighty!) they have to support. Maybe in the midst of patching their servers, some of the big companies that use OpenSSL will think of tossing them some real no-strings-attached funding so they can keep doing their job.

[matthewdgreen]

How do you know if an RNG is working?

No matter how much cryptographers accomplish, we're always building on a questionable foundation. (illustration: Marc S. Rousseau)

Last week, Edward Snowden spoke to a packed crowd at SXSW about the many problems (and limited solutions) facing those of us who want to keep our communications private. Snowden said a number of things -- including a shout out to Moxie's company Whisper Systems, who certainly deserve it. But instead of talking about that, I wanted to focus on (in my opinion) one of Snowden's most important quotes:

We need all those brilliant Belgian cryptographers to go "alright we know that these encryption algorithms we are using today work, typically it is the random number generators that are attacked as opposed to the encryption algorithms themselves. How can we make them [secure], how can we test them?"

Now it's possible I'm a little biased, but it seems to me this cuts to the core of our problems with building secure systems in an increasingly hostile world. Namely: most encryption relies on some source of "random" numbers, either to generate keys or (particularly in the case of public key encryption) to provide semantic security for our ciphertexts. What this means is that an attacker who can predict the output of your RNG -- perhaps by taking advantage of a bug, or even compromising it at a design level -- can often completely decrypt your communications. The Debian project learned this firsthand, as have many others. This certainly hasn't escaped NSA's notice, if the allegations regarding its Dual EC random number generator are true. All of this bring us back to Snowden's quote above, and the question he throws open for us. How do you know that an RNG is working? What kind of tests can we run on our code to avoid flaws ranging from the idiotic to the highly malicious? Unfortunately this question does not have an easy answer. In the rest of this post I'm going to try to explain why. Background: Random and Pseudorandom Number Generation I've written quite a bit about random number generation on this blog, but before we go forward it's worth summarizing a few basic facts about random number generation. First off, the 'random' numbers we use in most deployed cryptographic systems actually come from two different systems:

A 'true' random number generator (or entropy generator) that collects entropy from the physical world. This can include entropy collected from low-level physical effects like thermal noise and shot noise, or it can include goofy stuff like mouse movements and hard disk seek times.

An algorithmic 'pseudorandom number generator' (PRNG) that typically processes the output of (1) to both stretch the output to provide more bits and, in some cases, provide additional security protections in case the output of (1) proves to be biased.

It's important to note that pseudorandom number generators aren't "random number generators" at all. These generators typically use cryptographic algorithms (e.g., block ciphers or hash functions) to process a seed value from the RNG into many apparently random looking and unpredictable bytes. In most cases, it's quite rare for your application to ever see the raw output of a true random number generator.* Even the low-level entropy collector within Linux's RNG uses cryptographic constructs like hash functions in order to 'mix' the output of various entropy sources. To produce the bits produced in /dev/random or /dev/urandom Linux then seeds a PRNG like Yarrow or Fortuna.**

Another similar pattern occurs inside of the Intel "secure key" random number generator included in Intel Ivy Bridge processors. When you buy one of these processors, you're getting (free!) a hardware '1-shot' circuit that collects high-entropy electronic noise, which is then measured and processed into useful RNG output. The design looks like this:

Hardware random number generator used on Intel Ivy Bridge processors. Left: the '1-shot' circuit used to collect physical entropy. Right: the data flow from generator to output, including health checks and PRNG computation. (source).

Once again, with Intel's design you (i.e., the application developer) don't get access to this raw randomness. It's first used to seed a PRNG based on AES (CTR-DRBG from NIST SP800-90A). What you actually get as an application developer is the processed output of that algorithm.

In practice this typical design some implications. On the positive side, the presence of a PRNG means that the underlying RNG circuit can get pretty borked (e.g., biased) without the results being detectable by your application. On the negative side, the underlying RNG circuit can get pretty borked without the results being detectable in your application.

In other words, with only a few ugly glitches -- things that can happen in real life -- you can easily get a broken random number generator that nobody notices until it's way too late. And that's without deliberate tampering, which makes things way, way worse.

Which brings us back to our fundamental question: how do systems know that their RNG is working. This turns out to be a question without a perfect answer.

Statistical Tests

If you look at the literature on random number generators, you'll find a lot of references to statistical randomness testing suites like Diehard or NIST's SP 800-22. The gist of these systems is that they look a the output of an RNG and run tests to determine whether the output is, from a statistical perspective, "good enough" for government work (very literally, in the case of the NIST suite.) The nature of these tests varies. Some look at simple factors like bias (the number of 1s and 0s) while others look for more sophisticated features such as the distribution of numbers when mapped into 3-D space. Now I don't want to knock these tests. They're a perfectly valid way to detect serious flaws in a (true) RNG -- I can attest to this, since I've built one that failed the tests miserably -- but they probably won't detect flaws in your system. That's because like I said above, most deployed systems include a combination of RNG and PRNG, or even RNG plus "conditioning" via cryptographic hash functions or ciphers. The nature of these cryptographic, algorithmic processes is such that virtually every processed output will pass statistical tests with flying colors -- even if the PRNG is initialized with 'garbage' input. This means, unfortunately, that it can be very hard to use statistical tests to detect a broken RNG unless you properly test it only at the low level. And even there you won't rule out intentional backdoors -- as I'll discuss in a moment.

Known Answer Tests (KATs) Assuming that you've tested your true RNG properly and it's passing all tests, it's still important to test your PRNG. One approach to doing this is to use Known Answer Tests (KATs) that are essentially test vectors. These contain some input seed material as well as a set of output bytes that should be the algorithmic result of running the PRNG on that seed. Since PRNGs are purely algorithmic, the theory here is that you can test them like algorithms. While this approach is valid, it raises two potential issues (both of which I've seen in practice). First, you can only test your PRNG on so many points. Thus it's quite possible that your PRNG will succeed on one particular test vector (i.e., it'll output just so many valid bytes) but go completely off the reservation on some other input. This is unlikely, but not impossible in normal conditions. It's very possible if someone is trying to build a malicious backdoor into your PRNG implementation. Second, the process of instrumenting your PRNG implementation for testing can actually introduce vulnerabilities in your deployed system! Think about this for a second. Normal PRNGs take in real random seeds from your RNG. The last thing you'd ever want to do is run your PRNG on some predictable seed -- if you did, everyone would be able to predict the PRNGs outputs. Yet adding a test harness your system means building in logic to re-seed your RNG to something predictable! This is like adding an ejection seat to your car. Might make you safer -- unless it goes off while you're driving to work. A quick glance through e.g., the OpenSSL code shows that indeed, exactly this sort of code exists and ships in some versions of the library. Of course, the experienced developers will note that surely such features could be surrounded by pre-processor directives (or the equivalent in your language of choice) ensuring that they'll never be activated in production code. Sadly, at least in the case of FIPS, this is not possible -- for reasons I'll explain next. Runtime Health Checks Another approach to testing RNGs is to test them while the system is running. This isn't intended to rule out design-level flaws (as the above statistical and KAT tests are) but it is intended to catch situations where the RNG becomes broken during normal operation. This can occur for a variety of reasons, e.g., manufacturing defects, system damage, and even exposure to outside radiation. Health checks can take different forms. FIPS 140, for example, mandates that all approved RNGs be tested at startup time using KATs. (This is why you can't make your test harness conditional on compilation flags -- it must ship in your production code!) They subsequently mandate a runtime health check that verifies the generator has not become 'stuck', i.e., is spitting out the same bytes over and over again. While I'm sure this last test may have saved someone, somewhere, it seems totally inappropriate and useless when applied to the output of an RNG/PRNG pair, which is how NIST recommends it be used. This is because even the most broken algorithmic PRNGs will almost never spit out duplicate values -- even if the underlying RNG fails completely. The upshot of this decision is that NIST (FIPS) recommend a check that will almost never succeed in catching anything useful from a PRNG, but does introduce a whole bunch of extra logic that can suffer from flaws and/or malicious circumvention. I'm sure the good folks at NIST realize this, but they recommend it anyway -- after all, what else are they going to do?

Tampering

Which brings us to the $10 million question. What happens if an attacker is deliberately tampering with our RNG/PRNG in order to make it fail? Note that this is not an academic question. We have excellent reason to believe it's happened in some real systems.

Just for fun, let's go back to the Intel Ivy Bridge RNG described above. We'll take a look specifically at the PRNG portion of the design, which uses the NIST CTR-DRBG random number generator with AES:

Portion of the Intel Ivy Bridge design, with a few annotations added by yours truly. (original source) 

The CTR-DRBG design relies on two features. First, an AES key is selected at random along with some input seed. This pair goes into the AES cipher, where it is processed to derive a new key and data. The result should be unpredictable to most attackers. But if you were able to change the way keys were updated (in the key_in_mux hilighted) so that instead of updating the key and/or using an unpredictable one, it chose a fixed key known to the attacker, you would now have a very powerful backdoor. Specifically, the output would still look statistically perfectly random. But an attacker who knows this key could simply decrypt one block of RNG output to obtain all future and past outputs of the generator until the next time it was reseeded. Note that I am not saying the Intel system has a backdoor in it -- far from it. I'm only considering how easily it might be made to have one if you were an attacker with control of Intel's fabrication plants (or their microcode updates). And this is hardly Intel's fault. It's just the nature of this particular RNG design. Others could be just as vulnerable. Actually using this knowledge to attack applications would be more complex, since many system-level RNGs (including the Linux Kernel RNG) combine the output of the RNG with other system entropy (through XOR, unfortunately, not hashing). But Intel has pushed hard to see their RNG output used directly, and there exist plugins for OpenSSL that allow you to use it similarly. If you used such a method, these hypothetical flaws could easily make their way all the way into your cryptography. Designing against these issues Unfortunately, so far all I've done is call out the challenges with building trustworthy RNGs. And there's a reason for this: the challenges are easy to identify, while the solutions themselves are hard. And unfortunately at this time, they're quite manual. Building secure RNG/PRNGs still requires a combination of design expertise, careful low-level (true) RNG testing -- using expert design and statistical tests -- and the use of certified algorithms with proper tests. All of the techniques above contribute to building a secure RNG, but none of them are quite sufficient. Solving this problem, at least in software, so we can ensure that code is correct and does not contain hidden 'easter eggs', represents one of the more significant research challenges facing those of us who depend on secure cryptographic primitives. I do hope some enterprising graduate students will give these issues the attention they deserve. Notes: * Though there are some exceptions. See, for example, this FIPS certified smart card that included a bad RNG which was used to generate cryptographic secrets. In general FIPS disallows this except for a very small number of approved RNGs. Perhaps this was one. ** The original version of this post claimed that /dev/random seeds /dev/urandom. This is actually a mistake -- both /dev/random and /dev/urandom use the same PRNG, but /dev/random simply keeps track of how much 'entropy' is in the pool and blocks when you have drawn too many bits. Thanks to Brendan Long and Thomas Ptacek for setting me straight.

[matthewdgreen]

Cryptographic obfuscation and 'unhackable' software

I have a thing for over-the-top cryptography headlines -- mostly because I enjoy watching steam come out of researchers' ears when their work gets totally misrepresented. And although I've seen quite a few good ones, last week WIRED managed a doozy. The headline in question, Cryptography Breakthrough Could Make Software Unhackable, managed to accomplish something that few cryptography headlines do. It sent its own protagonist, Amit Sahai, into the comments section to perform intellectual garbage pickup. In contrast to the headline, which is quite bad, the article is actually pretty decent. Still, the discussion around it has definitely led to some confusion. As a result, many now think an amazing breakthrough has taken place -- one that will finally make software secure. They're probably right about the first part. They may be disappointed about the rest. The truth, as usual, is complicated. There is, indeed, something very neat going on with the new obfuscation results. They're just not likely to make software 'unhackable' anytime soon. They might, however, radically expand what we can do with cryptography. Someday. When they're ready. And in ways we don't fully understand yet. But before I go into all that, it's probably helpful to give some background. Program obfuscation The Wired article deals with the subject of 'program obfuscation', which is a term that software developers and cryptographers have long been interested in. The motivation here is pretty simple: find a way that we can give people programs they can run -- without letting them figure out how the programs work. Note that the last part necessarily covers a lot of ground. In principle it includes aspects ranging from the nature of specific secret algorithms used -- which may be proprietary and thus worth money -- to secret information like passwords and cryptographic keys that might be hardcoded into the program. For a simple example, consider the following routine: // Check a password and print out top secret information if it's correct // SuperSecretPasswordProtectedStuff(string passwd) {   if (password == "0xt438fh27266629zn28366492923aai3jnqobbyc4t!") {     print("Congratulations. Here's some super secret private information: ....\n");   } else {     print("Wrong password, fool.\n");   } }

If you're like me, you probably wrote a program like this at some point in your life. You may have eventually realized how ineffective it would be -- against a smart attacker who could dump the program code. This is because most programs (and even compiled binaries) are pretty easy to read. An attacker could just look at this program to recover the secret password. Program obfuscation is motivated by the idea that many useful programs would benefit if we could somehow 'stop' people from doing this, while still letting them possess and run the code on their own computers. In real world software systems, 'obfuscation' usually refers to a collection of ad-hoc techniques that turn nice, sensible programs into a morass of GOTOs and spaghetti code. Sometimes important constants are chopped up and distributed around the code. Some portions of the code may even be encrypted -- though only temporarily, since decryption keys must ship with the program so it can actually be run. Malware authors and DRM folks love this kind of obfuscation.

A chunk of 'birken', one of the winning entries in the 2013 obfuscated C contest.

While these techniques are nice, they're not really 'unhackable' or even secure against reverse-engineering in the strong sense we'd like. Given enough time, brains and tools, you can get past most common software obfuscation techniques. If you have, say, Charlie Miller or Dion Blazakis on your side, you probably do it quickly. This isn't just because those guys are smart (though they are), it's because the techniques are not mathematically rigorous. Most practical obfuscation amounts to roadblocks -- designed to slow reverse-engineers down and make them give up. So what does it mean to securely 'obfuscate' a program? The poor quality of existing software obfuscation set cryptographers up with a neat problem. Specifically, they asked, could we define a strong definition of program obfuscation that would improve on, to put it politely, the crap people were actually using? Given such an obfuscator I could hand you my obfuscated program to run while provably protecting all partial information -- except for the legitimate inputs and outputs.

If this could be done, it would have an incredible number of applications. Stock traders could obfuscate their proprietary trading algorithms and send them to the cloud or to end-customers. The resulting programs would still work -- in the sense that they produced the right results -- but customers would never learn anything about 'how they worked'. The internals of the program would be secret sauce.

Unfortunately, when the first researchers started looking at this problem, they ran into a very serious problem: nobody had any idea what it meant to securely 'obfuscate' a program in the first place. Do think about it for a second before you roll your eyes. What do you think it means to obfuscate a program? You're probably thinking something like 'people shouldn't learn stuff' about the program. But can you explain what stuff? And does 'stuff' depend on the program? What about programs where you can efficiently learn the whole program from sending it inputs and seeing the results? What does it mean to obfuscate those? Clearly before progress could begin on solving the problem, cryptographers needed to sit down and figure out what they were trying to do. And indeed, several cryptographers immediately began to do exactly this. Black-box cryptographic obfuscation The first definitions cryptographers came up addressed a very powerful type of obfuscation called 'virtual black box obfuscation'. Roughly speaking, it starts from the following intuitive thought experiment. Imagine you have a program P, as well as some code obfuscation technique you've developed. It's important that the obfuscation be efficient, meaning it doesn't slow the program down too much. To determine whether the obfuscation is successful, you can conduct the following experiment.

Give Alice a copy of the obfuscated program code Obf(P), in a form that she can look at and run on her own computer.               

Take the original (unobfuscated) program P, and seal it in a special computer located inside an armored 'black box'. Let a user Sam interact with the program by sending it inputs and receiving outputs. But don't let him access the code.

Roughly speaking, what we want from secure obfuscation is that Alice should learn 'no more' information after seeing the obfuscated program code, than could some corresponding user Sam who interacts with the same program locked up in the black box. What's nice here is that this is we have the beginnings of an intuitive definition. In some sense the obfuscation should render the program itself basically unintelligible -- Alice should not get any more information from seeing the obfuscated program than Sam could get simply by interacting with its input/output interface. If Sam can 'learn' how the program works just by talking to it, even that's ok. What's not ok is for Alice to learn more than Sam. The problem with this intuition is, that of course, it's hard to formulate. One thing you may have noticed is that the user Alice who views the obfuscated program truly does learn something more than the user Sam, who only interacts with it via the black box. When the experiment is over, the user who got the obfuscated program still has a copy of the obfuscated program. The user who interacted with the black box does not. To give a practical example, let's say this program P is a certificate signing program that has a digital signing key hard-coded inside of it -- say, Trustwave's -- that will happily attach valid digital signatures on certificates (CSRs) of the user's devising. Both Alice and Sam can formulate certificate signing requests and send them into the program (either the obfuscated copy or the version in the 'black box') and get valid, signed certificates out the other end. But here's the thing: when the experiment is over and we shut down Sam's access to the black box, he won't be able to sign any more certificates. On the other hand, Alice, who actually who learned the obfuscated program Obf(P), will still have the program! This means she can keep signing certificates on and forevermore. Knowing a program that can sign arbitrary certificates is a pretty darn significant 'piece' of information for Alice to have! Worse, there's no way the 'black box' user Sam can ever learn a similar piece of information -- at least not if the signature scheme is any good. If Sam could ask the black box for a bunch of signatures, then somehow learn a program that could make more signatures, this would imply a fundamental weakness in the digital signature scheme. This cuts against a basic property we expect of secure signatures. Barak et al. proposed a clever way to get around this problem -- rather than outputting an arbitrary piece of information, Alice and Sam would be restricted to outputting a single bit at the end of their experiment (i.e., computing a predicate function). This helps to avoid the problems above and seems generally like the "right" definition. An impossibility result Having proposed this nice definition, Barak et al. went on to do an irritating thing that cryptographers sometimes do: they proved that even their definition doesn't work. Specifically, they showed that there exist programs that simply can't be obfuscated under this definition. The reason is a little wonky, but I'm going to try to give the flavor for it below. Imagine that you have two programs A and B, where A is similar to our password program above. That is, it contains a hard-coded, cryptographic secret which we'll denote by password. When you run A(x), the program checks whether (x == password) and if so, it outputs a second cryptographically strong password, which we'll cleverly denote by password_two. If you run A on any other input, it doesn't output anything. Now imagine the second program B works similarly to the first one. It contains both password and password_two hardcoded within it. A major difference is that B doesn't take a string as input. It takes another computer program. You feed a program in as input to B, which then:

Executes the given program on input password to get a result r. 

If (r == password_two), it outputs a secret bit.

It should be apparent to you that if you run the program B on input the program A -- that is, you compute B(A) -- it will always output the secret bit.* It doesn't even matter if either B or A has been obfuscated, since obfuscation doesn't change the behavior of the programs. At the same time, Barak et al. pointed out that this trick only works if you actually have code for the program A. If I give you access to a black box that contains the programs A, B and will simply let you query them on chosen inputs, you're screwed. As long as password and password_two are cryptographically strong, you won't be able to get A to output anything in any reasonable amount of time, and hence won't be able to get B to output the secret bit. What this means is that Alice, who gets the obfuscated copies of both programs, will always learn the secret bit. But if Sam is a reasonable user (that is, he can't run long enough to brute-force the passwords) he won't be able to learn the secret bit. Fundamentally, the obfuscated pair of programs always gives more information than black-box access to them. It remains only to show that the two programs can be combined into one program that still can't be obfuscated. And this is what Barak et al. did, completing their work and showing the general programs can't be obfuscated using their definition. Now you can be forgiven for looking askance at this. You might, for example, point out that the example above only shows that it's hard to obfuscate a specific and mildly ridiculous program. Or that this program is some kind of weird exception. But in general it's not. There are many other useful programs that also can't obfuscate, particularly when you try to use them in real systems. These points were quickly pointed out by Barak et al., and later in other practical settings by Goldwasser and Kalai, among others. You might also think that obfuscation is plain impossible. But here cryptography strikes again -- it's never quite that simple. We can obfuscate some things! Before we completely write off black box obfuscation, let's take a moment to go back to the password checking program I showed at the beginning of this post. Here's a slightly simpler version: // Check a password and return true if it's correct, false otherwise // bool SuperSecretPasswordProtectedStuff(string passwd) {   if (password == "0xt438fh27266629zn28366492923aai3jnqobbyc4t!") {     return true;   } else {     return false;   } } This function is an example of a 'point function': that is, a functions that returns false on most inputs, but returns true at exactly one point. As you can see, there is exactly one point (the correct password) that makes this routine happy. Point functions are interesting for a two simple reasons: the first is that we use them all the time in real systems -- password checking programs being the obvious example. The second is that it turns out we can obfuscate them, at least under some strong assumptions. Even better, we can do it in a way that should be pretty familiar to real system designers. Let H be a secure hash function -- we'll get back to what that means in a second -- and consider the following obfuscated password checking routine: // Check a password and return 'true' if it's correct, 'false' otherwise // But do it all *obfuscated* and stuff // bool ObfuscatedSuperSecretPasswordProtectedStuff(string passwd) {

  static string HARDCODED_SALT          = 0x......; // this is a salt value

  static string HARDCODED_PASSWORD_HASH = 0x......; // this value is H(salt + target password)

  // First, hash the input password with the salt   hashedPass = H(HARDCODED_SALT + passwd);   if (hashedPass == HARDCODED_PASSWORD_HASH) {     return true;   } else {     return false;   } } Note that our 'obfuscated' program no longer stores the plaintext of the password. Instead we store its hash only (and salt), and wrap it inside a program that simply compares this hash to a hash of the user's input. This should be familiar, since it's the way you should be storing password files today.** A number of cryptographers looked at formulations like this and showed the following: if the password is very hard to guess (for example, it's secret and drawn at random from an exponentially-sized space of passwords) and the hash function is 'strong' enough, then the hash-checking program counts as a secure 'obfuscation' of the basic password comparison program above it. The intuition for this is fairly simple: imagine Alice and Sam don't know the password. If the password is strong, i.e., it's drawn from a large enough space, then their probability of ever getting the program to output 'true' is negligible. If we assume an ideal hash function -- in the simplest case, a random oracle -- then the hard-coded hash value that Alice learns is basically just a useless random string, and hides all partial input about the real password. This means, in practice, that any general question Alice can answer at the end of the experiment, Sam can answer with about the same probability.*** Finding better definitions More than a decade after the definition was formulated, there are basically two kinds of results about 'strong' virtual-black-box obfuscation. The first set shows that it's impossible to do it for general programs, and moreover, that many of the interesting functions we want to obfuscate (like some signatures and pseudorandom functions) can't be obfuscated in this powerful sense. The second class of results shows that we can black-box obfuscate certain functions, but only very limited ones like, say, point functions and re-encryption. These results are neat, but they're hardly going to set the world on fire. What cryptographers have been trying to achieve since then is a different -- and necessarily weaker -- definition that could capture interesting things we wanted from obfuscating general programs, but without all the nasty impossibility results. And that, finally, brings us to the advances described in the WIRED article. Indistinguishability Obfuscation In shooting down their own proposed definitions, Barak et al. also left some breadcrumbs towards a type of obfuscation that might actually work for general programs. They called their definition "indistinguishability obfuscation" (IO) and roughly speaking it says the following: Imagine we have two programs C1, C2 -- which we'll describe as similarly-sized circuits -- that compute the same function. More concretely, let's say they have exactly the same input/output behavior, although they may be implemented very differently inside. The definition of indistinguishability obfuscation states that it should be possible to obfuscate the two circuits C1, C2 such that no efficient algorithm will be able to tell the difference between Obf(C1) from Obf(C2).  While this idea was proposed years ago, nobody actually knew how to build any such thing, and it was left as one of those 'open problems' that cryptographers love to tear their hair out over. This remained the case until just last year, when a group of authors from UCLA, UT Austin and IBM Research proposed a 'candidate construction' for building such obfuscators, based on the new area of multilinear map-based cryptography. Another interesting variant of this notion is called extractability obfuscation (EO), which implies not only that you can't distinguish between Obf(C1) and Obf(C2), but moreover, that if you could distinguish the two, then you could necessarily find an input value on which both C1 and C2 would produce different outputs. Moreover, other work indicates IO and EO give essentially the 'best possible' obfuscation you can provide for general programs. The question you're probably asking is: so what? What can we do with indistinguishability obfuscation? And this is where the WIRED article differs substantially from the reality. The truth is that IO will probably bring us major cryptographic and software advances -- it's already been shown to bring about succinct functional encryption for all circuits, as well as advances in deniable encryption. Moreover it can be used to build known forms of encryption such as public-key encryption based on new techniques that differ from what we use today -- for example, by obfuscating 'symmetric' primitives like pseudorandom functions.**** And if this doesn't seem quite as exciting as the WIRED article would imply, that's because we're still learning what the possibilities are. The new techniques could, for example, allow us to build exciting new types of security systems -- or else show us radical new ways to build systems that we already have. Even the latter is very important, in case advances in our field result in 'breaks' to our existing constructions. What IO and EO will probably not do is make programs unhackable, since that implies something a whole lot stronger than either of these techniques currently provide. In fact, it's not clear what the heck you'd need to make programs unhackable. And the reason for that is quite simple: even obfuscated software can still suck. Notes: Thanks to Susan Hohenberger and Zooko for help with this post.  * The bit in the Barak et al. proof doesn't have to be secret. ** With a pretty damn big caveat, which is that in real life (as opposed to cryptographic examples) users pick terrible passwords, which makes your password hashes vulnerable to dictionary attacks. We have a variety of countermeasures to slow down these attacks, including salt and computationally intensive password hashing functions. *** God I hate footnotes. But it's worth unpacking this. Imagine that Alice learns 'some information' from seeing an average program containing the hash of a strong password. If the password is strong, then Alice can only guess the right input password with negligible probability. Then Sam can 'use' Alice to get the same information as follows. He formulates a 'fake' program that contains a completely bogus password hash and mails it to Alice. Whatever information she learns from his program, he takes and outputs as the information he 'learned'. It remains to show that if the password hash is strong (a random oracle), Alice isn't going to be able to learn more from a random hash than she would from the hash of a strong password. **** The basic idea here is that symmetric encryption (like AES, say) can't be used for public key encryption, since anyone who learns your encryption key also learns your decryption key. But if you can obfuscate an encryption program that contains your symmetric encryption key, then the new program becomes like a public key. You can hand it out to people to encrypt with.

[matthewdgreen]

A letter from US security researchers

This week a group of more than fifty prominent security and cryptography researchers signed a letter protesting the mass surveillance efforts of the NSA, and attempts by NSA to weaken cryptography and privacy protections on the Internet. The full letter can be found here.

Most of you have already formed your own opinions on the issue over the past several months, and it's unlikely that one letter is going to change that. Nonetheless, I'd like a chance to explain why this statement matters.

For academic professionals in the information security field, the relationship with NSA has always been a bit complicated. However, for the most part the public side of that relationship has been generally positive. Up until 2013 if you'd asked most US security researchers for their opinions on NSA, you would, of course, have heard a range of views. But you also might have heard notes of (perhaps grudging) respect. This is because many of the NSA's public activities have been obviously in everyone's interest -- helping to fund research and secure our information systems.

Even where evidence indicated the possibility of unfair dealing, most researchers were content to dismiss these allegations as conspiracy theories. We believed the NSA would stay between the lines. Putting backdoors into US information standards was possible, of course. But would they do it? We thought nobody would be that foolish. We were wrong.

In my opinion this letter represents more than just an appeal to conscience. It measures the priceless trust and goodwill the NSA has lost -- and continues to lose while our country fails to make serious reforms to this agency.

While I'm certain the NSA itself will survive this loss of faith in the short term, in the long term our economic and electronic security depend very much on the cooperation of academia, industry and private citizens. The NSA's actions have destroyed this trust. And ironically, that makes us all less safe.

[matthewdgreen]

A few more notes on NSA random number generators

Last Friday, Joseph Menn from Reuters published an article claiming that RSA, the pioneering security firm and division of EMC, accepted $10 million dollars to include the Dual EC random number generator as the default in their flagship BSAFE library. I've written a bit about Dual EC on this blog, so readers will know that I don't think highly of it. For one thing, it's a rotten choice for a commercial product, due to its lousy software performance. Much worse: it may introduce a practical backdoor into any system that uses it.

Given the numerous problems with Dual EC it's baffling that RSA would select this particular generator as the default for their software. It's particularly strange given that BSAFE is designed for use in Java-based and embedded systems where performance truly is at a premium. And none of this can be explained by the needs of a single RSA customer, since those needs could be satisfied merely by making BSAFE an option, rather than the default. Of course there have been many people who had viewed RSA's decision as potentially malicious. Unsupported rumors have been floating around since long before Reuters got involved. What's new this time is that RSA insiders appear to be going on the record. I suppose time will tell how the industry reacts to this news. In the interim I have a few small facts to add to the discussion, so I thought I'd sketch them out in this post. #1: Dual_EC_DRBG's 'backdoor' was known as of January 2005 It's widely believed that the 'vulnerability' in Dual_EC was first identified by Microsoft employees Dan Shumow and Niels Ferguson in the summer of 2007. Tanja Lange (and nymble) recently tipped me off to the fact that this isn't precisely true. In point of fact, the possibility of a backdoor was known to at least some members of the ANSI X9.82 standardization committee as far back in January 2005. This surprising news comes via a patent application filed by Certicom employees Dan Brown and Scott Vanstone. The application claims a priority date of January 2005. Here's the scary bit:

If P and Q are established in a security domain controlled by an administrator, and the entity who generates Q for the domain does so with knowledge of e (or indirectly via knowledge of d). The administrator will have an escrow key for every ECRNG that follows that standard. 

Escrow keys are known to have advantages in some contexts. They can provide a backup functionality. If a cryptographic key is lost, then data encrypted under that key is also lost. However, encryption keys are generally the output of random number generators. Therefore, if the ECRNG is used to generate the encryption key K, then it may be possible that the escrow key e can be used to recover the encryption key K. Escrow keys can provide other functionality, such as for use in a wiretap. In this case, trusted law enforcement agents may need to decrypt encrypted traffic of criminals, and to do this they may want to be able to use an escrow key to recover an encryption key. ... For example, in the SSL and TLS protocols, which are used for securing web (HTTP) traffic, a client and server perform a handshake in which their first actions are to exchange random values sent in the clear.

The patent also describes a number of ways to close the backdoor in Dual_EC_DRBG. Indeed, it may be due to Brown and Vanstone that the NIST standard includes an alternative method to close the backdoor (by generating a random Q point). The existence of this patent does not mean that Brown and Vanstone were responsible for Dual EC. In fact, the generator appears to be an NSA invention, and may date back to the early 2000s. What this patent demonstrates is that some members of the ANSI committee, of which RSA was also a member, had reason to at least suspect that Dual EC could be used to create a wiretapping backdoor. (Update: John Kelsey confirms this.) It would be curious to know how widely this information was shared, and whether anyone on the committee ever inquired as to the provenance of the default parameters. #2. Dual_EC_DRBG is not really a NIST standard. This is hardly a secret, but it's something that hasn't been widely acknowledged in the press. Dual_EC_DRBG is generally viewed as a NIST standard, since it was published in NIST Special Publication 800-90. But that's not the only place it appears, nor was it developed at NIST. A complete history of Dual_EC_DRBG would begin with NSA's drive to include it in the ANSI X9.82 DRBG standard, with a standardization process kicked off in the early 2000s. The draft ANSI standard includes Dual_EC_DRBG with all of the known parameters, along with several additional elliptic curve parameters that were not included in the NIST standards.

Members of the ANSI X9F1 Tool Standards and Guidelines Group which wrote ANSI X9.82.

However you'll also find Dual_EC_DRBG in the international standard ISO 18031. In other words, Dual EC was widely propagated in numerous standards long before NIST finalized it, and it's hardly limited to US borders. The ANSI and ISO drafts are in some sense worse, since they don't include a technique for generating your own Q parameter. #3. Dual_EC_DRBG is not the only asymmetric random number generator in the ANSI and ISO standards. Cryptographers generally think of Dual EC as the only 'public key' random number generator to be widely standardized. We also point to NSA's generation of the public parameters as evidence that Dual_EC may be compromised. But in fact, the ANSI X9.82 and ISO standards each include a second generator based on public key cryptographic techniques. And like Dual EC, this one ships with a complete set of default parameters! The additional generator is based on an algorithm due to Micali and Schnorr, and relies for its security on assumptions related to the hardness of factoring large composite numbers. It requires an RSA-type modulus, several of which are conveniently provided in the specification.

Two default MS-DRBG moduli from the ISO 18031 specification.

There's no reason to suspect that MS-DRBG is used by any real products, let alone that there's a backdoor in the standard. In fact, there's a curious fact about it: it's not obvious from the public literature how one would attack the generator even if one knew the factorization of the n values above -- though it seems intuitively likely that an attack does exist. Solving the problem, and finding a practical attack for known factorization, would be a fun project for an enthusiastic mathematician.

Since MS-DRBG comes from the same people who brought you Dual EC, if you are using it you might want to think twice.

[matthewdgreen]

Can hackers decrypt Target's PIN data?

Short answer: probably not.

Slightly longer answer: it depends on whether they have access to the encryption key, or to a machine that contains the encryption key. In case you have no idea what I'm talking about: there was recently a massive credit card breach at Target. If you're like many people you probably heard about this three times. First in the news, then again in your email when Target notified you that you were a victim, and finally a third time when you checked your credit card bill. Not a proud day for our nation's retailers. The news got a bit messier today when Target announced the thieves had also managed to get their hands on the PIN numbers of unfortunate debit card customers. But this time there's a silver lining: according to Target, the PIN data was encrypted under a key the hackers don't have.

Snyder said PIN data is encrypted at a retail location’s keypad with Triple-DES [3DES] encryption and that data remains encrypted over the wire until it reaches its payment processor. Attackers would have to have compromised the point-of-sale system and intercepted the PIN data before it is encrypted in order to have accessed it.

Several folks on Twitter have noted that 3DES is no spring chicken, but that's not very important. Aside from a few highly impractical attacks, there isn't much to worry about with 3DES. Moreover, PCI standards appear to mandate unique keys for every payment terminal, which means that the attackers would need to compromise the terminals themselves, or else break into the back-end payment processor. If Target is to be believed, this has not happened. Others have pointed out that PINs are pretty short. For example, there are only 10,000 4-digit PINs -- so surely the attackers can "brute-force" through this space to figure out your PIN. The good news is that encryption is decidedly not the same thing as password hashing, which means this is unlikely to be a serious concern. Provided that Target is being proactive and makes sure to change the keys now. Of course you shouldn't take my word for this. It helps to take a quick look at the PCI PIN encryption standards themselves. Before you encrypt a 4-digit PIN, the PIN is first processed and in some cases padded to increase the complexity of the data being encrypted. There are four possible encryption formats:

Format 0. XOR the PIN number together with the Primary Account Number (PAN), usually the rightmost twelve digits of the card number, not including the last digit. Then encrypt the result using 3DES in ECB mode.

Format 1. Concatenate the PIN number with a unique transaction number and encrypt using 3DES in ECB mode.

Format 2. Pad with some fixed (non-random) padding, then encrypt in 3DES/ECB with a unique, derived per-transaction key (called a DUKPT). Update: only used for EMV cards.

Format 3. Pad with a bunch of random bytes, then 3DES/ECB encrypt.

Notice that in each case the encryption is ECB mode, but in Formats 0, 1 and 3 the plaintext has been formatted in such a way that two users with PIN "1234" are unlikely to encrypt exactly the same value under the same key. For example, consider the Format 0 encryptions for two users with the same PIN (1234) but different PANs:

(PIN) 0x1234FFFFFFFF ⊕ (PAN) 0x937492492032 = 0x81406DB6DFCD (PIN) 0x1234FFFFFFFF ⊕ (PAN) 0x274965382343 = 0x357D9AC7DCBC

Notice that the values being encrypted (at right) will be quite different. ECB mode has many flaws, but one nice feature is that the encryption of two different values (even under the same key) should lead to effectively unrelated ciphertexts. This means that even an attacker who learns the user's PAN shouldn't be able to decompose the encrypted PIN without knowledge of the key. Their best hope would be to gain access to the terminal, hope that it was still configured to use the same key, and build a dictionary -- encrypting every possible PIN under a specific user's PAN -- before they could learn anything useful about one user's key.

This does not seem practical.

The one exception to the above rule is Format 2, which does not add any unpredictable padding to the plaintext at all. While the PIN is padded out, but there are still exactly 10,000 possible plaintexts going into the encryption. PCI deals with this by mandating that the payment terminal derive a unique key per transaction, hopefully using a secure key derivation function. Update: this one probably isn't used by Target.

All of this is a long, dull way of saying that encryption is not like password hashing. Provided that you can keep the keys secret, it's perfectly fine to encrypt messages drawn from even small message spaces -- like PINs -- provided you're not an idiot about it. The PCI standards clearly skirt the borders of idiocy, but they mostly steer clear of disaster.

So in summary, Target debit card users are probably just fine. Until tomorrow, when we learn that the thieves also have the decryption keys. Then we can panic.

[matthewdgreen]

An update on Truecrypt

Several people have been asking for an update on our public audit of the Truecrypt disk encryption software. I'm happy to say that the project is on track and proceeding apace. Here I wanted to give a few quick updates:

Thanks to the amazingly generous donations of 1,434 individual donors from over 90 countries, as of today, we've collected $62,104 USD and 32.6 BTC* towards this effort. This is an unbelievable response and I can't thank our donors enough. I'm blown away that this is happening.

We've assembled a stellar technical advisory board to make sure we spend this money properly and generally to keep us honest. More details shortly.

In order to make best use of the donated funds and manage on-going governance of the project, we've incorporated as a non-profit corporation in North Carolina—the Open Crypto Audit Project (OCAP)—and are currently seeking 501c(3) tax-exempt designation. Board members include myself, Kenn White (who has been doing most of the heavy organizational lifting) and the amazing Marcia Hoffman. We have high hopes that OCAP will find a purpose beyond this Truecrypt audit.

The Open Technology Fund has generously agreed to donate a substantial amount of contracted evaluation time to our effort

And finally, the most exciting news: we've signed a first contract with iSEC partners to evaluate large portions of the Windows software and bootloader code. This review will begin in January.

Despite the progress above, there's still a lot of work to do. The iSEC review will cover a lot of the thorniest bits of the code, but we are still working to audit the core cryptographic routines of Truecrypt and move the project onto a secure (deterministic) build footing. We hope to have further announcements in the next few weeks.

Let me add one more personal note.

I usually take a pretty skeptical attitude on this blog when it comes to Internet security. For the most part we do things wrong, and I used to think most people didn't care. The fact is that I was wrong. If the response to our audit call is any evidence, you do care. You care a lot.

Donations (click to enlarge)

I can't tell you how amazed I am that any of this is happening. As far as I know, this is the first time that the Internet has come together in this way for the purposes of making us all a bit safer. I hope it's the beginning of a trend. 

More updates to come.

* Incidentally, determining the dollar value of BTC is fun, fun fun. We've been trying to responsibly sell these at the 'best' price. But, ugh.

[matthewdgreen]

How does the NSA break SSL?

(source)

A few weeks ago I wrote a long post about the NSA's 'BULLRUN' project to subvert modern encryption standards. I had intended to come back to this at some point, since I didn't have time to discuss the issues in detail. But then things got in the way. A lot of things, actually. Some of which I hope to write about in the near future. But before I get there, and at the risk of boring you all to tears, I wanted to come back to this subject at least one more time, if only to pontificate a bit about a question that's been bugging me. You see, the NSA BULLRUN briefing sheet mentions that NSA has been breaking quite a few encryption technologies, some of which are more interesting than others. One of those technologies is particularly surprising to me, since I just can't figure how NSA might be doing it. In this extremely long post I'm going to try to dig a bit deeper into the most important question facing the Internet today. Specifically: how the hell is NSA breaking SSL?

Section of the BULLRUN briefing sheet. Source: New York Times.

To keep things on target I'm going to make a few basic ground rules. First, I'm well aware that NSA can install malware on your computer and pwn any cryptography you choose. That doesn't interest me at all, for the simple reason that it doesn't scale well. NSA can do this to you, but they can't do it for an entire population. And that's really what concerns me about the recent leaks: the possibility that NSA is breaking encryption for the purposes of mass surveillance. For the same reason, we're not going to worry about man-in-the-middle (MITM) attacks. While we know that NSA does run these, they're also a very targeted attack. Not only are MITMs detectable if you do them at large scale, they don't comport with what we know about how NSA does large-scale interception -- mostly via beam splitters and taps. In other words: we're really concerned about passive surveillance. The rules above aren't absolute, of course. We will consider limited targeted attacks on servers, provided they later permit passive decryption of large amounts of traffic; e.g., decryption of traffic to major websites. We will also consider arbitrary modifications to software and hardware -- something we know NSA is already doing. One last point: to keep things from going off the rails, I've helpfully divided this post into two sections. The first will cover attacks that use only known techniques. Everything in this section can be implemented by a TAO employee with enough gumption and access to software. The second section, which I've titled the 'Tinfoil Hat Spectrum' covers the fun and speculative stuff -- ranging from new side channel attacks all the way to that huge quantum computer the NSA keeps next to BWI. We'll start with the 'practical'. Attacks that use Known Techniques Theft of RSA keys. The most obvious way to 'crack' SSL doesn't really involve cracking anything. Why waste time and money on cryptanalysis when you can just steal the keys? This issue is of particular concern in servers configured for the TLS RSA handshake, where a single 128-byte server key is all you need to decrypt every past and future connection made from the device. In fact, this technique is so obvious that it's hard to imagine NSA spending a lot of resources on sophisticated cryptanalytic attacks. We know that GCHQ and NSA are perfectly comfortable suborning even US providers overseas. And inside our borders, they've demonstrated a willingness to obtain TLS/SSL keys using subpoena powers and gag orders. If you're using an RSA connection to a major website, it may be sensible to assume the key is already known. Of course, even where NSA doesn't resort to direct measures, there's always the possibility of obtaining keys via a remote software exploit. The beauty is that these attacks don't even require remote code execution. Given the right vulnerability, it may simply require a handful of malformed SSL requests to map the full contents of the OpenSSL/SChannel heap.

Source: New York Times

Suborning hardware encryption chips. A significant fraction of SSL traffic on the Internet is produced by hardware devices such as SSL terminators and VPN-enabled routers. Fortunately we don't have to speculate about the security of these devices -- we already know NSA/GCHQ have been collaborating with hardware manufacturers to 'enable' decryption on several major VPN encryption chips. The NSA documents aren't clear on how this capability works, or if it even involves SSL. If it does, the obvious guess is that each chip encrypts and exflitrates bits of the session key via 'random' fields such as IVs and handshake nonces. Indeed, this is relatively easy to implement on an opaque hardware device. The interesting question is how one ensures these backdoors can only be exploited by NSA -- and not by rival intelligence agencies. (Some thoughts on that here.) Side channel attacks. Traditionally when we analyze cryptographic algorithms we concern ourselves with the expected inputs and outputs of the system. But real systems leak all kinds of extra information. These 'side channels' -- which include operation time, resource consumption, cache timing, and RF emissions -- can often be used to extract secret key material. The good news is that most of these channels are only exploitable when the attacker is in physical proximity to a TLS server. The bad news is that there are conditions in which the attacker can get close. The most obvious example involves virtualized TLS servers in the cloud setting, where a clever attacker may share physical resources with the target device. A second class of attack uses remote timing information to slowly recover an RSA key. These attacks can be disabled via countermeasures such as RSA blinding, though amusingly, some 'secure' hardware co-processors may actually turn these countermeasures off by default! At very least, this makes the hardware vulnerable to attacks by a local user, and could even facilitate remote recovery of RSA keys. Weak random number generators. Even if you're using strong Perfect Forward Secrecy ciphersuites, the security of TLS depends fundamentally on the availability of unpredictable random numbers. Not coincidentally, tampering with random number generator standards appears to have been a particular focus of NSA's efforts. Random numbers are critical to a number of elements in TLS, but they're particularly important in three places:

On the client side, during the RSA handshake. The RNG is used to generate the RSA pre-master secret and encryption padding. If the attacker can predict the output of this generator, she can subsequently decrypt the entire session. Ironically, a failure of the server RNG is much less devastating to the RSA handshake.*

On the client or server side, during the Diffie-Hellman handshake(s). Since Diffie-Hellman requires a contribution from each side of the connection, a predictable RNG on either side renders the session completely transparent.

During long-term key generation, particularly of RSA keys. If this happens, you're screwed.

And you just don't need to be that sophisticated to weaken a random number generator. These generators are already surprisingly fragile, and it's awfully difficult to detect when one is broken. Debian's maintainers made this point beautifully back in 2008 when an errant code cleanup reduced the effective entropy of OpenSSL to just 16 bits. In fact, RNGs are so vulnerable that the challenge here is not weakening the RNG -- any idiot with a keyboard can do that -- it's doing so without making the implementation trivially vulnerable to everyone else. 

The good news is that it's relatively easy to tamper with an SSL implementation to make it encrypt and exfiltrate the current RNG seed. This still requires someone to physically alter the library, or install a persistent exploit, but it can be done cleverly without even adding much new code to the existing OpenSSL code. (OpenSSL's love of function pointers makes it particularly easy to tamper with this stuff.)

If tampering isn't your style, why not put the backdoor in plain sight? That's the approach NSA took with the Dual_EC RNG, standardized by NIST in Special Publication 800-90. There's compelling evidence that NSA deliberately engineered this generator with a backdoor -- one that allows them to break any TLS/SSL connection made using it. Since the generator is (was) the default in RSA's BSAFE library, you should expect every TLS connection made using that software to be potentially compromised.

And I haven't even mentioned Intel's plans to replace the Linux kernel RNG with its own hardware RNG.

Esoteric Weaknesses in PFS systems. Many web servers, including Google and Facebook, now use Perfect Forward Secrecy ciphersuites like ephemeral Diffie-Hellman (DHE and ECDHE). In theory these ciphersuites provide the best of all possible worlds: keys persist for one session and then disappear once the connection is over. While this doesn't save you from RNG issues, it does make key theft a whole lot more difficult. PFS ciphersuites are a good thing, but a variety of subtle issues can cramp their style. For one thing, the session resumption mechanism can be finicky: session keys must either be stored locally, or encrypted and given out to users in the form of session tickets. Unfortunately, the use of session tickets somewhat diminishes the 'perfectness' of PFS systems, since the keys used for encrypting the tickets now represent a major weakness in the system. Moreover, you can't even keep them internal to one server, since they have to be shared among all of a site's front-end servers! In short, they seem like kind of a nightmare. A final area of concern is the validation of Diffie-Hellman parameters. The current SSL design assumes that DH groups are always honestly generated by the server. But a malicious implementation can violate this assumption and use bad parameters, which enable third party eavesdropping. This seems like a pretty unlikely avenue for enabling surveillance, but it goes to show how delicate these systems are. The Tinfoil Hat Spectrum I'm going to refer to the next batch of attacks as 'tinfoil hat' vulnerabilities. Where the previous issues all leverage well known techniques, each of the following proposals require totally new cryptanalytic techniques. All of which is a way of saying that the following section is pure speculation. It's fun to speculate, of course. But it requires us to assume facts not in evidence. Moreover, we have to be a bit careful about where we stop. So from here on out we are essentially conducting a thought-experiment. Let's imagine the NSA has a passive SSL-breaking capability; and furthermore, that it doesn't rely on the tricks of the previous section. What's left? The following list begins with the most 'likely' theories and works towards the truly insane. Breaking RSA keys. There's a persistent rumor in our field that NSA is cracking 1024-bit RSA keys. It's doubtful this rumor stems from any real knowledge of NSA operations. More likely it's driven by the fact that cracking 1024-bit keys is highly feasible for an organization with NSA's resources. How feasible? Several credible researchers have attempted to answer this question, and it turns out that the cost is lower than you think. Way back in 2003, Shamir and Tromer estimated $10 million for a purpose-built machine that could factor one 1024-bit key per year. In 2013, Tromer reduced those numbers to about $1 million, factoring in hardware advances. And it could be significantly lower. This is pocket change for NSA. Along similar lines, Bernstein, Heninger and Lange examined at the feasibility of cracking RSA using distributed networks of standard PCs. Their results are pretty disturbing: in principal, a cluster about the size of the real-life Conficker botnet could do serious violence to 1024-bit keys. Given all this, you might ask why this possibility is even in the 'tinfoil hat' category. The simple answer is: because nobody's actually done it. That means it's at least conceivable that the estimates above are dramatically too high -- or even too low. Moreover, RSA-1024 keys are being rapidly being phased out. Cracking 2048 bit keys would require significant mathematical advances, taking us much deeper into the tinfoil hat.** Cracking RC4. On paper, TLS supports a variety of strong encryption algorithms. In practice, about half of all TLS traffic is secured with the creaky old RC4 cipher. And this should worry you -- because RC4 is starting to show its age. In fact, as used in TLS it's already vulnerable to (borderline) practical attacks. Thus it seems like a nice candidate for a true cryptanalytic advance on NSA's part. Unfortunately the problem with this theory is that we simply don't know of any attack that would allow the NSA to usefully crack RC4! The known techniques require an attacker to collect thousands or millions of ciphertexts that are either (a) encrypted with related keys (as in WEP) or (b) contain the same plaintext. The best known attack against TLS takes the latter form -- it requires the victim to establish billions of sessions, and even then it only recovers fixed plaintext elements like cookies or passwords. The counterargument is that the public research community hasn't been thinking very hard about RC4 for the past decade -- in part because we thought it was so broken people had stopped using it (oops!) If we'd been focusing all our attention on it (or better, the NSA's attention), who knows what we'd have today. If you told me the NSA had one truly new cryptanalytic capability, I'd agree with Jake and point the finger at RC4. Mostly because the alternatives are far scarier. New side-channel attacks. For the most part, remote timing attacks appear to have been killed off by the implementation of countermeasures such as RSA blinding, which confound timing by multiplying a random blinding factor into each ciphertext prior to decryption. In theory this should make timing information essentially worthless. In practice, many TLS implementations implement compromises in the blinding code that might resurrect these attacks, things like squaring a blinding factor between decryption operations, rather than generating a new one each time. It's quite unlikely there are attacks here, but who knows. Goofy stuff. Maybe NSA does have something truly amazing up its sleeve. The problem with opening this Pandora's box is that it's really hard to get it closed again. Did Jerry Solinas really cook the NIST P-curves to support some amazing new attack (which NSA knew about way back in the late 1990s, but we have not yet discovered)? Does the NSA have a giant supercomputer named TRANSLTR that can brute-force any cryptosystem? Is there a giant quantum computer at the BWI Friendship annex? For answers to these questions you may as well just shake the Magic 8-Ball, cause I don't have a clue. Conclusion We don't know and can't know the answer to these things, and honestly it'll make you crazy if you start thinking about it. All we can really do is take NSA/GCHQ at their word when they tell us that these capabilities are 'extremely fragile'. That should at least give us hope. The question now is if we can guess well enough to turn that fragility from a warning into a promise. Notes: * A failure of the server RNG could result in some predictable values like the ServerRandom and session IDs. An attacker who can predict these values may be able to run active attacks against the protocol, but -- in the RSA ciphersuite, at least -- they don't admit passive compromise. ** Even though 1024-bit RSA keys are being eliminated, many servers still use 1024-bit for Diffie-Hellman (mostly for efficiency reasons). The attacks on these keys are similar to the ones used against RSA -- however, the major difference is that fresh Diffie-Hellman 'ephemeral' keys are generated for each new connection. Breaking large amounts of traffic seems quite costly.

[matthewdgreen]

Let's audit Truecrypt!

[source]

A few weeks ago, after learning about the NSA's efforts to undermine encryption software, I wrote a long post urging developers to re-examine our open source encryption software. Then I went off and got distracted by other things. Well, I'm still distracted by other things, but people like Kenn White have been getting organized. Today I'm proud to announce the result. It is my great pleasure to publicize (and belatedly kick off) an open project to audit the Truecrypt disk encryption tool. If you already know why this is important, by all means stop reading this post now. Go to the site and donate! It doesn't have to be money, although that would be best. If you're an information security professional/expert/hobbyist please consider giving us some of your time to help identify bugs in the software. In case you don't see the reason for a Truecrypt audit, I'm going to devote the remainder of this post to convincing you how important it is. And who knows, maybe I'll even convince you we can do more.

Why audit Truecrypt? In case you haven't noticed, there's a shortage of high-quality and usable encryption software out there. Truecrypt is an enormous deviation from this trend. It's nice, it's pretty, it's remarkably usable. My non-technical lawyer friends have been known to use it from time to time, and that's the best 'usable security' complement you can give a piece of software.

  But the better answer is: because Truecrypt is important! Lots of people use it to store very sensitive information. That includes corporate secrets and private personal information. Bruce Schneier is even using it to store information on his personal air-gapped super-laptop, after he reviews leaked NSA documents. We should be sweating bullets about the security of a piece of software like this. So what's wrong with Truecrypt? Maybe nothing at all. Rest assured if I knew of a specific problem with Truecrypt, this post would have a very different title -- something with exclamation points and curse words and much wry humor. Let me be clear: I am not implying anything like this. Not even a little.

The 'problem' with Truecrypt is the same problem we have with any popular security software in the post-September-5 era: we don't know what to trust anymore. We have hard evidence that the NSA is tampering with encryption software and hardware, and common sense tells us that NSA is probably not alone. Truecrypt, as popular and widely trusted as it is, makes a fantastic target for subversion. But quite frankly there are other things that worry me about Truecrypt. The biggest one is that nobody knows who wrote it. This skeeves me out. As Dan Kaminsky puts it, 'authorship is a better predictor of quality than openness'. I would feel better if I knew who the TrueCrypt authors were. Now please don't take this the wrong way: anonymity is not a crime. It's possible the Truecrypt developers are magical security elves who are simply trying to protect their vital essence. More prosaically, perhaps they live in a country where privacy advocates aren't as revered as they are in the US. (I kid.)

But anonymity isn't the only thing that concerns me about Truecrypt. For one thing, the software does some damned funny things that should make any (correctly) paranoid person think twice. Here I will quote from the Ubuntu Privacy Group's review of Truecrypt 7.0:

[T]he Windows version of TrueCrypt 7.0a deviates from the Linux version in that it fills the last 65,024 bytes of the header with random values whereas the Linux version fills this with encrypted zero bytes. From the point of view of a security analysis the behavior of the Windows version is problematic. By an analysis of the decrypted header data it can't be distinguished whether these are indeed random values or a second encryption of the master and XTR key with a back door password. From the analysis of the source we could preclude that this is a back door... As it can't be ruled out that the published Windows executable of Truecrypt 7.0a is compiled from a different source code than the code published in "TrueCrypt_7.0a_Source.zip" we however can't preclude that the binary Windows package uses the header bytes after the key for a back door.

Which of course tees up the most important concern: even if the Truecrypt source code is trustworthy, there's no reason to believe that the binaries are. And many, many people only encounter Truecrypt as a Windows binary. In my very humble opinion that should worry you. In short: there are numerous reasons we need to audit this software -- and move its build process onto safe, deterministic footing. What's your plan? The exact terms are still a work in progress, but our proposal breaks down into roughly four components:

License review. Truecrypt uses an odd, potentially non-FOSS license. We'd like to have it reviewed by a competent attorney to see how compatible it is with GPL and other OSS software.

Implement deterministic/reproducible builds. Many of our concerns with Truecrypt could go away if we knew the binaries were compiled from source. Unfortunately it's not realistic to ask every Windows user to compile Truecrypt themselves. Our proposal is to adapt the deterministic build process that Tor is now using, so we can know the binaries are safe and untampered. This is really a precondition to everything else. And it's not an easy process.

Pay out bug bounties. Not every developer has time or money to audit the entire source. But some have a little time. If we collect enough, we'd like to compensate bug hunters a little bit for anything security critical they find in the code.

Conduct a professional audit. The real dream of this project is to see the entire codebase receive a professional audit from one of the few security evaluation companies who are qualified to review crypto software. We're hoping to convince one of the stronger companies to donate some time and/or reduced rates. But good work doesn't come free, and that's why we're asking for help.

We don't expect any single person to do all of this. The exact balance of payouts from our collected fund is still TBD, but we will be formalizing it soon. We also want specialists and experts, and we also want people to donate their time wherever possible. We deserve better tools than what we have now. Done correctly, this project makes us all stronger. Aren't you worried you'll insult the Truecrypt developers? I sure hope not, since we're all after the same thing. Remember, our goal isn't to find some mythical back door in Truecrypt, but rather, to wipe away any doubt people have about the security of this tool. But perhaps this will tick people off. And if you're one of the developers and you find that you're ticked, I'll tell you exactly how to get back at us. Up your game. Beat us to the punch and make us all look like fools. We'll thank you for it.

Wait, if we can do this for Truecrypt, couldn't we do it for other software? And now you've seen the true promise of this plan. Help us make it work for Truecrypt. Then let's talk.

[matthewdgreen]

RSA warns developers not to use RSA products

In today's news of the weird, RSA (a division of EMC) has recommended that developers desist from using the (allegedly) 'backdoored' Dual_EC_DRBG random number generator -- which happens to be the default in RSA's BSafe cryptographic toolkit. Youch.

In case you're missing the story here, Dual_EC_DRBG (which I wrote about yesterday) is the random number generator voted most likely to be backdoored by the NSA. The story here is that -- despite many valid concerns about this generator -- RSA went ahead and made it the default generator used for all cryptography in its flagship cryptography library. The implications for RSA and RSA-based products are staggering. In the worst case a modestly bad but by no means worst case, the NSA may be able to intercept SSL/TLS connections made by products implemented with BSafe. So why would RSA pick Dual_EC as the default? You got me. Not only is Dual_EC hilariously slow -- which has real performance implications -- it was shown to be a just plain bad random number generator all the way back in 2006. By 2007, when Shumow and Ferguson raised the possibility of a backdoor in the specification, no sensible cryptographer would go near the thing. And the killer is that RSA employs a number of highly distinguished cryptographers! It's unlikely that they'd all miss the news about Dual_EC.

We can only speculate about the past. But here in the present we get to watch RSA's CTO Sam Curry publicly defend RSA's choices. I sort of feel bad for the guy. But let's make fun of him anyway.

I'll take his statement line by line (Sam is the boldface):

"Plenty of other crypto functions (PBKDF2, bcrypt, scrypt) will iterate a hash 1000 times specifically to make it slower."

Password hash functions are built deliberately slow to frustrate dictionary attacks. Making a random number generator slow is just dumb.

At the time, elliptic curves were in vogue

Say what?

and hash-based RNG was under scrutiny.

Nonsense. A single obsolete hash based generator (FIPS 186) was under scrutiny -- and fixed. The NIST SP800-90 draft in which Dual_EC appeared ALSO provided three perfectly nice non-backdoored generators: two based on hash functions and one based on AES. BSafe even implements some of them. Sam, this statement is just plain misleading.

The hope was that elliptic curve techniques—based as they are on number theory—would not suffer many of the same weaknesses as other techniques (like the FIPS 186 SHA-1 generator) that were seen as negative 

Dual-EC suffers exactly the same sort of weaknesses as FIPS 186. Unlike the alternative generators in NIST SP800-90 it has a significant bias and really should not be used in production systems. RSA certainly had access to this information after the analyses were published in 2006.

and Dual_EC_DRBG was an accepted and publicly scrutinized standard.

And every bit of public scrutiny said the same thing: this thing is broken! Grab your children and run away!

SP800-90 (which defines Dual EC DRBG) requires new features like continuous testing of the output, mandatory re-seeding,

The exact same can be said for the hash-based and AES-based alternative generators you DIDN'T choose from SP800-90. 

optional prediction resistance and the ability to configure for different strengths.

So did you take advantage of any of these options as part of the BSafe defaults? Why not? How about the very simple mitigations that NIST added to SP800-90A as a means to remove concerns that the generator might have a backdoor? Anyone?

There's not too much else to say here. I guess the best way to put it is: this is all part of the process. First you find the disease. Then you see if you can cure it.

[matthewdgreen]

The Many Flaws of Dual_EC_DRBG

The Dual_EC_DRBG generator from NIST SP800-90A.

Update 9/19: RSA warns developers not to use the default Dual_EC_DRBG generator in BSAFE. Oh lord. As a technical follow up to my previous post about the NSA's war on crypto, I wanted to make a few specific points about standards. In particular I wanted to address the allegation that NSA inserted a backdoor into the Dual-EC pseudorandom number generator. For those not following the story, Dual-EC is a pseudorandom number generator proposed by NIST for international use back in 2006. Just a few months later, Shumow and Ferguson made cryptographic history by pointing out that there might be an NSA backdoor in the algorithm. This possibility -- fairly remarkable for an algorithm of this type -- looked bad and smelled worse. If true, it spelled almost certain doom for anyone relying on Dual-EC to keep their system safe from spying eyes. Now I should point out that much of this is ancient history. What is news today is the recent leak of classified documents that points a very emphatic finger towards Dual_EC, or rather, to an unnamed '2006 NIST standard'. The evidence that Dual-EC is this standard has now become so hard to ignore that NIST recently took the unprecedented step of warning implementers to avoid it altogether. Better late than never. In this post I'm going to try to explain the curious story of Dual-EC. While I'll do my best to keep this discussion at a high and non-mathematical level, be forewarned that I'm probably going to fail at least at a couple of points. I you're not the mood for all that, here's a short summary:

In 2005-2006 NIST and NSA released a pseudorandom number generator based on elliptic curve cryptography. They released this standard -- with very little explanation -- both in the US and abroad. 

This RNG has some serious issues with just being a good RNG. The presence of such obvious bugs was mysterious to cryptographers.

In 2007 a pair of Microsoft researchers pointed out that these vulnerabilities combined to produce a perfect storm, which -- together with some knowledge that only NIST/NSA might have -- opened a perfect backdoor into the random number generator itself.

This backdoor may allow the NSA to break nearly any cryptographic system that uses it. 

If you're still with me, strap in. Here goes the long version. Dual-EC For a good summary on the history of Dual-EC-DRBG, see this 2007 post by Bruce Schneier. Here I'll just give the highlights. Back in 2004-5, NIST decided to address a longstanding weakness of the FIPS standards, namely, the limited number of approved pseudorandom bit generator algorithms (PRGs, or 'DRBGs' in NIST parlance) available to implementers. This was actually a bit of an issue for FIPS developers, since the existing random number generators had some known design weaknesses.* NIST's answer to this problem was Special Publication 800-90, parts of which were later wrapped up into the international standard ISO 18031. The NIST pub added four new generators to the FIPS canon. None these algorithms is a true random number generator in the sense that they collect physical entropy. Instead, what they do is process the (short) output of a true random number generator -- like the one in Linux -- conditioning and stretching this 'seed' into a large number of random-looking bits you can use to get things done.** This is particularly important for FIPS-certified cryptographic modules, since the FIPS 140-2 standards typically require you to use a DRBG as a kind of 'post-processing' -- even when you have a decent hardware generator. The first three SP800-90 proposals used standard symmetric components like hash functions and block ciphers. Dual_EC_DRBG was the odd one out, since it employed mathematics more that are typically used to construct public-key cryptosystems. This had some immediate consequences for the generator: Dual-EC is slow in a way that its cousins aren't. Up to a thousand times slower. Now before you panic about this, the inefficiency of Dual_EC is not necessarily one of its flaws! Indeed, the inclusion of an algebraic generator actually makes a certain amount of sense. The academic literature includes a distinguished history of provably secure PRGs based on on number theoretic assumptions, and it certainly didn't hurt to consider one such construction for standardization. Most developers would probably use the faster symmetric alternatives, but perhaps a small number would prefer the added confidence of a provably-secure construction. Unfortunately, here is where NIST ran into their first problem with Dual_EC.

Flaw #1: Dual-EC has no security proof. 

Let me spell this out as clearly as I can. In the course of proposing this complex and slow new PRG where the only damn reason you'd ever use the thing is for its security reduction, NIST forgot to provide one. This is like selling someone a Mercedes and forgetting to attach the hood ornament. I'd like to say this fact alone should have damned Dual_EC, but sadly this is par for the course for NIST -- which treats security proofs like those cool Japanese cookies you can never find. In other words, a fancy, exotic luxury. Indeed, NIST has a nasty habit of dumping proof-writing work onto outside academics, often after the standard has been finalized and implemented in products everywhere. So when NIST put forward its first draft of SP800-90 in 2005, academic cryptographers were left to analyze it from scratch. Which, to their great credit, they were quite successful at. The first thing reviewers noticed is that Dual-EC follows a known design paradigm -- it's a weird variant of an elliptic curve linear congruential generator. However they also noticed that NIST had made some odd rookie mistakes. Now here we will have to get slightly wonky -- though I will keep mathematics to a minimum. (I promise it will all come together in the end!) Constructions like Dual-EC have basically two stages:

A stage that generates a series of pseudorandom elliptic curve points. Just like on the graph at right, an elliptic curve point is a pair (x, y) that satisfies an elliptic curve equation. In general, both x and y are elements of a finite field, which for our purposes means they're just large integers.*** The main operation of the PRNG is to apply mathematical operations to points on the elliptic curve, in order to generate new points that are pseudorandom -- i.e., are indistinguishable from random points in some subgroup. And the good news is that Dual-EC seems to do this first part beautifully! In fact Brown and Gjøsteen even proved that this part of the generator is sound provided that the Decisional Diffie-Hellman problem is hard in the specific elliptic curve subgroup. This is a well studied hardness assumption so we can probably feel pretty confident in this proof.  

Extract pseudorandom bits from the generated EC points. While the points generated by Dual-EC may be pseudorandom, that doesn't mean the specific (x, y) integer pairs are random bitstrings. For one thing, 'x' and 'y' are not really bitstrings at all, they're integers less than some prime number. Most pairs don't satisfy the curve equation or are not in the right subgroup. Hence you can't just output the raw x or y values and expect them to make good pseudorandom bits. Thus the second phase of the generator is to 'extract' some (but not all) of the bits from the EC points. Traditional literature designs do all sorts of things here -- including hashing the point or dropping up to half of the bits of the x-coordinate. Dual-EC does something much simpler: it grabs the x coordinate, throws away the most significant 16-18 bits, and outputs the rest.

In 2006, first Gjøsteen and later Schoenmakers and Sidorenko took a close look at Dual-EC and independently came up with a surprising result:

Flaw #2: Dual-EC outputs too many bits. 

Unlike those previous EC PRGs which output anywhere from 2/3 to half of the bits from the x-coordinate, Dual-EC outputs nearly the entire thing. This is good for efficiency, but unfortunately it also gives Dual-EC a bias. Due to some quirks in the mathematics of the field operations, an attacker can now predict the next bits of Dual-EC output with a fairly small -- but non-trivial -- success probability, in the range of 0.1%. While this number may seem small to non-cryptographers, it's basically a hanging offense for a cryptographic random number generator where probability of predicting a future bit should be many orders of magnitude lower. What's just plain baffling is that this flaw ever saw the light of day. After all, the specification was developed by bright people at NIST -- in collaboration with NSA. Either of those groups should easily have discovered a bug like this, especially since this issue had been previously studied. Indeed, within a few months of public release, two separate groups of academic cryptographers found it, and were able to implement an attack using standard PC equipment. So in summary, the bias is mysterious and it seems to be very much an 'own-goal' on the NSA's part. Why in the world would they release so much information from each EC point? It's hard to say, but a bit more investigation reveals some interesting consequences:

Flaw #3: You can guess the original EC point from looking at the output bits.

By itself this isn't really a flaw, but will turn out to be interesting in just a minute. Since Dual-EC outputs so many bits from the x-coordinate of each point -- all but the most significant 16 bits -- it's relatively easy to guess the original source point by simply brute-forcing the missing 16 bits and solving the elliptic curve equation for y. (This is all high-school algebra, I swear!) While this process probably won't uniquely identify the original (x, y), it'll give you a modestly sized list of candidates. Moreover with only 16 missing bits the search can be done quickly even on a desktop computer. Had Dual_EC thrown away more bits of the x-coordinate, this search would not have been feasible at all. So what does this mean? In general, recovering the EC point shouldn't actually be a huge problem. In theory it could lead to a weakness -- say predicting future outputs -- but in a proper design you would still have to solve a discrete logarithm instance for each and every point in order to predict the next bytes output by the generator. And here is where things get interesting.

Flaw #4: If you know a certain property about the Dual_EC parameters, and can recover an output point, you can predict all subsequent outputs of the generator.

Did I tell you this would get interesting in a minute? I totally did. The next piece of our puzzle was discovered by Microsoft researchers Dan Shumow and Niels Ferguson, and announced at the CRYPTO 2007 rump session. I think this result can best be described via the totally intuitive diagram below. (Don't worry, I'll explain it!)

Annotated diagram from Shumow-Ferguson presentation (CRYPTO 2007). Colorful elements were added by yours truly. Thick green arrows mean 'this part is easy to reverse'. Thick red arrows should mean the opposite. Unless you're the NSA.

The Dual-EC generator consists of two stages: a portion that generates the output bits (right) and a part that updates the internal state (left). Starting from the "r_i" value (circled, center) and heading right, the bit generation part first computes the output point using the function "r_i * Q" -- where Q is an elliptic curve point defined in the parameters -- then truncates 16 bits its off its x-coordinate to get the raw generator output. The "*" operator here describes elliptic point multiplication, which is a complex operation that should be relatively hard to invert. Note that everything after the point multiplication should be easy to invert and recover from the output, as we discussed in the previous section. Every time the generator produces one block of output bits, it also updates its internal state. This is designed to prevent attacks where someone compromises the internal values of a working generator, then uses this value to wind the generator backwards and guess past outputs. Starting again from the circled "r_i" value, the generator now heads upwards and computes the point "r_i * P" where P is a different elliptic curve point also described in the parameters. It then does some other stuff. The theory here is that P and Q should be random points, and thus it should be difficult to find "r_i * P" used for state update even if you know the output point "r_i * Q" -- which I stress you do know, because it's easy to find. Going from one point to the other requires you to know a relationship between P and Q, which you shouldn't actually know since they're supposed to be random values. The difficulty of this is indicated by the thick red arrow.

Looks totally kosher to me. (Source: NIST SP800-90A)

There is, however, one tiny little exception to this rule. What if P and Q aren't entirely random values? What if you chose them yourself specifically so you'd know the mathematical relationship between the two points? In this case it turns out you can easily compute the next PRG state after recovering a single output point (from 32 bytes of RNG output). This means you can follow the equations through and predict the next output. And the next output after that. And on forever and forever.**** This is a huge deal in the case of SSL/TLS, for example. If I use the Dual-EC PRG to generate the "Client Random" nonce transmitted in the beginning of an SSL connection, then the NSA will be able to predict the "Pre-Master" secret that I'm going to generate during the RSA handshake. Given this information the connection is now a cleartext read. This is not good. So now you should all be asking the most important question of all: how the hell did the NSA generate the specific P and Q values recommended in Appendix A of Dual-EC-DRBG? And do they know the relationship that allows them to run this attack? All of which brings us to:

Flaw #5: Nobody knows where the recommended parameters came from.

And if you think that's problematic, welcome to the club. But why? And where is Dual-EC used? The ten million dollar question of Dual-EC is why the NSA would stick such an obviously backdoored algorithm into an important standard. Keep in mind that cryptographers found the major (bias) vulnerabilities almost immediately after Dual-EC shipped. The possibility of a 'backdoor' was announced in summer 2007. Who would still use it? A few people have gone through the list of CMVP-evaluated products and found that the answer is: quite a few people would. Most certify Dual-EC simply because it's implemented in OpenSSL-FIPS, and they happen to use that library. But at least one provider certifies it exclusively. Yuck.

Hardcoded constants from the OpenSSL-FIPS implementation of Dual_EC_DRBG. Recognize 'em?

It's worth keeping in mind that NIST standards carry a lot of weight -- even those that might have a backdoor. Folks who aren't keeping up on the latest crypto results could still innocently use the thing, either by accident or (less innocently) because the government asked them to. Even if they don't use it, they might include the code in their product -- say through the inclusion of OpenSSL-FIPS or MS Crypto API -- which means it's just a function call away from being surreptitiously activated. Which is why people need to stop including Dual-EC immediately. We have no idea what it's for, but it needs to go away. Now. So what about the curves? The last point I want to make is that the vulnerabilities in Dual-EC have precisely nothing to do with the specifics of the NIST standard elliptic curves themselves. The 'back door' in Dual-EC comes exclusively from the relationship between P and Q -- the latter of which is published only in the Dual-EC specification. The attack can work even if you don't use the NIST pseudorandom curves. However, the revelations about NIST and the NSA certainly make it worth our time to ask whether these curves themselves are somehow weak. The best answer to that question is: we don't know. Others have observed that NIST's process for generating the curves leaves a lot to be desired. But including some kind of hypothetical backdoor would be a horrible, horrific idea -- one that would almost certainly blow back at us. You'd think people with common sense would realize this. Unfortunately we can't count on that anymore. Thanks to Tanja Lange for her assistance proofing this post. Any errors in the text are entirely mine. Notes: * My recollection of this period is hazy, but prior to SP800-90 the two most common FIPS DRBGs in production were (1) the SHA1-based DSA generator of FIPS 186-2 and (2) ANSI X9.31. The DSA generator was a special-purpose generator based on SHA1, and was really designed just for that purpose. ANSI X9.31 used block ciphers, but suffered from some more subtle weaknesses it retained from the earlier X9.17 generator. These were pointed out by Kelsey, Schneier, Wagner and Hall. ** This is actually a requirement of the FIPS 140-2 specification. Since FIPS does not approve any true random number generators, it instead mandates that you run your true RNG output through a DRBG (PRNG) first. The only exception is if your true RNG has been approved 'for classified use'. *** Specifically, x and y are integers in the range 0 to p-1 where p is a large prime number. A point is a pair (x, y) such that  mod p. The values a and b are defined as part of the curve parameters. **** The process of predicting future outputs involves a few guesses, since you don't know the exact output point (and had to guess at the missing 16 bits), but you can easily reduce this to a small set of candidates -- then it's just a question of looking at a few more bits of RNG output until you guess the right one.

[matthewdgreen]

A note on the NSA, the future and fixing mistakes

Readers of this blog will know this has been an interesting couple of days for me. I have very mixed feelings about all this. On the one hand, it's brought this blog a handful of new readers who might not have discovered it otherwise. On the other hand, it's made me a part of the story in a way I don't deserve to be. After speaking with my colleagues and (most importantly) with my wife, I thought I might use the last few seconds of my inadvertent notoriety to make some of highly non-technical points about the recent NSA revelations and my decision to blog about them. I believe my first point should be self-evident: the NSA has made a number of terrible mistakes. These range from policy decisions to technical direction, to matters of their own internal security. There may have been a time when these mistakes could have been mitigated or avoided, but that time has passed. Personally I believe it passed even before Edward Snowden made his first contact with the press. But the disclosures of classified documents have set those decisions in stone. Given these mistakes, we're now faced with the job of cleaning up the mess. To that end there are two sets of questions: public policy questions -- who should the NSA be spying on and how far should they be allowed to go in pursuit of that goal? And a second set of more technical questions: how do we repair the technological blowback from these decisions? There are many bright people -- quite a few in Congress -- who are tending to the first debate. While I have my opinions about this, they're (mostly) not the subject of this blog. Even if they were, I would probably be the wrong person to discuss them. So my concern is the technical question. And I stress that while I label this 'technical', it isn't a question of equations and logic gates. The tech sector is one of the fastest growing and most innovative areas of the US economy. I believe the NSA's actions have caused long-term damage to our credibility, in a manner that threatens our economic viability as well as, ironically, our national security. The interesting question to me -- as an American and as someone who cares about the integrity of speech -- is how we restore faith in our technology. I don't have the answers to this question right now. Unfortunately this is a long-term problem that will consume the output of researchers and technologists far more talented than I. I only hope to be involved in the process. So while I know there are people at NSA who must be cursing Edward Snowden's name and wishing we'd all stop talking about this. Too late. I hope that they understand the game we're playing now. Their interests as well as mine now depend on repairing the damage. Downplaying the extent of the damage, or trying to restrict access to (formerly) classified documents does nobody any good. It's time to start fixing things.

[matthewdgreen]

On the NSA

Let me tell you the story of my tiny brush with the biggest crypto story of the year. A few weeks ago I received a call from a reporter at ProPublica, asking me background questions about encryption. Right off the bat I knew this was going to be an odd conversation, since this gentleman seemed convinced that the NSA had vast capabilities to defeat encryption. And not in a 'hey, d'ya think the NSA has vast capabilities to defeat encryption?' kind of way. No, he'd already established the defeating. We were just haggling over the details. Oddness aside it was a fun (if brief) set of conversations, mostly involving hypotheticals. If the NSA could do this, how might they do it? What would the impact be? I admit that at this point one of my biggest concerns was to avoid coming off like a crank. After all, if I got quoted sounding too much like an NSA conspiracy nut, my colleagues would laugh at me. Then I might not get invited to the cool security parties. All of this is a long way of saying that I was totally unprepared for today's bombshell revelations describing the NSA's efforts to defeat encryption. Not only does the worst possible hypothetical I discussed appear to be true, but it's true on a scale I couldn't even imagine. I'm no longer the crank. I wasn't even close to cranky enough. And since I never got a chance to see the documents that sourced the NYT/ProPublica story -- and I would give my right arm to see them -- I'm determined to make up for this deficit with sheer speculation. Which is exactly what this blog post will be. 'Bullrun' and 'Cheesy Name'  If you haven't read the ProPublica/NYT or Guardian stories, you probably should. The TL;DR is that the NSA has been doing some very bad things. At a combined cost of $250 million per year, they include:

Tampering with national standards (NIST is specifically mentioned) to promote weak, or otherwise vulnerable cryptography.

Influencing standards committees to weaken protocols.

Working with hardware and software vendors to weaken encryption and random number generators.

Attacking the encryption used by 'the next generation of 4G phones'.

Obtaining cleartext access to 'a major internet peer-to-peer voice and text communications system' (Skype?)

Identifying and cracking vulnerable keys.

Establishing a Human Intelligence division to infiltrate the global telecommunications industry.

And worst of all (to me): somehow decrypting SSL connections.

All of these programs go by different code names, but the NSA's decryption program goes by the name 'Bullrun' so that's what I'll use here. How to break a cryptographic system There's almost too much here for a short blog post, so I'm going to start with a few general thoughts. Readers of this blog should know that there are basically three ways to break a cryptographic system. In no particular order, they are:

Attack the cryptography. This is difficult and unlikely to work against the standard algorithms we use (though there are exceptions like RC4.) However there are many complex protocols in cryptography, and sometimes they are vulnerable.

Go after the implementation. Cryptography is almost always implemented in software -- and software is a disaster. Hardware isn't that much better. Unfortunately active software exploits only work if you have a target in mind. If your goal is mass surveillance, you need to build insecurity in from the start. That means working with vendors to add backdoors.

Access the human side. Why hack someone's computer if you can get them to give you the key?

Bruce Schneier, who has seen the documents, says that 'math is good', but that 'code has been subverted'. He also says that the NSA is 'cheating'. Which, assuming we can trust these documents, is a huge sigh of relief. But it also means we're seeing a lot of (2) and (3) here. So which code should we be concerned about? Which hardware?

SSL Servers by OS type. Source: Netcraft.

This is probably the most relevant question. If we're talking about commercial encryption code, the lion's share of it uses one of a small number of libraries. The most common of these are probably the Microsoft CryptoAPI (and Microsoft SChannel) along with the OpenSSL library. Of the libraries above, Microsoft is probably due for the most scrutiny. While Microsoft employs good (and paranoid!) people to vet their algorithms, their ecosystem is obviously deeply closed-source. You can view Microsoft's code (if you sign enough licensing agreements) but you'll never build it yourself. Moreover they have the market share. If any commercial vendor is weakening encryption systems, Microsoft is probably the most likely suspect. And this is a problem because Microsoft IIS powers around 20% of the web servers on the Internet -- and nearly forty percent of the SSL servers! Moreover, even third-party encryption programs running on Windows often depend on CAPI components, including the random number generator. That makes these programs somewhat dependent on Microsoft's honesty. Probably the second most likely candidate is OpenSSL. I know it seems like heresy to imply that OpenSSL -- an open source and widely-developed library -- might be vulnerable. But at the same time it powers an enormous amount of secure traffic on the Internet, thanks not only to the dominance of Apache SSL, but also due to the fact that OpenSSL is used everywhere. You only have to glance at the FIPS CMVP validation lists to realize that many 'commercial' encryption products are just thin wrappers around OpenSSL. Unfortunately while OpenSSL is open source, it periodically coughs up vulnerabilities. Part of this is due to the fact that it's a patchwork nightmare originally developed by a programmer who thought it would be a fun way to learn Bignum division.* Part of it is because crypto is unbelievably complicated. Either way, there are very few people who really understand the whole codebase. On the hardware side (and while we're throwing out baseless accusations) it would be awfully nice to take another look at the Intel Secure Key integrated random number generators that most Intel processors will be getting shortly. Even if there's no problem, it's going to be an awfully hard job selling these internationally after today's news. Which standards? From my point of view this is probably the most interesting and worrying part of today's leak. Software is almost always broken, but standards -- in theory -- get read by everyone. It should be extremely difficult to weaken a standard without someone noticing. And yet the Guardian and NYT stories are extremely specific in their allegations about the NSA weakening standards. The Guardian specifically calls out the National Institute of Standards and Technology (NIST) for a standard they published in 2006. Cryptographers have always had complicated feelings about NIST, and that's mostly because NIST has a complicated relationship with the NSA. Here's the problem: the NSA ostensibly has both a defensive and an offensive mission. The defensive mission is pretty simple: it's to make sure US information systems don't get pwned. A substantial portion of that mission is accomplished through fruitful collaboration with NIST, which helps to promote data security standards such as the Federal Information Processing Standards (FIPS) and NIST Special Publications. I said cryptographers have complicated feelings about NIST, and that's because we all know that the NSA has the power to use NIST for good as well as evil. Up until today there's been no real evidence of malice, despite some occasional glitches -- and compelling evidence that at least one NIST cryptographic standard could have contained a backdoor. But now maybe we'll have to re-evaluate that relationship. As utterly crazy as it may seem. Unfortunately, we're highly dependent on NIST standards, ranging from pseudo-random number generators to hash functions and ciphers, all the way to the specific elliptic curves we use in SSL/TLS. While the possibility of a backdoor in any of these components does seem remote, trust has been violated. It's going to be an absolute nightmare ruling it out. Which people? Probably the biggest concern in all this is the evidence of collaboration between the NSA and unspecified 'telecom providers'. We already know that the major US (and international) telecom carriers routinely assist the NSA in collecting data from fiber-optic cables. But all this data is no good if it's encrypted. While software compromises and weak standards can help the NSA deal with some of this, by far the easiest way to access encrypted data is to simply ask for -- or steal -- the keys. This goes for something as simple as cellular encryption (protected by a single key database at each carrier) all the way to SSL/TLS which is (most commonly) protected with a few relatively short RSA keys. The good and bad thing is that as the nation hosting the largest number of popular digital online services (like Google, Facebook and Yahoo) many of those critical keys are located right here on US soil. Simultaneously, the people communicating with those services -- i.e., the 'targets' -- may be foreigners. Or they may be US citizens. Or you may not know who they are until you scoop up and decrypt all of their traffic and run it for keywords. Which means there's a circumstantial case that the NSA and GCHQ are either directly accessing Certificate Authority keys** or else actively stealing keys from US providers, possibly (or probably) without executives' knowledge. This only requires a small number of people with physical or electronic access to servers, so it's quite feasible.*** The one reason I would have ruled it out a few days ago is because it seems so obviously immoral if not illegal, and moreover a huge threat to the checks and balances that the NSA allegedly has to satisfy in order to access specific users' data via programs such as PRISM. To me, the existence of this program is probably the least unexpected piece of all the news today. Somehow it's also the most upsetting. So what does it all mean?  I honestly wish I knew. Part of me worries that the whole security industry will talk about this for a few days, then we'll all go back to our normal lives without giving it a second thought. I hope we don't, though. Right now there are too many unanswered questions to just let things lie. The most likely short-term effect is that there's going to be a lot less trust in the security industry. And a whole lot less trust for the US and its software exports. Maybe this is a good thing. We've been saying for years that you can't trust closed code and unsupported standards: now people will have to verify. Even better, these revelations may also help to spur a whole burst of new research and re-designs of cryptographic software. We've also been saying that even open code like OpenSSL needs more expert eyes. Unfortunately there's been little interest in this, since the clever researchers in our field view these problems as 'solved' and thus somewhat uninteresting. What we learned today is that they're solved all right. Just not the way we thought. Notes: * The original version of this post repeated a story I heard recently (from a credible source!) about Eric Young writing OpenSSL as a way to learn C. In fact he wrote it as a way to learn Bignum division, which is way cooler. Apologies Eric! ** I had omitted the Certificate Authority route from the original post due to an oversight -- thanks to Kenny Patterson for pointing this out -- but I still think this is a less viable attack for passive eavesdropping (that does not involve actively running a man in the middle attack). And it seems that much of the interesting eavesdropping here is passive. *** The major exception here is Google, which deploys Perfect Forward Secrecy for many of its connections, so key theft would not work here. To deal with this the NSA would have to subvert the software or break the encryption in some other way.

[matthewdgreen]

Is the cryptopocalypse nigh?

I've been traveling a bit over the past couple of weeks, so I haven't had much of a chance to keep up on blogging. One consequence is that I completely missed my chance to say something about, well, anything that happened at BlackHat or Def Con. Which is too bad, since a surprising amount of crypto stuff did go down! One thing that I wish I'd had a chance to talk about was a presentation at BlackHat called 'The Factoring Dead' by Tom Ritter, Javed Samuel and Alex Stamos. (Thomas Ptacek was also involved, but he insists that he did nothing and they only included him out of pity.) Although I don't quite agree with the premise of this presentation, talks like it are fun -- in the way that zombie movies are fun -- because you get to abandon reality and think about some non-serious things for a while. Factually, the presentation addresses some new results on the discrete logarithm problem published by Antoine Joux and his co-authors Razvan Barbulescu, Pierrick Gaudry and Emmanuel Thomé -- developments the presenters cite as a very serious reason for people to get worried. And we're not talking about the usual 'you're going to use crypto wrong' kind of worry, but a more earthshaking kind: namely that RSA and Diffie-Hellman and DSA are soon going to be broken altogether. Now let me be clear that Ritter, Samuel and Stamos and even lame, non-contributing Ptacek (henceforth RSSp) are all smart guys. In fact, I would venture to say they're probably much more familiar with the Joux et al. work than I am since they seem interested in the details. Me, I like my hardness assumptions the way I like my hamburgers: neatly ground up and without the mooing. I could live my whole life without voluntarily digging into the efficiency of discrete logarithm solvers in fields of small characteristic. Moreover, it's hard to really argue with the content of RSSp's presentation, since the bulk of what they do is to simply present facts. There really have been some major recent advances in solving discrete logarithms over certain special fields. There have been major attacks in the more distant past that took us by surprise. And yes, it would really awesome if people stopped fiddling with 1024-bit RSA keys and moved to elliptic curve crypto. What's concerning is the conclusions they (and other sources) have reached: namely, that factoring-based cryptosystems could be dead in just a few years. This kind of thing could incite panic! (I mean, it could if people actually cared about cryptography. Which unfortunately they mostly don't.) So let's spend some time examining this.

Razvan Barbulescu, Emmanuel Thomé and Antoine Joux hungrily eye a defenseless discrete logarithm instance. (Source: Steven Galbraith)

The background The jumping off point for RSSp's slides is a set of recent advances made by Joux and subsequently by Barbulescu, Gaudry, Joux and Thomé. The discrete logarithm problem (which you can learn about in this highly informative video) is noteworthy for two reasons. First, it's believed that in many settings, the discrete logarithm problem is difficult to solve. Second: that assumption is critical to the security of many of the cryptosystems we know and love -- for example, Diffie-Hellman and DSA. Now the Joux and Barbulescu et al. results are important work, and really do deserve attention from cryptographers and non-cryptographers alike. What they show is that there exist relatively efficient algorithms for solving discrete logarithms in certain very specific types of field. Even more amazingly, the new algorithms are efficient enough to actually implement and run -- against parameters that were previously thought to have cryptographic security! Indeed this has already had some (limited) impact on practitioners in the research community. For example, many of the pairing-based cryptography libraries I work with ship with parameters that are now deemed to be too risky thanks to these new attacks. However -- and this is key -- these are research libraries. To my knowledge, none of these fields is actually being used in deployment, let alone standardized cryptography. In other words, this is the kind of result that should receive (and has received!) lots of attention from cryptographers. But not necessarily from people who use cryptography. And here's why. You see, while the Joux and Barbulescu et al. algorithms really are efficient, they only work in fields with very specific properties. Namely, the fields must have small characteristic. Indeed, this feature of the field is critical to certain key steps of the algorithm. Take this property away and you still get some advances over the previous state of the art, but the advances are decidedly more theoretical. Which brings us to the payoff: all of the fields we use to implement most cryptography -- things like (non-elliptic-curve) DSA, Diffie-Hellman, and even the fields we use to implement NIST standard elliptic curves -- are prime fields and hence don't have the necessary properties to make the Joux results meaningful. Hence these attacks don't seem to apply. Moreover there's really no good reason to believe that they will anytime soon. The BlackHat presentation Which brings us to the RSSp BlackHat presentation. The overall premise of RSSp's presentation is that advances happen rapidly. It's not unprecedented for theoretical attacks in the literature to rapidly morph into real things that keep security engineers up at night. They also point out that attacks on the DLP have closely tracked attacks on factoring, both in the classical and the quantum world. (Ok, they don't say the last part but it's also true.) RSSp also correctly imply that we should be switching away from cryptosystems that rely on the hardness of the (field-based) discrete logarithm problem, and should instead be moving to cryptosystems based on the elliptic curve discrete logarithm problem (ECDLP).* This is because none of the efficient attacks on DLP -- including Joux's algorithms -- seem to apply in the (standardized) EC setting. Lastly, they correctly point out that cryptosystems based on factoring and (field-based) Discrete Logarithms are already being deprecated by organizations like NIST for a variety of good -- though not panic-related -- reasons. Mostly this is because our current pre-Joux algorithms against those settings have made it too costly to get long-term (256-bit) security; you just need enormous keys. This was the case before Joux came along, and it's still the case now. The last point RSSp make is also absolutely correct: we should be switching to elliptic curve cryptography (ECC) as soon as possible, in part just so people can start using high-security cryptosystems without paying performance and bandwidth through the nose for the privilege. This isn't totally academic, since -- as Thomas Ptacek reminds me -- we're getting close to the death of 1024-bit keys. If your adversary is the NSA, anyway. (It also doesn't hurt that getting more people on this bandwagon will reduce the number of people rolling their own RSA implementation.) So should we stock up on canned goods and move to Vermont? Vermont is lovely. But you shouldn't move there because of this presentation. In fact this is hardly the first time we've seen a major breakthrough against an important cryptographic problem. In the 90s it was fast number field sieving against factoring-based systems and slightly later, things like the MOV attack on the ECDLP. In both cases, there was a small degree of panic, but ultimately a pretty mild result: cryptographers carefully examined the attack and chose new parameters that made it impractical. Then everyone went back to business. In this case it looks like we've already got a set of parameters that keep us safe, so it's even more unlikely -- that except for a few researchers doing what researchers do -- any of us will have to think about this in three years or five or even ten. And by the way, you should not believe this because I say so -- that would be foolish. You should believe it because the people who work in this area also don't seem to think it's an issue. If you doubt this, go to CRYPTO this week look for people running around with their hair on fire. The number should be barely higher than usual. What would we do if there was a real cryptpocalypse? Right! If we're going to gin up a cryptpocalypse let's have a real one. What if in 2015, Joux and his co-authors publish a new algorithm that efficiently solves the DLP in prime fields and at realistic key sizes, and moreover has a factoring analog that breaks RSA? Well, this would certainly be very bad for everything we've encrypted in the past, but at least we'd have an immediate solution: a rapid transition to elliptic curve crypto. Whew! But this is not much fun: like watching an alien invasion movie where the aliens are allergic to water. So let's go way out on a limb and imagine that in 2017, after everyone has piled into ECC, Joux et al. and a team from the University of Waterloo team up to publish a revolutionary new attack that reduces ECDLP to roughly the hardness of field-based DLP. What would happen then? Well, this would be really bad. Let me reiterate that there's a reason we like our current batch of public-key cryptosystems -- EC, field-based and factoring-based systems. They're relatively easy to understand, they've all been studied quite a bit. But most importantly: they're really efficient. Once you leave this domain you enter a region that the maps label with 'here be dragons'. Not because this space is empty. It's just that there are relatively few efficient schemes that have received anywhere near the level of study that our beloved ones have. Probably the oldest and most familiar of the alternative encryption schemes is the McEliece cryptosystem, which was developed way back in 1978 (that's one year after RSA, in case you're keeping score at home). McEliece and its modern variants are based on problems in algebraic coding theory: they depend for security on the hardness of decoding general codes, as well as some assumptions about the specific code used. McEliece is surprisingly fast and (so far as we know) quite secure. There's only one major problem: the public keys are big. According to a 2008 analysis by Bernstein, Lange and Peters, achieving security equivalent to a 3072-bit RSA key (aka the '128 bit' symmetric-equivalent security level) requires a stunning 187 kilobyte McEliece public key. Moving up to 256-bit security -- notably hard even for RSA -- takes this to nearly 1MB. Recent improvements may cut that down a bit, but they're still relatively unstudied. Another possibility is to use Lattice-based cryptosystems. While there are several in the research literature, one of the most studied is the NTRU cryptosystem. I won't confess to caring much about NTRU, except to note that it's relatively well-studied by the standards of such alternative schemes and even shows up in some standards. Unfortunately that doesn't mean everyone loves it. The inventors also hold a patent on it. Lastly, for signatures at least we can always fall back on old standbys such as hash based signatures, which should hold us as long as Joan Daemen's team can think up new hash functions. Conclusion We live in frightening times and yes, it's always tempting to peek under the bed and imagine scary monsters. In practice, the reality is probably a bit more mundane. As much as we love to read stories of solitary mathematicians making revolutionary leaps in their unlit apartment, this is rarely how things go. Even the most significant advances are usually telegraphed via a series of public, widely-read research papers. In other words: when RSA and DSA really are in danger you'll know about it. Just look for a bunch of cryptographers running around with their hair on fire. Notes: * By 'based on' I don't mean that these cryptosystems necessarily reduce to the ECDLP, but rather that their security depends upon the hardness of the ECDLP.

[matthewdgreen]

TweetNaCl

About a year ago I got into a discussion on Twitter with a couple of other cryptographers. The subject: why do so many software developers use lazy cryptography? The instigation for this discussion was actually a piece of malware -- a popular, widespread botnet that forgot to use digital signatures to sign its control messages. Though I know it's wrong to complain about broken malware, at the same time: these idiots had money on the line! If they couldn't bother to properly secure their software, how can we possibly expect, say, Evernote to get it right? And indeed, the more you look at software, the more you realize this problem cuts across all types of software development. People suddenly find themselves in a position where they could really use strong cryptography (be it ciphers, signatures, collision-resistant hash functions) but instead of buckling down and doing it right, the developers inevitably opt for something terrible. Terrible can mean a lot of things in this context. Mostly it means using no crypto at all. Sometimes it's grabbing an RC4 implementation off of Wikipedia. Or copying something from Applied Cryptography. Or in a few borderline cases, grabbing the MS Crypto API and thus getting stuck with a basket of legacy algorithms thanks to ancient Windows XP compatibility issues. Anyway, the problem -- it seemed to us at the time -- wasn't just a lack of knowledge, or even  an absence of good crypto libraries. Rather, the problem was that you had to use libraries. If your developer has hit the point where s/he's willing to copy and paste RC4 from Wikipedia, you're already in a kind of Fifth Dimension of laziness. Nobody's going to pull in NaCl or OpenSSL just to encrypt one little blob of text. The output of all this thinking was a grand vision. If we couldn't bring the developers to the crypto, we would bring the crypto to the developers. Specifically, we'd develop an easy to use crypto library small enough that you could copy and paste it right into your code. Since we were already using Twitter, we had a metric for complexity right there: the entire library would have to fit in a small number of Tweets. Jean-Philippe Aumasson (developer of the SHA3 finalist BLAKE) even laid the cornerstone by developing TweetCipher, an entirely new authenticated cipher that fits in about six Tweets. It was an exciting time. We dreamed big! We made big plans! Then -- this being Twitter -- we got distracted by something shiny and forgot all about it. Fortunately others have risen to carry on our great work. Tonight marks the publication of TweetNaCl, a re-implementation of the NaCl crypto library that fits in exactly 100 Tweets. TweetNaCl is brought to you by the same people who wrote NaCl, which means that it's probably quite good. More to the point, it's actually compatible with NaCl, which means it uses standard and well-vetted algorithms. (Here's the code in indented, non-Tweet form.) Would I recommend you use TweetNaCl? Well, no. I'd recommend you use the real NaCl. But if you do find yourself with a crypto problem, and it looks like you're just about to copy code from Wikipedia.... Then maybe TweetNaCl could be just the thing.