Re: [TLS] Require deterministic ECDSA
Hi, Mike > On 24 Jan 2016, at 2:53 AM, Michael StJohns wrote: > > On 1/23/2016 7:17 PM, Yoav Nir wrote: >> 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 > > 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? 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 ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] Require deterministic ECDSA
> On 24 Jan 2016, at 2:47 AM, Michael StJohns wrote: > > On 1/23/2016 2:13 PM, Joseph Birr-Pixton wrote: >> 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 >> >> ___ >> TLS mailing list >> TLS@ietf.org >> https://www.ietf.org/mailman/listinfo/tls >> > > 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. 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 ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] Require deterministic ECDSA
On Sun, Jan 24, 2016 at 2:12 AM, Yoav Nir wrote: > Hi, Mike > >> On 24 Jan 2016, at 2:53 AM, Michael StJohns wrote: >> >> On 1/23/2016 7:17 PM, Yoav Nir wrote: >>> 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 >> >> 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? > > 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. 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 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. 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. > > Yoav > > > > ___ > TLS mailing list > TLS@ietf.org > https://www.ietf.org/mailman/listinfo/tls -- "Man is born free, but everywhere he is in chains". --Rousseau. ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] Require deterministic ECDSA
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. On Sat, Jan 23, 2016 at 7:13 PM, Joseph Birr-Pixton wrote: > 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 > > ___ > TLS mailing list > TLS@ietf.org > https://www.ietf.org/mailman/listinfo/tls ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] Require deterministic ECDSA
On 1/24/2016 5:15 AM, Yoav Nir wrote: >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. 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 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. ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
Re: [TLS] Require deterministic ECDSA
On 1/24/2016 5:12 AM, Yoav Nir wrote: 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. 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 ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
[TLS] Fwd: Re: Require deterministic ECDSA
Sorry - I hit the wrong "reply to" button. Forwarded Message Subject:Re: Require deterministic ECDSA Date: Sat, 23 Jan 2016 20:52:53 -0500 From: Michael StJohns To: Geoffrey Keating On 1/23/2016 8:05 PM, Geoffrey Keating wrote: Michael StJohns writes: On 1/23/2016 2:13 PM, Joseph Birr-Pixton wrote: 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 ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls 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. A test suite can easily determine, if it knows the private key in use by the implementation under test, whether that implementation is generating RFC 6979 deterministic signatures or not. That seems to me an adequate enforcement mechanism. Um.. not really. The actual worked example is FIPS. There are lots of FIPS TLS implementations and they all go through testing (your proposed enforcement mechanism), and there is exactly NO way for one FIPS implementation to ensure that it is talking to another FIPS implementation. The best they can do is limit the offer and acceptance of specific crypto suites. MUST or "Required" in IETF parlance is usually reserved for choices that have to be made to have interoperable products. Neither FIPS nor deterministic ECDSA rise to that level.FIPS at least recognizes that and imposes its requirements on the buyers (US Gov't and US Gov't contractors) who then ask for FIPS capable products. And people who want to sell to the government then make FIPS capable products that ... wait for it... interoperate with non-FIPS products. From 2119: In particular, they MUST only be used where it is actually required for interoperation or to limit behavior which has potential for causing harm (e.g., limiting retransmisssions) For example, they must not be used to try to impose a particular method on implementors where the method is not required for interoperability. Or would you argue that I'm misinterpreting the above and the impact of your suggested change? (Um.. in the above "causing harm" has usually been interpreted to mean "harm to the network" - not preventing stupidity in implementation). Later, Mike ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
