Round 1 (Additional Signatures) OFFICIAL COMMENT: EHT
707 views
Skip to first unread message
Adam Suhl
Jul 29, 2023, 12:30:51 AM7/29/23
to pqc-co...@nist.gov, pqc-...@list.nist.gov, kr...@ucsd.edu
Dear EHTv3 Team, and dear community,
We have developed and implemented a practical signature forgery attack on the category 1 security level parameters of EHTv3. Our proof-of-concept attack code is available at https://github.com/ucsd-hacc/ehtv3_cryptanalysis. Our attack uses 500000 signatures to learn an equivalent private key, and it takes approximately 122 core-hours. The underlying flaw is due to the biased distribution of signatures, and our partial key recovery algorithm exploits the special structure of the public key to find a matching private key.
EHTv3 is a signature scheme based on q-ary lattices. The private key (C, T, B) and public key (A) are rectangular matrices defined over Z_q such that A = CTB^{-1}. Furthermore, C is sparse, T is triangular, and B is invertible. Signatures are generated by first hashing to a vector h and then finding a random vector a satisfying Ca = h. Importantly, the triangular structure of T allows one to efficiently solve the Closest Vector Problem (Theorem 1 in the EHTv3 specification), so the signer finds vectors y and z such that a = Ty + z and the max norm of z is small. Finally, the signer computes signature x = By. Verification involves computing e = h - Ax = h - CTB^{-1}By = h - C(a - z) = Cz. Since C is sparse and z is small, e will be small for a correctly generated signature.
This signing method induces a secret-dependent distribution on the publicly observable values of e. We apply standard techniques to recover columns of C from this distribution, then we use a novel process to recover a valid signing key from A and the columns of C.
# Recovering columns of C
Observe that an attacker who observes many signatures can compute e_i = h_i - Ax_i = Cz_i for each sample. Both C and z_i have bounded norm, so the entries of e_i are small relative to the modulus, and usually no modular reduction occurs at this step. (Our attack will discard any e_i with any entry large enough that modular reduction may have taken place.) The values of e_i then lie in (a projection of) the parallelepiped generated by the columns of C. We use standard tools to learn this distribution and infer the columns of C.
As the EHTv3 submission mentions, if C were square this would be an instance of the Hidden Parallelepiped Problem: the e_i would lie in the parallelepiped generated by the columns of C, and we want to "learn the parallelepiped" by studying the distribution of observed Cz -- but C has more columns than rows. Instead, this is an instance of the Hidden Zonotope Problem (HZP) from [DucasNguyen12]. Ducas and Nguyen present a statistical algorithm for solving HZP that involves approximating the covariance matrix of C from observed samples and learning columns of C from the zonotope using gradient descent. We implemented the algorithm of [DucasNguyen12] and confirm that it succeeds for the category 1 parameters.
[DucasNguyen12]: Leo Ducas and Phong Nguyen, "Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures," Asiacrypt 2012. https://www.iacr.org/archive/asiacrypt2012/76580428/76580428.pdf
Concretely, in the category 1 security level parameters, all operations are modulo 47. C is a matrix of size 460x484 and is specially constructed so that all rows have l_1 norm 9. The vector z contains entries that lie between -3 and 3. Entries in e_i before modular reduction can be as large as +-27; discarding the roughly 10% signatures where e_i has entries large enough that modular reduction might have occurred, we ensure that each remaining e_i = C z_i over the integers. This rejection sampling, along with the way the z_i are generated in the first place, mean that the z_i are not exactly uniformly distributed, but empirically the [DucasNguyen12] algorithm succeeds anyway.
This recovers some information about the private matrix C, but it is as yet unclear how this can be used to forge signatures. In addition, the algorithm for HZP may return column vectors in any order, only recovers these vectors up to sign, and the set of recovered vectors may contain false positives. We demonstrate how this information is enough to forge EHTv3 signatures.
# Recovering a private key from columns of C
We assume, for the purposes of explanation, that the algorithm of [DucasNguyen12] has successfully recovered the unordered set of column vectors of C up to multiplication of each vector by 1 or -1. We wish to recover values C, T, and B that correspond to the public key that will enable us to forge signatures for this public key. Note that we do not need to recover exactly the same C, T, and B originally used to generate the public key; we only need C to be sparse, T to allow efficient CVP, and invertible B.
We use the triangular structure of T to progressively recover the correct ordering and sign of columns in C. T is a matrix of dimension kn x n, or 484 x 242. For example, if n=3, then T has the lower triangular form
[ 1 0 0 ]
[ 7 0 0 ]
[ * 1 0 ]
[ * 7 0 ]
[ * * 1 ]
[ * * 7 ]
where each * is replaced with a randomly generated value modulo 47.
Observe what happens when we compute the final column of CT. The final column of T is known, and all but the last two entries of this column are zero, so only the last two columns of C have any influence on the last column of CT. Because of the equality CT = AB, we also know that the last column (and all other columns) of CT lies in the column span of A. A is dimension 460 x 242, so a randomly chosen vector of dimension 460 is unlikely to be in this column span. Since we have a set of unordered columns of C up to sign, we can try all pairs and signs for the last two columns of C until we find one where the last column of CT is in the column span of A. Experimentally, this solution is almost always unique. Although the 484 * 483 * 2 * 2 possible pairs could be found with brute force search, we use a meet-in-the-middle attack to make this step faster.
This technique cannot be directly used to recover the order of the other columns of C. The second-to-last column of CT depends on the last four columns of C and the second-to-last column of T. There are now even more unknowns that go into this product: the choice of the third and fourth rightmost column of C, the choice of sign for these columns, and the choice of the two unknown subdiagonal values in the second-to-last column of T. We could try all 482 * 481 * 2 * 2 * 47 * 47 possibilities and check if the resulting column is in the column span of A, but the search quickly becomes prohibitively expensive as we have to guess more subdiagonal values of T.
We solve this problem by using kernels of recovered columns of C. If K is the left kernel of the rightmost two columns of C (which we recovered in the previous step), then the last two column vectors of KC are all zero. The second-to-last column of KCT therefore depends on the choice of the next two columns of C and the choice of sign, but it no longer depends on the unknown subdiagonal because they are multiplied by the zeros in KC. We search the 482 * 481 * 2 * 2 possibilities for the correct choice of C columns and signs that leads to the second-to-last column of KCT being in the column span of KA. The subdiagonal values can be recovered efficiently in a similar way, since the uncertainty in the choice of columns has been eliminated. This process repeats, recovering the order and sign of columns of C, the values of T, and allowing us to solve for the columns of B.
Our attack results in C, T, and B satisfying the key equation for EHTv3. For ease of explanation, we are leaving out some additional details like how we reduce the search space further by considering equivalent forms of different private keys for a single public key, or how we address the effect of the rank of K on the column span of KA. We will post these additional details of our attack to ePrint.
# Experiments
We have implemented our full attack and have published our code at https://github.com/ucsd-hacc/ehtv3_cryptanalysis. We ran the experiments on a cluster of machines with Xeon E5-2699 v4 processors (88 cores per machine at 2.20 GHz) and the peak RAM usage was under 16 GB per machine. We began by generating one of the KAT keys with the reference implementation, and we then generated 500000 signatures using the crypto_sign function from the reference implementation. For each of these signatures, we computed the error vectors e_i = h_i - Ax_i = Cz_i, which took 15 core-minutes. We ran the algorithm from [DucasNguyen12] on this instance of HZP. It took ~20 seconds to estimate the covariance matrix, and it took ~120 core-hours to perform gradient descent to recover 519 candidate columns of C up to sign. Using these candidate columns, we performed our partial key recovery attack to obtain a private key (C, T, B). This step took around 80 core-minutes. Finally, we used the recovered key to forge a signature in 38 core-seconds. This signature passes verification as implemented in crypto_sign_open.
The attack in total took around 122 core-hours, or using the units of [Beullens22], about one laptop-weekend.
[Beullens22]: Ward Beullens, "Breaking Rainbow Takes a Weekend on a Laptop," Crypto 2022. https://crypto.iacr.org/2022/papers/538804_1_En_16_Chapter_OnlinePDF.pdf
With additional computing time (and possibly additional signatures) we expect this attack will scale to the category 3 and category 5 parameters, although further implementation work is needed.
Section 10.1 of the specification notes that instances of EHTv4 may be transformed into instances of EHTv3, which suggests this attack would likely apply to EHTv4 as well.
Sincerely,
Keegan Ryan and Adam Suhl
We have developed and implemented a practical signature forgery attack on the category 1 security level parameters of EHTv3. Our proof-of-concept attack code is available at https://github.com/ucsd-hacc/ehtv3_cryptanalysis. Our attack uses 500000 signatures to learn an equivalent private key, and it takes approximately 122 core-hours. The underlying flaw is due to the biased distribution of signatures, and our partial key recovery algorithm exploits the special structure of the public key to find a matching private key.
EHTv3 is a signature scheme based on q-ary lattices. The private key (C, T, B) and public key (A) are rectangular matrices defined over Z_q such that A = CTB^{-1}. Furthermore, C is sparse, T is triangular, and B is invertible. Signatures are generated by first hashing to a vector h and then finding a random vector a satisfying Ca = h. Importantly, the triangular structure of T allows one to efficiently solve the Closest Vector Problem (Theorem 1 in the EHTv3 specification), so the signer finds vectors y and z such that a = Ty + z and the max norm of z is small. Finally, the signer computes signature x = By. Verification involves computing e = h - Ax = h - CTB^{-1}By = h - C(a - z) = Cz. Since C is sparse and z is small, e will be small for a correctly generated signature.
This signing method induces a secret-dependent distribution on the publicly observable values of e. We apply standard techniques to recover columns of C from this distribution, then we use a novel process to recover a valid signing key from A and the columns of C.
# Recovering columns of C
Observe that an attacker who observes many signatures can compute e_i = h_i - Ax_i = Cz_i for each sample. Both C and z_i have bounded norm, so the entries of e_i are small relative to the modulus, and usually no modular reduction occurs at this step. (Our attack will discard any e_i with any entry large enough that modular reduction may have taken place.) The values of e_i then lie in (a projection of) the parallelepiped generated by the columns of C. We use standard tools to learn this distribution and infer the columns of C.
As the EHTv3 submission mentions, if C were square this would be an instance of the Hidden Parallelepiped Problem: the e_i would lie in the parallelepiped generated by the columns of C, and we want to "learn the parallelepiped" by studying the distribution of observed Cz -- but C has more columns than rows. Instead, this is an instance of the Hidden Zonotope Problem (HZP) from [DucasNguyen12]. Ducas and Nguyen present a statistical algorithm for solving HZP that involves approximating the covariance matrix of C from observed samples and learning columns of C from the zonotope using gradient descent. We implemented the algorithm of [DucasNguyen12] and confirm that it succeeds for the category 1 parameters.
[DucasNguyen12]: Leo Ducas and Phong Nguyen, "Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures," Asiacrypt 2012. https://www.iacr.org/archive/asiacrypt2012/76580428/76580428.pdf
Concretely, in the category 1 security level parameters, all operations are modulo 47. C is a matrix of size 460x484 and is specially constructed so that all rows have l_1 norm 9. The vector z contains entries that lie between -3 and 3. Entries in e_i before modular reduction can be as large as +-27; discarding the roughly 10% signatures where e_i has entries large enough that modular reduction might have occurred, we ensure that each remaining e_i = C z_i over the integers. This rejection sampling, along with the way the z_i are generated in the first place, mean that the z_i are not exactly uniformly distributed, but empirically the [DucasNguyen12] algorithm succeeds anyway.
This recovers some information about the private matrix C, but it is as yet unclear how this can be used to forge signatures. In addition, the algorithm for HZP may return column vectors in any order, only recovers these vectors up to sign, and the set of recovered vectors may contain false positives. We demonstrate how this information is enough to forge EHTv3 signatures.
# Recovering a private key from columns of C
We assume, for the purposes of explanation, that the algorithm of [DucasNguyen12] has successfully recovered the unordered set of column vectors of C up to multiplication of each vector by 1 or -1. We wish to recover values C, T, and B that correspond to the public key that will enable us to forge signatures for this public key. Note that we do not need to recover exactly the same C, T, and B originally used to generate the public key; we only need C to be sparse, T to allow efficient CVP, and invertible B.
We use the triangular structure of T to progressively recover the correct ordering and sign of columns in C. T is a matrix of dimension kn x n, or 484 x 242. For example, if n=3, then T has the lower triangular form
[ 1 0 0 ]
[ 7 0 0 ]
[ * 1 0 ]
[ * 7 0 ]
[ * * 1 ]
[ * * 7 ]
where each * is replaced with a randomly generated value modulo 47.
Observe what happens when we compute the final column of CT. The final column of T is known, and all but the last two entries of this column are zero, so only the last two columns of C have any influence on the last column of CT. Because of the equality CT = AB, we also know that the last column (and all other columns) of CT lies in the column span of A. A is dimension 460 x 242, so a randomly chosen vector of dimension 460 is unlikely to be in this column span. Since we have a set of unordered columns of C up to sign, we can try all pairs and signs for the last two columns of C until we find one where the last column of CT is in the column span of A. Experimentally, this solution is almost always unique. Although the 484 * 483 * 2 * 2 possible pairs could be found with brute force search, we use a meet-in-the-middle attack to make this step faster.
This technique cannot be directly used to recover the order of the other columns of C. The second-to-last column of CT depends on the last four columns of C and the second-to-last column of T. There are now even more unknowns that go into this product: the choice of the third and fourth rightmost column of C, the choice of sign for these columns, and the choice of the two unknown subdiagonal values in the second-to-last column of T. We could try all 482 * 481 * 2 * 2 * 47 * 47 possibilities and check if the resulting column is in the column span of A, but the search quickly becomes prohibitively expensive as we have to guess more subdiagonal values of T.
We solve this problem by using kernels of recovered columns of C. If K is the left kernel of the rightmost two columns of C (which we recovered in the previous step), then the last two column vectors of KC are all zero. The second-to-last column of KCT therefore depends on the choice of the next two columns of C and the choice of sign, but it no longer depends on the unknown subdiagonal because they are multiplied by the zeros in KC. We search the 482 * 481 * 2 * 2 possibilities for the correct choice of C columns and signs that leads to the second-to-last column of KCT being in the column span of KA. The subdiagonal values can be recovered efficiently in a similar way, since the uncertainty in the choice of columns has been eliminated. This process repeats, recovering the order and sign of columns of C, the values of T, and allowing us to solve for the columns of B.
Our attack results in C, T, and B satisfying the key equation for EHTv3. For ease of explanation, we are leaving out some additional details like how we reduce the search space further by considering equivalent forms of different private keys for a single public key, or how we address the effect of the rank of K on the column span of KA. We will post these additional details of our attack to ePrint.
# Experiments
We have implemented our full attack and have published our code at https://github.com/ucsd-hacc/ehtv3_cryptanalysis. We ran the experiments on a cluster of machines with Xeon E5-2699 v4 processors (88 cores per machine at 2.20 GHz) and the peak RAM usage was under 16 GB per machine. We began by generating one of the KAT keys with the reference implementation, and we then generated 500000 signatures using the crypto_sign function from the reference implementation. For each of these signatures, we computed the error vectors e_i = h_i - Ax_i = Cz_i, which took 15 core-minutes. We ran the algorithm from [DucasNguyen12] on this instance of HZP. It took ~20 seconds to estimate the covariance matrix, and it took ~120 core-hours to perform gradient descent to recover 519 candidate columns of C up to sign. Using these candidate columns, we performed our partial key recovery attack to obtain a private key (C, T, B). This step took around 80 core-minutes. Finally, we used the recovered key to forge a signature in 38 core-seconds. This signature passes verification as implemented in crypto_sign_open.
The attack in total took around 122 core-hours, or using the units of [Beullens22], about one laptop-weekend.
[Beullens22]: Ward Beullens, "Breaking Rainbow Takes a Weekend on a Laptop," Crypto 2022. https://crypto.iacr.org/2022/papers/538804_1_En_16_Chapter_OnlinePDF.pdf
With additional computing time (and possibly additional signatures) we expect this attack will scale to the category 3 and category 5 parameters, although further implementation work is needed.
Section 10.1 of the specification notes that instances of EHTv4 may be transformed into instances of EHTv3, which suggests this attack would likely apply to EHTv4 as well.
Sincerely,
Keegan Ryan and Adam Suhl
Message has been deleted
Martin Feussner
Nov 26, 2023, 8:44:58 AM11/26/23
to pqc-forum, Adam Suhl, pqc-...@list.nist.gov, kr...@ucsd.edu, pqc-co...@nist.gov
Dear Keegan and Adam,
We have responded to this attack here.
Best regards,
Martin Feussner and Igor Semaev
Reply all
Reply to author
Forward
0 new messages