Recently in COMSEC Category


July 16, 2012

One of the most common responses to the Rizzo/Duong "BEAST" attack was why not just deploy TLS 1.1. See, for instance, this incredibly long Bugzilla bug about TLS 1.1 in Network Security Services (NSS), the SSL/TLS stack used by both Chrome and Firefox. Unfortunately, while TLS 1.1 deployment is a good idea in and of itself, it turns out not to be a very useful defense against this particular attack. The problem isn't that servers don't support TLS 1.1 (though most still don't) but rather that the attacker can force a client and server which both implement TLS 1.1 to negotiate TLS 1.0 (which is vulnerable).

Background: Protocol Negotiation and Downgrade Attacks
Say we are designing a new protocol to remotely control toasters, the Toaster Control Protocol (TCP). TCP has a client controller, a Toaster Control Equipment (TCE), and a device responsible for toasting the bread, or Toaster Heading Equipment (THE). We'll start by developing TCP 1.0, but we expect that as time goes on we'll want to add new features and eventually we'll want to deploy TCP 2.0. So, for instance, maybe TCP 1.0 will only support toasters up to two slots, but TCP 2.0 will add toaster ovens (as has been widely observed, TCP 3.0 will allow you to send and receive e-mail). We may also change the protocol encoding between versions, so TCP 1.0 could have an ASCII representation whereas TCP 2.0 added a binary encoding to save bits on the wire. For obvious reasons, each version doesn't roll out all at once, so I might want TCP 2.0 TCE to talk to my TCP 1.0 THE. Obviously, that communication will be TCP 1.0, but if I later add a TCP 2.0 toaster oven, I want that to communicate with my TCE using TCP 2.0.

One traditional way to address this problem is to have some sort of initial handshake in which each side advertises its capabilities and they converge on a common version (typically the most recent common version). So, for instance, my TCE would say "I speak 2.0" but if the says "I only speak 1.0" then you end up with 1.0. On the other hand if the TCE advertises 2.0 and the THE speaks 2.0, then you end up with 2.0. As in:

TCE TCE THE THE Hello, I speak versions 1.0, 2.0 Let's do 2.0 Version 2.0 traffic...

Another common approach is to have individual feature negotiation rather than version numbers. For instance, the TCE might say "do you know how to make grilled cheese" and the THE would say "yes" or "no". In that case, you can roll out individual features rather than have a big version number jump. Sometimes, systems will have both types of negotiation, with the version number indicating a pile of features that go together and also being able to negotiate individual features. TLS is actually one such protocol, though the features are called "extensions" (not an uncommon name for this). So you get something like:

TCE TCE THE THE Hello, I do "toaster oven", "grilled cheese", "bagels" I can do "bagels" OK, let's toast some bagels

For non-security protocol, or rather ones where you don't need to worry about attackers, or rather those where you don't think you need to worry about attackers, this kind of approach mostly works pretty well, though there's always the risk that someone will screw up their side of the negotiation. With protocols that are security relevant, however, things are a little different. Let's say that in TCP 2.0 we decide to add encryption. So the negotiation looks pretty much the same as before:

TCE TCE THE THE Hello, I speak versions 1.0, 2.0 Let's do 2.0 Encrypted traffic

But since we're talking security we need to assume someone might be attacking us, and in particular they might be tampering with the traffic, like so:

TCE TCE Attacker Attacker THE THE Hello, I speak versions 1.0, 2.0 Hello, I speak version 1.0 Let's do 1.0 Unencrypted traffic

This is what's called a downgrade attack or a bid-down attack. Even though in principle both sides could do version 2.0 (and an encrypted channel), the attacker has forced them down to 1.0 (and a clear channel). Similar attacks can be mounted against negotiation of cryptographic features. Consider, for instance, the case where we are negotiating cryptographic algorithms and each side supports both AES (a strong algorithm) and DES (a weak algorithm), and the attacker forces both sides down to DES:

TCE TCE Attacker Attacker THE THE I can do AES, DES I can do DES OK, let's do DES Traffic encrypted with DES

There are two basic defenses against this kind of downgrade attack. The first is for sides to remember the other side's capabilities and complain if those expectations are violated. So, for instance, the first time that the TCE and THE communicate, the TCE notices that the THE can do TCP 2.0 and from then on it refuses to do TCP 1.0. Obviously, an attacker can downgrade you on the first communication, but if you ever get a communication without the attacker in the way, then you are immune from attack thereafter (at least until both sides upgrade again). This isn't a fantastic defense for a number of reasons, but it's more or less the best you can do in the non-cryptographic setting. In the setting where you are building a security protocol, however, there's a better solution. Most association-oriented security protocols (SSL/TLS, IPsec, etc.) have a handshake phase where they do version/feature negotiation and key establishment, followed by a data transfer phase where the actual communications happen. In most such protocols, the handshake phase includes an integrity check over the handshake messages. So, for instance, in SSL/TLS, the Finished messages include a Message Authentication Code (MAC) computed over the handshake and keyed with the exchanged master secret:

Client Client Server Server ClientHello ServerHello, Certificate, ServerHelloDone ClientKeyExchange, ChangeCipherSpec, Finished ChangeCipherSpec, Finished

Any tampering with any of the handshake values causes the handshake to fail. This makes downgrade attacks more difficult: as long as the weakest share key exchange protocol and the weakest shared MAC are sufficiently strong (both of these things are true for TLS), then pretty much everything else can be negotiated safely, including features and version numbers. [Technical note: SSL version 2 didn't have anti-downgrade defenses and so there's some other anti-downgrade mechanisms in SSL/TLS as well.] This is why it's so important to establish a baseline level of cryptographic security in the first level of the protocol, so you can prevent downgrade attack to the nonsecure version.

Attacks on TLS 1.1 Negotiation
Based on what I said above, it would seem that rolling out TLS 1.1 securely would be no problem. And if everything was perfect, then that would indeed be true. Unfortunately, everything is not perfect. In order for version negotiation to work properly, a version X implementation needs to accept offers of version Y > X (although of course it will negotiate version X). However, some nontrivial number of TLS servers and/or intermediaries (on the order of 1%) will not complete the TLS handshake if TLS 1.1 is offered (I don't mean they negotiate 1.0 but instead an error is observed). There are similar problems (though less extensive with TLS extensions and offering TLS 1.0 as opposed to SSLv3).

No browser wants to break on 1% of the sites in the world, so instead when some browser clients (at least Chrome and Firefox) encounter a server which throws some error with a modern ClientHello, they seamlessly fall back to older versions. I.e., something like this (the exact details of the fallback order depend on the browser):

Client Client Server Server ClientHello (TLS 1.0) TCP FIN ClientHello (SSLv3) ClientKeyExchange, ChangeCipherSpec, Finished ChangeCipherSpec, Finished

It seems very likely that browsers will continue this behavior for negotiating TLS 1.1 and/or 1.2. Here's the problem: this fallback happens outside of the ordinary TLS version negotiation machinery, so it's not protected by any of the cryptographic checks designed to prevent downgrade attack. Any attacker can forge a TCP FIN or RST, thus forcing clients back to SSLv3, TLS 1.0, or whatever the lowest version they support is. The attack looks like this:

Client Client Attacker Attacker Server Server ClientHello (TLS 1.0) TCP FIN ClientHello (SSLv3) ClientKeyExchange, ChangeCipherSpec, Finished ChangeCipherSpec, Finished

The underlying problem here is that the various extension mechanisms for TLS weren't completely tested (or in some cases, specified; extensions in particular weren't part of SSLv3), and so the browsers have to fall back on ad hoc feature/version negotiation mechanisms. Unfortunately, those mechanisms, unlike the official mechanisms, aren't secure against downgrade attack.1

There is, however, one SSL/TLS negotiation mechanism that is extremely reliable: cipher suite negotiation. In TLS, each cipher suite is rendered as a 16-bit number: the client offers a pile of cipher suites and the server selects the one it likes. Because new cipher suites are introduced fairly regularly, and ignoring unknown suites is so easy, this mechanism has gotten a lot of testing, and it works pretty well, even through nearly all intermediaries. The result is that if you really need to have downgrade attack resistance, you need to put something in the cipher suites field. This is the idea behind the Signaling Cipher Suite Value used by the TLS Renegotiation Indication Extension [RFC 5746]. Recently, there have been several proposals that are intended to indicate TLS 1.1 and/or extension support in the cipher suite field. The idea here is to allow detection of version rollback attacks. Once you can detect version rollback, then you can use the ordinary handshake anti-tampering mechanisms to detect removal of extensions.2

The bad news about these mechanisms is that they require upgrading the server to detect the new cipher suite. On the other hand, they can be incrementally deployed. (Yngve Pettersen has a client-side only proposal which leverages the RI SCSV to a similar end, but relies on the assumption that any server which does RI is modern enough to handle extensions properly).

What's the lesson here? Minimally, this kind of negotiation facility needs to be clearly specified from the start and then extensively tested (and hopefully exercised as soon as possible). Once you've got a significant installed base of noncompliant implementations, it gets very difficult to distinguish a noncompliant peer and a downgrade attack and thus problematic to refuse to connect to apparently noncompliant peers.

1 Note that this isn't always a big deal. Consider, for instance, the TLS Server Name Indication message, which allows a server to host multiple HTTPS sites on the same IP. The attacker could force an SNI downgrade, but this will generally just cause a connection failure, which they could have easily have done by forging an RST for every connection. Downgrade attacks are mostly an issue when the attacker is forcing you to a weaker security posture, rather than just breaking stuff.


February 11, 2012

Cryptography is great, but it's not so great if you get arrested and forced to give up your cryptographic keys. Obviously, you could claim that you've forgotten it (remember that you need a really long key to thwart exhaustive search attacks, so this isn't entirely implausible.) However, since you also need to regularly be able to decrypt your data, this means you need to be able remember your password, so it's not entirely plausible either, which means that you might end up sitting in jail for a long time due to a contempt citation. This general problem has been floating around the cryptographic community for a long term, where it's usually referred to as "rubber hose cryptanalysis", with the idea being that the attacker will torture you (i.e., beat you with a rubber hose) until you give up the key. This xkcd comic sums up the problem. Being technical people, there's been a lot of work on technical solutions, none of which are really fantastic. (see the Wikipedia deniable encryption page for one summary).

Threat model
As usual, it's important to think about the threat model, which in this case is more complicated than it initially seems. We assume that you have some encrypted data and that the attacker has a copy of that data and of the encryption software you have used. All they lack is the key. The attacker insists you hand over the key and has some mechanism for punishing you if you don't comply. Moreover, we need to assume that the attacker isn't a sadist, so as long as there's no point in punishing you further they won't. It's this last point that is the key to all the technical approaches I know of, namely convincing the attacker that they are unlikely to learn anything more by punishing you further, so they might as well stop. Of course, how true that assumption is probably depends on the precise nature of the proceedings and how much it costs the attacker to keep inflicting punishment on you. If you're being waterboarded in Guantanamo, the cost is probably pretty low, so you probably need to be pretty convincing.

Technical Approaches
Roughly speaking, there seem to be two strategies for dealing with the threat of being legally obliged to give up your cryptographic keys:

  • Apparent Compliance/Deniable Encryption.
  • Verifiable Destruction

Apparent Compliance/Deniable Encryption
The idea behind an apparent compliance strategy is that you pretend to give up your encryption key, but instead you give up another key that decrypts the message to an innocuous ciphertext. More generally, you want a cryptographic scheme which produces a given ciphertext C which maps onto a series of plaintexts M_1, M_2, ... M_n via a set of keys K_1, K_2, ... K_n. Assume for the moment that only M_n is and M_1, ... M_n-1 are either fake or real (but convincing) non-sensitive data. So, when you are captured, you reveal K_1 and claim that you've decrypted the data. If really pressed, you reveal K_2 and so on.

The reason that this is supposed to work is that the attacker is assumed to not know n. However, since they have a copy of your software, they presumably know that it's multilevel capable, so they know that there may be more than one key. They just don't know if you've given them the last key. All the difficult cryptographic problems are about avoiding revealing n. There are fancy cryptographic ways to do this (the original paper on this is by Canetti, Dwork, Naor, and Ostrovsky), but consider one simple construction. Take each message M_i and encrypt it with K_i to form C_i and then concatenate all the results to form C. The decryption procedure given a single key is to decrypt each of the sub-ciphertexts in turn and discard any which don't decrypt correctly (assume there is some simple integrity check.) Obviously, if you have a scheme this trivial, then it's easy for an attacker to see how many keys there are just by insisting you provide keys for all the data, so you also pad C with a bunch of random-appearing data which you really can't decrypt at all, which in theory creates plausible deniability. This is approximately what TrueCrypt does):

Until decrypted, a TrueCrypt partition/device appears to consist of nothing more than random data (it does not contain any kind of "signature"). Therefore, it should be impossible to prove that a partition or a device is a TrueCrypt volume or that it has been encrypted (provided that the security requirements and precautions listed in the chapter Security Requirements and Precautions are followed). A possible plausible explanation for the existence of a partition/device containing solely random data is that you have wiped (securely erased) the content of the partition/device using one of the tools that erase data by overwriting it with random data (in fact, TrueCrypt can be used to securely erase a partition/device too, by creating an empty encrypted partition/device-hosted volume within it).

How well this works goes back to your threat model. The attacker knows there is some chance that you haven't revealed all the keys and maybe if they punish you further you will give them up. So, whether you continue to get punished depends on their cost/benefit calculations, which may be fairly unfavorable to you. The problem is worse yet if the attacker has any way of determining what correct data looks like. For instance, in one of the early US court cases on this, In re Boucher, customs agents had seen (or at least claimed to had seen) child pornography on the defendant's hard drive and so would presumably have known a valid decryption from an invalid one. Basically, in any setting where the attacker has a good idea of what they are looking for and/or can check the correctness of what you give them, a deniable encryption scheme doesn't work very well, since the whole scheme relies on uncertainty about when you have actually given up the last key.

Verifiable Destruction
An alternative approach that doesn't rely on this kind of ambiguity is to be genuinely unable to encrypt the data and to have some way of demonstrating this to the attacker. Hopefully, a rational attacker won't continue to punish you once you've demonstrated that you cannot comply. It's demonstrating part that's the real problem here. Kahn and Schelling famously sum up the problem of how to win at "chicken":

Some teenagers utilize interesting tactics in playing "chicken." The "skillful" player may get into the car quite drunk, throwing whiskey bottles out the window to make it clear to everybody just how drunk he is. He wears dark glasses so that it is obvious that he cannot see much, if anything. As soon as the car reaches high speed, he takes the steering wheel and throws it out the window. If his opponent is watching, he has won. If his opponent is not watching, he has a problem;

Of course, as Allan Schiffman once pointed out to me, the really skillful player keeps a spare steering wheel in his car and throws that out the window. And our problem is similar: demonstrating that you have thrown out the data and/or key and you don't have a spare lying around somewhere.

The technical problem then becomes constructing a system that actually works. There are a huge variety of potential technical options here, but at a high-level, it seems like solutions fall into two broad classes, active and passive. In an active scheme, you actively destroy the key and/or the data. For instance, you could have the key written on a piece of paper which you eat, or there is a thermite charge on your computer which melts it to slag when you press a button. In a passive system, by contrast, no explicit action is required by you, but you have some sort of deadman switch which causes the key/data to be destroyed if you're captured. So, you might store the data in a system like Vanish (although there are real questions about the security of Vanish per se), or you have the key stored offsite with some provider who promises to delete the key if you are arrested or if you don't check in every so often.

I'm skeptical of how well active schemes can be made to work: once it becomes widely known how any given commercial scheme works, attackers will take steps to circumvent it. For instance, if there is some button you press to destroy your data, they might taser you and ask questions later to avoid you pressing it. Maybe someone can convince me otherwise, but this leaves us mostly with passive schemes (or semi-passive schemes as discussed in a bit.) Consider the following strawman scheme:

Your data is encrypted in the usual way, but part of the encryption key is stored offsite in some location inaccessible to the attacker (potentially outside their legal jurisdiction if we're talking about a nation-state type attacker). The encryption key is stored in a hardware security module, and if the key storage provider doesn't hear from you (and you have to prove possession of some key) every week (or two weeks or whatever), they zeroize the HSM, thus destroying your key. It's obviously easy to build a system like this where the encryption software automatically contacts the key storage provider, proves possession, and thus resets their deadman timer, so as long as you use your files every week or so, you're fine.

So, if you're captured, you just need to hold out until the deadman timer expires and then the data really isn't recoverable by you or anyone else. Of course, "not recoverable" isn't the same as "provably not recoverable", since you could have kept a backup copy of the keys somewhere—though the software could be designed in a way that this was inconvenient, thus giving some credibility to the argument that you did not. Moreover, this design is premised on the assumption that there is actually somewhere that you could store your secret data that the attacker couldn't get it from. This may be reasonable if the attacker is the local police, but perhaps less so if the attacker is the US government. And of course any deadman system is hugely brittle: if you forget your key or just don't refresh for a while, your data is gone, which might be somewhat inconvenient.

One thing that people often suggest is to have some sort of limited-try scheme. The idea here is that the encryption system automatically erases the data (and/or a master key) if the wrong password/key is entered enough times. So, if you can just convincingly lie N times and get the attacker to try those keys, then the data is gone. Alternately, you could have a "coercion" key which deletes all the data. It's clear that you can't build anything like this in a software-only system: the attacker will just image the underlying encrypted data and write their own decryption software which doesn't have the destructive feature. You can, however, build such a system using hardware security modules (assume for now that the HSM can't be broken directly.) This is sort of a semi-passive scheme in that you are intentionally destroying the data, but the destruction is produced by the attacker keying in the alleged encryption key.

The big drawback with any verifiable destruction system is that it leaves evidence that you could have complied but didn't; in fact, that's the whole point of the system. But this means that the attacker's countermove is to credibly commit to punishing you for noncompliance after the fact. I don't think this question has ever been faced for crypto, but it has been faced in other evidence-gathering contexts. Consider, for instance, the case of driving under the influence: California requires you to take a breathalyzer or blood test as a condition of driving [*], and refusal carries penalties comparable to those for being convicted of DUI. One could imagine a more general legal regime in which actively or passively allowing your encrypted data to be destroyed once you have been arrested was itself illegal, and with a penalty that was large enough that it would almost never be worth refusing to comply (obviously the situation would be different in extra-legal settings, but the general idea seems transferable.) I'll defer to any lawyers reading this about how practical such a law would actually be.

Bottom Line
Obviously, neither of these classes of solution seems entirely satisfactory from the perspective of someone who is trying to keep their data secret. On the other hand, it's not clear that this is really a problem that admits of a good technical solution.


January 21, 2012

You've of course heard by now that much of the Internet community thinks that SOPA and PIPA are bad, which is why on January 16, Wikipedia shut itself down, Google had a black bar over their logo, etc. This opinion is shared by much of the Internet technical community, and in particular much has been made of the argument made by Crocker et al. that DNSSEC and PIPA are incompatible. A number of the authors of the statement linked above are friends of mine, and I agree with much of what they write in it, but I don't find this particular line of argument that convincing.

As background, DNS has two kinds of resolvers:

  • Authoritative resolvers which host the records for a given domain.
  • Recursive resolvers which are used by end-users for name mapping. Typically they also serve as a cache.

A typical configuration is for end-user machines to use DHCP to get their network configuration data, including IP address and the DNS recursive resolvers to use. Whenever your machine joins a new network, it gets whatever resolver that network is configured for, which is frequently whatever resolver is provided by your ISP. One of the requirements of some iterations of PIPA and SOPA has been that recursive resolvers would have to block resolution of domains designated as bad. Here's the relevant text from PIPA:

(i) IN GENERAL- An operator of a nonauthoritative domain name system server shall take the least burdensome technically feasible and reasonable measures designed to prevent the domain name described in the order from resolving to that domain name's Internet protocol address, except that--
(I) such operator shall not be required--
(aa) other than as directed under this subparagraph, to modify its network, software, systems, or facilities;
(bb) to take any measures with respect to domain name lookups not performed by its own domain name server or domain name system servers located outside the United States; or
(cc) to continue to prevent access to a domain name to which access has been effectively disable by other means; and ...
(ii) TEXT OF NOTICE.-The Attorney General shall prescribe the text of the notice displayed to users or customers of an operator taking an action pursuant to this subparagraph. Such text shall specify that the action is being taken pursuant to a court order obtained by the Attorney General.

This text has been widely interpreted as requiring operators of recursive resolvers to do one of two things:

  • Simply cause the name resolution operation to fail.
  • Redirect the name resolution to the notice specified in (ii).

The question then becomes how one might implement these.

Technical Implementation Mechanisms
Obviously if you can redirect the name, you can cause the resolution to fail by returning a bogus address, so let's look at the redirection case first. Crocker et al. argue that DNSSEC is designed to secure DNS data end-to-end to the user's computer. Thus, any element in the middle which modifies the DNS records to redirect traffic to a specific location will break the signature. Technically, this is absolutely correct. However, it is mitigated by two considerations.

First, the vast majority of client software doesn't do DNSSEC resolution. Instead, if you're resolving some DNSSEC-signed name and the signature is being validated at all it's most likely being validated by some DNSSEC-aware recursive resolver, like the ones Comcast has recently deployed. Such a resolver can easily modify whatever results it is returning and that change will be undetectable to the vast majority of client software (i.e., to any non-DNSSEC software).1. So, at present, a rewriting requirement looks pretty plausible.

Crocker et al. would no doubt tell you that this is a transitional stage and that eventually we'll have end-to-end DNSSEC, so it's a mistake to legislate new requirements that are incompatible with that. If a lot of endpoints start doing DNSSEC validation, then ISPs can't rewrite undetectably. They can still make names fail to resolve, though, via a variety of mechanisms. About this, Crocker et al. write:

Even DNS filtering that did not contemplate redirection would pose security challenges. The only possible DNSSEC-compliant response to a query for a domain that has been ordered to be filtered is for the lookup to fail. It cannot provide a false response pointing to another resource or indicate that the domain does not exist. From an operational standpoint, a resolution failure from a nameserver subject to a court order and from a hacked nameserver would be indistinguishable. Users running secure applications have a need to distinguish between policy-based failures and failures caused, for example, by the presence of an attack or a hostile network, or else downgrade attacks would likely be prolific.[12]


12. If two or more levels of security exist in a system, an attacker will have the ability to force a "downgrade" move from a more secure system function or capability to a less secure function by making it appear as though some party in the transaction doesn't support the higher level of security. Forcing failure of DNSSEC requests is one way to effect this exploit, if the attacked system will then accept forged insecure DNS responses. To prevent downgrade attempts, systems must be able to distinguish between legitimate failure and malicious failure.

I sort of agree with the first part of this, but I don't really agree with the footnote. Much of the problem is that it's generally easy for network-based attackers to generate situations that simulate legitimate errors and/or misconfiguration. Cryptographic authentication actually makes this worse, since there are so many ways to screw up cryptographic protocols. Consider the case where the attacker overwrites the response with a random signature. Naturally the signature is unverifiable, in which case the resolver's only response is to reject the records, as prescribed by the DNSSEC standards. At this point you have effectively blocked resolution of the name. It's true that the resolver knows that something is wrong (though it can't distinguish between attack and misconfiguration), but so what? DNSSEC isn't designed to allow name resolution in the face of DoS attack by in-band active attackers. Recursive resolvers aren't precisely in-band, of course, but the ISP as a whole is in-band, which is one reason people have talked about ISP-level DNS filtering for all traffic, not just filtering at recursive resolvers.

Note that I'm not trying to say here that I think that SOPA and PIPA are good ideas, or that there aren't plenty of techniques for people to use to evade them. I just don't think that it's really the case that you can't simultaneously have DNSSEC and network-based DNS filtering.


1. Technical note: As I understand it, if you're a client resolver who wants to validate signatures itself needs to send the DO flag (to get the recursive resolver to return the DNSSEC records) and the CD flag (to suppress validation by the recursive resolver). This means that the recursive resolver can tell when its safe to rewrite the response without being detected. If DO isn't set, then the client won't be checking signatures. If CD isn't set, then the recursive resolver can claim that the name was unvalidatable and generate whatever error it would have generated in that case (Comcast's deployment seems to generate SERVFAIL for at least some types of misconfiguration.)


December 18, 2011

The first step in most Internet communications is name resolution: mapping a text-based hostname (e.g., to a numeric IP address (e.g,, This mapping is generally done via the Domain Name System (DNS), a global distributed database. The thing you need to know about the security of the DNS is that it doesn't have much: records are transmitted without any cryptographic protection, either for confidentiality or integrity. The official IETF security mechanism, DNSSEC is based on digital signatures and so offers integrity, but not confidentiality, and in an any case has seen extremely limited deployment. Recently, OpenDNS rolled out DNSCrypt, which provides both encrypted and authenticated communications between your machine and a DNSCrypt-enabled resolver such as the one operated by OpenDNS. OpenDNS is based on DJB's DNSCurve and I've talked about comparisons between DNSSEC and DNSCurve before, but what's interesting here is that OpenDNS is really pushing the confidentiality angle:

In the same way the SSL turns HTTP web traffic into HTTPS encrypted Web traffic, DNSCrypt turns regular DNS traffic into encrypted DNS traffic that is secure from eavesdropping and man-in-the-middle attacks. It doesn't require any changes to domain names or how they work, it simply provides a method for securely encrypting communication between our customers and our DNS servers in our data centers. We know that claims alone don't work in the security world, however, so we've opened up the source to our DNSCrypt code base and it's available on GitHub.

DNSCrypt has the potential to be the most impactful advancement in Internet security since SSL, significantly improving every single Internet user's online security and privacy.

Unfortunately, I don't think this argument really holds up under examination. Remember that DNS is mostly used to map names to IP addresses. Once you have the IP address, you need to actually do something with it, and generally that something is to connect to the IP address in question, which tends to leak a lot of the information you encrypted.

Consider the (target) case where we have DNSCrypt between your local stub resolver and some recursive resolver somewhere on the Internet. The class of attackers this protects against is those which have access to traffic on the wire between you and the resolver. Now, if I type into my browser, what happens is that the browser tries to resolve, and what the attacker principally learns is (1) the hostname I am querying for and (2) the IP address(es) that were returned. The next thing that happens, however, is that my browser forms a TCP connection to the target host and sends something like this:

GET / HTTP/1.1
Connection: keep-alive
Cache-Control: max-age=0

Obviously, each IP packet contains the IP address of the target the Host header contains the target host name, so any attacker on the wire learns both. And as this information is generally sent over the same access network as the DNS request, the attacker learns all the information they would have had if they had been able to observe my DNS query. [Technical note: when Tor is configured properly, DNS requests are routed over Tor, rather than over the local network. If that's not true, you have some rather more serious problems to worry about than DNS confidentiality.]

"You idiot," I can hear you saying, "if you wanted confidentiality you should have used SSL/TLS." That's true, of course, but SSL/TLS barely improves the situation. Modern browsers provide the target host name of the server in question in the clear in the TLS handshake using the Server Name Indication (SNI) extension. (You can see if your browser does it here), so the attacker learns exactly the same information whether you are using SSL/TLS or not. Even if your browser doesn't provide SNI, the hostname of the server is generally in the server's certificate. Pretty much the only time that a useful (to the attacker) hostname isn't in the certificate is when there are a lot of hosts hidden behind the same wildcard certificate, such as when your domain is hosted using Heroku's "piggyback SSL". But this kind of certificate sharing only works well if your domain is subordinated behind some master domain (e.g,, which isn't really what you want if you're going to offer a serious service.

This isn't to say that one couldn't design a version of SSL/TLS that didn't leak the target host information quite so aggressively—though it's somewhat harder than it looks—but even if you were to do so, it turns out to be possible to learn a lot about which sites you are visiting via traffic analysis (see, for instance here and here). You could counter this kind of attack as well, of course, but that requires yet more changes to SSL/TLS. This isn't surprising: concealing the target site simply wasn't a design goal for SSL/TLS; everyone just assumed that it would be clear what site you were visiting from the IP address alone (remember that when SSL/TLS was designed, it didn't even support name-based virtual hosting via SNI). I haven't seen much interest in changing this, but unless and until we do, it's hard to see how providing confidentiality for DNS traffic adds much in the way of security.


November 5, 2011

A while ago I promised to write about countermeasures to the Rizzo/Duong BEAST attack that didn't involve using TLS 1.1. For reasons that the rest of this post should make clear, I had to adjust that plan a bit.

To recap, the requirements to mount this attack are a channel that:

  1. Is TLS 1.0 or older.
  2. Uses a block cipher (e.g., DES or AES).
  3. Is controllable by an attacker from a different origin.
  4. Allows the attackers to force the target secret to appear on at a controllable location.
  5. Allows the attacker to observe ciphertext block n and control a subsequent block m with only a small number of uncontrolled bits in between n and m.

I know this last requirement is a bit complicated, so for now just think of it as "observe block n and control the plaintext of n+1", but with an asterisk. It won't really enter into our story much.

So far, there are two publicly known channels that meet this criterion:

  • WebSockets-76 and previous (only relevant on Safari).
  • Java URLConnection

Note that requirements 1 and 2 are about the TLS stack and requirements 2-4 are about the Web application. Requirement 5 is about both. This suggests that there are two main angles for countermeasures: address the TLS stack and address the Web application. Moreover, there are three potential actors here: users, operators of potential victim sites, and implementors.

The TLS Stack
TLS 1.1
First let's dispose of the TLS 1.1 angle. As has been apparent from the beginning, the ultimate fix is to upgrade everyone to TLS 1.1. Unfortunately, the upgrade cycle is really long, especially as many of the popular stacks don't have TLS 1.1 support at all. To make matters worse, due to a number of unfortunate implementation decisions which I'll hopefully get time to write about later, it's likely to be possible for an attacker to force two TLS 1.1 implementations to speak TLS 1.0, making them vulnerable. So, upgrading to TLS 1.1 is basically a non-starter.

The next obvious angle (per requirement 2) is to force the use of RC4, which isn't vulnerable to this attack. This isn't really a general solution for a number of reasons, including that there are also (more theoretical) security concerns about the use of RC4 and there are a number of government and financial applications where AES is required.

The only really credible place to restrict the use of non-RC4 ciphers is the server. The browsers aren't going to turn them off because some sites require it. Users aren't going to turn them off en masse for the usual user laziness reasons (and because some browsers make it difficult or impossible to do). Even if users do restrict their cipher suite choices, Java uses its own SSL/TLS stack, so configuring the cipher suites on the browser doesn't help here. The server, however, can choose RC4 as long as the client supports it and this provides good protection. [Note that TLS's anti-downgrade countermeasures do help here; the server can use RC4 with clients which support both AES and RC4 and the attacker can't force the server to believe that the client supports only AES.] However, as I've said, this isn't really a permanent solution.

Record Splitting
A number of techniques have been suggested to randomize the CBC state. The general form of this is to split each plaintext write (i.e. the unit the attacker is required to provide) into two records, with the first containing less than one cipher block worth of plaintext. So, for instance, each time the user does a write you could send an empty record (zero-length plaintext). Because TLS encrypts the MAC, this means that the first plaintext block is actually the MAC, which the attacker can't predict, thus randomizing the CBC state.

In theory, this should work fine, since TLS doesn't guarantee any particular mapping between plaintext and records (just as TCP does not). However, it turns out that some SSL/TLS servers don't handle this kind of record splitting well (i.e., they assume some mapping) and so this technique causes problems in practice. Client implementors tried a bunch of techniques and ultimately settled on one where the first byte of the plaintext is sent separately in a single record and then the rest is sent in as many records as necessary (what has been called 1/n-1 splitting). [*]. This seems to be mostly compatible, though apparently some servers still choke

if you use Chrome or Firefox you should either have this fix already or get it soon. However, as mentioned above, those browsers aren't vulnerable to attack via WebSockets and Java uses a different stack, so the fix doesn't help with Java. The good news is that Oracle's October 18 Java patch claims to fix the Rizzo/Duong attack and running it under ssldump reveals that they are doing a 1/n-1 split. The bad news is that the version of Java that Apple ships for Lion hasn't been updated, so if you have a Mac you're still vulnerable.

Web-based Threat Vectors
The other angle is to remove the Web-based threat vectors. How feasible this is depends on how many such vectors there are. As I noted above, the only two known ones are WebSockets ≤ 76 and Java. I've heard claims that SilverLight is vulnerable, but Microsoft says otherwise here. This could of course be wrong. It's also of course possible to introduce a new threat vector. For instance, if we were to add an XHR variant that allowed streaming uploads, this combined with CORS would create a new potential vector. So, in the future we all need to adopt one of the TLS-based countermeasures or be really careful about what Web features we add; probably both to be honest.

We also need to subdivide these vectors into two categories: those which the server can protect itself against (WebSockets) and those which it cannot really (Java). To see the difference, consider that before the client is allowed to use WebSockets, the server needs to agree. So, if you have a standard non-WebSockets server, there's no WebSockets threat. By contrast Java allows URLConnections to the server without any agreement, so there's no way for the server to protect itself from a Java threat vector (other than trying to fingerprint the Java SSL/TLS stack and refuse service, which seems kind of impractical.) Obviously, then, the Java vector is more severe, especially since it's present even if the browser has been fixed.

To make matters worse, the previous version of Java is not only vulnerable to the Rizzo/Duong attack, but it also has what's called a "universal CSRF" issue. It's long been known that Java treats two hosts on the same IP address as on the same origin. It turns out that if you manage to be on the same IP address as the victim site (easy if you're a network attacker), then you can inject a Java applet which will do an HTTPS request to the victim site. That request (a) passes cookies to the site and (b) lets you read the response. These are the two elements necessary to mount a CSRF even in the face of the standard CSRF token defenses. (A related issue was fixed a few years ago, but only by suppressing client-side access to the cookie, which is an incomplete fix.) Obviously, this also serves as a vector for the Rizzo/Duong attack, though I don't know if it's the vector they used, since I don't have all the details of their procedure. Adam Barth and I discovered (or rediscovered, perhaps) the problem while trying to figure out how Rizzo and Duong's attack worked and notified Oracle, who fixed it in the most recent Java patch by supressing sending the cookie in this type of request. (Obviously, I put off writing this post to avoid leaking the issue.) The fix in question would also close this particular vector for the Rizzo/Duong attack, even without the 1/n-1 split, though that doesn't mean that this is the one they were using or that there aren't others.

The bottom line, then, is that you should be upgrading Java, or, if you can't do that, disabling it until you can.


October 25, 2011

Threat Level writes about the release of a denial of service tool for SSL/TLS web servers.
The tool, released by a group called The Hackers Choice, exploits a known flaw in the Secure Socket Layer (SSL) protocol by overwhelming the system with secure connection requests, which quickly consume server resources. SSL is what's used by banks, online e-mail providers and others to secure communications between the website and the user.

The flaw exists in the process called SSL renegotiation, which is used in part to verify a user's browser to a remote server. Sites can still use HTTPS without that renegotiation process turned on, but the researchers say many sites have it on by default.

"We are hoping that the fishy security in SSL does not go unnoticed. The industry should step in to fix the problem so that citizens are safe and secure again. SSL is using an aging method of protecting private data which is complex, unnecessary and not fit for the 21st century," said the researchers in a blog post.

The attack still works on servers that don't have SSL renegotiation enabled, the researchers said, though it takes some modifications and some additional attack machines to bring down the system.

In order to understand what's going on, you need to have some background about SSL/TLS. An SSL/TLS connection has two phases:

  • A handshake phase in which the keys are exchanged
  • A data transfer phase in which the actual data is passed back and forth.

For technical cryptographic reasons which aren't relevent here, the handshake phase is generally much more expensive than the data transfer phase (though not as expensive as people generally think). Moreover, the vast majority of the cost is to the server. Thus, if I'm an attacker and you're a server and I can initiate a lot of handshakes to you, I can force you to do a lot of computations. In large enough quantity, then, this is a computation denial of service attack. This is all very well known. What the attack would look like is that I would set up a client or set of clients which would repeatedly connect to your server, do enough of a handshake to force you to incur computational cost, and disconnect.

What's slightly less well-known is that SSL/TLS includes a feature called "renegotiation", in which either side can ask to do a new handshake on an existing connection. Unsurprisingly, the cost of a new handshake is roughly the same as an initial one. [Technical note: not if you're doing resumption but in this case the client wouldn't offer resumption, since he wants to maximize server cost.] So, what this attack would look like is that instead of opening multiple connections, I'd open a single connection and just renegotiate over and over. As I said, this is slightly less well-known, but it's certainly been known that it's a possibility for some time, but most of the analyses I have seen suggested that it wasn't a major improvement from the attacker's perspective.

The Impact of This Attack
What you should be asking at this point is whether a computational DoS attack based on renegotiation is any better for the attacker than a computational DoS attack based on multiple connections. The way we measure this is by the ratio of the work the attacker has to do to the work that the server has to do. I've never seen any actual measurements here (and the THC guys don't present any), but some back of the envelope calculations suggest that the difference is small.

If I want to mount the old, multiple connection attack, I need to incur the following costs:

  1. Do the TCP handshake (3 packets)
  2. Send the SSL/TLS ClientHello (1 packet). This can be a canned message.
  3. Send the SSL/TLS ClientKeyExchange, ChangeCipherSpec, Finished messages (1 packet). These can also be canned.

Note that I don't need to parse any SSL/TLS messages from the server, and I don't need to do any cryptography. I'm just going to send the server junk anyway, so I can (for instance) send the same bogus ClientKeyExchange and Finished every time. The server can't find out that they are bogus until it's done the expensive part [Technical note: the RSA decryption is the expensive operation.] So, roughly speaking, this attack consists of sending a bunch of canned packets in order to force the server to do one RSA decryption.

Now let's look at the "new" single connection attack based on renegotiation. I need to incur the following costs.

  1. Do the TCP handshake (3 packets) [once per connection.]
  2. Send the SSL/TLS ClientHello (1 packet). This can be a canned message.
  3. Receive the server's messages and parse the server's ServerHello to get the ServerRandom (1-3 packets).
  4. Send the SSL/TLS ClientKeyExchange and ChangeCipherSpec messages (1 packet).
  5. Compute the SSL/TLS PRF to generate the traffic keys.
  6. Send a valid Finished message.
  7. Repeat steps 2-7 as necessary.

The advantage of this variant is that I get to amortize the TCP handshake (which is very cheap). The disadvantage is that I can't just use canned packets. I need to do actual cryptographic computations in order to force the server to do an RSA private key decryption. This is just a bunch of hashes, but it's still not free.

Briefly then, we've taken an attack which was previously limited by network bandwidth and slightly reduced the bandwidth (by a factor of about 2 in packets/sec and less than 10% in number of bytes) at the cost of significantly higher computational effort on the attacker's client machines. Depending on the exact characteristics of your attack machines, this might be better or worse, but it's not exactly a huge improvement in any case.

Another factor to consider is the control discipline on the server. Remember that the point of the exercise is to deny service to legitimate users. It's not uncommon for servers to service each SSL/TLS connection in a single thread. If you're attacking a server that does this, and you use a single connection with renegotiation, then you're putting a lot of load on that one thread; a sane thread scheduler will try to give each thread equivalent amounts of CPU, which means that you don't have a lot of impact on other legitimate users; your thread just falls way behind. By contrast, if you use a lot of connections then you get much better crowding out of legitimate users. On the other hand, if you have some anti-DoS device in front of your server, it might be designed to prevent a lot of connections from the same client, in which case the single connection approach would be more effective. Of course, if single-connection attacks become popular, it's trivial to enhance anti-DoS devices to stop them. [Technical note: SSL/TLS content types are in the clear so renegotiation is easily visible.]

Is this a flaw in SSL/TLS?
Zetter and the THC guys characterize this as a flaw in SSL/TLS. Without offering a general defense of SSL/TLS, this seems overstated at best. First, this isn't really a threat that endangers citizens ability to be "safe and secure". Rather, it's a mechanism for bringing down the Web sites they visit. This isn't to say that there aren't problems in SSL/TLS that would lead to compromise of user's data, but this sort of DoS attack doesn't fall into that category.

Second, computational DoS attacks of this type have been known about for a very long time and in general security protocol designers have made a deliberate choice not to attempt to defend against them. Defenses against computational DoS typically fall into two categories:

  • Force users to demonstrate that they are reachable at their claimed IP address. This prevents "blind" attacks where the attacker can send forged packets and thus makes it easier to track down attackers.
  • Try to impose costs on users so that the ratio of attacker work to defender work is more favorable. (There are a variety of schemes of this type but the general term is "client puzzles").

Because SSL/TLS runs over TCP, it gets the first type of defense automatically. [Technical note: Datagram TLS runs over UDP and so Nagendra Modadugu and I explicitly added a reachability proof mechanism to protect against blind attack.] However, SSL/TLS, like most other Internet security protocols, doesn't do anything to push work onto the client. The general reasoning here is that DoS attackers generally use botnets (i.e., other people's compromised computers) to mount their attacks and therefore they have a very large amount of CPU available to them. This makes it very hard to create a puzzle which creates enough of a challenge to attackers to reduce the attack threat without severely impacting people with low computational resources such as those on mobile devices. Obviously, there is a tradeoff here, but my impression of the history of DoS attacks has been that this sort of CPU-based attack isn't that common and so this has been a generally reasonable design decision.

More generally, defending against computational DoS attacks is a really hard problem; you need to be able to serve large numbers of people you don't really have a relationship with, but it's easy for attackers who control large botnets to pretend to be a lot of legitimate users. All the known defenses are about trying to make it easier to distinguish legitimate users from attackers before you've invested a lot of resources in them, but this turns out to be inherently difficult and we don't have any really good solutions.

UPDATE: Fixed a writing error. Thanks to Joe Hall for pointing this out.


September 23, 2011

If you're familiar with network security and haven't been living under a rock you've probably seen the recent coverage of Rizzo and Duong's attack on SSL/TLS implementations. they've demoed the attack and information is starting to trickle out (the news articles above were written prior to release), we can begin evaluate the impact of this work. (See AGL's post on this). Unfortunately, there's no paper publicly available and the live chat during the talk raised more questions than were answered. [in large part due to the inadequacies of trying to ask questions over WebEx chat -- EKR 9/24]

First, the bottom line: Don't Panic. Yes, this is interesting work, no SSL/TLS is not completely broken. In particular, your communications with your bank are quite likely to be fine. In particular, AGL suggests that Chrome is fine.

Background: CBC Encryption

In order to understand what's going on here, you need some background. SSL/TLS can encrypt data with two kinds of ciphers: block ciphers like AES and DES and stream ciphers like RC4. You don't need to worry about stream ciphers for now. This attack only applies to block ciphers. The way that a block cipher works is that it's a keyed mapping from plaintext blocks (typically 128 bits) onto ciphertext blocks of the same size. So, it's like having a huge table with 2128 entries showing each plaintext block M and it's corresponding ciphertext block C. Each key represents a different table. So, we represent encryption as a functin C = E(Key, M) meaning that we compute the encryption function on Key and M and the result is the ciphertext.

The obvious way to use a block cipher is to break up plaintext into 128-bit blocks and encrypt each block separately (this is called electronic codebook (ECB) mode. It should be obvious that if you have two blocks that are the same in the plaintext they are also the same in the ciphertext and so you patterns in the plaintext get reflected in the ciphertext. This is bad. This Wikipedia article has a good visual comparison of just how bad it can be. In order to prevent this, other cipher modes have been developed that break up those patterns. The one used by SSL/TLS (at least prior to TLS 1.2) is called cipher-block chaining (CBC) mode. The way that CBC works is that when you encrypt block i you first XOR in the encryption of block i-1. More formally:

Ci = E(Key, Ci-1 ⊕ Mi)

Obviously, when you go to encrypt the first block, there is no previous block to XOR; in, so the standard practice is to generate a random initialization vector (IV) and use that as if it were the encryption of the previous block. The effect of all this is to break up patterns: consider the first block M0. To encrypt it you compute:

C0 = E(Key, IV ⊕ M0).

And then to encrypt M1 we do:

C1 = E(Key, C0 ⊕ M1).

Now, unless C0 happens to be the same as IV (which is very unlikely), then even if M0 = M1 the input to the two encryption functions will be different and so C0 ≠ C1, thus breaking up the pattern.

How CBC is used in SSL/TLS
The way I've described CBC above is as if you're just encrypting a single data blob (e.g., a file) consisting of a number of blocks. However, SSL/TLS is a channel encryption protocol and so it wants to encrypt not a single file but a series of records. For instance, you might use a single SSL/TLS connection for a series of HTTP requests, each of which is broken up into one or more records which might be sent over the course of seconds to minutes. All the records (in each direction) are encrypted with the same traffic key.

There are two basic ways to use CBC in this kind of environment:

  • Treat each record as if it were independent; generate a new IV and encrypt the record as described above.
  • Treat the records as if they were concatenated into a single large object and just continue the CBC state between records. This means that the IV for record n is the last block (the CBC residue) for record n-1.

SSLv3 and TLS 1.0 chose the second of these options. This seems to have been a mistake, for two reasons. First (and more trivially) it makes it hard to use TLS over any kind of datagram transport (hence DTLS) and second, it turns out that there is a security issue.

The Original Predictable IV Issue
Back in 2004, Moeller [*] observed that it was possible to exploit this behavior under certain circumstances. (the original observation of this style of attack seems to be due to Rogaway [*] and then extended to SSH by Wei Dai.). Imagine that you're an attacker who can convince one side of the SSL/TLS implementation to encrypt some data of your choice. This allows you to learn about other parts of the plaintext, even if you wouldn't ordinarily be allowed to see that plaintext.

Consider the case where we have a connection between Alice and Bob. You observe a record which you know contains Alice's password in block i, i.e., Mi is Alice's password. Say you have a guess for Alice's password: you think it might be P. Now, if you know that the next record will be encrypted with IV X, and you can inject a chosen record, you inject:

X ⊕ Ci-1 ⊕ P

When this gets encrypted, X get XORed in, with the result that the plaintext block fed to the encryption algorithm is:

Ci-1 ⊕ P

If P == Mi, then the new ciphertext block will be the same as Ci, which reveals that your guess is right.

The question then becomes how the attacker would know the next IV to be used. However, because the IV for record j is the CBC residue of record j-1 all the attacker needs to do is observe the traffic on the wire and then make sure that the data they inject is encrypted as the next record, using the previous record's CBC residue as the IV.

While troubling, this isn't that great an attack. First, the attacker needs to be able to somehow mix traffic they control with traffic they don't control and can't see, all over the same SSL/TLS connection. This isn't impossible; for instance it might happen over an SSL-VPN, but it's also not that common. Second, it only lets you guess a whole plaintext block at a time, so even if you're guessing a very low entropy value, it takes a lot of guesses to search the space.

Still, this is a serious enough issue that the IETF felt like it was worth fixing, and the TLS Working Group duly developed TLS 1.1, which changed to the first strategy (called "explicit IV" in the standard). [Technical note: the required defense is actually slightly more complicated because you need to make the TLS-using application commit to the entire plaintext block prior to revealing the IV.] TLS 1.1 was developed in 2006, but deployment has been pretty limited ([*]). We don't know why for sure, but I think the general feeling in the security community is that the threat didn't seem serious enough to motivate upgrading.

The Rizzo/Duong Attack
Rizzo and Duong's paper improves on this attack in two ways:

  1. They have developed a more efficient attack which allows the attacker to guess a single byte at a time rather than having to guess a whole block.
  2. They observe that a specific use of Web technologies (cross-origin requests and in particular Web Sockets) allows the attacker to mix traffic in the fashion described above.

Shifting the Boundary
The improvement in the attack is easy to understand. Imagine that the attacker has some control about the way that data is fitted into blocks. So, consider the case where we want to guess Alice's password, which (without loss of generality) we know is 8 characters long. If the attacker can arrange for the password to be split up in between records so that the first character is in one record with otherwise predictable contents and the next 7 characters are in the next record, then the attacker only needs to guess the first character.

For instance, if the way the username/password protocol works is that you send the string user: alice password: ******** where ******** is the password itself. So, if the attacker can arrange that this is broken up as lice password: * | *******........., then they can guess the first character of the password in isolation. Furthermore, if they know the first character, they can then shift the record boundary by one byte and then guess the next character. The way this attack plays out in practice is that the attacker exhaustively searches the first character, then fixes the first character, and searches the second, and so on.

Exploiting WebSockets
The previous best attacks involved VPNs, but Rizzo and Duong suggest a different vehicle. The basic idea is that the Web is an inherently multi-site environment and it's very common for JavaScript coming from Site A to talk to Site B (for instance, for mashups). To give just one example, if you embed an image on your Web page that comes from, the browser makes a request to Importantly, this request includes any cookies you might have for This capability is the basis for a variety of attacks, including cross-site request forgery (CSRF), and cross-origin requests (i.e., those made by scripts from site A going to site B) are strictly limited in order to limit those attacks.

These restrictions, however, are inconvenient, and so many newer Web technologies are moving to a security model of origin-based consent. The idea here is that when a cross-origin request is made to site B from site A, the browser asks site B whether it's OK from that site, thus allowing site B to selectively allow access only to safe resources. One such technology is Web Sockets, which is designed to allow a client/server pair to start with an HTTP transaction and upgrade it to a transparent (non-HTTP channel) that allows the transmission of arbitrary messages that aren't framed as HTTP messages. The way that WebSockets works is that there is an initial HTTP handshake (including cookies) that allows the client to verify that the server is prepared to do WebSockets. The handshake looks something like this:

        GET /chat HTTP/1.1
        Upgrade: websocket
        Connection: Upgrade
        Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==
        Cookie: 0123456789abcdef
        Sec-WebSocket-Protocol: chat, superchat
        Sec-WebSocket-Version: 13

        HTTP/1.1 101 Switching Protocols
        Upgrade: websocket
        Connection: Upgrade
        Sec-WebSocket-Accept: s3pPLMBiTxaQ9kYGzzhZRbK+xOo=
        Sec-WebSocket-Protocol: chat

After the handshake, client-side JavaScript is allowed to send arbitrary data to the server, though it is wrapped in some framing data.

It should be obvious at this point how one might use WebSockets as a vehicle for Rizzo and Duong's attack. Say the attacker wants to recover the cookie for He stands up a page with any origin he controls (e.g., This page hosts JS that initiates a WebSockets connection to Because WebSockets allows cross-origin requests, he can initiate a HTTPS connection to the target server if the target server allows it (e.g., because it wants to allow mash-ups). Because the URL (/chat above) is provided by the attacker, he can make it arbitrarily long and therefore put the Cookie wherever he wants it with respect to the CBC block boundary. Once he has captured the encrypted block with the cookie, he can then send arbitrary new packets via WebSockets with his appropriately constructed plaintext blocks as described above. There are a few small obstacles to do with the framing, but Rizzo and Duong claim that these can be overcome and those claims seem plausible.

The Impact of Masking
That's the idea anyway. Fortunately, I've omitted one detail: what I've just described is WebSockets draft -76. This version of WebSockets was shipped in some browsers and then largely disabled (for instance here) because of a vunerability published by David Huang, Eric Chen, Adam Barth, Collin Jackson, and myself. The version of WebSockets which the IETF is standardizing incorporates a feature called masking in which the browser generates a random 32-bit mask that gets XORed with the content of the packet prior to transmission (and hence prior to SSL/TLS encryption). The impact of this change is that if an attacker wants to use WebSockets they only have a 2-32 chance of being able to generate the right input to the encryption algorithm to mount the attack. Obviously, this isn't as good as random IVs (which increase the difficulty by a factor of 2128 for AES), but it's a pretty significant barrier nonetheless.

Note that I'm not saying that my co-authors and I knew about this attack or that we pushed for it as a countermeasure. Rather, we were concerned about a different class of attacks in which an attacker was able to control bits on the wire, and masking was intended to deny the attacker that kind of control. However, since similar levels of control are required in order to mount this attack, masking seems to be an effective countermeasure here as well.

As should be clear based on the above discussion I don't think that this is an issue with newer versions of WebSockets (which means recent versions of browsers other than Safari) and of course older browsers don't implement WebSockets at all. And even if you have a browser which is vulnerable, you need to be talking to a target site which actually accepts cross-origin WebSockets requests, which as far as I know is very rare for high-value sites such as financial sites.

Exploiting Java
The demo that Duong and Rizzo showed today used Java to provide the vector for the attack. As I understood their presentation (and note I don't have their papera copy of their paper with full details on how they're using Java but the version that is floating around says URLConnection [-- updated 9/24]) they say they don't need any heightened Java privileges. What's a little confusing here is exactly how they are getting past same-origin issues. In particular, which Java APIs they are using and whether this was expected/known Java behavior with respect to SOP or whether they had found a way around SOP was really unclear. That's important to know, in part because it dictates the right response and also because it tells us whether they've found a threat that extends past HTTPS. In particular, if their is a clear SOP violation (as for instance in this exploit) then you have a serious problem regardless of any crypto magic.

Requirements for a Successful Attack
This post is really long, but the last thing I want to cover is what conditions would be required to mount a succesful attack using this type of technique. As far as I can tell, we need to have a target domain which allows cross-origin requests that:

  1. Contain some user secret (e.g., a cookie) in a predictable location.
  2. Allow scripts from the attacker's origin to tightly control additional data on the same HTTPS connection as the user secret.

It's this mixing of data under control of the attacker and data which should be kept secret from the attacker that constitutes the threat. This is a a very natural thing to do in the Web context; mashing up data from one site with another is something that happens all the time. The Web security model is designed to protect you from that, but the lesson here (once again) is that actually getting that right is somewhat tricky.

I'm actively trying to get more details on how this attack works, so more as I get them. At the moment, my advice would be to disable Java—that would be my advice in any case—and otherwise probably don't get too excited.

Next Up: Countermeasures other than upgrading to TLS 1.1


September 18, 2011

Techcrunch has been writing about a new startup called Bitcasa. Roughly speaking, Bitcasa offloads your storage to a cloud service. They use data deduplication to avoid storing multiple copies of common data. In Techcrunch's original review, they wrote:

When you save a file, Bitcasa writes those 1's and 0's to its server-side infrastructure in the cloud. It doesn't know anything about the file itself, really. It doesn't see the file's title or know its contents. It doesn't know who wrote the file. And because the data is encrypted on the client side, Bitcasa doesn't even know what it's storing.

So if you want to cloud-enable your 80 GB collection of MP3's or a terabyte of movies (acquired mainly through torrenting, naughty you!), go ahead. Even if the RIAA and MPAA came knocking on Bitcasa's doors, subpoenas in hand, all Bitcasa would have is a collection of encrypted bits with no means to decrypt them.

This seems intuitively wrong from an information theory perspective, but it's certainly possible that Bitcasa is using some crypto magic I'm unaware of. Luckily, in this article Bitcasa explains the technology.

OK, so convergent encryption... what happens is when you encrypt data, I have a key and you have a key. And let's say that that these are completely different. Let's say that we both have the exact same file. I encrypt it with my key and you encrypt it with your key. Now the data looks completely different because the encryption keys are different. Well, what happens if you actually derive the key from the data itself? Now we both have the exact same encryption key and we can de-dupe on the server side.

They don't provide a cite, but we're probably talking about a system like that described by Storer et al.. If so, then there's no reason to think it won't work, but the implied security claim above seems over-strong. In particular, as far as I can tell, Bitcasa does in fact learn which user has stored which chunk. Consider what happens when you and I both try to store file X. The encryption is a deterministic function, so we each generate the same n chunks X_1, X_2, ... X_n. When we upload them (or query Bitcasa for whether we need to upload them), Bitcasa learns which chunks I have. When you do the same, Bitcasa learns we have the same file. More generally, the pattern of chunks you have serves as a signature for the files you have; if you have a copy of a given file, you can easily determine whether a given user has stored it on Bitcasa. So, unless I've missed something I don't think that in fact this provides security against attempts by Bitcasa to determine whether a given user is storing one of a given set of contraband files.


August 29, 2011

One of the "poster child" applications for research into privacy-preserving cryptography has been electronic tolling (i.e., for highways and bridges). Tolling is an attractive application for a number of reasons, including:
  • There are some really serious privacy implications to knowing where where your car is, or at least people think there are. (See for instance the IETF's Geographic Location Privacy WG).
  • The kinds of infrastructure that you would need (transponders, receivers at the toll plaza, etc.) to implement are already in place. You would of course need to upgrade them, but it's not like people would find it hard to understand "we're sending you a new E-ZPass transponder. Stick it to your windshield".
  • You can hide most of the complexity in the transponder, so it's not like the users need to know how to execute blind signatures or cut-and-choose protocols.
  • A lot of money changes hands.
Most importantly, the existing situation is stunningly bad, both from a privacy and a security perspective. To take an example, Fastrak transponders are simple RFID tags, so it's trivial to clone someone's transponder as well as to place your own Fastrak readers to track people at locations of your choice. It's clear you could do a lot better than this, even without getting into any fancy cryptography, and with some cleverness, you can do much better. There has been a huge amount of research on privacy-preserving tolling over the years, but the basic idea is always to ensure that people pay tolls when appropriate but also to avoid anyone—including the toll authority—from determining through the protocol when given cars passed a given location. How achievable this goal is depends on the model: it's pretty well understood how to do this when the toll plazas are in fixed locations; it's rather harder to do when you have large expanses of toll roads and you want people to pay by the mile.

Against this background, last Thursday's NYT Article on E-ZPass toll fraud makes sobering reading. Briefly, E-ZPass can operate in a "gateless" mode where you drive through the plaza but there's nothing to stop you if you don't pay. Instead, there are license plate cameras and so if someone doesn't pay you can send them a ticket in the mail. (Note that the transponders aren't that reliable, so in some cases you keep a record of which license plates are registered to have a transponder and just bill people with registered plates but whose transponders didn't register as if the transponder had worked.) In any case, according to this article roughly 2% of people don't pay and the enforcement procedures are proving to be quite problematic. The problem isn't identifying the offender, it's billing them:

The process for trying to catch toll cheats begins with a photograph, automatically taken at the toll plaza, that is used to identify the offending vehicle's license plate number. Using motor vehicle records, the Port Authority then tracks down the vehicle owner and sends a letter indicating that a toll and possibly a fine are due.


"That is one of the great untold secrets for any given agency," Neil Gray, the director of government affairs for the Washington-based International Bridge, Tunnel and Turnpike Association, said about toll cheats. "You'll probably spend more time and money chasing the toll than you will get for the toll."


Then it comes down to how much time and what resources states want to invest to chase down these funds. In Maine, officials are able to suspend the registration of vehicles with unpaid E-ZPass bills; in Delaware, drivers with outstanding toll violations cannot renew their registrations. Jennifer Cohan, director of Delaware's Division of Motor Vehicles, acknowledged that there were harsher measures that could be employed.

"We technically could arrest these folks," Ms. Cohan said, suggesting that it was possible to have a police officer at every toll booth. "But our law enforcement officers are extremely busy."

What lessons does this have for more complicated cryptographic tolling mechanisms? First, the fact that the rate at which non-subscribers go through the toll plaza without paying is so high and that it needs to be enforced with cameras sort of negates concerns about the privacy of the tolling system itself. It doesn't really help to have a privacy-preserving cryptographic tolling protocols if you need cameras everywhere to detect fraud. And since toll plazas tend to be placed at choke points like bridges, tunnels, etc., there's a lot of information leakage. There's been a fair amount of work on tolling that doesn't use fixed toll plazas (e.g., where you pay by mile of road driven) and then uses secret cameras for auditing (see, for instance, Meiklejohn, Mowery, Checkoway, and Shacham's The Phantom Tollbooth) in this year's USENIX Security), but it's not clear how useful these models are. First, you still need a fair amount of surveillance (and hence information leakage) in order to enforce compliance. Second, tolls get collected at choke points not only because it's easy but also because those are the limited resource you want to control access to, so just charging people for miles driven on a large number of roads isn't an adequate substitute. (And of course in the case where you want to charge people for all miles driven, it's easier to just install mileage meters and/or charge a gas tax scaled to your car's expected MPG).

Second, a level of fraud this high suggests that concerns about the technical security of the system are premature. If you have photographic proof of 2% of people passing through the toll plaza and just outright not paying and you can't even manage to punish them and/or collect money from them, then you've got bigger things to worry about than fancy technical attacks. So, for instance, Meiklejohn et al. describe an attack on previous systems in which drivers collude to discover the locations of secret cameras and use that to defraud the tolling authority. It's a clever attack but kind of pointless if it's easier to just not pay entirely and figure you won't get caught.

More generally, I think this represents an argument against a broad variety of privacy-preserving cryptographic mechanisms based on this style of "voluntary" compliance enforced by auditing and punishment. The argument for this strategy goes that it allows you to (mostly) preserve people's privacy because the vast majority of transactions go unexamined while ensuring compliance because people are afraid of being caught if they cheat. The first half of this argument is fine as long as you can design an auditing mechanism which itself isn't too invasive. However, it's the second half of the argument that seems really problematic: if the value to me of cheating is V and the chance of getting caught is α, then the punishment P must be ≥ V/α or I'd be better off cheating and taking the occasional punishment. If either P or &alpha is too small, then the system won't work. So, here we have an instance where this has actually been tried, and the state has the capacity to inflict quite high punishments (including putting you in jail), and it's not working very well.

Many of the settings that people talk about using privacy-preserving cryptography in (e.g., digital payments) have weaker enforcement mechanisms and much more ambiguous evidence of cheating. For instance, the transaction itself might not be that well tied to your real-world identity, making punishment difficult. Moreover, often these protocols are complicated and involve a lot of fancy cryptography, so even if you do get caught you can argue that it was an inadvertant error and so you shouldn't receive the whole punishment. If we can't even make this stuff work in the current simple setting, it seems pretty questionable that it will work in more complicated cases.


May 25, 2011

As I wrote a while back, NSTIC feels like requirements written with a solution already in mind, specifically what's called a "federated identity" system. The basic idea behind a federated identity system is that a person who wants to do stuff on the Internet (i.e., you) will have a relationship with some identity provider (IdP). At minimum, you'll share some set of authentication credentials with the IdP, so that you're able to establish to them that you're sitting at a given computer. Then, when you go to an arbitrary site on the Internet and want to authenticate, that site (called the relying party) can verify your identity via the IdP. What's nice (at least theoretically) about a system like this is that you can just authenticate once to the IdP and then all other authentication transactions are handled more or less seamlessly via the IdP. (This is often called single sign-on (SSO)). What makes the system federated is that there is expected to be more than one IdP and so I might be able to get my identity through the USPS and you get yours through Wells Fargo, but Amazon trusts both so we're both able to get our $0.59 stoneware bowls via Amazon Prime.

This isn't by any means a new idea. In the US your driver's license is issued by your state, but it's accepted as identification by a whole variety of relying parties, not just the state and its agents. It's not just your driver's license, either; you likely have a relationship with multiple IdPs. For instance, I have a driver's license (issued by California) and a passport (issued by the US State Department), plus a variety of more specialized credentials which are arguably used for authentication/authorization, such as credit cards, library cards, etc. That's not really the state of play for Internet transactions, though, with the partial exception of Facebook Connect (discussed below).

Simple SSO
In the simplest case, all the IdP does is attest to the fact that you have an account with them and maybe some weak indication of your identity, such as your claimed display name and an account identifier. There are a variety of systems of this type, such as OpenID, but by far the most popular is Facebook Connect. The way that Facebook Connect works is that you log into Facebook and then when you visit a Facebook Connect relying party, they are able to get your account information from Facebook, though that mostly consists of information you've given Facebook, so there's no real guarantee that for instance the name that Facebook delivers the relying party is your real name.

Even a simple system like this presents technical challenges, especially when it's implemented in the extremely limited Web environment (hopefully more on this in a separate post). First, there's the question of privacy: just because I have an account with IdP X and site Y is a relying party for IdP X doesn't mean that when I visit site Y I want them to be able to identify me. The more widely accepted an IdP is, the more serious this problem becomes; if every site in the world accepts my IdP, then potentially I can be tracked everywhere I visit, both by the IdP and by the relying parties. If we want to avoid creating a universal tracking mechanism (people often call this a supercookie), we need to somehow let users decide whether to authenticate themselves to relying parties via their IdPs. This creates obvious UI challenges, especially because there's plenty of evidence that users get fixated on whatever task they are trying to accomplish and tend to just click through whatever dialogs are required to achieve that objective.

The second challenge is dealing with multiple IdPs: in an environment where there are a lot of different IdPs and different relying parties accept different IdPs, then we need some mechanism to let relying parties discover which IdP (or IdPs) I have an account with. This is actually a little trickier than it sounds to do in a privacy-preserving way because the profile of which IdPs I support can itself be used as a user-specific fingerprint even if none of the IdPs directly discloses my identity to the relying party. Moreover, when I have a pile of different IdPs, I need to somehow select which IdP to authenticate with, which means more UI.

Real-Life Attributes and Minimal Disclosure
Once you get past a system that just carries an identifier—especially one that's unique but not really tied to any form of verifiable identity—life gets more complicated. Consider your driver's license, which typically has your name, address, age, picture, and driver's license number. When I go to a bar to buy a drink, all I need is to demonstrate that I'm over 18, but there's no reason for the bar to know my real name, let alone my address. In general, the more attributes an identity system can prove, the more useful it is, but also the more of a privacy threat it potentially is if any relying party just learns everything about me.

There has been a lot of work on cryptographic systems designed to allow people to prove individual properties to relying parties without revealing information that the relying party doesn't need to see (the term here is "minimal disclosure"), such as Microsoft's U-Prove. The idea here is that you will establish a whole bunch of attributes about yourself to one or more "claims providers". You can individually prove these claims to relying parties without revealing information about other claims. In the best case, even claims providers/IdPs don't get to know which relying parties you are proving claims to or which claims you are proving (e.g., the state wouldn't get to find out that you were proving your age to a bar.)

Making this work requires a lot of cryptography, though at this point that's pretty well understood. However, it also requires user interaction to allow users to determine which claims are to be proven to which relying parties. So, for instance, you would visit a site and it would somehow tell your Web browser which claims it wanted you to prove; your browser would produce some UI to let you agree; once you've agreed, your browser would cooperate with the claims provider to prove those claims to the relying party.1

Putting it Together
Putting the pieces together here, what NSTIC seems to envision is a federated identity system of users, IdPs, claims providers, and relying parties. As a user you'd be able to select your IdP/claims providers and as a relying party you'd be able to decide which of these you trust. The whole system would be glued together with by privacy-preserving cryptographic protocols. In the next post, I'll try to explain some of the challenges of actually building a system like this in the Web environment.

1. It's worth noting that if you don't mind your IdP/claims provider learning who you authenticate to and which claims you prove, then you don't need any crypto magic. This is basically the kind of system Facebook Connect already is.