Re: [Cfrg] ISE seeks help with some crypto drafts

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Cfrg <[e-mail]> On Behalf Of D. J. Bernstein
> 
> Time for security reviewers is a precious resource in cryptography. It
should be

True.

***

Hmm, hints of the Monty Hall problem: given the prize behind door OCB2,
maybe we should switch from door OCB3 to door OCB1? (Given only these
choices ... ;).

***

I was very shaken to hear about OCB2 being broken.

***

A non-precious security review follows. 

The results are extremely harsh towards OCB3 and OCB1, but presumably, the
harsh results can be refuted by a more serious security review.

Assume that [Breakablity of OCBn] for n=1,2,3,... is a random variable,
taking Boolean values, having an independent identical distribution (IID),
with a common probability p of being true (each OBCn independently breakable
with prob p).

The observed data is that at least one of OCB{1-3} is breakable, because
OCB2 has been broken.  The likelihood of such an observation is L =
1-(1-p)^3  = 3p - 3p^2 + p^3.  (Similarly, the likelihood is just p for the
simpler observation that at least OCB2 is breakable.)

A maximum likelihood estimate (MLE) puts p=1 (to maximize L, and this is the
unique maximum of L), which means MLE tells us to infer that both OCB1 and
OCB3 are 100% breakable.  To infer otherwise, means we need more (1)
observations, (2) different assumptions, or (3) a different inference method
(arguably MLE is too crude).

To defend the MLE inference method, suppose that there had been no
observations of breakability in OCB{1-3}.   This means the number of
breakables could be any of {0-3}.  This event has likelihood 1, and does not
depend on p.  Then MLE method tells us that all values of p maximizes the
likelihood, so the inference for p is actually a set, now the whole interval
[0,1].   This inference interval does not inspire much confidence, of
course. (Indeed, it is a formal general reason no to immediately trust
any-old new algorithm XYZ.)  But the inference interval [1,1] (i.e., p=1)
seems worse than [0,1].  The simple MLE method is consistent with intuition,
that if one observes (assumedly related) algorithms Doe1, Doe2, Doe3, ...,
Doe7, all broken, but Doe8 is not (yet) broken one might prefer an
(assumedly) unrelated algorithm Joe over Doe9 (unless you know Joe is really
Joe9 and is (assumedly) related to broken Joe{1-8}, e.g. if you ask 8
ordinary Joes off the street etc.)

For an example of an inference strategy different from MLE, we could try an
optimistic benefit-of-the-doubt method.  By this, I mean to presume that p
is as a low as possible, subject to some lower bound on likelihood, say
0.05.  With L = 1-(1-p)^3 > 0.05, we conclude that p > 0.017, which (in my
opinion) is not nearly low enough.   This kind of benefit-of-the-doubt
inference method is perhaps fine in some applications, but seem intuitively
unjustifiable in security (*).  

(*) On the other hand, saying the inference p in interval [1,1] is worse
than the inference p in [0,1], is essentially granting slight
benefit-of-the-doubt, allowing optimists to imagine that p in [0,1] might be
small.  Pessimists may see not difference in these inferences.  However,
when choosing the least bad options, interval [0,1] seems better.

Again, a better inference would at least have (1) better observations, and
(2) better assumptions.  Better observations could include the number of
reviewers, the time spent; better assumptions could include various other
unknown variables, such as, existing of breaks, severities of breaks,
difficulty of finding breaks reviewer's skill or efforts, and then
assumptions about the probability for these variables, such as, independence
of security reviewers chances of finding an attack (if it exists).  

I realize that the consensus practice does not attempt use the formal
statistical inference described above to present security review data,
whether that of CFRG, other standards, various crypto competitions, academic
reviews and so on.  I do not object to that practice, since the security
review is the "precious resource", while statistical formality is just a
nuisance.    

Regardless, if such formal inferences could be made, OCB3 may well fare
comparably with the other state-of-the-art algorithms (e.g. GCM), for all I
know. Nevertheless, the point is that the related OCB2 has dug OCB3 into a
shallow hole, which, yes, can be gotten out of, but requires extra effort to
regain (my) confidence.