Recently in COMSEC Category

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.

Background
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).¹. 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.)

The first step in most Internet communications is name resolution: mapping a text-based hostname (e.g., www.educatedguesswork.org) to a numeric IP address (e.g,, 69.163.249.211). 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 http://www.educatedguesswork.org/ into my browser, what happens is that the browser tries to resolve www.educatedguesswork.org, 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
Host: www.educatedguesswork.org
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, example-domain.heroku.com), 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.

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.

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

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.

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

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 2¹²⁸ 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:

C_i = E(Key, C_i-1 ⊕ M_i)

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 M₀. To encrypt it you compute:

C₀ = E(Key, IV ⊕ M₀).

And then to encrypt M₁ we do:

C₁ = E(Key, C₀ ⊕ M₁).

Now, unless C₀ happens to be the same as IV (which is very unlikely), then even if M₀ = M₁ the input to the two encryption functions will be different and so C₀ ≠ C₁, 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., M_i 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 ⊕ C_i-1 ⊕ P

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

C_i-1 ⊕ P

If P == M_i, then the new ciphertext block will be the same as C_i, 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 www.example.com, the browser makes a request to www.example.com. Importantly, this request includes any cookies you might have for www.example.com. 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:

Client->Server:
        GET /chat HTTP/1.1
        Host: server.example.com
        Upgrade: websocket
        Connection: Upgrade
        Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==
        Origin: http://example.com
        Cookie: 0123456789abcdef
        Sec-WebSocket-Protocol: chat, superchat
        Sec-WebSocket-Version: 13

Server->Client:
        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 https://www.google.com/. He stands up a page with any origin he controls (e.g., http://www.attacker.com/. This page hosts JS that initiates a WebSockets connection to https://www.google.com/. 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 2¹²⁸ 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

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.

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.

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

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.

If everyone loved passwords, then we wouldn't be having an extended discussion about how to get rid of them (incidentally, I was at IIW this week, where the suckiness of passwords is a basic assumption.) So, what's there not to like?

Replayability
The biggest problem with passwords as currently deployed is that they are replayable: in order for Alice to authenticate to her bank, she must provide her bank with her password. The unfortunate consequence of that is that once Alice has authenticated to her bank, then the bank can impersonate her in the future. This doesn't sound so bad, since it's not that useful for the bank to impersonate me to itself, but it has two very bad implications:

• Phishing: If some attacker can convince me that they are my bank, and I give them my password, then they can impersonate me indefinitely, including to my bank. This sort of fraud is a huge issue for banks.
• Unsafe Password Reuse: I'm not (overly) worried about my bank impersonating me to itself, but if I use the same password with two banks, then evil bank A might impersonate me to good bank B. More generally, any time I use the same password at two different sites, then I have to worry about whether I trust both those sites. This is what motivates the advice people usually get to use a different password at each site.

It turns out that there are technical mechanisms for alleviating these issues. The basic principle is to arrange that the merchant never gets to see a replayable password. The technology is complicated and there are a bunch of different mechanisms, but the basic idea is that when Alice establishes her account she gives the site some numeric verifier (V). Then when she comes back, she types her password into her browser which can then prove to the server that she knows V without ever giving the server a copy of V. PwdHash is one example of such a system, as are PAKE-based systems.

Password Proliferation
As Constant observes, it's probably not necessary to worry about Slashdot stealing your password and using it to impersonate you to Kayak, but even people without a lot of commercial relationships tend to have fair number of accounts that they probably don't treat interchangeably. This is particularly difficult when those accounts span a spectrum of security. Consider the following accounts ranked somewhat in increasing order of sensitivity:

• Slashdot
• Twitter
• Gmail
• Amazon
• Bank of America
• Morgan Stanley

I think there is a pretty fair argument that each of these represents a distinct level of security. I don't much care whether people post as me on Slashdot, but I probably do as Twitter. Unlike Twitter, I have actual private information on Gmail but there's actual money involved at Amazon but less than one the table for my bank account, and perhaps less than what I have for my investment portfolio at Morgan Stanley (Note: these providers do not necessarily represent my actual accounts.) Since these exist at different levels of security, they should have different passwords. Moreover, at the highest levels, I most likely want the use different credentials for each site. The end result of this is that I need to have (and likely remember, see below) a whole pile of passwords. This is not something that people like.

Backward Compatibility
Although we know how to build password-based systems that don't reveal the user's password to the relying party, we don't really know how to deploy them securely. The basic problem is that users are already prepared to type their passwords into Web forms that give the password to the server. It's not at all clear how to construct a UI that the user can be sure is safe and thus can type their password into and that also can't be imitated by a malicious Web site. [Technical note: it's easy to build UI that can't be imitated precisely, but the test is whether users will be fooled by bad imitations.] (More about this issue be found here.)

Low Entropy Space
A well-known problem with passwords is that they generally have a very low entropy level, which is to say that your average user draws their password from a relatively small number of passwords. This means, that if I have some oracle which will tell me whether a given candidate password is valid (e.g., a list of encrypted passwords, a server which I can try to log into, etc.) it doesn't take as many attempts as one would like to try the most probable candidate passwords. This is generally called dictionary attack.

The low entropy of the passwords isn't actually quite as bad as it sounds: even though users generally choose terrible passwords, in order to check a candidate password you generally need to try to log into the site in question, which affords the site the ability to do velocity checks and/or limited-try capabilities, such as locking your account after some fixed number of login failures. However, even then you need to use a password with a certain minimum level of security; if I use "ekr" as my username, then this is going to be a lot of attacker's first guess, so I need to get far enough up the entropy curve to make this kind of attack infeasible. That said, low entropy passwords significantly weaken the guarantees of using password diversification technologies like PwdHash, since it's comparatively easy for an attacker who has a verifier to extract the original password.

