FIPS 204: ML-DSA hash OIDs encoded backwards

[Markku-Juhani O. Saarinen]

Hi All,

HashML-DSA.Sign() and HashML-DSA.Verify() in FIPS 204 insert the hash function OID using the primitive IntegerToBytes(), which converts the input integers to bytes in little-endian order. Since the OID is handled as a "big integer" for some reason, the OID bytes end up backwards in ML-DSA in relation to ASN.1 DER byte encoding.

Using SHA-512 as an example (Line 14 of Alg 4 and Line 10 of Alg 5 in FIPS 204):
0x0609608648016503040203 -> IntegerToBytes() -> (0x) 03 02 04 .. 06

In FIPS 205 the OID is not backwards: The corresponding functions hash_slh_sign() and hash_slh_verify() noth use the toByte() function to encode the same OIDs (expressed as integers). The behavior seems correct here as this encoding function is big-endian.

Again, with SHA-512, the same OID (Line 13 of Alg 23 and Line 9 of Alg 25 in FIPS 205):
0x0609608648016503040203 -> toByte() -> (0x) 06 09 60 .. 03.

(Sidenote: Encodings in FIPS 205 are generally big-endian, while encodings in  FIPS 203 and FIPS 204 are little-endian. The DER byte encoding and ordering of ASN.1 items is unambiguous; which is really the main selling point of ASN.1, if any.)

For the sake of interoperability, it would seem helpful to include the signing and verification functions in the scope of CAVP testing and the FIPS 140-3 certification process.

Cheers,

-markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

[Blumenthal, Uri - 0553 - MITLL]

Absolutely!

 

I’m surprised that NIST missed that, and hope they will quickly address the problem and align (that part of) FIPS 204 with FIPS 2-5 and DER.

--

V/R,

Uri

 

There are two ways to design a system. One is to make it so simple there are obviously no deficiencies.

The other is to make it so complex there are no obvious deficiencies.

                                                                                                                                     -  C. A. R. Hoare

 

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Markku-Juhani O. Saarinen <mjos....@gmail.com>
Date: Wednesday, August 14, 2024 at 03:50
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXT] [pqc-forum] FIPS 204: ML-DSA hash OIDs encoded backwards

Hi All, HashML-DSA. Sign() and HashML-DSA. Verify() in FIPS 204 insert the hash function OID using the primitive IntegerToBytes(), which converts the input integers to bytes in little-endian order. Since the OID is handled as a "big integer"

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender

This message came from outside the Laboratory.

 

ZjQcmQRYFpfptBannerEnd

--
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/CA%2BiU_q%3De8BkrRkYCwPjx7WvdGrPeFgk1bv4QOq%2B8brJFx_tqZQ%40mail.gmail.com.

[Perlner, Ray A. (Fed)]

Hi Markku and Uri,

 

We agree. The byte ordering in HashML-DSA looks like a mistake.

 

We are currently looking into fixing it,

 

Ray

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/PH1P110MB1412AE7E7799B98703490EBE9087A%40PH1P110MB1412.NAMP110.PROD.OUTLOOK.COM.

[Perlner, Ray A. (Fed)]

Dear all.

 

We have posted an update to FIPS 204 to correct this issue. The byte ordering of the OID should now match standard DER encoding (and the byte ordering used by FIPS 205.) We also made some minor editorial changes and modifications to the pseudocode of algorithms 9,11, and 13, to make implementation mistakes less likely in the case that the pseudocode is assumed (contrary to our intent) as passing algorithm inputs by reference. These algorithms (if interpreted as pass by value) are functionally equivalent to the pseudocode prior to our update.

 

Ray

[Paul Hoffman]

On Aug 22, 2024, at 09:04, 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-...@list.nist.gov> wrote:
> We have posted an update to FIPS 204 ...

Where?

--Paul Hoffman

[Moody, Dustin (Fed)]

https://csrc.nist.gov/pubs/fips/204/final

Federal Information Processing Standard (FIPS) 204, Module-Lattice-Based Digital Signature Standard Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. In addition, the recipient of signed data can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time. This standard specifies ML-DSA, a set of algorithms that can be used to generate and verify digital signatures. ML-DSA is believed to be secure, even against adversaries in possession of a large-scale quantum computer. csrc.nist.gov

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of Paul Hoffman <paul.h...@icann.org>
Sent: Thursday, August 22, 2024 12:38 PM
To: Perlner, Ray A. (Fed) <ray.p...@nist.gov>
Cc: pqc-forum <pqc-...@list.nist.gov>

