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

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

+1 for EdDSA.

P.S. Other proposals should be changed to include pub key in the hash.
-- 
Regards,
Uri Blumenthal





On 9/18/15, 4:48 , "Cfrg on behalf of Paterson, Kenny"
<[e-mail] on behalf of [e-mail]> wrote:

>Dan,
>
>Thanks, this is a very valuable contribution and provides a strong
>argument in favour of including the public key in the hash, as in the
>EdDSA proposal (while the other proposals can be adapted to add this
>feature).
>
>If anyone wishes to change their existing vote in the on-going poll in the
>light of this new information, please feel free to do so (I maybe have
>missed some messages, but I believe that there's only one "+1" at the
>moment for any proposal other than EdDSA).
>
>Cheers,
>
>Kenny 
>
>On 17/09/2015 23:47, "Cfrg on behalf of D. J. Bernstein"
><[e-mail] on behalf of [e-mail]> wrote:
>
>>This message continues the security analysis of inserting the public key
>>A into the hash in Schnorr's signature system: e.g., H(R,A,M) instead of
>>Schnorr's classic H(R,M). The 'brown' and 'ladd' proposals omit the key
>>from the hash but the other proposals include it.
>>
>>The Ed25519 paper says that including the key is an inexpensive way "to
>>alleviate concerns that several public keys could be attacked
>>simultaneously". Here's the background regarding these concerns:
>>
>>   * Most of the literature on signature-system security focuses on the
>>     problem of forging messages under _one_ public key.
>>
>>   * The real-world attacker actually sees _many_ public keys, and is
>>     probably happy if he solves the problem of forging messages under
>>     any one of those keys. (For example, he simply wants to take over
>>     _somebody's_ account to gain computer power, relay more attacks,
>>     etc.) This isn't the same problem.
>>
>>   * The concern is that switching to the multi-key problem could give
>>     the attacker an advantage, compared to the original problem. There
>>     _is_ an analogous advantage in attacking secret-key protocols---
>>     which is why I recommend 256-bit secret keys.
>>
>>   * It's easy to prove, for any signature system, that attacking a
>>     billion keys at once can't give the attacker an advantage of more
>>     than a factor of a billion. But, yikes, a billion is a big number!
>>
>>I hope it's clear that the word "concern" does _not_ mean that there are
>>any known multi-key attacks better than single-key attacks on any of the
>>signature schemes under consideration. What it means is that one can
>>reasonably be worried about the _possibility_ of multi-key attacks, and
>>about the lack of study of this possibility.
>>
>>I'm happy to announce that there's now a theorem guaranteeing that key
>>insertion completely eliminates this concern:
>>
>>   probability of breaking any 1 of N signature keys using H(R,A,M)
>>   <= probability of breaking a targeted signature key using H(R,M).
>>
>>In other words, if you believe that the classic H(R,M) system in the
>>single-key case is secure, then you have to believe that the H(R,A,M)
>>system is secure for any number of keys. The proof is a simple reduction
>>that takes any attack against multi-key H(R,A,M) and converts it into a
>>single-key attack against H(R,M); the single-key attack has practically
>>identical performance and success probability to the multi-key attack.
>>
>>The proof relies critically on the insertion of the public key A into
>>the hash. There's a huge obstacle to proving a similar theorem without
>>the public key, as I'll explain below. The best theorem we know without
>>hashing A is the generic
>>
>>   probability of breaking any 1 of N signature keys using H(R,M)
>>   <= N*probability of breaking a targeted signature key using H(R,M)
>>
>>which still leaves the concern unaddressed. To summarize:
>>
>>   * Inserting the public key eliminates the multi-key concerns.
>>   * Omitting the public key doesn't.
>>
>>I should emphasize that the theorem is for a quite traditional form of
>>Schnorr's system, and hasn't yet been combined with modern features such
>>as derandomization, key derivation, cofactors, etc.; many of these
>>features obviously complicate the "provable security" picture. However,
>>even with its limited scope, the theorem---together with the inability
>>to prove the same theorem with the key omitted---justifies the idea that
>>inserting the key into the hash is the conservative thing to do.
>>
>>The proof idea appeared many years ago, but unfortunately with a serious
>>mistake, leading to various incorrect conclusions, both by the original
>>authors and by subsequent readers. This week I've conferred with and
>>heard back from various people, including two of the original authors,
>>and everyone seems to agree with what I'm saying. The rest of this
>>message discusses the history, the mistake, and the proof details.
>>
>>Rene Struik writes:
>>> one does not need to include the public key in the signing process,
>>> since security in the multi-user setting is roughly the same as in the
>>> single-user setting (see [1], [2]).
>>
>>Reference #1 doesn't quantify security levels, and doesn't have any
>>proof techniques relevant to the concerns under discussion.
>>
>>Reference #2 _does_ quantify security levels, and specifically claims to
>>have proven that "security does not decrease with the number of users"
>>for Schnorr signatures. This claim will have to be retracted. The proof
>>is wrong, and there's no hope of proving the claimed theorem.
>>
>>The overall proof idea in reference #2 is good, _except_ that the proof
>>skips past a critical step (namely, proving that the alleged forgery is
>>on a message that wasn't legitimately signed); the huge obstacle sinks
>>the proof at exactly this point. Inserting the public key into the hash
>>dodges the obstacle, and makes the whole proof idea work, producing the
>>new theorem, which _does_ eliminate the concern for multi-key H(R,A,M).
>>
>>End of summaries. I'll now dive into the proof details, with the goal of
>>allowing public verification of what I said above.
>>
>>"Classic scheme", parametrized by a standard group and a standard base
>>point B: The signer, given a message M, produces as signature a uniform
>>random R, independent of everything else, and the unique S satisfying
>>SB = R+H(R,M)A, where A is the public key.
>>
>>Let's consider single-key attacks against the classic scheme. An attack
>>receives as input
>>
>>   * a key A and
>>   * an oracle that, given M, produces a uniform random R, independent
>>     of everything else, and the unique S satisfying SB = R + H(R,M)A.
>>
>>An attack produces as output a message M and an alleged signature (R,S).
>>Success means that
>>
>>   * SB = R+H(R,M)A, i.e., (R,S) is a signature of M under A; and
>>   * M was not an oracle query, i.e., key A did not legitimately sign
>>     message M.
>>
>>The starting assumption is that such attacks have been adequately
>>studied, and that the classic scheme is (for appropriate distributions
>>of A) secure against these attacks: i.e., any attack with a feasible
>>cost has a negligible probability of success.
>>
>>"Generalized scheme", parametrized by a standard group, a standard base
>>point B, and a standard function "tag": The signer, given M, produces as
>>signature a uniform random R, independent of everything else, and the
>>unique S satisfying SB = R+H(R,tag(A),M)A, where A is the public key.
>>I'm implicitly assuming that R and tag(A) are both self-delimiting, so
>>we can recover R and tag(A) and M from the concatenation (R,tag(A),M).
>>
>>If tag(A) is defined as the empty string then the generalized scheme is
>>the same as the classic scheme. If tag(A) is defined as A then the
>>generalized scheme includes the whole public key in the hash.
>>
>>Let's consider N-key attacks against the generalized scheme. An attack
>>receives as input
>>
>>   * keys A_1,A_2,...,A_N and
>>   * an oracle that, given a key T in {A_1,A_2,...,A_N} and a message M,
>>     produces a uniform random R, independent of everything else, and
>>     the unique S satisfying SB = R+H(R,tag(T),M)T.
>>
>>An attack produces as output a public key T, a message M, and an alleged
>>signature (R,S). Success means that
>>
>>   * T is in {A_1,A_2,...,A_N}, i.e., T is one of the specified keys;
>>   * SB = R+H(R,tag(T),M)T, i.e., (R,S) is a signature of M under T; and
>>   * (T,M) was not an oracle query, i.e., key T did not legitimately
>>     sign message M.
>>
>>What I'll do is convert any N-key attack X against the generalized
>>scheme into a single-key attack ReRandomize(X) against the classic
>>scheme. The goal is to ensure that ReRandomize(X) and X have practically
>>identical costs and the same identical success probabilities. We'll see
>>that this works if the tag function is injective. We'll also see what
>>the obstacle is if multiple keys collide under the tag function, for
>>example if tag(A) = empty.
>>
>>Here's what ReRandomize(X) does.
>>
>>Generate uniform random r_1,r_2,...,r_N, and convert the input key A
>>into N independent uniform random keys A+r_1 B, A+r_2 B, ..., A+r_N B.
>>Run X on these N keys. Whenever X asks for a signature of M under T:
>>
>>   * Look up T in the list of A+r_1 B, A+r_2 B, ..., A+r_N B to find an
>>     i such that T = A+r_i B; if none exists, reject the query.
>>
>>   * Relay the concatenation (tag(T),M) to the input oracle. By
>>     hypothesis the input oracle produces a uniform random R,
>>     independent of everything else, and the unique S satisfying
>>     SB = R + H(R,tag(T),M)A.
>>
>>   * Compute S' = S+r_i H(R,tag(T),M). Then S'B = R + H(R,tag(T),M)T;
>>     i.e., (R,S') is a signature of M under T in the generalized scheme.
>>
>>   * Return (R,S') to X. Notice that this is exactly the behavior of a
>>     normal signer who knows the secret key for T in the generalized
>>     scheme: namely, returning a uniform random R, independent of
>>     everything else, and a solution to the right equation.
>>
>>This is exactly a run of X against N independent uniform random keys and
>>an appropriate oracle for those keys. Eventually X produces as output
>>T,M,R,S. As above find i such that T = A+r_i B (aborting if there is no
>>such i), and compute S' = S - r_i H(R,tag(T),M). Output the
>>concatenation (tag(T),M) and the pair (R,S').
>>
>>_If_ tag is injective, and X is successful against the generalized
>>scheme, then this algorithm ReRandomize(X) is successful against the
>>classic scheme. Indeed, recall the definition of success for X:
>>
>>   * First, T is in {A_1,A_2,...,A_N}. This means that there _will_ be an
>>     i such that T = A+r_i B.
>>
>>   * Second, SB = R+H(R,tag(T),M)T. This implies S'B = R+H(R,tag(T),M)A;
>>     i.e., (R,S') is a signature of (tag(T),M) under A.
>>
>>   * Third, (T,M) wasn't an oracle query from X. What I want to conclude
>>     at this point is that (tag(T),M) wasn't legitimately signed by A,
>>     i.e., wasn't an oracle query from ReRandomize(X). This is where the
>>     injectivity of tag(T) matters.
>>
>>     The queries from ReRandomize(X) are exactly (tag(T'),M') for the
>>     queries (T',M') from X such that T' is in {A+r_1 B,...,A+R_N B}.
>>     I'm using the notation T',M' here to avoid confusion with the T,M
>>     output by X.
>>
>>     Suppose the output (tag(T),M) was a query from ReRandomize(X). Then
>>     (tag(T),M) = (tag(T'),M') for some query (T',M') from X. Now tag is
>>     self-delimiting, so tag(T) = tag(T') and M = M'; tag is injective,
>>     so T = T'; so (T,M) = (T',M'); so (T,M) _was_ a query from X,
>>     contradiction. Hence (tag(T),M) wasn't a query from ReRandomize(X).
>>
>>That's the end of the proof.
>>
>>What happens if we drop the injectivity requirement for the tag
>>function? The argument still works if the tag function is injective _on
>>the generated keys_. If the tag length is, say, 160 bits, and there are
>>2^60 keys, then it's reasonable to conjecture that the collision chance
>>is around 2^-40, which is acceptable as an attack probability. Maybe one
>>could even prove something about the collision chance of 160-bit tags
>>for 256-bit curves. But this approach obviously breaks down for short
>>tag lengths, and in particular for empty tags.
>>
>>(I don't think there's a real reason to consider any intermediate tag
>>lengths between empty tags and complete tags. There's negligible impact
>>on hashing cost. The extreme "I need to minimize secret-key storage and
>>can't afford to recompute the public key on demand" argument is an
>>argument for an empty tag, not an argument for a short tag.)
>>
>>Even worse, if tags collide, the conclusion that we're trying to prove
>>is simply wrong. As an extreme example, take empty tags, and consider a
>>very slow 2-user attack X that
>>
>>   * asks the first key for a signature of the message "yes",
>>
>>   * applies any ECDLP algorithm (however long this takes) to compute
>>     the discrete logarithm of the second key, and
>>
>>   * applies the normal signing procedure to forge a signature of the
>>     message "yes" under the second key.
>>
>>This attack X has success probability almost exactly 1: the only way it
>>fails is in the extremely rare case that the two keys happen to be
>>identical. However, the attack ReRandomize(X) has success probability
>>exactly 0: it outputs a signature of "yes", but that's not a forgery,
>>since earlier it asked for a signature of "yes".
>>
>>Could ReRandomize be modified somehow to work for empty tags? The
>>obstacles are formidable:
>>
>>   * The signature scheme hashes messages, and I can't imagine how the
>>     reduction could modify hash inputs, so the reduction will have to
>>     produce a forgery on the same message "yes" forged by X.
>>
>>   * For this to be a forgery, the reduction has to retroactively avoid
>>     asking for a signature on "yes". How can the reduction predict that
>>     "yes" will be the message to be forged?
>>
>>   * Even if the reduction does somehow predict this, how will it answer
>>     X's signing query for "yes" from the first user? The reduction
>>     can't simply skip that query---maybe X actually does some
>>     interesting computation on the signature result, influencing its
>>     final output.
>>
>>The original paper doesn't try to address any of these obstacles. It
>>writes down ReRandomize(X) for the case of empty tags (minor difference:
>>it takes r_1=0, assuming that A is uniformly distributed), and correctly
>>observes that success in X implies that the output of ReRandomize(X) is
>>a valid signature. It then leaps to the conclusion that the output is a
>>"valid forgery", without checking whether the message was signed before.
>>
>>---Dan
>>
>>_______________________________________________
>>Cfrg mailing list
>>[e-mail]
>>https://mail.ietf.org/mailman/listinfo/cfrg
>
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>https://mail.ietf.org/mailman/listinfo/cfrg