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

[Brian Smith <[e-mail]>]

Stanislav V. Smyshlyaev <[e-mail]> wrote:
> 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.

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
> occurs in another case  - when a random value used in ECDSA/EC-RDSA is
> obtained from the same potentially broken entropy source.

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