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/.