Re: [Cfrg] NUMs/rigidity security (Re: [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom)

David McGrew <mcgrew@cisco.com> Thu, 16 January 2014 12:44 UTC

Return-Path: <mcgrew@cisco.com>
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 D60C21AE329 for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 04:44:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -15.039
X-Spam-Level:
X-Spam-Status: No, score=-15.039 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5] 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 31lNa6dXQEwG for <cfrg@ietfa.amsl.com>; Thu, 16 Jan 2014 04:44:21 -0800 (PST)
Received: from rcdn-iport-4.cisco.com (rcdn-iport-4.cisco.com [173.37.86.75]) by ietfa.amsl.com (Postfix) with ESMTP id 6BC341AE099 for <cfrg@irtf.org>; Thu, 16 Jan 2014 04:44:21 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=2407; q=dns/txt; s=iport; t=1389876250; x=1391085850; h=message-id:date:from:mime-version:to:cc:subject: references:in-reply-to:content-transfer-encoding; bh=XLJOdiKPh+vmuX+YbeUS6Yw3SzX/Ja72FALlG1DuWNE=; b=fxN6+O1eoCVSe1PgS9alwInMlME2v7bwBG14hEPEfj9LU79lHrdp7IsU EaPV/s1C/1TFEvuHRXdni6uOXAS+E0B9Mv+XAp4PGf3eAEf6x/7GH8nRV k3uHSGgqpU2VZ3PdF2pbjQKdC7BXW9Lg41oLM4shYpuW2GWgBP7bw4jL7 U=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AiEFAODT11KtJV2d/2dsb2JhbABZgwu5EIMIgQ8WdIIlAQEBBDhAARALGAkWDwkDAgECAUUGDQEHAhSHbMNcF45/B4Q3AQOJR45ZhkWLUIFvgVwe
X-IronPort-AV: E=Sophos;i="4.95,667,1384300800"; d="scan'208";a="297809714"
Received: from rcdn-core-6.cisco.com ([173.37.93.157]) by rcdn-iport-4.cisco.com with ESMTP; 16 Jan 2014 12:44:09 +0000
Received: from [10.0.2.15] (rtp-mcgrew-8914.cisco.com [10.117.10.229]) by rcdn-core-6.cisco.com (8.14.5/8.14.5) with ESMTP id s0GCi8eG014488; Thu, 16 Jan 2014 12:44:08 GMT
Message-ID: <52D7D418.9070305@cisco.com>
Date: Thu, 16 Jan 2014 07:44:08 -0500
From: David McGrew <mcgrew@cisco.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130922 Icedove/17.0.9
MIME-Version: 1.0
To: Adam Back <adam@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>
In-Reply-To: <20140116120434.GA26078@netbook.cypherspace.org>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Cc: Dan Brown <dbrown@certicom.com>, "'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 12:44:23 -0000

Hi Adam,

On 01/16/2014 07:04 AM, Adam Back wrote:
> You know in principle we ought to stick to something with low entropy for
> the NUMs/rigidity seed.  I commented previously for example that 
> someone can
> do a fair bit of grinding by building a catalog of headlines, quote
> dictionaries, and permuting their punctuation, white space etc. Also
> permuting arbitrary implementation choices (encoding, endianness, equally
> plausible rigid choices, etc) So possibly the digits of pi are more
> convincing than some obscure literary quote or a headline.  The point 
> is to
> start from an ungrindable starting point, with canonicalized choices 
> at each
> step.  I think so far the NUMS argument is probably gamable to a 
> non-trivial
> extent due to the above effects.
>
> ie for secure NUMs you actually need to canonically encode all fo the
> arbitrary choices in a standardized language, sort them, and select the
> arbitrary choices at all levels, using the deterministic PRNG seed off 
> pi. And even the PRNG design itself needs to be standardized, 
> otherwise its
> design variants also admit yet more bits.
>
> The NUMs argument is good but so far is probably itself gameble, we 
> need a
> NUMs standard to remove as many of those variabilities as possible.
>
> Adam

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.)

I agree that using the digits of pi is in some sense more appealing.   
With the hash-of-prices approach, and people could come along after the 
curve group had been generated and call into question whether the 
canonicalization had actually been fixed beforehand.   Using the digits 
of pi would avoid this (mis)perception issue.

Off topic: you mention obscure literary quotes, and this one comes to 
mind.   "How I need a drink, alcoholic of course, after the heavy 
lectures involving quantum mechanics".   Which is of course just a very 
arbitrary encoding of another bit of information ...

David