776 views

Skip to first unread message

Apr 10, 2023, 1:33:29 AM4/10/23

to KpqC-bulletin

Dear all,

We would like to announce our analysis of [1], which is a paper version of Layered ROLLO-I.

Layered ROLLO-I is a BII-LRPC code-based KEM.

In the attached note, we calculated the complexity of several attacks for the proposed parameters of Layered ROLLO-I, demonstrating that they fall far short of the claimed security levels.

The proposed parameters do not even reach the security levels for the structural attacks suggested by the submitters.

We also found a conversion of Layered ROLLO-I to ROLLO-I using only its public keys.

This implies that Layered ROLLO-I is essentially identical to ROLLO-I.

All the best,

Seongtaek Chee, Kyung Chul Jeong, Nari Lee, Hansol Ryu

Layered ROLLO-I is a BII-LRPC code-based KEM.

In the attached note, we calculated the complexity of several attacks for the proposed parameters of Layered ROLLO-I, demonstrating that they fall far short of the claimed security levels.

The proposed parameters do not even reach the security levels for the structural attacks suggested by the submitters.

We also found a conversion of Layered ROLLO-I to ROLLO-I using only its public keys.

This implies that Layered ROLLO-I is essentially identical to ROLLO-I.

All the best,

Seongtaek Chee, Kyung Chul Jeong, Nari Lee, Hansol Ryu

--

[1] Kim, Chanki, Young-Sik Kim, and Jong-Seon No. "New Design of Blockwise Interleaved Ideal Low-Rank Parity-Check Codes for Fast Post-Quantum Cryptography." *IEEE Communications Letters* (2023).

May 19, 2023, 2:41:59 AM5/19/23

to KpqC-bulletin

Dear all,

We would like to inform you about our response to the recent attack on the Layered ROLLO scheme. After thorough analysis, we have determined that the new attacks pose a potential risk to the conventional Layered ROLLO scheme, which could compromise its security or even break the cryptosystem. In order to address this issue, we have made the following modifications to the Layered ROLLO scheme:

Firstly, to prevent new combinatorial and algebraic attacks, we have increased the rank weight 𝑟 of the error vector. It is important to note that this increase in 𝑟 may result in a slight decrease in processing speed. However, computer simulations has demonstrated that the overall performance advantage is still maintained.

Secondly, we have implemented a measure to avoid direct attacks using two public keys. This is achieved by selecting different modulus pairs from 𝑃 and 𝑃^𝑏. Such attacks were observed when the inverse (𝑃^′ )^(−1) of the modulus 𝑃^𝑏 could be reduced by (𝑃^′ )^(−1) on modulus 𝑃 after 𝑃-modulus reduction by equality 𝑃^′ (1+𝑃+…+𝑃^(𝑏−1) )(𝑃^′ )^(−1)=𝑃^𝑏−1 if 𝑃^′ (𝑃^′ )^(−1)=𝑃−1. we effectively mitigate this type of attack using the different moduli.

Lastly, we have addressed the error by enhancing the security level against conventional combinatorial attacks. This is achieved by increasing the degree of 𝑃_𝐼.

For more detailed information about our modifications, we have provided an attached document that outlines the revised schemes and suggests new parameters. Additionally, we have included the corresponding implementation code for your reference.

We would like to express our gratitude to the researchers for their valuable analysis and suggestions regarding the vulnerabilities in the Layered ROLLO scheme.

Sincerely,

Chanki Kim, Young-Sik Kim, and Jong-Seon No

2023년 4월 10일 월요일 오후 2시 33분 29초 UTC+9에 Nari Lee님이 작성:

Sep 4, 2023, 7:29:08 PM9/4/23

to KpqC-bulletin

Dear all,

We want to announce our analysis on the modified version of Layered-ROLLO-I

that was proposed on the 19/05/2023 in the kpqc forum:

https://groups.google.com/g/kpqc-bulletin/c/8nOd28f2K7k/m/P7K0p9r-AQAJ.

