search

usnistgov / ACVP-Server

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

> Note I did not validate if _all_ of the failures were due to the bounds check: #164

Closed angelshadow closed 2 years ago

angelshadow commented 2 years ago

Note I did not validate if all of the failures were due to the bounds check:

{
  "vsId": 559135,
  "disposition": "failed",
  "tests": [
    {
      "tcId": 1,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 2,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 3,
      "result": "passed"
    },
    {
      "tcId": 4,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 5,
      "result": "passed"
    },
    {
      "tcId": 6,
      "result": "passed"
    },
    {
      "tcId": 7,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 8,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 9,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 10,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 11,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 12,
      "result": "passed"
    },
    {
      "tcId": 13,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 14,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 15,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 16,
      "result": "passed"
    },
    {
      "tcId": 17,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 18,
      "result": "passed"
    },
    {
      "tcId": 19,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 20,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 21,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 22,
      "result": "passed"
    },
    {
      "tcId": 23,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 24,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 25,
      "result": "passed"
    },
    {
      "tcId": 26,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 27,
      "result": "passed"
    },
    {
      "tcId": 28,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 29,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 30,
      "result": "passed"
    },
    {
      "tcId": 31,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 32,
      "result": "passed"
    },
    {
      "tcId": 33,
      "result": "passed"
    },
    {
      "tcId": 34,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 35,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 36,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 37,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 38,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 39,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 40,
      "result": "passed"
    },
    {
      "tcId": 41,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 42,
      "result": "passed"
    },
    {
      "tcId": 43,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 44,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 45,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 46,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 47,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 48,
      "result": "passed"
    },
    {
      "tcId": 49,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 50,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 51,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 52,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 53,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 54,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 55,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 56,
      "result": "passed"
    },
    {
      "tcId": 57,
      "result": "passed"
    },
    {
      "tcId": 58,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 59,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 60,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 61,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 62,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 63,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 64,
      "result": "passed"
    },
    {
      "tcId": 65,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 66,
      "result": "passed"
    },
    {
      "tcId": 67,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 68,
      "result": "passed"
    },
    {
      "tcId": 69,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 70,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 71,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 72,
      "result": "failed",
      "reason": "Unable to resolve deferred crypto: Key is not a valid key"
    },
    {
      "tcId": 73,
      "result": "passed"
    },
    {
      "tcId": 74,
      "result": "passed"
    },
    {
      "tcId": 75,
      "result": "passed"
    }
  ]
}

I have the same issue that "reason": "Unable to resolve deferred crypto: Key is not a valid key". What does "bounds check" mean? And how should I fix it ?

Originally posted by @angelshadow in https://github.com/usnistgov/ACVP-Server/issues/108#issuecomment-999449462

Kritner commented 2 years ago

@angelshadow it's described in https://github.com/usnistgov/ACVP-Server/issues/108#issuecomment-845911377 in that same linked issue. The provided X value in the several test cases from that issue were below the acceptable values as specified in the algorithm highlighted in that comment.

I don't know if you've run into a similar issue or not, I would need a vector set ID, environment test case ID, and/or test case specifics to verify.

angelshadow commented 2 years ago

@angelshadow it's described in #108 (comment) in that same linked issue. The provided X value in the several test cases from that issue were below the acceptable values as specified in the algorithm highlighted in that comment.

I don't know if you've run into a similar issue or not, I would need a vector set ID, environment test case ID, and/or test case specifics to verify.

Not exactly the same test case. image The problem I encountered about this set of test cases is image I read the previous post, I think this problem is also because the leftmost 0 is not recognized. Can I modify the corresponding bitlens to solve the problem? image Regarding this set of test cases, the problem mentioned in the article was encountered, and it is not clear what the specific reason is and how to solve it？ image

attachment is my test results. Can you help me analyze it in detail and tell me how to solve it in order to pass the acvp server verification? Thank you very much.

824049.zip

Kritner commented 2 years ago

See https://github.com/usnistgov/ACVP-Server/issues/67 for some additional information around the MSB of the bitlength values.

Whatever values are provided/chosen that match the bitlengths chosen, the most significant bit must be a 1.

Just as a small example, if using the byte "1A", with a bitlength of 6, this would be invalid, as the 6th bit of 1A -> 0001 1010 is a 0. If that same "1A" were used with a bitlength of 5, it would be valid. The IUT just needs to ensure that whatever values are used for the bitlengths, that the MSB is 1.

regarding the other failures, like tcId 51 as an example:

var p = new BitString("4b2ff2aae3ce0e7d10598e248801183fdd3cbe6a43fe023ac12ddf163be6c553951a206898cb6a63572c671633493f3db0e95099c7bca05d55ddb9599a12e5fcfaa57b45b203399b7def946af10fdad61c954695aecaa345e6c45dc6e2836729b55085a61142991c1bc336a9ec7c0b3cd297384c83722b9c87183e6c0ec5e5eb")
  .ToPositiveBigInteger();
var q = new BitString("9de5d3ff1d55c8bf135853de094b9f9954b829c53e61642c5c7f52224c825274e698884b616fd2993f765cba9b6058be3fcb366a474626e522090b66783a8b0817be27ed71b5ac456b72fb300ed8c5f53dc34211e6f3ba529eb44764023be138faea21ad2dec9cb3ceb897633075097101afc246ff814afaec8d2b3bf9d12ed2")
  .ToPositiveBigInteger();

The above p and q both fail the miller rabin routine. The p fails within the first iteration due to check:

if (mod != n - 1 && temp.IsEven)
{
    return false;
}

Regarding q, since even values aren't prime q is immediately disqualified from being "probably prime".

angelshadow commented 2 years ago 
if (mod != n - 1 && temp.IsEven)
{
  return false;

What do variables in the check mean？

Kritner commented 2 years ago

We seem to have an "or equivalent" process for miller rabin, but the full algorithm can be found on FIPS186-4 in our case, it's a fall through of the checks of hitting step 4.6 naturally

mods initial value is that of the modPow operation, n is the number being checked for probably prime, temp is initially the value of n-1 shifted right until odd.

angelshadow commented 2 years ago

See #67 for some additional information around the MSB of the bitlength values.

Whatever values are provided/chosen that match the bitlengths chosen, the most significant bit must be a 1.

Just as a small example, if using the byte "1A", with a bitlength of 6, this would be invalid, as the 6th bit of 1A -> 0001 1010 is a 0. If that same "1A" were used with a bitlength of 5, it would be valid. The IUT just needs to ensure that whatever values are used for the bitlengths, that the MSB is 1.

regarding the other failures, like tcId 51 as an example:

var p = new BitString("4b2ff2aae3ce0e7d10598e248801183fdd3cbe6a43fe023ac12ddf163be6c553951a206898cb6a63572c671633493f3db0e95099c7bca05d55ddb9599a12e5fcfaa57b45b203399b7def946af10fdad61c954695aecaa345e6c45dc6e2836729b55085a61142991c1bc336a9ec7c0b3cd297384c83722b9c87183e6c0ec5e5eb")
  .ToPositiveBigInteger();
var q = new BitString("9de5d3ff1d55c8bf135853de094b9f9954b829c53e61642c5c7f52224c825274e698884b616fd2993f765cba9b6058be3fcb366a474626e522090b66783a8b0817be27ed71b5ac456b72fb300ed8c5f53dc34211e6f3ba529eb44764023be138faea21ad2dec9cb3ceb897633075097101afc246ff814afaec8d2b3bf9d12ed2")
  .ToPositiveBigInteger();

The above p and q both fail the miller rabin routine. The p fails within the first iteration due to check:

if (mod != n - 1 && temp.IsEven)
{
  return false;
}

Regarding q, since even values aren't prime q is immediately disqualified from being "probably prime".

How does the server interpret the results? Is it big endian or little endian? Look at the code screenshot, is it to call Java's BigInteger to perform a 32-bit group storage according to the big endian? For example if the real value is "4b2ff2aa e3ce0e7d", I need to output my value as "e3ce0e7d 4b2ff2aa"?

I think it may be the problem of the small-endian conversion that caused my result to fail to parse? Because the code did make the miller-rabin routine according to the specification？

Kritner commented 2 years ago

From https://pages.nist.gov/ACVP/draft-fussell-acvp-spec.html#name-endianness:

BitStrings SHALL be considered in big endian order, unless otherwise specified by the algorithm.

The hex string "FA" (assuming all bits are considered) SHALL represent the bits 11111010 (in MSb) or the value 250.

Aside from the question of endianness, I'm not sure I understand what's being asked, specifically around:

Look at the code screenshot, is it to call Java's BigInteger to perform a 32-bit group storage according to the big endian? For example if the real value is "4b2ff2aa e3ce0e7d", I need to output my value as "e3ce0e7d 4b2ff2aa"?

For something a bit more concrete in case this is what you're asking about...

BitString p:

4b2ff2aae3ce0e7d10598e248801183fdd3cbe6a43fe023ac12ddf163be6c553951a206898cb6a63572c671633493f3db0e95099c7bca05d55ddb9599a12e5fcfaa57b45b203399b7def946af10fdad61c954695aecaa345e6c45dc6e2836729b55085a61142991c1bc336a9ec7c0b3cd297384c83722b9c87183e6c0ec5e5eb

Represents the positive integer:

52798315179598227407391346092083765120081603165025769685880278074403001683024379882051281145671964756296831278192846359482148012361830723615409214322541037461970030176934060174609746371674705473863690766915819618680276582491807797155793927134033904981805702473853828729643332204349982596485303871490687886827

BitString q:

9de5d3ff1d55c8bf135853de094b9f9954b829c53e61642c5c7f52224c825274e698884b616fd2993f765cba9b6058be3fcb366a474626e522090b66783a8b0817be27ed71b5ac456b72fb300ed8c5f53dc34211e6f3ba529eb44764023be138faea21ad2dec9cb3ceb897633075097101afc246ff814afaec8d2b3bf9d12ed2

Represents the positive integer:

110879582053542540636594509928317482692196025190946564307500667340330281703435899999804495585268524749724090089152784244600995876131611290777589946233719878433132601845139979021422005610936240313053456661673149369616874115618224051769627618262427279555165806987156765815622475513941121576200008682990069690066

Conversion between bitstrings and integers (and vice versa) is documented in Appendix C.2 in https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

Kritner commented 2 years ago

This issue seems pretty stale, so I'm closing but feel free to bump/reopen if there's something outstanding.