Subject: [Cfrg] Security proofs v DH backdoors

From: Dan Brown <[email-masked]>
Date: Tue, 25 Oct 2016 13:10:16 +0000

How do the 3 recent IACR eprints on FFDH backdoors‎ reconcile with past security proofs for TLS, SSH, etc?

Some guesses: (1) the attacks are outside the security definitions (=> attacks not so important?), (2) the proofs assume strong FFDH groups plus validation, etc.

Sent from my BlackBerry 10 smartphone on the Rogers network.

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 25 Oct 2016 16:30:17 +0300

On Tue, Oct 25, 2016 at 01:10:16PM +0000, Dan Brown wrote:
> Some guesses: (1) the attacks are outside the security definitions
> (=> attacks not so important?), (2) the proofs assume strong FFDH
> groups plus validation, etc.

I guess the proofs assume strong FFDH groups, such that dlog and
dh attacks are infeasible.

I think there was one TLS implementation that tries to verify the
groups sent (of course, not all can be verified, even if those
aren't maliscously constructed).

And the backdoors in one of the papers was about constructing
prime such that one can use faster special case for dlogs. That
can't be easily discovered, even if one somehow can obtain the
group order. So one can't validate against it.

-Ilari

---

From: Hanno Böck <[email-masked]>
Date: Tue, 25 Oct 2016 15:41:49 +0200

On Tue, 25 Oct 2016 13:10:16 +0000

> groups plus validation, etc.

I think the general assumption is that a server is non-malicious and
sends good parameters.
However there was one example of an attack discovered by a formal
analysis of the TLS protocol where impersonating a user with a client
certificate to another server involved using bad DH parameters (Triple
Handshake [1]). That seems a bit like a special cornercase though.

I wonder how the scenario of malicious parameters can be formally
stated and what the expectations would be. Somewhat related is that the
whole NUMS idea is still unsettled, given that we had a bunch of cases
where the designers of some algorithm tried to make something
nonsuspicious looking, but it was later still criticized for being
suspicious (e.g. NIST curves, Brainpool vs. Bada55).

[1] https://mitls.org/pages/attacks/3SHAKE

-- 
Hanno Böck
https://hboeck.de/

mail/jabber: [email-masked]
GPG: FE73757FA60E4E21B937579FA5880072BBB51E42

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 26 Oct 2016 04:32:49 +0000

Ilari Liusvaara <[email-masked]> writes:

>I think there was one TLS implementation that tries to verify the groups sent
>(of course, not all can be verified, even if those aren't maliscously
>constructed).

Mark Bauschke mentioned they do checking on the OpenSSH list, taking (i.e.
assuming) that q = ( p - 1 ) / 2.  I don't recall any TLS implementation doing
this.  However, with TLS-LTS there are one or more implementations now that do
check.

(Hey, I've got to get the maximum mileage out of this one :-).  LTS has
already foiled attacks that postdate its publication, so you know it's a good
thing).

Peter.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Wed, 26 Oct 2016 16:20:32 -0700

Peter Gutmann <[email-masked]> writes:

> Mark Bauschke mentioned they do checking on the OpenSSH list, taking

Minor typo. The lastname is Baushke without the "c" in it. Long story.

> (i.e. assuming) that q = ( p - 1 ) / 2. 

I may have sent a confusing message.

OpenSSL 1.0.2f (to address CVE-2016-0701) added a check where a "q"
parameter is available.

The OpenSSH dh.c::dh_new_group() is able to setup a dh->q value by using
the q = (p - 1) / 2 math. The dh.c::dh_pub_is_valid() could also check
any incoming DH using the OpenSSL
crypto/dh/dh_check.c::DH_check_pub_key() functionality which does:

       /* Check pub_key^q == 1 mod p */
        if (!BN_mod_exp(tmp, pub_key, dh->q, dh->p, ctx))
            goto err;
        if (!BN_is_one(tmp))
            *ret |= DH_CHECK_PUBKEY_INVALID;

as is mandated by NIST SP 800-56A rev1 section 5.6.2.4 FCC Full Public
Key Validation Routine.

In the Juniper Networks OpenSSH implementation a "q" with q=(p-1)/2
parameter validation is performed in FIPS mode because we are mandated
to validate the DH parameters for FIPS 140-2.

This is true even if it is the well known DH group14 (which is not
required for TLS or IPsec).

DH parameter validate can cause some issues if users configure support
for RFC 4419 while in FIPS mode as most of those groups seem to have a
problems finding a proper set of parameters to use a which results in a
well formed q-ordered subgroup evaluation... the result of the DH mod p
operations is p-1 in those situations which is not good.

	-- Mark

---

From: Dan Brown <[email-masked]>
Date: Thu, 27 Oct 2016 10:32:17 +0000

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?

Sent from my BlackBerry 10 smartphone on the Rogers network.
  Original Message
From: Mark D. Baushke
Sent: Wednesday, October 26, 2016 7:21 PM
To: Peter Gutmann
Cc: Ilari Liusvaara; Dan Brown; CFRG
Subject: Re: [Cfrg] Security proofs v DH backdoors

        -- Mark

---

From: Hanno Böck <[email-masked]>
Date: Thu, 27 Oct 2016 12:51:20 +0200

On Thu, 27 Oct 2016 10:32:17 +0000
Dan Brown <[email-masked]> wrote:

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

---

From: Daniel Bleichenbacher <[email-masked]>
Date: Thu, 27 Oct 2016 12:59:47 +0200

One question is what a good standard would be?

PKCS #3 does not include the q in the parameters.
Implementations (e.g. DHParameterSpec in java) use this standard and hence
don't have this parameter either.
Without q it doesn't seem just tricky to verify general DH public keys, it
kind of seems infeasible.

On Thu, Oct 27, 2016 at 12:51 PM, Hanno Böck <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: John Mattsson <[email-masked]>
Date: Thu, 27 Oct 2016 12:12:59 +0000

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" <[email-masked]

---

From: Dan Brown <[email-masked]>
Date: Thu, 27 Oct 2016 14:40:03 +0000

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:[email-masked]] 
Sent: Thursday, October 27, 2016 8:13 AM
To: Hanno Böck <[email-masked]>; Dan Brown <[email-masked]>
Cc: CFRG <[email-masked]>; Peter Gutmann <[email-masked]>
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" <[email-masked] on behalf of [email-masked]> wrote:

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

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 28 Oct 2016 09:36:07 +0000