Unmemorability
This brings us back to the memorability problem. Every new password is something else to remember, and (loosely) the higher the entropy of the passwords, the harder they are to remember.In the limit, if I have a randomly generated password for each site, I'm pretty much going to need some password manager to remember them (either that or a big pile of of post-it notes).¹

One-to-Oneness
Aside from the drawbacks listed above, passwords are inherently a 1-1 mechanism. If I have relationships with five different banks, I need to have established a password—even if it's the same one—with each of them. This sort of entry barrier is a pain for users, but especially for new sites, which have trouble converting visitors to users because they first need to drive them through an annoying registration experience. So, passwords don't really permit any notion of delegating trust to someone else. This is also true in the inverse sense, where I can't easily give you permission to look at my bank balance without giving you permission to make funds transfers, at least not without the bank going to a lot of effort.

A related concern is that passwords don't really have any mechanism for establishing stuff about users outside the system. For instance, when I want to sign up for a credit card, the issuer really wants to know that it's me, but the best they can do is use the (not-really) secrecy of my social security number, address, etc. as a weak password. Once I've signed up with them, a password may be fine, but it's not a useful entry point into the relationship. Similar arguments apply for proving that I'm over 21 or that I live in a given state.

Next Up: What kind of architecture is NSTIC contemplating?
Hopefully the above gives you a sense of the sort of concerns that are motivating something like NSTIC. While formally NSTIC is written as a set of requirements, to my eyes it's more like one of those documents whose authors start with a given solution in mind and write the requirements around that. In the next post in this series I'll try to talk a little bit about that implicit architecture.

^1. Some people use a sort of lame mental hash function to generate related but distinct passwords for each site, but this seems to involve a fair amount of mental overhead.

As I said earlier, a lot of the use cases used to motivate NSTIC are about the inadequacy of existing 1-1 authentication mechanisms. As you can imagine, a huge amount of research has gone into trying to figure out how to build a set of systems which don't have these drawbacks, but the results haven't been entirely satisfactory. The following is an attempt to briefly survey the space and why it's proven so difficult. To be honest, I'm getting a little tired of writing this kind of thing (an older attempt to do this in longer form for the non-Web context can be found here), but it has to get done if you're to make sense of the rest.

It's probably easiest to get a sense of what the problem is by looking at deficiencies in the existing password-type systems on the Web. As you all know, what happens now is that you go to some site—which, if you're lucky, uses HTTPS— and it gives you a form (i.e., text fields on the page) to enter your username and password. This user interface is completely under control of the Web site, and to a first order just looks like any other Web form to the browser¹ You type that stuff in, hit return or click on the submit button, and the browser sends the username and password to the server, which verifies them and either lets you log in or not. [Technical note: each page you fetch/link you click on a site is sort of an independent transaction. The site uses web cookies to string the transactions to gether so you don't have to type your username/password on each page.] There's plenty to hate here, but before we talk about that, it's worth talking about the stuff that's good.

Portability
From the user's perspective one of the most important properties is portability. Say I buy a new machine or I want to use a kiosk somewhere: as long as I remember my password (this is a lot easier if I use the password monkey10 everywhere than if I generate a random 16-character password for each site), then I just sit down, type it in, and I'm good to go. Even if I have a really long password, I can write it down on a piece of paper which will survive the failure of any particular device. This sounds simple, but it's actually a feature that many of the proposed fixes for this problem don't have. To give you just one example, pretty much all the systems that involve you having a long-term client-side public key then require some way to haul that key around. There have been a lot of proposed answers to this (USB tokens, smartphones, etc.) but none of them have come close to taking off.

Backward Compatibility
Say you've just invented a really good remote authentication technique. What now? Well, if it involves modifying the client, then you've got a real problem since Web browsers turn over comparatively slowly (10% of the net is still running IE 6). So, even if you manage to convince all the browser manufacturers to put your system in, you're looking at years before you can count on everyone being able to authenticate with it, and hence before you can use it exclusively. Similar reasoning applies when you need to modify the server, since any new mechanism on the client is useless without server support. The only lowest common denominator mechanism is passwords through Web forms, which is why so many new authentication systems have been structured as enhancements to that basic mechanism, either on the server side (e.g., if you don't recognize this image, don't proceed) or on the client side (e.g., PwdHash) so that they can be deployed unilaterally.

Site Control of Look and Feel
Passwords in web forms aren't the only authentication mechanism that was intended when the Web was first designed. Indeed, HTTP supports not one but two password-based authentication mechanisms, "Basic" (i.e., passwords in the clear in the HTTP header) and "Digest" (i.e., challenge response in the HTTP header). Neither of these sees much usage, most likely due to the hideous user interface they typically have, which involves the browser bringing up a modal or semi-modal dialog as you first go to the page (generally before you see anything on the page). It turns out that this is not what site operators want, which is instead to control the UI experience, including offering you first-time registration without an annoying dialog box, password recovery, branding, etc. In other words, they want to brand it, and aren't really interested in authentication mechanisms which don't offer that ability.

Next Up: What's bad about passwords?
While passwords have some useful features, if they were really great then we wouldn't be having this discussion. Next, I'll talk about some of the obvious drawbacks, but as you're reading that you should remember that while annoying none of them have been severe enough to push us over the edge into actually discarding passwords for most applications.

^1. The exception here is that there is a special indicator that tells the browser that the password field should display dots or stars or whatever instead of your real password.