Rainbow Signatures Overview and New Attacks
Rainbow signatures, introduced in 2005, offer good performance with small signatures but raise concerns due to large key sizes. This article explores the history of Rainbow, its vulnerabilities, new attacks, and the challenges posed by multivariate trapdoors. The overview delves into practical implications and the need for enhanced security measures in cryptographic systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Breaking Rainbow takes a weekend on a Laptop Ward Beullens IBM Research Europe Crypto 2022
Rainbow signatures (2005) Small signatures (66B), good performance. But large Keys (59KB) and not secure.
History of Rainbow 1997 Oil & Vinegar [Patarin] 2005 Rainbow [Ding, Schmidt] 2008 First wave of cryptanalysis dries up [KS98,BC05,BG06, DYCCC08, ] 2017 NIST PQC 20- 21 Improved MinRank attacks, RBS [BBCGPSTV20,BBBGNRT20,BBCPSV21, PS20,NIWDR20] 2021 Rainbow is one of signature finalists. 2021 New description of Rainbow, new attacks [Beu21] 2022 Practical break [this work]
New attacks log2(bit cost) *full key recovery attack (as opposed to universal forgery attack)
Oil & vinegar Rainbow Overview New attacks Conclusion
Multivariate Trapdoors ? ?? ? Public key is multivariate quadratic map ? = (?1? , ,??(?)):?? 2+ ?1?2+ 6 ?1?3+ ?3 2+ 2?1?2+ ?2 2+ ?1?2+ 3?2 2 ??? 7 ?1? = 2 ?1 ?2? = 5?1 ?3? = 4?1 2+ 6?2?3 ??? 7 2+ 4?2?3 ??? 7 ? is supposed to look random Sampling preimages for ? is hard. But, there is hidden structure in ? which allows to solve ? ? = ? for ?.
Trapdoor signatures ? ?? ? Public key: ? = (?1? , ,??(?)):?? Secret key: trapdoor information Signature for message ?: ? s.t. ? ? = ? ? How to trapdoor a MQ map?
Oil & Vinegar Trapdoor as presented in [Beu21] ? ?? ? Public key is a quadratic map: ? = (?1? , ,??(?)):?? Trapdoor is a subspaces ? ?? ? of dimension ? on which ? vanishes. ? ?? ? ?? ? ? ? . 0
Definition of differential: ? ?? ?, then we define it s differential at ? as: Let ?:?? ? ?? ?:? ? ? + ? ? ? ? ? ??:?? This is bi-linear in ? and ?: ??+? ? = ??? + ?? ? ??? + ? = ??? + ??(? )
Using the trapdoor ? ? ?? ?,?,? ?? ?. We want to find ? s.t. ? ? = ?. Given ?:?? ? uniformly at random. 1. Pick ? ?? 2. Solve for ? ? s.t. ? ? + ? = ?. ? ? + ? = ? ? + ? ? + ??(?) = ? Is a linear system of ? equations in ? variables. If no solution, retry with different ?.
Oil & vinegar Rainbow Overview New attacks Conclusion
Rainbow Trapdoor as presented in [Beu21] ? ?? ? Public key is a quadratic map: ? ? :?? Trapdoor consists of subspaces ?2 ?1 ?? ? ? and subspaces ? ?? ? s.t. ?? ? ?? ? ? ?? ?1 ? ?|O1 ?? ?2 ?|O2 . 0
Oil & vinegar Rainbow Overview New attacks Conclusion
Main idea ? ?? ? ?? ? ?2 ? ? ?? ?? ? ?? ? that sends ?2 to ?. For every ? we get a linear map ??:?? We want to find ?2. (This reduces to a MinRank problem [Beu21]) Main observation: ?? is more likely to have a kernel vector in ?2.
?? is likely to have kernel vectors in ?2 ?? ? ? ?? ?2 ? ? ?? ?? ? Average number of non-zero kernel vectors in ?2 is ?2 1 1 ? The probability of a non-zero kernel vector in ?2 is 1/(? 1)
New Attack: ?, hope that ker(??) ?2 is non-trivial 1. Guess ? ?? 2. Solve ??? = 0 ? ? = 0 3. If no solutions, return to 1. R2SL1: Attempting to solving the system takes 3 hours 32 minutes using standard techniques. (Wiedemann-XL) Repeat ? 1 = 15 times 53 hours (one weekend)
Finishing the attack We have a single vector ? in ?2. How to find the full sk key (?1,?2,?)? 1) ? ??? ? , so we learn all of ? 2) Solve for all ? s.t. ??? ? for all ?, reveals all of ?2 ?? ? ? ?? ? ? ?? ?1 ? ?|O1 ?? ?2 ?|O2 . 0
Finishing the attack We have a single vector ? in ?2. How to find the full sk key (?1,?2,?)? 1) ? ??? ? , so we learn all of ? 2) Solve for all ? s.t. ??? ? for all ?, reveals all of ?2 3) Take quotient by ?2 and ?. Break the remaining Oil & Vinegar key with existing attacks (e.g. Kipnis-Shamir) ?/?2 ?? ?/? ?1/?2 ?? ? .0
Oil & vinegar Rainbow Overview New attacks Conclusion
Wrapping up: Rainbow is not secure. (R2SL1 is broken in practice.) Increasing parameters would be expensive 4.4x larger PK 2.5xlarger signatures 5x slower Oil & Vinegar is much simpler and now more efficient/compact. Questions?
