Trivial multi-key attacks + attack on ALTEQ

[wa...@beullens.com]

Hi everyone,

 

Because of the recent messages on the forum, I had a look at PROV and I noticed KeyGen uses only 128 bits of randomness. It looks like this is also the case for MQOM, SDitH, and Alteq. (I’m not claiming this list is exhaustive.)

This allows for a generic attack, where one can recover the secret key for one out of X public keys, simply by running keygen roughly 2^128/X times until the generated public key collides with one of the X honest public keys. This is not ideal, as mentioned in NIST’s call for signatures:

“Another desirable property is resistance to multi-key attacks. Ideally an attacker should not gain an advantage by attacking multiple keys at once, whether the attacker’s goal is to compromise a single key pair, or to compromise a large number of keys.”

I think for the 4 schemes in question it is easy to prevent the attack simply by sampling a longer random seed. 

In the case of ALTEQ, the use of 128-bit seeds elsewhere in the signing algorithm is also a problem for single-key security. E.g., for the SL1 “balanced” parameters, each signature reveals r  = 84 trilinear forms that are computed as \phi_C \circ B_i (line 8 of the Sign algorithm), where \phi_C is part of the public key and B_i is expanded from a 128-bit seed (line 6).

 

That means that after seeing X signatures, the attacker knows 84*X values of the form  \phi_C \circ B, where B is expanded from a 128-bit seed. Therefore, by guessing seeds, an attacker can find one of the B’s with an effort of only 2^128/(84*X) group action evaluations. Knowing the seed reveals 1/7th of the secret key, repeating it roughly 7*ln(7) ~= 14 times recovers the whole secret (coupon collector’s problem). I believe this leads to a key recovery attack with roughly 14*2^128/(84*X) group action evaluations worth of effort if the attacker has access to X signatures.

I think the easiest solution is to include a random salt in the signature and do B_i <- ExpandColumns(seed||salt||i), similar to how the updated versions of MEDS and LESS prevented this attack.
 

 Regards,

Ward

 

 

 

 

[Matthieu Rivain]

Dear Ward,

Thank you and well done for spotting this.

We acknowledge the multi-key issue for MQOM and SDitH and we will double the size of the master seed for the key generation. We will patch the specifications and implementations accordingly as the standardisation process advances.

Best regards,

Matthieu (on behalf of the SDitH and MQOM teams)

-- 
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/00ff01da64c5%24155f6840%24401e38c0%24%40beullens.com.

[Youming Qiao]

Dear Ward,

Thanks for pointing out this attack on ALTEQ, and for suggesting a remedy. We will provide an update of our scheme, including a fix for this, by the end of March.

Best,
Youming (on behalf of the ALTEQ team)

[Youming Qiao]

Dear Ward, dear all, 

We've patched ALTEQ by adding salt to prevent this attack pointed out by Ward. The new spec and files are available at: 

https://pqcalteq.github.io/

Again, thanks to Ward for pointing out this attack and also suggesting a remedy. 

Best regards,

Youming

On Wednesday 21 February 2024 at 11:54:25 pm UTC+11 wa...@beullens.com wrote: