Re: [TLS] STRAW POLL: Size of the Minimum FF DHE group

Manuel Pégourié-Gonnard <mpg@polarssl.org> Wed, 05 November 2014 11:23 UTC

Return-Path: <mpg@polarssl.org>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3E0AD1A1BA3 for <tls@ietfa.amsl.com>; Wed, 5 Nov 2014 03:23:23 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.397
X-Spam-Level:
X-Spam-Status: No, score=0.397 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HELO_MISMATCH_COM=0.553, HOST_EQ_NL=1.545, MIME_8BIT_HEADER=0.3, SPF_PASS=-0.001] autolearn=no
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 UYgT7rahYZfS for <tls@ietfa.amsl.com>; Wed, 5 Nov 2014 03:23:21 -0800 (PST)
Received: from vps2.offspark.com (vps2.brainspark.nl [141.138.204.106]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C16421A1B3C for <tls@ietf.org>; Wed, 5 Nov 2014 03:23:21 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=polarssl.org; s=exim; h=Subject:Content-Transfer-Encoding:Content-Type:In-Reply-To:References:To:MIME-Version:From:Date:Message-ID; bh=zcAD54BwE8AlW0x3bFvH4z6Zm8hTsv1appB9IIulPdQ=; b=ATTq26v8NCwF4d6RbhjPGYZUqbLJy1z2oVyvZaNMYPVdayl5ivAzjU04N6uL52DmHrM2Y2O7iCtPsCf7+hMjF9r/eUDk6QrRGKHB/0kLa0jSYL3H5JUte5RuwKKjb9MiZXGmkSFYGZSQFYujR92O2ApEuYJt5Ln+ZbpHNF4tgZk=;
Received: from thue.elzevir.fr ([88.165.216.11] helo=[192.168.0.124]) by vps2.offspark.com with esmtpsa (TLS1.2:DHE_RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <mpg@polarssl.org>) id 1XlygC-0003jV-5J; Wed, 05 Nov 2014 12:23:13 +0100
Message-ID: <545A08A4.7090400@polarssl.org>
Date: Wed, 05 Nov 2014 12:23:16 +0100
From: Manuel Pégourié-Gonnard <mpg@polarssl.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.2.0
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>, "tls@ietf.org" <tls@ietf.org>
References: <8E6B8F53-9E8C-46B2-A721-85E918576F3A@ieca.com> <20141105012314.GG23599@mournblade.imrryr.org> <CACsn0ckLpGnxjaiFwEUc7dn6BXXHg30oKyyS5Ub58LUPJPyrFA@mail.gmail.com>
In-Reply-To: <CACsn0ckLpGnxjaiFwEUc7dn6BXXHg30oKyyS5Ub58LUPJPyrFA@mail.gmail.com>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 7bit
X-SA-Exim-Connect-IP: 88.165.216.11
X-SA-Exim-Mail-From: mpg@polarssl.org
X-SA-Exim-Version: 4.2.1 (built Mon, 26 Dec 2011 16:24:06 +0000)
X-SA-Exim-Scanned: Yes (on vps2.offspark.com)
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/ofiO_Vf3T-F9ujRCiahxVXBx-nE
Subject: Re: [TLS] STRAW POLL: Size of the Minimum FF DHE group
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 05 Nov 2014 11:23:23 -0000

On 05/11/2014 03:19, Watson Ladd wrote:
> On Tue, Nov 4, 2014 at 5:23 PM, Viktor Dukhovni <ietf-dane@dukhovni.org> wrote:
>> Basically, what's the expected ratio of DH-per-second between the
>> two proposed field sizes, and between the 2048-bit group and $F_p$
>> with $q = (p-1)/2$ and $p$ a 2048-bit Sophie-Germain prime.  Is
>> the "new" 2432 as fast or faster than the "old" 2048?
> 
> Slower, by a quadratic factor assuming standard algorithms for bignum
> arithmetic. No acceleration of either is possible, and for good
> reason: SNFS uses the same characteristics as we would use to optimize
> arithmetic.
> 
Unless I'm mistaken, if textbook multiplication is used, it's rather cubic:
multiplication is quadratic, and the length of the exponent, which is roughly
the number of multiplications, is linear in the size of the group.

Which gives a 67% performance penalty for 2432 compared to 2048

Now, for this size, Karatsuba is probably the best multiplication algorithm,
which is about n^1.58, so a total of n^2.58 for exponentiation, which gives a
performance penalty of 58% with this algorithm.

Manuel.