Re: [TLS] Negotiated Discrete Log DHE revision

Samuel Neves <sneves@dei.uc.pt> Wed, 09 April 2014 10:51 UTC

Return-Path: <sneves@dei.uc.pt>
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 CD7221A0217 for <tls@ietfa.amsl.com>; Wed, 9 Apr 2014 03:51:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.873
X-Spam-Level:
X-Spam-Status: No, score=-2.873 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.272, 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 Q9qc78wpqDrg for <tls@ietfa.amsl.com>; Wed, 9 Apr 2014 03:51:22 -0700 (PDT)
Received: from smtp.dei.uc.pt (smtp.dei.uc.pt [193.137.203.253]) by ietfa.amsl.com (Postfix) with ESMTP id F0D6F1A01FA for <tls@ietf.org>; Wed, 9 Apr 2014 03:51:21 -0700 (PDT)
Received: from [194.210.172.187] ([194.210.172.187]) (authenticated bits=0) by smtp.dei.uc.pt (8.14.4/8.14.4) with ESMTP id s39ApGvt024859 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Wed, 9 Apr 2014 11:51:22 +0100
Message-ID: <53452609.9040304@dei.uc.pt>
Date: Wed, 09 Apr 2014 11:50:49 +0100
From: Samuel Neves <sneves@dei.uc.pt>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>
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> <CACsn0cnoxQcQvRGg39jOZCVbpnB4=QPLaak4JYDqjBdsCVwMWw@mail.gmail.com>
In-Reply-To: <CACsn0cnoxQcQvRGg39jOZCVbpnB4=QPLaak4JYDqjBdsCVwMWw@mail.gmail.com>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-FCTUC-DEI-SIC-MailScanner-Information: Please contact helpdesk@dei.uc.pt for more information
X-FCTUC-DEI-SIC-MailScanner-ID: s39ApGvt024859
X-FCTUC-DEI-SIC-MailScanner: Found to be clean
X-FCTUC-DEI-SIC-MailScanner-SpamCheck: not spam, SpamAssassin (not cached, score=-60.25, required 3.252, autolearn=not spam, ALL_TRUSTED -10.00, BAYES_00 -0.25, L_SMTP_AUTH -50.00)
X-FCTUC-DEI-SIC-MailScanner-From: sneves@dei.uc.pt
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/qvqGqPWDxd3205hE3YPP00uAaC8
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 10:51:27 -0000

On 09-04-2014 06:07, Watson Ladd wrote:
> 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).

Sorry, I was not clear. I was not associating any particular property with e; any choice of constant will have roughly
the same expected ~2^24 attempts. That e happens to require more is a statistical accident.