Subject: [TLS] Require deterministic ECDSA

From: Joseph Birr-Pixton <[email-masked]>
Date: Sat, 23 Jan 2016 19:13:40 +0000

Hi,

I'd like to propose that TLS1.3 mandates RFC6979 deterministic ECDSA.

For discussion, here's a pull request with possible language:

https://github.com/tlswg/tls13-spec/pull/406

Cheers,
Joe

---

From: Joseph Birr-Pixton <[email-masked]>
Date: Sat, 23 Jan 2016 19:59:15 +0000

Hi,

The other benefit is being able to test that a critical code path
produces the correct answers. With randomised k, this is not really
possible. For instance, you can choose k with the top bit clear
without any obvious or externally-testable effects, except effectively
publishing your long-term private key after a large number of
signatures[1].

Given the history of these things, I would perhaps challenge the
assumption that all TLS stacks will have a bug-free, thread-safe,
fork-safe, high quality, uncompromised, backdoor-free, unbiased random
number generator :)

Cheers,
Joe

[1]: http://people.rennes.inria.fr/Jean-Christophe.Zapalowicz/papers/asiacrypt2014.pdf

On 23 January 2016 at 19:27, Jacob Maskiewicz <[email-masked]> wrote:
> The main argument I see from the RFC for deterministic ECDSA is computing k
> on systems without high quality entropy sources. But any system running a
> TLS stack is already going to have a high quality entropy source for
> client/server randoms and IVs and such, so what's the benefit of
> deterministic ECDSA here?
>
> -Jake M
>
> On Jan 23, 2016 11:13 AM, "Joseph Birr-Pixton" <[email-masked]> wrote:
>>
>> Hi,
>>
>> _______________________________________________
>> TLS mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/tls

---

From: Geoffrey Keating <[email-masked]>
Date: 23 Jan 2016 12:16:29 -0800

[I guess we're top-posting...]

Another benefit is that if it turns out the entropy source is broken,
then if client/server random or IV is guessable, that's something that
affects one connection and can be addressed for future connections by
fixing the entropy source.  But if k generation is broken, then that
leaks the key permanently and you need to get a new one and revoke the
old one, which may be difficult.

Perhaps the RFC should say something to that effect?  I think there's
already a section in the security considerations about random number
generators.

---

From: Yoav Nir <[email-masked]>
Date: Sun, 24 Jan 2016 02:17:27 +0200

Also if the signatures are done in a separate hardware module, that module is even less likely to have a good random source. 

And if we make it rely on external input for the random, that’s a good way of getting it to reveal information about the private key, whereas keeping the private key secret forever was the whole point of using a hardware module.

So that’s another argument in favor of deterministic signatures.

Yoav

> On 23 Jan 2016, at 9:59 PM, Joseph Birr-Pixton <[email-masked]> wrote:
> 
> Hi,
>

---

From: Michael StJohns <[email-masked]>
Date: Sat, 23 Jan 2016 19:47:11 -0500

> https://github.com/tlswg/tls13-spec/pull/406

Correct me if I'm wrong but:

1) A receiver of an deterministic ECDSA signature verifies it EXACTLY 
like they would a non-deterministic signature.
2) A receiver of an ECDSA signature cannot determine whether or not the 
signer did a deterministic signature.
3) A TLS implementation has no way (absent repeating signatures over 
identical data) of telling whether or not a given signature using the 
client or server private key  is deterministic.

  All that suggests that this is a completely unenforceable requirement 
with respect to TLS.

The above is a long way of saying that this is a WG overreach on 
internal security module behavior that is not central, cognizable or 
identifiable to a TLS implementation.

I'd instead recommend you approach the CFRG and offer a internet draft 
with a target of BCP on the general topic of ECDSA rather than specific 
guidance for TLS.

Mike

---

From: Michael StJohns <[email-masked]>
Date: Sat, 23 Jan 2016 19:53:43 -0500

> So that’s another argument in favor of deterministic signatures.

I tried to parse the above into meaningful A implies B logic and failed.

If you have an HSM, the key that's generating the signature tends to be 
generated inside the HSM.  If your HSM has a bad RNG, then the key 
generation is going to be a problem well before the signature generation 
RNG problem kicks in.   And to clarify, a key generated inside an HSM 
tends to use that HSM's signature mechanism, not something in a separate 
module.

I don't think your argument holds.

"If we make it rely on external input for the random"???   Isn't that 
exactly what the RFC uses in the form of the hashed message?

Mike

---

From: Michael StJohns <[email-masked]>
Date: Sat, 23 Jan 2016 20:00:40 -0500

On 1/23/2016 3:16 PM, Geoffrey Keating wrote:
> But if k generation is broken, then that

I agree that if RNG generation is broken then it breaks k generation.    
But if RNG generation was broken during key generation, you also have a 
problem.

In your arguments, assuming that the RNG was fine for key generation and 
broken for signature generation IMHO only applies to software modules 
(where you have the option of using separate RNGs for different functions).

For HSMs with any reasonable amount of good design, if the RNG is bad, 
the thing just stops working (and there are ALL sorts of tests to ensure 
that).

With respect to a software module, I'd find it easier just to read the 
key bits out of memory than apply most of the other threats that seem to 
be creeping into the argument.

Later, Mike

---

From: Brian Smith <[email-masked]>
Date: Sat, 23 Jan 2016 19:20:48 -1000

> I'd like to propose that TLS1.3 mandates RFC6979 deterministic ECDSA.

What about the way BoringSSL (and OpenSSL, I think) does it? It
incorporates all the inputs that RFC6979 does, but using SHA-512 instead of
HMAC. And, it also includes a random element in the SHA-512 hash.

Ed25519 uses SHA-512 instead of HMAC for the same purpose and people seem
to think it works fine.

Also hashing in some randomness seems like it would help avoid some side
channel leakage. Note that most (all the ones I've looked at for more than
5 minutes) open-source ECDSA implementations have side-channel issues of
various levels of significance.

Anyway, I do think that implementations should do something *like this* to
avoid problems when the RNG is bad, but I think prescribing RFC 6979 as the
solution is overly-specific, especially when it doesn't even seem to be the
best way to accomplish the goal in many cases.

Cheers,
Brian

---

From: Dave Garrett <[email-masked]>
Date: Sun, 24 Jan 2016 02:04:28 -0500

> All that suggests that this is a completely unenforceable requirement 

We can have unverifiable & unenforceable MUSTs. A SHOULD might be more appropriate, however, if we want to acknowledge this limitation to some degree.

> identifiable to a TLS implementation.

As far as I'm concerned, anything that directly affects the security of TLS is not an overreach. Beyond scope of control, yes, but it's not an overreach to lay out how to do things properly that commonly result in vulnerabilities with TLS. Like everything else in an RFC, it can of course be ignored, but I think it's worth it to make an official statement in the spec on how to do things properly.

Dave

---

From: Yoav Nir <[email-masked]>
Date: Sun, 24 Jan 2016 12:12:57 +0200

Hi, Mike

> On 24 Jan 2016, at 2:53 AM, Michael StJohns <[email-masked]> wrote:
> 
> If you have an HSM, the key that's generating the signature tends to be generated inside the HSM.  If your HSM has a bad RNG, then the key generation is going to be a problem well before the signature generation RNG problem kicks in.   And to clarify, a key generated inside an HSM tends to use that HSM's signature mechanism, not something in a separate module.
> 
> "If we make it rely on external input for the random"???   Isn't that exactly what the RFC uses in the form of the hashed message?

Yeah, it was way past midnight when I wrote that. Only so much coherence in those hours.

The HSM has enough entropy to generate (once) a 256-bit (or 384-bit or 521-bit) key. When working as part of a TLS server using regular ECDSA it would need to generate a random k for each full handshake, and many such servers routinely handle tens of thousands of such handshakes per second. So it’s hundreds of kilobytes per second, for an HSM that has no network input, no I/O of any kind other than the signature requests, this may be a problem. I’ve seen people claim this in the past.

That last sentence there. If we’re using regular ECDSA, the HSM can either generate its own k or receive a k from the caller. For our software’s FIPS certification we had to support both modes to be able to produce a predictable ECDSA. I don’t know, but I imagine hardware would be required to support this as well. If you run the HSM in production with the external random input, you’re making it possible for an attacker who has compromised the system to discover the key bits by repeatedly calling the HSM with same k’s for different inputs. This is negated by using deterministic ECDSA where the k is a function of the input.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Sun, 24 Jan 2016 12:15:32 +0200

> On 24 Jan 2016, at 2:47 AM, Michael StJohns <[email-masked]> wrote:
> 
> 1) A receiver of an deterministic ECDSA signature verifies it EXACTLY like they would a non-deterministic signature.
> 2) A receiver of an ECDSA signature cannot determine whether or not the signer did a deterministic signature.
> 3) A TLS implementation has no way (absent repeating signatures over identical data) of telling whether or not a given signature using the client or server private key  is deterministic.

I might be missing something, but if k is deterministic, do we really need to send it? Can’t the receiver figure it out the same way that the sender did?

I know that makes it break compatibility, but since this is TLS 1.3 anyway, that’s not an issue, I think.

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Sun, 24 Jan 2016 08:25:01 -0800

> The HSM has enough entropy to generate (once) a 256-bit (or 384-bit or 521-bit) key. When working as part of a TLS server using regular ECDSA it would need to generate a random k for each full hand…

