OFFICIAL COMMENT: pqsigRM
Perlner, Ray (Fed)
Dear pqrmsig submitters,
Jacob, Dustin and I have dramatically improved our attack on your proposed 128 and 192 bit parameters. Our implementation of the attack on the 192 bit parameters can recover an equivalent private key in a matter of seconds and we expect similar performance for the 128 bit parameters.
- We can trivially locate the punctured columns by taking the support of the intersection of the public code and its dual code. The code will have support everywhere except on the punctured columns. (This applies to all three parameter sets.)
- For the 192 and 128 bit parameters (rm4,12 and rm 6,11) we can apply the Chizov-Borodin attack starting from the intersection of the code and its dual code. This will be a subcode of rm4,12 for the 128 bit parameters and rm5, 12 for the 192 bit parameters. The attack performs best when, instead of simply computing a product code when the Chizov-Borodin attack calls for it, we start with the union of the two codes being multiplied and add codewords from the product code until we reach the desired rank (e.g. when squaring the subcode of rm5,12 with 30 punctures, we stop when the rank is 30 less than the expected rank of an rm10,12 code.) The attack yields a permutation that takes the columns of the public parity check matrix to the columns of a punctured reed muller code of the appropriate size.
In summary, combining these results with our previous observations, it seems that all the known attacks on the Sidelnikov cryptosystem carry over with minimal overhead to the punctured case. It is possible that a self-dual instance of the Sidelnikov cryptosystem might be secure, but it likely requires a code larger than even your largest parameter set (which is itself based on a self-dual code.) The next large Reed Muller code would be a rm(7,15) code, which would yield a key size of 32 megabytes. It should also be noted that all disguised Reed Muller codes, including their punctured variants, are detectably non-random, since, unlike random codes, they have a large intersection with their dual codes.
I have attached the sage file implementing our attack on the 192 bit parameters and a pdf record of the output. Dustin wishes to apologize for the amateurish coding.
Ray Perlner
Yongwoo Lee
Dear Dr. Perlner, Dr. Moody and Dr. Alperin-Sheriff.
Thank you for your comments.
We found that the proposed attacks can be prevented by simply changing the random matrix part of the generator matrix to another position of the generator matrix.
The public key of pqsigRM is a permuted parity check matrix corresponding to the generator matrix of the RM code, in which p columns are replaced by random vectors.
Here, we will simply replace another position of the generator matrix with random matrix, instead of “p columns”.
For example, in pqsigRM-6-13, G represents the generator matrix of RM (6,13).
We replace the partial matrices, G[3534:3790, 6144: 6656], G[3534:3790, 6656:7168], G[3534:3790, 7168: 7680], and G[3534:3790, 7680: 8192] with [R|R], where R is a 256 * 256 binary random non-singular matrix and this modified generator matrix is referred to as G_m.
(G[3534:3790, 6144: 6656], G[3534:3790, 6656:7168], G[3534:3790, 7168: 7680], and G[3534:3790, 7680: 8192] originally corresponds to the generator matrix of RM(4,9).)
G_m is described as in Fig.1.
Fig. 1. Generator matrix of modified RM code
Then we can build the parity check matrix H_m corresponding G_m, and generate an (n-k)*(n-k) scrambler matrix S and n*n permutation matrix Q.
The public key is given as H’ = S*H_m*Q.
The private keys are given as S, Q.
In this case, we do not need to obtain e_p separately when signing.
Instead, we can include this process in syndrome decoding.
You can decode this code by simply adding two lines to the original recursive decoding of RM code. Modifications are shown in Algorithm 1.(the first two lines in red).
With this modification, there are no all-zero position on the hull of public key.
The probability of 1’s in the elements of the signature is not different.
Near-minimum weight codewords are no longer useful for locating the punctured/inserted positions.
Because 1/4 elements of each codeword are replaced by random elements and the minimum weight of the code is much less than n/4.
Modifying the generator matrix in this way also prevents square code attack, Chizhov-Borodin attack, and Minder-Shokrollahi attack.
For 196-bit security,
we replace G[1868: 2124, 2560: 3072] and G[1868: 2124, 3584: 4096] with [R|R], where G is a generator matrix of RM(6,12).
For 128-bit security,
we replace G[894: 958, 1536: 1664], G[894: 958, 1664: 1792], G[894: 958, 1792: 1920] and G[894: 958, 1920: 2048] with [R|R], where G is a generator matrix of RM(5,11).
Algorithm 1. Modified decoding of pqsigRM
rec_dec(y, r, m, rear, front):
if front == 3534 and rear == 3790:
y[front : rear] <- the nearest 2-repetition codeword from y[front : rear]
else if r == 0:
d1 <- distance(y[front:rear], [-1 -1 -1 … -1]);
d2 <- distance(y[front:rear], [ 1 1 1 … 1]);
if d1 < d2:
y[front:rear] <- [-1 -1 -1 … -1]
else:
y[front:rear] <- [ 1 1 1 … 1]
elif r == m:
for i from front to rear:
y[i] <- (y[i] >= 0)? 1: -1
else:
mid = (front + rear)/2
y_v <- copy( y[mid : rear] )
y [ mid : rear ] <- y[mid : rear] * y[ front : mid ]
rec_dec( y, r-1, m-1, mid, rear)
y [ front : mid ] <- (y [ front : mid ] + y [ mid : rear ] * y_v)/2
rec_dec( y, r, m-1, rear, mid)
y [ mid : rear ] <- y[mid : rear] * y[ front : mid ]
Yongwoo Lee.
From: Perlner, Ray (Fed) <ray.p...@nist.gov>
Sent: Saturday, March 10, 2018 2:30 AM
To: pqc-comments <pqc-co...@nist.gov>
Cc: pqc-...@list.nist.gov
Subject: [pqc-forum] OFFICIAL COMMENT: pqsigRM
Dear pqrmsig submitters,
Jacob, Dustin and I have dramatically improved our attack on your proposed 128 and 192 bit parameters. Our implementation of the attack on the 192 bit parameters can recover an equivalent private key in a matter of seconds and we expect similar performance for the 128 bit parameters.
1) We can trivially locate the punctured columns by taking the support of the intersection of the public code and its dual code. The code will have support everywhere except on the punctured columns. (This applies to all three parameter sets.)
2) For the 192 and 128 bit parameters (rm4,12 and rm 6,11) we can apply the Chizov-Borodin attack starting from the intersection of the code and its dual code. This will be a subcode of rm4,12 for the 128 bit parameters and rm5, 12 for the 192 bit parameters. The attack performs best when, instead of simply computing a product code when the Chizov-Borodin attack calls for it, we start with the union of the two codes being multiplied and add codewords from the product code until we reach the desired rank (e.g. when squaring the subcode of rm5,12 with 30 punctures, we stop when the rank is 30 less than the expected rank of an rm10,12 code.) The attack yields a permutation that takes the columns of the public parity check matrix to the columns of a punctured reed muller code of the appropriate size.
In summary, combining these results with our previous observations, it seems that all the known attacks on the Sidelnikov cryptosystem carry over with minimal overhead to the punctured case. It is possible that a self-dual instance of the Sidelnikov cryptosystem might be secure, but it likely requires a code larger than even your largest parameter set (which is itself based on a self-dual code.) The next large Reed Muller code would be a rm(7,15) code, which would yield a key size of 32 megabytes. It should also be noted that all disguised Reed Muller codes, including their punctured variants, are detectably non-random, since, unlike random codes, they have a large intersection with their dual codes.
I have attached the sage file implementing our attack on the 192 bit parameters and a pdf record of the output. Dustin wishes to apologize for the amateurish coding.
Ray Perlner
--
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.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.
Perlner, Ray (Fed)
Dear submitters,
We believe that the modification suggested in your previous email makes the RM(6,13) code significantly weaker than the unmodified code and we believe all of the modified codes in the previous email can be practically broken.
A couple of points to make the notation easier. First, note that WLOG, we may assume that the 256x256 matrix R is an identity matrix, since (0….0|R|R|R|R|R|R|R|R) and R^-1(0….0|R|R|R|R|R|R|R|R) = (0….0|I|I|I|I|I|I|I|I) generate the same code. Second, we will think of codewords as being polynomials over the variables (x0, x1, x2 x3 … x12), where x0 represents the high order bit of the column index and x12 represents the low order bit of the column index. So, for example, the support of x0x1 is identical to the locations of the modified columns, and the codewords generated by (0….0|I|I|I|I|I|I|I|I) are of the form x0*x1*p(x5, x6, x7, … x12), for some polynomial p. Note also that the symmetries of the modified code are such that it will have the same form if we substitute any degree 1 polynomials for (x0, x1, x2 x3 … x12) and reorder the columns accordingly, as long as the above two properties hold. We now describe the procedure for key recovery.
- Use information set decoding to find codewords in the modified code that have hamming weight 8. There will be 256 such codewords and their combined support will be the support of x0*x1.
- We can also easily recover the code generated by x0 and x1. If we take the subcode of the public code that lacks support on x0*x1 (i.e. the dual code of (1+ x0x1) times the public code) and square it, we get a code whose dual code (restricted to the columns where x0*x1 lacks support) is generated by 1, x0, and x1.
- WLOG we may pick two weight 4096 codewords from this dual code, each containing the support of x0x1, and call them x0 and x1.
- We may now apply Chizov Borodin to the submatrices of the public code consisting of the support columns of 1+ x0 and 1+x1. Each submatrix has a rowspace equal to an RM (6,12) code and can be attacked cheaply since GCD(6,12-1) = 1. We need to make sure that the two column orderings agree, but this just amounts to a linear constraint that the same degree 1 codeword is assigned to be x2, x3 … x12 in both cases.
- The Chizov Borodin attack may also be applied to x1 times the public code, but in this case there is a slight complication. The rowspace of that code contains an RM(6,12) code, but it also contains the codewords generated by (0….0|I|I|I|I|I|I|I|I). To get rid of these, we may take the intersection of the code with its dual code, resulting in a subcode of RM (5,12). This will not contain all the codewords from RM(5,12), but it will contain all degree 4 monomials that do not include a factor of x2*x3*x4. As such, the square of this code will be identical to RM(8,12), since we can get degree 8 monomials containing x2*x3*x4 e.g. by multiplying x2*x5*x6*x7*x8 by x3*x4*x9*x10*x11 to get x2*x3*x4*x5*x6*x7*x8*x9*x10*x11. Again we have some linear constraints on the choice of degree 1 codewords. In particular, all three assignments of degree 1 codewords to variables (x0, x1, … x12) must agree, x0 and x1 must agree with our original assignment of variables, and x5, … x12 must either be identically 1 or identically 0 on the support of each of the weight 8 codewords extracted in step 1.
We’ve verified some of this experimentally, but haven’t yet implemented the whole attack.
- We can trivially locate the punctured columns by taking the support of the intersection of the public code and its dual code. The code will have support everywhere except on the punctured columns. (This applies to all three parameter sets.)
- For the 192 and 128 bit parameters (rm4,12 and rm 6,11) we can apply the Chizov-Borodin attack starting from the intersection of the code and its dual code. This will be a subcode of rm4,12 for the 128 bit parameters and rm5, 12 for the 192 bit parameters. The attack performs best when, instead of simply computing a product code when the Chizov-Borodin attack calls for it, we start with the union of the two codes being multiplied and add codewords from the product code until we reach the desired rank (e.g. when squaring the subcode of rm5,12 with 30 punctures, we stop when the rank is 30 less than the expected rank of an rm10,12 code.) The attack yields a permutation that takes the columns of the public parity check matrix to the columns of a punctured reed muller code of the appropriate size.
Yongwoo Lee
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.
--
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+unsubscribe@list.nist.gov.
Yongwoo Lee
Dear all.
We have updated the documentation and code.
You can see the updated documentation and code below:
https://sites.google.com/view/pqsigrm/home
Yours!
pqsigRM Team.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.
--
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.
Visit this group at https://groups.google.com/a/list.nist.gov/group/pqc-forum/.
--
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.
Perlner, Ray (Fed)
On looking at some modified keys of the form described, Dustin and I found that the dual of the hull of such codes typically has a lot of code words with hamming weight 4. We suspect, but haven’t yet checked, that the support of such codewords, as found by standard information set decoding techniques will reveal which columns have been modified. Given that information, techniques we’ve already described should be sufficient to easily recover the key. Please comment.
Thanks,
Ray
Yongwoo Lee
Dear Perlner.
Sorry for late answer.
It seems natural that the minimum weight of the dual of hull is as small as four.
The reason for this is the dimension of the dual of hull is large, and it is not a well-designed code.
However, we have found an attack algorithm that finds half of the permutation Q using the statistical characteristic of low weight codewords of the dual of hull.
However, we found that we could modify pqsigRM’s public code slightly to prevent these attacks, which reduces the signing time.
Cryptanalysis of pqsigRM using the low weight Hamming weight codewords of the dual of the hull.
Collecting the low weighted codewords of the dual of the hull of the public code shows that the probability bit 1 is different depending on the location.
For example, in pqsigRM-5-11, the bits of c(n/4, …, 2n/4 -1) (indices before permutation Q) are always 0, where c is a codeword of of the dual of the hull with Hamming weight less than or equal to 8.
In addition c(0, …, n/4 -1) are more probable to be 1 and c(2n/4, …, n-1) is less probable to be one. Using this fact, we can design an attack algorithm to reveal the half of permutation Q.
An attacker can easily obtain the dual of hull of public code.
Next, by information set decoding, he can collect low weight codewords of the dual of the hull. Since the target weight is small, the information set decoding can efficiently be done. Using the statistical feature, he can divide the permutation into three parts: (0, …, n/4-1), (n/4, …, 2n/4-1), and (2n/4, …, n-1).
Note that for any codeword c of pqsigRM, c(0, …, n/2-1) is a original RM(r, m-1).
Chizhov-Borodin’s attack can be performed on c(0, …, n/2-1), which makes it to find out the half of permutation Q.
Hull vulnerability of pqsigRM
The hull of the previously proposed pqsigRM’s public code is a subset of original RM code. There is a threat by Minder-Shokrollahi's attack using the property.
Hence, we have to design our public code such that its hull is not a subset or many codewords of the hull is not in RM code.
Modified version of pqsigRM preventing those attacks
In summary, the following two properties should be considered.
There should be no statistical characteristics of the low weight codeword in the dual of the hull.
Hull should not be the subset of original RM code. Moreover, there should be many codewords in the hull of public code which are not RM code.
In addition, since RM code has a u|u+v structure, we have to consider:
The hull is not a u | u code.
Moreover, we propose method to reduce the signing time.
Modified RM code
We define \sigma_(p)^1(.) and \sigma_(p)^2(.) as two distinct partial permutations which are randomly permute of p columns out of n/4 columns.
The modified code C is given as:
C = {(\sigma_(p)^1)(x|x|x|x) | x in RM(r,m-2)} + {(0|x|0|x) | x in RM(r-1, m-2)}
+{(0|0|x|x) | x in RM(r-1, m-2)} + {(\sigma_(p)^2)(0|0|0|x) | x in RM(r-2, m-2)}
which is described in the document.
C satisfies the above four conditions that public code should have.
Also, it is resistant to all attacks against the proposed RM code based crypto algorithms until this point.
Please refer to the updated pqsigRM document for details on performance analysis, parameters, and so on.
link: https://sites.google.com/view/pqsigrm/home/documentation
Thanks,
pqsigRM Team.
From: Perlner, Ray (Fed) <ray.p...@nist.gov>
Sent: Wednesday, June 13, 2018 3:46 AM
To: Yongwoo Lee <yong...@ccl.snu.ac.kr>; pqc-...@list.nist.gov; pqc-comments <pqc-co...@nist.gov>
Cc: 'Jong-Seon No' <js...@snu.ac.kr>; '김영식' <iamy...@chosun.ac.kr>; 'ccl 이위직형' <leew...@ccl.snu.ac.kr>
Subject: RE: [pqc-forum] OFFICIAL COMMENT: pqsigRM
On looking at some modified keys of the form described, Dustin and I found that the dual of the hull of such codes typically has a lot of code words with hamming weight 4. We suspect, but haven’t yet checked, that the support of such codewords, as found by standard information set decoding techniques will reveal which columns have been modified. Given that information, techniques we’ve already described should be sufficient to easily recover the key. Please comment.
Thanks,
Ray
From: Yongwoo Lee [mailto:yong...@ccl.snu.ac.kr]
Sent: Monday, June 04, 2018 5:42 AM
To: pqc-...@list.nist.gov; pqc-comments <pqc-co...@nist.gov>
Cc: 'Jong-Seon No' <js...@snu.ac.kr>; '김영식' <iamy...@chosun.ac.kr>; 'ccl 이위직형' <leew...@ccl.snu.ac.kr>
Subject: RE: [pqc-forum] OFFICIAL COMMENT: pqsigRM
Dear all.
We have updated the documentation and code.
You can see the updated documentation and code below:
Yongwoo Lee
Dear all.
We modified the email yesterday for readability as follows.
It is easy to check that the minimum Hamming weight of the dual of hull
of the public code (H’) in the previous document is as small as four.
The reason for this is that the dimension of the dual of hull is large
and it is not a well-designed code.
However, we have found an attack algorithm to find half of the permutation Q
using the statistical characteristic of low Hamming weight codewords of the dual of hull.
However, we found that we could modify pqsigRM’s public code slightly
to prevent these attacks as in the revised pqsigRM document,
which reduces the signing time.
1) Cryptanalysis of pqsigRM using the low Hamming weight codewords
of the dual of the hull in the previous document.
Collecting the low Hamming weight codewords of the dual of the hull of the public code
shows that the probability of bit 1 is different depending on the location.
For example, in pqsigRM-5-11, the bits of c(n/4, …, 2n/4 -1) (indices before permutation Q) are always 0,
where c is a codeword of of the dual of the hull with Hamming weight less than or equal to 8.
In addition, the elements of c(0, …, n/4 -1) are more probable to be 1 and
the element of c(2n/4, …, n-1) is less probable to be 1.
Using this fact, we can design an attack algorithm to reveal the half of permutation Q.
An attacker can easily obtain the dual of hull of the public code.
Next, by information set decoding, he can collect low Hamming weight codewords of the dual of the hull.
Since the target Hamming weight is small, the information set decoding can efficiently be done.
Using the statistical feature, he can divide the permutation into three parts: (0, …, n/4-1), (n/4, …, 2n/4-1), and (2n/4, …, n-1).
Note that for any codeword c of pqsigRM, c(0, …, n/2-1) is a codeword of RM(r, m-1).
Chizhov-Borodin’s attack can be performed on c(0, …, n/2-1), which makes it possible to find out the half of permutation Q.
Thus, pqsigRM in the previous document is not secure.
2) Hull vulnerability of pqsigRM
The hull of the previously proposed pqsigRM’s public code is a subset of original RM code,
which makes it possible to attack pqsigRM by Minder-Shokrollahi's attack.
Hence, we have to design our public code such that its hull is not a subset of RM code
or many codewords in the hull is not in RM code.
3) Modified version of pqsigRM preventing those attacks in the modified document
In summary, the following two properties should be considered.
i) There should be no statistical characteristics of the low Hamming weight codewords in the dual of the hull.
ii) Hull should not be the subset of the original RM code. Moreover, there should be many codewords
in the hull of public code which are not in RM code.
In addition, since RM code has a u|u+v structure, we have to consider:
iii) The hull should not be a (u | u) code.
iv) Moreover, we propose method to reduce the signing time.
Thus, modified RM code in the modified version of pqsigRM is given as follows:
We define \sigma_(p)^1(.) and \sigma_(p)^2(.) as two distinct partial permutations
which are randomly permute p columns out of n/4 columns of generator matrix.
The modified code C is given as:
C = {(X|X|X|X)}; X denotes (\sigma_(p)^1)( RM(r,m-2) )
+ {(0|X|0|X)}; X denotes RM(r-1, m-2)
+ {(0|0|X|X)}; X denotes RM(r-1, m-2)
+ {(0|0|0|X)}; X denotes (\sigma_(p)^2)(RM(r-2, m-2))
which is described in the document in details.
C satisfies the above four conditions that the public code of the modified pqsigRM should have.
Also, it is resistant to all attacks against the proposed RM code based crypto algorithms upto this point.
Yongwoo Lee
2018. 10. 5. 오전 9:59, Yongwoo Lee <yong...@ccl.snu.ac.kr> 작성:
Yours!pqsigRM Team.From: Yongwoo Lee <yong...@ccl.snu.ac.kr>
Sent: Wednesday, April 11, 2018 11:31 PM
To: Perlner, Ray (Fed) <ray.p...@nist.gov>
Cc: pqc-...@list.nist.gov; pqc-comments <pqc-co...@nist.gov>; Jong-Seon No <js...@snu.ac.kr>; 김영식<iamy...@chosun.ac.kr>; ccl 이위직형 <leew...@ccl.snu.ac.kr>
Subject: Re: [pqc-forum] OFFICIAL COMMENT: pqsigRM
Dear Dr. Perlner.Thank you for your comment.After reviewing the attacking algorithm you proposed, we found that we could modify our proposed algorithm to defend against that attack.To be more specific, the inserted matrix does not have to be a generator matrix of 2-repitition codes.This can be replaced by a generator matrix of any code that has a decoding algorithm which returns a codeword even in the presence of a large error.For example, we can partially modify the generator matrix of RM(5,11) with the permuted generator matrix of RM(4, 9), instead of 2-repitition codeas below.Experiments have shown that decoding performance is good in this case.(Of course, the decoding requires additional depermutation.)Applying this idea, we have devised a way to replace the larger part of the generator matrix.For example, for 128-bit security, the public code is, H’ = S*H_m*Q, where H_m is the parity check matrix of the modified RM code, generated by the modified generator matrix of RM(5,11) as below:.And then, the decoding algorithm becomes:
<image001.png>
<image002.png>
Yongwoo Lee
We have updated pqsigRM.
Using code and decoding to find small weight error vectors for a given syndrome, we can reduce the iterations needed to sign in the CFS signature scheme.
It can be implemented as a constant-time algorithm that ensures successful signatures, with dozens to thousands of iterations.
We also resolved all the issues mentioned in pqc-forum by further modifying using adding/removing some rows of generator matrix.
You can see the document in the Archive:
https://eprint.iacr.org/2019/678
Thanks.
pqsigRM team.
Dear Dr. Ray Perlner;
I am one of submitters of pqsigRM
and enjoyed your talk at CBC, Darmstadt last weekend.
In fact, we totally modified our proposal, pqsigRM,
called a modified pqsigRM as attached.
We think that the modified pqsigRM is robust against all known attacks.
Now, there is no code-based post-quantum signature scheme
in the second round. As you said, standardization should be diverse
and include many candidates as possible as you can.
Is it possible to give us another chance to put our proposal on the pqc-forum?
How do you think about consolation match round(^^)
for the modified proposals, which are not in the second round?
Or, can we have one half-day session for the modified proposals after review process at Crypto2019?
Then, we may find good proposals for this PQC standardization.
I think that those additional process may be needed for the perfectness of the PQC standardization.
Thanks.
Jong-Seon No
---------------------------------------------------------
Jong-Seon No, Professor
Department of Electrical and Computer Engineering
Seoul National University
1 Gwanak-ro Gwanak-gu, Seoul 08826, Korea
email) js...@snu.ac.kr
Ph) +82-2-880-1809
Fax) +82-2-880-8222
---------------------------------------------------------
From: Perlner, Ray (Fed) [mailto:ray.p...@nist.gov]
Sent: Wednesday, June 13, 2018 3:46 AM
김영식' <iamy...@chosun.ac.kr>; 'ccl 이위직형' <leew...@ccl.snu.ac.kr>