crypto-attacks - Python implementations of cryptographic attacks an

项目说明

Introduction

Python implementations of cryptographic attacks and utilities.

Requirements

* SageMath with Python 3.9
* PyCryptodome

You can check your SageMath Python using the following command:

If your SageMath Python 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 deser 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 , therefore wasting the time spent reducing. Hence, this is a trade-off.

In the current 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 = 1 until 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 of the attack you're trying to use (with known results), and determine the m value which results in good lattice . Then directly call the attack method with the correct m value.

Implemented attacks

Approximate Common Divisor

* [x] Multi polynomial attack [^acd_mp]
* [x] Orthogonal based attack [^acd_ol]
* [x] Simultaneous Diophantine approximation attack [^acd_sda]

CBC

* [x] Bit flipping attack
* [x] I attack
* [x] Padding oracle attack

CBC + CBC-MAC

* [x] Key reuse attack (encrypt-and-MAC)
* [x] Key reuse attack (encrypt-then-MAC)
* [x] Key reuse attack (MAC-then-encrypt)

CBC-MAC

* [x] Length extension attack

CTR

* [x] Bit flipping attack
* [x] CRIME attack
* [x] Separator oracle attack

ECB

* [x] Plaintext recovery attack
* [x] Plaintext recovery attack (harder )
* [x] Plaintext recovery attack (hardest )

Elliptic Cur

* [x] ECDSA nonce reuse attack
* [x] Frey-Ruck attack [^ecc_frey_ruck_attack]
* [x] MO [^ecc_mo]
* [x] Parameter recovery
* [x] Singular cur
* [x] Smart's attack (with curves o fields) [^ecc_smart_attack1] [^ecc_smart_attack2]

ElGamal Encryption

* [x] Nonce reuse attack
* [x] Unsafe generator attack

ElgGamal Signature

* [ ] Bleichenbacher's attack
* [ ] Khadir's attack
* [x] Nonce reuse attack

Factorization