The modified version has been proposed as a response to the analysis of Chee,

Jeong, Lee, and Ryu, which was announced in: https://groups.google.com/g/kpqc-bulletin/c/8nOd28f2K7k.

The analysis performed by Chee, Jeong, Lee, and Ryu recomputes the costs of

rank syndrome decoding (RSD) attacks and points out the inadequacy of the

suggested parameters w.r.t. the considered security levels.

Also, a direct attack has been found which exploits the shape of the public key

in order to neutralize the effect of the multiplication by polynomials P_I and

P_O. This leverages the fact that P divides P^b in order to obtain a congruence

modulo P from a congruence modulo P^b.

The modified version overcomes the attack mentioned above by replacing the

modulus polynomials P and P^b with two primitive polynomials P_1 and P_2 so that

the congruence modulo P_2 cannot be considered modulo P_1. Moreover, new sets

of parameters have been proposed to boost security against RSD attacks.

In our work, we use the same techniques pointed out in the analysis of REDOG,

considering the latest improvements to RSD attacks, to compute complexities

corresponding to the new suggested parameters. For more details on these

strategies and Sage scripts, see:

https://link.springer.com/chapter/10.1007/978-3-030-64837-4_17

and

https://eprint.iacr.org/2023/1205

and the "search-rsd.sage" script attached to this email.

We found that the parameters provided in the slides for the modified version

are still not satisfying the corresponding security parameters. The costs of

the attacks are reported in the following table

Security BBC+

128 93.72

192 105.90

256 114.10

This shows that the suggested parameters are still too low to fight off

RSD attacks.

Furthermore, we managed to reduce any instance of the modified Layered-ROLLO-I

to an instance of ROLLO-I which uses a smaller code. Also, the reduction

recovers the PO and PI parts of the private key, showing a leakage in the

system. We do this by computing R=PH/PP and considering the system of

equations \Psi(PI)RM = \Psi(z), where RM is the matrix of the multiplication

by R mod P2.

The choices of degrees of PI and z ensure that the system has as a solution the

representatives of PI and z modulo P1. Actually, we recover k*PI, where k is a

field constant, by computing the left kernel of the matrix consisting of the

last deg(PI)+1 columns of RM. Compute now PO/k from PP/(k*PI) and k*z from

PH/(PO/k). Finally, compute y/x from (k*z)/(k*PI).

The attached "attack.sage" script computes y/x on a Linux Mint VM in around

1.85 seconds for security 128, around 2.42 seconds for security 192 and around

4.21 seconds for security 256.

With the knowledge of PO/k and k*PI we can similarly reduce a modified

Layered-ROLLO-I ciphertext to a ROLLO-I ciphertext.

In the end, from a (q,m,n1,n2,r,d,degPI) instance of modified Layered-ROLLO-I

we obtain a (q,m,n1,r,d) instance of ROLLO-I. Computing the costs of the same

RSD attacks to this reduced instance of ROLLO-I we obtain

Security BBC+

128 84.48

192 95.04

256 99.69

Please find attached a more detailed document explaining our analysis.

All the best,

Tanja and Alex

We want to announce our analysis on the modified version of Layered-ROLLO-I

that was proposed on the 19/05/2023 in the kpqc forum:

https://groups.google.com/g/kpqc-bulletin/c/8nOd28f2K7k/m/P7K0p9r-AQAJ.

The modified version has been proposed as a response to the analysis of Chee,

Jeong, Lee, and Ryu, which was announced in: https://groups.google.com/g/kpqc-bulletin/c/8nOd28f2K7k.

The analysis performed by Chee, Jeong, Lee, and Ryu recomputes the costs of

rank syndrome decoding (RSD) attacks and points out the inadequacy of the

suggested parameters w.r.t. the considered security levels.

Also, a direct attack has been found which exploits the shape of the public key

in order to neutralize the effect of the multiplication by polynomials P_I and

P_O. This leverages the fact that P divides P^b in order to obtain a congruence

modulo P from a congruence modulo P^b.

