[Cfrg] 40 bit loop and DragonFly

"Igoe, Kevin M." <kmigoe@nsa.gov> Sun, 05 January 2014 01:41 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 [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0105F1AE0D9 for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 17:41:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.539
X-Spam-Level:
X-Spam-Status: No, score=-5.539 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, RCVD_IN_DNSWL_HI=-5, RP_MATCHES_RCVD=-0.538] 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 Z9CzM6k9__fc for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 17:41:36 -0800 (PST)
Received: from nsa.gov (emvm-gh1-uea09.nsa.gov [63.239.67.10]) by ietfa.amsl.com (Postfix) with ESMTP id 3090F1AE0D6 for <cfrg@irtf.org>; Sat, 4 Jan 2014 17:41:36 -0800 (PST)
X-TM-IMSS-Message-ID: <48c79cba00052ae9@nsa.gov>
Received: from MSHT-GH1-UEA01.corp.nsa.gov ([10.215.227.18]) by nsa.gov ([63.239.67.10]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 48c79cba00052ae9 ; Sat, 4 Jan 2014 20:41:44 -0500
Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSHT-GH1-UEA01.corp.nsa.gov ([10.215.227.18]) with mapi id 14.02.0342.003; Sat, 4 Jan 2014 20:41:26 -0500
From: "Igoe, Kevin M." <kmigoe@nsa.gov>
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: 40 bit loop and DragonFly
Thread-Index: Ac8Jtz8QHBqZuWIRSrC0AhG0eZjDKg==
Date: Sun, 5 Jan 2014 01:41:25 +0000
Message-ID: <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.215.227.232]
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: [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 01:41:38 -0000

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