[Cryptography] a question on consensus over algorithmic agility

[Jerry Leichter]

On Jun 30, 2014, at 12:32 PM, John Kelsey <crypto.jmk at gmail.com> wrote:
>> 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....
>> 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.
No, the situation I'm assuming subsumes yours, as you're ignoring the break that doesn't make it into the open literature.  The mixed strategy covers both.  (Actually, as was pointed out earlier, encrypting with first one algorithm and then the other also does - but the order may matter.  Choosing the order at random per message is then again the best strategy.)

Once the academic papers start to come out, your estimate of the probability that the attacked algorithm is actually broken goes up, and your best mixed strategy naturally shifts to the other - until one of the algorithms is considered to be definitely unsafe, at which point the optimal strategy is clearly to ignore it.

Game theory is about optimal decision making in the presence of uncertainty.  That's the situation you face any time you field a cryptographic system:  You have to assume others will try to attack it, but you have no way to know if they'll succeed.  Game theory is cast in terms of the potential strategies available to you and your opponent.  Here, your strategies involve using A or B.  You opponent *has a strategy that counters A (respectively B) if and only if he has broken A(B)."

                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140630/76cc94fb/attachment.bin>