Re: [TLS] Another INRIA bug in TLS

Andrey Jivsov <crypto@brainhub.org> Fri, 22 May 2015 23:27 UTC

Return-Path: <crypto@brainhub.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 01F281A0382 for <tls@ietfa.amsl.com>; Fri, 22 May 2015 16:27:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 ELiBZhz3Ms78 for <tls@ietfa.amsl.com>; Fri, 22 May 2015 16:27:41 -0700 (PDT)
Received: from resqmta-po-02v.sys.comcast.net (resqmta-po-02v.sys.comcast.net [IPv6:2001:558:fe16:19:96:114:154:161]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B3E001A0318 for <tls@ietf.org>; Fri, 22 May 2015 16:27:40 -0700 (PDT)
Received: from resomta-po-04v.sys.comcast.net ([96.114.154.228]) by resqmta-po-02v.sys.comcast.net with comcast id XBTQ1q0074vw8ds01BTgdm; Fri, 22 May 2015 23:27:40 +0000
Received: from [IPv6:::1] ([71.202.164.227]) by resomta-po-04v.sys.comcast.net with comcast id XBTe1q00K4uhcbK01BTeCG; Fri, 22 May 2015 23:27:39 +0000
Message-ID: <555FBB6A.7040508@brainhub.org>
Date: Fri, 22 May 2015 16:27:38 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: tls@ietf.org
References: <9A043F3CF02CD34C8E74AC1594475C73AB029727@uxcn10-tdc05.UoA.auckland.ac.nz> <1432317148442.5357@microsoft.com> <87pp5snxha.fsf@alice.fifthhorseman.net> <BLUPR03MB13963BE37177243E5B89262B8CC00@BLUPR03MB1396.namprd03.prod.outlook.com>
In-Reply-To: <BLUPR03MB13963BE37177243E5B89262B8CC00@BLUPR03MB1396.namprd03.prod.outlook.com>
Content-Type: text/plain; charset="windows-1252"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1432337260; bh=cLOFmmr/Ztg7fFvxOkegt65gXFSYLbOR8X8CXPQLlvE=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=bYt18lkTciLc7LZ+oZ+XNFtrAGpKxoUF9B3bbcOQGB8If/QKIKmAVO6wnyNbK3pic KXcWbgmVjjOGxXIz7Qma4kSbhfWqHJHJae3MVRZkLzk/EbeanhTgFznleccYs/sMgD GGWYrxS68JlJMxi69Gz4sOyrRNGW4ZiKBZGsoo2E80AFWqr3pbroEC7u2XZZy1i1wd q33B4czbpYF1hlZnrlKi6dCPEbmhRB7RSq5P1FWV+zE/pNt2jgpC1JJ+KGCk7erOp3 NzuihuFubkgkndddPxhHSUcthksxeouG045wZBNzFK9E5IP8ze1Q0UpTekZ8boK4cr E4bYxV9ir+3Sw==
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/aip9b_3GTvrJdq1lsBaRbVWLR28>
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 23:27:45 -0000

On 05/22/2015 02:09 PM, Andrei Popov wrote:
> 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.
>

( Correct me if I am wrong, but I thought that IE only offered DHE with 
DSS until the last year, when a security update added DHE support with 
RSA. Last time I checked the IE's ClientHello this year, there were no 
DHE+RSA in IE 11, supposedly without that security update. )

What I wonder here about is the support for DHE 2048 by the (legacy) 
clients on the Internet. If the server will start sending DHE 2048 in 
the ServerKeyExchange, the DHE handshakes with older clients will fail, 
with a fallback to even less secure ciphersuites. The only way I see 
these old clients not failing is when these clients don't offer DHE in 
the ClientHello, but then there is no clear benefit to upgrade the 
server to send DHE 2048.

If ECDHE P-256 cannot be used, and absent any DHE size 
negotiation/signaling mechanism, fixing TLS clients not to accept short 
groups with non-export ciphersuites, which enabled the TS-specific 
attack, and perhaps switching to periodically regenerated DHE 1024 
groups looks like the safest plan.

To rephrase, what's the slice of the Internet that cannot do DHE P-256 
but can do DHE 2048?

> 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
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>