Re: [TLS] Negotiated Discrete Log DHE revision [was: Re: Confirming Consensus on removing RSA key Transport from TLS 1.3]

Fedor Brunner <fedor.brunner@azet.sk> Sat, 12 April 2014 10:19 UTC

Return-Path: <fedor.brunner@azet.sk>
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 7C20C1A0402 for <tls@ietfa.amsl.com>; Sat, 12 Apr 2014 03:19:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.333
X-Spam-Level: **
X-Spam-Status: No, score=2.333 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HELO_EQ_SK=1.35, HOST_EQ_SK=0.555, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.272, 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 UrGnyhaC9bpE for <tls@ietfa.amsl.com>; Sat, 12 Apr 2014 03:19:47 -0700 (PDT)
Received: from smtp-01-out.s.azet.sk (smtp-05-out.s.azet.sk [91.235.53.55]) by ietfa.amsl.com (Postfix) with ESMTP id 1C7891A03FE for <tls@ietf.org>; Sat, 12 Apr 2014 03:19:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=azet.sk; s=azet; t=1397297983; bh=7z3P6fzaiBhkrD4hajvBP5d0JZpAOVsC/I1KDLhXBJU=; h=Date:From:To:Subject:References:In-Reply-To:From; b=wPeStaIW5+wXJHfKFs+FmjSBlTGdYJKLSOaJMO6zB+IxaLT9u5jpJ4CfrxSuMOo8S pbb0YDqzDSTEa8C4v5mhWjsXMPpstmVrH0DL1NWSQnjRCUq5MRkelMLoyB3/n9W/Qm sChBG2YoD/eWHwXS+r7mzf1ZIfp+1YfNOd0TbAKI=
X-Virus-Scanned: by AntiSpam at azet.sk
Received: from [0.0.0.0] (afo8.torproject.afo-tm.org [178.254.39.32]) (Authenticated sender: fedor.brunner@azet.sk) by smtp.azet.sk (Postfix) with ESMTPA id AB2466B for <tls@ietf.org>; Sat, 12 Apr 2014 12:19:38 +0200 (CEST)
X-SenderID: Sendmail Sender-ID Filter v1.0.0 smtp.azet.sk AB2466B
Authentication-Results: smtp.azet.sk; sender-id=fail (NotPermitted) header.from=fedor.brunner@azet.sk; auth=pass (PLAIN); spf=fail (NotPermitted) smtp.mfrom=fedor.brunner@azet.sk
Message-ID: <53491338.6060503@azet.sk>
Date: Sat, 12 Apr 2014 12:19:36 +0200
From: Fedor Brunner <fedor.brunner@azet.sk>
MIME-Version: 1.0
To: tls@ietf.org
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> <53449A18.9000803@fifthhorseman.net> <5347EB9F.8030400@azet.sk> <534823E1.3020707@fifthhorseman.net>
In-Reply-To: <534823E1.3020707@fifthhorseman.net>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/QIVKno85TsYLr81gew9j7BBlfSI
Subject: Re: [TLS] Negotiated Discrete Log DHE revision [was: Re: Confirming Consensus on removing RSA key Transport from TLS 1.3]
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: Sat, 12 Apr 2014 10:19:49 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

On 11.04.2014 19:18, Daniel Kahn Gillmor wrote:
> On 04/11/2014 09:18 AM, Fedor Brunner wrote:
>> Your groups dldhe3072, dldhe4096 look similar to MODP groups 15, 16. If
>> you assume that an attack can be developed for MODP groups, could this
>> attack be also developed for dldhe3072, dldhe4096?
>
> probably, yes.  at the moment, i believe such an attack on any given
> group would be quite expensive in both time and money.  My hope is that
> it is prohibitively expensive in general, because of the large amount of
> computing power and data storage that would be needed to effectively map
> the space.  but it's possible that an extremely well-funded organization
> could pull it off.  will they be able to attack two groups in this way?
>  not without increasing the expenses even further.
>
> if we use a single group for everything (IKE as well as TLS), the cost
> of attacking that group stays the same, but the value of breaking the
> group goes up.
>
>> If you assume an attack exists for fixed DH group then not fixed  DH
>> groups generated for each server (as is current option in TLS) would
>> make the attack much more expensive.
>
> this is true, but it also makes it possible for bad groups to be used,
> either through malice or misconfiguration.  arbitrary groups also
> increases the size of the handshake significantly, and clients have no
> inexpensive way of verifying that the groups have reasonable structure
> and that they are not in a small subgroup.  With named groups, both
> peers can have pre-computed tables that should make ephemeral keying
> cheaper and easier, whereas with arbitrary groups only the server gets
> this advantage.
>
>> For example OpenSSH supplies a set of 40 DH groups for each 1023, 1535,
>> 2047, 3071, 4095, 6143, 8191-bit primes . During key exchange one of
>> these groups with desired size is selected in server by random. The
>> OpenSSH server administrator can also generate his own set DH
>> parameters, for each prime length.
>
> i'm aware of this model.  in practice, nearly everyone seems to be
> content using the moduli that are shipped by their vendor in
> /etc/ssh/moduli.
>
>> Could you please provide estimated strength of the dldhe2432,
dldhe3072, ...
>> groups ? For example see the estimated strength of MODP groups in RFC
3526
>>
>> https://tools.ietf.org/html/rfc3526#section-8
>
> yes, that's a good idea, thanks.
>
>> Please consider describing the algorithm for generation of the groups
>> dldhe2432, dldhe3072, ...
>> The generation of MODP groups is described in RFC 2412 (Appendix E)
>
> do you think the introduction to Appendix A is insufficient?  if so, do
> you have a concrete suggestion for how it should change?

You have stated why the high and low bits are ones (Montgomery or
Barrett reduction), please describe also the decision to use the base of
the natural logarithm for the middle part of discrete log groups.

For example in RFC 2412 (Appendix E)

"
The middle bits
   are taken from the binary expansion of pi.  This guarantees that they
   are effectively random, while avoiding any suspicion that the primes
   have secretly been selected to be weak.
"

>
>     --dkg

-----BEGIN PGP SIGNATURE-----

iQJ8BAEBCgBmBQJTSRM4XxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w
ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXQ4QkVFQ0NBRDcyNzU1RTk2RTQwMzlEQjc2
RTE3NDA5NTQwNTY2M0FEAAoJEG4XQJVAVmOtiQUQALTcHlrEMKK82SsLaHku1GLL
xg+eWZnhkHc36xkeMDQsvY6DIPRHbdyyqP79pdRGJt7ZJHJ53lXxYHoSepnarwNa
DFRcwP5HHwPMXpFlylnDXWcBrCalM00AgSUR6tGlHVpnxRnqajKYunLKqSl1/HYC
C9hWtyfv7M7J6lba/yq7rP6DDJEK1llGYYxCSwtO1qhXsg7gjTRjDCBIIYv5UIbU
CVsrmH7KNchxPID7CGjC0SQcJUATrxuGXtMpOqB7IwnvFNClQ75cDb4eISV6ye6U
vkA1xqVgiESp+LUERxOdQzRfL2UMILcNmBBqXYrvL10tW5oR2oRiteoHJLssYTUi
BMG9Y662j9EFh+x20TCITOdT/PZkEenpX88oTkMFa6Wxb9Ioz+PclX6V3KFb+RVy
nLYqYsuWZq7ewo+r1H+vWbi/tQBPtDbfGUF1akGvwsLhN7a4jJgPty/yCmtGebhr
rO//Wi8s1ecjvUBRlS4JN0/KMu/zDQJ8yUEPu9U1aBA7M7PPUF5ePuT9dNrnt5tQ
SSisxL/VVxiCeM3xs3ssBpA6bg9UUAFavTU/ngFpuBOw6/rfDvUQAPY+kAQ2d5os
5LaJQi/xUYAk0lyYK3inddyTh9wnp6n1ggoLI33DyibHPZfnh0vIsqpPAfSmeuv4
nyGb7zY1pEoi12n/01mE
=8X4w
-----END PGP SIGNATURE-----