Cryptographic Attacks

Repository containing my Sage and/or Python implementations of attacks on popular ciphers and public key cryptosystems.

Overview

As of yet, there are implementations for attacks against RSA, Diffie-Hellman and its elliptic curve variant, AES-ECB, and AES-CBC. There are also miscellaneous factoring attacks, which may be applicable for targeting many public key schemes, and some notes on topics such as elliptic curve pairings. I plan to finish all existing public key attacks in the future and significantly expand attack support for symmetric key primitives, as the latter has been relatively lacking for the past few years. Additionally, I aim to add more general purpose algorithms in the domains of factoring, state recovery for non-cryptographically secure PRNG (such as ones that use linear congruential generators or linear-feedback shift registers), and more, the reason being that doing so should allow for more flexibility when attacking cryptographic primitives.

Currently Implemented Attacks

Public Key Cryptographic Schemes

RSA

• Generalized Hastad's broadcast attack
• Common modulus attack
• Wiener's attack for small d
• Blinding attack on Unpadded RSA signatures
• Fault attack on RSA-CRT
• Franklin-Reiter related message attack + Coppersmith short pad attack
• Coron's simplification of Coppersmith's root finding algorithm for bivariate polynomials in Z[x, y]
• Partial key recovery attack with bits of d known

Diffie-Hellman

• Pohlig-Hellman attack for finding discrete logarithms in cyclic multiplicative groups with smooth order
• Pohlig-Hellman attack for finding discrete logarithms in elliptic curve additive groups with smooth order
• Small-subgroup confinement attack

Factoring algorithms (applicable for many public key primitives)

• Cheng's 4p - 1 = Ds^2 elliptic curve complex multiplication based factoring

Elliptic Curves

• MOV attack for curves of low embedding degree

Symmetric Key Ciphers

AES

• Byte-at-a-time ECB decryption
• AES-CBC Padding Oracle

Installing SageMath

SageMath is available on both Windows and Un*x.

To install SageMath on Windows, download an installer from the following link: https://github.com/sagemath/sage-windows/releases

To install on Ubuntu and other Linux distros, I believe sudo apt install sagemath, or something along those lines will get the job done.

SageMath also has a presence in the cloud:

• SageMathCell: (useful as a quick go-to for evaluating Sage code without the need to save, also be mindful of no external connections)

• CoCalc: (optimal for hosting personal projects in the cloud)

It is also possible to host a personal SageMath server, though I have never tried this.

Current Notes

The Notes directory contains my notes on miscellaneous cryptography-related topics. As of now, I have written up a summary of the first few chapters of Craig Costello's Pairings for Beginners and a SageMath script demonstrating elliptic curve point addition and doubling in projective coordinates.

Future Works

Existing Attacks

1. Implement the small-subgroup confinement attack for Diffie-Hellman and its Elliptic Curve counterpart.
2. Implement the MOV attack for elliptic curves of low embedding degree.

Future Attacks

1. Boneh-Durfee attack for d < N^0.292
2. BLS rogue public key attack
3. Fault attack on standard (non-CRT) RSA
4. Small-subgroup confinement attack on Diffie-Hellman
5. Linear / differential cryptanalysis against DES/AES
6. Invalid point attacks on Elliptic Curve Diffie-Hellman
7. State recovery on linear congruential generators (LCGs), truncated and non-truncated
8. State recovery on linear feedback shift registers (LFSRs)

Miscellaneous

1. Add docstrings to each attack to better describe their functionalities.
2. Add more general purpose scripts that may prove useful for breaking some cryptographic schemes
3. Improve overall code quality, efficiency, and consistency

Feel free to let me know if there are any bugs.

Frequently Asked Questions

Q: Why use SageMath instead of pure Python?

A: Sage provides many convenient number-theoretic functions and constructors for algebraic structures commonly used by or used against cryptographic primitives, such as groups, polynomial rings, fields, and elliptic curves. This saves a lot of time since it allows focus to be placed solely on implementing attacks and useful general purpose algorithms rather than the structures that they depend upon.

Relevant Links

• General overview of Coppersmith's attack
• Coron's simplification of Coppersmith's algorithm
• Cheng's 4p - 1 elliptic curve complex multiplication based factoring
• Craig Costello's Pairings for Beginners
• 20 years of attacks on RSA