search

usnistgov / ACVP-Server

A repository tracking releases of NIST's ACVP server. See www.github.com/usnistgov/ACVP for the protocol.
51 stars 18 forks source link

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

Closed mwcw closed 5 months ago

mwcw commented 5 months ago

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

celic commented 5 months ago

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 commented 5 months ago

@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 ```c #include #include #include #include #include #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 commented 5 months ago

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 commented 5 months ago

Perfect, thank you @celic!

celic commented 5 months ago

This will also impact FIPS 203, ML-KEM.

celic commented 5 months ago

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 commented 5 months ago

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 commented 5 months ago

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 https://github.com/usnistgov/ACVP-Server/issues/320#issuecomment-2046166718, or unsubscribe https://github.com/notifications/unsubscribe-auth/AATQXEJBEP7FOSJY2NSDRTDY4RWQNAVCNFSM6AAAAABF3Z6DO6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDANBWGE3DMNZRHA . You are receiving this because you were mentioned.Message ID: @.***>

mwcw commented 5 months ago

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 commented 5 months ago

Allow me to add my observations:

ML-DSA:

ML-KEM:

celic commented 5 months ago

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 commented 5 months ago

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