[Cfrg] Rigidity and performance

Michael Hamburg <mike@shiftleft.org> Tue, 09 September 2014 18:31 UTC

Return-Path: <mike@shiftleft.org>
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 44FB31A88B7 for <cfrg@ietfa.amsl.com>; Tue, 9 Sep 2014 11:31:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 4.255
X-Spam-Level: ****
X-Spam-Status: No, score=4.255 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id IT2Y9Cmy_Zki for <cfrg@ietfa.amsl.com>; Tue, 9 Sep 2014 11:31:11 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net []) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4F1861A8969 for <cfrg@irtf.org>; Tue, 9 Sep 2014 11:27:26 -0700 (PDT)
Received: from [] (unknown []) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 7F21F3AA27 for <cfrg@irtf.org>; Tue, 9 Sep 2014 11:24:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1410287065; bh=H91+x9y4tkOAfkLTXUk1BYmpn/dA/yc36gHSckvVqIU=; h=From:Subject:Date:To:From; b=RM97fNXx1E6HAs32kx5YBgQF8A1mbkCiIIP2GuqBl9vzLSQKCe5/IdgMrumceG0G4 z/FD0Id1F4KaIzPjlzvefjlT0PHlztOmJQgbdr2cMcnx/VATTt1Sza/UReuyWPuAFk ENNTtSnEZRW7puKK18WAK0Hb/gBM9yTw0FH3Iu3g=
From: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Message-Id: <D1EFFB24-C4C1-4595-8F5A-A2834BBA8217@shiftleft.org>
Date: Tue, 09 Sep 2014 11:27:23 -0700
To: IRTF Crypto Forum Research Group <cfrg@irtf.org>
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1973.6\))
X-Mailer: Apple Mail (2.1973.6)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/TwF3GJ2uH-FHx3m1DtlG7qzXbKc
Subject: [Cfrg] Rigidity and performance
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: Tue, 09 Sep 2014 18:31:12 -0000

Hello CFRGers,

I tried to send this last night, and it was delivered to cfrg but didn’t go through somehow?  So I’m trying again with an abridged version.

It’s been argued a few times here that choosing primes for performance (or performance vs security trade-off) is too flexible.  In an effort to quantify how flexible this is, I searched for primes which could be advanced on these grounds in the range of about 192 to about 256 bits of security.  Specifically, I searched for primes which have something about their shape to recommend them (fast Montgomery or Barrett reduction, or Solinas or nearly-Solinas form).  I restricted my attention to primes which have the carry-handling properties that DJB and I have been recommending, on either 64-bit platforms or both 64-bit and 32-bit.

I also searched for numbers which had a nice shape and were not prime themselves, but were divisible by a large prime.

I then wrote a partial order on these primes, where one prime is potentially better than another if it’s 3 mod 4, or 5 mod 8, or larger, or sparser, or has fewer limbs, or has fewer non-1 coefficients, or has a Montgomery-friendly or Barrett-friendly or Karatsuba-friendly shape.  I eliminated primes which could not be defended because another prime in the same class was clearly better on every axis.  For example, 2^416 - 2^208 - 1 has the same performance as 2^448 - 2^224 - 1 on almost any platform, has the same sparsity and shape, the same residue mod 8, and so on, but it’s smaller and therefore has a worse security vs performance tradeoff.

Surely I missed some, but the goal of this exercise was to determine whether the number of primes which can be advanced on security vs performance reasons is in the dozens, or in the thousands or millions.  Here is what I found:

Performance should be fine on 32-bit or 64-bit machines:
2^521 - 1
  NIST-P521, E-521, of course.

2^392 - 2^280 + 1
  Good on 32-bit or 64-bit machines; 14 or 7 limbs
  This might not be a terrible idea at 192-bit security, since it falls within the 4-rho-bit limit set by Kenny.
  Too bad it’s 1 mod 8.

2^414 - 17

2^448 - 2^224 - 1

 2^416 - 18*2^364 + 1
  This is probably actually terrible, but it’s suitable for signed Montgomery reduction.

 2^408 - 13*2^204 - 11
  The best 5-mod-8 not-quite-Solinas-quadratic prime.  Probably terrible.

 (2^424 - 2^212 - 1) / 11
  Faster than the above prime but has a “cofactor"; clearly worse than Goldilocks unless you need 5 mod 8.

Performance is only good on 64-bit machines:
2^406 - 2^174 + 1
  Solinas, 7 limbs.

2^480 - 2^240 - 1 

2^480 - 47
  Nice except that it’s 1 mod 8.

 2^468 - 17
  3 mod 4.  There might be a larger prime with a bigger coefficient; I only searched up to -50.

 2^470 - 35
  5 mod 8.

 2^456 - 8*2^399 - 1
  Montgomery form.

As listed, some of these primes are probably not actually good enough to be advanced even on performance grounds, but then again, there are probably some other options which could be advanced.

Of this baker’s dozen of primes, four have already been proposed for cryptographic purposes.  This might just mean I’m not very creative, but it might also mean that the space of high-performance primes isn’t all that large.

— Mike