Re: [Cfrg] Is Diffie-Hellman Better Than We Think? (was: Ideal Diffie-Hellman Primes)

Christopher Patton <cpatton@cloudflare.com> Tue, 20 October 2020 17:49 UTC

Return-Path: <cpatton@cloudflare.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 31E0F3A1288 for <cfrg@ietfa.amsl.com>; Tue, 20 Oct 2020 10:49:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cloudflare.com
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 4jnVllad8EVz for <cfrg@ietfa.amsl.com>; Tue, 20 Oct 2020 10:49:15 -0700 (PDT)
Received: from mail-qk1-x72a.google.com (mail-qk1-x72a.google.com [IPv6:2607:f8b0:4864:20::72a]) (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 ADEF93A12AA for <cfrg@irtf.org>; Tue, 20 Oct 2020 10:49:14 -0700 (PDT)
Received: by mail-qk1-x72a.google.com with SMTP id 140so2339769qko.2 for <cfrg@irtf.org>; Tue, 20 Oct 2020 10:49:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cloudflare.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=5RCX/JSlly9WsX03znEoOYE2t2/gAsaWvurLdSILma0=; b=oqAq7eWiXXgRHtmBJQuNLYMscESstiS8LfJU2j+SmLCaMiqIJ+7Z9gCxoS20saKhol kewbnRf+RkxMzYogU1l6yP+lJZMkpXtJ93zH9bXXELvWvIeW6Zyt10VHRLu3CJwozL4G 0d+Az6EzXZ3jekTwc2IXOj0ZluYGZN7IVlWC8=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=5RCX/JSlly9WsX03znEoOYE2t2/gAsaWvurLdSILma0=; b=YuOyy9dMZxEy7UnEKOgyMtKTMIiH93bLTW5PGkfAV10UMn1fPs1yYH3vvFMjeIv8NG UuFtWOhJ8FC6uMh4krlstq2Nth3te8TzHz4DIDkLQRXtYbcAQfH8IfGxLCmI1Fu9p7Ra UMLjzseH4tVUlzWgDsJBdBg8QdvGrM1ODsCP1jcFHv70lKaoWZ/lPMNjU879diEuSWVE EZfYsmV1QSvQW0NGBqPi33eaBVC+a51E0PZUMSekglF3vWqxEQZRGlfY+4y91yvpgPrJ sIq5JB10HaNOh8TLVD3x0pFlHzuZChU/bWQbXc3OsyUGYHRhvyuixrfkhbTx4NqcQs3D VvhA==
X-Gm-Message-State: AOAM531P/o9OsZQh1JnvKkgVxEbw8GXeHW4q7d2RMU3Wu346SGeP3jKz mNziLI/fF70PmasSfO/CvBrjZF28fV/9w05yXT1L97dpXFCSAA==
X-Google-Smtp-Source: ABdhPJx+NGNkp2l9BqAgT26Q3L2VcYMLKHPM9/llr1w+BDfr14XNR6KyAXbCnrfJzaaucxQil8NprhRrko9xGiliMSU=
X-Received: by 2002:a37:b342:: with SMTP id c63mr2025595qkf.146.1603216153696; Tue, 20 Oct 2020 10:49:13 -0700 (PDT)
MIME-Version: 1.0
References: <07090aa6-1bd1-4a37-810d-6cd95a6f1e7c@www.fastmail.com> <ACF3D521-99D7-4A46-A3E6-2865FE53A816@gmail.com> <19672d78-77de-4744-b9d8-470a18dc3ac0@www.fastmail.com> <770E332F-B404-45C8-898B-BAD69A9B75A0@shiftleft.org> <cc5b03ef-01d0-44a3-9030-1faa99107425@www.fastmail.com> <3c63be30-5c09-42b0-a0a4-18190ef5d548@www.fastmail.com> <bc77f256-2fc6-48c1-9a7a-60ec6caaa55d@www.fastmail.com> <1ed370e4-8a09-4a41-bf15-22d8e61bef6e@www.fastmail.com>
In-Reply-To: <1ed370e4-8a09-4a41-bf15-22d8e61bef6e@www.fastmail.com>
From: Christopher Patton <cpatton@cloudflare.com>
Date: Tue, 20 Oct 2020 10:49:02 -0700
Message-ID: <CAG2Zi20O6rb6TgSMKLwHefFAsHHWC5-9fiPWFQ4Cm4ghBoAyQw@mail.gmail.com>
To: "Michael D'Errico" <mike-list@pobox.com>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000056f8a605b21dd911"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/xGJlJHtD453u2tjwHHHKZondvVc>
Subject: Re: [Cfrg] Is Diffie-Hellman Better Than We Think? (was: Ideal Diffie-Hellman Primes)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 20 Oct 2020 17:49:23 -0000

> My theory is that vanilla modular-exponentiation
> Diffie-Hellman is not as bad as currently thought [...]
>

Note that there's a number of issues with classical DH that are solved by
ECDH. For example, It's much easier to make secret key operations constant
time for ECDH:
https://tools.ietf.org/html/rfc7748#section-1

There are also some crazy attacks that impact classical DH when parameters
are used for a long time:
https://weakdh.org/


> Does anybody have access to a Number Field Sieve
> program who can do the following experiment?
>

It seems like there's lots of great open source implementations to play
with, if you'd like to try it yourself:
https://en.wikipedia.org/wiki/General_number_field_sieve#Implementations


Best,
Chris P.