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.
@ Michael,
It’s not just the length that’s an issue (there are others that are less obvious).
One way of looking at it is that the system or protocol contains static and dynamic components.
You can do your security etc proofs on the static components but not the dynamic.
Normally it is fairly easy to tell the static and dynamic components of a system or protocol apart. However when it comes to message content assumptions are made which can have consiquences in practical systems.
With regards to length well… it should be fairly well known that an “efficient implementation” cannot hide this factor even with a provably unbreakable system such as the One Time Pad.
In many respects the dynamic parts of a system or protocol should be looked at in a similar way to “traffic analysis” issues. This is due to amongst other reasons the soloutions to traffic analysis and the dynamic parts of a system or protocol are the same and have the same failings.
Oh there is another issue where proofs mislead people and that is “side channels”. The majority of workable attacks on systems and protocols are due to side channel attacks. Often the system or protocol designers assume that such issues fall within that of implementation.
However it is a significant mistake to ignore both dynamic components and side channel issues when specifying a system or protocol as they often result from fundimental design concepts.
One of the critisisms leveled at the AES contest was that practical implementation issues such as “loop unrolling” and “cache hits and missess” where not considered during the selection process nor where any warnings given to implementers of making an “overly efficient” design and opening up side channels etc.
The issue of “efficiency -v- security” is something that has not realy made it onto the radar of “public security” research which is going to be a signifficant issue in the not to distant future.