Analysis of Layered ROLLO-I
Nari Lee
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
Chanki Kim
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
Alex Pellegrini
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
Chanki Kim
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
Alex Pellegrini
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
Chanki Kim
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
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.
Chanki Kim
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