OFFICIAL COMMENT: ALTEQ

[Markku-Juhani O. Saarinen]

Hi All,

I'll describe a simple signature forgery attack against ALTEQ.

An ALTEQ signature consists of three parts: (cha, seed_i, D_i). ALTEQ is built on the Fiat-Shamir transform, and the verify function checks cha==cha' where cha' is reconstructed using the public key and the message. We observe that the challenge space can be reduced to binomial(r,K) size simply by setting the "seed_i" and "D_i" parts of the signature to zeros. The attack consists of finding a matching expandChallenge() output in this reduced space. 

We demonstrate the attack with a full forgery against Level I ShortSig-ALTEQ. The attack is especially easy in this case as we have r=16 and K=14.

The signed message "sm", expressed in Python as follows:

sm = (bytes.fromhex('E4E7C61518AD2CE12B20D96734B665C0E7F61286186D21B1FD4BF5BD7019BAA3') + (b'\x00' * 9496) + b'Forgery')

Passes as valid with the first public key of the ShortSig-ALTEQ level I test vectors (in file `[..]/ref_mode_lp/1/PQCsignKAT_16.rsp`, starting `pk = 9F4602C4C84A05..`) I have checked this against the reference C implementation.

The forged signature consists of a 32-bit challenge hash cha=E4E7C6.. with the rest of the signature (9496 bytes) set to zeros. This is a valid signature for 7-byte ASCII text 'Forgery' or  466F7267657279.

During verification of this signature, the input to the challenge hash cha' = H(H(M) |  psi'0 | psi'1 '| .. ) on line 11 in Vf function of Fig 2 of the spec) becomes:
idx [len] hex
H(M): [32] 67a14a46b32990b13d97fa4961c9baed4ba64d09b24c70e199f981d41824e70a
psi0: [1144] 83044487cf6021aaa5ae526928fd54d4468e27a3810abd02d4bb08d86257ec44..
psi1: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi2: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi3: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi4: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi5: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi6: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi7: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi8: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi9: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi10: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi11: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi12: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi13: [1144] 0000000000000000000000000000000000000000000000000000000000000000..
psi14: [1144] 83044487cf6021aaa5ae526928fd54d4468e27a3810abd02d4bb08d86257ec44..
psi15: [1144] 0000000000000000000000000000000000000000000000000000000000000000...

This is a collision as the two (r-K) non-zero vectors are expanded at the same locations by expandChallenge. We only had to perform binomial(16,14)=120 trials to find a match. Note that the non-zero vector 1144-byte vector 8304.. depends only on the public key.

The attack complexity is log2(binomial(r,K)) bits. One can observe the r and K parameters from Tables 2 and 3 in the specification -- the attack breaks all parameter sets much faster than indicated by the security category (at most 2^113 effort, even at Level 5.) The challenge space was apparently intended be  binomia(r,K)*C^K  which closely matches 2^lambda for all parameter sets.

An obvious countermeasure would be to filter the signature space against such pathological cases, but this was not done in the specification or the reference implementation.

Cheers,
-markku

Markku-Juhani O. Saarinen

[Markku-Juhani O. Saarinen]

Hi,