The modified version overcomes the attack mentioned above by replacing the

modulus polynomials P and P^b with two primitive polynomials P_1 and P_2 so that

the congruence modulo P_2 cannot be considered modulo P_1. Moreover, new sets

of parameters have been proposed to boost security against RSD attacks.

In our work, we use the same techniques pointed out in the analysis of REDOG,

considering the latest improvements to RSD attacks, to compute complexities

corresponding to the new suggested parameters. For more details on these

strategies and Sage scripts, see:

https://link.springer.com/chapter/10.1007/978-3-030-64837-4_17

and

https://eprint.iacr.org/2023/1205

and the "search-rsd.sage" script attached to this email.

We found that the parameters provided in the slides for the modified version

are still not satisfying the corresponding security parameters. The costs of

the attacks are reported in the following table

Security BBC+

128 93.72

192 105.90

256 114.10

This shows that the suggested parameters are still too low to fight off

RSD attacks.

Furthermore, we managed to reduce any instance of the modified Layered-ROLLO-I

to an instance of ROLLO-I which uses a smaller code. Also, the reduction

recovers the PO and PI parts of the private key, showing a leakage in the

system. We do this by computing R=PH/PP and considering the system of

equations \Psi(PI)RM = \Psi(z), where RM is the matrix of the multiplication

by R mod P2.

The choices of degrees of PI and z ensure that the system has as a solution the

representatives of PI and z modulo P1. Actually, we recover k*PI, where k is a

field constant, by computing the left kernel of the matrix consisting of the

last deg(PI)+1 columns of RM. Compute now PO/k from PP/(k*PI) and k*z from

PH/(PO/k). Finally, compute y/x from (k*z)/(k*PI).

The attached "attack.sage" script computes y/x on a Linux Mint VM in around

1.85 seconds for security 128, around 2.42 seconds for security 192 and around

4.21 seconds for security 256.

With the knowledge of PO/k and k*PI we can similarly reduce a modified

Layered-ROLLO-I ciphertext to a ROLLO-I ciphertext.

In the end, from a (q,m,n1,n2,r,d,degPI) instance of modified Layered-ROLLO-I

we obtain a (q,m,n1,r,d) instance of ROLLO-I. Computing the costs of the same

RSD attacks to this reduced instance of ROLLO-I we obtain

Security BBC+

128 84.48

192 95.04

256 99.69

Please find attached a more detailed document explaining our analysis.

All the best,

Tanja and Alex

Sep 22, 2023, 2:25:16 AM9/22/23

to KpqC-bulletin

Dear all,

We would like to inform you about our response to the recent analysis on the Layered ROLLO scheme. In the previous round, we modified the Layered ROLLO scheme in order to prevent the new attacks: Improved attack based on the RSD on rank weight r and direct attack by using two PKs P_H and P_P. However, the modified scheme still exhibited some vulnerabilities and we fixed those issues as follows.

For the first attack, we focused on a single attack scenario, but there are still several variants that can diminish security levels further. The positive aspect is that we can offset the reduction in security levels quite easily. In the proposed scheme, we further increase the rank weight 'r.' It is important to note that we have previously emphasized that decryption performance primarily depends on d rather than r.

For the second attack, we thought that using two co-prime moduli P^{(1)} and P^{(2)} can make a trapdoor for the proposed scheme. However, they found that low degree on P_I can be used to get an over-determined linear equation because the attacker knows that many zeros should be located in the higher degrees. In the key generation phase of the new scheme, the concept of polynomial masking is used, which was actually adopted in the initial submission. In detail, the PK P_P=P_IP_O is converted into P_P =P_O(P_I+P_NP^{(1)}), where
P_I+P_NP^{(1)} can have high degree and it makes an under-determined equation. With modified degree constraints, the remaining procedure of encapsulation and decapsulation remained unchanged. Another idea is exploiting P^{(1)} as SK, which hides the structure of P_H and the ideal LRPC codes. With the modified scheme, attack scenarios should be changed and written in the attached slide.

