Unexpected zero bits in SHAKE-128 VOT test output #347
Comments
|
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 |
|
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. |
|
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 |
|
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. |
|
Do you believe your update to SHAKE will affect cSHAKE and KMAC validation results for the similar case of non-byte oriented outputs? |
|
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?): Specfically, the bit-oriented tests for SHAKE are at this link: 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. |
The change we made shouldn't effect cSHAKE and KMAC. |
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 :). |
Have you had any issues testing cSHAKE and KMAC? |
|
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. |
|
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. |
One of our clients is facing the same problem. |
|
Hi @davyrouillard, @dspdon, we do apologize for not being able to give this attention sooner. This task as well as the related #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 |
|
Hello @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. |
|
Hi guys, a belated happy new year to you! Any update on the fix for this issue? |
|
Thank you! Yes, we believe we have this fixed. But we're still hashing out #352. I assume that both this issue and #352 are preventing you from testing particular algorithm implementations. We could possibly get the SHAKE fix out before the KMAC one. Would there be any advantage to that for you? I.e., Would the KMAC issue still block you from moving forward? |
|
Yes, I would benefit from an update just to SHAKE, with a future update to KMAC coming later. |
|
Great, the fix for this issue is ready. It will be included in our next Demo deployment. It missed the v1.1.0.38 release that went to Demo on Tuesday, but if we need to do a hotfix for v1.1.0.38 we'll include it in that. |
|
Attached are SHAKE-128 and SHAKE-256 test vectors that were produced using our updated testing. Feel free to run the tests through your implementation to confirm that we're getting the same results. |
|
Thanks guys - just downloading and testing these now. |
|
Great, thanks for doing that @dspdon. We needed to put together a hotfix for the ACVTS v1.1.0.38 release and it was pretty simple to add this to it. The fix for this should be available on Demo by the end of tomorrow. |
|
I see a problem in the last byte of all bit-oriented VOT test cases in your latest SHAKE128 dataset. I did not test SHAKE256 data set. I believe the spec we are after for bit-oriented bitstreams is to pack the final 1-7 bits into the MSbits of the last byte. Let's ensure we agree on this, as everything else we discuss relies on that --- do you agree? This is the primary problem in the SHAKE VOT test cases. The particulars of how that last byte had its bits scrambled in the SHAKE VOT test cases was the rest of the issue. In the new test file you posted, all VOT test cases fail and show this same issue once again. Starting with tcId 1393, "md" ends with 0x0B. It has length 3326, therefore rem(3326,8) is 6 so there should be 6 bits "used" and 2 bits "unused" - i.e., the two LSbits should be 0. However, the 2 LSbits of 0x0B are non-zero. There's the problem. It was a bit of luck that 0x0B happened to have those bits set, but it did, and you see those two 1-bits set in the LSbits for tcId 1393. Those LSbits should have been zeros if we are packing data into MSbits. A shift-left by 2 bits is needed to correct this problem. If we agree on the above, it seems you need to correct the last byte in all SHAKE128 VOT test cases by shifting bits left by "8-rem(outLen,8)" when rem(outLen,8) > 0. I made this temporary fix to the data from your latest file, and with that, all of your test cases match my IUT. |
|
I confirmed that the same problem exists in the new SHAKE256 data set. The last byte in all VOT test cases requires a left-shift by "8 - outLen % 8" when "outLen % 8 > 0." If I apply the appropriate left-shift, all of your new SHAKE256 test cases match my IUT. |
|
Hi @dspdon. Eck, I really thought we had this one worked out. Since this issue only effects the VOT cases where "outLen % 8 > 0" and we're pretty sure we were already doing those incorrectly, I think we'll still include these changes in the hotfix. Let me try to dig into this more and get back to you. |
|
Ok, timing is up to you of course. And you are so close ! Your final byte just has its bits aligned to the LSbits, instead of the MSbits. Shifting bits to occupy the MSbits should be as simple as: If you can add that conditional to the new code, you'd have a good chance of a correct result. ;-) |
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.
The text was updated successfully, but these errors were encountered: