Re: [openpgp] Disadvantages of Salted Signatures

Aron Wussler <aron@wussler.it> Mon, 11 December 2023 09:51 UTC

Return-Path: <aron@wussler.it>
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 5B877C14F5F7 for <openpgp@ietfa.amsl.com>; Mon, 11 Dec 2023 01:51:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.105
X-Spam-Level:
X-Spam-Status: No, score=-7.105 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_DNSWL_HI=-5, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=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=wussler.it
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 Xq8gNXO-L1Ub for <openpgp@ietfa.amsl.com>; Mon, 11 Dec 2023 01:51:40 -0800 (PST)
Received: from mail-4022.proton.ch (mail-4022.proton.ch [185.70.40.22]) (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 ECE96C14F5E2 for <openpgp@ietf.org>; Mon, 11 Dec 2023 01:51:38 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wussler.it; s=protonmail2; t=1702288296; x=1702547496; bh=+UYeOkOK80CNUxGQac9X9vQiZoHpus6piIAJHK2cNPg=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=nk/xo29EF/d9QcOWEVt1gO/vNRtFrJh9kDEWqczF6q/ELNXDK0za7gb0nNMzUyEMB Xxswws7DkizUHY5scfUyA6YOvlVDoV47+AB54RMKhRzW14/Kc9e0BZd4qua9LGNnkT ugcgqax7MfIus2Tfa6dJkWvharxZHRMx8kLTCuK3UdFQckf2PyqGNDhdkBG8VMivpv XkJkDDs1sirWEFjTuDPaGk7xlVVUklGl4CVSQnNSeP/T8hhOBF15mM4i4y/SRuDB8s tYGTn82iWlYCvXcBJCGO6us0V2p42/2ZyzHHGcy3zI9cGSxwCbVOuYvHZYp15T7Hqz dqX734OcuJfxA==
Date: Mon, 11 Dec 2023 09:51:31 +0000
To: Stephan Verbücheln <verbuecheln@posteo.de>, "Neal H. Walfield" <neal@walfield.org>
From: Aron Wussler <aron@wussler.it>
Cc: openpgp@ietf.org
Message-ID: <_6FpNimQPKbg-enGJw_JK8OK5wVX3ZnCx5unc7GxbDIGNRFmoM8hkCOpYrEp-dNy8GB4artek-tHKOwZApKZM8BidhI2meoECIkmGRVzcBs=@wussler.it>
In-Reply-To: <87jzplrtfy.wl-neal@walfield.org>
References: <077dd27cef0c7d3968967fc4c3a880081b8bd9dd.camel@posteo.de> <87jzplrtfy.wl-neal@walfield.org>
Feedback-ID: 10883271:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg="pgp-sha512"; boundary="------de574d886737bd054d28662fa54306249343a0dbc12c01c180f99aa548d42ac1"; charset="utf-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/HUJGDXtVDxwu0EElXejjZv8OMvs>
Subject: Re: [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: Mon, 11 Dec 2023 09:51:45 -0000

Hi Stephan,

I'll be tackling the following points of the thread:

> 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.

and

> At least 13.2 is so erroneous that it has potential to damage the
> reputation of the standard. The references do not support either of the
> claims. 


(Note: in this context we consider only non-faulty RNGs, if not the whole security model of OpenPGP collapses. We specify in 13.10: "OpenPGP requires a cryptographically secure pseudorandom number generator (CSPRNG).")

Given an honest signer, that picks an unpredictable salt, they will sign h = H(r || x) where x is the message.
In the existential unforgeability setting, an adversary can query the honest signer for any x' != x and obtain a signature.

Now, without the randomization parameter r, the adversary has to find H(x) = H(x') for any x' = x, and this is collision-resistance.
They can pre-compute what h will be, and submit the request to the oracle, that will produce a deterministic signature.

Having the randomization parameter, the adversary has to find H(r || x) = H(r || x') for chosen r (i.e. submit x to the oracle, then find x') and this requires breaking second-preimage resistance.
An adversary cannot leverage anymore the H(x) = H(x') relation, because every plaintext will be prefixed with a random salt. Any time the signature is re-submitted, we get a diffrent salt, and once r is fixed the adversary has then to search for the suitable x' given h. 


Note that the same stucture is also used to randomize SPHINCS+ (now SLH-DSA) [1] (Section 11):
> Moreover, a collision attack against the hash function does not suffice to break the security
> of SPHINCS+ . We consider this an important feature given the successful collision attacks
> on MD5 and SHA1. Especially given that even for MD5 second-preimage resistance has not
> been broken, yet.

This was specifically introduced to counter chosen prefix attacks (as Neal pointed out) but I think it can be extended to 2nd-preimage, and by fixing the length to the hashing algorithm we match the desired security level and initialize the hash in a fully unpredictable state when signing.

> One could also ask: Does such a deep dive into cryptography
> even belong there?

I think it's fair for the security considerations, rather than a deep dive it's more of a design justification. It does not contain any security game or security notion and still references some papers that take care of that.

Personally, I'd agree we could improve the references to this part with the 2nd-preimage resistance, but I don't think the point is moot.

Cheers,
Aron

[1] http://sphincs.org/data/sphincs+-r3.1-specification.pdf



--
Aron Wussler
Sent with ProtonMail, OpenPGP key 0x7E6761563EFE3930



On Monday, 11 December 2023 at 10:15, Neal H. Walfield <neal@walfield.org> wrote:


> On Sat, 09 Dec 2023 10:04:14 +0100,
> Stephan Verbücheln wrote:
> 

> > 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.
> 

> 

> I rereviewed the SHA-1 is a Shambles paper. For those following
> along, it is is available here:
> 

> https://sha-mbles.github.io/
> 

> I'm confused as to why you think a salt wouldn't help prevent this
> attack.
> 

> As I understand it, the Shambles attack is a chosen-prefix attack.
> From section 6:
> 

> We recall that a chosen-prefix collision attack works as follows:
> given two arbitrary prefixes P and P′, an attacker can generate two
> messages M and M′ such that H(P ‖ M) = H(P′ ‖ M′).
> 

> The scenario is: the attacker finds two, carefully crafted prefixes
> that collide. One appears to be benign, and the other is malicious.
> The attacker convinces the victim to sign the benign text, and then
> transfers the signature to the malicious text. From Section 1.1:
> 

> The chosen prefixes correspond to headers of two PGP identity
> certificates with keys of different sizes, an RSA-8192 key and an
> RSA-6144 key. By exploiting properties of the OpenPGP and JPEG
> format, we can create two public keys (and their corresponding
> private keys): key A with the victim name, and key B with the
> attacker name and picture, such that the identity certificate
> containing the attacker key and picture leads to the same SHA-1 hash
> as the identity certificate containing the victim key and
> name. Therefore, the attacker can request a signature of his key and
> picture from a third party (from the Web of Trust or from a CA) and
> transfer the signature to key A. The signature stays valid because
> of the collision, while the attacker controls key A with the name of
> the victim, and signed by the third party. Therefore, he can
> impersonate the victim and sign any document in her name.
> 

> This attack is possible due to the structure of a PGP signature; the
> attacker is able to choose the prefix that the victim signs. This is
> illustrated in Figure 8 of the paper: the attacker controls a huge
> part of the prefix.
> 

> Wouldn't this attack fail if the victim prepended a salt to the data
> that they sign? Then the attacker wouldn't be able to chose the
> prefixes.
> 

> Thanks,
> 

> Neal
> 

> _______________________________________________
> openpgp mailing list
> openpgp@ietf.org
> https://www.ietf.org/mailman/listinfo/openpgp