Problem with keyGen validation for LMS with M=24

[kriskwiatkowski]

environment
Demo

testSessionId
N/A I've run ACVP server locally

vsId
N/A

Algorithm registration
LMS keyGen with M=24 (any hash function, Winternitz coefficient or tree level). The sigGen is also affected by this issue.

Endpoint in which the error is experienced
According to SP800-208 LMS can be used with digest size of 24 bytes. The ACVP implementation uses same parameters as in IETF draft draft-fluhrer-lms-more-parm-sets-10.

The SP800-208 requires that key generation process uses procedure described in RFC 8554, appendix A (see section 6.1 in SP800-208). The procedure for pseudo random key generation, described in RFC 8554 (app. A) requires the seed to be exactly M-byte long. Note a subtle difference between appendix A and procedure described in the section 5.2 of RFC 8554, where the latter requires seed to be "at least" m-bytes long.

Current implementation of LMS uses seed value that are not exactly equal to M. It seems to me that seed is always 32 bytes long.

For example, here tests are successfully passing even with 32-byte long seeds. And this check should check equality with lmOtsAttribute.N rather than checking if seed buffer is shorter.

Following test case was generated by ACVP-server (commit: 90d9d00).

Input:

{
  "vsId": 0,
  "algorithm": "LMS",
  "mode": "keyGen",
  "revision": "1.0",
  "isSample": true,
  "testGroups": [
    {
      "tgId": 1,
      "testType": "AFT",
      "lmsMode": "LMS_SHAKE_M24_H5",
      "lmOtsMode": "LMOTS_SHAKE_N24_W1",
      "tests": [
        {
          "tcId": 1,
          "seed": "16B60A793A6401BF5C691ECD261019E2EE2527728A70A0A4458E51940E952553", <--- 32 bytes
          "i": "1D9993F4670B187D0612123A4570E86E"
        }
      ]
    }
  ]
}

Expected output:

{
  "vsId": 0,
  "algorithm": "LMS",
  "mode": "keyGen",
  "revision": "1.0",
  "isSample": true,
  "testGroups": [
    {
      "tgId": 1,
      "tests": [
        {
          "tcId": 1,
          "publicKey": "000000140000000D1D9993F4670B187D0612123A4570E86E2D16404856857CC4C2E2BB39B2BC5EEF0C76C942D0DAD3B4"
        },

Expected behavior
This problem affects testing of public key generation. The length of seed should be exactly 24 bytes, as per Appendix A of RFC 8554.

Additional context
To be honest, I couldn't find a root cause of this issue. It seems that CalculateNewSeedIdFromExisting calculates seeds that have lenght of lmOtsAttribute.N, so the root cause should be somewhere before this function is called.

[celic]

Interesting. Thanks for the report. I think I found the issue... See https://github.com/usnistgov/ACVP-Server/tree/master/gen-val/src/crypto/src/NIST.CVP.ACVTS.Libraries.Crypto.Common/Asymmetric/LMS/Native/Helpers/AttributesHelper.cs#L253 (and the following function on L296). There's even a helpful TODO on a known issue that made it through to production... I can explain why this happened but I'm still embarrassed that it did.

[celic]

I think as a result this probably applies to both M24 LMS and N24 LMOTS trees, though by requirement in SP 800-208, they must be used together.

[celic]

Sorry. What I mentioned previously is a separate issue that is actually resolved internally but could be cleaned up as indicated by the TODO.

The real issue here is the bound check you mentioned in conjunction with this line: https://github.com/usnistgov/ACVP-Server/blob/master/gen-val/src/orleans/src/NIST.CVP.ACVTS.Libraries.Orleans.Grains/Lms/OracleObserverLmsKeyCaseGrain.cs#L38. That one is on me. I hardcoded the seed at 256 bits instead of looking at M. We'll get this fixed. There are two elements to the fix. The first is that we precompute all of our LMS trees in Demo and Prod because of the time involved in tree generation. These trees all use a 32-byte seed. We will remove the incorrect seed length trees and work on generating new ones to put in the Demo and Prod environments. We will also fix the code that spawned this and the bound check. The code deployment may take a while as it'll get grouped into our usual deployment cycle. Because we never actually call the LMS tree generation routines in a deployed environment, we can fix it there first. This isn't something you see in the code we released on GitHub. We use a different Oracle.cs concrete than the one provided here to use our database of precomputed values (think RSA keys, etc.).

Sorry, this is a bit confusing to explain. The tl;dr is we'll get this fixed, you'll notice it first in Demo/Prod before noticing it in the code.

[kriskwiatkowski]

Thanks Chris!
Indeed, hardcoded seed at 256 bits seems to be a root cause. I didn't notice that when looking at the code.
I'm running the ACVP-server locally for some testing, so I'm happy to double check generated vectors against my implementation once fix is done.

Thank you a lot for this analysis.

[celic]

I believe the algorithm implementation is still fully correct, despite the files we looked at. I believe the only issue is that hard coded 256 value, and as a result, all of our precomputed M24 trees. A lot of our "tests" are self-referential and not very useful as "tests". They exist to help ensure consistency rather than correctness because we used our own implementation to generate the tests.

Thanks again for the discussion. I'm happy to hear someone is digging through our code, and has success running it all.

[kriskwiatkowski]

I agree, implementation seems to be correct and done in accordance with both RFC 8554 and draft-fluhrer-lms-more-parm-sets-10.

FYI: I've alternative implementation that we plan to push thru FIPS at some point. I did interoperability testing between ACVP-Server and mine implementation and both look to work between each other just fine (for keyGen, sigGen and sigVer), at least for M=32.

[livebe01]

Hi @kriskwiatkowski, an fyi that while we will get the code we post to https://github.com/usnistgov/ACVP-Server updated, in the meantime you can access/get trees that have been computed with the proper seed lengths via the ACVTS Demo server.

[celic]

Or just change the line to this in the code you are using...

In https://github.com/usnistgov/ACVP-Server/blob/master/gen-val/src/orleans/src/NIST.CVP.ACVTS.Libraries.Orleans.Grains/Lms/OracleObserverLmsKeyCaseGrain.cs#L38
var seed = _entropyProvider.GetEntropy(AttributesHelper.GetLmsAttribute(_param.LmsMode).M * 8);

This may require the addition of using NIST.CVP.ACVTS.Libraries.Crypto.Common.Asymmetric.LMS.Native.Helpers; to grab that function.

[kriskwiatkowski]

Thanks. Makes sense, I'll go ahead with changing the code then.

[livebe01]

The fix for this is now available in release v1.1.0.31.