Unexpected zero bits in SHAKE-128 VOT test output

[dspdon]

I'm seeing a possible problem in some message digest ("md") result strings recorded in SHAKE-128 ACVP test vector files. The problem appears in most of the VOT test cases (test group 3).

One of the test files is here: gen-val/json-files/SHAKE-128-1.0/internalProjection.json

In the VOT test cases, the last byte of md has unexpected, message-independent zero-value bits in the right-most N bit positions (LSbits), where N is from 1 to 4 bits. Specifically, N = min(8-R,R) where R = mdlen % 8. Only cases where R > 0 have these unexpected zero-bits, i.e., cases where mdlen is not a multiple of 8 bits. This implicates 453 of 512 VOT test cases. These unexpected zero-bits are in addition to the zero-bits that are expected in the left-most 8-R bit positions (MSbits) of the last byte when R > 0, which are normal zero-padding up to a full byte.

Aside from these 1 to 4 unexpected zero bits, all other bits in the md vector for these VOT test cases match the output of a test implementation I am using for SHAKE-128. Also, all other non-VOT test cases in the file match the output of that same test implementation. I suspect a bug in the generator code when computing the last byte of md in test group 3 when R > 0.

Example: tcId 1394 (the first VOT test case with R > 0) mdlen = 3381 R = mdlen % 8 = 5 N = min(8-R,R) = 3, the # of unexpected bits overwritten with 0 In the ACVP file, the last byte of md is 0x18 = b'00011000' You can see the right-most 3 LSbits are 0 (The left-most 3 MSbits are also 0, which is normal zero-padding to a full byte) An IUT gives 0x1F = b'00011111' for the last byte

I repeated the above to verify that N right-most zero-bits appear in the last byte of all 453 VOT test cases when R > 0, in addition to the expected 8-R left-most zero bits for padding.

[dspdon]

A possible cause could be that ACVP is under-requesting output bits from KECCAK by a number equal to N, hence those bits remain "stuck at 0" in ACVP md results. Another guess is errant zero-padding when packing the bit string into hex digits. Of course, the simplest explanation is ACVP is fine and I have incorrect bit counts on my end.

Debug info follows for the SHAKE128 ACVP file, showing one line for each VOT tcId (first 20 cases). Bits for the last byte of md are shown for the ACVP reference result and for an IUT. The 0-based index of the last byte of md is in brackets. You can see the 0-valued LSbits in the mdACVP result and "presumptively correct" bits from an IUT. The number of stuck-at-0 bits is noted.

ACVP SHAKE128 tgId=3 tcId 1393: mdlen=1634, mdACVP[ 204]=00000000, mdIUT[ 204]=00000000 <- 1634%8=2, N=2 LSbits stuck-at-0 tcId 1394: mdlen=3381, mdACVP[ 422]=00011000, mdIUT[ 422]=00011111 <- 3381%8=5, N=3 LSbits stuck-at-0 tcId 1395: mdlen=1505, mdACVP[ 188]=00000000, mdIUT[ 188]=00000001 <- 1505%8=1, N=1 LSbits stuck-at-0 tcId 1396: mdlen=2389, mdACVP[ 298]=00011000, mdIUT[ 298]=00011011 <- 2389%8=5, N=3 LSbits stuck-at-0 tcId 1397: mdlen=1660, mdACVP[ 207]=00000000, mdIUT[ 207]=00001101 <- 1660%8=4, N=4 LSbits stuck-at-0 tcId 1398: mdlen=3122, mdACVP[ 390]=00000000, mdIUT[ 390]=00000000 <- 3122%8=2, N=2 LSbits stuck-at-0 tcId 1399: mdlen=3690, mdACVP[ 461]=00000000, mdIUT[ 461]=00000011 <- 3690%8=2, N=2 LSbits stuck-at-0 tcId 1400: mdlen=0585, mdACVP[ 73]=00000000, mdIUT[ 73]=00000001 <- 585%8=1, N=1 LSbits stuck-at-0 tcId 1401: mdlen=1433, mdACVP[ 179]=00000000, mdIUT[ 179]=00000000 <- 1433%8=1, N=1 LSbits stuck-at-0 tcId 1402: mdlen=3678, mdACVP[ 459]=00001100, mdIUT[ 459]=00001110 <- 3678%8=6, N=2 LSbits stuck-at-0 tcId 1403: mdlen=1915, mdACVP[ 239]=00000000, mdIUT[ 239]=00000110 <- 1915%8=3, N=3 LSbits stuck-at-0 tcId 1404: mdlen=3949, mdACVP[ 493]=00001000, mdIUT[ 493]=00001111 <- 3949%8=5, N=3 LSbits stuck-at-0 tcId 1405: mdlen=1752, mdACVP[ 218]=10011001, mdIUT[ 218]=10011001 <- 1752%8=0 tcId 1406: mdlen=1578, mdACVP[ 197]=00000000, mdIUT[ 197]=00000011 <- 1578%8=2, N=2 LSbits stuck-at-0 tcId 1407: mdlen=0177, mdACVP[ 22]=00000000, mdIUT[ 22]=00000000 <- 177%8=1, N=1 LSbits stuck-at-0 tcId 1408: mdlen=1027, mdACVP[ 128]=00000000, mdIUT[ 128]=00000011 <- 1027%8=3, N=3 LSbits stuck-at-0 tcId 1409: mdlen=2771, mdACVP[ 346]=00000000, mdIUT[ 346]=00000100 <- 2771%8=3, N=3 LSbits stuck-at-0 tcId 1410: mdlen=1110, mdACVP[ 138]=00101100, mdIUT[ 138]=00101101 <- 1110%8=6, N=2 LSbits stuck-at-0 tcId 1411: mdlen=0784, mdACVP[ 97]=11101100, mdIUT[ 97]=11101100 <- 784%8=0 tcId 1412: mdlen=1989, mdACVP[ 248]=00001000, mdIUT[ 248]=00001100 <- 1989%8=5, N=3 LSbits stuck-at-0

