Re: [TLS] Another IRINA bug in TLS

Santiago Zanella-Beguelin <santiago@microsoft.com> Fri, 22 May 2015 17:52 UTC

Return-Path: <santiago@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 0C2B41A87BC for <tls@ietfa.amsl.com>; Fri, 22 May 2015 10:52:55 -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 2alVBg8gbTb1 for <tls@ietfa.amsl.com>; Fri, 22 May 2015 10:52:52 -0700 (PDT)
Received: from na01-bl2-obe.outbound.protection.outlook.com (mail-bl2on0148.outbound.protection.outlook.com [65.55.169.148]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 13AD11A87E7 for <tls@ietf.org>; Fri, 22 May 2015 10:52:36 -0700 (PDT)
Received: from CO2PR03CA0038.namprd03.prod.outlook.com (10.141.194.165) by BL2PR03MB289.namprd03.prod.outlook.com (10.141.68.12) with Microsoft SMTP Server (TLS) id 15.1.166.22; Fri, 22 May 2015 17:52:34 +0000
Received: from BN1AFFO11FD045.protection.gbl (2a01:111:f400:7c10::179) by CO2PR03CA0038.outlook.office365.com (2a01:111:e400:1414::37) with Microsoft SMTP Server (TLS) id 15.1.160.16 via Frontend Transport; Fri, 22 May 2015 17:52:33 +0000
Authentication-Results: spf=pass (sender IP is 206.191.250.196) smtp.mailfrom=microsoft.com; cs.auckland.ac.nz; dkim=none (message not signed) header.d=none;
Received-SPF: Pass (protection.outlook.com: domain of microsoft.com designates 206.191.250.196 as permitted sender) receiver=protection.outlook.com; client-ip=206.191.250.196; helo=064-smtp-out.microsoft.com;
Received: from 064-smtp-out.microsoft.com (206.191.250.196) by BN1AFFO11FD045.mail.protection.outlook.com (10.58.53.60) with Microsoft SMTP Server (TLS) id 15.1.172.14 via Frontend Transport; Fri, 22 May 2015 17:52:31 +0000
Received: from DB4PR30MB032.064d.mgd.msft.net (141.251.50.216) by DB4PR30MB030.064d.mgd.msft.net (141.251.50.210) with Microsoft SMTP Server (TLS) id 15.1.112.16; Fri, 22 May 2015 17:52:29 +0000
Received: from DB4PR30MB032.064d.mgd.msft.net ([141.251.50.216]) by DB4PR30MB032.064d.mgd.msft.net ([141.251.50.216]) with mapi id 15.01.0112.000; Fri, 22 May 2015 17:52:29 +0000
From: Santiago Zanella-Beguelin <santiago@microsoft.com>
To: Peter Gutmann <pgut001@cs.auckland.ac.nz>, "<tls@ietf.org>" <tls@ietf.org>
Thread-Topic: [TLS] Another IRINA bug in TLS
Thread-Index: AdCUn0KvDdHZ+lmQNUW54l67jurcrQAGEh4F
Date: Fri, 22 May 2015 17:52:29 +0000
Message-ID: <1432317148442.5357@microsoft.com>
References: <9A043F3CF02CD34C8E74AC1594475C73AB029727@uxcn10-tdc05.UoA.auckland.ac.nz>
In-Reply-To: <9A043F3CF02CD34C8E74AC1594475C73AB029727@uxcn10-tdc05.UoA.auckland.ac.nz>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [109.216.4.228]
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-EOPAttributedMessage: 0
X-Microsoft-Exchange-Diagnostics: 1; BN1AFFO11FD045; 1:ApJaUoG98TN0ZjBNcBm1q6WLQGwQT/+aKGjH60els6+veFcKevxiQT3mxGEmUEmR90dvTRgKjRjpLATq37XYj+YOYRdF/1KmeXljjKsT/KloiSWvSjGf60gx3FJ5kHGnj56klp+DnudNFIOJAoHaoFUGI0aen3Pn4mmR2akT3+y8OVnm/gpmAXf5EjSfmi8dgaR63qPO0Scmvx6cJTPy7sFXeLL35ul7YUlnlSJEFSGMiAG4tJZYr1P7sZM+dFOXs59+SQ1la0WqcL4X5sufYg==
X-Forefront-Antispam-Report: CIP:206.191.250.196; CTRY:US; IPV:NLI; EFV:NLI; SFV:NSPM; SFS:(10019020)(6009001)(438002)(377454003)(189002)(199003)(51704005)(107886002)(5001830100001)(5001960100002)(117636001)(62966003)(69596002)(5001770100001)(5001860100001)(189998001)(19580395003)(36756003)(16796002)(2900100001)(19580405001)(86362001)(50466002)(64706001)(23756003)(54356999)(76176999)(86146001)(2656002)(86612001)(6806004)(66066001)(87936001)(92566002)(97736004)(2950100001)(81156007)(15975445007)(77156002)(4001540100001)(47776003)(106466001)(50986999)(46102003)(68736005)(102836002)(491001); DIR:OUT; SFP:1102; SCL:1; SRVR:BL2PR03MB289; H:064-smtp-out.microsoft.com; FPR:; SPF:Pass; PTR:ErrorRetry; MX:1; A:1; LANG:en;
X-Microsoft-Exchange-Diagnostics: 1; BL2PR03MB289; 2:2WWgm8iGwXcP7OzxMK5bTGeb4ZVhlkuQfHQ2FwXmr7TENWdfTKU4UIaYPIpuuuTz; 2:h9LUFi4n+i7rHPs9w65Fs1lA2OpmZRJlc5vnlqZptxBBccgdrPrhTF3DOYAnEpIoX7cHTryOWL2cZ3Wb2XXigPVgt5P67MjvBa39QfA/SPim8cgUKCxZ3I0H7xxZzQejoIZsD11zytBJ3WoKR5+O//ey9jhulefQ3fQy0v0x/2GtushS0uEPtNlmrBPGGlgR76yIeK1GpdS2Yj17Z8YfZI/ZL/4slufLsQCVJ3fvUNUpS7jq1ToHR0z2kD5EHNS9; 6:ZIWy4Xnx+nY8HxsLFz+I+fbhIdpyKr0b8nQfsEeTaAux6Rkklpr5K3S65QMi2BvlbMqJIPiLjJqdiXNutGqXNc/JNwbphdoAuM59csjxf10CZlrcUuNZ6Wo40ton6St6Rk3k3spYH2+HwER6y0RGN+uUuzLWyisyM+ZWJlBm8q2vtRteqoDm934GOdh2WmtkUHvOAZV9PPTNLo6UDqEVJuH07JqED0xPDrNmkTgZXVbEkAxVTVcmsS7RoF92qHi+KsNbbZTLGAgZmu/0LcloG+YlXgYQ5FQTzEtcSGzZ+M893qT7uOwGJWjesK9ry4h6Y4vaw+1TXZxU033534Zw+/2EdnPm0h5q+5EmBm3xRibtdelfrhiMKraXT5QmwL2uRL1jSEx06XZO5TBYJjRt4AGDXaQXYe3MxzUquHR3lD5eyIUuyb755IMzVlSg/49NN9nWu+cpzI+6rII/ofRaY4v5FEuogkJi5fREyFypSQlGSxm08Qof5JTWWTQWhfRu
X-Microsoft-Antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BL2PR03MB289;
X-Microsoft-Antispam-PRVS: <BL2PR03MB2891DDBD8E8DD83D530F4C0C9C00@BL2PR03MB289.namprd03.prod.outlook.com>
X-Exchange-Antispam-Report-Test: UriScan:;
X-Exchange-Antispam-Report-CFA-Test: BCL:0; PCL:0; RULEID:(601004)(2401001)(520002)(5005006)(3002001); SRVR:BL2PR03MB289; BCL:0; PCL:0; RULEID:; SRVR:BL2PR03MB289;
X-Microsoft-Exchange-Diagnostics: 1; BL2PR03MB289; 3:97S/PNauGmtxuK5GF9fK/1hDA4KbHWxoSSP9ZPHWTyBEAZgxko6B6ZtvJcWhlN9T6SyKbrl+Ld1fl3P4EoNQq8Y6TZXcIoyHC+LqmvuzamCB7xCIgVyAU70MDU8WvQMiynufu2AzLeX+Lc2+DsIZLgTH/pi4Hh5Sh1TGqlJ86wyZLnKZcJ8/Rs8CKqhiJdGlMDYuV7yYdSc8NZL3tl6fbKd5hNqRwmEO0rkA/ToB6mgxYQ6HpBg8/jm1sD440O/q/UdBROxbdE+y2v1K2cUqVLMkfIcs7CA0eadVd/xgz9TzN/p1Ixot1+mjdxCq77E9SBD/HOjPd3TllTVT/BoyYA==
X-Forefront-PRVS: 058441C12A
X-Microsoft-Exchange-Diagnostics: 1; BL2PR03MB289; 9:WIRlegqhlRfyBdXEE2UgeQwc4PSZV9sUd4napgZlfvLFJwdn5eUllyeKO1zPcbbk8qariK23tLT6HCYysY/V+SoqAmLmwVd+5KEybUb6Inc+tkvWtmxZXD7N9KiW/LmRQhNdZNxXwizJJsaXGsYd4p041gyCbkr5i3rSqfhyPtob4NFiaOKiVNZu7iprhhN4zetXFHTQO8ZvL8/gRUdhr+uEPFF3VCVg1Ph9F7ubjhERDW5jkt+f8BFh05Jt3eTPGpX94mdqL1jBGvawW+QWOY6n+ZF6OaTxQi8+JpWBTyJVbPZg1CpY0crt5A1NPHVakvj2F1YEI4vLv3AHWWJ8iJ2Dpxuba1k+KgN9/M3GZe8Ubp5eR+4R0BwIMJ99nfv91FEBtmVw9chb4/X+rlvLJAwtx48e3IS/hrDemupFBPTOiGd5NO2U5D3a1hGjifaaYaIkjnhyszGlkgZ31myWby3USUD93tqLDm4D8YgF7XX+kpY8sr7FhXTCrKHfDTwIWkKHQrMxzZzf2RCf0Jdzejaiqc5hUOSXAPnO/sUrirnfm9JUOJVrGrWJhNaMERrZV5MQeEcb3IX3zq+l/xDofwfXQkFY5B+WDT5eJfTwnn1f45i25aAOJ56rJ/+W/QPanhxKSs2rhhmXUG3+CaOSwXBEt/b5K0OSericG08h4sfUZVQ7JxjnlkFQU88rP9A2xXAPaDiyy4BzIc5hyaOOc13aRhnK0Tf2QqG7jKH5Z/znVKYLF1tBJ9ZC5r8Zvpg7WpDrZ//X7z8L/J/taEmwnadLgDNmnBEdeNr+NmpOMgUTA7kBfNW269ptQEe+JMfP9f49XIfCYTGVSqXeiYV4dhbN/4egtTbJB/g1KA0J4/8PuCNgPahE5TAj7WZ0jSC5o/TxvhVunxtjRQXkNq9WDbThvsd2CJrgyMEXy+oM4OodbbY2pfzRBfED93RXRL+1op18Yn1CxslpHzfhDCmtZFwdWmlkh88NUQilOcTxO2H/4UYa6LfA7UNwRK0LDc5IAamFET7m4gDSysI63eK8y69XUgZFn0wKF6FVvER2m8CVku3VoBUkXyjxzSMPMK4b7PHkwe7rAeGLioMCugEgXPiSyYy7LBJfoW76XLO7byHnjTmmjGeACfDC134mQmIX/jlaEHSe2nrkVm1uqzovwDTX/XOmEkKXolZpY41f/4iUHoYABq2C4hRn4UJP2eDO
X-Microsoft-Exchange-Diagnostics: 1; BL2PR03MB289; 3:tAuoUNE09VC+pP//VKbUWyjVeYNxZ0RXBqtwf57U5yH5v4nDbepwfwIT2QdAGmm+oFtwviB5MsGeNkzvmfNGTsk04beTV8uOX7BafhIwIlbCLiW0R1wUefHJq5DYUPhqoaB2rFhUjnDAeZVPMfLFNw==; 10:u2If6VOy561Lfv1HPQWA9ITMlcZV0UGCP07aj7ZZEeuB8VZShjwLZ78TyDwQHA4Y3Y86St4/puqMasfi086quzzE1M0ATvy+MSiYlWYaf8U=; 6:QmsODSYFPTn35N8tcJrn1ZaK2dHv/LUz4LnFaru/IMkI7sU2vVRGPKVQaB83WalI
X-OriginatorOrg: microsoft.com
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 22 May 2015 17:52:31.0118 (UTC)
X-MS-Exchange-CrossTenant-Id: 72f988bf-86f1-41af-91ab-2d7cd011db47
X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=72f988bf-86f1-41af-91ab-2d7cd011db47; Ip=[206.191.250.196]; Helo=[064-smtp-out.microsoft.com]
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL2PR03MB289
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/H5_wezFhj6RFp1HnI1k3za_78RA>
Subject: Re: [TLS] Another IRINA 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 17:52:55 -0000

>>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.

> What testing do you do on unsafe primes?

We accept them if they're in the pre-populated cache. If not, we reject them
because we can't check the order of the generator and validate ephemeral keys.
Unsafe primes have other problems too, e.g. NFS pre-computation is a bit easier
than for safe primes.

--Santiago

________________________________________
From: TLS <tls-bounces@ietf.org> on behalf of Peter Gutmann <pgut001@cs.auckland.ac.nz>
Sent: Friday, May 22, 2015 3:54 PM
To: <tls@ietf.org>
Subject: Re: [TLS] Another IRINA bug in TLS

Santiago Zanella-Beguelin <santiago@microsoft.com> writes:

>Regarding validation of DHE parameters and how reasonable it is in practice,
>I wanted to make some publicity for miTLS (http://www.mitls.org/).
>
>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?
Doesn't that make it awfully slow?

>If the modulus is prime but not safe, miTLS checks if it is in the table of
>trusted parameters and otherwise rejects it. We distribute miTLS with a pre-
>populated table of parameters which we tested thoroughly (and we welcome
>people to test further). Most of the time we hit an entry in the table.

What testing do you do on unsafe primes?

Peter.

_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls