Re: [Cfrg] Why hash verifier's key?

[Dan Brown <[e-mail]>]

I think there's a similar random self-reduction for some kinds of ECDSA forgeries, but not Schnorr or ECDSA_CFRG or ECDSA with hashed public key. Chances are I'm wrong, again, but before I forget I'll sketch it out.
‎
‎Goal: forge M under public key A.
Use: 1 of n forger.

choose messages M_1, ..., ‎M_n.
choose public keys A_j = H(M_j)/H(M) A
run 1 of n forger: ask it to forge M_j under A_j for some j.
Obtain for‎gery (r_j,s_j) of M_j under A_j for some j.
Output (r,s)=(r_j,s_j H(M)/H(M_j)) as forgery of M under A.

I doubt this reduction would work for existential or chosen-message 1 of n forgery.‎
‎
‎the 1 of n forger might somehow fail if M_j and A_j are correlated as above. So, we have to posit a 1 of n forger that never fails.
‎
  Original Message  
From: D. J. Bernstein
Sent: Saturday, August 1, 2015 7:03 PM
To: [e-mail]
Subject: Re: [Cfrg] Why hash verifier's key?

Context: EdDSA computes H(R,A,M) where A is the public key, instead of
Schnorr's H(R,M). The original Ed25519 paper says that this is "an
inexpensive way to alleviate concerns that several public keys could be
attacked simultaneously".

Dan Brown writes:
> Could one the EdDSA proposers more formally expand on what these
> "concerns" might be?

Is it clear that an attack against N keys can't succeed---i.e., find at
least one of the keys---with probability N times higher than an attack
against 1 key?

There are real attacks of this type. For example, if N users encrypt the
same counter with N AES-128 keys (a perfectly normal situation with many
modes---we don't want to blame the mode developers for doing something
simple and deterministic), then a well-known attack finds one of the
keys in time just 2^128/N with high probability. This turns into a
serious threat as N grows. This is why I recommend 256-bit secret keys;
it's also why EdDSA systematically avoids guessable 128-bit secrets.

For discrete logs the situation is better. There's a very strong "random
self-reduction" (the strongest type of "worst-case-to-average-case
reduction", stronger than in lattice-based crypto) guaranteeing that an
attack against N discrete logs can't have higher success probability
than an attack against 1 discrete log.

However, forging a signature could be easier than computing a discrete
log, and forging signatures against one of N keys could be N times more
likely than that. There's extensive security analysis regarding the
first concern, but where's the security analysis regarding the second
concern?

Inserting the public key A into the hash alleviates this concern---this
doesn't mean that it necessarily resolves the concern completely, but
it's similar to defenses that have been shown to work in other contexts.
The way that this type of insertion would show up in a hypothetical
generic-hash proof would be to force an attacker computing hashes to
commit to one key being attacked by each hash computation. Without the
public key, there's only a commitment to R, and it's not at all clear
that R is tied tightly enough to the public key to avoid the same loss
factor of N.

> Does inclusion of the verifier's public key in the hash precludes
> derivation of the verifier's public key from the signature?

It has this anonymity effect, yes, as pointed out by Ransom. However,
there are other ways to achieve the same effect with only slightly
higher cost; see Section 2.5 of the Elligator paper. This isn't the big
reason to insert the public key into the hash.

> On the other hand, being able to recover the public key from a
> signature might have some other advantages. For example, one could
> compress certificate chain by omitting the issuer's public keys.

The current situation is that there are very large gaps between

(1) the actual amount of data needed to send safe certificate chains,
(2) the bandwidth used by TLS to send certificate chains, and
(3) the total bandwidth used by TLS.

The huge gap between #2 and #3 is the obvious explanation for why the
gap between #1 and #2 has been allowed to persist.

My experience is that protocols that send much less data, and that pay
more attention to the overhead of signatures, start by removing the
massive redundancy of constantly sending the same public keys with the
same certificates---so their "chains" are just single signatures, and
then the type of tweak you're talking about doesn't save space.
Pintsov--Vanstone message recovery _does_ still save space, but
unfortunately is still patented (7249259) until September 2019.

---Dan

_______________________________________________
Cfrg mailing list
[e-mail]
http://www.irtf.org/mailman/listinfo/cfrg