Hi,
It looks like the verification algorithm of HPPC accepts if F(signature,public key) = Hash(message), for some function F, and for some hash function with only 128,192, or 256 bits of output for security levels 1,3,or 5 respectively.
This means that one can do a chosen-message attack with roughly 2^64, 2^96 or 2^128 of work by finding a collision for H, or one can do a key-only universal forgery attack with roughly the same amount of work by finding claws between F and H.
Ward
Dear all,
We would like to report weaknesses in the polynomial system underlying HPPC.
This system was assumed to behave as a semi-regular one over GF(2) in the specification. However, our MAGMA experiments show a rather different behavior. More precisely, we observe 2n degree fall polynomials from degree 3 to degree 2 regardless of the value of d.
We believe that they are caused by the central map having 2-rank 2. This map is given by a univariate polynomial F(X) = l_1(X) \times l_2(l_1(X)), where l_1 and l_2 are linearized permutation polynomials. The number of degree falls may come from the fact that for the linearized polynomials A = l_1 and B = l_2 ° l_1, A*F and B*F have 2-rank 2. The conclusion follows from the same standard arguments as in [1], Equation (5).
The presence of degree falls at degree 3 does not necessarily mark the end of the Gröbner basis computation but it does show a weakness in the scheme:
- For instance, there could be the possibility of stopping the algorithm at this step and then exploiting these polynomials in a more astute way (this was for example the case in [1]).
- This may also pave the way for practical MinRank attacks. In addition to the Minors modeling mentioned in the specification, we can think of applying methods similar to the one against GeMSS in [2] (with target rank 2). More precisely, for the category 5 parameters, if we use b=1, the first step should involve solving (5 choose 3)*256 linear equations in (5 choose 2)*256 variables (concretely this should cost something like (2560)^2.8 = 2^32 bit operations). For the GeMSS parameters attacked in [2], the first step was always the most expensive, but even if the second step turns out to be the most expensive step, we are confident this attack will still be practical.
Please find attached our MAGMA code and two traces of its execution on n=30 and n=50 parameters where d=10 (note that d=10 and n=128 corresponds to security level I).
Sincerely,
Pierre Briaud, Maxime Bros, and Ray Perlner
[1] https://eprint.iacr.org/2020/1442.pdf
[2] https://eprint.iacr.org/2021/1677.pdf
(apologies if this is a double post. We tried posting through the website but it didn’t work immediately.)