Round 1 (Additional Signatures) OFFICIAL COMMENT: EHTv3
891 views
Skip to first unread message
Wessel van Woerden
Jul 25, 2023, 12:31:53 PM7/25/23
to pqc-forum, Eamonn Postlethwaite
Dear EHTv3 Team,
In the proposal it is written that
"Hence, to forge a signature for EHTv3 NIST category 1 parameters it may be enough to solve an approximate SVP in the Euclidean norm for the lattice LI with an approximation factor α ≤ 3. Since the approximation factor is small, that might be as hard as finding a shortest non-zero vector in LI".
The approximation factor 3 is in practice rather large.
Let's have a look at the security level 1 parameters of EHTv3, where this lattice has dimension l=451.
BKZ with a blocksize of around 205 is enough to find an approximate shortest vector of the required length, which then with reasonable probability has a small enough infinity norm (according to your arguments around Table 4).
Roughly, this leads to only 0.292*205=59.86 bits of security in the core-SVP model.
We recommend to first randomise the lattice basis for LI as the q-vectors might interfere with the usual conversion to the infinity norm, see e.g. Appendix C of [4].
To forge one actually has to solve an approximate CVP problem, this can be approached e.g. in the following ways:
1. Embed the target into a lattice of dimension l+1.
With proper randomisation and due to the q-ary structure any approximate short vector can be expected to give a solution to the approximate CVP instance with probability about 2/q. One may sieve to find many such.
2. b-BKZ reduce the lattice, then incrementally lift the target t by solving CVP in blocks [l-b:l), [l-2*b+1:l-b+1),.. following [1]. This gives about the same (Hermite)-CVP approximation factor as BKZ does for (Hermite)-SVP.
In short, a signature can be forged with an SVP/CVP oracle in dimension 205, which puts the scheme far below security level 1.
If we do not project to the 451 dimensional sublattice as in the specification, but do the same attack in the full 460 dimensions, while allowing m-l coefficients to be arbitrarily large, then we expect the successful blocksize to be even lower.
Secondly, we present a potentially better attack based on the fact that the scheme uses a low modulus q, e.g. q=47 for the security level 1 parameters.
This gives the basis profile a particular Z-shape.
Following the ideas of [2] we can first reduce the lattice such that nq of the initial vectors are q-vectors.
Then we first find many approx CVP solutions in the projected lattice p_nq(L) via sieving/batch-CVPP, and lift them to the full context by solving exact CVP on q*ZZ^nq (by simple rounding).
The probability that one such lift has enough small coefficients is rather small, but this can be compensated by the many solutions given by the sieving/batch-CVPP.
We created a script [5] that shows that an equivalent of blocksize b=170 is enough for this attack to break the security level 1 parameters of EHTv3.
All steps have a cost of the order 2^(0.292b+o(b)). This script uses some functions [3] from [2].
For security levels 3 and 5, b=300 and b=400 respectively are enough for this attack.
Best regards,
Eamonn Postlethwaite and Wessel van Woerden
[1] https://msp.org/obs/2020/4-1/p16.xhtml
[2] https://eprint.iacr.org/2023/1125.pdf
[3] https://github.com/verdiverdiverdi/ISIS-small-q
[4] https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf
[5] https://github.com/WvanWoerden/EHT/blob/main/EHT.sage
In the proposal it is written that
"Hence, to forge a signature for EHTv3 NIST category 1 parameters it may be enough to solve an approximate SVP in the Euclidean norm for the lattice LI with an approximation factor α ≤ 3. Since the approximation factor is small, that might be as hard as finding a shortest non-zero vector in LI".
The approximation factor 3 is in practice rather large.
Let's have a look at the security level 1 parameters of EHTv3, where this lattice has dimension l=451.
BKZ with a blocksize of around 205 is enough to find an approximate shortest vector of the required length, which then with reasonable probability has a small enough infinity norm (according to your arguments around Table 4).
Roughly, this leads to only 0.292*205=59.86 bits of security in the core-SVP model.
We recommend to first randomise the lattice basis for LI as the q-vectors might interfere with the usual conversion to the infinity norm, see e.g. Appendix C of [4].
To forge one actually has to solve an approximate CVP problem, this can be approached e.g. in the following ways:
1. Embed the target into a lattice of dimension l+1.
With proper randomisation and due to the q-ary structure any approximate short vector can be expected to give a solution to the approximate CVP instance with probability about 2/q. One may sieve to find many such.
2. b-BKZ reduce the lattice, then incrementally lift the target t by solving CVP in blocks [l-b:l), [l-2*b+1:l-b+1),.. following [1]. This gives about the same (Hermite)-CVP approximation factor as BKZ does for (Hermite)-SVP.
In short, a signature can be forged with an SVP/CVP oracle in dimension 205, which puts the scheme far below security level 1.
If we do not project to the 451 dimensional sublattice as in the specification, but do the same attack in the full 460 dimensions, while allowing m-l coefficients to be arbitrarily large, then we expect the successful blocksize to be even lower.
Secondly, we present a potentially better attack based on the fact that the scheme uses a low modulus q, e.g. q=47 for the security level 1 parameters.
This gives the basis profile a particular Z-shape.
Following the ideas of [2] we can first reduce the lattice such that nq of the initial vectors are q-vectors.
Then we first find many approx CVP solutions in the projected lattice p_nq(L) via sieving/batch-CVPP, and lift them to the full context by solving exact CVP on q*ZZ^nq (by simple rounding).
The probability that one such lift has enough small coefficients is rather small, but this can be compensated by the many solutions given by the sieving/batch-CVPP.
We created a script [5] that shows that an equivalent of blocksize b=170 is enough for this attack to break the security level 1 parameters of EHTv3.
All steps have a cost of the order 2^(0.292b+o(b)). This script uses some functions [3] from [2].
For security levels 3 and 5, b=300 and b=400 respectively are enough for this attack.
Best regards,
Eamonn Postlethwaite and Wessel van Woerden
[1] https://msp.org/obs/2020/4-1/p16.xhtml
[2] https://eprint.iacr.org/2023/1125.pdf
[3] https://github.com/verdiverdiverdi/ISIS-small-q
[4] https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf
[5] https://github.com/WvanWoerden/EHT/blob/main/EHT.sage
Martin Feussner
Aug 28, 2023, 9:34:20 AM8/28/23
to pqc-forum, Wessel van Woerden, Eamonn Postlethwaite
Dear Wessel van Woerden and Eamonn Postlethwaite.
Thank you for the comment on the security of EHTv3. You have raised
an interesting question on how large the SVP approximation factor may
be such that the hardness of the problem is comparable to the hardness
of the SVP itself in practice. Unfortunately, neither detailed analysis,
nor detailed algorithm and nor computational evidence were presented in
your comment. As we were not able to verify your assertions, we suggest
a challenge as a response to the comment, you can find it here. That is an
EHTv3 instance with smaller parameters than in the specification for
the security level 1. It is based on a q-ary (for q=47) lattice of rank
280 instead of rank 460 as in the specification. We estimate the security of the challenge at around 80 bits. If
your observation is correct, then you would be able to break the
challenge. Besides the solution, we kindly ask you to provide your code
in order to replicate the attack.
Martin Feussner
Aug 29, 2023, 9:50:11 AM8/29/23
to pqc-forum, Martin Feussner, Wessel van Woerden, Eamonn Postlethwaite
Dear all
There seems to be some sharing issues with the link (requires you to request permission to access). You can also try this link. If you're still prompted to request access, please do so and I will approve it immediately.
Best regards,
EHT team.
There seems to be some sharing issues with the link (requires you to request permission to access). You can also try this link. If you're still prompted to request access, please do so and I will approve it immediately.
Best regards,
EHT team.
Wessel van Woerden
Aug 30, 2023, 7:52:00 AM8/30/23
to pqc-forum, Martin Feussner, Wessel van Woerden, Eamonn Postlethwaite
Dear EHT Team,
# output of break.sage using the BKZ-100 reduced basis B100.txt:
The details of the algorithm and the analysis was presented in the linked script with extensive comments [1], so I do not agree that none such details were given.
Anyway, I never mind a challenge so below a solution obtained via a method similar to the first attack we presented.
In short, to solve it:
1. Create a basis of the q-ary lattice L = A*Z^n + q*Z^m starting with m-n q-vectors.
1. Create a basis of the q-ary lattice L = A*Z^n + q*Z^m starting with m-n q-vectors.
2. BKZ-reduce it with blocksize 100
3. Find a close vector to h using Babai reduction. Randomize with the last few basis vectors to obtain multiple close vectors and pick one that satisfies the constraints.
For step 2 I used [2] with pump_and_jump+gpu and jump=3, but with a bit more patience plain G6K should also work.
In terms of quality it seems comparable to BKZ with blocksize +-90.
The total runtime was less than 3 hours on 8 threads and 1 partial a100 gpu.
For step 3 a simple sage script is available at [3], which runs in a few seconds. The output is copied below.
# output of break.sage using the BKZ-100 reduced basis B100.txt:
Loading data..
Starting babai reduction..
Solution found with minl = 273 >= l
x_vec = (23, 22, 46, 33, 1, 7, 3, 42, 29, 17, 18, 12, 14, 15, 12, 30, 18, 27, 11, 27, 26, 18, 17, 36, 6, 38, 0, 9, 13, 31, 23, 23, 36, 26, 16, 3, 42, 0, 39, 21, 10, 16, 46, 23, 5, 9, 37, 34, 0, 19, 37, 40, 42, 31, 24, 3, 27, 31, 9, 23, 35, 29, 3, 23, 30, 19, 8, 6, 14, 11, 44, 29, 31, 17, 36, 37, 22, 32, 10, 43, 42, 25, 13, 19, 9, 22, 31, 31, 6, 31, 8, 27, 25, 42, 0, 11, 42, 8, 9, 3, 36, 2, 11, 37, 43, 21, 8, 29, 27, 46, 26, 34, 5, 37, 15, 17, 16, 21, 20, 6, 6, 43, 28, 10, 42, 14, 20, 7, 39, 40, 12, 10, 9, 41, 9, 4, 29, 17, 41, 4, 1, 38, 21, 30, 27, 8, 20, 35, 21, 21, 41, 7)
Verify solution..
Solution verified, e= (1, -8, -2, 6, 4, -12, 3, -5, 0, 3, 0, -1, 2, 6, -2, -2, 8, -7, 1, 1, 0, 11, -2, -7, -8, -7, 9, 4, 1, -4, -3, 0, 3, 4, -2, -4, -1, 0, -2, 3, -3, 3, 2, 8, -3, -7, -1, 0, 1, -3, -5, 4, -3, -1, 3, -3, -4, -3, -7, 0, -6, 1, -5, 4, -5, 0, -6, 0, -10, -3, 9, -3, -2, -10, 0, 0, -1, 0, -2, 1, -9, -8, 7, 0, 0, -2, 7, 0, 3, 0, 6, 0, -2, 4, 1, -1, 4, -2, 0, -7, 0, 7, -6, 6, -1, -3, 0, 3, 0, 0, 0, 0, 0, 4, -2, 0, 0, -9, -1, 0, 0, 0, 0, 0, 0, 1, 0, -6, 0, 0, 0, 0, 0, 8, 6, 0, 2, 0, 0, 0, 6, -1, 0, 0, 0, 0, -3, 0, 10, 0, -17, 0, 16, 6, 9, 5, 1, -4, -18, 1, 6, -3, 17, 10, -3, -3, -2, 3, 9, -2, 3, 2, -23, 7, -1, 3, 13, 0, 10, 22, -2, 1, -2, 7, 9, -2, 14, -1, -2, 1, 4, 1, -9, -5, 0, 12, -3, 3, 4, -2, -4, -1, 0, -7, -1, 5, -7, -3, -4, -1, 1, 0, 1, 1, -1, -5, 3, -3, -6, 2, -9, -5, -6, -4, 1, -4, 4, 0, 4, 7, -9, -6, -3, -2, -3, -1, 1, 3, 5, 4, 2, 6, -4, 1, -3, 6, -3, 0, 2, -1, -4, -3, 3, -3, 0, 3, 2, 5, -3, 1, 1, -3, 8, 9, 2, 1, -2, -3, -1, -4, 0, -7, -1, -1, 0, -2, -1, 0, -6, -1)
Starting babai reduction..
Solution found with minl = 273 >= l
x_vec = (23, 22, 46, 33, 1, 7, 3, 42, 29, 17, 18, 12, 14, 15, 12, 30, 18, 27, 11, 27, 26, 18, 17, 36, 6, 38, 0, 9, 13, 31, 23, 23, 36, 26, 16, 3, 42, 0, 39, 21, 10, 16, 46, 23, 5, 9, 37, 34, 0, 19, 37, 40, 42, 31, 24, 3, 27, 31, 9, 23, 35, 29, 3, 23, 30, 19, 8, 6, 14, 11, 44, 29, 31, 17, 36, 37, 22, 32, 10, 43, 42, 25, 13, 19, 9, 22, 31, 31, 6, 31, 8, 27, 25, 42, 0, 11, 42, 8, 9, 3, 36, 2, 11, 37, 43, 21, 8, 29, 27, 46, 26, 34, 5, 37, 15, 17, 16, 21, 20, 6, 6, 43, 28, 10, 42, 14, 20, 7, 39, 40, 12, 10, 9, 41, 9, 4, 29, 17, 41, 4, 1, 38, 21, 30, 27, 8, 20, 35, 21, 21, 41, 7)
Verify solution..
Solution verified, e= (1, -8, -2, 6, 4, -12, 3, -5, 0, 3, 0, -1, 2, 6, -2, -2, 8, -7, 1, 1, 0, 11, -2, -7, -8, -7, 9, 4, 1, -4, -3, 0, 3, 4, -2, -4, -1, 0, -2, 3, -3, 3, 2, 8, -3, -7, -1, 0, 1, -3, -5, 4, -3, -1, 3, -3, -4, -3, -7, 0, -6, 1, -5, 4, -5, 0, -6, 0, -10, -3, 9, -3, -2, -10, 0, 0, -1, 0, -2, 1, -9, -8, 7, 0, 0, -2, 7, 0, 3, 0, 6, 0, -2, 4, 1, -1, 4, -2, 0, -7, 0, 7, -6, 6, -1, -3, 0, 3, 0, 0, 0, 0, 0, 4, -2, 0, 0, -9, -1, 0, 0, 0, 0, 0, 0, 1, 0, -6, 0, 0, 0, 0, 0, 8, 6, 0, 2, 0, 0, 0, 6, -1, 0, 0, 0, 0, -3, 0, 10, 0, -17, 0, 16, 6, 9, 5, 1, -4, -18, 1, 6, -3, 17, 10, -3, -3, -2, 3, 9, -2, 3, 2, -23, 7, -1, 3, 13, 0, 10, 22, -2, 1, -2, 7, 9, -2, 14, -1, -2, 1, 4, 1, -9, -5, 0, 12, -3, 3, 4, -2, -4, -1, 0, -7, -1, 5, -7, -3, -4, -1, 1, 0, 1, 1, -1, -5, 3, -3, -6, 2, -9, -5, -6, -4, 1, -4, 4, 0, 4, 7, -9, -6, -3, -2, -3, -1, 1, 3, 5, 4, 2, 6, -4, 1, -3, 6, -3, 0, 2, -1, -4, -3, 3, -3, 0, 3, 2, 5, -3, 1, 1, -3, 8, 9, 2, 1, -2, -3, -1, -4, 0, -7, -1, -1, 0, -2, -1, 0, -6, -1)
Best regards,
Wessel van Woerden
IMB, Université de Bordeaux
Martin Feussner
Nov 26, 2023, 8:46:54 AM11/26/23
to pqc-forum, Martin Feussner, Eamonn Postlethwaite
Dear
Eamonn and Wessel,
We have responded to this attack here.
Best regards,
Martin Feussner and Igor Semaev
Reply all
Reply to author
Forward
0 new messages