Subject: Re: [EXT] [pqc-forum] FIPS 204: ML-DSA hash OIDs encoded backwards

--
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/81BB1E7B-19D2-4458-8696-FADC605A2F11%40icann.org.

[Paul Hoffman]

On Aug 22, 2024, at 09:49, Moody, Dustin (Fed) <dustin...@nist.gov> wrote:
>
> https://csrc.nist.gov/pubs/fips/204/final

The link on that page goes to the not-updated version of the document. Ray said "We have posted an update to FIPS 204 to correct this issue". I'm asking where that update is posted.

--Paul Hoffman

[Moody, Dustin (Fed)]

That is the correct link.  The .pdf has been updated there.  Perhaps you need to refresh the browser.  

---

From: Paul Hoffman <paul.h...@icann.org>
Sent: Thursday, August 22, 2024 12:58 PM
To: Moody, Dustin (Fed) <dustin...@nist.gov>
Cc: Perlner, Ray A. (Fed) <ray.p...@nist.gov>; pqc-forum <pqc-...@list.nist.gov>

Subject: Re: [EXT] [pqc-forum] FIPS 204: ML-DSA hash OIDs encoded backwards

[Paul Hoffman]

On Aug 22, 2024, at 09:59, Moody, Dustin (Fed) <dustin...@nist.gov> wrote:
>
> That is the correct link. The .pdf has been updated there. Perhaps you need to refresh the browser.

I did, and have again. The first page of https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf says that it was published August 13, 2024. Either the document was not updated, or the front page has incorrect information on it. I was assuming the former.

--Paul Hoffman

[Moody, Dustin (Fed)]

If you go to section 5.4, you'll see that the OIDs no longer have IntegerToBytes, which was present in the original.

I guess the publication date on the front was left alone.

---

From: Paul Hoffman <paul.h...@icann.org>
Sent: Thursday, August 22, 2024 1:02 PM

To: Moody, Dustin (Fed) <dustin...@nist.gov>
Cc: Perlner, Ray A. (Fed) <ray.p...@nist.gov>; pqc-forum <pqc-...@list.nist.gov>
Subject: Re: [EXT] [pqc-forum] FIPS 204: ML-DSA hash OIDs encoded backwards

[Markku-Juhani O. Saarinen]

Hi All,

Here's a further public comment about the prehash OIDs:

The SHAKE128 example in (the "sneak-revised") FIPS 204 (Algorithms 4 and 5) and FIPS 205 (Algorithms 23 and 25) uses { hashAlgs 11 } uses the OID "id-shake128" and truncates XOF output to 256 bits. The id-shake128 and id-shake256 OIDs can be found at https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration

id-shake128 OBJECT IDENTIFIER ::= { hashAlgs 11 }
id-shake256 OBJECT IDENTIFIER ::= { hashAlgs 12 }

(The "hashAlgs" prefix is 2.16.840.1.101.3.4.2.)

However, NIST actually defines two sets of OIDs for SHAKE. The prehash algorithms could also use OIDs "id-shake128-len" and "id-shake256-len", allowing one to specify the XOF output length explicitly.

id-shake128-len OBJECT IDENTIFIER ::= { hashAlgs 17 }
id-shake256-len OBJECT IDENTIFIER ::= { hashAlgs 18 }
Alg-SHAKE128-LEN ALGORITHM ::= { OID id-shake128-len PARMS ShakeOutputLen }
Alg-SHAKE256-LEN ALGORITHM ::= { OID id-shake256-len PARMS ShakeOutputLen }

These length-specifying OIDs are needed for security reasons in some use cases. However, in this particular case, I don't see a direct security concern as the length of XOF output PH_M is authenticated by other means; it is the *last element* of M'. The "internal" signature process authenticates the length of M' and hence the length of PH_M too. Encoding of these longer hash-length-specifying SHAKE OIDs might be a bit cumbersome, so perhaps the simpler OIDs are better.

