brunoproduit / roca

Implementation of the ROCA attack

Implementation of the ROCA attack (CVE-2017-15361)

This is the implementation of the paper Return of the Coppersmith attack.

The implementation is in python 2.7 and uses the Howgrave-Graham code from RSA-and-LLL-attacks.

For the detection of vulnerable keys, the code from the original authors of the paper is used (detect.py) crocs-muni

PR's welcome!

Usage

$ python roca.py <path to key> -j <number of cores>

$ python optimization.py <path to key> -j <number of cores>

Test

$ cd src
$ cp ../test/test_roca.py .
$ python test_roca.py

Optimization

The optimization is based on an analysis of properties observed from real keys exported from affected card (Infineon JavaCard SLJ52GCA150). The parameters a' and k' turn out to have a lower entropy than stated in the original paper.

a' is fixed at the MSB and biased to be even, This is used to shrink the bruteforce range and speedup the attack.

HPC

$ sbatch slurm.sh <path to key>

Organization of the Code

data/512.pem -> Vulnerable RSA 512-bit key

LICENSE -> APACHE 2.0

README.md -> This file

requirements.txt -> Python 2.7 requirements

HPC/optimization_hpc.py -> modified attack implemetation for HPC

HPC/slurm.sh -> SLURM start script for the attack

HPC/split_iteration.py -> helper for SCRUM

src/optimization.py -> Optimized ROCA attack

src/params.py -> Used to calculate the parameters

src/roca.py -> Non-optimized attack

src/roca.sage -> Pure sage version of the attack

src/detect.py -> crocs-muni

test/test_roca.py -> Test the attack

roca's Issues

Negative estimated benchmark time for 1024 bit keys with optimization

I create some 1024 public keys for testing. With the optimization a negative time is calculated. This means (top - start) is negative. Why is this and does this impact a successful attack?

$ python3 optimization.py -j 96 ~/roca/keys/generated-1024.pub [+] Importing key [+] Key is vulnerable [+] RSA-1024 key [+] N = 168624943669182758974280215781456011569038629744526376535337045252130727107381534170843439375955244315238908028241243340891689953428487159534726263781126648823691789933070782777310828563238437149205109600525674261831766067602042561054635704257297596345836435239010691607435325759065388907902349357304317653381 [+] c' = 850102604 [+] Time for 1 coppersmith iteration: 0.02 seconds [+] Estimated (worst case) time needed for the attack: -20801.3 seconds
and
$ python3 optimization.py -j 96 ~/roca/keys/generated-1024-2.pub [+] Importing key [+] Key is vulnerable [+] RSA-1024 key [+] N = 164120015764097722873438454177657444658349361286249714149317571057211681342705706088083034394301304785150344998122085256288378726566732045477079852530000003998378252495184330586999905751865897641752300811879885650760909043777375010103534231282193794056566679087421654114716835957907434904884516675168844585517 [+] c' = 364568529 [+] c' is odd: we only need to iterate over even a' [+] Time for 1 coppersmith iteration: 0.02 seconds [+] Estimated (worst case) time needed for the attack: -36929.93 seconds

Bad indentation and work distribution

Hi
I had tried to use your code and noticed three things:

• indentation is wrong in roca.py and optimization.py scripts:

        a_prime = start
        while a_prime < stop:
          if manager.finished:
            break 
            
            # Construct polynomial
            m_inv = int(inverse_mod(M_prime, N))

  Infinite loop over if manager.finished.

• Distribution of work (below # Spawn processes) is wrong. For example with 512 bit key and 7 cpus:

   top = 0xc5772
   c_prime = 0x65ab4
   ord_prime = 0x125430
   start | stop |  stop-start
   0x80000 | 0x1c359 | -0x63ca7
   0x1c359 | 0x386b2 | 0x1c359
   0x386b2 | 0x54a0c | 0x1c35a
   0x54a0c | 0x70d65 | 0x1c359
   0x70d65 | 0x8d0bf | 0x1c35a
   0x8d0bf | 0xa9418 | 0x1c359
   0xa9418 | 0xc5772 | 0x1c35a
  

  First worker returns immediately, and next four do unnecessary jobs.

  Should be something like:

  top = 0xc5772
  c_prime = 0x65ab4
  ord_prime = 0x125430
  start | stop |  stop-start
  0x80000 | 0x89ec8 | 0x9ec8
  0x89ec8 | 0x93d90 | 0x9ec8
  0x93d90 | 0x9dc58 | 0x9ec8
  0x9dc58 | 0xa7b20 | 0x9ec8
  0xa7b20 | 0xb19e8 | 0x9ec8
  0xb19e8 | 0xbb8b0 | 0x9ec8
  0xbb8b0 | 0xc5778 | 0x9ec8
  

• manager.finished not working, when one worker finds the factorization, other workers don't stop