Subject: [pqc-forum] OFFICIAL COMMENT: RaCoSS From: "A. Huelsing" Reply-To: authorcontact-racoss@box.cr.yp.to Date: Sat, 23 Dec 2017 15:15:48 +0100 To: pqc-comments@nist.gov Cc: pqc-forum@list.nist.gov, authorcontact-racoss@box.cr.yp.to Message-ID: User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.5.0 Dear designers, dear all, The low-weight hash function used in RaCoSS is not secure. Please see below for a message colliding with the first KAT message when hashed together with the data used in RaCoSS, hence the signature of the first KAT is also a signature for this second-preimage. This does not use the implementation flaw we observed before. It exploits the fact that the size of the image of the wrhf hash function is small, thus (second-)preimages can easily be found by brute force. The message we found is (without quotes): "NISTPQC is so much fun! 10900qmmP" To check this, replace the original message of the first KAT by this message and leave the rest of the signed message (sm) unchanged; it will still verify for the same public key. The hash function wrhf takes as input a message m, the desired weight w, and a length n and outputs a string c of length n having exactly w non-zero entries. The internals of wrhf do not matter, only the size of the range of wrhf is relevant. For the proposed parameters n=2400, w=3 there are only (2400 choose 3) = 2301120800 ~ 2^31.09 possible outputs. This means that a (second-)preimage can be found in roughly 2^31 runs of wrhf, allowing for a forgery under random message attacks. The hash function is relatively slow, but the above preimage attack was done overnight. It is also possible to select a particular message by varying other parts of the hash input. Chosen message attacks are even faster. A collision can be found in 2^15.5 runs of wrhf. Regards Andreas, Dan, Lorenz, and Tanja ----------- Andreas Huelsing, Daniel J. Bernstein, Lorenz Panny, Tanja Lange -- You received this message because you are subscribed to the Google Groups "pqc-forum" group. To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov. Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.