cryptopals

README

cryptopals

This is a repo providing solutions written in Go to the Matasano Cryptopals Challenges.

Challenge 1

This challenge asks us to decode a hex-encoded string into a byte slice and re-encode it as base64.

Challenge 2

This challenge asks us to xor two hex-encoded strings together. This can be accomplished by decoding the strings into byte slices and xoring them together.

Here is a tiny truth table for XOR :)

A	B	Output
0	0	0
0	1	1
1	0	1
1	1	0

Challenge 3

This challenge asks us to decode a hex-encoded string xored with a single character, which should look something like hello ^ XXXXX. Since we know that the value of the byte type can only be 0..255 we can brute force the ciphertext against each value to derive the plaintext and key.

However, we want to return the correct plaintext, not 256 potential candidates, so we will need additional infrastructure for this challenge. For each decrypted candidate we can perform frequency analysis. We can construct a map of the frequency of each letter as it appears in English texts, keeping global state of which decrypted string has the highest score. This allows us to return only the highest scoring string rather than all potential candidates, which will prove essential in later challenges.

Challenge 4

This challenge asks us to open a file (conveniently located at testdata/4.txt) and apply our logic from challenge 3. We will need to brute force each string and return the highest scoring plaintext.

Challenge 5

This challenge asks us to look into decrypt a ciphertext encrypted with repeating-key XOR. We can modify our existing XOR code to instead do x[i] ⊕ y[i%len(y)] (modulo length of y).

Challenge 6

This challenge is definitely the hardest to understand without a background in cryptography. To make it easier we can break it into multiple sections.

Firstly, we will need to understand the concept of hamming distance at the bit level. In essence, we are counting the number of differing bits between two strings of equal length. This can be accomplished by xoring the strings together and counting the number of bits that are set to one.

As mentioned in the example, we can validate that our code works correctly by testing it against the strings this is a test and wokka wokka!!!; it should come out to 37.

The concept of hamming distance can be applied to help us solve this challenge when we understand how it interacts with English ASCII. The entire English alphabet (uppercase and lowercase) is represented in 52 out of the 256 possible values in ASCII, and it helps that the letters are conveniently located right next to each other and thus have a normalized average hamming distance far lower than legitimately random data.

A nice thing to note is that when XOR encrypted with the same key, two strings have the same hamming distance as their plaintext forms; it is only a matter of us finding the key length through brute force; the noticeably lower normalized hamming distance will be our key length :)

The example algorithm as described on the challenge page advises us to attempt to guess the key length from 2 to 40, which entails taking the first two chunks of the text of size KEYSIZE (the first block would be slice[:keysize], the second would be slice[keysize:keysize*2]). However, this sample size is too small to be accurate, which is why they advise taking up to the first four chunks of the ciphertext and finding the mean among those. In my testing, I found this to yield the wrong key size still (although it could have just been buggy code), but I was still determined to figure it out without magic numbers.[^1]

In my research, I happened upon this site discussing this topic in detail as well as another set of cryptopals solutions written in Python which prompted me to begin working on code that would iterate through the length of the ciphertext and compare each chunk (slice[size*(i+1):size*(i+2)]) against the first chunk. This worked as expected, which allowed us to determine the key size.

Armed with the key size, we attempt to split the ciphertext into chunks of len(keysize). We transpose the blocks (create a slice of byte slices) by placing the first byte of each chunk in one slice, the second byte in the second, and so on. We can then attempt to brute force each byte slice with scoring + single character XOR; we are then able to reconstruct the key and ultimately solve the challenge.

Challenge 7

This challenge asks us to decrypt a ciphertext encrypted in ECB mode. We use the crypto/aes package, decrypting the ciphertext 16 bytes at a time with Block.Decrypt.

Challenge 8

This challenge takes advantage of the fact that AES-ECB encrypts the same plaintext block into the same ciphertext (lack of diffusion). We track the encrypted blocks in a map so we can easily lookup the existence of the ciphertext and determine whether a certain string was encrypted with ECB mode.

Challenge 9

This challenge asks us to pad a message to a specific block size with PKCS#7. In essence, this means padding to a specified uint8 length while ensuring the value of the added bytes is equivalent to the number of bytes added.

Challenge 10

This challenge asks us to decrypt a AES-CBC encrypted ciphertext. CBC is a confidentiality-only mode whose encryption can be formalized as C[i] = E(P[i] ^ C[i-1]), with decryption being P[i] = D(C[i]) ^ C[i-1].

Challenge 11

This challenge asks us to construct an oracle that encrypts a given input with CBC mode 50% of the time and ECB mode the other half of the time. The key should be securely generated with the operating system's CSPRNG (see crypto/rand) and it should prepend 5-10 random bytes and append 5-10 random bytes to the plaintext before encryption.

