Re: [Cfrg] key as message prefix => multi-key security

["D. J. Bernstein" <[e-mail]>]

I now have a paper online analyzing multi-user signature security:

   http://cr.yp.to/papers.html#multischnorr

There's also a separate project analyzing the security of EdDSA's
r-generation mechanism. Nothing is online yet from that project but the
quantitative multi-user security results look completely satisfactory
_assuming_ a double-length hash.

Overall I'd say that the multi-user proof picture is shaping up nicely,
leaving very few ways that an attack breaking 1 out of N signature keys
could be faster than an attack breaking a single targeted key. However,
I see one remaining theoretical concern, and there are ways that Ed25519
signers could be tweaked to eliminate this concern; I think this is
worth some discussion.

Background: Let's say you're an attacker trying to break 1 of N discrete
logs. Assume that each of the N users has chosen a scalar completely at
random from {0,1,...,l-1}, where the base point has prime order l. Can
you succeed more quickly for large N than for N=1?

The answer is no. Any algorithm that breaks 1 of N discrete logs can be
reused to break a single targeted discrete log at the same speed and
with the same success probability:

   * Take the original target kB.

   * Choose random r_1,r_2,...,r_N.

   * Apply the 1-of-N algorithm to kB+r_1 B,kB+r_2 B,...,kB+r_N B.

   * If the 1-of-N algorithm successfully finds the jth discrete log
     k+r_j mod l, simply subtract r_j mod l, and you've successfully
     found k.

The point is that discrete logs in {0,1,...,l-1} have a "random
self-reduction", a very strong type of "worst-case-to-average-case
reduction".

Now here's the theoretical concern in a nutshell. Assume that each of
the N users has instead chosen a scalar from the half-size interval
{0,1,...,ceil(l/2)-1}. Does this help you?

This is pretty much the situation in Ed25519. The range of secret
scalars in Ed25519 is chosen to match the range of secret scalars in
X25519, for people who want to reuse X25519 code; X25519 chooses that
range as 2^251 through 2^252-1 (times a factor of 8 that isn't relevant
to this analysis), so that a "start with the first 1 bit" Montgomery
ladder has constant length, while people who reuse Weierstrass code
don't bump into infinity; l is slightly above 2^252 in Curve25519. Is
this an issue?

For N=1 this is a well-known question. On the provability side, the same
random self-reduction shows that you can't gain more than a factor F in
success probability from targeting an interval of size l/F. On the
cryptanalysis side, "kangaroos" do gain a probability factor roughly
proportional to F (with sqrt(l/F) computations, kangaroos have success
probability roughly 1, while "rho" against the whole interval has
success probability only roughly 1/F), but they also lose a constant
factor, and after tons of work on the constant factor there still
doesn't seem to be any gain for F=2. I already commented on this in a
message last year.

For N>1, however, I don't see any literature on this question. The same
random self-reduction shows that the probability gain can't beat F^N,
but that's not useful when N is large and F is noticeably larger than 1.
A different argument produces an upper bound of NF, but that's still not
satisfactory. In Section 5 of the multischnorr paper I've outlined a
tight proof compared to finding 1 discrete log in an interval of length
l/NF, but that's also not satisfactory.

Even if the rho probability curve is optimal, all of these proofs are
consistent with speedup factors proportional to sqrt(min{F^N,NF}): e.g.,
breaking 1 of 2^40 keys with F=2 in only 2^105 operations.

The looseness here is much smaller than the looseness in, e.g., the
Pointcheval--Stern reduction from single-key discrete-log attacks to
single-key generic-hash Schnorr-signature attacks. However, those two
problems are tightly related for generic-group attacks, and Schnorr
signatures are well known to cryptanalysts; many experts would be
surprised if there were a way to exploit the Pointcheval--Stern
looseness for Schnorr signatures on any standard elliptic curve. For
comparison, I think that

   * generic-group analyses and
   * actual cryptanalytic efforts

are both missing for the 1-of-N interval question.

Here are two ways to eliminate this concern:

   * Take an extra bit in the Ed25519 secret scalars: specifically,
     take a 256-bit scalar, clear bit positions 0 1 2, and set bit
     position 255 (rather than setting 254 and clearing 255). This is,
     aside from the factor of 8, the same as taking the range 2^252
     through 2^253-1.

     This would also work for X25519, so it's still compatible with a
     merged code base. It _does_ mean, for both X25519 and Ed25519, that
     there's no longer a structural prohibition on key 0, and on staying
     away from infinity in standard Weierstrass scalarmult methods. Of
     course, the key hashing in Ed25519 means that even a malicious RNG
     can't target any particular scalars, and maybe the same type of
     hashing should also be done for X25519. (On the other hand, X25519
     was designed from the outset to be usable without hash functions.)

   * Hide the top bit of the scalars: i.e., send |A| rather than A,
     where A is the public key. This is tantamount to expanding the key
     interval to {-2^252+1,...,-2^251,2^251,...,2^252-1}, which is
     indistinguishable from {0...l-1}, so it should reenable the usual
     random self-reduction.

     X25519 already does something equivalent to this. For Ed25519 it's
     simplest to clear the Edwards x sign bit in public keys, and
     include a constant-time conditional negation of the scalar in the
     signing procedure.

Both of these are compatible with existing Ed25519 verifiers. For the
first approach there's an issue of testing Weierstrass implementations,
but I'm not sure this noticeably affects the probability of obtaining
security with such implementations in any case. The second approach is
fingerprintable, and if it becomes popular enough then people might
start leaving out the corresponding conditional negation in verifiers---
so if this is going to be done at all then it would be best for everyone
to agree on doing it.

The parameter examples in the EdDSA paper already take the first
approach for Ed41417, Ed448, and Ed521. In each of these cases, l is
slightly _below_ a power of 2 rather than slightly above, so there's no
hope of structurally avoiding the 0 cases anyway. Does anyone care?

---Dan