CurveCP: Usable security for the Internet

Integrity ("the truth and nothing but the truth") means that all of the data that Bob thinks Alice sent was, in fact, sent to Bob by Alice, not by an attacker.

Availability ("the truth, the whole truth, and nothing but the truth") means that the data that Bob thinks Alice sent is exactly the data that Alice actually sent to Bob: nothing more and nothing less.

For example, an attacker can abort an SSH connection or an HTTPS connection by forging a single TCP Reset packet. The user sees an error message such as "Connection closed by remote host" or "Connection reset by peer." The user isn't receiving bad data from the attacker, but also isn't receiving good data from the legitimate server. This is not a violation of integrity but it is a violation of availability.

As another example, PGP-encrypting and PGP-signing an email message protects confidentiality and integrity: an attacker who steals the email message won't understand it and can't replace it with a different message. But PGP does nothing to protect availability: the email has silently disappeared! Retroactively checking integrity can't restore availability.

The problem, part 2: availability is quantitative

Alice and Bob can communicate through a completely hostile network, filled with billions of attack computers, and still be assured of the confidentiality and integrity of their data. Modern cryptographic techniques reach levels of confidentiality and integrity that are infeasible to break.

The same is not true for availability. For example, a large botnet sending a flood of packets will overwhelm the network between Alice and Bob, preventing communication between Alice and Bob; or a malicious ISP can simply refuse to deliver packets from Alice to Bob; or an attacker with physical access to the network can cut a cable. These attacks do not violate confidentiality or integrity, but they do violate availability.

Internet designers can nevertheless strive to improve availability by increasing the cost of denying service and decreasing the amount of communication affected by denial of service. CurveCP takes several steps in this direction.

Beware that there are also serious denial-of-service problems in many other layers of Internet communication, including the physical layer (especially 802.11) and the routing layer (BGP). CurveCP eliminates several denial-of-service problems in the transport layer (TCP), but much more work has to be done.

Unauthenticated packets

Let's look at Bob copying a tiny file through SSH. Measurements show that SSH uses a total of 40 packets back and forth to set up the connection and copy the file.

An attacker eavesdropping on the network watches Bob set up the connection. After (say) 20 packets the attacker forges a TCP Reset packet, or a regular TCP packet containing bogus data. Bob's connection dies. Bob has not yet received any of the legitimate data. If Bob tries again, the attacker breaks that connection too. The attacker is sending only a tiny fraction as much data as Bob is sending, and is still preventing Bob from communicating.

CurveCP is different. CurveCP authenticates and verifies each packet. If a bogus packet arrives, CurveCP simply discards the packet and waits for the legitimate packet.

An attacker can, at somewhat higher cost, prevent the legitimate packet from being delivered. But CurveCP handles this in the same way as other network failures: it recognizes that data is missing and retransmits the data. To stop communication the attacker has to stop essentially all of the legitimate packets; this is considerably more expensive for the attacker than forging an occasional packet, so the number of victims is reduced.

Predictable retransmission times

An attacker who watches the client send a few packets in a typical TCP connection can easily predict when the client will send its next packet. The attacker can stop that packet by briefly flooding the network at that moment. The attacker can also predict when TCP will try retransmitting the packet, and can stop that retransmission with another carefully timed flood. This is less expensive than flooding the network continuously.

CurveCP adds some randomness to its packet-transmission schedule. This randomness gives each packet a chance of fitting through the holes in any part-time flood pattern chosen by the attacker.

Blind amplification

Some protocols allow attackers anywhere on the Internet to generate a packet that will trigger a much larger outgoing packet from the server to a victim address selected by the attacker. The issue here isn't the availability of that protocol; the issue is that the protocol is amplifying the attacker's resources, damaging availability for the rest of the Internet. The worst offender at the moment is DNSSEC, which has set up a remote-controlled machine-gun pool containing more than 2000 servers with amplification factors between 30 and 95 and with an overall outgoing attack capacity estimated to be close to 50 gigabits per second.

With CurveCP, the first incoming packet from the client is padded so that it is as large as the outgoing packet from the server. If this padding is missing, the server won't respond. Subsequent packets from the client need to repeat server cookies and can't be generated blindly.

Non-blind amplification

Heavy amplification sometimes hurts availability even when it's limited to attackers who can see where the packets are going. An attacker who has seized control over a few computers on a network can use those computers to generate a much larger flood back to the same network.

Insisting on all client packets being as large as server packets would double the network bandwidth used by large downloads and still wouldn't eliminate amplification: a server that doesn't receive client responses will retransmit packets. CurveCP nevertheless takes several steps to reduce amplification:

The server doesn't retransmit its first packet, the Cookie packet. The client is responsible for repeating its Hello packet to ask for another Cookie packet.
The ratio between maximum and minimum packet sizes is much smaller in CurveCP than it is in other protocols. CurveCP packets are limited to 1024 bytes of data (plus some overhead). CurveCP never triggers packet fragmentation on standard networks.
CurveCP backs off more quickly than TCP from a congested network, reducing the bandwidth used by retransmissions.

Blind memory consumption

Once upon a time, TCP servers would allocate memory (inside a "TCP control-block table") for each incoming SYN packet. This allowed attackers to trivially fill up memory with blind "SYN flooding": sending a stream of SYN packets.

Phil Karn introduced a cookie exchange as the first step of the Photuris protocol (1994) to prevent the attacker from blindly allocating memory on the server. It was later observed that TCP servers could unilaterally apply the same technique inside TCP, with no changes to TCP clients; these cookies are called "SYN cookies" (1996). The more general technique of "remote storage" eliminates storage on a server in favor of storage inside the network: the server sends data as an encrypted authenticated message to itself via the client.

A CurveCP server does not allocate memory in response to a client's first packet, the Hello packet. Instead it uses remote storage: it sends a Cookie packet containing a cookie that the client cannot understand but must repeat. This packet also contains a client-comprehensible part, the server's short-term public key S' for this connection, used to provide forward secrecy.

A CurveCP server does allocate memory in response to a client's second packet, the Initiate packet, but only if the second packet contains a valid recent cookie from the server. Blind attackers have no way to forge these cookies, and therefore no way to allocate memory on the server.

Unauthenticated memory consumption

Many SSH servers are configured as high-security "public-key-only" servers. These servers do not authorize communication from random clients; they have a list of public keys of authorized clients (in .ssh/authorized_keys), and are willing to talk only to clients sending data authenticated by those public keys.

An attacker can trivially fill up memory on these servers, disabling legitimate communication, by making a series of TCP connections and leaving those connections idle. SYN cookies mean that this attack cannot be carried out blindly, so a server can try to defend itself by imposing separate per-IP-address connection limits, but this defense is trivially subverted by attackers who control many computers or who are eavesdropping on the network.

With CurveCP, the client's Initiate packet contains the client's long-term public key C (encrypted to the server's short-term public key S'), together with a message from C vouching for this connection (a Vouch subpacket). If a CurveCP server is not willing to talk to unauthorized clients, it simply checks C against the list of authorized clients, and drops the packet if C is unauthorized. Unauthorized clients therefore have no way to allocate memory on the server.

Several servers that share a long-term key still use separate minute keys, so they don't understand each other's cookies. An Initiate packet replayed to a different server is quickly discarded.

CPU consumption

Many cryptographic protocols allow unauthenticated attackers to easily overload server CPUs or client CPUs, preventing the CPUs from processing legitimate traffic. Of course, an attacker can achieve the same result by flooding the network; the issue here is that many protocols allow the attacker to overload the CPUs with a much smaller amount of traffic, reducing the attacker's costs and increasing the number of victims.

There are several different mistakes that lead to this type of attack:

Poor choice of cryptographic mechanisms. For example, TCPcrypt overloads the decryption ability of a quad-core 2.66GHz Intel Xeon X5355 client with just 400 packets per second. (TCPcrypt uses 2048-bit RSA, with security level approximately 2^112.) Imagine how much more trouble these computations would cause for a single-core 1GHz Apple iPad!
Poor protocol design. For example, typical implementations of TCP SACK (selective acknowledgments) perform huge computations in response to a single forged attacker packet.
Poor choice of data structures. For example, many servers allow hash flooding: an attacker puts a huge number of entries into a single hash-table bucket, drastically increasing the time required for the server to process those entries.

CurveCP's worst-case server CPU load is very small, and its worst-case client CPU load is very small. CurveCP uses high-speed high-security elliptic-curve cryptography so that a typical CPU can perform public-key operations more quickly than a typical Internet connection can ask for those operations.

Version

This is version 2011.02.09 of the availability.html web page.