>concerning thing: We haven't learned how to use Diffie Hellman properly

Well, we have, what it really shows is that there are still implementations
around that use it badly.  As there are for almost everything.

>But why should we have this discussion when we already know DH is on its way
>out? 

It's going to be around for a long, long time, if not forever, for three
reasons.  Firstly, your assumption, which I've heard from others as well,
seems to be based on the browser/web server worldview where you can roll out
an update any time you like to make the server/client do whatever you want it
to.  However, if you look at real-world surveys of TLS traffic, the most
common TLS mode is still 1.0, dating from 1999.  This means that for general
web traffic, not just what Chrome, Firefox, and Edge do, there's at least a
15-year latency for deployment.  In terms of industry bodies, groups like the
PCI council are planning to move to TLS 1.1, from ten years ago, by 2018.
There's no indication of when they'll start looking at TLS 1.2.  Other
industry bodies in the SCADA/embedded space are roughly the same, there's a
gradual move from TLS 1.0 to TLS 1.1 with some mutterings about 1.2 in some
places.

Secondly, DH's replacement, the ECC algorithms, are an absolute non-starter in
any kind of harsh environment.  They're the most brittle crypto you can
possibly deploy, any fault of any kind inevitably ends up leaking the private
key.  I know several industries who, despite its great trendiness, won't touch
the ECC stuff because it's just too brittle to safely use.

Finally, specifically for the Bernstein protocol suite [0] if that's what
you're thinking of for supplanting DH, it's easy enough for someone like
Google to decree that from now on we all have to use X, but many industries
are heavily constrained and regulated and can't just adopt whatever new
algorithm comes along.  Also, hardware support for crypto is almost
universally AES, SHA-1, SHA-2, and sometimes (rarely) some bignum stuff.
You're not going to see any move to TLS 1.3/2.0/whatever-it'll-be-called
outside the web server/client space any time soon there, if ever.

>Chrome already decided to disable it, others will follow. 

That's because Google can decree that from now on we're all going do be doing
what Google wants.  That doesn't work in other industries.

Peter.

