ML-DSA keyGen and sigVer success only after byte order reversal of seed / message

[mwcw]

environment
Demo

testSessionId
501055 -- sigVer all passing with reversal of message
501053 -- keyGen all passing with reversal of seed

vsId
2261682 -- sigVer
2261680 -- keyGen

Algorithm registration

[
  {
    "acvVersion": "1.0"
  },
  {
    "isSample": true,
    "algorithms": [
      {
        "mode": "sigVer",
        "parameterSets": [
          "ML-DSA-44",
          "ML-DSA-65",
          "ML-DSA-87"
        ],
        "algorithm": "ML-DSA",
        "revision": "FIPS204"
      }
    ]
  }
]

and

[
  {
    "acvVersion": "1.0"
  },
  {
    "isSample": true,
    "algorithms": [
      {
        "mode": "keyGen",
        "parameterSets": [
          "ML-DSA-44",
          "ML-DSA-65",
          "ML-DSA-87"
        ],
        "algorithm": "ML-DSA",
        "revision": "FIPS204"
      }
    ]
  }
]

Endpoint in which the error is experienced
demo

I was able to get ML-DSA sigVer vectors to pass if I reversed the byte order of the message being supplied to our verifier.
Looking at the spec, and I am not super familiar with Dilithium, it appears that the message M is passed into H as is without any modification during the verification operation.

Our test harness passes hex encoded byte arrays from left to right, so "ABCDEF" => [0xAB, 0xCD, ... etc]

With respect to keyGen I was able to get a successful pass if I reversed the byte order of seed supplied to our implementation as well.

Without the byte order reversal it is 100% failure in for the modes tested so far.

Reversal in this case is: [0,1,2,3] => [3,2,1,0]

Let me know if you need any more information?

I have attached vector sets, our responses etc

Thanks,

MW

[ml-dsa_keygen_pass.zip](/~https://github.com/us
ml-dsa_sigVer_pass.zip
nistgov/ACVP-Server/files/14899860/ml-dsa_keygen_pass.zip)

[celic]

Can you please verify the implementation has the algorithm in Draft FIPS 204 Section 8.1 defined properly? They define how to read the byte values.

The reverse byte order is an interesting problem. We've published tests produced from this code previously and didn't receive such feedback. I'd like to verify that it isn't just this implementation before diving deeper.

[cipherboy]

@celic I'm a little confused by your statement. As far as I can tell (and I may be wrong!), Algorithm 2 ML-DSA.Sign(sk, M)'s use of M does not depend on the helper algorithms defined in Section 8.1 at all?

In particular, we define M as message M ∈ {0, 1}* i.e., a bitstring, and only use it in step 6 AFAICT:

μ ← H(tr||M, 512) ▷ Compute message representative μ

i.e., simple concatenation into the XOF's input stream.

Building a simple reproducer here in C, based off of the reference implementation:

Source code

#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "../sign.h"
#include "../api.h"

uint8_t *decode_hex(const char *hex, size_t *size);

uint8_t *swapped_msg(uint8_t *msg, size_t msg_len);

int randombytes(unsigned char *x, unsigned long long xlen)
{
  return -1;
}

