Re: [Cfrg] key as message prefix => multi-key security
"D. J. Bernstein" <djb@cr.yp.to> Sat, 21 November 2015 22:39 UTC
Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E974B1B2E21 for <cfrg@ietfa.amsl.com>; Sat, 21 Nov 2015 14:39:49 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.196
X-Spam-Level: *
X-Spam-Status: No, score=1.196 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HELO_EQ_NL=0.55, HOST_EQ_NL=1.545, J_CHICKENPOX_45=0.6, RCVD_IN_DNSWL_MED=-2.3, UNPARSEABLE_RELAY=0.001] autolearn=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6j645wOUBl9A for <cfrg@ietfa.amsl.com>; Sat, 21 Nov 2015 14:39:47 -0800 (PST)
Received: from calvin.win.tue.nl (calvin.win.tue.nl [131.155.70.11]) by ietfa.amsl.com (Postfix) with SMTP id 163301B2E24 for <cfrg@ietf.org>; Sat, 21 Nov 2015 14:39:46 -0800 (PST)
Received: (qmail 21397 invoked by uid 1017); 21 Nov 2015 22:40:05 -0000
Received: from unknown (unknown) by unknown with QMTP; 21 Nov 2015 22:40:05 -0000
Received: (qmail 19764 invoked by uid 1000); 21 Nov 2015 22:39:37 -0000
Date: Sat, 21 Nov 2015 22:39:37 -0000
Message-ID: <20151121223937.19762.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@ietf.org
Mail-Followup-To: cfrg@ietf.org
In-Reply-To: <CAKt=43p6X+Byb_a-pin-OVS8RXi82AFpzML80KzeYWKve0aG6A@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/vaCDxhmL89juFEPFYZyTV4s1YTI>
Subject: Re: [Cfrg] key as message prefix => multi-key security
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 21 Nov 2015 22:39:50 -0000
Summary first. There has always been, and continues to be, a reasonable concern that forging a message under 1 of N Schnorr keys could be significantly less secure than the problem that (we hope!) has actually been thoroughly studied, namely forging a message under a single targeted key. It's easy to prove that the security loss is limited to a factor N, but this is quantitatively unsatisfactory. http://cr.yp.to/papers.html#multischnorr compares the key-prefixed H(R,A,M) system to the traditional H(R,M) system and proves that 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) which completely eliminates the issue for H(R,A,M). An old paper, by Galbraith--Malone-Lee--Smart (GMLS), claimed to prove the same thing _without_ inserting the key into the hash--- probability of breaking any 1 of N signature keys using H(R,M) <= probability of breaking a targeted signature key using H(R,M) ---but the proof turned out to be wrong in a way that seems extremely difficult to fix. A new paper, by Kiltz--Masny--Pan (KMP), claims to have proven that "the original GMLS theorem is correct". This claim is, unfortunately, not an accurate characterization of what KMP actually proved; I expect KMP to withdraw this claim. What the KMP paper actually proves (I'm assuming that the new proof is correct---I haven't had a chance to check this yet) is a new theorem that's * different from the GMLS claim, and * significantly weaker than the GMLS claim, with * no hope of obtaining the GMLS claim as a corollary. The bottom line is the same as before: there's a reasonable concern that breaking 1 of N Schnorr keys could be significantly less secure than breaking a single targeted key. Inserting the key into the hash eliminates this concern. Now details, starting with background. There's an old paper by Schnorr and Jakobsson showing that Schnorr signatures provide security sqrt(group size) against generic attacks (attacks that work for any group and any hash function): http://www.math.uni-frankfurt.de/~dmst/research/papers/schnorr.random_oracle_generic_model.1999.dvi This 2^(b/2) is much stronger than the conclusion of the well-known Pointcheval--Stern paper, the Neven--Smart--Warinschi paper, etc., and the proof is conceptually simpler. The same technique should easily generalize to multiple keys, superseding, e.g., the GMLS paper. The only reason that the Schnorr--Jakobsson paper isn't the end of the story is that there's a big difference between "generic attacks" and "all attacks". There's a legitimate, and very frequently expressed, concern about the possibility of a _non-generic_ attack breaking any _specific_ standardized group and any _specific_ standardized hash function. This possibility is exactly why there are many papers criticizing proofs in the generic-group "model" and the generic-hash "model" (typically called the "random-oracle model"), and instead advertising proofs in the "standard model". Consider, for example, the paper "Practical Chosen Ciphertext Secure Encryption from Factoring" by Hofheinz and Kiltz, which * won a best-paper award at Eurocrypt 2009; * works in the "standard model"---the same result _for generic-hash attacks_ had already been accomplished many years earlier by much simpler techniques; and * criticizes analysis of generic-hash attacks as follows: "We stress that although a proof in the random oracle model has a certain value it is still only a heuristic security argument for any implementation of the scheme." Of course, there's lots of work on studying particular types of attacks against particular choices of parameters: e.g., discrete-log attacks against particular groups, or preimage attacks against particular hash functions. But maybe someone can break the _signature_ scheme more easily than breaking the problems that have actually been studied. As a concrete example, the attack stated in my "Security concerns regarding short hashes" message from July breaks narrow-pipe short-hash signatures without breaking discrete logs and without breaking the traditional single-target preimage problem. With this background in mind, I'm puzzled to see Kiltz's message glossing over * the difference between analyzing _all_ attacks and merely analyzing _generic_ attacks ("This is the original GMLS theorem, except that we make the random oracle requirement") and * the difference between assuming standard unforgeability and having to assume "strong" unforgeability. If we don't care about differences in attack genericity, then why don't we simply use the original Schnorr--Jakobsson theorem? If we don't care about differences in attack targets, then why don't we simply analyze discrete logs and preimage resistance? The answer, of course, is that we _do_ care about these differences. Having to assume "strong" unforgeability isn't as good as assuming standard unforgeability---there could be huge differences in security between these two attack targets. Studying all generic-hash attacks (= "attacks in the random-oracle model") goes beyond studying generic-group generic-hash attacks but isn't as good as studying _all_ attacks. The new KMP paper makes the following claim in its introductory section: 1.1 Our results Our main result states that the original GMLS theorem is correct, namely that single-user security of the Schnorr signatures scheme tightly implies multi-user security of the same scheme. This claim is incorrect for a minor reason and a major reason. The minor reason is that the original GMLS theorem actually claims something quantitatively very strong, namely that there is _no_ loss of security (theorem: "epsilon_n = epsilon_1"; subsequent summary: "security does not decrease with the number of users"). Saying "tight" allows some security loss, such as the factor 2+epsilon lost in the KMP theorem. The major reason that the claim is incorrect is that the KMP theorem assumes "strong" unforgeability, while the GMLS claim merely assumed _standard_ unforgeability. Strong unforgeability * is much less studied than standard unforgeability and * could be much easier to break---as I said before, there's no limit on how much security this could lose. Kiltz's response is that there's a tight limit _for generic attacks_, but this is an even more restrictive hypothesis---there's no limit on the security gap between generic attacks and all attacks. Eike Kiltz writes: > Our results are not stated entirely correctly, so let me clarify first. If I've misstated something, my apologies; please pinpoint the error! > Our results show that key-prefixing does not provide any advantage > for multi-user security Eike, if you're thinking "the advantage factor can't be more than about 2", why do you say that there isn't "any advantage"? This isn't terribly important but it's sloppy. More importantly, GMLS claimed a theorem about _all_ multi-key attacks assuming _standard_ unforgeability for a single key. Key prefixing makes this work. Your paper, by contrast, has to * assume "strong" unforgeability---not addressing the concern that this could be much easier to break than standard unforgeability--- or * fall back to the random-oracle model---i.e., consider only generic-hash attacks, not addressing the concern that there could be much faster non-generic attacks. So how can you claim that there's no advantage to the key-prefixing theorem? That theorem completely _eliminates_ the concern regarding multi-key attacks, while your theorem obviously doesn't accomplish this. > As I understand the history of this thread, initially the group agreed > that key-prefixing should be avoided for Schnorr No; the group took very few actions, and this wasn't one of them. During the discussion, a few people spoke up for avoiding key-prefixing, but not many. It seems that very few people are in situations where * the signer doesn't care about knowing its own public key _and_ * storing the 32-byte public key next to the secret signing key is a space problem _and_ * recomputing the public key on demand is a speed problem, so the performance argument for H(R,M) is quite flimsy, while there has always been a _security_ argument for H(R,A,M). The relevant series of events during the discussion started early in September, when Struik---backed by the GMLS paper---claimed that H(R,M) had the same security feature. The eventual conclusion, after some investigation, was that * H(R,A,M) is now _proven_ to be (at least) as strong against multi-key attacks as H(R,M) is against single-key attacks, while * H(R,M) doesn't have any such proof---it's possible that multi-key attacks against H(R,M) are significantly easier than single-key attacks, contrary to the GMLS claim. Your paper doesn't change either part of this conclusion. It's hard to guess what effect the original claim would have had on the final CFRG decision if the claim had lasted for more than two weeks. In the "provable security" literature it's common to say that design elements should be included if and only if those elements are contributing to security proofs (as discussed in the last paragraph of Section 1.2 of my multischnorr paper); on the other hand, for many good reasons, real-world cryptography is actually guided by many factors beyond the known security proofs. Anyway, as a historical matter, the agreement on a particular signature scheme came after the dust had settled regarding this claim. > we recommend to reconsider this decision Still seems feasible, logistically, but I'm missing what the argument is supposed to be for making the opposite decision. ---Dan
- [Cfrg] EC signature: next steps Alexey Melnikov
- Re: [Cfrg] EC signature: next steps Simon Josefsson
- Re: [Cfrg] EC signature: next steps Watson Ladd
- [Cfrg] EC signature: next steps Dan Brown
- Re: [Cfrg] EC signature: next steps Ilari Liusvaara
- Re: [Cfrg] EC signature: next steps Stephen Farrell
- Re: [Cfrg] EC signature: next steps Dan Brown
- Re: [Cfrg] EC signature: next steps Simon Josefsson
- Re: [Cfrg] EC signature: next steps Ilari Liusvaara
- [Cfrg] Side inputs to signature systems D. J. Bernstein
- Re: [Cfrg] Side inputs to signature systems Natanael
- Re: [Cfrg] EC signature: next steps Simon Josefsson
- Re: [Cfrg] Side inputs to signature systems Michael Hamburg
- Re: [Cfrg] EC signature: next steps Rene Struik
- Re: [Cfrg] EC signature: next steps David Jacobson
- Re: [Cfrg] EC signature: next steps Mike Hamburg
- Re: [Cfrg] EC signature: next steps William Whyte
- Re: [Cfrg] EC signature: next steps Stephen Farrell
- Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] EC signature: next steps Ilari Liusvaara
- Re: [Cfrg] EC signature: next steps Stephen Farrell
- Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] EC signature: next steps Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] key as message prefix => multi-key sec… Dan Brown
- [Cfrg] key as message prefix => multi-key security D. J. Bernstein
- Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
- Re: [Cfrg] key as message prefix => multi-key sec… Paterson, Kenny
- Re: [Cfrg] key as message prefix => multi-key sec… Sven Schäge
- Re: [Cfrg] key as message prefix => multi-key sec… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] key as message prefix => multi-key sec… William Whyte
- Re: [Cfrg] key as message prefix => multi-key sec… Bill Cox
- Re: [Cfrg] key as message prefix => multi-key sec… Andrey Jivsov
- Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
- Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
- Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
- Re: [Cfrg] key as message prefix => multi-key sec… Eike Kiltz
- Re: [Cfrg] key as message prefix => multi-key sec… D. J. Bernstein
- Re: [Cfrg] key as message prefix => multi-key sec… Simon Josefsson