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.