[openpgp] Binding signature salt size to hash function [was: Re: changing v5 signature salt size from 16 to 32 octets?]

[Aron Wussler <[e-mail]>]

Hi all,

First of all, thank you for the productive discussion at the IETF-115 session!

I've prepared a PR with the necessary changes to bind salt size to the hash on gitlab [1]. I've also attached a git patch for the proposed change.

The change is quite straightforward: salt size is explicit in the table, and justified as MAX(16, hashOutputSize/2) octets.

I've had a further thought about the point raised by Scott, that it is an online attack and guessing 16 octets should already provide enough security.
Personally I agree with this statement with the current state of the art, but if we assume that the hash function used is partially compromised (e.g. SHA1, where collisions have been found, but 2nd-preimage resistance still holds), we cannot assume that the attack will be able to reduce the search space of the hash.

Therefore binding the size of the salt to the expected collision resistance will guarantee that as long as a hash has 2nd-preimage resistance it will be "safe" to use - at least to verify old signatures (not advertising here to go back to SHA1 signatures).

Cheers,
Aron



[1] https://gitlab.com/openpgp-wg/rfc4880bis/-/merge_requests/219


--
Aron Wussler
Sent with Proton Mail, OpenPGP key 0x7E6761563EFE3930



------- Original Message -------
On Friday, November 4th, 2022 at 10:52, Andreas Hülsing <[e-mail]> wrote:


> Hi all,
> 

> To give a bit of context why the SPHINCS+ team did this and I still
> consider this a very good idea also in OpenPGP:
> 

