All posts by Michael Roe

Variable Length Fields in Cryptographic Protocols

Cryptology

Many crypto protocols contain variable length fields: the names of the participants, different sizes of public key, and so on.

In my previous post, I mentioned how Liqun Chen has (re)discovered the attack that many protocols are broken if you don’t include the field lengths in MAC or signature computations (and, more to the point, a bunch of ISO standards fail to warn the implementor about this issue).

The problem applies to confidentiality, as well as integrity.

Many protocol verification tools (ProVerif, for example) will assume that the attacker is unable to distinguish enc(m1, k, iv) from enc(m2, k, iv) if they don’t know k.

If m1 and m2 are of different lengths, this may not be true: the length of the ciphertext leaks information about the length of the plaintext. With Cipher Block Chaining, you can tell the length of the plaintext to the nearest block, and with stream ciphers you can tell the exact length. So you can have protocols that are “proved” correct but are still broken, because the idealized protocol doesn’t properly represent what the implementation is really doing.

If you want different plaintexts to be observationally equivalent to the attacker, you can pad the variable-length fields to a fixed length before encrypting. But if there is a great deal of variation in length, this may be a very wasteful thing to do.

The alternative approach is to change your idealization of the protocol to reflect the reality of your encryption primitive. If your implementation sends m encrypted under a stream cipher, you can idealize it as sending an encrypted version of m together with L_m (the length of m) in the clear.

Hidden Assumptions in Cryptographic Protocols

Cryptology

At the end of last week, Microsoft Research hosted a meeting of “Cryptoforma”, a proposed new project (a so-called “network of excellence”) to bring together researchers working on applying formal methods to security. They don’t yet know whether or not this project will get funding from the EPSRC, but I wish them good luck.

There were several very interesting papers presented at the meeting, but today I want to talk about the one by Liqun Chen, “Parsing ambiguities in authentication and key establishment protocols”.

Some of the protocol specifications published by ISO specify how the protocol should be encoded on the wire, in sufficient detail to enable different implementations to interoperate. An example of a standard of this type is the one for the public key certificates that are used in SSL authentication of web sites (and many other applications).

The security standards produced by one group within ISO (SC27) aren’t like that. They specify the abstract protocols, but give the implementor considerable leeway in how they are encoded. This means that you can have different implementations that don’t interoperate. If these implementations are in different application domains, the lack of interoperability doesn’t matter. For example, Tuomas Aura and I recently wrote a paper in which we presented a protocol for privacy-preserving wireless LAN authentication, which we rather boldly claim to be based on the abstract protocol from ISO 9798-4.

You could think of these standards as separating concerns: the SC27 folks get the abstract crypto protocol correct, and then someone else standardises how to encode it in a particular application. But does the choice of concrete encoding affect the protocol’s correctness?

Liqun Chen points out one case where it clearly does. In the abstract protocols in ISO 9798-4 and others, data fields are joined by a double vertical bar operator. If you want to find out what that double vertical bar really means, you have to spend another 66 Swiss Francs and get a copy of ISO 9798-1, which tells you that Y || Z means “the result of the concatenation of the data items Y and Z in that order”.

Oops.

When we specify abstract protocols, it’s generally understood that the concrete encoding that gets signed or MAC’d contains enough information to unambigously identify the field boundaries: it contains length fields, a closing XML tag, or whatever. A signed message {Payee, Amount} K_A should not allow a payment of $3 to Bob12 to be mutated by the attacker into a payment of $23 to Bob1. But ISO 9798 (and a bunch of others) don’t say that. There’s nothing that says a conforming implementation can’t send the length field without authentication.

No of course, an implementor probably wouldn’t do that. But they might.

More generally: do these abstract protocols make a bunch of implicit, undocumented assumptions about the underlying crypto primitives and encodings that might turn out not to be true?

See also: Boyd, C. Hidden assumptions in cryptographic protocols. Computers and Digital Techniques, volume 137, issue 6, November 1990.

Anti-theft Protocols

Hardware & signals, Security engineering

At last Friday’s Security Group meeting, we talked about security protocols that are intended to deter or reduce the consquences of theft, and how they go wrong.

Examples include:

  • GSM mobile phones have an identifier for the phone (separate from the identifier for the user) that can be blacklisted when the phone is stolen.
  • Some car radios will stop working when the battery is disconnected, and only start working again when a numeric code is entered. This is intended to deter theft of the radio.
  • In Windows Vista, Bitlocker can be used to encrypt files. One of the intended applications for this is that if someone steals your laptop, it will be difficult for them to gain access to your encrypted files.

Ross told a story of what happened when he needed to disconnect the battery on his car: the radio stopped working, and the code he had been given to reactivate it didn’t work – it was the wrong code.
Ross argues that these reactivation codes are unecessary, because other measures taken by the car manufacturers – such as making radios non-standard sizes, and hence not refittable in other car models – have made them redundant.

I described how the motherboard on a laptop had needed to be replaced recently. The motherboard contains the TPM chip, which contains the encryption keys needed to decrypt files protected with Bitlocker. If you replace the motherboard, the files on your hard disk will become unreadable, even if the disk is physically OK. Domain-joined Vista machines can be configured so that a sysadmin somewhere within your organization is able to recover the keys when this happens.

Both of these situations suffer from classic usability problems: the recovery procedures are invoked rarely (so users may not know what they’re supposed to do), and, if your system is configured incorrectly, you only find out when it is too late: you key in the code to your radio and it remains a doorstop; the admin you hoped was escrowing your keys turns out not to have the private key corresponding to the public key you were encrypting under (or, more subtly: the person with the authority to ask for your laptop’s key to be recovered is not you, because the appropriate admin has the wrong name for the laptop’s owner in their database).

I also described what happens when an XBox 360 is stolen. When you buy XBox downloadable content, you buy two licenses: one that’s valid on any XBox, as long as you’re logged in to XBox live; and one that’s valid on just your XBox, regardless of who’s logged in. If a burglar steals your Xbox, and you buy a new one, you need to get another license of the second type (for all the other people in your household who make use of it). The software makes this awkward, because it knows that you already have a license of the first type, and assumes that you couldn’t possibly want to buy it again. The work-around is to get a new email address, a new Microsoft Live Account, and a new Gamer Tag, and use these to repurchase the license. You can’t just change the gamertag, because XBox live doesn’t let the same Microsoft Live account have two gamertags. And yes, I know, your buddies in the MMORPG you were playing know you by your gamertag, so you don’t want to change it.