Subject: [Cfrg] draft-irtf-cfrg-randomness-improvements-00 vs currently-deployed alternatives

From: Brian Smith <[email-masked]>
Date: Sat, 2 Jun 2018 18:00:15 -1000

Hi,

Hi all,

Here are the initial questions that came into my haed after my first
skim of draft-irtf-cfrg-randomness-improvements-00 [0]. I'm probably
stating the obvious, but I just thought I'd double-check.

The document says "Sig MUST be a deterministic signature function,
e.g., deterministic ECDSA [RFC6979]."

Let's say you did use Determistic ECDSA as described in RFC 6979. Then
really you've basically implemented a special case of NIST HMAC-DRBG,
perhaps by literally using an HMAC-DRBG implementation as described in
section 3.3 of that RFC [1]. Given that, why not just use your
HMAC-DRBG implementation for the individual nonces too, instead of
implementing draft-cremers-cfrg-randomness-improvements-00 on top of
it? For example, why not use (a variant of) the scheme that Cisco
documented at [2], which they claim is even FIPS-certifiable? It seems
BoringSSL switched to a variant of that as well [3] during their FIPS
certification. I think explicitly stating the advantages of
draft-cremers-cfrg-randomness-improvements-00 over that technique
would be very helpful for people evaluating both.

More generally, it seems problematic to me to require that we seed
this with a *deterministic* signature to start out with. I understand
that we want to protect ourselves against the case where we have
little to no secret entropy. However, isn't it going to be pretty
likely that we have a pretty good amount of secret entropy available
from the beginning? It seems bad to just ignore it when it is probably
available. I think it would be good to reformulate the mechanism in a
way that allowed a possibly-randomized computation to be used instead.

The draft says "Both tags SHOULD be generated such that they never
collide with another accessor or owner of the private key.  This can
happen if, for example, one HSM with a private key is used from
several servers, or if virtual machines are cloned." Isn't it highly
likely that people will fail to follow this recommendation due to the
fact that it's very easy to accidentally break this rule? In fact many
crypto libraries have specific defenses built-in and enabled by
default, based on the assumption that users cannot follow such
recommendations. This seems like one reason why it would be good to
mix in some entropy into the initial key. With that in mind, I think
it would be good to reformulate the mechanism in a way where we feel
comfortable removing this requirement.

[0] https://tools.ietf.org/html/draft-irtf-cfrg-randomness-improvements-00
[1] https://tools.ietf.org/html/rfc6979#section-3.3
[2] https://blogs.cisco.com/security/fips-and-deterministic-ecdsa-achieving-robust-security-and-conformance
[3] https://boringssl.googlesource.com/boringssl/+/783e0957875ac62b35aa4f8741069e133695a3d4

Cheers,
Brian
-- 
https://briansmith.org/

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 8 Jun 2018 19:11:44 +0300

Dear Brian!

Sorry for the delay – all this time we've been discussing the issues you
raised in an off-list discussion among the authors of the draft.

First of all, thank you very much for your questions and comments. They
highlight the issues that haven't been discussed thoroughly enough in the
current version of the draft.

About deterministic signature functions.

Actually the worst case scenario we are defending against is a complete
breakdown of all existing entropy sources (say, because of failure of
hardware RNG) on a certain computer. In this case we don't have even the
initial randomness to feed a DRBG (say, HMAC-DRBG you mentioned), and DRBG
without initialization with good randomness of course does not provide any
pseudorandom properties of outputs. But, yes, if we use (non-deterministic)
ECDSA or, say, EC-RDSA implemented in a separate hardware with a separate
entropy source (say, an HSM with its own RNGs), we can use it. The problem
occurs in another case  - when a random value used in ECDSA/EC-RDSA is
obtained from the same potentially broken entropy source.

According to your comments, we believe that recommendations should be
stated more explicitly in the draft, and comments of what would occur if
one uses a non-deterministic signature scheme (with no additional separated
trusted entropy source) with our techniques. We'll try to address this
issue in the future versions of the draft.

About different tags.

Of course it would be better to mix-in entropy, but we'd like to stress
that the main reason of using the techniques described in our draft is to
address the possible worst-case scenarios of having no working entropy
sources – when we cannot rely on any mixed-in entropy at all.
You cite the following place of the draft: "one HSM with a private key is
used from several servers, or if virtual machines are cloned". In fact the
problem we're trying to address here is the following. If we do not have
any actual entropy, then, in case of using our techniques, we'll leverage
the security of such worst-case scenarios – but – if we also have two
equivalent environments (two cloned virtual machines, for example) and two
tags are equivalent, then we can do nothing at all: no entropy and no
differences between two environments would lead to completely equivalent
outputs.
It seems that we really need to add some explanations about it in the text,
since such questions remain after reading the current version.

Thank you again for your comments, Brian.

We'll try our best to address these issues in the future versions of the
document.

Best regards,
Stanislav

2018-06-03 7:00 GMT+03:00 Brian Smith <[email-masked]>:

> [2] https://blogs.cisco.com/security/fips-and-deterministic-
> ecdsa-achieving-robust-security-and-conformance
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Brian Smith <[email-masked]>
Date: Wed, 13 Jun 2018 17:07:42 -1000

Stanislav V. Smyshlyaev <[email-masked]> wrote:
> hardware RNG) on a certain computer.

The draft says "In the NAXOS key exchange protocol, raw entropy output
x is replaced by H(x, sk), where sk is the sender's private key.
Unfortunately, as private keys are often isolated in HSMs, direct
access to compute H(x, sk) is impossible. An alternate yet
functionally equivalent construction is needed. [...] Implementations
SHOULD apply this technique when indirect access to a private key is
available and CSPRNG randomness guarantees are dubious"

