Re: [Cfrg] key as message prefix => multi-key security
"D. J. Bernstein" <djb@cr.yp.to> Wed, 30 September 2015 22:56 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 375291AC3E8 for <cfrg@ietfa.amsl.com>; Wed, 30 Sep 2015 15:56:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.896
X-Spam-Level: **
X-Spam-Status: No, score=2.896 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HELO_EQ_NL=0.55, HOST_EQ_NL=1.545, RCVD_IN_DNSWL_NONE=-0.0001, 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 DF7uPEldHKUD for <cfrg@ietfa.amsl.com>; Wed, 30 Sep 2015 15:56:31 -0700 (PDT)
Received: from calvin.win.tue.nl (calvin.win.tue.nl [131.155.70.11]) by ietfa.amsl.com (Postfix) with SMTP id D7B8A1AC3E1 for <cfrg@irtf.org>; Wed, 30 Sep 2015 15:56:30 -0700 (PDT)
Received: (qmail 23058 invoked by uid 1017); 30 Sep 2015 22:56:50 -0000
Received: from unknown (unknown) by unknown with QMTP; 30 Sep 2015 22:56:50 -0000
Received: (qmail 21807 invoked by uid 1000); 30 Sep 2015 22:56:22 -0000
Date: Wed, 30 Sep 2015 22:56:22 -0000
Message-ID: <20150930225622.21805.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <5608377F.5020008@brainhub.org>
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/YrmMR-e44iEGTeDUqLOjJHYk8wg>
Subject: Re: [Cfrg] key as message prefix => multi-key security
X-BeenThere: cfrg@mail.ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.mail.ietf.org>
List-Unsubscribe: <https://mail.ietf.org/mailman/options/cfrg>, <mailto:cfrg-request@mail.ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@mail.ietf.org>
List-Help: <mailto:cfrg-request@mail.ietf.org?subject=help>
List-Subscribe: <https://mail.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@mail.ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 30 Sep 2015 22:56:33 -0000
Andrey Jivsov writes: > Because CFRG requires a deterministic signature method, "classic" > scheme in [1] doesn't look like a good model for any current signature > proposal. The whole point of this type of security analysis is to understand the potential gaps in difficulty between _different_ problems facing the attacker: e.g., between the problem of breaking signature system X and the problem of breaking signature system Y. The gold standard in this area is proving that a new problem is at least as hard to solve as a classic problem. This doesn't say that the two problems are good models of each other: maybe the new problem is even _harder_ to break! But that's not relevant to the logic. Here's the standard argument: the classic problem has survived scrutiny; this means (hopefully) that the classic problem is hard to solve; this in turn implies that the new problem is hard to solve. (Of course, all of this breaks down if the classic problem is actually easy to solve---maybe everybody missed an important attack strategy against that problem.) Consider, for example, the following chain of problems: * Problem 1: Forge signatures from a single signer in the classic Schnorr signature scheme. This has been around long enough, and studied long enough, that one can reasonably hope that it's hard to break. However, even if we _assume_ that it's hard to break, we still need to figure out what this means for other problems facing the attacker. * Problem 2: Forge signatures from any 1 of N signers in a modified signature scheme that uses the public key as a prefix of a message. It's conceivable that Problem 2 is _harder_ to solve than Problem 1. Maybe an attack against Problem 1 requires particular message prefixes that can't be adjusted to match the public key. (One can manufacture artifically dumb hash functions that allow attacks against Problem 1 without obviously breaking Problem 2; on the other hand, this doesn't say anything about real hash functions.) Earlier I was explaining in detail a proof that Problem 2 can't be _easier_ to solve than Problem 1: any attack against Problem 2 can be converted into an attack against Problem 1 with the same success probability and practically identical speed. * Problem 3: Same as Problem 2, except with "signature caching" by all of the legitimate signers. This means that, once a message has been signed, the signer will always return that signature for that message, rather than generating new signatures for that message. It's conceivable that Problem 3 is _harder_ to solve than Problem 2. Maybe having multiple signatures on the same message leaks information somehow, and signature caching stops this (as in, e.g., http://cr.yp.to/papers.html#rwtight). Problem 3 can't be _easier_ to solve than Problem 2. Any attack against Problem 3 can be converted (by caching!) into an attack against Problem 2 with the same success probability and practically identical speed. * Problem 4: Same as Problem 3, except that now the legitimate signers deterministically generate each one-time scalar as a keyed hash of the message to be signed, where the key is a long-term signer secret, independent of everything else. If the keyed hash is indistinguishable from uniform---this is a standard "PRF" assumption---then Problem 4 is indistinguishable from Problem 3, and thus can't be easier or harder to solve than Problem 3. The main conclusion is that _if_ classic Schnorr for a single signer is hard to break, _and_ the PRF assumption holds, _then_ the deterministic key-prefixed system for N signers is hard to break. This provides the following guidance to someone looking for attacks against the deterministic key-prefixed system: * find a single-key attack against classic Schnorr, or * find an attack against the PRF assumption, or * find an error in the logic, or * find an attack outside the attack model. The bigger picture is that this is still only part of a comprehensive security analysis. Earlier I mentioned several complications in the "provable security" picture; derandomization was only one of the items, certainly not the most difficult item. ---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