Re: [Cfrg] 40 bit loop and DragonFly

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Sun, 05 January 2014 20:36 UTC

Return-Path: <sfluhrer@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 6E0331AE097 for <cfrg@ietfa.amsl.com>; Sun, 5 Jan 2014 12:36:27 -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 xLVnyPML_fKJ for <cfrg@ietfa.amsl.com>; Sun, 5 Jan 2014 12:36:25 -0800 (PST)
Received: from rcdn-iport-9.cisco.com (rcdn-iport-9.cisco.com [173.37.86.80]) by ietfa.amsl.com (Postfix) with ESMTP id 3AC3E1AF818 for <cfrg@irtf.org>; Sun, 5 Jan 2014 12:36:25 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=3661; q=dns/txt; s=iport; t=1388954177; x=1390163777; h=from:to:subject:date:message-id:references:in-reply-to: content-transfer-encoding:mime-version; bh=vlkh3S+vAxb5FZeFXERfdeBReFSqL2aigl+DdJ9RnG0=; b=XLr3wcKEydbpmdR7c7uZTcJ0I80TKgE1oZWNNZ6W/MXwLJa66oMdYOob JlGL2AfLPK16RvXLau+xaPM5rRDLwcNo5Mjn/mxrRp+UQySn+O+JU9FjW wElep+ed39xNnqSWR0JS8FOXclox5fAPV/miONObmSlCD8cSZ7uQ0aDb1 Q=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgUFADXByVKtJV2a/2dsb2JhbABYgws4VbktgQ0WdIIlAQEBAwEBAQE3NBcEAgEIEQQBAQEKFAkHJwsUCQgBAQQBEggBh3MIDcNnF4xtKIFJOAaDHoETBKosgy2CKg
X-IronPort-AV: E=Sophos;i="4.95,608,1384300800"; d="scan'208";a="292374883"
Received: from rcdn-core-3.cisco.com ([173.37.93.154]) by rcdn-iport-9.cisco.com with ESMTP; 05 Jan 2014 20:36:16 +0000
Received: from xhc-aln-x09.cisco.com (xhc-aln-x09.cisco.com [173.36.12.83]) by rcdn-core-3.cisco.com (8.14.5/8.14.5) with ESMTP id s05KaFlV014632 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL); Sun, 5 Jan 2014 20:36:15 GMT
Received: from xmb-rcd-x04.cisco.com ([169.254.8.37]) by xhc-aln-x09.cisco.com ([173.36.12.83]) with mapi id 14.03.0123.003; Sun, 5 Jan 2014 14:36:15 -0600
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: "Igoe, Kevin M." <kmigoe@nsa.gov>, "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: 40 bit loop and DragonFly
Thread-Index: Ac8Jtz8QHBqZuWIRSrC0AhG0eZjDKgAnaYVw
Date: Sun, 5 Jan 2014 20:36:14 +0000
Message-ID: <A113ACFD9DF8B04F96395BDEACB340420B77D4CC@xmb-rcd-x04.cisco.com>
References: <3C4AAD4B5304AB44A6BA85173B4675CABA99F80C@MSMR-GH1-UEA03.corp.nsa.gov>
In-Reply-To: <3C4AAD4B5304AB44A6BA85173B4675CABA99F80C@MSMR-GH1-UEA03.corp.nsa.gov>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.86.245.240]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: Re: [Cfrg] 40 bit loop and DragonFly
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: Sun, 05 Jan 2014 20:36:27 -0000

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Igoe, Kevin M.
> Sent: Saturday, January 04, 2014 8:41 PM
> To: 'cfrg@irtf.org'
> Subject: [Cfrg] 40 bit loop and DragonFly
> 
> Scott Fluhrer wrote:
> 
> I think we agree that what Dan specified in the draft is broken.  However, I
> believe that's because Dan got it wrong (and I was busy elsewhere, and did
> not review the draft).
> 
> I believe my suggestion is an improvement (but still needs caution; the
> checking if x^3+ax+b is a QR must be done in constant time, or in random
> time via blinding; I believe that in this case blinding is easier).
> 
> Now, I believe the issue is 'did Kevin endorse my suggestion, or did he
> endorse Dan's implementation?'
> ---------------------------------
> 
> Actually I had something more like the process outlined below in mind.

Both your procedure and mine look good.

The only thing (and I think we ought to be explicit about it) is that the various operations need to run in constant time; we need to explicitly state that the modular additions and multiplications need to be run in time independent of the values being added and multiplied.  The only exception in either of our proposals is the Legendre symbol computation, and that's true IF you are using blinding like I suggested; that's safe because the time it takes is not correlated with any value we need to keep secret.

This might be fairly obvious; however I don't know if we want to omit obvious precautions.

> 
> First an elementary (and somewhat obscure)fact:
> 
>   For any prime p = 3 mod 4 and any non-zero f in Z/p, let
>             r = f**((p+1)/4).
>   If f is a quadratic residue mod p (i.e. has a square root mod p),
>   then r**2 = f, otherwise r**2 = -f.
> 
> (This is easy to see since
>              r**2 = f**((p+1)/2) mod p
>                   = f * f**((p-1)/2) mod p and f**((p-1)/2) = 1 mod p if f has a square
> root mod p and is
> -1 otherwise).
> 
> Aside from cases of vanishingly small probability (e.g f = 0, 1 or -1), the time
> to do this exponentiation  depends upon two publicly known values, the
> modulus p and the exponent ((p+1)/4), and not upon the secret values x and
> f.  I'd advise using Montgomery arithmetic as this is a very efficient and
> methodical technique for doing mod p arithmetic.
> 
> So what had I envisioned is something like this (in pythonese):
> 
> Bad = []
> Good = []
> for t in range(40):
>     x  = one_way_update(x)
>     f  = x**3 + a*x + b mod p
>     r  = f**((p+1)/4)
>     f1 = r**2
>     if f1 == f:
>         Good.append( (x,r) )
>     else:
>         Bad.append( (x,r) )
> 
> if len(Good) == 0:
>     raise ValueError
> else:
>     return Good[0]
> 
> 
> Observations:
>  - This should be consant in time and memory usage.
>  - Prob of hitting the error condition is 2**-40 ~= 10**-12.
>  - The 40 could be increased if the RG deems that to be prudent.
> 
> 
> Potential IPR issues:
> Certicom has granted permission to the IETF to use the NIST curves, and at
> least two of these, P256 and P384, have p = 3 mod 4.  Not being a patent
> lawyer, I have no idea what impact the Certicom patents have on the use of
> newer families of curves, such as Edwards curves.
> RFC 6090 outlines elliptic curve technology which predates the Certicom
> patents.
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg