Subject: [pqc-forum] OFFICIAL COMMENT: RaCoSS From: Tanja Lange Reply-To: authorcontact-racoss@box.cr.yp.to Date: Sat, 23 Dec 2017 15:16:01 +0100 To: pqc-comments@nist.gov Cc: pqc-forum@list.nist.gov Message-ID: <20171223141601.GF29571@ein.win.tue.nl> Dear designers, dear all, We have identified a serious flaw in the design of RaCoSS and can quickly sign any message for any public key with the specified RaCoSS parameters, without knowing the secret key. Here is the setup. The system uses a public, shared matrix H which is a 340x2400 low-weight binary matrix. The secret key is a low-weight 2400x2400 matrix S^t. The public key is H*S^t. The signer picks a random, low-weight 2400-bit vector y; computes v = H * y; computes a hash function on v, m, and H to get a low-weight 2400-bit vector c; and computes z = S^t * c + y. The signature on m is the pair (z,c), where z has 2400 bits and c has 2400 bits and only very few non-zero entries. The verifier checks that z has not too large weight. If so the verifier computes v1 = H * z, v2 = T * c, v = v1 + v2 and verifies that c matches the output of the hash function on v, m, and H. This works for a valid message because v2 = T * c = H * S^t * c and v1 = H * z = H * (S^t * c + y) = H * S^t * c + H * y = v2 + v. Here is the attack. The attacker takes a subset of 340 linearly independent columns of H. Note that any set has about a 29% chance of being invertible, and there are (2400 choose 340) subsets to choose from. For ease of exposition assume that H = (H1 | H2) with H1 an invertible 340x340 matrix; this is true for the particular matrix H used in the RaCoSS reference software. To forge a signature on a message m, follow the steps as above up to the computation of c. Then compute z1 = H1^(-1) * (H * y + T * c), a 340 bit vector, and put z = (z1|00...0) to fill up to 2400 bits. This vector z passes all the computational checks. Each entry of z1 is 1 with probability 1/2, so verification of the weight restriction works if 170 errors are allowed. If the bound is more restrictive, the attacker can try with other splits of H. However, for functionality reasons the bound cannot be much smaller than this, because a properly generated vector z is likely to have weight at least this large. Note: Computing H1^(-1) is a one-time effort that works for _all_ public keys. The costs for the forgery are essentially the same as the costs for a regular signature; the only additional operation is the multiplication by the 340x340 matrix H1^(-1). See https://helaas.org/racoss-20171222.tar.gz for an implementation of the attack. 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/.