brunoproduit / roca Goto Github PK

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

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