[Cfrg] 40 long loop, not 40 bit loop

"Igoe, Kevin M." <kmigoe@nsa.gov> Sun, 05 January 2014 01:48 UTC

Return-Path: <kmigoe@nsa.gov>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 9D32C1AE0DF for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 17:48:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.438
X-Spam-Status: No, score=-7.438 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id QrG65T6FmmQS for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 17:48:22 -0800 (PST)
Received: from nsa.gov (emvm-gh1-uea08.nsa.gov []) by ietfa.amsl.com (Postfix) with ESMTP id 114C71AE0D6 for <cfrg@irtf.org>; Sat, 4 Jan 2014 17:48:21 -0800 (PST)
X-TM-IMSS-Message-ID: <5cdd73140005b4a3@nsa.gov>
Received: from MSHT-GH1-UEA02.corp.nsa.gov ([]) by nsa.gov ([]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 5cdd73140005b4a3 ; Sat, 4 Jan 2014 20:47:25 -0500
Received: from MSMR-GH1-UEA08.corp.nsa.gov ( by MSHT-GH1-UEA02.corp.nsa.gov ( with Microsoft SMTP Server (TLS) id 14.2.342.3; Sat, 4 Jan 2014 20:48:13 -0500
Received: from MSMR-GH1-UEA03.corp.nsa.gov ([]) by MSMR-GH1-UEA08.corp.nsa.gov ([]) with mapi id 14.01.0289.001; Sat, 4 Jan 2014 20:48:13 -0500
From: "Igoe, Kevin M." <kmigoe@nsa.gov>
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: 40 long loop, not 40 bit loop
Thread-Index: AQHPCbgxwT9LWRjbJE2posWREnpjhQ==
Date: Sun, 05 Jan 2014 01:48:12 +0000
Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CABA99F816@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-originating-ip: []
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: [Cfrg] 40 long loop, not 40 bit loop
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 01:48:23 -0000

Make that 40 long loop, not 40 bit loop.

(Proofreading on a Blackberry is a torturous task.  I'm not sure why Pres. Obama is so addicted to these things!)

----- Original Message -----
From: Igoe, Kevin M.
Sent: Saturday, January 04, 2014 08:41 PM Eastern Standard Time
To: 'cfrg@irtf.org' <cfrg@irtf.org>
Subject: 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.  

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) )
        Bad.append( (x,r) )

if len(Good) == 0:
    raise ValueError
    return Good[0]

 - 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