We will use our previous function to detect ECB mode by crafting 3 contiguous blocks and sending it to the oracle. 3 blocks ensures that no matter how many bytes are prepended/appended, we will always encrypt two blocks of identical plaintext.

Challenge 12

https://book-of-gehn.github.io/articles/2018/06/10/Breaking-ECB.html

Challenge 13

This challenge asks us to construct a function that will take an arbitrary input for email (the below map)

{
    "email": "foo@bar.com",
    "uid":   "10",
    "role":  "user",
}

and encode it into "URL encoded form" like email=foo@bar.com&role=user&uid=10. This input is then encrypted with ECB mode and the oracle is provided to the attacker. We aren't able to directly encode the bytes '&' and '=', so we have to play some clever tricks with padding. We know that the block size is 16 bytes, so we just have to separate the key= and the literal value into separate blocks. Using a 4 byte email allows us to get exactly this.

email=AAAA&role= user&uid=10

We can then craft a large email so that the word admin is not in the first block, and then replace the first block. The plaintext should ultimately look like the below.

email=AAAA&role= admin&role=user& uid=10

Challenge 14

This challenge asks us to extend the previous append-only oracle in Challenge 12 by prepending a consistent, but random number of random bytes. We will need to pad the prepended bytes to a full block and then solve like Challenge 12.

For instance, if we had the setup

PPPP PPPP PPAT TACK ERCO NTRO LLED <- appended bytes go here

we should pad the prepended bytes to a full block, like so:

PPPP PPPP PPXX ATTA CKER CONT ROLL ED <- appended bytes go here
            ^^ padding

then we should craft an oracle that will append the number of padding bytes consistently when run and solve like 12, so we can have something like the below:

PPPP PPPP PPXX <- delete these bytes by slicing
ATTA CKER CONT ROLL ED <- appended bytes go here

We then solve like normal.

Challenge 15

This challenge just asks us to modify our unpadding PKCS#7 function to take the last byte and verify that the added bytes are of the correct number and value.

Challenge 16

This challenge takes advantage of the lack of authentication of CBC mode to flip a couple of bits in the ciphertext to get our desired result in the plaintext.

We should think back to our CBC implementation and remember that the result of the AES decryption pass for each block is the plaintext xored by the previous ciphertext block. If we can change the previous ciphertext block we can create a block that looks like C[i] ^ P[i+1] ^ DESIRED_BYTE. We can just craft a plaintext block that looks like XadminXtrue, replacing the desired bytes with the capital X and changing the ciphertext byte in the block immediately prior so at decryption time it will look like C[i-1] (which is really P[i] ^ C[i-1] ^ DESIRED_BYTE) ^ P[i], giving us DESIRED_BYTE in the final decrypted plaintext.

Challenge 17

Back from a hiatus :) I'll try to write my own AES implementation in the near future. Now, onto the challenge.

We are given the IV and a padding oracle that tells us whether some padding was valid. If we look at CBC decryption, we see the ciphertext of the previous block is xored with the decryption of the current block. Thus, changing a bit of the ciphertext allows us to influence the decryption of the current block. We know that for any given m ^ m = 0, so if we modify the last byte, we xor our guess m with 0x1; if m is correct, then the padding will likely* be valid. Then we modify the next one for a padding of 2, and so on. But as padding gets longer we run into the risk of a collision, and to rectify this you could also temporarily modify the previous one and see if the padding remains valid. I haven't implemented that here, but it would be a trivial addition.

[^1]: I looked at Filippo Valsorda's solutions @ mostly-harmless/ as well as his livestream but it turns out he just guessed the magic number; this isn't good enough for me.

Documentation

Overview

Package cryptopals provides solutions for set 1 of cryptopals.

This package requires Go 1.18, as it makes use of generics, even though the challenges can be solved entirely without them.

Index