If the private key `sk` is available to the user then one could use
NAXOS or a variant of it.

If the private key `sk` is not available but the HSM lets the user
choose the nonce then the user can extract `sk` from the HSM by using
the standard ECDSA attack, and then use NAXOS or a variant of it.

If the private key `sk` is not available and the HSM rightly doesn't
let the user choose the nonce then the only way one can follow the
recommendation to use a deterministic signature function is if the HSM
implements deterministic ECDSA itself. But it is really uncommon for
an HSM to implement deterministic ECDSA, especially because
deterministic ECDSA is non-compliant with all specifications for
ECDSA. Note: I'm not saying this is good or bad.

The main consequence of this is that, practically speaking, it seems
like one can't really use deterministic ECDSA except in cases where
one could also use NAXOS or a similar thing. Thus the "e.g.,
deterministic ECDSA [RFC6979]" seems to contradict "direct access to
compute H(x, sk) is impossible."

Similarly, APIs for HSMs generally don't let one choose the salt for
PSS signature generation, though in some implementations one can set
the salt length to zero to get a deterministic PSS signature. However,
other work on PSS in TLS has already tried to make it so an
implementation (e.g. mine and a few other new implementations) need
only support specific non-zero lengths of salts. Thus one probably
can't rely on deterministic PSS being available either.

Similarly, TLS 1.3 says that we must use PSS instead of PKCS#1
signatures so a TLS 1.3 implementation wouldn't need to implement
PKCS#1 signing. Further, everybody knows that we shouldn't use the
same private key for two different algorithms, so if we have an RSA
private key for use with TLS 1.3 then we shouldn't use it to make
PKCS#1 signatures; ideally the HSM would enforce that.

Thus, the requirement that "Sig MUST be a deterministic signature
function" seems unrealistic except in cases where a new mechanism may
not even be useful since NAXOS or similar would work fine.

> The problem

Right. One the one hand you don't want to trust the ECDSA's
implementation's RNG. On the other hand, ECDSA implementations don't
generally expose APIs that let you replace their RNG unless they also
give you the raw private key, in which case we wouldn't need to use
ECDSA to derive the initial key.

> Of course it would be better to mix-in entropy, but we'd like to stress that
> the main reason of using the techniques described in our draft is to address
> the possible worst-case scenarios of having no working entropy sources –
> when we cannot rely on any mixed-in entropy at all.

The point I'm trying to make is subtle:
1. Obviously, we don't want to rely on having any entropy.
2. Less obviously, if there is entropy available then it seems silly
to ignore it.

> In fact the
> problem we're trying to address here is the following. If we do not have any
> actual entropy, then, in case of using our techniques, we'll leverage the
> security of such worst-case scenarios – but – if we also have two equivalent
> environments (two cloned virtual machines, for example) and two tags are
> equivalent, then we can do nothing at all: no entropy and no differences
> between two environments would lead to completely equivalent outputs.

There are four cases to consider:
1. A working entropy source is available, and the two tags are the same.
2. A working entropy source is available, and the two tags are different.
3. The entropy source is broken, and the two tags are the same.
4. The entropy source is broken, and the two tags are different.

In your paragraph above, you are describing case #3. But what about case #1?

BTW, I think that you and I may be thinking of different use cases for
draft-irtf-cfrg-randomness-improvements-00. The question I original
set out to answer is "Would it be better to use
draft-irtf-cfrg-randomness-improvements-00 instead of RFC 6979 when
implementing ECDSA?" From re-reading the draft I think that target use
case might have been more about "How can we strengthen key agreement
(e.g. ECDH)?"

Since I posted my question I actually came up a few with more
questions, but the general question I think is still unanswered is
"Why is this mechanism better than using other established
mechanisms?" In particular, why is this mechanism better than a
variant of NAXOS or better than using the HMAC DRBG? Speaking from my
own experience and motivation for reading thedocument, that's the main
question that I think is left unanswered in the draft.

Cheers,
Brian

---

From: Christopher Wood <[email-masked]>
Date: Sat, 16 Jun 2018 10:06:17 -0700

Hi Bryan,

Apologies for the delay. Please see inline below.

On Wed, Jun 13, 2018 at 8:07 PM Brian Smith <[email-masked]> wrote:
> own experience and motivation for reading the document, that's the main

I think the delta between what's proposed and what's implemented is
small. This is what's proposed:

  PRF(KDF(G(x) || H(Sig(sk, tag1))), tag2)

Here, G(x) is the CSPRNG, which uses whatever entropy is available at
the time on the caller, which
is not necessarily where the signature is computed. The input to the
KDF is thus effectively whatever
randomness is available and a function of the private key, which I'll
denote as r. The construction then
simplifies to:

  PRF(KDF(r), tag2)

This is basically HKDF -- Expand(Extract(r), tag2, x). (I would prefer
it be rewritten using this common terminology
to make it more readable.) It could also be recast as the HMAC DRBG as
outlined in Section 3.3 of RFC 6979
by setting entropy_input to r and nonce to bits2octets(H(tag2)), for example.

So the difference between this and NAXOS or HMAC DRBG as specified in
Section 3.3 is how the private key
is used. In both NAXOS and RFC 6979, it's assumed the caller has
direct access to the private key, which is not
the assumption here. That's the extent of the difference, as I see it.
Do you think unifying terminology around RFC
6979 would help emphasize that difference?

Thanks,
Chris