[0] No disrespect to Dan et al intended, I'm just using it as a collective
    noun for 25519, 448, ChaCha, Poly1305, etc because I don't know of any
    other collective term for them.

---

From: Hanno Böck <[email-masked]>
Date: Fri, 28 Oct 2016 11:47:58 +0200

On Fri, 28 Oct 2016 09:36:07 +0000
Peter Gutmann <[email-masked]> wrote:

> Secondly, DH's replacement, the ECC algorithms, are an absolute
> non-starter in any kind of harsh environment.  They're the most
> brittle crypto you can possibly deploy, any fault of any kind
> inevitably ends up leaking the private key.  I know several
> industries who, despite its great trendiness, won't touch the ECC
> stuff because it's just too brittle to safely use.

Can you elaborate what brittleness you mean? Because based on what I
know I come to a different conclusion. I think modern ECC is less
brittle than DH.
Reading the past 4 papers on DH (+ maybe logjam and 3shake) should be
enough to tell everyone that DH has a lot of brittleness in it.

Brittleness of ECC:
I'm aware of invalid curve attacks, which can be completely mitigated
by using a twist-secure curve and point compression as far as I'm
aware. Then there's the issue of ECDSA bad randomness (which affects
classic DSA in the same way), but it's irrelevant for key exchanges.

> Finally, specifically for the Bernstein protocol suite [0] if that's
> what you're thinking of for supplanting DH, it's easy enough for
> someone like Google to decree that from now on we all have to use X,
> but many industries are heavily constrained and regulated and can't
> just adopt whatever new algorithm comes along.

So your general idea here is that there are situations where people are
constrained not to use ECC with another curve, but they *can* use DH
with another parameter set?

I mean I can imagine that this happens (there's probably some
certification out there mandating specific curves and allowing
arbitrary DH parameters), but only in situations free of any
cryptographic knowledge.

But if there's a need for DH parameter sets: RFC 7919 has just been
published recently and was already mentioned in this thread. Would it
satisfy the needs of people if there simply was some kind of document
(could be an RFC, but maybe also just an errata) saying that the DH
parameters from 7919 may be used outside TLS? (not sure if this has to
be explicitly stated, but if it helps people, why not?)

-- 
Hanno Böck
https://hboeck.de/

---

From: Michael Scott <[email-masked]>
Date: Fri, 28 Oct 2016 10:51:59 +0100

On Fri, Oct 28, 2016 at 10:36 AM, Peter Gutmann <[email-masked]>
wrote:

> non-starter in

Wow. As an influential opinion leader I think you really need to expand on
that last paragraph. In the first sentence you need to define "harsh
environment". The second sentence ("any fault of any kind") is manifestly
untrue. And in the third sentence what industries exactly? Thanks

Mike

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 28 Oct 2016 09:58:16 +0000

Hanno Böck <[email-masked]> writes:

>Can you elaborate what brittleness you mean?

Uh, faults, as I said in my original message.  Any data corruption, bit-flips,
RNG faults, anything, and you end up leaking the private key.

>constrained not to use ECC with another curve, but they *can* use DH with
>another parameter set?

They've been using DH forever, and will continue to do so.  They won't move to
an entirely new and/or extremely brittle algorithm class (and, in the case of
TLS 1.3/2.0, an entirely new protocol).

>Would it satisfy the needs of people if there simply was some kind of
>document (could be an RFC, but maybe also just an errata) saying that the DH
>parameters from 7919 may be used outside TLS? (not sure if this has to be
>explicitly stated, but if it helps people, why not?)

Uh, that's exactly the question I asked in my post...

I think it's more of a political than technical problem.  If you (meaning the
server) can generate your own parameters you're fine, if you're an industry
body you can mandate whatever it is you feel comfortable mandating, so it's
mostly a case of asking who would want/need standard parameter sets, and what
would it take to keep them happy about how they're generated?  Look at the
Brainpool curves for an example, one group of people regard them as perfectly
good NUMS values, another group regards them as having too much scope for
manipulation.  So it's a case of how far down the rabbit hole do you want to
go for generation?

Peter.

---

From: Hanno Böck <[email-masked]>
Date: Fri, 28 Oct 2016 12:43:19 +0200

On Fri, 28 Oct 2016 09:58:16 +0000
Peter Gutmann <[email-masked]> wrote:

