[Cryptography] a question on consensus over algorithmic agility

John Kelsey crypto.jmk at gmail.com
Mon Jun 30 12:32:43 EDT 2014


> On Jun 30, 2014, at 9:28 AM, Jerry Leichter <leichter at lrw.com> wrote:
> 
>> On Jun 26, 2014, at 5:21 PM, John Kelsey <crypto.jmk at gmail.com> wrote:
>> a.  The security benefit of algorithm agility is entirely in being able to *stop* using some algorithms while still functioning.  
>> 
>> This means that you only really get this benefit if you have at least two ciphersuites that are both SHALLs.  If everyone implements RC4 + CRC32 (the SHALL), and some people also implement AEC-GCM (the SHOULD), then when someone finally realizes that RC4+CRC32 is insecure, you can't actually get rid of it.  
> But this leads us to an interesting position.  We have two schemes (algorithms, protocols what have you), A and B, that both ends definitely implement and which in other ways (performance, cost) are essentially interchangeable (else, again, we would not be in a position to stop supporting either).  We think both are secure, but one of them *may* have been broken - we just don't know which.

I'm working on the assumption that we learn what's broken by seeing academic publications and demonstrated attacks.  So while we don't know today which ciphersuite will be broken, we expect to find out at some point in the future.  At that point, we can switch over to another ciphersuite, but only if that ciphersuite is also implemented in the field.  If it's an optional ciphersuite that is implemented by half the devices in the field, then we don't actually manage to switch over--indeed, we'll probably remain vulnerable to version rollback attacks since devices need to be able to communicate with other devices that only implemented RC4+CRC32.  

Ideally, we should choose two ciphersuites that are rock solid and will remain so for decades to come--maybe AES256-GCM and Twofish256-CMAC or something.  

> This is then simple game theory:  We have two strategies, with equivalent payoffs that may be low (if the opponent "chose" to attack the same strategy we chose), or high otherwise.  And game theory tells us that the optimal strategy is a mixed one:  Choose A or B at random with equal probability.  (You can weight the probability to match knowledge of a weighted probability on the opponent's side.)
> 
> So the logical outcome of asking for algorithm agility is ... a single more complex algorithm.

You're assuming a somewhat different situation.  If we know that someone has attacked one of the ciphersuites, but don't know which, then we have an interesting problem.  I don't know how likely that is, though.  

What we've seen in the past is that we know that there are problems with some fielded algorithms/ciphersuites, but we can't change because there are no alternatives in the field.  Some equipment froze DES or RC4 or MD5 in place, and it's very hard to get rid of it now.  That's a problem that we can address by having two mandatory algorithms defined, so we have something to switch over to.  

The other problem is that people keep fielding crap that's been known to be flawed forever, because  they can make some elaborate argument that the currently-known weaknesses probably don't matter too much in this one case.  So people have kept fielding RC4 for years, despite all kinds of known statistical flaws in the keystream.  And similarly, people kept fielding DES, MD5, etc.  I think this is tightly bound up with this common failure mode in standards, where we end up including everything anyone has implemented.  So since a bunch of people are using something that's obviously unwise to keep using, that becomes part of the standard and gets propagated forward into the next decade of unwise use.  

If you want to build one more complex algorithm instead of two alternatives, that's doable.  But you'll have a couple problems:  

a.  There's a performance impact.  If you first encrypt each plaintext with 3DES in CBC-mode, and then superencrypt with AES in CTR mode, you have a lot more work per encrypted bit.  Probably that doesn't matter most places, but there are some places where it will matter.  

b.  Some attacks (reaction attacks, compression side channels) work regardless of superencryption.  If someone does a reaction attack on your CBC-padding, superencrypting with CTR mode won't have any effect on the attack.  

Now, we can probably avoid most of (b) by careful design.  But it's not so clear how to get away from (a).  

>                                                        -- Jerry

--John


More information about the cryptography mailing list