The Cryptopals Crypto Challenges

What It is

The cryptopals challenges (https://cryptopals.com/) are a set of practical cryptography exercises that simulate real-world crypto attacks. They're derived from weaknesses in real-world systems and modern cryptographic constructions.

What's The Purpose Of This Project

The following is my walkthrough of these challenges using the Python 3.10, although only the solution is provided without a detailed explanation (might be added later on), since it should be understandable from the code itself and inserted comments in it.

Status Of This Project

This is still a work in progress. Since I am not solving the challenges on a regular basis, the update schedule is erratic. In the table of contents, every solved challenge is indicated with a ✔️, while every unsolved challenge is marked with a ❌.

Structure Of This Project

.
├── cryptopals
│   ├── s01
│   │   ├── c01                     
│   │   │   ├── README.md
│   │   │   ├── solution_c01.py
│   │   │   └── test_c01.py
│   │   └── ...
│   ├── s02
│   ├── ...
│   ├── utils.py
│   └── ...
├── ...
├── .gitignore
├── LICENSE
├── pyproject.toml
├── README.md
└── requirements.txt

Sets

Each set of challenges has it's corresponding folder with the according number, e.g. the challenges from Set 1 - Basics reside in folder s01.

Challenges

Every challenge has it's corresponding folder with the according number, e.g. the Challenge 1 - Convert hex to base64 has its own folder c01.

Solution

The solution for the particular challenge has a "solution_" prefix added to it, e.g. solution for Challenge 1 is in module solution_c01.py.

#
#   01 - Convert hex to base64
#

import codecs


def hex_to_base64(hex_bytes: bytes) -> bytes:
    return codecs.encode(codecs.decode(hex_bytes, "hex"), "base64").rstrip()

Test

Test for the solution has a "test_" prefix added to it, e.g. test for solution of Challenge 1 is in test_c01 module.

#
#   01 - Convert hex to base64
#

from cryptopals.s01.c01.solution_c01 import hex_to_base64


def test_c01() -> None:
    # Input String
    string = b"49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d"
    
    # Valid Result
    result = b"SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t"
    
    assert hex_to_base64(string) == result

Refactored Solutions

Every solution/code that proves useful is refactored and moved to a different module, that'll be used in the future challenges. For e.g., the solution for Challenge 1, is going to be refactored into a Converter class in the module utils:

# utils.py

class Converter:
    @staticmethod
    def hex_to_base64(hex_bytes: bytes) -> bytes:
        return codecs.encode(codecs.decode(hex_bytes, "hex"), "base64")

How To Run

Virtual Environment

Python virtual environment is being used for running these challenges, with a small guide on how to set it up here:

Installation And Activation

# Install virtualenv If Not Already Installed
$ pip install virtualenv

# Create The Virtual Environment
$ virtualenv -p python3 venv

# Activate The Virtual Environment
$ source venv/bin/activate

Deactivation

# Deactivate The Virtual Environment After Being Done Running This Project
(venv) $ deactivate

Dependencies

The dependencies must be installed for everything to work properly by running the following command:

# Install The Dependencies For The Virtual Environment
(venv) $ pip install -r requirements.txt

Tests

Running The Tests

To run the tests for the solutions, run the pytest command:

# Run pytest With The Verbosity Flag
(venv) $ pytest -v

test_c01.py::test_c01 PASSED                                                                                        [100%]

Timeout

The timeout for every test is set to 120 seconds by default, however it may have to be increased if some solutions take longer to give the final result for the tests. This timeout can be configured in the pyproject.toml file as follows:

[tool.pytest.ini_options]
timeout = 120

Set 1: Basics

Convert hex to base64 ✔️
Fixed XOR ✔️
Single-byte XOR cipher ✔️
Detect single-character XOR ✔️
Implement repeating-key XOR ✔️
Break repeating-key XOR ✔️
AES in ECB mode ✔️
Detect AES in ECB mode ✔️

Set 2: Block crypto

Implement PKCS#7 padding ✔️
Implement CBC mode ✔️
An ECB/CBC detection oracle ✔️
Byte-at-a-time ECB decryption (Simple) ✔️
ECB cut-and-paste ✔️
Byte-at-a-time ECB decryption (Harder) ✔️
PKCS#7 padding validation ✔️
CBC bitflipping attacks ✔️

Set 3: Block & stream crypto

The CBC padding oracle ✔️
Implement CTR, the stream cipher mode ✔️
Break fixed-nonce CTR mode using substitutions ✔️
Break fixed-nonce CTR statistically ✔️
Implement the MT19937 Mersenne Twister RNG ✔️
Crack an MT19937 seed ✔️
Clone an MT19937 RNG from its output ✔️
Create the MT19937 stream cipher and break it ✔️

Set 4: Stream crypto and randomness

Break "random access read/write" AES CTR ✔️
CTR bitflipping ✔️
Recover the key from CBC with IV=Key ✔️
Implement a SHA-1 keyed MAC ✔️
Break a SHA-1 keyed MAC using length extension ✔️
Break an MD4 keyed MAC using length extension ✔️
Implement and break HMAC-SHA1 with an artificial timing leak ✔️
Break HMAC-SHA1 with a slightly less artificial timing leak ✔️

Set 5: Diffie-Hellman and friends

Implement Diffie-Hellman ✔️
Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection ✔️
Implement DH with negotiated groups, and break with malicious "g" parameters ✔️
Implement Secure Remote Password (SRP) ✔️
Break SRP with a zero key ✔️
Offline dictionary attack on simplified SRP ✔️
Implement RSA ✔️
Implement an E=3 RSA Broadcast attack ✔️

Set 6: RSA and DSA

Implement unpadded message recovery oracle ✔️
Bleichenbacher's e=3 RSA Attack ✔️
DSA key recovery from nonce ✔️
DSA nonce recovery from repeated nonce ✔️
DSA parameter tampering ✔️
RSA parity oracle ✔️
Bleichenbacher's PKCS 1.5 Padding Oracle (Simple Case) ✔️
Bleichenbacher's PKCS 1.5 Padding Oracle (Complete Case) ✔️

Set 7: Hashes

CBC-MAC Message Forgery ❌
Hashing with CBC-MAC ❌
Compression Ratio Side-Channel Attacks ❌
Iterated Hash Function Multicollisions ❌
Kelsey and Schneier's Expandable Messages ❌
Kelsey and Kohno's Nostradamus Attack ❌
MD4 Collisions ❌
RC4 Single-Byte Biases ❌

Set 8: Abstract Algebra

Diffie-Hellman Revisited: Small Subgroup Confinement ❌
Pollard's Method for Catching Kangaroos ❌
Elliptic Curve Diffie-Hellman and Invalid-Curve Attacks ❌
Single-Coordinate Ladders and Insecure Twists ❌
Duplicate-Signature Key Selection in ECDSA (and RSA) ❌
Key-Recovery Attacks on ECDSA with Biased Nonces ❌
Key-Recovery Attacks on GCM with Repeated Nonces ❌
Key-Recovery Attacks on GCM with a Truncated MAC ❌
Truncated-MAC GCM Revisited: Improving the Key-Recovery Attack via Ciphertext Length Extension ❌
Exploiting Implementation Errors in Diffie-Hellman ❌

License

Everything in this repository is released under the terms of the MIT License. For more information, please see the file "LICENSE".

Skrekulko/cryptopals-crypto-challenges