Cryptopals

Matasano crypto challenges (http://cryptopals.com/) implemented mostly in C.

Introduction

This is a serie of 56 technical challenges around software programming and cryptography made by some people at Matasano. Every solution can be built either on Windows or on Linux (Mint and Arch tested).

The tools folder contains implementations of several standard cryptographic protocols and utilities : do not use them in production.

Requirements

• You need to have access to the gcc toochain and basic shell commands (make, cd, sed, awk, etc.). On Windows, every challenge has been tested against the mingw32 compiler.
• Some challenges use pythons scripts : everything has been written for Python 3xx. Older versions may or may not work.
• pip requirements :
  • On Linux, install pip3 : sudo (apt-get install | yum install | pacman -S) python3-pip to prevent name clashing with the system-wide pip binary.
  • bottle web framework for challenges 31 & 32
  • tkinter for challenge 20
• libcurl : challenge 31 & 32 use libcurl to make requests to a remote webpage.
  • Libcurl isn't installed by default on Windows, so you will need to download the static library compatible with your compiler (or build it yourself) and placing it in the corresponding's lib folder. Download page : http://curl.haxx.se/download.html
  • On Unix systems, you can either use libcurl statically of dynamically (modify the Makefile to your needs). Don't forget to add the installed lib folder (something like /usr/lib/x86_64-linux-gnu ) in the LDFLAGS.

Usage

The Makefile located in the root folder contains every useful commands, while global.mk has every project-wide variables.

Ex :

• make 01 all will build all the targets in first challenge.
• make tools will build all the necessary libraries and bins in the tools folder.
• make exos clean will run make clean on every challenges.
• make exos build will run make build on every challenges, building the binary. (make whill aslo do the same)
• make exos solve will run make solve on every challenges, building the binary and running it.
• make 01 07 09 solve will run make solve on challenge 01, 07 and 09.

Caveat : challenge #31 & #32 can't be called from the top-level Makefile since you need to fire up a websever. To test the challenge , you need to type :

• cd "[$ex]_..."
• make webserver on one terminal
• make solve on an another terminal

Set 1

• [X] Convert hex to base64
• [X] Fixed XOR
• [X] Single-byte XOR cipher
• [X] Detect single-character XOR
• [X] Implement repeating-key XOR
• [X] Break repeating-key XOR
• [X] AES in ECB mode
• [X] Detect AES in ECB mode

Set 2

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

Set 3

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

Set 4

• [X] Break "random access read/write" AES CTR
• [X] CTR bitflipping
• [X] Recover the key from CBC with IV=Key
• [X] Implement a SHA-1 keyed MAC
• [X] Break a SHA-1 keyed MAC using length extension
• [X] Break an MD4 keyed MAC using length extension
• [X] Implement and break HMAC-SHA1 with an artificial timing leak
• [X] Break HMAC-SHA1 with a slightly less artificial timing leak
  • This challenge works only on Linux (Arch Linux & Mint tested).

Set 5

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

Set 6

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

Set 7

• [ ] 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

Licensing

My own code is free to use (attribution is nice, but not mandatory). Other licenses :

• curl : libcurl has a fairy complicated license mix. Since I only link against the lib, my work is not derivative and is not subject to libcurl's licenses.
• mini-gmp is doubly licensed GPL and LGPL.
• sha1 is copied from polarSSL/mbed is GPL also.
• sha256 is copied from Brad conte crypto-algorithms and is copyleft.
• rsa prime generation is adapted from SSH 1.2.0, found in MIT Athena's project (Copyright 1995 SSH Communications Security).