[Cryptography] open questions in secure protocol design?

[David Johnston]

On 5/30/2015 7:21 PM, Jerry Leichter wrote:
> This is an interesting approach, but it's missing a careful threat analysis.  You've baked in consideration of the "death by 1000 cuts" failure, where there's plenty of time to anticipate that the current algorithm is heading for trouble.  But what if the current algorithm fails suddenly?
The problem here is that the crypto implementation will be baked into 
hardware devices. Responding to sudden crypto failure in this context 
seems like a hard problem and I don't claim to have a solution. However 
we don't seem to see that happen much with mainstream algorithms. It's 
more like SHA-1 or the AES 256 key schedule. We have time to respond.

I do actually claim to have a solution, but I don't think it would fly 
in terms of getting buy in by manufacturers. Namely parameterizing 
algorithms with parameters we can negotiate on the fly. Like a 
minimum_extra_rounds parameter. It's easy to bake that into an 
implementation and it's easy to negotiate. It would address a certain 
class of crypto failures, but not all. It also gives you an opportunity 
to shoot yourself in the foot. Never use the same key with different 
numbers of rounds.

> You have no mechanism to move quickly to something else.  Alternatively, what if it turns out, half way through your distribution of a new algorithm, that the *new* one fails, while the old one seems to still be strong?  Can you somehow move back to it, without enabling rollback attacks?
Yes you can rollback - but this is the thing I'm least happy with. I 
don't want to run into TLS's downgrade nightmare.

>
> Negotiation of the protocol to use makes sense in situations where endpoints can actually make a rational choice among alternatives.  You might be able to construct such a situation for communication within a group of experts - e.g., well-trained spies.  I find it very hard to come up with more common situations in which it makes sense.
Yes. There will be no experts present.
> Picking a single cipher is like engineering with a known single point of failure.  That's not necessarily a bad thing!  Your car's steering system has multiple single points of failure, because there's really not much you can do to make it redundant without increasing other risks due to complexity.  On the other hand, your car's brakes are dual-redundant because that's a better assignment of risks for them.  Whether a single-cipher system makes more sense than one with N ciphers depends on your failure scenarios.  Do you include rollback attacks?  How about "directed failure" attacks, where an opponent is able to break one of your ciphers and then force connections to use that one?  Against such attacks, adding more ciphers *decreases* your security!
This presupposes we can define a cluster of algorithms of which not all 
will fail. Algorithms fail all the time. There's usually a few new 
attacks at each IACR conference. But the suite of well burnished 
algorithms is small and many are tainted by coming from governments, 
which impedes their acceptance in international markets.
> Consider a situation where you have two ciphers, and you think your opponent might be able to break one, *but you don't know which*.  Then you're into game theory, and the optimal strategy is a mixed one:  Choose one cipher or the other by tossing a coin each time.  (Of course, you could also encrypt with both.  That reduces you to a single cipher approach - but the cipher is a more complicated one resulting from combining the other two, a combination that may be less well studied that either of your original choices.)
'Break' in this case would primarily means fraudulently authenticating 
as something that is authorized. My sensibilities lead me to think the 
risk from the implementation complexity of these schemes is worse than 
the risk of the chosen algorithm not outliving the device.
>
> We go back and forth on 1TCS versus algorithm agility versus algorithm evolution without stepping back and admitting that *this choice is itself a protocol design problem*, and needs to be approached as such.  A threat analysis is the first step....
>                    
Yes. I expect specs, TA and source code will be out in the public fairly 
soon, so we can beat it to a pulp in the grand tradition of this forum.
>                                        -- Jerry