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

[Paul Lambert <[e-mail]>]

David,

Thank you for the thoughtful position.

I to agree that  there should be a slight preference to have a 'proof' of security where possible.  However, the lack of a formal proof should not be considered a flaw.

Some of the text you have below might be worth squirreling away to  for use in some future form of CFRG guidelines for recommendations.

Regards,

Paul



From: David McGrew [mailto:[e-mail]]
Sent: Tuesday, February 04, 2014 5:02 AM
To: Paul Lambert
Cc: Watson Ladd; [e-mail]
Subject: Re: 2^40. I can't exhibit it, but it exists. -> Re: [Cfrg] I-D Action: draft-irtf-cfrg-dragonfly-03.txt

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