> Uh, faults, as I said in my original message.  Any data corruption,
> bit-flips, RNG faults, anything, and you end up leaking the private
> key.

I'm really interested what you mean here, can you point to concrete
examples of such attacks?

Then main thing I'm aware of that goes into this direction are the
attacks on RSA-CRT. (originally Lenstra 1996, recently reinvestigated
with practical impact by Florian Weimer [1]) Which kinda for me
supports the impression that a seemingly simple alg like RSA has more
brittleness than many people realize.

I heard people speculating on similar attacks on eddsa (the signatures,
not the key exchange), but this was more chatter that something
practical.

[1] https://access.redhat.com/blogs/766093/posts/1976703

-- 
Hanno Böck
https://hboeck.de/

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 28 Oct 2016 17:08:27 +0300

> already foiled attacks that postdate its publication, so you know it's a good

Unfortunately, LTS is a non-starter as web browsers are concerned. And
it is pretty much non-starter as far as everything else is concerned.

It also does not fix the reasons why web browers are first moving DHE
behind fallback and now deimplementing it entierely (because you can't
realistically reject any DHE parameters, but if you dont reject insecure
ones, you get serious security problems. Catch 22.).

Heck, the web browser vendors don't seem to be interested in DHE in TLS
1.3, even after -15 fixed the "DHE downnegotiation" problem (TLS 1.3
draft 15 and forward are not affected by the major trouble DHE causes
in prior TLS versions).

And the "backup" of DHE is unfortunately RSA key exchange, which is
well-known to be very broken (serious security problems).

So the only asymmetric key exchange that actually works is ECDHE
(P-256 or X25519).

-Ilari

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 30 Oct 2016 10:56:48 +0000

Michael Scott <[email-masked]> writes:

>As an influential opinion leader I think you really need to expand on that
>last paragraph. In the first sentence you need to define "harsh environment".
>The second sentence ("any fault of any kind") is manifestly untrue. And in
>the third sentence what industries exactly?

So I've been sitting here trying to figure out how to respond to this (and one
or two other messages).  I think there must be some sort of miscommunication
happening because I can't otherwise explain why you're asking what you are.
The options seem to be:

1. You're unaware of how vulnerable to faults ECC is.
2. You're unaware that computers experience faults.
3. We're talking at cross purposes/miscommunicating in some way.

Before I type up a long essay on #1 or #2 (which I'm not terribly keen on
doing) I want to make sure that you're really asking what you appear to be
asking, and one or both of us hasn't misinterpreted the others' position.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 30 Oct 2016 11:04:48 +0000

Ilari Liusvaara <[email-masked]> writes:

>Unfortunately, LTS is a non-starter as web browsers are concerned. 

Sure, and if you read the -LTS draft you'll see it's not targeted at web
browsers.  I know that this is probably hard for some people to understand,
but there's a lot (an awful lot) of TLS used outside of web browsers.
Unfortunately, like HTTP/2, this use seems to be mostly ignored (in HTTP/2 it
was explicitly ignored, the response on the WG was "let them eat HTTP 1.1"
when the matter was brought up).

>And it is pretty much non-starter as far as everything else is concerned.

Do you have any basis for saying this, or are you just, I dunno, making random
statements?

>It also does not fix the reasons why web browers [...]
>
>Heck, the web browser vendors don't seem to [...]

As I've already said, there are lots of uses of TLS outside of web browsers.

Yes, it's true, there are!  

TLS 1.3/2.0/whatever-it'll-be-called is TLS-for-web-browsers (and content
providers serving them).  TLS-LTS is TLS for everyone else.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 30 Oct 2016 11:11:55 +0000

Hanno Böck <[email-masked]> writes:

>I'm really interested what you mean here, can you point to concrete examples
>of such attacks?

