Re: [TLS] Another INRIA bug in TLS

Jeffrey Walton <noloader@gmail.com> Fri, 22 May 2015 22:37 UTC

Return-Path: <noloader@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 D38F31A898A for <tls@ietfa.amsl.com>; Fri, 22 May 2015 15:37:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 vVsLJwzgNrEt for <tls@ietfa.amsl.com>; Fri, 22 May 2015 15:37:55 -0700 (PDT)
Received: from mail-ie0-x22a.google.com (mail-ie0-x22a.google.com [IPv6:2607:f8b0:4001:c03::22a]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 156FB1A896A for <tls@ietf.org>; Fri, 22 May 2015 15:37:55 -0700 (PDT)
Received: by ieczm2 with SMTP id zm2so41112396iec.1 for <tls@ietf.org>; Fri, 22 May 2015 15:37:54 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:reply-to:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; bh=3uKyOIHKKH0KvKcqiZP+DA2ZDB/GwBCQwGjh9kQudqg=; b=TFx27jXKZCB5g/uN2wmrWQ9RQ8LMbrBCHuA+pydxjxtKAx110VzcCeBuX4LTIGNxi7 5/9yjAIgQuyOCqgO4RPTGHJL92qYcTTkZXrrjOh+N/+6Os+tkC99dkKrpSpEp+DidHEC oJx3l305LFrE/hKy8b34QyM7n99rGR1bmD3BIlkrlZu7BUVDkAcE7gcC09jgkRYOiHFk Psh2f7KLKagmkmXMD5rN0OGUpyF7CgF7pFh8hgneW2KLYwkP0klh9Bs0BdcRFa2nIQOH tl7BVQcO42vjRqB0G1+igAhT7wV1tTtAVH9iNWskTw/NObLeICZrZ5NOUMkbzgzNaSRM EggQ==
MIME-Version: 1.0
X-Received: by 10.43.58.206 with SMTP id wl14mr440869icb.36.1432334274633; Fri, 22 May 2015 15:37:54 -0700 (PDT)
Received: by 10.36.77.15 with HTTP; Fri, 22 May 2015 15:37:54 -0700 (PDT)
In-Reply-To: <87pp5snxha.fsf@alice.fifthhorseman.net>
References: <9A043F3CF02CD34C8E74AC1594475C73AB029727@uxcn10-tdc05.UoA.auckland.ac.nz> <1432317148442.5357@microsoft.com> <87pp5snxha.fsf@alice.fifthhorseman.net>
Date: Fri, 22 May 2015 18:37:54 -0400
Message-ID: <CAH8yC8k8C_PJqwJe38hjtaHhcga5iSZ2+sRx8EOQAp9E8SfZ+w@mail.gmail.com>
From: Jeffrey Walton <noloader@gmail.com>
To: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/T7v-UagJzBaKCgYWF4BBjfR_8j4>
Cc: "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] Another INRIA bug in TLS
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: noloader@gmail.com
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 22:37:57 -0000

On Fri, May 22, 2015 at 4:55 PM, Daniel Kahn Gillmor
<dkg@fifthhorseman.net> wrote:
> [ 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
>
M-R is one check, but there are others. For example, trial division
and the choice of g in a group (g may not necessarily be a generator).

As a practical example from a guy who regularly validates all
parameters, see
http://crypto.stackexchange.com/questions/17707/trial-divisions-before-miller-rabin-checks
and http://crypto.stackexchange.com/questions/12961/diffie-hellman-parameter-check-when-g-2-must-p-mod-24-11.

What I found in the past that the IETF's choice of g = 2 meant that
various DH_param_check(...) would fail.

Jeff