Re: [Cfrg] NUMs/rigidity security (Re: [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom)
Adam Back <adam@cypherspace.org> Thu, 16 January 2014 14:06 UTC
Return-Path: <adam@cypherspace.org>
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 236D41AE333 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 06:06:10 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001] autolearn=ham
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 Y_9grAliLX34 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 06:06:08 -0800 (PST)
Received: from mout.perfora.net (mout.perfora.net [74.208.4.194]) by ietfa.amsl.com (Postfix) with ESMTP id 59C0F1AE356 for <cfrg@irtf.org>; Thu, 16 Jan 2014 06:06:08 -0800 (PST)
Received: from netbook (c107-70.i07-27.onvol.net [92.251.107.70]) by mrelay.perfora.net (node=mrus4) with ESMTP (Nemesis) id 0LmbBD-1VTdTq2lSF-00ZXHs; Thu, 16 Jan 2014 09:05:54 -0500
Received: by netbook (Postfix, from userid 1000) id 0808E2E283F; Thu, 16 Jan 2014 15:05:46 +0100 (CET)
Received: by flare (hashcash-sendmail, from uid 1000); Thu, 16 Jan 2014 15:05:46 +0100
Date: Thu, 16 Jan 2014 15:05:45 +0100
From: Adam Back <adam@cypherspace.org>
To: David McGrew <mcgrew@cisco.com>
Message-ID: <20140116140545.GA31053@netbook.cypherspace.org>
References: <20140113230750.6111382.6841.8590@certicom.com> <52D48450.3070701@akr.io> <810C31990B57ED40B2062BA10D43FBF5C1F190@XMB116CNC.rim.net> <52D59C35.10807@cisco.com> <810C31990B57ED40B2062BA10D43FBF5C2217A@XMB116CNC.rim.net> <52D72201.6030803@cisco.com> <20140116120434.GA26078@netbook.cypherspace.org> <52D7D418.9070305@cisco.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format="flowed"
Content-Disposition: inline
In-Reply-To: <52D7D418.9070305@cisco.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Hashcash: 1:20:140116:mcgrew@cisco.com::+3kjO/TFXjB0K9VD:00Tij
X-Hashcash: 1:20:140116:dbrown@certicom.com::z4k1exTl8AOLpHYb:000000000000000000 00000000000000000000000002iP
X-Hashcash: 1:20:140116:cfrg@irtf.org::oMGOcWmPb3GcFtc8:00004Adz
X-Hashcash: 1:20:140116:adam@cypherspace.org::94GPdQt3bV1lTh39:00000000000000000 0000000000000000000000001N3I
X-Provags-ID: V02:K0:b52OkXWs8IJ/CeWCw1PfxrcgLFcoHte0GV/lleQE3Yd NqfiwPlc03SLF8J2VA1PTwI9uH4AI3w+Z67/nUlfTShQOCr6ah E83YYw3DuY4By1glr2pwr3P0L9vuIklCBzf2fSXat4qUvBRy7D /SP2q2K+baTKyuakZ+Bw4XGsG5QMi7KHuTCAQUz4iSUFWpjPxq R9Bv1oRXyQyRejaXBEEYFG1u928D9BRiw2O7NNeqLdtBJxVlau y0rvyw2UtcV100L7f7FqEdbKRbb6DBOL9nV8NVh2No1e/HvWE5 u7P+99k/I8eeYr1cT56WOgoihAv8oW5+lV7mvUukTbaBFqP3kV VeST9a6ASZFiWDyxqm0qUan1RMlT68tVy7ienGjfj
Cc: Dan Brown <dbrown@certicom.com>, Adam Back <adam@cypherspace.org>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Subject: Re: [Cfrg] NUMs/rigidity security (Re: [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 16 Jan 2014 14:06:10 -0000
On Thu, Jan 16, 2014 at 07:44:08AM -0500, David McGrew wrote: >On 01/16/2014 07:04 AM, Adam Back wrote: >I think this is right. In my comment about using a hash of the S&P >500 prices on some future date, I had assumed that the >canonicalization step would be fixed in advance, and used unchanged >when trading closed on that day. (My thinking: those prices are >easily accessible in the public record, and would be implausibly >expensive to manipulate, and are not under the control of any >government. There might be better examples, but I couldn't think of >any.) OK. So what about this: if the generation progam were time-stamped, by placing the hash of the rigid selection code into the bitcoin block chain, and then the containing block hash as the prng seed, and placing the hash of the selected curve in a following block. (The current block hash includes the hash of the previous block hash recursively forming a hash chain). Minimally this limits the grinding to what can be achieved within 10mins (and most of the grinding power of an adversary is used up competing with a 17 petahash/sec = 181 exaflop/sec distributed supercomputer formed by bitcoins hashcash-SHA256^2 ASIC miners), in a directly verifiable way with no reference to external authority (the usual source of conspiracy theories). Its not quite ideal, but it is better than previous proposals I've seen. Note the ASIC miners are very hardware optimized 28nm/20nm high parallelism chips, actual curve cooking selection would have to do far more complicated selection and do it on general purpose programmable hardware not repeated ASIC with hashcash coded into it. Bitcoins hashrate outperforms the top 500 super computrs in *aggregate* by a factor of about 1000x. Add in the work to validate a curve for desired properties vs double SHA256 maybe by more. Secondly looking back in time a month or a year later, both the code and the rng seed become ever more difficult to retroactively modify. Thirdly the curve selection code could have a nonce placed into it that should be kept secret until a month after the selection. Then people can review the code and verify the curve. Not knowing the nonce, a third party could not grind the following hash. The current hash forms a quite secure distributed signature on the parameters. Adam ps I invented hashcash back in 1997 (bitcoins mining function) - might as well get something useful out of the 35MW ongoing powerdraw otherwise only doing a provably fair job of consensus/validation.
- [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Ps… Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Alyssa Rowan
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Michael Hamburg
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Paul Lambert
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Paul Lambert
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Manuel Pégourié-Gonnard
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Igoe, Kevin M.
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Mike Hamburg
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- [Cfrg] publishing drafts (was: Re: [CFRG] Safecur… David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Alyssa Rowan
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Paul Lambert
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Watson Ladd
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Igoe, Kevin M.
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Dan Brown
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Manuel Pégourié-Gonnard
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … Johannes Merkle
- [Cfrg] NUMs/rigidity security (Re: [CFRG] Safecur… Adam Back
- Re: [Cfrg] NUMs/rigidity security (Re: [CFRG] Saf… David McGrew
- Re: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid … David McGrew
- Re: [Cfrg] NUMs/rigidity security (Re: [CFRG] Saf… Adam Back