int
main()
{
  const char *pk_hex = "051EB9609C254C299E2105FDB4DB2F4783B6D65504CF93289188A443B4CA59EDD372C8272A4DDCA95D890D8AFB9D7122D7463A22FEEB7A118C67A836CC1BB987D4149EBDA0BC05B0EF337ABAAE2F6216B8A7A497128F14B38051D87023328DC016E7277B0204A8399BB553FCC88666A1C1B58129C9AB07BAD3980F11EFFD1CA4347C0FDE6BE896D9F33B5AA69B70F077395CC00B0C82365470E516E789034B3A4CA5A147F8B50FB210C2C2AF8EB4D24E9F7CE298FF4763A161BB3984A16E34B111065491A38E36A1ACCBED68D1494ACA6805E304E1DE41C517DF983C41EC19E6CE3BF4F4119F7CDB2F34A81847D1C599BF350F2E081FD952652973912077F99E6F6474883D86838D4D09BD0FF56850A54CD778BB3F89CB4188BA3279D643E681509380E68D48E6B97A7D03B5E76D8331600620BCCC3508B64C91E1A6E1ED37D6536D9AB485039F26160232E9B699317E6DF634B9C947E43461C9DF225856F5EBE122918135063E3051CCC87D6EBB5CA72B134874D98A60EC7619E8D9B8C2FE9B9AA757CEE702EF23FB312D44460D6183558D9DD042EAC217FAA0A875F92CCC6103069DF9220E2EEC5394778146A6437DE24110D0B1EAF4D84A0583B355D77F0605188A97228F28CD6A67EA2B1B423363F9FD8ECA2A2B031B1D8A4B0AEE0A44C622BE372EEB52255CDDB6FC082477E7CED75BEC36D76F13E30688171DB20FA8E517178AEF0578765D63B39298205A3AAE23B3EC043A7753BEF489D27D14922D5B8BFEBA436EFF7E1C3E07CE8CA928652EDA9798A4AEAC7264199CF7F974AE56C1D877A565C0BC27488E96F123D005BF1A29AB1DD402881989C43824A4300D476CAE73D817B081D792B232FF58E79BEBEE010EC27B09CEB52E559C4F1AF1758B4107D2BD2299862B9E7DD1140F4EEF22FF3EE9696368ACDA352610563943B66AC6763854CE79C3CDED7AD86822F8A0FDDDCA7ED6136B8DD758E9C4A848ED1C5C935B08EC1640B7809C6E8ECE70080BB52154D26AE19916E172709940673B647E842C6F94E1FBF386C63589E0BD5B6FB8A34D618DF0AB2A64AF8C91A681C85297BA311F9D214FAFA20CD4043565207C63997974F78AF76E239DEB8492C108BFA2A753736FCF57245EF774DE581F815AC9A7D0BDDDD59CAD45D384F09762F23088FE1795290DF9AE3CF4F1A6F727C372FB906166471F01AB594CEAEB97B3E6AE26EB9D77AA87132C0EB536A8807B8FA24B832567395E6DFACAAE555C66AAA226A1C6B61CFD8C2E2BDD23F344952186C6762583278F0C61E6557F705414FE9FC6F63EBDA281ACECB32DB1292C2E74B7A90B75D8B62207AF3B4249BE439332C4931637BEF3D274F6038168EF17A2FA72010D3212416B933B07E4805B92275110A0E74EB369377EF0A4CE553C3EC1041BFBE5856339850D279C2FA1FD02503CA8BDE02B62266366DD6D601F7B7C2DB8833AA155DCB3C22981917BEFA0DD000E6382FC19A41F4811EE636C1CFFC226D10C5C30E64B7363C64C9D76461E4B4DB9758C4FFAFEEB3D6FFC8234C6FAFAB0257859481131B7B17BC77461AE4D852978281952F16FE487A08CD229F15C3556CC174456CF56EE5410C5288EEF6B08C60C73F9DF0D545FC11153FC6EADB51D5545356CCE75C178A219F8CCA21408E8350A93187F55FE1AF904B1E350D3B3B16E87C1E52E763F0B3B4895BFC117DD16A062C113A950DC91F9A936314CBF0AA277F895E11136F8B4CB48FA1EB089C78B76222DDD578E9B08B4DA7583EE1BFEAE3F563213C5ABE611B3B66435C8336E11EBF850EE4F3C061C5EC8CB87B1E92A62DBD5DCEC9E6A75F70F24C279793E1BAAA23099659569";
  const char *msg_hex = "FC8B7DBB1859F24012BB262D521FE00F439A517A9C8AF25066B9C09C4BE78C1D7E9FE4E987CBD13A3C0F29864E9A1D7F0143AC0BE0C576E1740487EA932F4F3C4274C86F9EE252EFA6323F126B6755EEA354CB9B23CF91460F82CBD9BB776C7B2194EDA388C1D3CDDED0DA720C856340DE426200AB71D03018513071AF31BF80";
  const char *sig_hex = "9FDF37B39592DB390D24F9C6553F125DBC708256A31427C4AEF28D79D883960C5D064FD43F692B296F67660B1B30EFD94F706907C626CA1A2C30755FAE2752662209A39F109CB468AA66981DC682A25B02434A1396AE62B89132AC4413C597D81F535BCBB0FF76716E8F17533FF7B7B904D3E8E4906B77029B61799AD87EE3A744A1B4FAB55884B6D8463C18ED5E14E542E2C58D36892C6AFA94165906770D6A0A0BBC9E572C61EB565571BBA2BBC951CE4F1DFF9C88E40FEB2EEFEA60C0B88EFA85D70B25191B0895231E31497F0F526DB259FB9DA91DADF3019445C00FF7A94DFF4E3B7DF849F70E2A8F0A3919E16F4E2EDD537052C06FE971D541168A56DEE45537D04649A17C2838ECCB3796D2D7348CA3E80BC87E5085FB6D569BEADE9281413137B8C43E9C2E6C760ECF5F70135ABCABBE6E3D62383A10DFA27730F3C27E3105AB3E96368AEF94AD66B6FE3C9551D2B0AD21D20A67214DD6502888F06F87B716D79AEFBB4DBB3374444BB2F378AB813A550927D77EACA667026E156AF083C6138C12C5404BEBD66AE0B3BFA97411CA48BD644F076128D6BE7B8BAB57B972F1857E1004619305F62550249E2B5B1F30E33009CF94C449524F81FDB64D99A28B1969609A0A4474E7E3ADF53F8480EC1F9C5F65857C46A00099A5C2036E29557F0B9A4B211CC6DB7E727E8211B0BF3531ABDCF023DC775BA5FE02145D50ADD2027740FAA75C41840929A096DBA63E0D078E4EC7B60BC8682FE6961D0F8BEF7B91BA3BE94395D173C9E6995BB1DD47C7F3023D54E15EC6DC6AFEEB3A13D7C6B83242931B30E4F8372F26CC920B3F8F9DBF03B22275F4766B13B2DFAC2A655B7E0C889053D4CF45B1315A81A9495C75A23DFDC9CACBEF9E65A6BD2A1B0D97D37F9289A40A395C61BDEABE00CCE68031844DDCF009DDED2EF5D482A4A3134D3F08E3C1E62FE3C5DC6A71CE6664DC2FC2AB4AC818F617BC6746E32C8F77B4E59F01F159D61E5C12238AD6880C877602E09202E2799E91C85EAEC5A1FB822A89F8DE6A87FE170959F27006D67C0A5B3AB44B28FA8A6EE6C87AFFD94FDDA84827642733196C698CB7BF54D3ABA0F93E14A2AA9B885A08ED580219EAC22A16B1141BE4D746AFFB8C7E8870A2C8AB4EC8D6C20323194A2B74EA0C27D5A46655B05088F6EC52BBD5B0331010FE16FE9F81068A677E6F8DC085BF20EAF66FB9242FF85FFE7FFE5A2583B6150AAD78F4B708E43CEF8C83525C8EA57A5E7FFEF8D48685D3A32811CDF99C0D4ED64F210BF55C069411C25FEF0973CEC32DA53FF37C61026D315803DD93592FB41037CB0EAF69ED8B0966737276838EE740B8FA72C1BE20050894812437DC463D2A3D5A390AF7D13D0BE957EC2DFE3C99D5CE38FFC07CA9B01606C9F4BBD8D7AB97DDE34EE04EF1E37595CF367F34174EA2815B2DF98B5376974ABD58C73A21C30106665CCDD826F5F00E5A8E7627FF0063E1AF99E0DD525AB95929A07503485F209C4A95D0AACD77996572AD510234FE328CA14C8E270BB08544EDE507E97A60425D51C818ED51948F10CF53C66357C9DC73AC63FF9FF7293C3F765AA22A1C91D3841C76004C21BE7DC47D3B6DEDFBD2CA02C525E1AC316EF53E1D19E7A560435E453D85498F500751F07E9D2994749890CE685EB6C01A1A921BCBC4AC4FBA57FE59E5F272845062278064D45A5733A97497D83A69EBD1D96B870CB93C9E70AB7678B6C9D20698D503846F389E5B0CDD8D289CEEB84A66E2B41A7F2414073974A66DB55369A027E615F78150BA5094404171083D4BE2BF6171E29AF1BEFC1BC43DD825EB2BDA06A3EA7BBF6D32FBC9F1A705B01962A10C80D98FFFD8F568D5A01B1DE62C3102BF6229277850EB7157C840C90D1DA1DAC970275E8D43A1548F24BF04ACCC64D2900BFDEDF67B39A28A0BEBB0E8DAE1F07FE9F121DEF35974D5E82BC6533745F8ED659A213C83514950EE1E1CA7CF6F74D3DD5D13C2B218DDC8B63CD5808E728DCCAD088E87F130F3A68A03F8C0D8DFD00FF2C7EA45C5F150657A866AE5FA5BA362E232952E14C6D959D7F432B20E6F3AEF37A7DC521A8D1DACF068F3CB361207F61A2853297B0167509E8B1C0EA1C3B25611B0349C226B80F22B9A7B6A2FA1A24181787588312C36BE9C7A565FEEC81B6EF017303ED77B4B272262BCDA7C9A1E1CE1A0C43F1D7A2CF849D111B23573902E972B7248B74E83317BBE04158433BC1CBB5E41FD12B644A713456142412978E2B8B4423486429D2BF88F63C2B7B6E861D2382FD9F6A1C20FACA05D01B1040D35F8948FABAF9B6E3243D16D5230A0A8E4C750983080C737513D956306F8222A430D79C3B5B9258B141E95CCAA119F409D945EC9A8B99139707B701412D8290DE324C7E371E21AD32D15A1B655924F91C057018CE1691803CD65838BDDAE8B778C9115018684C6024C6BBA5CC2083E69F26B82846A702DF8733D892753568FED7DD48C15DCEB1AAA3F12A082166FD60B7D467EAD4C3538A73F444BC2312D269EF3505B426B494DEBC8B08B91FDDBA7FE5BD235AAFC6ECF015103D169F80CB7CDC0886E57F551F44A50A6141E399F24C91D3122C96CCE0A452B6AFE2B5A5CFA8C5AC2EDCE7777CED16AFFF53D6462205C8E5E1CB02D8E02E4A935E0D68778CFA62947825CA44D49A9EC961E79512015FC1E3B22E44F50F2F1604771BB1680BFCBE7A948371CB9C6D59F827829AB427D41B43F073140F8572475A2F16C9A63FB63B1D7A1F7D84E65A1EAC535021F03D992AA4D1696C260DA02387288E26C967C6792E95C38C434278B23D0F22AFAE4764E6A4132178AC5CF05EA56B20E3529CCC912B080BA184F0E5CD2A100542DBA5FA34F517ECF19F522985ECFC8950089433C9E3ABFF5A7D9A8F23A5CE25ECAF6CC8E4504927D400726D8D368ACF6D49AF67481240ABA0909382B4FD01066A243A6DCC8DC38222CA097E52E99F7DE2DD102CB49DEC426672BEE45A26F614F4C054E5DD23E1BFC887A7C40992D8FAE51CDEF8A319869A1D5FEB49E30CD0F51D3EC5A740211DFF541C2E91AD8DBAC7707C748A10696E65932F226E255202DF05F2A516C7047B8CE0681895A876E58767EEB75E461ACB4C2E8A5CFE097A4117DAA43DB3F04CB50ADC28214074DE7EDBA6189E65DB0E08C7A92E867C49F1A98171BCD803CF879975286655D96D16A9445304CEFD7D2E1B28C74912D42DD671FB32DCF406C9123F49D10AA94F510CFEF76A528C941A5E43C086E66B50721A5956F4ACFF2D6A4599A9DE1FF5B774E3F1357BDA690F417FE000F1014324D5D64687487CBD2F013486B6D7882859B9FA7DDE2090A101A343F425358646A8A9EAEBEDBE1EEFA081641505C6E818BA1C7CBD6EDFC0000000000000000000000000000000000000000000E1A2D3B";

  size_t pk_len = 0;
  uint8_t *pk = decode_hex(pk_hex, &pk_len);

  if (pk_len != pqcrystals_dilithium2_PUBLICKEYBYTES)
  {
    printf("%s - pk=%zu vs pqcrystals_dilithium2_PUBLICKEYBYTES=%zu\n", "got unexpected length of public key", pk_len, pqcrystals_dilithium2_PUBLICKEYBYTES);
    return 1;
  }

  size_t msg_len = 0;
  uint8_t *msg = decode_hex(msg_hex, &msg_len);

  size_t sig_len = 0;
  uint8_t *sig = decode_hex(sig_hex, &sig_len);

  if (sig_len != pqcrystals_dilithium2_BYTES)
  {
    printf("%s - sig=%zu vs pqcrystals_dilithium2_BYTES=%zu\n", "got unexpected length of signature", sig_len, pqcrystals_dilithium2_BYTES);
    return 1;
  }

  // MESSAGE REVERSAL
  uint8_t *swapped = swapped_msg(msg, msg_len);

  if (crypto_sign_verify(sig, sig_len, swapped, msg_len, pk) != 0)
  {
    printf("%s", "got error verifying signature\n");
    return 1;
  }
}