Typo below: It should be obvious but the challenge hash cha is 32 bytes, not 32 bits (it's included in full).

I put my Python implementation of ALTEQ together with the forgery demonstration here: https://github.com/mjosaarinen/alteq-py

Test vectors, of course, don't guarantee that the Python verification function is correct -- the forgeries have also been checked against the C reference code.

Cheers,

- markku

[Youming Qiao]

Dear Markku, Ward, and all, 

I am Youming, a member of the ALTEQ team. 

Thank you very much, Markku, for spotting this issue. And thank you very much, Ward, for providing your insight. 

Ward already summarised the situation well. So I am writing mostly to confirm the following: 

1. Markku's attack works for the current implementation. 
2. This is due to an oversight in the implementation, namely we didn't check the invertibility of matrices in the input to the verification procedure. 
3. The ALTEQ specification requires these matrices to be invertible. 
4. Adding such an invertibility check should invalidate this attack, and this check should not be expensive. 

We are working on an update version of the code and we will provide an update at https://pqcalteq.github.io/ when we are done. 

We thank Markku again for spotting this issue and providing a concrete code to implement this attack so quickly. This is impressive!

We welcome and look forward to more attention and efforts on the study of ALTEQ. 

Best regards,

Youming Qiao

[Markku-Juhani O. Saarinen]

Thanks Youming.

Recently ALTEQ security popped up in another context -- based on that feedback, I need to note that in my view, ALTEQ should be considered broken until the team updates the specification to counter this type of attack (the specification does not contain mechanisms or checks that could be directly used as a countermeasure). The countermeasure may also affect running times, as I don't see an entirely trivial check that is also sufficient -- even though the particular "backdoor signature" used in the PoC below was quite trivial. The issue is not just with all-zero inputs or plain matrix invertibility, so something like straightforward determinant computation isn't adequate.

Of course, after that update, the security of ALTEQ signature verification function reverts to essentially "unknown" until it receives some more scrutiny.

Cheers,

- markku

[Youming Qiao]

Dear Markku-Juhani, 

Thank you again for your close examination of ALTEQ. We took your attack seriously, and we had an updated version about three weeks ago. 

We delayed the release, because we wished to examine other possible attacks following your approach more carefully, and took this opportunity to speedup the code further. 

We aim to release a new version, hopefully sometime this week, and if not, definitely next week. Thank you for your patience. 

Best regards,

Youming

[Youming Qiao]

Dear Markku-Juhani, dear colleagues,

We just updated the ALTEQ website (https://pqcalteq.github.io/) with a new version (v1.1). The main updates are as follows.

1. We added the invertibility check of the matrices in the verification step, so to avoid from Markku-Juhani's attack.
   In a follow-up post, we will explain our understanding of this attack, and why we believe invertibility check is enough.
2. We sped up the code further.
   Briefly speaking, for balanced parameters, we achieve speed up ~2x speed up for verification. For short signature parameters, we achieve ~4x speed up for verification. The signing time is slightly (between 6% to 25 %) faster. The key gen time is slightly (between 8% to 10%) slower for some parameter sets, and faster for other parameter sets.
   While the addition of the invertibility check was supposed to slow down the verification, we achieved a speed-up at last due to a revamped implementation (but still generic) for AVX2.

We thank Markku-Juhani for his nice attack, and Ward for his timely suggestion on understanding this attack.

We welcome more scrutiny and examinations of ALTEQ.

Best regards,
Youming (on behalf of the ALTEQ team)

[Youming Qiao]

Dear all, 

In the following we explain our understanding of Markku-Juhani's attack. 

=========

Synopsis of the attack.

Part 1. We discuss simplified versions of ALTEQ and the attack, as we believe that they highlight the key to Markku-Juhani's attack.

The public key of ALTEQ consists of a set of trilinear forms (phi_0, ..., phi_C) in the same orbit.

The signature of ALTEQ consists of a sequence of challenges vc=(c_0, c_1, ..., c_{r-1}), where each c_i is in {0, 1, ..., C}, and a sequence of matrices (D_0, D_1, ..., D_{r-1}).

(In ALTEQ the challenge value C is special: if c_i=C then D_i will be expanded from a seed. In this part we omit this; we will come to this one in part 2.)

Let M be the message to be signed. Let psi_i be the result of transforming phi_{c_i} by D_i. This sequence of challenges is obtained from the hash value H(H(M)|psi_0|...|psi_{r-1}).

(In the signing procedure psi_i are obtained first and then based on the hash values, D_i are computed with the help of the private key. Here we are describing the viewpoint of the verifier.)

Now Markku-Juhani's forgery (in this simplified setting) goes as follows. Let rho be the all-zero trilinear form, and A be the all-zero matrix. Compute vc=H(H(M)|rho|...|rho). Send (vc, (A, ..., A)) as the signature.

The verification will pass, because it first computes psi_i=phi_{c_i}∘A=rho, and then computes H(H(M)|rho|...|rho), which is equal to vc.

The main reason can be understood as follows: if a matrix A is not invertible, then it is possible that phi_i∘A=phi_j∘A for i, j different. In the extreme case A=0, phi_i∘A=phi_j∘A for any i, j. From the Sigma protocol viewpoint, this means that the challenge does not matter for the all-zero trilinear form as the commitment, as there is a universal reply A (the all-zero matrix) that works for any challenge.

Therefore, we believe that adding the invertibility check should invalidate this attack (and the slightly more complicated ones such as A is not zero but of rank 1).

Part 2. Further details regarding Markku-Juhani's attack.

Markku-Juhani's attack utilises the above but there is more. As mentioned in part 1, for c_i=C, D_i will be expanded from a seed. Therefore for c_i=C, the matrix expanded from a seed will be invertible, so the idea in part 1 (using all-zero matrices) does not work for this case. Markku-Juhani's clever new idea here is to insert matrices spanned from a fixed seed at some positions. He then uses collision to identify a sequence of challenges where those positions are indeed of value C. Despite some probability of failure, this works out in practice for some parameter sets.

It is then natural to wonder if this idea would still work with the invertibility check added. Note that the difference is that it is not enough for the "collision" step to ensure that the chosen positions are of value C. It also needs to ensure that the other positions are exactly the given ones, as there is no freedom such as "any value in other positions would work". Theoretically, it can be shown that this design is EUF-CMA (assuming the hardness of ATFE and hash functions). Of course, in practice there might be attacks exploiting other types of loopholes. 

=========

Best regards,
Youming (on behalf of the ALTEQ team)