Skip to content

Python implementations of cryptographic attacks and utilities.

License

Notifications You must be signed in to change notification settings

KeL3vRa/crypto-attacks

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Introduction

Python implementations of cryptographic attacks and utilities.

Requirements

You can check your SageMath Python version using the following command:

$ sage -python --version
Python 3.9.0

If your SageMath Python version is older than 3.9.0, some features in some scripts might not work.

Usage

Unit tests are located in the test directory and can be executed using the unittest module or using pytest. This should not take very long, perhaps a few minutes depending on your machine.

To run a specific attack, you must add the code to the proper file before executing it.

Example

For example, you want to attack RSA using the Boneh-Durfee attack, with the following parameters (taken from test_rsa.py):

N = 88320836926176610260238895174120738360949322009576866758081671082752401596826820274141832913391890604999466444724537056453777218596634375604879123818123658076245218807184443147162102569631427096787406420042132112746340310992380094474893565028303466135529032341382899333117011402408049370805729286122880037249
e = 36224751658507610673165956970793195381480143363550601971796688201449789736497322700382657163240771111376677180786660893671085854060092736865293791299460933460067267613023891500397200389824179925263846148644777638774319680682025117466596019474987378275216579013846855328009375540444176771945272078755317168511

You add the following code at the bottom of the boneh_durfee.py file:

import logging

# Some logging so we can see what's happening.
logging.basicConfig(level=logging.DEBUG)

N = 88320836926176610260238895174120738360949322009576866758081671082752401596826820274141832913391890604999466444724537056453777218596634375604879123818123658076245218807184443147162102569631427096787406420042132112746340310992380094474893565028303466135529032341382899333117011402408049370805729286122880037249
e = 36224751658507610673165956970793195381480143363550601971796688201449789736497322700382657163240771111376677180786660893671085854060092736865293791299460933460067267613023891500397200389824179925263846148644777638774319680682025117466596019474987378275216579013846855328009375540444176771945272078755317168511
p_bits = 512
delta = 0.26

p, q = attack(N, e, p_bits, delta=delta)
assert p * q == N
print(f"Found p = {p} and q = {q}")

Then you can simply execute the file using Sage. It does not matter where you execute it from, the Python path is automagically set:

[crypto-attacks]$ sage -python attacks/rsa/boneh_durfee.py
INFO:root:Trying m = 1, t = 0...
DEBUG:root:Generating shifts...
DEBUG:root:Filling the lattice (3 x 3)...
DEBUG:root:Executing the LLL algorithm...
DEBUG:root:Reconstructing polynomials...
DEBUG:root:Polynomial at row 0 is constant, ignoring...
DEBUG:root:Reconstructed 2 polynomials
DEBUG:root:Using Groebner basis method to find roots...
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 1
INFO:root:Trying m = 2, t = 0...
DEBUG:root:Generating shifts...
DEBUG:root:Filling the lattice (6 x 6)...
DEBUG:root:Executing the LLL algorithm...
DEBUG:root:Reconstructing polynomials...
DEBUG:root:Polynomial at row 0 is constant, ignoring...
DEBUG:root:Reconstructed 5 polynomials
DEBUG:root:Using Groebner basis method to find roots...
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 1
INFO:root:Trying m = 3, t = 1...
DEBUG:root:Generating shifts...
DEBUG:root:Filling the lattice (11 x 11)...
DEBUG:root:Executing the LLL algorithm...
DEBUG:root:Reconstructing polynomials...
DEBUG:root:Polynomial at row 8 is constant, ignoring...
DEBUG:root:Reconstructed 10 polynomials
DEBUG:root:Using Groebner basis method to find roots...
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 1
DEBUG:root:Groebner basis length: 2
Found p = 7866790440964395011005623971351568677139336343167390105188826934257986271072664643571727955882500173182140478082778193338086048035817634545367411924942763 and q = 11227048386374621771175649743442169526805922745751610531569607663416378302561807690656370394330458335919244239976798600743588701676542461805061598571009923

You can also call the attacks from other Python files, but then you'll have to fix the Python path yourself.

Implemented attacks

Approximate Common Divisor

CBC

CBC + CBC-MAC

CBC-MAC

CTR

ECB

Elliptic Curve Cryptography

ElGamal Encryption

ElgGamal Signature

Factorization

GCM

  • Forbidden attack [More information: Joux A., "Authentication Failures in NIST version of GCM"]

Hidden Number Problem

  • Extended hidden number problem [More information: Hlavac M., Rosa T., "Extended Hidden Number Problem and Its Cryptanalytic Applications" (Section 4)]
  • Fourier analysis attack
  • Lattice-based attack

IGE

Knapsack Cryptosystems

  • Low density attack [More information: Coster M. J. et al., "Improved low-density subset sum algorithms"]

Linear Congruential Generators

Learning With Errors

  • Arora-Ge attack [More information: "The Learning with Errors Problem: Algorithms" (Section 1)]
  • Blum-Kalai-Wasserman attack
  • Lattice reduction attack

Mersenne Twister

One-time Pad

Pseudoprimes

RC4

RSA

Shamir's Secret Sharing

Other interesting implementations

Elliptic Curve Generation

  • MNT curves
  • Prescribed order
  • Prescribed trace
  • Supersingular curves

Small Roots

About

Python implementations of cryptographic attacks and utilities.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 100.0%