I've heard an industry person saying that they'd like to use "SHA3" for ML-DSA or SLH-DSA signatures. Indeed, one might think that using SHA3-256 and SHA3-512 would be the most natural way to use the SHA-3 standard FIPS 202 to generate fixed-length hashes. The main reason for not doing this is related to performance when processing large amounts of message data, as is expected to be done with the prehash modes. Assuming that data transfers are significantly faster than the core Keccak f1600 permutation that both use, the block sizes imply that:
- SHAKE128 (256-bit output) is 21/17 = 23.5% faster than SHA3-256 and
- SHAKE256 (512-bit output) is 17/9 = 88.9% faster than SHA3-512.
The relevant security properties, namely collision resistance, are maintained. However, one obviously should not expect collision resistance with more than 256 bits of SHAKE128 output.

So, given the many options and potential for non-interoperable implementations and security mishaps, I hope that NIST will explicitly write down (perhaps in the FIPS 140-3 IG document) that:
- "id-shake128" and "id-shake256" OIDs should be used when signing with FIPS 202, not any of { id-shake128-len, id-shake256-len, id-sha3-256, id-sha3-384, id-sha3-512 }.
- SHAKE128 is only allowed with Category 1 or 2 parameter sets (lambda=128, n=16), while SHAKE256 must be used for Categories 3 or above (lambda>128, n>16). Output truncation should be 2*lambda bits (FIPS 204) or 2*n bytes (FIPS 205).

Best Regards,

-markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

--

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/SA1PR09MB86699D503A3DE0698949CA77E58F2%40SA1PR09MB8669.namprd09.prod.outlook.com.

[David A. Cooper]

Hello Markku,

You said with respect to the different SHAKE OIDs that "Encoding of these longer hash-length-specifying SHAKE OIDs might be a bit cumbersome, so perhaps the simpler OIDs are better." This is not actually correct. The encodings OIDs for both id-shake128 and id-shake128-len are the same length and only differ in the last byte. The parameters mentioned below are associated with the OID, but are not part of the OID.

Cryptographic algorithm OIDs are frequently used in the AlgorithmIdentifer data structure:

   AlgorithmIdentifier  ::=  SEQUENCE  {
        algorithm               OBJECT IDENTIFIER,
        parameters              ANY DEFINED BY algorithm OPTIONAL  }

The contents of the parameters field depends on the OID. When the algorithm is ecPublicKey, the parameters field indicates the elliptic curve (e.g., P-256). When the algorithm is id-shake128-len, the parameters field indicates the output length. When the parameters field is id-shake128, the parameters field is absent. The ALGORITHM structure (see RFC 5912) provides information about an algorithm such as its OID and how the parameters field should be populated in the AlgorithmIdentifier structure.

FIPS 204 and FIPS 205 specify that M' is constructed for pre-hash as something like 1 ||  |ctx|  || ctx || OID || PH(M). Only an OID is included, no parameters.

FIPS 186-5 allows for the use of any approved hash function or XOF when generating a signature, regardless of the length of the key pair, as long as the security strength of both the hash function and key pair "meet or exceed the security strength required for the digital signature process." While FIPS 186-5 says that the security strength of the hash function should meet or exceed that of the key, it is not a requirement.

For the approved XOFs, FIPS 186-5 says that the output length shall be 256 bits for SHAKE128 and 512 bits for SHAKE256, regardless of RSA modulus size of elliptic curve used. FIPS 205 specifies these same output lengths for SHAKE128 and SHAKE256 for all parameter sets.

FIPS 204 and FIPS 205 only show a few examples for options for the pre-hash function, and for the OIDs that will be listed at https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration, we expect to show even fewer options (one per parameter set). Hopefully this will promote interoperability by encouraging implementers to use these choices.

[Markku-Juhani O. Saarinen]

Hi David,

Yep. The lack of a SEQUENCE to wrap the OID with parameters does indeed rule out the use of shake128-len and shake-256-len parametrized OIDs, as this would not be secure. However, it would be good to clarify this in the IG.

You mention that in current standards SHAKE256 is always truncated to 512 bits regardless of security level; this seems reasonable. For consistency, perhaps it would make sense to specify the use use SHA2-512 instead of SHA2-384 at security Category 3 parameter sets of ML-DSA and SLH-DSA ? One can also consider the CNSA FAQ, which now makes this possible (it was a bit strange to require SHA2-384 with Category 5 parameter sets anyway.)

Best Regards,

-markku

The NIST ASN.1 module seems to specify these other OIDs should be used in conjunction with parameters.