* [x] Base con factorization
* [x] Branch and prune attack [^factorization_branch_and_prune]
* [x] Complex multiplication (elliptic cur [^factorization_complex_multiplication]
* [x] Coppersmith factorization
* [x] Fermat factorization
* [x] Ghafar-Ariffin-Asbullah attack [^factorization_gaa]
* [x] Implicit factorization [^factorization_implicit]
* [x] Known phi factorization [^factorization_known_phi]
* [x] ROCA [^factorization_roca]
* [x] Shor's algorithm (classical) [^factorization_shor]
* [x] Twin primes factorization
* [x] Factorization of unbalanced moduli [^factorization_unbalanced]

GCM

* [x] Forbidden attack [^gcm_forbidden_attack]

Hidden Number Problem

With applications to partial (EC)DSA nonce exposure.
* [x] Extended hidden number problem [^hnp_extended_hnp]
* [ ] Fourier analysis attack
* [x] Lattice-based attack

IGE

* [x] Padding oracle attack

Knapsack Cryptosystems

* [x] Low density attack [^knapsack_low_density]

Linear Congruential Generators

* [x] LCG parameter recovery
* [x] Truncated LCG parameter recovery [^lcg_truncated_parameter_recovery]
* [x] Truncated LCG state recovery [^lcg_truncated_state_recovery]

Learning With Errors

* [x] Arora-Ge attack [^lwe_arora_ge]
* [ ] Blum-Kalai-Wasserman attack
* [ ] Lattice reduction attack

Mersenne Twister

* [x] State recovery

One-time Pad

* [x] Key reuse

Pseudoprimes

* [x] Generating Miller-Rabin pseudoprimes [^pseudoprimes_miller_rabin]

RC4

* [x] Fluhrer-Mantin-Shamir attack

RSA

* [x] Bleichenbacher's attack [^rsa_bleichenbacher]
* [x] Bleichenbacher's signature forgery attack
* [x] Boneh-Durfee attack [^rsa_boneh_durfee]
* [x] Cherkaoui-Semmouni's attack [^rsa_cherkaoui_semmouni]
* [x] Common modulus attack
* [x] CRT fault attack
* [x] d fault attack
* [x] Desmedt-Odlyzko attack (selecti) [^rsa_desmedt_odlyzko]
* [x] Extended Wiener's attack [^rsa_extended_wiener_attack]
* [x] Hastad's broadcast attack
* [x] Known CRT exponents attack [^rsa_known_crt_exponents]
* [x] Partial known CRT exponents attack [^rsa_partial_known_crt_exponents]
* [x] Known private exponent attack
* [x] Low public exponent attack
* [x] LSB oracle (parity oracle) attack
* [x] Manger's attack [^rsa_manger]
* [x] Nitaj's CRT-RSA attack [^rsa_nitaj_crt_rsa]
* [x] Non coprime public exponent attack [^rsa_non_coprime_exponent]
* [x] Partial key exposure [^rsa_partial_key_exposure1] [^rsa_partial_key_exposure2] [^rsa_partial_key_exposure3]
* [x] Related message attack
* [x] Stereotyped message attack
* [x] Wiener's attack
* [x] Wiener's attack for Common Prime RSA [^rsa_wiener_attack_common_prime]
* [x] Wiener's attack (Heuristic lattice ) [^rsa_wiener_attack_lattice] [^rsa_wiener_attack_lattice_extended] [^small_roots_aono]

Shamir's Secret Sharing

* [x] Deterministic coefficients
* [x] Share forgery

Other interesting implementations

* [x] Adleman-Manders-Miller root extraction method [^adleman_manders_miller]
* [x] Fast CRT using di
* [x] Fast modular in
* [x] Linear Hensel lifting
* [ ] Quadratic Hensel lifting
* [x] Babai's Nearest Plane Algorithm
* [x] Matrix discrete logarithm
* [x] Matrix discrete logarithm (equation)
* [x] PartialInteger
* [x] Fast polynomial GCD using half GCD

Elliptic Cur

* [x] Complex multiplication
* [x] Anomalous curves
* [x] MNT curves
* [x] Prescribed order
* [x] Prescribed trace
* [x] Supersingular curves

Small Roots

* [x] Polynomial roots using Groebner bases
* [x] Polynomial roots using resultants
* [x] Polynomial roots using Sage (triangular decomposition)
* [x] Aono method (Minkowski sum lattice) [^small_roots_aono]
* [x] Blomer-May method [^small_roots_blomer_may]
* [x] Boneh-Durfee method [^rsa_boneh_durfee]
* [x] Coron method [^small_roots_coron]
* [x] Coron method (direct) [^small_roots_coron_direct]
* [x] Ernst et al. methods [^rsa_partial_key_exposure2]
* [x] Herrmann-May method (unra linearization) [^small_roots_herrmann_may]
* [x] Herrmann-May method (modular multi) [^small_roots_herrmann_may_multi]
* [x] Howgra method [^small_roots_howgra]
* [x] Jochemsz-May method (modular roots) [^small_roots_jochemsz_may_modular]
* [x] Jochemsz-May method (integer roots) [^small_roots_jochemsz_may_integer]
* [x] 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 Cur" (Section 3)
[^ecc_mo]: Harasawa R. et al., "Comparing the MOV and FR Reductions in Elliptic Cur" (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 "
[^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 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., "Impro 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 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 Ad 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 with Primes Sharing Most Significant Bits"
[^rsa_desmedt_odlyzko]: Coron J. et al., "Practical Cryptanalysis of ISO 9796-2 and EM (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 Multi Polynomials with New Applications in Attacking RSA " (Section 5)
[^rsa_wiener_attack_lattice]: Nguyen P. Q., "Public-Key Cryptanalysis"
[^rsa_wiener_attack_lattice_extended]: Howgra 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 Re" (Section 5)

[^small_roots_aono]: Aono Y., "Minkowski sum based lattice construction for multi 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 Bi Integer Polynomial Equations Re"
[^small_roots_coron_direct]: Coron J., "Finding Small Roots of Bi 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_multi]: Herrmann M., May A., "Solving Linear Equations Modulo Di: On Factoring Given Any Bits" (Section 3 and 4)
[^small_roots_howgra]: May A., "New RSA Using Lattice Reduction Methods" (Section 3.2)
[^small_roots_jochemsz_may_modular]: Jochemsz E., May A., "A Strategy for Finding Roots of Multi Polynomials with New Applications in Attacking RSA " (Section 2.1)
[^small_roots_jochemsz_may_integer]: Jochemsz E., May A., "A Strategy for Finding Roots of Multi Polynomials with New Applications in Attacking RSA " (Section 2.2)
[^small_roots_nitaj_fouotsa]: Nitaj A., Fouotsa E., "A New Attack on RSA and Demytko's Elliptic Cur"

项目信息

开发语言：Python

Star 数：1289

技术要点

该项目属于CTF思路方向的开源资源，代码结构清晰，适合安全研究人员学习参考。项目围绕Python implementations of cryptographic attacks and utilities.展开，提供了可运行的实现，对理解相关安全机制、工具原理与攻防技术具有较高的研究价值。

从技术实现角度看，此类项目的核心在于对底层原理的深入理解与工程化落地。开发者在研究过程中可以结合官方文档与社区讨论，梳理项目的初始化流程、核心模块职责与数据流转，逐步掌握其中的技术细节与设计思路。

使用与学习建议

1. 下载源码压缩包，解压到本地环境。

2. 根据项目类型准备对应的运行环境与依赖。

3. 按照 README 中的步骤完成配置与部署。

4. 在隔离的测试环境中运行验证，避免影响生产系统。

免责声明

本资源来源于开源社区，仅供安全研究、技术学习与合法授权范围内的攻防演练使用，请勿用于任何非法或侵害他人权益的用途。使用本项目产生的一切后果由使用者自行承担。