• Variables
• func ComputeHamming(x, y []byte) (count int)
• func DecryptAdmin(src []byte, bl cipher.Block) bool
• func DecryptAppendOracle(oracle func([]byte) []byte) []byte
• func DecryptCBC(bl cipher.Block, src []byte, iv []byte) []byte
• func DecryptECB(src []byte, block cipher.Block) []byte
• func DecryptPaddingOracle(src []byte, blockSize int, padCheck func([]byte) bool) string
• func DecryptPrependOracle(oracle func([]byte) []byte) []byte
• func DecryptStream()
• func DetectECB(src []byte, blockSize int) bool
• func EncryptCBC(bl cipher.Block, src []byte, iv []byte) []byte
• func EncryptCTR(bl cipher.Block, src []byte, nonce []byte) []byte
• func EncryptECB(src []byte, bl cipher.Block) []byte
• func FindTransposedXorKey(src []byte, size int) []byte
• func FindXorKeySize(src []byte) (result int)
• func GenRandKey(size int) []byte
• func GenerateAdmin(oracle func(email string) []byte, size int) []byte
• func GenerateProfile(email string) string
• func GuessKey(src []byte) (key byte, high float64)
• func HexToBase64(hs string) string
• func NewAppendECBOracle(secret string) func([]byte) []byte
• func NewCBCBitflipOracle() (oracle func([]byte) []byte, checkAdmin func([]byte) bool)
• func NewCBCECBOracle() func([]byte) []byte
• func NewCBCPaddingOracle(strs []string) (res []byte, plaintext string, verify func([]byte) bool)
• func NewPrependECBOracle(secret string) func([]byte) []byte
• func NewProfileOracle() (oracle func(email string) []byte, block cipher.Block)
• func PadPKCS7(src []byte, size uint8) []byte
• func ScoreString(s string) (count float64)
• func SingleXor[T constraints.Integer](x []T, key T) []T
• func SolveCBCBitflipOracle(oracle func([]byte) []byte) []byte
• func TransposeBytes(src []byte, size int) [][]byte
• func UnpadPKCS7(src []byte, size uint8) []byte
• func XorSlice[T constraints.Integer](x, y []T) []T

Variables

var DecryptCTR = EncryptCTR

Functions

func ComputeHamming

func ComputeHamming(x, y []byte) (count int)

ComputeHammering counts the differing bits in the strings by xoring them together and counting the remaining bits.

func DecryptAdmin

func DecryptAdmin(src []byte, bl cipher.Block) bool

DecryptAdmin decrypts the ciphertext and evaluates if it grants admin access.

func DecryptAppendOracle

func DecryptAppendOracle(oracle func([]byte) []byte) []byte

DecryptAppendOracle attempts to recover appended plaintext given by NewAppendECBOracle.

func DecryptCBC

func DecryptCBC(bl cipher.Block, src []byte, iv []byte) []byte

DecryptCBC decrypts a block by decrypting the ciphertext block and xoring it with the previous ciphetext to obtain the plaintext.

func DecryptECB

func DecryptECB(src []byte, block cipher.Block) []byte

DecryptECB decrypts a byte slice encrypted in ECB mode.

func DecryptPaddingOracle

func DecryptPaddingOracle(src []byte, blockSize int, padCheck func([]byte) bool) string

func DecryptPrependOracle

func DecryptPrependOracle(oracle func([]byte) []byte) []byte

DecryptPrependOracle is very similar in spirit to DecryptAppendOracle; however, there is a random but consistent number of random bytes prepended to our plaintext. By consistently padding these bytes out we can slice/discard the ciphertext up to our controlled bytes and use DecryptAppendOracle to solve.

func DecryptStream

func DecryptStream()

func DetectECB

func DetectECB(src []byte, blockSize int) bool

DetectECB detects if a string is encrypted in ECB mode by checking for the existence of identical blocks with a map.

func EncryptCBC

func EncryptCBC(bl cipher.Block, src []byte, iv []byte) []byte

EncryptCBC encrypts a block by xoring the plaintext block by the previous ciphertext block and encrypting with the block cipher.

func EncryptCTR

func EncryptCTR(bl cipher.Block, src []byte, nonce []byte) []byte

EncryptCTR encrypts plaintext using ECB mode.

func EncryptECB

func EncryptECB(src []byte, bl cipher.Block) []byte

EncryptECB encrypts plaintext using ECB mode.

func FindTransposedXorKey

func FindTransposedXorKey(src []byte, size int) []byte

FindTransposedXorKey guesses the key by taking transposing the byte slice into chunks of length size and attempting to solve each chunk via GuessKey.

func FindXorKeySize

func FindXorKeySize(src []byte) (result int)

FindXorKeySize is a probabilistic search for the key length in a range of 2..40. This is done by exploiting the fact that English has a lower hamming distance than random bytes; utilizing this property allows us to perform a search for the length of the key.

If our two chunks (x, y) are indeed the length of the key, we can expect the hamming distance between them to be exactly the same as their actual hamming distance. We can test this by writing a simple function.

x, y := []byte{1, 3, 3, 7}, []byte{10, 14, 14, 15}
key := decodeHex("f00d")
a, b := ComputeHamming(x, y), ComputeHamming(XorSlice(x, key), XorSlice(y, key))
if a != b {
	panic("oh no this should not happen???")
}

