DSA Broken: Troubleshooting

[mcp292]

Hello, I tried troubleshooting this library. I was attracted by how readable and well commented it is, but it seems there might be deeper problems with this implementation that I do not have time to inspect. Here are my findings to get the ball rolling:

Casting a uint8_t array to a uint32_t is dangerous, as it is affected by the underlying architecture's endianness. When you bit shift, the shift is abstracting the hardware's endianness and treating everything as big endian. So the safest procedure is to either copy to a uint32_t array via bitshifts, or to define it as such in the first place. The other option is to only use byte arrays of uint8_t. I didn't see a good reason to go for the uint32_t.

There may be unexpected behavior caused by bitvec_clr_bits(). If the range you are clearing over is not less than 32 or a multiple of 32, you will have some uncleared bits floating in the middle of the cleared range. It would be safer to clear strictly in one direction as opposed to starting at the LSB of each byte. (Clever use of & 31U as a mod 32 (consider commenting).)

In step 2 of the signing, you are not taking the leftmost bits. You are actually blanking the MS (most significant) bits with use of bitvec_clr_bits() incrementing over a range. It can be said that you're modding the natural number represented by the entire hash. This may cause variation when testing results against other libraries. Maybe you could use bitvec_clr_bits() as is, but decrement over a range starting at the LSB; then you'd be blanking right to left.

I would check the conditional operations in the Galois field arithmetic. There are places where you say, if this is zero then it's the equivalent of the addition of that, etc.. I would check all to be safe actually.

I would also consider not defining the bitvec with a size (see this post). More importantly though, it makes the copy calls unclear to the reader. How do we know we are copying the right ranges? I do see the value in the sizes updating automatically, but it wouldn't hurt to just pass these #defined values as parameters.