Re: [Cfrg] 2^40. I can't exhibit it, but it exists. -> Re: I-D Action: draft-irtf-cfrg-dragonfly-03.txt

[David McGrew <[e-mail]>]

HI Paul and Watson,

On 02/04/2014 03:05 AM, Paul Lambert wrote:
>
>
>     > A proof might be desirable but should not block the use of a proposed protocol.
>     > For example there is no adequate proof that integer
>     factorization is “secure”.
>     > This is not a reason to stop using RSA based algorithms.  The
>     lack of
>     > a  complete security proof for draft-irtf-cfrg-dragonfly-03.txt
>     should not
>     > stop it’s use (in fact it’s already in other standards that
>     would benefit
>     > from the analysis and improvements of this group).
>
>     But there is a proof that OAEP has a reduction to RSA security.
>     PKCS 1.5 had no proof, and got broken a few times. RSA has been
>     intensively studied for decades, dragonfly hasn't. Slight variants
>     of RSA (Rabin-Williams) are provably reducible to factoring, an
>     extensively studied problem for centuries.
>
> You missed the point.  The difficulty of factoring as a problem to 
> build secure systems is not provable.
> . . .
>

Paul, you are right that the computational cost of factoring the product 
of two large primes is unknown, and there is no proof that it is hard.   
But Watson also has a point, that the factoring problem is easily 
understood and has been very well studied.   In particular, it has been 
more well studied than the dragonfly security conjecture, whatever that 
conjecture is.   (Has it been isolated?)

At the end of the day, none of the crypto that we use is actually proven 
to be unconditionally secure.  (I'm ignoring information theoretic 
security here, to make the discussion easier ;-)  It might be proven to 
be secure if factoring is hard, or if AES with a random secret key is 
indistinguishable from a random permutation, or under some other 
well-understood conjecture.   It is a major goal to reduce the number of 
conjectures that we need to rely on, and to rely on conjectures that we 
have more confidence in.

I think we should prefer algorithms and protocols that rely only on 
well-understood conjectures.   I will hedge this statement, though, and 
say that the security conjectures are just one factor in the decision 
making process.   For instance: the Blum Blum Shub (BBS) pseudorandom 
number generator is secure if factoring is hard, but we use AES or HMAC 
based PRNGs instead, because BBS would be *slow*. Furthermore, it is 
quite possible that AES-CTR is more secure than BBS; it may we be that 
we see advances in the state of the art in factoring.

>     > Watson, in your technical analysis of the
>     > protocol in its current form (draft-irtf-cfrg-dragonfly-03.txt),
>     > can you identify any exploitable security flaw specific to
>     > the protocol?
>
>     Yes: an algorithm exists that guesses passwords in time 2^40. I
>     can't exhibit it, but it exists. JPAKE doesn't have this issue.
>

Watson, can you quantify the claim of 2^40?

David

> I will take your answer as a ‘no’ - you are unable to identify any 
> exploitable security flaw with draft-irtf-cfrg-dragonfly-03.txt
>
> Making such repeated and  adversarial negative pronouncements on a 
> technical topic without documentation or your own demonstrable 
> analysis would be considered by some to be unprofessional behavior.
>
>
> Paul
>