Re: [Cfrg] Security proofs v DH backdoors

"Paterson, Kenny" <> Wed, 02 November 2016 12:05 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id EF1ED12952C for <>; Wed, 2 Nov 2016 05:05:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 7UM64Qh7i19m for <>; Wed, 2 Nov 2016 05:05:16 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 9FF8F1295CB for <>; Wed, 2 Nov 2016 05:05:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=selector1-rhul-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=wcIPABQBmdX0waRz53jJA6+JRvrz6rYdcVUKrfy0gkU=; b=uq580AoapnCYOVZfT22ZMGxzNU3dq88WRYSZPODZVoTbvnJiKHT9RL8sYPaOGhOnGWVCHND5Sc27FRr27BYdry6EeHsVRvdrsph2T6JKLDKi78G0g2EXX40HWrLMNpJHK0YQ9sOELaO5/uJveNTDamMN8vaaFDS2vElcmSyOpjM=
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.693.12; Wed, 2 Nov 2016 12:05:12 +0000
Received: from ([]) by ([]) with mapi id 15.01.0693.009; Wed, 2 Nov 2016 12:05:12 +0000
From: "Paterson, Kenny" <>
To: Ilari Liusvaara <>, Dan Brown <>
Thread-Topic: [Cfrg] Security proofs v DH backdoors
Date: Wed, 02 Nov 2016 12:05:12 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-GB, en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
authentication-results: spf=none (sender IP is );
x-ms-exchange-messagesentrepresentingtype: 1
x-originating-ip: []
x-ms-office365-filtering-correlation-id: 62dda965-3fbf-4e73-33e3-08d403187fc2
x-microsoft-exchange-diagnostics: 1; HE1PR0302MB2745; 7:Xi4Lh/HRUYafUKhdw0GjwPB5Nkx7w9nqIvXFfetHkrIV7UIkw0xVxOlSOcS0etuj1llk5VT/fn/opMTibbfjOhRFBan/SkFawJwFSFKlgQGcjTd7iBbCV4Qs/yUA407U9udQDekaAewwN5c8JP7c6h0HTuEp/SmzlJWZ6T0QD1VP1mfZV7/RhVhy72yBorQ9e1kR7AiVu+QwdXsZNnws5VFkdZxiZsksFhJ4GGSehMr+m0lOu7IXYJ0q7lDQ2dXGw31BHhlKsp0kgbOrCiwrn+znfKtTTJhabj/Qk3SOIC0rSgK0hfDv2q8ZnbLW/Qy2y3ABJ8X6h+I1Pb6r9ngEU3bsTGbQ3e9A2Un4zohAtME=
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:HE1PR0302MB2745;
x-microsoft-antispam-prvs: <>
x-exchange-antispam-report-test: UriScan:(158342451672863)(192374486261705);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6040176)(601004)(2401047)(8121501046)(5005006)(10201501046)(3002001); SRVR:HE1PR0302MB2745; BCL:0; PCL:0; RULEID:; SRVR:HE1PR0302MB2745;
x-forefront-prvs: 0114FF88F6
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(7916002)(189002)(199003)(24454002)(97736004)(92566002)(4326007)(2900100001)(8936002)(77096005)(105586002)(54356999)(50986999)(106356001)(15650500001)(76176999)(11100500001)(81156014)(2906002)(15975445007)(8676002)(81166006)(101416001)(68736007)(6116002)(102836003)(3846002)(19580395003)(586003)(10400500002)(7846002)(305945005)(3660700001)(19580405001)(83506001)(3280700002)(5660300001)(7736002)(5001770100001)(5002640100001)(4001350100001)(42882006)(189998001)(86362001)(36756003)(122556002)(87936001)(66066001)(2950100002)(74482002); DIR:OUT; SFP:1101; SCL:1; SRVR:HE1PR0302MB2745;; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
received-spf: None ( does not designate permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 02 Nov 2016 12:05:12.1903 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR0302MB2745
Archived-At: <>
Cc: CFRG <>
Subject: Re: [Cfrg] Security proofs v DH backdoors
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 02 Nov 2016 12:05:18 -0000

Hi Dan,

Bringing this thread back to where it started...

On 25/10/2016 14:30, "Cfrg on behalf of Ilari Liusvaara"
< on behalf of> wrote:

>On Tue, Oct 25, 2016 at 01:10:16PM +0000, Dan Brown wrote:
>> How do the 3 recent IACR eprints on FFDH backdoors‎ reconcile with
>> past security proofs for TLS, SSH, etc?
>> Some guesses: (1) the attacks are outside the security definitions
>> (=> attacks not so important?), (2) the proofs assume strong FFDH
>> groups plus validation, etc.
>I guess the proofs assume strong FFDH groups, such that dlog and
>dh attacks are infeasible.

I can confirm that this is the correct explanation, at least for TLS.

For example, the security proof* for static DH ciphersuites in [1, Section
7] assumes that a certain CDH-like assumption holds (specifically, the
PRF-ODH assumption, which concerns the combination of the KDF used in TLS
and the DH problem).

This assumption is stronger than the assumption that the DLP is hard in
the specific group in which the protocol is run.

The proof in [1] also assumes group membership tests are carried out
(which, as has been discussed on this thread, is a problem for TLS, where
the server cannot tell the client anything about the group, not even its
claimed order). 

In the group instances under discussion, PRF-PDH is not hard for an
adversary who has the trapdoor/backdoor information.



*Other proofs for this and other modes are available in the literature.

[1] Hugo Krawczyk, Kenneth G. Paterson, Hoeteck Wee: On the Security of
the TLS Protocol: A Systematic Analysis. CRYPTO (1) 2013: 429-448

>I think there was one TLS implementation that tries to verify the
>groups sent (of course, not all can be verified, even if those
>aren't maliscously constructed).
>And the backdoors in one of the papers was about constructing
>prime such that one can use faster special case for dlogs. That
>can't be easily discovered, even if one somehow can obtain the
>group order. So one can't validate against it.
>Cfrg mailing list