uint8_t *
decode_hex(const char *hex, size_t *size)
{
  size_t chars = strlen(hex);
  size_t length = chars/2;
  uint8_t *ret = calloc(length, sizeof(uint8_t));

  for (int i = 0; i < chars; i += 2)
  {
    uint8_t value = 0;
    char ch = hex[i];
    if ( (ch >= '0') && (ch <= '9') )
      value |= ch - '0';
    else if ( (ch >= 'A') && (ch <= 'F') )
      value |= ch - 'A' + 10;
    else if ( (ch >= 'a') && (ch <= 'f') )
      value |= ch - 'a' + 10;
    else // shouldn't ever get here
      value |= 0;
    value <<= 4;

    ch = hex[i+1];
    if ( (ch >= '0') && (ch <= '9') )
      value |= ch - '0';
    else if ( (ch >= 'A') && (ch <= 'F') )
      value |= ch - 'A' + 10;
    else if ( (ch >= 'a') && (ch <= 'f') )
      value |= ch - 'a' + 10;
    else // shouldn't ever get here
      value |= 0;

    ret[i/2] = value;
  }

  *size = length;
  return ret;
}

uint8_t *
swapped_msg(uint8_t *msg, size_t msg_len)
{
  uint8_t *ret = calloc(msg_len, sizeof(uint8_t));

  for (size_t i = 0; i < msg_len; i++) {
    ret[msg_len - i - 1] = msg[i];
  }

  return ret;
}