To this ends, we apply a slight change for the procedure and parameters of ROLLO based on our analysis. Accordingly, the implementation codes are also modified and newly uploaded in the web. New simulation shows that the performance gain is maintained. You may build and run a test. In addition, we found an error on the analyzed SL values originated from the typo in the sagemath codes. Thus, we modified the codes and recalculated the security level correctly.

We would like to express our gratitude to the researchers for their valuable analysis and suggestions regarding the vulnerabilities in the Layered ROLLO scheme.

Sincerely,

Chanki Kim, Young-Sik Kim, and Jong-Seon No

2023년 9월 5일 화요일 오전 8시 29분 8초 UTC+9에 Alex Pellegrini님이 작성:

Oct 3, 2023, 12:14:56 PM10/3/23

to KpqC-bulletin

Dear all,

I would like to inform you about my analysis on the new version of the

modified-Layered-ROLLO-I cryptosystem (NMLROLLO-I in short).

This analysis describes a full break of the system in the form of a message

recovery attack. Actually, this attack breaks every version of

Layered-ROLLO-I announced so far.

One can transform the ciphertext of NMLROLLO-I into a ciphertext of a weak

McEliece cryptosystem and decrypt the latter to obtain the shared secret.

The decryption of the weak McEliece ciphertext is made easy and fast thanks

to the low degree of the error vectors e_1 and e_2 as well as the knowledge of

where their zero coordinates are.

Indeed, I simply used the fact that the number of error-free positions in the

ciphertext is large enough to allow the use of linear algebra to efficiently

decrypt any NMLROLLO-I ciphertext.

The document attached to the email provides detailed explanations of my attack.

The sage script attached to this email faithfully implements the latest

specification of the cryptosystem and then proceeds to break 50 random

ciphertexts for a chosen set of parameters. It successfully decrypts all the

produced ciphertexts for level 128,192 and 256 on an average of 2.21s, 3.18s

and 6.65s respectively.

All the best,

Alex

I would like to inform you about my analysis on the new version of the

modified-Layered-ROLLO-I cryptosystem (NMLROLLO-I in short).

This analysis describes a full break of the system in the form of a message

recovery attack. Actually, this attack breaks every version of

Layered-ROLLO-I announced so far.

One can transform the ciphertext of NMLROLLO-I into a ciphertext of a weak

McEliece cryptosystem and decrypt the latter to obtain the shared secret.

The decryption of the weak McEliece ciphertext is made easy and fast thanks

to the low degree of the error vectors e_1 and e_2 as well as the knowledge of

where their zero coordinates are.

Indeed, I simply used the fact that the number of error-free positions in the

ciphertext is large enough to allow the use of linear algebra to efficiently

decrypt any NMLROLLO-I ciphertext.

The document attached to the email provides detailed explanations of my attack.

The sage script attached to this email faithfully implements the latest

specification of the cryptosystem and then proceeds to break 50 random

ciphertexts for a chosen set of parameters. It successfully decrypts all the

produced ciphertexts for level 128,192 and 256 on an average of 2.21s, 3.18s

and 6.65s respectively.

All the best,

Alex

Oct 20, 2023, 1:51:26 AM10/20/23

to KpqC-bulletin

Dear all,

We would like to inform you about our response to the recent analysis on the
Layered ROLLO scheme. In the previous round, we modified the Layered ROLLO
scheme in order to prevent the attack using PK. On the contrary, new
attacks are based on the fixed location of the error polynomial 𝑃_(𝐸,1)
and 𝑃_(𝐸,2)
on the ciphertext, which can recover the error vector directly. Note that the
new attack uses information set decoding from CT and PK and it is different
from the previous attack using PK only. Nevertheless, both attacks actually
originated from the fixed nonzero element indices by the low-degree polynomials
and thus, the corresponding solutions are similarly induced.

For the modified schemes, polynomial masking on CT can be used, which makes it hard to find exact values without guessing the noise term P_(N,C). Accordingly, we apply a parameter change including increased PK sizes compared to the those of layered ROLLO submission.