[livebe01]

Hi @dspdon, thanks for mentioning this. It's certainly possible that a bug has been introduced into the SHAKE VOT tests. I wonder if others have been running into this as well.

Can you try using the sample files from an older release to see if you're getting the same results? Try these: v1.1.0.27

[dspdon]

I ran the same test script on the v1.1.0.27 file you pointed out. It contains different test case data, but shows the same issue. I mentioned the current test file has 453 non-byte-oriented tests out of 512 VOT test cases, and those 453 test cases all have stuck-at-zero result bits. The v1.1.0.27 version has 446 non-byte-oriented tests out of 512 VOT test cases, and those 446 test cases all have the same stuck-at-zero bits in the same predictable bit locations.

A couple lines of code predicts where zeros are located within the specified digest bit-length, meaning a 128-bit digest is only as strong as 124 to 127 bits (for non-byte-oriented input messages). I test that all of those bits are ALWAYS zero in all non-byte-oriented VOT test cases. Unfortunately, I don't use ACVP source code so I won't be helpful in identifying a potential cause.

In a separate issue I opened, I requested a SHAKE256 test file be added to the json file folder. If you do that, I will assess whether this issue exists there as well.

[livebe01]

Thanks for doing that @dspdon. @jbrock24 is looking into this and will get back with you when he has more to share.

[livebe01]

Hi @dspdon, thanks for sticking with us on this one. We think we've identified the issue.

Can you try running the linked updated tests to confirm that we've resolved the issue?

registration.json prompt.json internalProjection.json expectedResults.json validation.json

[dspdon]

Yes, these updated files look good: no stuck-bits in internalProjection.json, and I confirm a match to my IUT for all cases within AFT and VOT test groups. Nice job on this.

FWIW, I also had to correct an issue on my end, where I failed to left-align output bits within the last byte for these non-byte oriented cases. With that correction, your new files match.

[dspdon]

Do you believe your update to SHAKE will affect cSHAKE and KMAC validation results for the similar case of non-byte oriented outputs?

[dspdon]

Returning to the output bit alignment issue, I could use confirmation that your intent is to shift the least-significant bits of "partial bytes" into the most-significant bits of the last byte in the digest hex strings. This difference caused me to make the correction I mentioned earlier.

Other older bit-oriented validation files from NIST retain their trailing bits in the LEAST-significant bits of the last byte. The validation files you posted here shift those trailing bits into the MOST-significant bits of the last byte.

Just to quickly compare, here is a page with NIST pre-ACVP validation files (SHAVS?): Examples with intermediate values

Specfically, the bit-oriented tests for SHAKE are at this link: "Samples to illustrate SHAKE128 for output bit lengths that are not divisible by 8."

All of those digests show the final bits are retained in the least-significant bits of the final byte. It's possible to see that in the file, since the validation tests decrease by 1 bit with each successive test case, and you can see the final byte value is getting truncated one MSbit at a time.

[livebe01]

Do you believe your update to SHAKE will affect cSHAKE and KMAC validation results for the similar case of non-byte oriented outputs?

The change we made shouldn't effect cSHAKE and KMAC.

[livebe01]

Returning to the output bit alignment issue, I could use confirmation that your intent is to shift the least-significant bits of "partial bytes" into the most-significant bits of the last byte in the digest hex strings. This difference caused me to make the correction I mentioned earlier.

Other older bit-oriented validation files from NIST retain their trailing bits in the LEAST-significant bits of the last byte. The validation files you posted here shift those trailing bits into the MOST-significant bits of the last byte.

Just to quickly compare, here is a page with NIST pre-ACVP validation files (SHAVS?): Examples with intermediate values

Specfically, the bit-oriented tests for SHAKE are at this link: "Samples to illustrate SHAKE128 for output bit lengths that are not divisible by 8."

All of those digests show the final bits are retained in the least-significant bits of the final byte. It's possible to see that in the file, since the validation tests decrease by 1 bit with each successive test case, and you can see the final byte value is getting truncated one MSbit at a time.

Hi @dspdon, I'm going to need to take a closer look at this. We were surprised to see that we had an issue in the VOT testing as we didn't think it had really changed since it was first written. But when we looked, it doesn't look like anyone has actually tested SHAKE with outbit=true before :).

[livebe01]

Do you believe your update to SHAKE will affect cSHAKE and KMAC validation results for the similar case of non-byte oriented outputs?

The change we made shouldn't effect cSHAKE and KMAC.

Have you had any issues testing cSHAKE and KMAC?

[dspdon]

I confirm cSHAKE test vectors use MSbit alignment of any trailing ( < 8 ) bits within the last byte, which is consistent with the (repaired) SHAKE validation files. My cSHAKE IUT also suggests those test vectors are correct. ;-) So all seems good here.

But just to note that this is a change from the SHAVS SHAKE validation file (URL provided above). That test file has LSbit-aligned trailing bits, which is NOT the same as what you now have (or will soon have) in the ACVP SHAKE validation file. Once you confirm the issue in the SHAVS test file, consider adding a short note on that legacy NIST page that indicates the LSbit alignment. That takes work/discovery to deduce. I wouldn't change that old file however due to potential downstream impact.

I haven't re-checked KMAC but intend to do so shortly.

[dspdon]

To wrap up on SHAKE, if you produce a SHAKE256 json file, I'd be happy to test with that. Your fix for SHAKE128 may be needed for SHAKE256.

For cSHAKE, as I mentioned above, you seem to be all set.

Finally, I plan to move KMAC discussion to a new Issue. In a nutshell, all KMAC byte-oriented test cases in ACVP pass with my IUT, but I have never passed KMAC bit-oriented test cases in ACVP. I was waiting for resolution of the SHAKE128 issue to see if it may have impacted the message digests you recorded for KMAC. You've confirmed the fixes to SHAKE do not affect KMAC results. Therefore the issue I see persists, and seems distinct. And of course, the issue is likely to be on my end. My conclusion is that I will open a new Issue for KMAC bitstreams once I get more concrete data.

[davyrouillard]

Returning to the output bit alignment issue, I could use confirmation that your intent is to shift the least-significant bits of "partial bytes" into the most-significant bits of the last byte in the digest hex strings. This difference caused me to make the correction I mentioned earlier.

Other older bit-oriented validation files from NIST retain their trailing bits in the LEAST-significant bits of the last byte. The validation files you posted here shift those trailing bits into the MOST-significant bits of the last byte.

Just to quickly compare, here is a page with NIST pre-ACVP validation files (SHAVS?): Examples with intermediate values

Specfically, the bit-oriented tests for SHAKE are at this link: "Samples to illustrate SHAKE128 for output bit lengths that are not divisible by 8."

All of those digests show the final bits are retained in the least-significant bits of the final byte. It's possible to see that in the file, since the validation tests decrease by 1 bit with each successive test case, and you can see the final byte value is getting truncated one MSbit at a time.

One of our clients is facing the same problem. The standard FIPS-202 appendix B refers to https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values. On this page, we can see a link to 'Samples to illustrate SHAKE128 for output bit lengths that are not divisible by 8.' This is the document pointed out by @dspdon above.
Theferfore, I tend to agree with @dspdon that there is an issue in the CAVP implementation. Could you provide us with an approximate date by which you will be able to get back to us on this point (correction or precise specification)?

[livebe01]

Hi @davyrouillard, @dspdon, we do apologize for not being able to give this attention sooner. This task as well as the related https://github.com/usnistgov/ACVP-Server/issues/352 issue are assigned to @jbrock24 and he should be getting freed up to look at these sometime this week.

Our thought is that 1) the CAVP implementation is likely incorrect and 2) that the CAVP implementation should match https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values.

-Ben

[davyrouillard]

Hello @livebe01, Could you please provide an update on the progress of the fix? Thank You Davy

[livebe01]

Sure. Our plan is to have a fix for this issue included in our next release, v1.1.0.38. We'd like to have the v1.1.0.38 release on Demo before Thanksgiving.