Re: [openpgp] Ed25519 and digest choices (issue 31)

Daniel Kahn Gillmor <dkg@fifthhorseman.net> Mon, 24 May 2021 16:00 UTC

Return-Path: <dkg@fifthhorseman.net>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B1E513A2D7D for <openpgp@ietfa.amsl.com>; Mon, 24 May 2021 09:00:29 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.306
X-Spam-Level:
X-Spam-Status: No, score=-1.306 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=neutral reason="invalid (unsupported algorithm ed25519-sha256)" header.d=fifthhorseman.net header.b=SNr2UIxB; dkim=pass (2048-bit key) header.d=fifthhorseman.net header.b=By5FVmrr
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 cq0FwRTg6fMd for <openpgp@ietfa.amsl.com>; Mon, 24 May 2021 09:00:24 -0700 (PDT)
Received: from che.mayfirst.org (unknown [162.247.75.117]) (using TLSv1.2 with cipher ADH-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BCDC53A2D78 for <openpgp@ietf.org>; Mon, 24 May 2021 09:00:24 -0700 (PDT)
DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/simple; d=fifthhorseman.net; i=@fifthhorseman.net; q=dns/txt; s=2019; t=1621872021; h=from : to : subject : in-reply-to : references : date : message-id : mime-version : content-type : from; bh=1du2B2LWWhRYdoI4GXB8QUx4iz5NIskiXiJfd0aZOEY=; b=SNr2UIxBRbDnsRKgqJNJSWmuAVGpvr7OlQFqrJ3adPtKRckhjpz0j/8x+u0st0XpwWGY+ KLpC3zii0jBLWTYBg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=fifthhorseman.net; i=@fifthhorseman.net; q=dns/txt; s=2019rsa; t=1621872021; h=from : to : subject : in-reply-to : references : date : message-id : mime-version : content-type : from; bh=1du2B2LWWhRYdoI4GXB8QUx4iz5NIskiXiJfd0aZOEY=; b=By5FVmrrJDR3EZFdaKzQJBRTJXSgaglRCA+EaCnn4XT4MyqBIeIUxMIZ+tyb2kUGFBQYu yKFRaDnOa4Taad61sOyrlnbd/KAdo0v9WA2IFPYxrpZ6uLOmKh5fyyjTgJxwYZzo0QieKMl vwl4AtGqAtPqcrVS7Pfm4hNLEbLhztiABBDtGWR5CXj39pkncBc4E/ghb8U2/DWSRk/tKZw UCYWT2UY7ZpmxyVFsAxJUDeXtPB2OFGe0S/504XKE3QxY5mmKpG+K8VliBjAaX6JywKdIMR oMldvBT/nW5yH+fpSG2iJ1QSAXQkA2uunSDkCsaIOD07wnmQ2v5qyILZ938g==
Received: from fifthhorseman.net (lair.fifthhorseman.net [108.58.6.98]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by che.mayfirst.org (Postfix) with ESMTPSA id 344F4F9A7; Mon, 24 May 2021 12:00:20 -0400 (EDT)
Received: by fifthhorseman.net (Postfix, from userid 1000) id 7CC1121D0C; Mon, 24 May 2021 11:58:42 -0400 (EDT)
From: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
To: "brian m. carlson" <sandals@crustytoothpaste.net>, openpgp@ietf.org
In-Reply-To: <YKgVesA8U+EKgboS@camp.crustytoothpaste.net>
References: <878s48dlkn.fsf@fifthhorseman.net> <YKgVesA8U+EKgboS@camp.crustytoothpaste.net>
Autocrypt: addr=dkg@fifthhorseman.net; prefer-encrypt=mutual; keydata= mDMEX+i03xYJKwYBBAHaRw8BAQdACA4xvL/xI5dHedcnkfViyq84doe8zFRid9jW7CC9XBiI0QQf FgoAgwWCX+i03wWJBZ+mAAMLCQcJEOCS6zpcoQ26RxQAAAAAAB4AIHNhbHRAbm90YXRpb25zLnNl cXVvaWEtcGdwLm9yZ/tr8E9NA10HvcAVlSxnox6z62KXCInWjZaiBIlgX6O5AxUKCAKbAQIeARYh BMKfigwB81402BaqXOCS6zpcoQ26AADZHQD/Zx9nc3N2kj13AUsKMr/7zekBtgfSIGB3hRCU74Su G44A/34Yp6IAkndewLxb1WdRSokycnaCVyrk0nb4imeAYyoPtBc8ZGtnQGZpZnRoaG9yc2VtYW4u bmV0PojRBBMWCgCDBYJf6LTfBYkFn6YAAwsJBwkQ4JLrOlyhDbpHFAAAAAAAHgAgc2FsdEBub3Rh dGlvbnMuc2VxdW9pYS1wZ3Aub3JnL0Gwxvypz2tu1IPG+yu1zPjkiZwpscsitwrVvzN3bbADFQoI ApsBAh4BFiEEwp+KDAHzXjTYFqpc4JLrOlyhDboAAPkXAP0Z29z7jW+YzLzPTQML4EQLMbkHOfU4 +s+ki81Czt0WqgD/SJ8RyrqDCtEP8+E4ZSR01ysKqh+MUAsTaJlzZjehiQ24MwRf6LTfFgkrBgEE AdpHDwEBB0DkKHOW2kmqfAK461+acQ49gc2Z6VoXMChRqobGP0ubb4kBiAQYFgoBOgWCX+i03wWJ BZ+mAAkQ4JLrOlyhDbpHFAAAAAAAHgAgc2FsdEBub3RhdGlvbnMuc2VxdW9pYS1wZ3Aub3Jnfvo+ nHoxDwaLaJD8XZuXiaqBNZtIGXIypF1udBBRoc0CmwICHgG+oAQZFgoAbwWCX+i03wkQPp1xc3He VlxHFAAAAAAAHgAgc2FsdEBub3RhdGlvbnMuc2VxdW9pYS1wZ3Aub3JnaheiqE7Pfi3Atb3GGTw+ jFcBGOaobgzEJrhEuFpXREEWIQQttUkcnfDcj0MoY88+nXFzcd5WXAAAvrsBAIJ5sBg8Udocv25N stN/zWOiYpnjjvOjVMLH4fV3pWE1AP9T6hzHz7hRnAA8d01vqoxOlQ3O6cb/kFYAjqx3oMXSBhYh BMKfigwB81402BaqXOCS6zpcoQ26AADX7gD/b83VObe14xrNP8xcltRrBZF5OE1rQSPkMNy+eWpk eCwA/1hxiS8ZxL5/elNjXiWuHXEvUGnRoVj745Vl48sZPVYMuDgEX+i03xIKKwYBBAGXVQEFAQEH QIGex1WZbH6xhUBve5mblScGYU+Y8QJOomXH+rr5tMsMAwEICYjJBBgWCgB7BYJf6LTfBYkFn6YA CRDgkus6XKENukcUAAAAAAAeACBzYWx0QG5vdGF0aW9ucy5zZXF1b2lhLXBncC5vcmcEAx9vTD3b J0SXkhvcRcCr6uIDJwic3KFKxkH1m4QW0QKbDAIeARYhBMKfigwB81402BaqXOCS6zpcoQ26AAAX mwD8CWmukxwskU82RZLMk5fm1wCgMB5z8dA50KLw3rgsCykBAKg1w/Y7XpBS3SlXEegIg1K1e6dR fRxL7Z37WZXoH8AH
Date: Mon, 24 May 2021 11:58:41 -0400
Message-ID: <87r1hwcedq.fsf@fifthhorseman.net>
MIME-Version: 1.0
Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha256; protocol="application/pgp-signature"
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/P0NYp2OjKDsv5ReCJvn-XEm5vtE>
Subject: Re: [openpgp] Ed25519 and digest choices (issue 31)
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 24 May 2021 16:00:30 -0000

On Fri 2021-05-21 20:18:02 +0000, brian m. carlson wrote:
> On 2021-05-21 at 17:48:56, Daniel Kahn Gillmor wrote:
>> Alternately, maybe we should instead reframe OpenPGP's use of Ed25519 as
>> a "PureEdDSA" scheme that signs only the OpenPGP digest (not the signed
>> data directly).  That bypasses the "PH" parameter, but it also means
>> that any cryptanalsis that is applied to EdDSA isn't necessarily
>> applicable to OpenPGP, because we have this additional step involved.
>
> I would prefer this approach.  OpenPGP has traditionally allowed users
> to use whatever digest they like with keys, even when the standards have
> traditionally fixed a digest.  For example, DSA generally has specified
> that either SHA-1 or SHA-2 has to be used and it has to be used with the
> proper size q, but we've allowed RIPEMD-160 and SHA-256 with smaller q.
>
> If, for example, we discover a weakness in SHA-512, it should be fine
> to switch to SHA3-512 for signatures without problems.

well, it's true that we could swap out PH(x) (the prehash function) but
if i'm understanding EdDSA correctly, we could *not* swap out H(x) (the
hash function), which is SHA-512(dom2(phflag,context)||x) for any
variant of Ed25519.

see https://datatracker.ietf.org/doc/html/rfc8032#section-5.1 for more
details about the EdDSA parameter choices for the three different
flavors of Ed25519.

If i'm understanding how OpenPGP uses Curve25519 for signatures
correctly, I don't think that the OpenPGP choice of digest has any
effect on H(x).  If it does, it's hard to say that we'll have dodged a
SHA-512 weakness entirely.

> I will admit that using multiple digests may require additional work for
> cryptanalysis, but I suspect that if PureEdDSA is secure with arbitrary
> messages and the hash function is collision resistant (both of which we
> would reasonably expect), then this approach will likely be secure.  I
> provide no proof of my conjecture, though.

I have the same intuition as you, and the same lack of rigorous proof :P

  --dkg