Note that the implementation codes are also modified and newly uploaded in the web. We also fixed some issues of constant implementation and memory leaks commented from KPQClean.

We would like to express our gratitude to the researchers for their valuable
analysis and suggestions regarding the vulnerabilities in the Layered ROLLO
scheme.

Sincerely,

Chanki Kim,
Young-Sik Kim,
and Jong-Seon
No

2023년 10월 4일 수요일 오전 1시 14분 56초 UTC+9에 Alex Pellegrini님이 작성:

Oct 22, 2023, 3:43:29 PM10/22/23

to KpqC-bulletin

Dear all,

I want to announce my analysis on the last patch of the Layered-ROLLO-I

cryptosystem, which consists in a fast message recovery attack working for the

security levels 128 and 192.

It is indeed possible to manipulate, and thereafter use, the public key data to

expose linear relations between the three additive factors of the masked

ciphertext. The attack uses two key observations:

- it is possible to get rid of one of the additive factors at a time and

thus, deal with only two unknown factors.

- Thanks to the size of the finite field, it is possible to construct

certain invertible matrices that allow to efficiently carry out

computations and recover the factors.

The attached document contains a detailed explanation of my attack, where I give

explicit formulas for recovering the plaintext from the corresponding ciphertext

and secret key.

The attached Sage script implements faithfully the new version of the system as

reported in the authors' slides, then proceeds to break 50 ciphertexts and

measures the consumed time.

Best regards,

Alex Pellegrini.

I want to announce my analysis on the last patch of the Layered-ROLLO-I

cryptosystem, which consists in a fast message recovery attack working for the

security levels 128 and 192.

It is indeed possible to manipulate, and thereafter use, the public key data to

expose linear relations between the three additive factors of the masked

ciphertext. The attack uses two key observations:

- it is possible to get rid of one of the additive factors at a time and

thus, deal with only two unknown factors.

- Thanks to the size of the finite field, it is possible to construct

certain invertible matrices that allow to efficiently carry out

computations and recover the factors.

The attached document contains a detailed explanation of my attack, where I give

explicit formulas for recovering the plaintext from the corresponding ciphertext

and secret key.

The attached Sage script implements faithfully the new version of the system as

reported in the authors' slides, then proceeds to break 50 ciphertexts and

measures the consumed time.

Best regards,

Alex Pellegrini.

Nov 5, 2023, 10:03:55 PM11/5/23

to KpqC-bulletin

Dear all,

We would like to inform you about our response to the 4th analysis on the
Layered ROLLO scheme. As in the response, the new scheme can successfully prevent
the new attack, which is achieved by using new PK regarding the inner modulus
P^{(1)}. However, The new PK can be used to additionally reveal some
information and new attacks can break the LROLLO-128 and LROLLO-192, where the
degree of error polynomials, represented by difference between n^{(1)} and
n^{(2)}, are small.

In the revised scheme, we increased the parameter of n^{(2)}, where the n^{(2)} increased nearly to 2n^{(1)} for LROLLO-128 and LROLLO-192. However, KEM scheme and parameter of LROLLO-256 are unchanged.

In
addition, we notice commented issues on the implementation on inner modulus
P^{(1)} , where P^{(1)} is declared as a fixed polynomial as in the initial
source code RBC in the ROLLO-I. In this case, the corresponding SL can be
lowered from the low-degree polynomial P_B/P^((1) ) when modulus polynomial P^((1) ) is
known by attacker. Therefore, We are trying to modify it with minimizing the
additional processing speed (i.e. processing cycle) until the end of 2nd submission. There seems to be some
options when considering the performance optimization.

We would like to express our gratitude to the researchers for their valuable
analysis and suggestions regarding the vulnerabilities in the Layered ROLLO
scheme.

Sincerely,

Chanki Kim, Young-Sik Kim, and Jong-Seon

No

2023년 10월 23일 월요일 오전 4시 43분 29초 UTC+9에 Alex Pellegrini님이 작성:

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu