Hunting season is open (for submissions to the NIST post-quantum project). After our PhD student Lorenz Panny already broke “Guess Again” within three hours, the next hit took a moment. Actually, it didn’t. We (Lorenz, Tanja Lange, Daniel J. Bernstein and me) already found three vulnerabilities in RaCoSS within one hour. Only problem: One of them was a low complexity second-preimage attack against the internal hash function. Low complexity means about 2^31 hashes and the input consists not only of the message but also a 2400 bit vector and the serialization of a 2400 x 340 binary matrix. This took the night to finish and we wanted to demonstrate the attack before publishing. Also, everyone was on their way to spent the holidays somewhere, so coordination was a mess (Deutsche Bahn and Wifi…. grrr). But now the attack is online.

Briefly, we first found an implementation flaw that made the first KAT signature a valid signature for about 65% of the messages we tried. The problem was essentially using a byte array to represent a bit string, using one byte per bit but using the length of a classical byte representation of the bit string (8 bits per byte).

This happened when we were trying to exploit the low-complexity second-preimage attack. The latter exists as RaCoSS maps messages — together with some other stuff — to 2400 bit strings of weight 3. Problem: The image of this function only has ~2^31 elements. Kind of small for the cryptographic setting.

At this point we started to look closer and Tanja observed that one can actually comparatively easy compute valid signatures just given the public key. Sadly it seems really hard to fix this as a straight forward fix would work towards making the second-preimage attack even easier. Hence, it seems as if a fix would have to solve this connection between the two attacks.