Cryptographic competitions

Disasters

The trust that users place in secret-key cryptography has been repeatedly and flagrantly violated. Consider the following recent and ongoing examples:

• 2009 Albrecht–Paterson–Watson introduced an attack that, with probability 2^(-18), verifiably recovers 32 bits of OpenSSH-encrypted plaintext at an attacker-selected position. The underlying problem is a flaw in the interaction between the secret-key encryption and secret-key authentication mechanisms used by OpenSSH.
• 2011 Duong–Rizzo demonstrated two-minute recovery of TLS-encrypted cookies, specifically cookies enabling access to a PayPal user account. The core problem, another flaw in the interaction between encryption and authentication, had been pointed out years earlier by Dai, by 2004 Moeller, and by 2006 Bard, and was fixed in TLS 1.1; but almost all HTTPS sites continue to use TLS 1.0.
• 2011 AlFardan–Paterson introduced an efficient attack that recovers full plaintext from the OpenSSL implementation of DTLS, and about 4% of the plaintext from the GnuTLS implementation of DTLS. This attack exploits not only details of the encryption and authentication but also timing information. An emergency OpenSSL upgrade on 4 January 2012 introduced a workaround for this attack; another emergency OpenSSL upgrade on 18 January 2012 fixed a denial-of-service problem that had been introduced by the workaround.
• 2012 Minematsu–Morita–Iwata announced a fast forgery attack against EAXprime, an authenticated-encryption block-cipher mode standardized by ANSI C12.22-2008 for the "Smart Grid" and announced as the subject of a forthcoming NIST standard. "Block-cipher mode" means that EAXprime converts any block cipher, for example AES, into an authenticated cipher; the attack works independently of the choice of cipher.
• 2008 Eisenbarth–Kasper–Moradi–Paar–Salmasizadeh–Shalmani extracted master keys from the popular Keeloq RFID devices, allowing them to surreptitiously observe keys from dozens of yards away and almost instantly build clones of those keys. Previous work had already shown that the Keeloq cipher provided less security than suggested by its 64-bit key size; the master-key computation by Eisenbarth et al. also exploited side-channel information leaked by the Keeloq devices.
• A large fraction of existing 802.11 networks around the world continue to use WEP and are easily broken by the popular aircrack tool. This tool (2007 Tews–Weinmann–Pyshkin, building on previous work by Devine et al.) exploits various weaknesses in the underlying cipher, RC4, and after a few minutes prints out the "secret" WEP key.

Less obvious, but even more pervasive, is an even more extreme type of disaster, in which the attacker does not need to break an authenticated cipher because the application is failing to use an authenticated cipher. Consider the following examples:

• IPsec continues to allow unauthenticated encryption as a standard option, even though this option has been thoroughly broken. See 1996 Bellovin, 2006 Paterson–Yau, and 2007 Degabriele–Paterson; for more context see 2010 Degabriele–Paterson. Users seem to understand that unauthenticated encryption allows the attacker to forge random messages, but seem surprised when it allows the attacker to forge selected messages or to decrypt ciphertext.
• VMWare View is a remote desktop protocol supported by low-cost terminals from various manufacturers. Documentation from VMWare (2010), Dell (2009), etc. recommends switching from "AES-128" to "SALSA20-256" for the "best user experience"; apparently the AES-128 implementations cannot keep up with network graphics faster than about 5Mbps, while Salsa20 is considerably more efficient. Unfortunately, a closer look at the documentation indicates that "AES-128" is actually "AES-128-GCM" while "SALSA20-256" is actually "Salsa20-256-Round12". AES-128-GCM includes authentication, but 12-round Salsa20 does not. Salsa20 can be combined with authentication, of course, but there is no indication that VMWare's "Salsa20-256-Round12" includes any authentication.
• There is an extensive, and apparently never-ending, literature on "lightweight identification protocols" such as HB, HB+, HB++, HB-MP, HB*, Trusted-HB, and HBsharp. Each of these protocols was broken within one year of being proposed. Note that any authenticated cipher can trivially be used for identification: the challenger sends a random message; the prover sends back the same message, authenticated.

It is easy to blame many of these security problems on a lack of user education, where in this case the users are the software and hardware engineers choosing cryptographic primitives to apply. The AES block cipher was standardized more than a decade ago and apparently has none of the weaknesses of RC4, Keeloq, etc.; there is an extensive literature explaining how to use AES to encrypt and authenticate messages of any length (for example, with AES-OCB3); many of these explanations are backed by proofs of security, assuming nothing more than the security of AES; and there is an extensive literature on defenses against timing attacks and other side-channel attacks.

However, in many cases there is a tension between security and the performance requirements of the applications. For example, RC4 became popular precisely because it offers high speed in software: AES needs more than 10 cycles per byte on most CPUs, while RC4 typically runs in fewer than 6. HB was introduced, and remains widely studied, precisely because it can fit into very small hardware, under 1000 gates. Software side-channel defenses impose a noticeable cost, and hardware side-channel defenses impose a much larger cost.