There's so much I don't really know where to start... I've just done a quick
google of "fault attack ecdsa" and got 29,700 hits (OK, lots will be dups :-),
but the first few (de-dup'd) papers are:

  A Fault Attack on ECDSA
  Fault Attacks on Elliptic Curve Cryptosystems
  A Novel Fault Attack Against ECDSA
  Synthesis of Fault Attacks on Cryptographic Implementations
  Fault Attack to the Elliptic Curve Digital Signature Algorithm
  [...]

Real-world attacks would be, for example, the recovery of the PS3 master
signing key due to bad RNG use in ECDSA, equivalent to an RNG fault.

Peter.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 30 Oct 2016 13:12:57 +0200

> asking, and one or both of us hasn't misinterpreted the others' position.

Is ECC even more vulernable to faults than e.g. RSA-CRT? AFAIK, release
even _one_ any way faulty signature computed using RSA-CRT and your
private key walks.

It is so bad that most implementations using RSA-CRT internally
verify the generated signature first. Even if not operating in any sort
of "harsh" environment.

I certainly haven't heard anything similar for ECC. Fault key recovery
attacks yes, but those at least required some degree of control over
the faults, not "one random fault and key walks" RSA-CRT has.

For determininistic ECC signatures, computing the signature twice and
comparing is cheaper than verifying it.

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 30 Oct 2016 13:49:37 +0200

> when the matter was brought up).

Do the devices need to interop with web browsers? 

- If yes, those devices should be designed with newest specs (because
  otherwise those things likely will become stale an cause security
  headaches for _others_). Oh, and ECC asymmetric crypto is the lightest
  here.
- If no, then you should be using top-edge TLS or something non-TLS that
  is competently designed (esp. on constrained environments, as TLS is
  not very economical there, even with pure-PSK).

> Do you have any basis for saying this, or are you just, I dunno, making random

What libraries would implement that? TLS is not exactly simple to
implement. As evidenced by plenty of implementations with very basic
flaws (e.g. not sequencing the handshake properly, or not checking
MACs).

> Yes, it's true, there are!  

Well, I know: I regularly have non-web TLS connections open, some even
with a client certificate.

> providers serving them).  TLS-LTS is TLS for everyone else.

What you think in TLS 1.3 is unsuitable for other usecases (excepting
quite constrained ones, where TLS (any version) is generally overly
complcated).

-Ilari

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 30 Oct 2016 13:01:01 +0000

> providers serving them).  TLS-LTS is TLS for everyone else.

I hope that the WG will adopt TLS-LTS and review it perhaps in January.

---

From: Michael Scott <[email-masked]>
Date: Sun, 30 Oct 2016 17:49:45 +0000

Its dead simple really (so surely must be a miscommunication). For example
you said that "any fault of any kind inevitably ends up leaking the
private key".
This is a technical group, so I expected that this was not some rhetorical
flourish, but you meant exactly what you said. In hindsight (and here is
the miscommunication) it probably was meant as a rhetorical flourish.

A beginner reading that comment might assume that all they have to do is
induce any fault at all anywhere in an ECC binary, and out will pop the
private key. So no reverse engineering required to determine where to
induce the fault, just whack it anywhere.

In my experience the vast majority of "any faults" just cause the program
to rather boringly crash, not revealing nothing to nobody.

Mike

---

From: Tony Arcieri <[email-masked]>
Date: Sun, 30 Oct 2016 13:10:23 -0700

> signing key due to bad RNG use in ECDSA, equivalent to an RNG fault.

Note the common theme here: ECDSA. Using deterministic ECDSA solves the RNG
issue, but opens you up to an additional class of fault attacks.

EdDSA is considerably more resilient to these sort of attacks than ECDSA:

https://books.google.com/books?id=EC0DDQAAQBAJ&lpg=PA192&ots=UHwHH8LGA4&pg=PA182#v=onepage&q&f=false

-- 
Tony Arcieri

---

From: Hanno Böck <[email-masked]>
Date: Sun, 30 Oct 2016 21:33:15 +0100

On Sun, 30 Oct 2016 11:11:55 +0000
Peter Gutmann <[email-masked]> wrote:

> There's so much I don't really know where to start... I've just done
> a quick google of "fault attack ecdsa" and got 29,700 hits (OK, lots
> will be dups :-), but the first few (de-dup'd) papers are:
> 
>   A Fault Attack on ECDSA
> Real-world attacks would be, for example, the recovery of the PS3
> master signing key due to bad RNG use in ECDSA, equivalent to an RNG
> fault.

Peter, I find your line of reasoning very dishonest.

You bring up an example that has nothing to do with ECC. The PS3 issue
is a well known problem of both classic / finite field DSA and ECDSA.
How is that an argument for the brittleness of ECC?

Yeah, we can agree that ECDSA is a bad algorithm. DSA is also a bad
algorithm. But we were talking about key exchanges, so that's really
beside the point here.
We can also agree that fault attacks against ECC can happen. However
that's not the question. The question is whether ECC is more at risk
compared to non-ECC crypto. I don't see evidence for that.

As far as I see several of the papers you mention also talk about
attacks against RSA or DSA.

I have not yet seen an attack that is specific to ECC that is as
devastating and practical as the RSA-CRT fault attacks.

-- 
Hanno Böck
https://hboeck.de/

---

From: Tony Arcieri <[email-masked]>
Date: Sun, 30 Oct 2016 14:20:27 -0700

> around that use it badly.  As there are for almost everything.

FFDH has a massive legacy of insecure deployments. I do not think you can
say the same of ECDH. Granted there are implementations which e.g. fail to
check if points are on the curve (a problem X25519 remedies by design), but
I don't think ECDH in general has issues which are nearly as widespread or
pervasive as they are with FFDH.

-- 
Tony Arcieri

---

From: David Adrian <[email-masked]>
Date: Sun, 30 Oct 2016 22:54:34 +0000

On Fri, Oct 28, 2016 at 2:54 AM Peter Gutmann <[email-masked]>
wrote:

> common TLS mode is still 1.0, dating from 1999.
>

Could you point to some of these surveys?

Thanks,

---

From: Watson Ladd <[email-masked]>
Date: Mon, 31 Oct 2016 01:56:05 +0100

> >I'm really interested what you mean here, can you point to concrete
examples
> signing key due to bad RNG use in ECDSA, equivalent to an RNG fault.

How many of those papers would apply to DSA? What about the vulnerability
of RSA signatures to faults?

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 31 Oct 2016 09:13:59 +0000

Michael Scott <[email-masked]> writes:

>you said that "any fault of any kind inevitably ends up leaking the private
>key". This is a technical group, so I expected that this was not some
>rhetorical flourish, but you meant exactly what you said. In hindsight (and
>here is the miscommunication) it probably was meant as a rhetorical flourish.

Yeah, it was just general complaining about the brittleness of ECC (and some
of the other mechanisms it's used with).  At one end of the scale you've got
some pretty bulletproof/abuseproof modes, CBC with HMAC and -PSK, to which you
can do almost anything and mostly just end up with data corruption
(pathological worst-case with CBC, if you memset() the IV to all-zeroes on
each block, is degradation to ECB), while at the other end of the scale you
have ECC + AES-GCM, a simple fault in the RNG (so repeated k, repeated
counter) means you lose the ECC private key, confidentiality, and integrity-
protection, all in one go.

>private key. So no reverse engineering required to determine where to induce
>the fault, just whack it anywhere.

I think they're probably going to realise it's not as simple as that :-).

>In my experience the vast majority of "any faults" just cause the program to
>rather boringly crash, not revealing nothing to nobody.

If there's a fault and it's unhandled, the watchdog restarts the system.  In
fact that's a standard error-handling strategy, fail-fast, go into an endless
loop until the watchdog restarts the system and the error is cleared.

Peter.

---

From: Antonio Sanso <[email-masked]>
Date: Mon, 31 Oct 2016 09:21:23 +0000

hi Peter,

> protection, all in one go.

isn’t this a consequence of the reuse of GCM n-once rather than ECC fault?

regards

antonio

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 31 Oct 2016 09:39:02 +0000

>Peter, I find your line of reasoning very dishonest.

Uh, it's exactly what it says on the box, if you use a repeated k you're
toast, and a fault in the RNG will give you a repeated k.

>You bring up an example that has nothing to do with ECC. The PS3 issue is a
>well known problem of both classic / finite field DSA and ECDSA. How is that
>an argument for the brittleness of ECC?

Because a faulty RNG won't kill RSA?

>As far as I see several of the papers you mention also talk about attacks
>against RSA or DSA.

Sure, but ECC just seems a lot more vulnerable to these problems than RSA
does.  And then if you want to defend against the problem the cost for a
pairwise consistency check for an RSA sig. is almost free (the public-key op
takes close to no time), while for DSA/ECDSA it has about the same cost as the
private-key op.  Looking at the ever-useful Crypto++ benchmark timings, that
makes a pairwise-consistency-checked ECDSA-256 sig. operation nearly twice as
expensive as a checked RSA-2048 one.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 31 Oct 2016 09:44:50 +0000

Tony Arcieri <[email-masked]> writes:

>FFDH has a massive legacy of insecure deployments. I do not think you can say
>the same of ECDH.

I don't know if you could call the small number of examples shown in various
papers "massive", it's certainly a real issue, but hardly a major one
affecting millions of systems.  In any case though the problem isn't DH or
ECDH, there's no long-term private key to leak, it's how they're
authenticated, with ECDSA, with RSA, or with PSK.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 31 Oct 2016 09:45:58 +0000

>Could you point to some of these surveys?   

Sure, see e.g. the paper referenced in the LTS draft, "TLS in the Wild: An
Internet-Wide Analysis of TLS-Based Protocols for Electronic Communication",
table IV, "Passive monitoring observed connections".  That's for the public
internet, for the non-public (SCADA/embedded/etc) there's no easy way to do a
survey like this so the info is all anecdotal, but there it's pretty much 1.0
all the way (probably helped by the fact that until quite recently that was
what was mandated by major standards like 62351-3.  It's OK though, there was
an addendum to say you were allowed to use AES with it).

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 31 Oct 2016 09:53:15 +0000

>isn’t this a consequence of the reuse of GCM n-once rather than ECC fault?

Well, the RNG affects k so that affects ECC, and it affects the nonce so it
affects GCM integrity and confidentiality.  Fault once, fail everywhere.

Peter.

---

From: Hanno Böck <[email-masked]>
Date: Mon, 31 Oct 2016 10:58:51 +0100

On Mon, 31 Oct 2016 09:39:02 +0000
Peter Gutmann <[email-masked]> wrote:

> >You bring up an example that has nothing to do with ECC. The PS3
> >issue is a well known problem of both classic / finite field DSA and
> >ECDSA. How is that an argument for the brittleness of ECC?  
> 

But a faulty modular exponentiation will.

Just one last thing: Look at the subject of this mail - this discussion
started when I asked whether it's worthy trying to fix DH or if it'd be
better to switch to modern ECC for key exchanges. Now you're making it
a discussion whether ECDSA or RSA is better. (FWIW I would never
recommend replacing RSA with ECDSA, despite all the potnetial hazards
with RSA.) You're constantly shifting the discussion to other topics
trying to make your point that ECC is brittle by including unrelated
things.

This will be my last mail in this thread, I don't find this discussion
helpful in this way.

-- 
Hanno Böck
https://hboeck.de/

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 31 Oct 2016 11:59:20 -0700

On Mon, Oct 31, 2016 at 2:44 AM, Peter Gutmann <[email-masked]>
wrote:

> affecting millions of systems.

I don't know about "millions" (it's hard to say without stats on internal
TLS deployments which aren't visible from the Internet), but Logjam was
pretty pervasive, and also one of the forcing factors for the PCI council
to mandate TLS 1.1 at a minimum by 2018.

-- 
Tony Arcieri

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 1 Nov 2016 00:50:17 +0000

Tony Arcieri <[email-masked]> writes:

>I don't know about "millions" (it's hard to say without stats on internal TLS
>deployments which aren't visible from the Internet), but Logjam was pretty
>pervasive, and also one of the forcing factors for the PCI council to mandate
>TLS 1.1 at a minimum by 2018.

Logjam wasn't really a DH weakness though, it was a "dear God, we're still
using 512-bit keys in 2015?!?!?!?" weakness.  Also, TLS 1.1 won't fix that,
you can use toy keys with any version of the protocol (there's a somewhat
resigned explanatory comment in -LTS next to a SHOULD NOT that says that it
shouldn't be necessary to have an explicit SHOULD NOT for something that was
known to be broken 20 years ago, but that it's necessary because people will
continue to use it otherwise).  

Having said that, using logjam as an excuse to mandate 1.1 was pretty 
crafty :-).

Peter.

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 31 Oct 2016 18:13:51 -0700

On Mon, Oct 31, 2016 at 5:50 PM, Peter Gutmann <[email-masked]>
wrote:

> TLS
> using 512-bit keys in 2015?!?!?!?" weakness.

Rewinding back to my original point:

"FFDH has a massive legacy of insecure deployments. I do not think you can
say the same of ECDH."

-- 
Tony Arcieri