Re: [TLS] Negotiated Discrete Log DHE revision

Watson Ladd <watsonbladd@gmail.com> Wed, 09 April 2014 05:07 UTC

Return-Path: <watsonbladd@gmail.com>
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 7B7991A00E1 for <tls@ietfa.amsl.com>; Tue, 8 Apr 2014 22:07:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.6
X-Spam-Level:
X-Spam-Status: No, score=-0.6 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] 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 QH_r9wyxi_hc for <tls@ietfa.amsl.com>; Tue, 8 Apr 2014 22:07:10 -0700 (PDT)
Received: from mail-yh0-x231.google.com (mail-yh0-x231.google.com [IPv6:2607:f8b0:4002:c01::231]) by ietfa.amsl.com (Postfix) with ESMTP id CBF5C1A00BC for <tls@ietf.org>; Tue, 8 Apr 2014 22:07:09 -0700 (PDT)
Received: by mail-yh0-f49.google.com with SMTP id z6so1887491yhz.36 for <tls@ietf.org>; Tue, 08 Apr 2014 22:07:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=EpqDrax/+5FSMsOQ7vw0dNSHlkRqG4b1bq/JYtqk1r4=; b=kKNp2o4aZ1qGzfHdJFCQtiwsMpF+FXvpuV+XuFJAA2OspZrJAY8KKih9e51yr7t5wv Dj0OuoNeEBSsQxpbowD8gjfuTa2dB8gNNJ5I8mrev9dNYfQ2cSwBuJYKt6lcWPECnClK 8fuxYKOsGk0naBvz4T2QX9kT1FlQ6nd4+C0MGxY8KZl2zd3E4g5zUZRdAwwm/TyspbI+ Rk7cKuQA+Y1cbtEUbTs2ZlLUAGADCoMIcYFYHHq982RKxiAy6wU/t9f4n9Cz8dJc8nwy rSmJZ/aSPIPq12GckIo48X1AALjB4FERf0fhBazVk8y1fD4yLHxpGDVO2x8//Zs70U71 IswA==
MIME-Version: 1.0
X-Received: by 10.236.230.41 with SMTP id i39mr11748421yhq.14.1397020029208; Tue, 08 Apr 2014 22:07:09 -0700 (PDT)
Received: by 10.170.63.197 with HTTP; Tue, 8 Apr 2014 22:07:09 -0700 (PDT)
In-Reply-To: <5344B22F.5010903@dei.uc.pt>
References: <AD51D38F-2CFE-4277-854D-C0E56292A336@cisco.com> <20140326211219.27D281AC7D@ld9781.wdf.sap.corp> <20140327095527.5335c7fa@hboeck.de> <533622F3.2090406@fifthhorseman.net> <87eh18xtrl.fsf@alice.fifthhorseman.net> <53442983.1030703@pobox.com> <5344303C.2050607@pobox.com> <53443ADD.3040008@streamsec.se> <53449D64.8070806@fifthhorseman.net> <5344B22F.5010903@dei.uc.pt>
Date: Tue, 08 Apr 2014 22:07:09 -0700
Message-ID: <CACsn0cnoxQcQvRGg39jOZCVbpnB4=QPLaak4JYDqjBdsCVwMWw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Samuel Neves <sneves@dei.uc.pt>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/PNu7MSdXi_UafCcK7eSWhI11uv0
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] Negotiated Discrete Log DHE revision
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, 09 Apr 2014 05:07:14 -0000

On Tue, Apr 8, 2014 at 7:36 PM, Samuel Neves <sneves@dei.uc.pt> wrote:
> On 09-04-2014 02:07, Daniel Kahn Gillmor wrote:
>>
>> I confess i don't see why the safe primes should be farther for this
>> construction than a similar construction with pi, but it certainly seems
>> to be the case.  Is there a reference that i should read to understand
>> this better?
>>
>
> It seems to be an unlucky choice. The probability that p is prime is roughly
> 1/log(p) by the Prime Number Theorem. Assuming independence, the probability
> that (p-1)/2 is also prime can be given by the same expression. Thus we can
> get a rough approximation of the number of integers to go through: log(p)^2.
> In the case of p ~ 2^6144, the expected iteration number is ~2^24.

I don't see why e inherently has this property. Granted this is
probably deep (and nobody at Berkeley does this, so I have no clue),
although it is worth noting that the bounds on pi(x) are quite weak in
comparison to the asymptotics. (It could of course be a quirk of small
numbers).

Burn enough computer time and generation will stop. Once it does
validation (not of minimality) is fairly quick, and we can make a
certificate to enable fast ECPP checking. Minimality certification is
tough: even safecurves.cr.yp.to doesn't do it.

If you give up and want another transcendental constant, \zeta(3)
(Apéry's constant) could be worth a look. So could \e^{\pi}. Logs of
small integers could also work. Alternatively we could use the
precomputed groups for the larger orders: the damage from shared
factor bases is most acute when the group size is close to breakable.

Sincerely,
Watson Ladd

>
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin