Introduction
Python implementations of cryptographic attacks and utilities.
Requirements
SageMath with Python 3.9
You can check your SageMath Python version using the following command:
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):
You add the following code at the bottom of the boneh_durfee.py file:
Then you can simply execute the file using Sage. It does not matter where you execute it from, the Python path is automagically set (you can also call the attacks from other Python files, but then you'll have to fix the Python path yourself):
The parameters m and t as shown in the output log deserve special attention. These parameters are used in many lattice-based (small roots) algorithms to tune the lattice size. Conceptually, m (sometimes called k) and t represent the number of "shifts" used in the lattice, which is roughly equal or proportional to the number of rows. Therefore, increasing m and t will increase the size of the lattice, which also increases the time required to perform lattice reduction (currently using LLL). On the other hand, if m and t are too low, it is possible that the lattice reduction will not result in appropriate vectors, therefore wasting the time spent reducing. Hence, this is a trade-off.
In the current version of the project, m must always be provided by the user (the default value is set to 1). t can, in some cases, be computed based on the specific small roots method used by the attack. However it can still be tweaked by the user. In general, there are two ways to use these kinds of parameters:
Implement a loop which starts at
m = 1until an answer is found (example below). This is a simple approach, but risks wasting time on futile computations with too small lattices.
Implement a debug version of the attack you're trying to use (with known results), and determine the
mvalue which results in good lattice vectors. Then directly call the attack method with the correctmvalue.
Implemented attacks
Approximate Common Divisor
Multivariate polynomial attack [^acd_mp]
Orthogonal based attack [^acd_ol]
CBC
CBC + CBC-MAC
CBC-MAC
CTR
ECB
Elliptic Curve Cryptography
Frey-Ruck attack [^ecc_frey_ruck_attack]
MOV attack [^ecc_mov_attack]
Smart's attack (with curves over extension fields) [^ecc_smart_attack1] [^ecc_smart_attack2]
ElGamal Encryption
ElgGamal Signature
Bleichenbacher's attack
Khadir's attack
Factorization
Branch and prune attack [^factorization_branch_and_prune]
Complex multiplication (elliptic curve) factorization [^factorization_complex_multiplication]
Ghafar-Ariffin-Asbullah attack [^factorization_gaa]
Implicit factorization [^factorization_implicit]
Known phi factorization [^factorization_known_phi]
ROCA [^factorization_roca]
Shor's algorithm (classical) [^factorization_shor]
Factorization of unbalanced moduli [^factorization_unbalanced]
GCM
Forbidden attack [^gcm_forbidden_attack]
Hidden Number Problem
With applications to partial (EC)DSA nonce exposure.
Extended hidden number problem [^hnp_extended_hnp]
Fourier analysis attack
IGE
Knapsack Cryptosystems
Low density attack [^knapsack_low_density]
Linear Congruential Generators
Truncated LCG parameter recovery [^lcg_truncated_parameter_recovery]
Truncated LCG state recovery [^lcg_truncated_state_recovery]
Learning With Errors
Arora-Ge attack [^lwe_arora_ge]
Blum-Kalai-Wasserman attack
Lattice reduction attack
Mersenne Twister
One-time Pad
Pseudoprimes
Generating Miller-Rabin pseudoprimes [^pseudoprimes_miller_rabin]
RC4
RSA
Bleichenbacher's attack [^rsa_bleichenbacher]
Boneh-Durfee attack [^rsa_boneh_durfee]
Cherkaoui-Semmouni's attack [^rsa_cherkaoui_semmouni]
Desmedt-Odlyzko attack (selective forgery) [^rsa_desmedt_odlyzko]
Extended Wiener's attack [^rsa_extended_wiener_attack]
Known CRT exponents attack [^rsa_known_crt_exponents]
Partial known CRT exponents attack [^rsa_partial_known_crt_exponents]
Manger's attack [^rsa_manger]
Nitaj's CRT-RSA attack [^rsa_nitaj_crt_rsa]
Non coprime public exponent attack [^rsa_non_coprime_exponent]
Partial key exposure [^rsa_partial_key_exposure1] [^rsa_partial_key_exposure2] [^rsa_partial_key_exposure3]
Wiener's attack for Common Prime RSA [^rsa_wiener_attack_common_prime]
Wiener's attack (Heuristic lattice variant) [^rsa_wiener_attack_lattice] [^rsa_wiener_attack_lattice_extended] [^small_roots_aono]
Shamir's Secret Sharing
Other interesting implementations
Adleman-Manders-Miller root extraction method [^adleman_manders_miller]
Quadratic Hensel lifting
Elliptic Curve Generation
Small Roots
Polynomial roots using Sage variety (triangular decomposition)
Aono method (Minkowski sum lattice) [^small_roots_aono]
Blomer-May method [^small_roots_blomer_may]
Boneh-Durfee method [^rsa_boneh_durfee]
Coron method [^small_roots_coron]
Coron method (direct) [^small_roots_coron_direct]
Ernst et al. methods [^rsa_partial_key_exposure2]
Herrmann-May method (unravelled linearization) [^small_roots_herrmann_may]
Herrmann-May method (modular multivariate) [^small_roots_herrmann_may_multivariate]
Howgrave-Graham method [^small_roots_howgrave_graham]
Jochemsz-May method (modular roots) [^small_roots_jochemsz_may_modular]
Jochemsz-May method (integer roots) [^small_roots_jochemsz_may_integer]
Nitaj-Fouotsa method [^small_roots_nitaj_fouotsa]
[^acd_mp]: Galbraith D. S. et al., "Algorithms for the Approximate Common Divisor Problem" (Section 5) [^acd_ol]: Galbraith D. S. et al., "Algorithms for the Approximate Common Divisor Problem" (Section 4) [^acd_sda]: Galbraith D. S. et al., "Algorithms for the Approximate Common Divisor Problem" (Section 3)
[^ecc_frey_ruck_attack]: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography" (Section 3) [^ecc_mov_attack]: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Curve Cryptography" (Section 2) [^ecc_smart_attack1]: Smart N. P., "The Discrete Logarithm Problem on Elliptic Curves of Trace One" [^ecc_smart_attack2]: Hofman S. J., "The Discrete Logarithm Problem on Anomalous Elliptic Curves"
[^factorization_branch_and_prune]: Heninger N., Shacham H., "Reconstructing RSA Private Keys from Random Key Bits" [^factorization_complex_multiplication]: Sedlacek V. et al., "I want to break square-free: The 4p - 1 factorization method and its RSA backdoor viability" [^factorization_gaa]: Ghafar AHA. et al., "A New LSB Attack on Special-Structured RSA Primes" [^factorization_implicit]: Nitaj A., Ariffin MRK., "Implicit factorization of unbalanced RSA moduli" [^factorization_known_phi]: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3) [^factorization_roca]: Nemec M. et al., "The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli" [^factorization_shor]: M. Johnston A., "Shor’s Algorithm and Factoring: Don’t Throw Away the Odd Orders" [^factorization_unbalanced]: Brier E. et al., "Factoring Unbalanced Moduli with Known Bits" (Section 4)
[^gcm_forbidden_attack]: Joux A., "Authentication Failures in NIST version of GCM"
[^hnp_extended_hnp]: Hlavac M., Rosa T., "Extended Hidden Number Problem and Its Cryptanalytic Applications" (Section 4)
[^knapsack_low_density]: Coster M. J. et al., "Improved low-density subset sum algorithms"
[^lcg_truncated_parameter_recovery]: Contini S., Shparlinski I. E., "On Stern's Attack Against Secret Truncated Linear Congruential Generators" [^lcg_truncated_state_recovery]: Frieze, A. et al., "Reconstructing Truncated Integer Variables Satisfying Linear Congruences"
[^lwe_arora_ge]: "The Learning with Errors Problem: Algorithms" (Section 1)
[^pseudoprimes_miller_rabin]: R. Albrecht M. et al., "Prime and Prejudice: Primality Testing Under Adversarial Conditions"
[^rsa_bleichenbacher]: Bleichenbacher D., "Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1" [^rsa_boneh_durfee]: Boneh D., Durfee G., "Cryptanalysis of RSA with Private Key d Less than N^0.292" [^rsa_cherkaoui_semmouni]: Cherkaoui-Semmouni M. et al., "Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits" [^rsa_desmedt_odlyzko]: Coron J. et al., "Practical Cryptanalysis of ISO 9796-2 and EMV Signatures (Section 3)" [^rsa_extended_wiener_attack]: Dujella A., "Continued fractions and RSA with small secret exponent" [^rsa_known_crt_exponents]: Campagna M., Sethi A., "Key Recovery Method for CRT Implementation of RSA" [^rsa_partial_known_crt_exponents]: May A., Nowakowski J., Sarkar S., "Approximate Divisor Multiples - Factoring with Only a Third of the Secret CRT-Exponents" [^rsa_manger]: Manger J., "A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0" [^rsa_nitaj_crt_rsa]: Nitaj A., "A new attack on RSA and CRT-RSA" [^rsa_non_coprime_exponent]: Shumow D., "Incorrectly Generated RSA Keys: How To Recover Lost Plaintexts" [^rsa_partial_key_exposure1]: Boneh D., Durfee G., Frankel Y., "An Attack on RSA Given a Small Fraction of the Private Key Bits" [^rsa_partial_key_exposure2]: Ernst M. et al., "Partial Key Exposure Attacks on RSA Up to Full Size Exponents" [^rsa_partial_key_exposure3]: Blomer J., May A., "New Partial Key Exposure Attacks on RSA" [^rsa_wiener_attack_common_prime]: Jochemsz E., May A., "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants" (Section 5) [^rsa_wiener_attack_lattice]: Nguyen P. Q., "Public-Key Cryptanalysis" [^rsa_wiener_attack_lattice_extended]: Howgrave-Graham N., Seifert J., "Extending Wiener’s Attack in the Presence of Many Decrypting Exponents"
[^adleman_manders_miller]: Cao Z. et al., "Adleman-Manders-Miller Root Extraction Method Revisited" (Section 5)
[^small_roots_aono]: Aono Y., "Minkowski sum based lattice construction for multivariate simultaneous Coppersmith's technique and applications to RSA" (Section 4) [^small_roots_blomer_may]: Blomer J., May A., "New Partial Key Exposure Attacks on RSA" (Section 6) [^small_roots_coron]: Coron J., "Finding Small Roots of Bivariate Integer Polynomial Equations Revisited" [^small_roots_coron_direct]: Coron J., "Finding Small Roots of Bivariate Integer Polynomial Equations: a Direct Approach" [^small_roots_herrmann_may]: Herrmann M., May A., "Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA" [^small_roots_herrmann_may_multivariate]: Herrmann M., May A., "Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits" (Section 3 and 4) [^small_roots_howgrave_graham]: May A., "New RSA Vulnerabilities Using Lattice Reduction Methods" (Section 3.2) [^small_roots_jochemsz_may_modular]: Jochemsz E., May A., "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants" (Section 2.1) [^small_roots_jochemsz_may_integer]: Jochemsz E., May A., "A Strategy for Finding Roots of Multivariate Polynomials with New Applications in Attacking RSA Variants" (Section 2.2) [^small_roots_nitaj_fouotsa]: Nitaj A., Fouotsa E., "A New Attack on RSA and Demytko's Elliptic Curve Cryptosystem"