[Cfrg] What groups to use for Diffie Hellman?

Phillip Hallam-Baker <phill@hallambaker.com> Thu, 27 October 2016 14:47 UTC

Return-Path: <hallam@gmail.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 9AA40129622 for <cfrg@ietfa.amsl.com>; Thu, 27 Oct 2016 07:47:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.597
X-Spam-Level:
X-Spam-Status: No, score=-2.597 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 g0L-dgqlpa3z for <cfrg@ietfa.amsl.com>; Thu, 27 Oct 2016 07:47:35 -0700 (PDT)
Received: from mail-wm0-x241.google.com (mail-wm0-x241.google.com [IPv6:2a00:1450:400c:c09::241]) (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 1480B12964B for <cfrg@irtf.org>; Thu, 27 Oct 2016 07:47:24 -0700 (PDT)
Received: by mail-wm0-x241.google.com with SMTP id y138so3069476wme.1 for <cfrg@irtf.org>; Thu, 27 Oct 2016 07:47:24 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:from:date:message-id:subject:to; bh=f1a5CXHF0fJOTX2eJSlK+OA6MxIBQjKV2My8OYCCwRE=; b=cAxSG5gBZiNa7YX4RiSmVQXiYbnrRxVlpR9pOkQZOHIRmZu2mOH5NNAOVv4ssiKogy klHTY52y7Pw67KXkLkAUfhfedHy96J04JZLqayYE6VBGxTlZMnGzdKcjSAqkFuaoBTRX bt9Ja0hYFhxwkIMpyULy53rr+woFrklv4fmZAnk845gklPgHV8ebADLTzOoQYZWS0rO/ nLlopvbCne2xp+YdAr1Z6mVU8iTi+M0qlXj3zDIC9bFI3ZMmUqN2fX29jNI8fWOfIpUm oC7qvIUatkysW3HS3lJVXu23OV+1FGMOgDT9HAg51dh+e6pFLHx2nVGN+uRmlegPP70Q Hf+Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:sender:from:date:message-id:subject :to; bh=f1a5CXHF0fJOTX2eJSlK+OA6MxIBQjKV2My8OYCCwRE=; b=aSLTjC2MJTKo7Vr/DiZqyRK3c6H8yufddGZzPePeQyIms3lAaoqWXwD7AJrGlf3WQN +Ud9QYuwf/vB0wCI5VOknsHVqlw2ZqpZ/OVpzuJAJHAMWVigNjotadA7oEoBEEIZdjH0 mOaqMto8CN7oNczpj60qqw5BDLLvmTKw/kqWdSBttlSvkVG2sRTA1/+UBajl1bw2UiAN 8NuhJDWwc5uyUtreQcoVW7B7KQpEGtrHyjFH7qyBwUPDEpTOZDdiomXYFQ0m/0Wmn/vu covC0nSO2uZlqGfwC1zVBz6qGLjVj0Nr9LnJojGW6wTQb5eGm4PVfvTJI1FmxK/nan4T lgaw==
X-Gm-Message-State: ABUngvfsfUQ8fYnQRI/8QANLmcQI/CDWCu1RhQEhs54LdvPqAey6R21ig49GStYU3afdskQb1letF90KrTXqig==
X-Received: by 10.28.167.14 with SMTP id q14mr776013wme.21.1477579642381; Thu, 27 Oct 2016 07:47:22 -0700 (PDT)
MIME-Version: 1.0
Sender: hallam@gmail.com
Received: by 10.194.227.170 with HTTP; Thu, 27 Oct 2016 07:47:21 -0700 (PDT)
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Thu, 27 Oct 2016 10:47:21 -0400
X-Google-Sender-Auth: FYa9RlSfi9QEI1Ua3xQ6loOaIY8
Message-ID: <CAMm+LwjZX=xsq7xM8Tti6u4ecNKHjXW_rsEUSV=63so816uNWw@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=001a114b40acb62a5c053fd9d102
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/APMFTQUvZvkl9tLKR1UgAj6kFH8>
Subject: [Cfrg] What groups to use for Diffie Hellman?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
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: Thu, 27 Oct 2016 14:47:40 -0000

I am currently working on a set of APIs to support the use of proxy
recryption within a cryptography application. Recryption solves many
problems in designing end-to-end secure messaging applications.

The following draft shows where I am headed:
https://datatracker.ietf.org/doc/draft-hallambaker-mesh-recrypt/

Links to the code libraries and API documentation can be found here:
http://www.prismproof.org/code.html

The beginnings of the recryption API are to be found here:
http://www.prismproof.org/code/portable/html/1a1794fd-cbe8-6e8b-9868-64028331fad8.htm

[All the code is under MIT license]

The API does not change much for recryption. The first step is identical,
the only difference being that instead of putting the key agreement
BigInteger result through a hash function, you send it on to the recipient
who then calls an agreement method that takes it as an additional parameter.


For ease of debugging, I would prefer to have as few moving parts to debug
at one time. So even though the intention is to us ECDH with curves x25519
and x448 for production, I am developing using straight DH with the
parameters in RFC 5114. (DH might also turn out to be necessary in
deployment if quantum resistance becomes an issue though I suspect if
people can build a 64 QBit quantum computer they will have solved most of
the problems they need to solve to go to several thousand)

The reason I am using this is that I don't want to spend time debugging
Miller-Rabin primality tests and getting them to run fast enough to be
useful. And that is the only RFC with DH parameters I could find that
specifies p and q values.

While finding it, I also found a lot of people complaining that RFC5114 is
not rigidly constructed. And there are good reasons for concern.


While writing 5114 die die die might be a good idea. A precondition for
having people take notice is to propose a set of alternative shared
parameters that have been constructed in a form that is 'sufficiently
rigid'.

One thing that seems to be a source of confusion is what the boundary
between the public and the shared parameters is. And this is different in
different protocols and while there are vast volumes of opinion on the
subject, it is hard to get a reading.


DH has the following parameters:

The modulus prime - p
The sub group prime - q
The generator - g = h^{(p-1)/q} mod p
The private key - x
The public key - g^x mod p

>From my point of view as a protocol designer, the shared parameters are
anything that is common between all the users and the public key is
anything that isn't a shared parameter and isn't part of the private key.
So there are multiple choices for the boundary between public and shared:

1) Share nothing
2) Share p
3) Share p, q
4) Share p, q, g

There are two reasons to share a parameter

1) The parameter is expensive to generate.
2) The parameter might introduce a weakness if it isn't generated correctly.

There is one good reason not to

1) Using a shared parameter may allow an attacker to attack multiple
private keys in parallel.


Generating p and q is costly. I don't want to do that on a constrained
device. So the choice comes down to g. And here I have a few choices.

1) Use fixed h and thus g.
2) Include h in the public key parameters.
3) Include g in the public key parameters.

The reason to include h rather than g is that it ensures that the generator
has been correctly generated. The reason not to is that this takes extra
time and knowing h might reduce the work factor for an attacker.


Any ideas?