Crypto Attacks

A collection of cryptographic attack implementations and proofs-of-concept in SageMath and Python.

Requirements

• SageMath, Python 3
• PyCryptodome

Structure and Contents

AES Attacks

• CBC Padding Oracle Attack - Recover plaintext by modifying ciphertext blocks and using a valid/invalid padding oracle to infer bytes.
• CTR Bit Flipping Attack - Modify ciphertext to produce a chosen plaintext upon decryption.
• ECB Byte At A Time - Recover secret appended to controlled input using an ECB encryption oracle.
• ECB Cut and Paste Attack - Create and rearrenge encrypted blocks to forge a new message.

Diffie-Hellman Attacks

• Discrete log in GL(n, p) – Solve discrete log in GL(n, p).
• Pohlig-Hellman Attack – Solve discrete log when the group order is smooth (factorable into small primes).
• Small Subgroup Attack – Solve discrete log when the order of the group is small.

Elliptic Curve Attacks

• ECDSA Biased Nonces Attack – Recover private key when nonces are partially predictable (lattice attack).
• ECDSA Nonce Reuse Attack – Recover private key when the same nonce is reused in two signatures.
• Invalid Curve Attack - Exploits missing point validation to force scalar multiplication on other weak curves.
• MOV Attack – Reduce elliptic curve discrete log to finite field discrete log using weil-pairing.
• Smart Attack – Solve discrete log on anomalous curves (when #E = p).

LWE Attacks

• Arora-Ge - Algebraic attack on LWE by solving polynomial systems (works for small noise).
• Least-Squares Attack - Recover secret vector when modulus reduction is not applied.

RSA Attacks

• Batch GCD Attack - Factor multiple RSA moduli sharing primes.
• Blinding Attack - Forge a valid signature for a prohibited message using a signing oracle.
• Common Modulus Attack - Recover plaintext when same modulus is used with coprime exponents.
• Coppersmith Short Pad Attack - Recover message when padding is too short (small unknown part).
• Franklin-Reiter Attack - Recover messages that are linearly related and encrypted with same modulus.
• Hastad Broadcast Attack - Recover plaintext sent to multiple recipients with a small exponent.
• Small Exponent Attack - Recover plaintext directly when exponent is small.
• Wiener Attack - Recover $d$ when $d < \frac{1}{3} N^{1/4}$.

References

• Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem.
• Arora, S., & Ge, R. (2011). New algorithms for learning in presence of errors.
• Menezes, A. J., & Wu, Y.-H. (1997). The Discrete Logarithm Problem in GL(n, q).
• Pohlig, S. C., & Hellman, M. (1978). An Improved Algorithm for Computing Logarithms over GF(p).
• Smart, N. P. (1999). The Discrete Logarithm Problem on Elliptic Curves of Trace One.
• Menezes, A., Okamoto, T., & Vanstone, S. (1993). Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field.
• Breitner, J., & Heninger, N. (2019). Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies.