EHTv3 and EHTv4 Response to Posted Attacks
Martin Feussner
Dear all,
The EHT team would like to let everyone know that we have now updated our scheme/submission with countermeasures against the two attacks posted on the PQC-forum in July. These countermeasures were already mentioned at the Oxford PQC workshop in September. It took us some time to research around those attacks. We have also invested time in revamping the implementation to enhance its readability. The updated submission package is now accessible here.
Below, we briefly describe the attacks and
the countermeasures now implemented. The
detailed explanation is in the submission package.
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
[Attack 1] Eamonn Postlethwaite and Wessel van Woerden (Posted here)
Given public key A and a hash value vector h, the attack finds x₁ and e₁ such that e₁ = h - Ax₁ modulo q and maxₗ(e₁) ≤ s. The signature x₁ for h may be forged by solving the underlying CVP with BKZ reduction and Babai nearest plane algorithm for a lattice generated by the columns of A modulo q. They were able to break the posted 80-bit security challenge.
Countermeasure: We remark that e = Cz = h - Ax modulo q generated by the signature algorithm and e₁ = h - Ax₁ modulo q from the attack are distributed differently. So, one takes a real-valued distinguisher f and bounds s₁ and s₂ and introduces an additional signature generation and verification rule: s₁ ≤ f(e) ≤ s₂ . This holds with high probability with regular e. We sampled over 5.7×10⁵ such e₁ from which none pass verification with f. In fact, they are still very far. The estimated probability for e₁ to pass in around 2⁻⁶⁴ for the challenge, that is within 80-bit security. We have chosen s₁ and s₂ for every parameter set of EHTv3 and EHTv4 similarly.
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
[Attack 2] Keegan Ryan and Adam Suhl (Posted here)
Hidden Zonotope Problem (HZP) attack recovers some columns of the secret key matrix C from observing e = Cz, where z is distributed uniformly. 5×10⁵ signatures were enough to break EHTv3-level-1 and similar has been verified by us for EHTv4-level-1.
Countermeasure: As C is rectangular, we may provide that a significant portion z' of z has the distribution of our choice. For instance, z' is half of the entries of z for EHTv4. The entries of z' were made dependent and non-uniformly distributed by using the multinomial distribution. This seems to undermine the theoretical foundations of the HZP attack as it is described by Ducas and Nguyen in [1]. Also, we have slightly redefined the construction of C. With 5×10⁶ signatures, no information of matrix C was leaked by the HZP attack.
[1] L. Ducas, P. Q. Nguyen, Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures, in Asiacrypt 2012, LNCS, vol. 7658, pp. 433-450, Springer, 2012.
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
We highly appreciate the contributions of the authors of these attacks. The simple countermeasures mentioned above affect neither the size of the signature, nor the size of the public key, the effect on the algorithm efficiency is negligible.
Best regards,
Martin Feussner and Igor Semaev