Dilithium hint unpacking

[Mike Hamburg]

Hello all,

I have a question about hint bit unpacking in the FIPS-204 draft.  Apologies if someone else has asked this already.

The HintBitUnpack procedure is supposed to undo HintBitPack, and it checks that the y[omega] terms are in ascending order, but it does not check that the y[index] terms are in (strictly) ascending order.  If I understand the draft spec correctly, this means that signatures are malleable: by rearranging the hints, or by listing the same index twice, someone can rewrite a valid signature into a different valid signature.

The Dilithium reference code at https://github.com/pq-crystals/dilithium/blob/master/ref/packing.c appears to check that the hints are in ascending order.  I don’t see where the round 3 specification specifies how to encode the hints at all, beyond Section 3’s vague:

> The signer therefore simply sends the positions in which these carries occur (these are the extra bytes in Dilithium compared to the signature in Fig. 1), which allows the verifier to compute the high order bits of Az − ct.

Am I missing something here, so that signatures aren’t malleable?  If not, then in my opinion, it’s better if this decoder is changed to remove this malleability.

Or are they malleable anyway due to some other trick?

Regards,

— Mike

[John Mattsson]

Hi Mike,

 

>Or are they malleable anyway due to some other trick?

 

They shouldn’t be. NIST writes in Draft FIPS 204 that ML-DSA is designed to be SUF-CMA: "ML-DSA is designed to be strongly existentially unforgeable under chosen message attack (i.e. it is expected that even if an adversary can get the honest party to sign arbitrary messages, the adversary cannot create any additional valid signatures based on the signer’s public key, including on messages for which the signer has already provided a signature)"

 

>If not, then in my opinion, it’s better if this decoder is changed to remove this malleability.

 

If you are correct, this definitly needs to be fixed. I strongly think ML-DSA should be designed to be SUF-CMA.

 

Cheers,

John

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/B2DB9D16-2665-4BC0-A3F5-FE1BF29CBE54%40shiftleft.org.

[John Mattsson]

Hi,

 

Sönke Jendral who is currently doing his master thesis on ML-DSA (at Ericsson and KTH in Stockholm) looked into the hint bit unpacking procedure as specified in draft FIPS 204. He implemented the currently specified pseudo code for hint bit unpacking and experimentally verified the problem pointed out by Mike Hamburg, that an attacker can indeed create additional valid signatures when the current procedure is followed. ML-DSA is claimed to be SUF-CMA-secure, but ML-DSA with the currently specified procedure is not. Sönke also verified that as Mike already pointed out, existing implementations (all he could find) have an additional check in place that prevents the attack.

 

Cheers,

John Preuß Mattsson (on behalf of Sönke Jendral)

 

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB9678960A83AC51A93100C3B189462%40GVXPR07MB9678.eurprd07.prod.outlook.com.

[Perlner, Ray A. (Fed)]

Thank you Mike for catching this error in our pseudocode and thank you Sönke for confirming it.

 

We will fix the error in the final version of the FIPS.

 

Ray Perlner (NIST PQC)

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/GVXPR07MB9678F1C6A1B7441AD9A81AAB89452%40GVXPR07MB9678.eurprd07.prod.outlook.com.