> The attacks on SHA1 have demonstrated that collision attacks are also in
> practice significantly easier than (second-)preimage attacks (not only
> in absolute cost but in a "getting better than the generic
> attack"-sense). This is something theory has predicted in some sense for
> a long time -> you cannot build a collision resistant hash function from
> 

> every one-way or second-preimage resistant hash function. This seems to
> be a good reason to avoid collision resistance as an assumption.
> 

> Including an unpredictable salt in the hash input (for MD-based hashes
> this value has to be included as prefix) avoids collision attacks up to
> "guessing the prefix". In consequence, you want to make this salt the
> length of the security parameter. For SPHINCS+ this is the output length
> of the used hash functions. For other schemes it is the bit security,
> i.e., 128 bit for a 256 bit curve scheme like Ed25519.
> 

> Best wishes,
> 

> Andreas
> 

> 

> On 04-11-2022 10:58, Aron Wussler wrote:
> 

> > Hi dkg, hi all,
> > 

> > > Are there any size concerns worth considering here?
> > > I agree, generally I don't like the idea of increasing size for everyone, especially when it's not needed. Compact signatures like Ed25519 will definitely be affected from this change.
> > > This is a trade-off between simple design (fixed size - but larger) or on-wire efficiency.
> > 

> > > > (2) it is possible to bind the salt size to the hash function.
> > > > Is it the hash function that is relevant here or is it the public key
> > > > signature function?
> > > > IMO here it's the hash function specifically. Given a weak hash function that still provides second preimage-resistance but not collision resistance an attacker can not craft a plaintext such that its signature will match another message.
> > > > Furthermore the algorithm ID unfortunately does not univocally identify the strength of the algorithm. RSA could be 2K or 8K, EdDSA may be Ed25519 or Ed448, ...
> > 

> > Therefore, I would bind it to the hash function. Generally speaking hashing with SHA-512 and then producing a signature with Ed25519 will make the curve the weak link.
> > 

> > > I understand that SPHINCS+ is itself hash-based, so perhaps this is
> > > getting too far into the PQC discussion, but can you give the WG a
> > > summary of how you think binding the salt size to the hash function
> > > would work?
> > 

> > I would imagine to change the following notes [1], [2] to a fixed-size octet string that depends on the hash algorithm ID, and add a reference to the table at 9.5.
> > In section 9.5 [3] I would add a column "Salt size" with 16 octets for all 256 bits or lower hashes, 24 octets for 384 bits hashes, and 32 octets for 512 bits hashes.
> > 

> > OpenPGP has the requirement of hashing the message before signing, for instance already now without PQC in EdDSA we follow this paradigm (be it streaming, or how "things are done")
> > This expands the attack surface, because a collision on the hash means a valid signature. The crypto-refresh addresses this by adding salted signing, and we'd like to leverage this to maintain the security proofs in Dilithium and SPHINCS+ because, similarly to EdDSA, both algorithms expect the full data to be passed there, not just the hash of the data.
> > 

> > The change we're proposing would be independent of PQC crypto, even though it has its roots in SPHINCS+. It would allow us to reuse the decision done from the authors of SPHINCS+ of hashing a random string of variable length n (see section 6.4 and table 3 and in [4]), therefore maintaining the security proof at the same level even with the OpenPGP construction.
> > 

> > Finally, being this an online attack, I acknowledge that 16 bytes will be sufficient for most uses, but would mean a degradation of security in certain contexts, for instance when signing using SPHINCS+-192 or SPHINCS+-256 and expecting the full security of the algorithm.
> > 

> > Cheers,
> > Aron
> > 

> > [1] https://www.ietf.org/archive/id/draft-ietf-openpgp-crypto-refresh-07.html#section-5.4-3.5
> > [2] https://www.ietf.org/archive/id/draft-ietf-openpgp-crypto-refresh-07.html#section-5.2.3-2.10
> > [3] https://www.ietf.org/archive/id/draft-ietf-openpgp-crypto-refresh-07.html#section-9.5
> > [4] https://sphincs.org/data/sphincs+-r3.1-specification.pdf
> > 

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

> > ------- Original Message -------
> > On Friday, November 4th, 2022 at 03:13, Daniel Kahn Gillmor [e-mail] wrote:
> > 

> > > On Thu 2022-11-03 08:32:00 +0000, Aron Wussler wrote:
> > > 

> > > > In v5 we added a 16-byte random salt prefixing the data when hashing for signature, great idea because if it's unpredictable it can prevent collision attacks.
> > > > 

> > > > In SPHINCS+ this is also similarly done in the construction, but it has a variable size depending on the hash output size.
> > > > 

> > > > To make randomized hashing coherent with PQC signature schemes I'd like to ask if
> > > > 

> > > > (1) it is possible to extend the field to 32 bytes to match other constructions,
> > > > Are there any size concerns worth considering here?
> > > 

> > > The salt needs to be represented in a few different contexts:
> > > 

> > > - in the one-pass signature packet
> > > - in the SaltedHash Armor header for a (LIT SIG)-style signed
> > > message (non-one-pass), and probably
> > > - in some sort of RFC 3156-style parameter to enable one-pass
> > > validation of a signed e-mail message.
> > > 

> > > base64-encoding the 32-byte value will bring this to 43 characters.
> > > 

> > > That would make the SaltedHash: armor header 43+13+8 = 64 characters
> > > long, like so:
> > > 

> > > SaltedHash: SHA3-256:9haH8LirCmteTImei9GQtIHMgJ26zM/uPAoiZepB4cw
> > > 

> > > That's not implausible for messages of already moderate size, though it
> > > does double the size of the signature itself for small-signature formats
> > > like ed25519.
> > > 

> > > I should add a note of historical caution about including too much
> > > gratuitous randomness. tls-extended-random [0] has not aged well [1].
> > > 

> > > [0] https://datatracker.ietf.org/doc/html/draft-rescorla-tls-extended-random
> > > [1] https://blog.cryptographyengineering.com/2017/12/19/the-strange-story-of-extended-random/
> > > 

> > > The crypto-refresh revision to RFC 4880 does caution about this in the
> > > "Random Number Generation and Seeding" section. It might be worth
> > > including pointers to that section in the section where we talk about
> > > salts for v5 signatures.
> > > 

> > > > (2) it is possible to bind the salt size to the hash function.
> > > > Is it the hash function that is relevant here or is it the public key
> > > > signature function? From OpenPGP's perspective, the message is hashed,
> > > > and the hash is signed. In the OPS packet, there is an explicit
> > > > indication of the public key algorithm used. What if we were to tie the
> > > > salt size to the public key algorithm, perhaps by adding a column to
> > > > Public-key algorithm registry indicating "v5 signature salt size"?
> > > 

> > > I understand that SPHINCS+ is itself hash-based, so perhaps this is
> > > getting too far into the PQC discussion, but can you give the WG a
> > > summary of how you think binding the salt size to the hash function
> > > would work? Are you suggesting that the salt should be (for example)
> > > the size of the hash used? That would make the SaltedHash header long
> > > enough to potentially cause linewraps when, say, SHA2-512 or SHA3-512 is
> > > in use.
> > > 

> > > --dkg
> > > 

> > > _______________________________________________
> > > openpgp mailing list
> > > [e-mail]
> > > https://www.ietf.org/mailman/listinfo/openpgp
> > > 

> > > _______________________________________________
> > > openpgp mailing list
> > > [e-mail]
> > > https://www.ietf.org/mailman/listinfo/openpgp