[Cryptography] End-to-End Protocols and Wasp Nests

[Bear]

On Wed, 2014-03-05 at 11:28 -0800, Dennis E. Hamilton wrote:
>   -----Original Message-----
> From: Jerry Leichter

> > It needs to be easy to add "interesting combinations" to the test suite. 

> > If it is possible, generating a complete set of combinations of flaws 
> is not unreasonable. 

> With regard to both of those cases, it seems to me that detection and 
> mitigation is not that complex.  

I like your "wasp nest" idea; a sort of crowdsourced set of 
remotely accessible test cases would be very useful, because 
most developers never come up with more than a few dozen.  

It seems to me that most "interesting cases" are made 
up of unexpected combinations of Ops & Circs (Operations 
& Circumstances), and that by the time humans have written 
a thousand bug reports, they've probably discovered eighty 
or a hundred different Ops & Circs of interest -- each of 
the thousand bug reports/future test cases being composed 
of combinations of two or three or four of them. 

I think it would be a worthwhile methodology to start 
trying to abstract the Ops & Circs - each 'aspect' that 
is normally handled well but combines with some specific
other thing to reveal a bug, is a candidate.

You can write a brute-force algorithm that just keeps trying
combinations of different known Ops & Circs of interest -- but 
the problem there is that if you've got forty of them, you're 
exploring a forty-bit keyspace, with an "operation" that takes 
a hell of a lot longer than a decryption.  And if you've got 
sixty of them, you have to restrict your search somehow.  

I think you get most of the coverage if you just tell your 
brute-force test generator to limit the number of bits it flips
"on" -- most bugs are a combination of two or three or four 
things, not a combination of twenty or thirty or forty.  There's 
a simple algorithm to generate numbers from lowest setbit count 
to highest, so that would probably be the test enumerator for 
this hypothetical brute-force testing tool.  

Start from zero, and work your way up, as they say.  It's not 
a fully rigorous proven-complete test suite (because you can't 
ever prove you've found all the ops & circs of interest) but 
it surely would generate and test a nearly-infinite number of 
cases, and whenever a particular new op or circ were discovered, 
it would very quickly delineate the circumstances in which it 
becomes a problem.

And unlike most automated testing proposals, the method is simple 
enough for ordinary developers to understand and use.

			Bear