Re: [Cfrg] Security proofs v DH backdoors

[Dan Brown <[e-mail]>]

Yes, ECC is the best, and should be a MUST whenever public key agreement is needed.

But there's still good in DH (classic prime field DH).  Generally, older is better (which is fun to call aegis = age * eyes).

Long term, strongest link crypto should be under consideration; over time, it should become affordable.  (Between two individual end users, what's a few extra milliseconds?)  E.g. ECDH && QRC && RSA && FFDH for key agreement.  (Of course, ECDH || QRC || ... is weakest link, which should be phased out.)

It's really baffling to me that DH, which is so simple mathematically, still has implementation security issues, such as invalid public keys and small subgroups.

But the latest incarnations of Gordon's hidden SNFS-DL issue seems to be a more fundamental problem with DH.

Suppose I need to trust somebody else's DH parameters (maybe an some authority's recommendation, e.g. CFRG's).  

Is there a way to prove that SNFS-DL does not apply?  I presume that there are heuristic ways to certify DH parameters as likely to be immune: are these standardizable?  Surely, somebody has done this for the IKE groups, or other named DH groups.

If not, then shouldn't I just assume SNFS-DL applies, and insist on an appropriate adjustment of key size.  (Maybe double what I take for GNFS-DL, so 6144 for full-out 128-bit security?)

If I generate my own DH parameters, say randomly, is there way to a formally prove SNFS is at least unlikely to apply?  I presume that this is well-understood, at least heuristically, because it is the same reason why SNFS is indeed special.  

More generally, what are the probabilities versus speed-ups in hidden SNFS-DL?  Suppose that I estimate that an authoritative DH prime was be drawn from a set of at most 1 million of DH primes.  When can I reasonably that those 1 million candidates are about as vulnerable to SNFS-DL as random DH primes?  In that case, how much of a speed-up in SNFS-DL can I expect for a 1-in-a-million most greatest speed-up? 

In ECC, the situation seems clearer.  The known special case non-generic attacks on ECC (the attacks MOV and SASS) are easily detectable.  It seems SNFS-DL is not in the same situation.  On the more generic-group attack front, such as invalid-keys (super-group keys) and Pohlig-Hellman, ECC usually specifies the cofactor, (and I still don't know why DH sometimes does not), and there's a bunch of other mitigations (in the standards I am familiar with). 

As for randomization/rigidity in ECC, its main purpose is to thwart secret attacks, not known attacks.  These are tenuous mitigations against tenuous attacks.  I find it a little awkward to thwart a known real-world attack (SNFS-DL) using randomization/rigidity techniques.  

Best regards,

Dan

-----Original Message-----
From: John Mattsson [mailto:[e-mail]] 
Sent: Thursday, October 27, 2016 8:13 AM
To: Hanno Böck <[e-mail]>; Dan Brown <[e-mail]>
Cc: CFRG <[e-mail]>; Peter Gutmann <[e-mail]>
Subject: Re: [Cfrg] Security proofs v DH backdoors

Very much agree with you Hanno, the ONLY reason I can see to still support DH at all, is to have a fallback if someone comes up with a way of solving ECDLP faster that O(q^1/2).


/John

On 27/10/16 12:51, "Cfrg on behalf of Hanno Böck" <[e-mail] on behalf of [e-mail]> wrote:

>On Thu, 27 Oct 2016 10:32:17 +0000
>Dan Brown <[e-mail]> wrote:
>
>> For q=(p-1)/2, literally computing c^q for client public key is very 
>> slow.
>> 
>> Why not use a faster alternative, such as checking Legendre symbol 
>> (c/p), use cofactor DH,‎ or use even private keys?
>
>This line of debate and all the recently released papers show one very 
>concerning thing: We haven't learned how to use Diffie Hellman properly
>- although it's an algorithm at the end of its life.
>
>I think when I read the logjam paper I became aware of how tricky of an 
>issue this is and how many things can go wrong with DH. It was also the 
>time when I concluded that the best is probably to just move beyond DH.
>
>Sure, there is probably a way to use DH in a way that reflects all 
>security concerns, is still reasonably performant etc. But why should 
>we have this discussion when we already know DH is on its way out?
>Chrome already decided to disable it, others will follow.
>Is there a good reason to keep DH around? One I'm aware of is that some 
>people think due to its larger size it's more resistant against quantum 
>computers. But I have heard multiple people familiar with QC and 
>pqcrypto that they don't buy that argument.
>
>I'm not arguing that ECC is simpler, but I'm arguing that we have 
>solved a lot of these issues facing DH already in a better way for ECC:
>By simply not using random parameters which whoever decides, but by 
>using one or two good curves that have all desired properties. We 
>probably could do the same for DH, but we don't have to if DH is 
>deprecated anyway.
>
>--
>Hanno Böck
>https://hboeck.de/
>
>mail/jabber: [e-mail]
>GPG: FE73757FA60E4E21B937579FA5880072BBB51E42