BreakingRainbow
Scripts for the 'Breaking Rainbow takes a Weekend on a Laptop' paper.
We have the following scripts:
- SimpleAttack.sage: Contains an implementation of the simple attack. Only constructs the \hat{P} system. You can use the block wiedemann XL implementation of Niederhagen to find a solution. http://polycephaly.org/projects/xl
- SimpleAttackRankExp.sage: Script to reproduce tables 2 and 3.
- CombinedAttackRankExp.sage: Script to reproduce table 4.
- SimpleAttackStatistics.sage: Counts how many guesses are good.
- Rainbow.sage: Used by the other scripts to generate a Rainbow public key
Demonstration of the full attack
The "Attack_demo" folder contains two sage scripts that demonstrate the full attack.
Running KeyGen.sage creates a rainbow key pair and writes the public key to a file. By default a toy parameter set is used, but the parameters can be changed in the script.
Running Full_Attack.sage compiles the WXL algorithm, and repeatedly makes a guess x, builds an MQ system and tries to solve it. Once a solution is found it completes the key recovery attack, writes the recovered secret key to a file, and compares it to the original secret key to verify that the attack was succesful.
using the wiedemann XL implmentation of Niederhagen et al.
The SimpleAttack.sage script creates a file named 'systemN-M.txt' for some values of N, M. You need to compile the wiedemann XL implementation with these values of N,M. For example, the NIST SL 1 parameters result in 'system63-30.txt'. (N is one less than the value N in the paper, because the homogenous system with N variables is converted to a inhomogenous system by putting x_N = 1.)
So in the XL Makefile you should set
Q = 16
M = 63
N = 30
After compiling, you can then run the XL algorithm with:
./xl --challenge system63-30.txt --all