Standard conjectures in cryptography imply that counter mode for short
messages is indistinguishable from random data. A device with 256
random bits can create a long random key . Maybe the issue is the HSM
isn't made by people who know the first thing about cryptography, who
believe the widely peddled nonsense about entropy.

> That last sentence there. If we’re using regular ECDSA, the HSM can either generate its own k or receive a k from the caller. For our software’s FIPS certification we had to support both modes to b…

The whole point of HSMs is to protect keys, by denying the ability to
use the API in ways that reveal keys. Providing k along with the
message breaks that entirely.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Filippo Valsorda <[email-masked]>
Date: Sun, 24 Jan 2016 17:19:16 +0000

Strong support for this. TLS will be deployed with broken
implementations and on broken systems. Anything the spec can do to
limit or prevent damage is more than appropriate.

However, agreed that a SHOULD makes more sense, to avoid having
discussions about OpenSSL not being compliant because of a different
PRF.

I've always been puzzled by pure-random ECDSA deployments anyway.

---

From: Michael StJohns <[email-masked]>
Date: Sun, 24 Jan 2016 13:08:39 -0500

> I know that makes it break compatibility, but since this is TLS 1.3 anyway, that’s not an issue, I think.

Hi Yoav

If K is known and the signature is known then the private key is known.

The particular method the RFC uses to create the signature is to 
incorporate the signing private key as part of the input to the 
pseudo-random generation of K (along with the message).  The receiver 
doesn't have the private key and so can't derive K (which is a *GOOD* 
thing - see the point above.  :-) )

Mike.

---

From: Michael StJohns <[email-masked]>
Date: Sun, 24 Jan 2016 13:24:58 -0500

> The HSM has enough entropy to generate (once) a 256-bit (or 384-bit or 521-bit) key. When working as part of a TLS server using regular ECDSA it would need to generate a random k for each full hand…

This *really* isn't how most HSMs work.  They mostly have TRNGs (True 
Random Number Generators) aka Hardware RNGs based on noisy diodes or 
ring oscillators or some such (e.g. no stupid linux like entropy source 
from keyboard motion or network interrupts).  This gets fed into a PRBG 
construct - something like the ones in SP800-90A.  Which does the 
entropy expansion/extraction to get you pretty much any number of bits 
you want of good quality randomness in plenty of time to do handshakes.

There's actually a cool set of USB devices that provide *very* good 
TRNG.    Take a look at 
http://ubld.it/products/truerng-hardware-random-number-generator/ or 
http://ubld.it/ and the drivers (or internal logic) feed what they get 
from the TRNG into a good PRBG.  I've been playing with using them as an 
augmentation of how I generate keys.

If you're stuck on commodity hardware (e.g. intel motherboard)  and 
worried about randomness, there's also this: 
https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide. 
Later versions of the intel platform have a TRNG embedded in them as 
well as an SP800-90A PRBG.

One of the things about FIPS and RNGs is that there is a pretty good set 
of requirements AND tests that can be used to establish just how good of 
an RNG source you have (and provide pretty good error detection and fail 
logics).

Later, Mike

---

From: Hubert Kario <[email-masked]>
Date: Mon, 25 Jan 2016 12:35:47 +0100

On Sunday 24 January 2016 02:04:28 Dave Garrett wrote:
> > 2) A receiver of an ECDSA signature cannot determine whether or not
> > the signer did a deterministic signature.
> We can have unverifiable & unenforceable MUSTs. A SHOULD might be more
> appropriate, however, if we want to acknowledge this limitation to
> some degree.

a MUST is only necessary if you are not sure or simply know that your 
RNG is broken, if you're doing a HSM implementation you know that your 
RNG is good so you can just use it

and while we can have unverifiable MUSTs, it just looks silly if you do, 
especially if the other way of doing things is just as interoperable, 
and just as secure (if implemented properly) as the mandated one...

SHOULD with explanation why it's there is definitely better approach
-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

---

From: Jacob Maskiewicz <[email-masked]>
Date: Sat, 23 Jan 2016 11:27:36 -0800

-Jake M

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 25 Jan 2016 15:08:37 +0000

> But any system running a TLS stack is already going to have a high quality entropy source for client/server randoms and IVs and such

That's assuming a constraint that isn't accurate.

---

From: Adam Langley <[email-masked]>
Date: Mon, 25 Jan 2016 07:19:02 -0800

On Sat, Jan 23, 2016 at 9:20 PM, Brian Smith <[email-masked]> wrote:
> What about the way BoringSSL (and OpenSSL, I think) does it? It incorporates
> all the inputs that RFC6979 does, but using SHA-512 instead of HMAC. And, it
> also includes a random element in the SHA-512 hash.
>
> Ed25519 uses SHA-512 instead of HMAC for the same purpose and people seem to
> think it works fine.
>
> channel leakage. Note that most (all the ones I've looked at for more than 5
> minutes) open-source ECDSA implementations have side-channel issues of

