Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

[Watson Ladd <[e-mail]>]

On May 7, 2015 8:45 AM, "Dan Brown" <[e-mail]> wrote:
>
>
> > -----Original Message-----
> > From: Watson Ladd [mailto:[e-mail]]
> >
> > On Wed, May 6, 2015 at 8:39 AM, Dan Brown <[e-mail]>
> > wrote:
> > > Accordingly, I now amend my proposal to k = F(m,a,t) where F is some
> > > to-be-specified cryptographically strong deterministic function, m is
> > > the message, a is the actual long-term (signing) key, and t is a
> > > temporal value (tweak/nonce), preferably secret and unpredictable, or at
> > least non-repeating, optionally fixed (including empty: reducing the signature
> > scheme to an outright deterministic signature scheme), and not under any
> > influence from an adversary.
> >
> > I think that if we worry about kleptography, t should not be used.
>
> [DB] Good catch.  So, that cost should be weighed against the gains from using t.
>
> Just to expand: is your concern about the following kleptographic malware? The malware lets multiple t values be generated (honestly), say t_1, t_2, ... t_n, and then search the corresponding k_1, ..., k_n for a value k_i that suffers from bias needed to make a lattice attack work? The kleptographic malware then lets k=k_i through to per a normal signature.

Exactly.

>
> >
> > >
> > > When k is used in signatures, this approach could be called tweakably
> > deterministic signatures, although I would prefer to call it message-dispersed
> > signatures (to avoid the silly pitfall I mentioned of over-generalizing the value
> > of determinism in key generation).
> > >
> > > The changes my previous proposal have brought my current proposal closer
> > to deterministic signatures than to purely randomized signatures. The tweak
> > value t helps to address some of the potential pitfalls of purely deterministic
> > signatures that I listed in my previous email.  Please let me know if you think
> > the cost of tweaking outweighs the gains I described.
> > >
> > > So, I'm not intending to be critical of deterministic signatures, or to
> > support/defend past pure PRNG-based or underspecified randomized
> > signatures, but rather to be in support something slightly securer than either,
> > by combining the good features of both randomized and deterministic
> > signatures.  Yet more reasons and responses in-line below.  So, please take
> > them with a grain of salt, and read them in the light of trying make things
> > securer.
> >
> > How is this proposal more secure, i.e. what properties does it have, that
> > protocols rely on, that EdDSA doesn't?
> >
> [DB] Maybe I was unclear above: the tweak tries to address the issues I labelled 3a..3h in the first email I sent.  If you have time to spare, then please consider these issues.  I think you know that Bernstein responded to 3a...3h already, so I would fully understand if you didn't want to waste any time.

As far as I can tell, only 3a and 3h involves anything that actually
can be analyzed. And the results in 3h, knowing that ROM=>PRF and we
need ROM (or generic group model) for Schnorr security, are not good
for your position. (I don't know if generic group implies PRF exists,
and my earlier comment on PRF->collision was completely bogus, when
looking at multiple queries) 3a is actually a reasonable argument, but
there are quite a few cases where power analysis doesn't matter.

>
> >
> > Let me see if I have this correct. You're arguing that an implementor, told to
> > compute k=F(m, x), and go through some more steps, will skip that step. Fine:
> > they evidently skipped the random number generation step. But at that point
> > we might as well specify an implementor who skips over comparison steps in
> > signature verification.
>
> [DB] Wasn't there were real world examples (goto fail???) of signature verification steps being accidentally skipped?  I'm trying to see if the point of your paragraph is to compare realisms of two failure modes, or to just give up on protecting against attack X because we cannot protect against attack Y. ASIDE: implicit certificates, e.g. SEC4 (includes IPR), can _sometimes_ address this failure to verify a cert, because of instead of a verification step to miss it absorbs the authentication right into the use of the public key.

No, it's to point out that once you assume the implementor isn't
reading the spec, there is nothing you can do. I don't see how your
proposal makes this better. In fact it makes it worse in a number of
ways, and makes implementations more complicated.

First, you are proposing that the "implementation" include a DRGB,
that gets instantiated once, and called multiple times. That's
incompatible with threads in C, unless the library author forces
applications to call per-thread initialization functions, etc, etc. Of
course, encryption libraries essentially need to do this, but there's
a workaround: open /dev/urandom once, and use the fact that read is a
threadsafe system call. Some operating systems have a systemwide
random number generator that is a single, nonfailing, call. Libraries
that require randomness can use it. But that's not all operating
systems. Some CPUs have an instruction that can be used to generate
random data. But that isn't universal.

Once we decide to make a DRGB, with the possibility of injecting
seeds, applications have to remember not to do this, but to seed the
DRGB correctly before using. But now we have a Big Red Button, which
if pushed utterly destroys security. Libraries that require strong
randomness should use standard system provided means to obtain it, and
should not offer alternatives with no security. Fork security, and VM
restarts are good reasons not to do this. (Passing in a secret key for
testing does not have this problem: it's exactly the same interface as
used when using the code not in testing).

With your amended proposal, signatures remain secure even with bad
randomness (unless we have kleptographic bugs, induced by our good
friends at Fort Mead). So what exactly is the point of having all this
extra code lying around, and dependencies on randomness?

Of course, you've stated that implementors should be permitted to make
deterministic signatures instead, but we should warn people that this
is less secure and not recommended. Instead we should recommend design
decisions which weaken, not strengthen, security, increase the volume
of code to be written, and make certain design decisions impossible.

Sincerely,
Watson Ladd