I use the the second vector of the first test case from MW's above -- and with MW's reversal noted -- it passes:

$ cc -Wno-unused-result -O3 -fomit-frame-pointer -DDILITHIUM_MODE=2 \
  -o nistacvp/testacvp nistacvp/main.c sign.c packing.c polyvec.c poly.c ntt.c reduce.c rounding.c fips202.c symmetric-shake.c  -lcrypto
... compiler output elided ...
$ ./nistacvp/testacvp ; echo $?
0

with the message byte order swap above (// MESSAGE REVERSAL) commented out -- hopefully corresponding to the expected interpretation of the vectors, using the decoded hex verbatim -- it fails:

$ cc -Wno-unused-result -O3 -fomit-frame-pointer -DDILITHIUM_MODE=2 \
  -o nistacvp/testacvp nistacvp/main.c sign.c packing.c polyvec.c poly.c ntt.c reduce.c rounding.c fips202.c symmetric-shake.c  -lcrypto
... compiler output elided ...
$ ./nistacvp/testacvp ; echo $?
got error verifying signature
1

(this is built against /~https://github.com/pq-crystals/dilithium/tree/standard/ as of standard's latest commit at the time of writing (e7bed6258b9a3703ce78d4ec38021c86382ce31c) -- placed in a file called ref/nistacvp/main.c and built from the ref/ directory. I chose the second vector since the first one is expected to fail verification, but according to the server responses above, the second vector is meant to pass and does so correctly).

However, without swapping the byte order of the message itself, it fails verification against the algorithm author's standard reference implementation...

AFAICT -- and again, I might be wrong -- if Section 8.1's reversal algorithms is meant to be applied to the input message M, this isn't called out as a difference either in the NIST ML-DSA IPD draft over upstream (Section 1.3 doesn't mention this), and isn't made clear in the Algorithm 2 definition...

Thanks!

[celic]

Our BitString.cs class that we use to store things like byte string values for test case generation works as a big endian structure. Draft FIPS 204 operates on the reversed byte order, little endian bytes. I see why this is happening then. We use byte[] within the crypto for ML-DSA, but need to bring it back into a BitString to put it into JSON. The endianness is being lost in that translation.

I'll see if I can put a fix for this in quickly.

[cipherboy]

Perfect, thank you @celic!

[celic]

This will also impact FIPS 203, ML-KEM.

[celic]

Also to clarify, do you notice this on the signatures, or key values output from the server? Do you need to reverse the public and private key when communicating back to the server to get the correct verdict?

[mwcw]

Also to clarify, do you notice this on the signatures, or key values output from the server? Do you need to reverse the public and private key when communicating back to the server to get the correct verdict?

I'll put it in points so we can refer to it more easily.

ML-DSA:

1. SigGen -- Total fail at the moment both AFT and GDT, reversing or not reversing the message.
2. SigVer -- I can obtain passes if I reverse the message.
3. KeyGen -- I can obtain passes if I reverse the seed.

I have not needed to reverse the outputs, pk,sk or signature, I did not dig too far into SigGen failures at this point because of this issue. I have not attempted to implement any testing for ML-KEM beyond fetching vectors.

Probably off topic, with KeyGen, we had an error report on one set of vectors about a PK and SK not matching on one test but it is intermittent, I have held of looking into that as well. (I have these vectors saved)

Please let me know if you need any more information?

MW

[celic]

Try siggen where you reverse the resulting signature before sending it to the server.

…

On Tue, Apr 9, 2024, 6:53 PM MW ***@***.***> wrote: Also to clarify, do you notice this on the signatures, or key values output from the server? Do you need to reverse the public and private key when communicating back to the server to get the correct verdict? I'll put it in points so we can refer to it more easily. ML-DSA: 1. SigGen -- Total fail at the moment both AFT and GDT, reversing or not reversing the message. 2. SigVer -- I can obtain passes if I reverse the message. 3. KeyGen -- I can obtain passes if I reverse the seed. I have not needed to reverse the outputs, pk,sk or signature, I did not dig too far into SigGen failures at this point because of this issue. I have not attempted to implement any testing for ML-KEM beyond fetching vectors. Probably off topic, with KeyGen, we had an error report on one set of vectors about a PK and SK not being related but it is intermittent, I have held of looking into that as well. (I have these vectors saved) Please let me know if you need any more information? MW — Reply to this email directly, view it on GitHub <#320 (comment)>, or unsubscribe </~https://github.com/notifications/unsubscribe-auth/AATQXEJBEP7FOSJY2NSDRTDY4RWQNAVCNFSM6AAAAABF3Z6DO6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDANBWGE3DMNZRHA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[mwcw]

I got 100% failure, AFT, GDT SigGen with:

1. With our without reversed message
2. All runs with reversed signature bytes.

Not tried:
Reversing pk in GDP results.

With GDP we are "non deterministic" and we are generating a key pair using a random entropy source.

[smuellerDD]

Allow me to add my observations:

ML-DSA:

• keygen, sigver: all pass with the bit flip above
• siggen: AFT passes, GDT fails (partially also due to issue ML-DSA: Siggen GDT: rnd value missing? #322 I guess)

ML-KEM:

• Keygen: pass without the bit flip
• Encap: pass
• Decap: pass without the bit flip (except the issue ML-KEM decap: some test vectors fail #323)

[celic]

I see. This is concerning the BitArray from BitString conversion used for the message in ML-DSA SigGen and SigVer, and the seed for ML-DSA KeyGen. All that is needed is the final BitString that we use in the JSON needs the byte order reversed.

[livebe01]

The fix for this issue is on Demo as of this afternoon's v1.1.0.34 hotfix deployment.