Analysis of Layered ROLLO-I

776 views
Skip to first unread message

Nari Lee

unread,
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

--
[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).
Analysis on Layered ROLLO-I.pdf

Chanki Kim

unread,
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님이 작성:
Layered_ROLLO_Documentation.pdf

Alex Pellegrini

unread,
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
search-rsd.sage
attack.sage
document.pdf

Chanki Kim

unread,
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님이 작성:
New_Comments_230922.pdf

Alex Pellegrini

unread,
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
document.pdf
message-recovery.sage

Chanki Kim

unread,
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님이 작성:
New_Comments_231020.pdf

Alex Pellegrini

unread,
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.
attack20231022.pdf
message-recovery20231022.sage

Chanki Kim

unread,
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님이 작성:
New_Comments_231105.pdf
Reply all
Reply to author
Forward
0 new messages