Re: [TLS] Another INRIA bug in TLS

Andrei Popov <Andrei.Popov@microsoft.com> Fri, 22 May 2015 21:09 UTC

Return-Path: <Andrei.Popov@microsoft.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 AE20F1A8889 for <tls@ietfa.amsl.com>; Fri, 22 May 2015 14:09:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-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 17eTKhvrXRaT for <tls@ietfa.amsl.com>; Fri, 22 May 2015 14:09:31 -0700 (PDT)
Received: from na01-by2-obe.outbound.protection.outlook.com (mail-by2on0126.outbound.protection.outlook.com [207.46.100.126]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EE8081A8892 for <tls@ietf.org>; Fri, 22 May 2015 14:09:29 -0700 (PDT)
Received: from BLUPR03MB1396.namprd03.prod.outlook.com (10.163.81.142) by BLUPR03MB1393.namprd03.prod.outlook.com (10.163.81.14) with Microsoft SMTP Server (TLS) id 15.1.166.22; Fri, 22 May 2015 21:09:27 +0000
Received: from BLUPR03MB1396.namprd03.prod.outlook.com ([10.163.81.142]) by BLUPR03MB1396.namprd03.prod.outlook.com ([10.163.81.142]) with mapi id 15.01.0166.017; Fri, 22 May 2015 21:09:27 +0000
From: Andrei Popov <Andrei.Popov@microsoft.com>
To: Daniel Kahn Gillmor <dkg@fifthhorseman.net>, "tls@ietf.org" <tls@ietf.org>
Thread-Topic: [TLS] Another INRIA bug in TLS
Thread-Index: AQHQlNG6+AHsQvXpsUGOwpc7u3GouZ2IekhA
Date: Fri, 22 May 2015 21:09:26 +0000
Message-ID: <BLUPR03MB13963BE37177243E5B89262B8CC00@BLUPR03MB1396.namprd03.prod.outlook.com>
References: <9A043F3CF02CD34C8E74AC1594475C73AB029727@uxcn10-tdc05.UoA.auckland.ac.nz> <1432317148442.5357@microsoft.com> <87pp5snxha.fsf@alice.fifthhorseman.net>
In-Reply-To: <87pp5snxha.fsf@alice.fifthhorseman.net>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Andrei.Popov@microsoft.com;
x-originating-ip: [2001:4898:80e8:ed31::2]
x-microsoft-exchange-diagnostics: 1; BLUPR03MB1393; 3:TlstlRw7hZFPIARrqEXz++iz1E8XZjpskqLvm8XGvLj07fHwsF2Oom/MhnAzceutNoNApipAxkpOOgCnBcDw77Vxt+sFfN0IdqJ9A/iD6P6/YG1yqq5XB1bYltWBeIuhhXkchn1K2BQ9KmKuHBeiew==; 10:TDwM7aCwK4DAoapJPu3up4yvMkijtrSDLGQD8X6yNA4LyXmJIXr/HIy69SYKaspsdJLjIx1+8r58wAy6PIafljBl5MG25VfUR7feFIbl+EU=; 6:6xYmYfidt1syU5Zx+pMvwFnKC8jRbrgCR28jcoO4Z/57e2zLe8Nz3YXeCNIvPcwb
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BLUPR03MB1393;
x-microsoft-antispam-prvs: <BLUPR03MB1393018F1E87FEA1566B3C818CC00@BLUPR03MB1393.namprd03.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(2401001)(5005006)(520002)(3002001); SRVR:BLUPR03MB1393; BCL:0; PCL:0; RULEID:; SRVR:BLUPR03MB1393;
x-forefront-prvs: 058441C12A
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(6009001)(24454002)(13464003)(377424004)(51704005)(377454003)(189002)(199003)(87936001)(33656002)(19580405001)(46102003)(81156007)(74316001)(107886002)(77156002)(62966003)(189998001)(40100003)(122556002)(19580395003)(4001540100001)(97736004)(101416001)(2656002)(105586002)(5001960100002)(92566002)(86362001)(15975445007)(77096005)(102836002)(2950100001)(2900100001)(68736005)(50986999)(54356999)(76176999)(5001830100001)(64706001)(5001860100001)(99286002)(106356001)(5001770100001)(2501003)(86612001)(106116001)(76576001)(3826002); DIR:OUT; SFP:1102; SCL:1; SRVR:BLUPR03MB1393; H:BLUPR03MB1396.namprd03.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
received-spf: None (protection.outlook.com: microsoft.com does not designate permitted sender hosts)
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: microsoft.com
X-MS-Exchange-CrossTenant-originalarrivaltime: 22 May 2015 21:09:26.2867 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BLUPR03MB1393
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/IhESioZ_XsJ4pVsfRIbW9xSakNc>
Subject: Re: [TLS] Another INRIA bug in TLS
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: Fri, 22 May 2015 21:09:33 -0000

I agree that sufficiently large known groups make precomputation infeasible, and also simplify both client and server implementation.

So the immediate mitigation could be for clients to stop accepting small DH groups, and for servers to send larger DH groups (this will of course create interop issues, esp. initially).

In the long term, it may become possible to only allow DHE cipher suites when a known group has been negotiated using draft-ietf-tls-negotiated-ff-dhe.

Cheers,

Andrei

-----Original Message-----
From: TLS [mailto:tls-bounces@ietf.org] On Behalf Of Daniel Kahn Gillmor
Sent: Friday, May 22, 2015 1:55 PM
To: tls@ietf.org
Subject: Re: [TLS] Another INRIA bug in TLS

[ i fixed typo in the Subject line because it bothered me; sorry if that
  kills threading in anyone's MUA ]

On Fri 2015-05-22 13:52:29 -0400, Santiago Zanella-Beguelin wrote:
>>>A miTLS client maintains a table of known trusted parameters, 
>>>including the subgroup order for parameters with non-safe primes. 
>>>When receiving unknown parameters from a server, it tests the 
>>>primality of p and (p-1)/2 to check if p is a safe prime (and caches a positive result in the table).
>> 
>>So you do a full primality test (Miller-Rabin or whatever) for each connect?
>
> No. We do primality tests only if the prime isn't in the cache. That 
> happens the first time the client connects to a server, or when the 
> server refreshes its parameters. That, assuming the parameters aren't 
> already in the pre-populated cache.
>
>>Doesn't that make it awfully slow?
>
> No. The typical cost of validation is just one table lookup. This 
> works extremely well when people use just a few thousand parameters 
> and don't change them often. Even if that changes in light of Logjam 
> (I hope it does!), online primality tests for every connection are not 
> prohibitive. I did a quick test using Sage and the stock 
> is_pseudoprime: testing if a 2048-bit prime is safe takes ~180ms in a 
> laptop, while computing two DH operations (exponentiations) takes ~17ms. The amortized cost using a cache is of course much lower.

I'm considering adding a Miller-Rabin primality check for the group modulus to negotiated-ff-dhe's "Local Policy for Custom Groups" section:

 https://tools.ietf.org/html/draft-ietf-tls-negotiated-ff-dhe-09#section-3.1

I'm also considering adding a suggestion for checking that the modulus is a safe prime, if it is not already known to the client to be an acceptable modulus.  What do others think about either of these additions?

----

I see how the idea of every server choosing their own groups makes sense From a crypto theory point of view, and if everyone does it right, it would indeed probably be the best situation.

I have concerns about it from a practical perspective, though.

A client encountering a novel group now has to make a choice about whether to perform some tests on the group (as suggested above) or to proceed without testing (hoping that the server picked the right parameters).  Since TLS clients are in tension between the demands of efficiency (make connections faster and cheaper for your user) and security (ensure the integrity and confidentiality of your user's communications), many will be tempted to skip the extra checks, since if the remote servers are well-configured, the check should be unnecessary.

Furthermore, generating a large safe prime group is expensive and slow, which puts it out of reach of many devices that act as TLS servers, which practically might mean we're delegating the job of prime selection to implementors or software distributors.

As a case in point, the SSH protocol provides custom moduli, but i believe most SSH servers ship with a set of default moduli (e.g. the OpenSSH project ships a default set of moduli), and everyone just uses those.  In the OpenSSH case, the upstream moduli appear to be generated, tested and found to be safe primes on the basis of 100 rounds of Miller-Rabin (see moduli(5) and /etc/ssh/moduli on a debian system, for example), instead of generating proofs of primality (which are significantly more expensive).

Yesterday, OpenSSH updated the set of moduli they'll be distributing for the first time in 3 years [0] (this is better than the oakley groups, which haven't been updated!).  The new ones were also tested on the basis of 100 rounds of Miller-Rabin.  There is also discussion on the openssh-unix-dev mailing list that different distributions might consider shipping different sets of moduli, though this could potentially introduce a distro-fingerprinting attack in places where such an attack might not already exist.

We need protocol designs that simplify things for implementators and deployers, and that remove the need for expensive security checks that might be skipped for efficiency reasons. sufficiently large known-groups seem to solve that problem, as long as we deprecate smaller groups promptly.  I'm not sure that encouraging custom groups does, even though it sounds like it would be the safer option when everyone is playing by the best practice guidelines.

      --dkg

[0] https://anongit.mindrot.org/openssh.git/commit/?id=8b02481143d75e91c49d1bfae0876ac1fbf9511a