I wrote that design before RFC6979 (or, at least, before I was aware
of it). The reason that I included randomness into the mix was because
I worried that someone might be depending on the randomised nature of
ECDSA signatures and suddenly making them deterministic seemed like a
risky thing to do. That's not a problem in TLS.

I think that those implementations that care about DPA-level
side-channel attacks will probably do their thing no matter what the
standard says, so I wouldn't have an objection to putting a "SHOULD"
in the spec for RFC 6979. I suspect that adherence would be poor,
however. As for using that RFC over what I came up with or anything
else: at least RFC 6979 has been written down already.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Yoav Nir <[email-masked]>
Date: Mon, 25 Jan 2016 21:10:13 +0200

> On 25 Jan 2016, at 5:08 PM, Salz, Rich <[email-masked]> wrote:
> 

Eh. Just s/is/should/

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 25 Jan 2016 19:25:37 +0000

> is/should, or they're going to have other problems. 

Really?

Some high-value device that is rarely connected-to?  Like a missle?

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Mon, 25 Jan 2016 14:36:08 -0500

>> That's assuming a constraint that isn't accurate.

Remember that keys (whether in HSMs or not) can be moved between
implementations.  While it seems (hopefully) likely that most keys will
usually be used with a TLS stack with a high-quality entropy source,
it's also possible that the key gets used occasionally with some other,
less sophisticated code or platform.

We should be pushing heavily for deterministic ECDSA, even though it's
not something we can require via wire protocol at runtime.

   --dkg

---

From: Joseph Birr-Pixton <[email-masked]>
Date: Mon, 25 Jan 2016 20:15:54 +0000

Thanks for the discussion so far on this.

I've closed PR 406; it is replaced by:

https://github.com/tlswg/tls13-spec/pull/408

to wit:

- ECDSA details para says RFC6979 is RECOMMENDED (I've tried to keep
this part succinct, but I think it fits next to the X9.62 reference).
- Crypto pitfalls section has a new point with a little further
discussion, trying to impress upon the reader how badly this goes
wrong.

Cheers,
Joe

---

From: Watson Ladd <[email-masked]>
Date: Mon, 25 Jan 2016 12:38:30 -0800

> Some high-value device that is rarely connected-to?  Like a missle?

If you can't generate 256 random bits for use as a DH key or a client
random, anyone can read the connection if they know what the random
number generator actually produced. If you can produce 256 random
bits, and the device maker was halfway competent, they should know how
to turn 256 random bits into computationally indistinguishable
infinite stream of random bits. If your missile maker was not halfway
competent at computer security, I can only hope the guidance engineers
were of the same caliber.

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 25 Jan 2016 20:42:34 +0000

And your lightbulb maker?  Or your stove maker?  Or your fridge?  All on coming IoT?

---

From: Jacob Maskiewicz <[email-masked]>
Date: Mon, 25 Jan 2016 11:21:47 -0800

-Jake M

---

From: Bill Cox <[email-masked]>
Date: Mon, 25 Jan 2016 16:41:48 -0800

Just an off-topic point about the missile example... Thankfully, the Air
Force seems to have the sense to follow the KISS rule now and then.  I
would be shocked to see TLS in the launch flow :)  Can you imagine the
handshake?  Hopefully this humorous rather than poor taste:

Command: Here's everything you need in one flight of packets to launch.
Missile: Please send a CertificateVerify, and let's do a 1-RTT.  I'll just
ignore that launch command.  Here's my new server-config so you can learn
to speak to me properly.  I rotate it ever 7 years to provide
forward-secrecy.
Command: Here's my cert, and another launch command.  I was supposed to
resend it, right?  Let's not tell the application layer that I sent the
launch command twice, or that my first flight is replayable.
Missile: Symantec, really?  What about certificate transparency?  Was I
supposed to include that first launch command in the handshake hash?  :-p

I have low expectations for IoT vendors' TRNGs.  When deadlines get tight,
good engineering on the TRNG is easy to drop.  As long as they whiten the
output, it is very difficult to detect TRNG flaws, so there is little
incentive to put in much engineering.  IIRC, the FIPS standard requires
vendors to be secretive about their TRNGs.  They are not allowed to give us
access to the raw data from the entropy source, and cannot show us
schematics for their design, making it nearly impossible to differentiate a
well designed TRNG from an insecure one.

Basically, it is a poor assumption that the TRNG is any good.  Sure, it's
required for secure crypto, but whatever...

Bill