See https://crypto.stackexchange.com/a/8118 for more info.

func GenRandKey

func GenRandKey(size int) []byte

GenRandKey generates a cryptographically random key of length size.

func GenerateAdmin

func GenerateAdmin(oracle func(email string) []byte, size int) []byte

GenerateAdmin takes advantage of our ability to manipulate blocks to craft a block with the role key and the admin value in separate blocks.

For instance, the plaintext blocks for email foo@bar.com when blocksize is 16 looks something like

email=foo@bar.co m&role=user&uid=1 0

We can isolate the role key and value to obtain the ability to effectively the key to an arbitrary value; it will look like the below.

email=AAAA&role= user&uid=10

Afterwards, we can just make a large email that will take up the whole block and then some; we can combine these two blocks together to yield

email=AAAA&role= admin&role=user& uid=10

func GenerateProfile

func GenerateProfile(email string) string

GenerateProfile takes an email and encodes it into "URL encoded" form.

func GuessKey

func GuessKey(src []byte) (key byte, high float64)

GuessKey automates iterating over 0..255 SingleXors, returning the single byte key with the highest scoring string along with the score.

func HexToBase64

func HexToBase64(hs string) string

HexToBase64 takes a hex-encoded string, decoding it as a byte slice and re-encoding it in base64 format.

func NewAppendECBOracle

func NewAppendECBOracle(secret string) func([]byte) []byte

NewAppendECBOracle creates a new ECB oracle that appends the specified secret, padding appropriately and encrypting the input in ECB mode.

func NewCBCBitflipOracle

func NewCBCBitflipOracle() (oracle func([]byte) []byte, checkAdmin func([]byte) bool)

NewCBCBitflipOracle returns an oracle that takes an input, prepends "comment1=cooking%20MCs;userdata=" and appends ";comment2=%20like%20a%20pound%20of%20bacon", padding with PKCS#7, as well as another function that decrypts the input and checks for the existence of ";admin=true;"

func NewCBCECBOracle

func NewCBCECBOracle() func([]byte) []byte

NewCBCECBOracle takes a plaintext and encrypts it with AES, choosing ECB mode or CBC mode randomly. The key (and IV for CBC mode) are cryptographically secure, using the crypto/rand package.

func NewCBCPaddingOracle

func NewCBCPaddingOracle(strs []string) (res []byte, plaintext string, verify func([]byte) bool)

NewCBCPaddingOracle crafts a new CBC padding oracle and appends the IV to the ciphertext, automatically removing it at decryption time.

func NewPrependECBOracle

func NewPrependECBOracle(secret string) func([]byte) []byte

NewPrependECBOracle creates a new ECB oracle that prepends the specified secret, padding appropriately and encrypting the input in ECB mode.

func NewProfileOracle

func NewProfileOracle() (oracle func(email string) []byte, block cipher.Block)

NewProfileOracle returns an oracle that takes an email, generates a profile from it, and encrypts it under ECB mode.

func PadPKCS7

func PadPKCS7(src []byte, size uint8) []byte

PadPKCS7 pads src according to the PKCS#7 spec.

func ScoreString

func ScoreString(s string) (count float64)

ScoreString scores how the string is in-line with the most frequent English letters.

func SingleXor

func SingleXor[T constraints.Integer](x []T, key T) []T

SingleXor XORs an integer slice by an integer.

func SolveCBCBitflipOracle

func SolveCBCBitflipOracle(oracle func([]byte) []byte) []byte

SolveCBCBitflipOracle solves challenge 14 by flipping two bits to get ;admin=true; in the plaintext. This works by taking advantage of how CBC decryption works: a plaintext block is the result of decrypting the ciphertext and xoring it with the previous block.

If we can control the plaintext, we know that the raw result of the AES decryption pass is

D[i] ^ C[i-1]

By editing the same byte in the previous block we can craft a byte that is

C[i] ^= NEXT_BYTE_SAME_POSITION ^ TARGET_BYTE

I've elected to choose the 'X' byte to make this obvious, but it could feasibly be any byte.

func TransposeBytes

func TransposeBytes(src []byte, size int) [][]byte

TransposeBytes takes an integer slice and creates a slice of length size, then transposes those bytes appropriately.

func UnpadPKCS7

func UnpadPKCS7(src []byte, size uint8) []byte

UnpadPKCS7 unpads src by reading the last byte value and deleting the specified number of bytes.

func XorSlice

func XorSlice[T constraints.Integer](x, y []T) []T

XorSlice takes two integer slices and XORs the first slice by the second one. Callers should be careful to ensure that the length of y is greater than zero to avoid divide by 0.