CROSS broken sigs validate

[baentsch]

I’ve run the suggested test by @baentsch and noticed that the CROSS signature scheme seems to fail in some cases, passing the verification of modified signatures.

Tagging @rtjk.

Originally posted by @bhess in #1919 (comment)

[rtjk]

Thank you @baentsch @bhess. I'm looking into this. Am I understanding correctly: if a single byte of a valid signature is changed, CROSS may still accept the modified signature as valid in certain cases?

[bhess]

Hi @rtjk, this is correct, the issue occurred when incrementing a single random byte of the signature.

[rtjk]

The arrays that store nodes for the merkle tree and seed tree are fixed in size to a certain upper bound. However, they often end up with a bunch of empty (zero-padded) bytes at the end. It appears these zeros aren't checked during verification, so tampering with them results in a (wrongly) valid signature. Adding a check for these bytes should be straightforward, I’ll discuss this with the team and prepare a PR. Kudos to the liboqs test framework for catching this! By the way, this issue is somewhat related to #1958.

[baentsch]

Kudos to the liboqs test framework for catching this!

I'm afraid that wasn't so good -- but rather my stupid review question followed by diligent trialing by @bhess. I'd suggest you chime in to #1999 to help turn this into something really reliable.

[alexrow]

I can confirm what @rtjk said before: the mismatches are arising from the fact that a specific technique (seed trees and Merkle trees) allow to save some signature size but, in turn have a variable length signature. The savings in signature size
are there even when considering the largest possible among the variable lenghts.

To avoid the pains of handling an actual variable-length specification from an engineering standpoint (this is especially troublesome in hardware), in CROSS we're allocating the maximum signature size and zero-padding the unused bytes. We did not check that the padding bytes are actually set to zero (as they are not used in the signature verification process, but, it's a good idea to check them anyway (strictly speaking, it's an EUF-CMA violation, although I cannot see how an attacker can profit from this on the spot).

Thank you very much for the catch @baentsch @bhess !