Battle Report (first 30 hours, Add'l Sigs Round 1)
Daniel Apon
Here's a synopsis of the first 30 hours of (claimed) analysis of the On-Ramp Signature submissions (Round 1):
https://i.imgur.com/F1Xdg8I.png
Cheers,
--Daniel
Daniel Apon
Apologies for Comic Sans font on the header
--
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+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/ed621b8f-10bc-4259-8e46-b73298ba54cbn%40list.nist.gov.
wa...@beullens.com
Hi Daniel, Markku, all
I think crossing ALTEQ off the list might be a bit harsh.
I believe the problem causing the attack is that the scheme/security proof expects the D_i matrices in the signature to be invertible, but the implementation forgets to check this.
Algorithm 3 in the specification document says that the input to the verification algorithm contains matrices D_i \in GL(n,q), so one could argue that the problem is due to an input validation “bug”, rather than a flaw in the scheme itself. Checking that the D_i matrices are invertible should not be too expensive and it would solve the problem.
I’m not part of the ALTEQ or MEDS teams, just speaking for myself.
Ward
PS: As far as I can tell the MEDS submission suffers from the same bug and Markku’s attack also applies although it would not be practical because the MEDS parameters are different. In the ALTEQ case, there is a parameter set with (r choose k) = 120, so Markku gets a very efficient attack. In the case of MEDS, I believe the best attack is on MEDS-13220, where (t choose w) ~ 2^89.1. So it’s still very far from a practical attack. (And I won’t write a Python script to prove that the attack applies.)
PPS: I don’t want to downplay Markku’s attack. I think it’s impressive that he found this problem so quickly. I could imagine this problem going undetected for a much longer time.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CAPxHsSJoz9_hf%3DTU9b%3DegFoaAsuO9hwybSHq1vKLWrp_YsYKmA%40mail.gmail.com.