[openpgp] Disadvantages of Salted Signatures

Stephan Verbücheln <verbuecheln@posteo.de> Sat, 09 December 2023 09:04 UTC

Return-Path: <verbuecheln@posteo.de>
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 84D87C09C237 for <openpgp@ietfa.amsl.com>; Sat, 9 Dec 2023 01:04:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.104
X-Spam-Level:
X-Spam-Status: No, score=-2.104 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, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=posteo.de
Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id svuebuy1G-rR for <openpgp@ietfa.amsl.com>; Sat, 9 Dec 2023 01:04:19 -0800 (PST)
Received: from mout02.posteo.de (mout02.posteo.de [185.67.36.66]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 995BBC0DC7E2 for <openpgp@ietf.org>; Sat, 9 Dec 2023 01:04:18 -0800 (PST)
Received: from submission (posteo.de [185.67.36.169]) by mout02.posteo.de (Postfix) with ESMTPS id 26DE7240101 for <openpgp@ietf.org>; Sat, 9 Dec 2023 10:04:16 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=posteo.de; s=2017; t=1702112656; bh=Mc8w6+Qy8NdV2SsDXmARmGviqcQ6WWJRV7hj+jqVUNQ=; h=Message-ID:Subject:From:To:Date:MIME-Version:From; b=FHP6GIWi2F93ztfWrKNVdqge7ZKivFnLR7wStFjJUMfjEqjlKrCrZ5+jeN47Ch5ai skfaci/N0iw2WvszUIh/SyCPMsHUWNQdhiUKmIr03Ahl2r92vwCwmbciNXTHnTk9ri 8l1cxEby+/mEsDo1Z46ZLsWnyDb8l+Bt++XahGAoyMDWMbilRQ6E4EWFesjwnj/bkw ZcG4uEp4weG7tUCa+b95BnJxjykfeTmYtW/XhMaKeOAPru7IJuqdKNw0wc5gfn+uX3 arj7BV1BSbCp9VETPNIP2JxIcSTFPwVI9de7NCvOVELiCjt5KflyGKxp1f6y0PrMbF cGZpsJZUU15vw==
Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4SnMWg4XZrz9rxH for <openpgp@ietf.org>; Sat, 9 Dec 2023 10:04:15 +0100 (CET)
Message-ID: <077dd27cef0c7d3968967fc4c3a880081b8bd9dd.camel@posteo.de>
From: Stephan Verbücheln <verbuecheln@posteo.de>
To: openpgp@ietf.org
Date: Sat, 09 Dec 2023 09:04:14 +0000
Content-Type: multipart/signed; micalg="pgp-sha256"; protocol="application/pgp-signature"; boundary="=-bGGwqjENIwqrzWeTQjV2"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/uGHlHjeqo7VEZ55JO_7IcV-Q1Nk>
Subject: [openpgp] Disadvantages of Salted Signatures
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.39
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: Sat, 09 Dec 2023 09:05:16 -0000

Alternative title: Advantages of Deterministic Signatures

Hello everyone

Deterministic signatures have their own value. Especially with the
increasing popularity of ECC algorithms, because these are in
particular vulnerable to kleptographic attacks.

What is a kleptographic attack? The term kleptographic attack was
coined by Adam Young and Moti Yung more than 25 years ago for discrete-
logarithm-based signature schemes.[1]

A kleptographic attack can be summarized as follows:
1. A malicious blackbox implementation (e.g. PGP smartcard) can choose
the nonce in a way that allows the attacker to compute the secret key
from two signatures.
2. This is not news. Everyone here probably knows about nonce reuse and
related problems. However, the attacker can generate these two nonces
in a way that is provably impossible to detect (i.e., without breaking
the security of a cryptographically secure pseudorandom number
generator).
3. The attacker uses his own secret key which is required to detect
malicious nonces and compute the victim's secret key.
4. The core requirement for this attack is that the attacker beforehand
knows the Diffie-Hellman (DH) group parameters which are used for the
key and signatures. While with classic DSA, each PGP key basically has
its own DH group, elliptic-curve-based keys select one of a few
predefined curves. This makes the attack even more feasible.

Some years ago, I wrote down how the attack works on Bitcoin
transactions, which are basically ECDSA-signed messages.[2] The same
can be applied to signed PGP messages.

Deterministic signatures can be helpful to detect this kind of attacks.
For instance, if a PGP key is imported into multiple smartcards, then
they should give the same result when signing the same data.
In fact, the current version of GnuPG is doing exactly that when using
EdDSA (with the same timestamp).


In section 13.2. (Advantages of Salted Signatures) of the draft 
draft-ietf-openpgp-crypto-refresh-12, there are two motivations
mentioned for salted signatures.
The first is resistance to hash collision attacks with reference to
"SHA-1 Is A Shambles". This analysis seems to be plain wrong. I do not
see how the salt would make collision attacks any harder, let alone
raise the cost to second-preimage levels.
But even if they would, this is only relevant for almost broken hash
algorithms which should be avoided in the first place. SHA-1 was
reaching its end of life because 80 bits of attack complexity were not
unfeasible any more. The algorithm's additional weaknesses discovered
by some smart cryptographers made it crack a few years earlier, but it
would have been cracked soon anyway.
The second motivation is resilience to fault attacks. Here, the salt
looks to me like an effective countermeasure. However, this attack
appears to be quite exotic and requires the attacker to have some
access to the victim's vulnerable machine (e.g., shared cloud
hardware).
It further requires the victim to sign the same data over and over
again, which is not realistic in a practical scenario on the PGP layer
because the timestamp will be different for each signature. There is no
point in signing the same data with the same timestamp over and over
again because it will always have the same result. In the far-fetched
use case where the PGP user wants to sign over and over again with the
same timestamp but different results, he is free to add a salt to his
data.


As a conclusion, I would rather recommend against salted signatures.

Best regards
Stephan


[1]
https://www.researchgate.net/publication/221354983_The_Prevalence_of_Kleptographic_Attacks_on_Discrete-Log_Based_Cryptosystems

[2] https://arxiv.org/abs/1501.00447