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

From: Paul Lambert <[email-masked]>
Date: Tue, 4 Feb 2014 00:05:03 -0800

> 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.
. . .

> 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.

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

---

From: David McGrew <[email-masked]>
Date: Tue, 04 Feb 2014 08:02:17 -0500

HI Paul and Watson,

On 02/04/2014 03:05 AM, Paul Lambert wrote:
>     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.
>

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.

>     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
>

---

From: Paul Lambert <[email-masked]>
Date: Tue, 4 Feb 2014 13:42:31 -0800

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:[email-masked]]
Sent: Tuesday, February 04, 2014 5:02 AM
To: Paul Lambert
Cc: Watson Ladd; [email-masked]
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:

> For example there is no adequate proof that integer factorization is "secure".
> stop it's use (in fact it's already in other standards that would benefit

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.

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

Paul