CSAW Quals 2019

ECB Byte at a time attack.

Information

category : crypto
points : 50

Description

(Byte Me) if you can nc crypto.chal.csaw.io 1003

Writeup

Ok let’s try to connect to server and see what this challenge is about (I’ll mark # the comment):

nc crypto.chal.csaw.io 1003
23ace1ee2679fa7c81ccf66a865e98c5e80c9208a206b78776a8dd16f5ea1457f44c8a9882d7f440fc2b4aad213b65436510556e7c2f57422a959ea2b1b0c8ba

Tell me something:							# With empty input I receive the same ciphertext
23ace1ee2679fa7c81ccf66a865e98c5e80c9208a206b78776a8dd16f5ea1457f44c8a9882d7f440fc2b4aad213b65436510556e7c2f57422a959ea2b1b0c8ba

Tell me something: a						# The ciphertext of a is different from the ciphertext of b  
cd49af33294afc9b843bb713517f12bd89d92e5b0c9244d5d71d33815a4e8cf7adc474c0f5e77546a43732488e5ce6afdfeca90bd8711ba453f4bedd051902da

Tell me something: b
b769ee2ef66a76351a62a2e38dc38f1989d92e5b0c9244d5d71d33815a4e8cf7adc474c0f5e77546a43732488e5ce6afdfeca90bd8711ba453f4bedd051902da

Tell me something: aaa
38ae0e0c0f19f15a55eee646ba888c4e73dd7e606cc6755f22e3e5d9e5b22bede4eca07d36503b4d12f3a2228df1d40063217add6089a5357875c46ff0457291

Tell me something: bbb
282e6c3ac5cf6f1b367b37056332b781921ee57568816ccdf6a1889c736030c7e4eca07d36503b4d12f3a2228df1d40063217add6089a5357875c46ff0457291

Tell me something: aaaaaaaaa				# The first block of the enc(aaa) is equal to the first block of enc(aaaaaaaaa) where enc is the encryption
38ae0e0c0f19f15a55eee646ba888c4ed87f273b983ee8b13f1d5f48bcd7197e333191ae17102fdfe97131dd0e9b82bccc2be3d21f1a8fa27c19af26aa77f9f59eaf3341c8216c7e42ae21e7fc665881

Tell me something: bbbbbbbbb				# From this block we can deduce that the blocksize of the ciphertext is 16 bytes = 32 hex digits
282e6c3ac5cf6f1b367b37056332b781e034117ceda52b3bf2ed14b57f088803333191ae17102fdfe97131dd0e9b82bccc2be3d21f1a8fa27c19af26aa77f9f59eaf3341c8216c7e42ae21e7fc665881

Tell me something: aaaaaaabbbb				# As expected the first block of enc(aaaaaaabbbb) = enc(aaaaaaaxxxx)
38ae0e0c0f19f15a55eee646ba888c4e1bc7b1e266a3ece24d184a2080e66271557f58d5358319774b16842b0fd34189a6dedbe100d30fe9a356f73cfa61439699b14bfc188dd46879f8e53c851e82b6

Tell me something: aaaaaaaxxxx
38ae0e0c0f19f15a55eee646ba888c4e9fbbac9bf0b2a35bd1d46db6e809d964557f58d5358319774b16842b0fd34189a6dedbe100d30fe9a356f73cfa61439699b14bfc188dd46879f8e53c851e82b6

# Let's see if the ciphertext is using ECB as mode of operation
Tell me something: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
38ae0e0c0f19f15a55eee646ba888c4eed4605b6ad00c4151179392e6436f97eed4605b6ad00c4151179392e6436f97eed4605b6ad00c4151179392e6436f97eed4605b6ad00c4151179392e6436f97eed4605b6ad00c4151179392e6436f97ef6886e8837caefd9dc554fd9a6cb78d014381d2cdad87676ef62fe39851139e43d51a965425508ed39911610b213351b5ad5764d547113d60305dfbbcf5db01d

From the the output above we see that the server it’s encrypting every plaintext taken in input, so we can craft a Chosen Plaintext Attack (CPA).

“Fuzzing” the server with some requests we can deduce:

It’s using ECB as encryption scheme because there are repetitive blocks from a ciphertext derived from a repetitive plaintext.
It’s add random byte at the start because enc(aaaaaaabbbb)[:First_Block] = enc(aaaaaaaxxxx)[:First_Block].
The blocksize of the PRF/PRP is 16 bytes = 32 hex digits.
The last blocks are always the same, so probably it’s appending the encryption of (flag || pad).

To confirm all this deduction I started writing an exploit :

import sys
from pwn import *

class Oracle():
    def __init__(self, host, port):
        self.host = host
        self.port = port
        self.conn = remote(self.host, self.port)
    
    def receive_enc_flag(self):
        flag = self.conn.recvline()
        return to_byte(flag)

    def receive_enc_pt(self, pt):
        self.conn.recvuntil('something: ')
        self.conn.sendline(pt)
        self.conn.recvline()
        s = self.conn.recvline()
        return to_byte(s)

    def compute_bsize(self):
        plaintext = b''
        # aes-ecb(key, junk || unknown-string = flag || pad)
        initial_len = len(self.receive_enc_pt(plaintext))
        final_len = initial_len
        # aes-ecb(key, junk || plaintext || unknown-string = flag || pad)
        while final_len == initial_len:
            plaintext += 'a'
            final_len = len(self.receive_enc_pt(plaintext)) 
        return (final_len - initial_len)
    
    def compute_junk(self, blocksize):
        ciphertexts = []
        ciphertexts.append(self.receive_enc_pt('')[:blocksize])
        # Incrementing the plaintext of one 'a' at every iteration
        # There will be 2 consecutive first block of the ciphertexts
        # equal. From there I can deduce the size of the junk
        for i in range(1, 17):
            ciphertexts.append(self.receive_enc_pt('a' * i)[:blocksize])
            if ciphertexts[i] == ciphertexts[i - 1]:
                return 17 - i
        # 16 or 0 is indifferent!
        return 0

def to_byte(s):
    # Remove \n\r
    return s[:-2].decode("hex")

def identify_ecb(ct, blocksize):
    blocks = [ct[i: i + blocksize] for i in range(0, len(ct), blocksize)]
    for i in range(0, len(blocks)):
        for j in range(i+1, len(blocks)-1):
            if blocks[i] == blocks[j]:
                return 1
    return None

def main():
    host = 'crypto.chal.csaw.io'
    port = '1003'
    oracle = Oracle(host, port)
    flag_enc = oracle.receive_enc_flag()

    # Compute blocksize of the cipher --> 16 
    blocksize = oracle.compute_bsize()
    log.info("blocksize : " + str(blocksize))

    # Compute junk size --> Random
    junk = oracle.compute_junk(blocksize)
    log.info("junk size : " + str(junk))

    # Check if the cryptosystem is using ECB --> YES
    enc_pt = oracle.receive_enc_pt('a' * 100)
    if identify_ecb(enc_pt, blocksize) == None:
        log.info("ecb : false\nleaving...")
        exit(1) 
    log.info("ecb : true")
 
if __name__ == '__main__':
    main()

$ python2 exploit.py
[+] Opening connection to crypto.chal.csaw.io on port 1003: Done
[*] blocksize : 16
[*] junk size : 1
[*] ecb : true

$ python2 exploit.py
[+] Opening connection to crypto.chal.csaw.io on port 1003: Done
[*] blocksize : 16
[*] junk size : 4
[*] ecb : true

How can we decrypt the flag ?

Well ECB is not CPA secure because is a deterministic encryption (not randomized).

Let’s wee how we can decrypt the flag using a CPA called byte at a time.

If you have trouble understanding my scheme check this repository or cryptopals set 2 chall 12.

Now we need just to write the function to decrypt each character of the flag :

def get_secret(self, blocksize, part_secret, junk):
	# Length of plaintext must be between 0 and 15, so % blocksize = 16
	length_plaintext = (blocksize - junk - (1 + len(part_secret))) % blocksize
	# Length to crack is always length_plaintext + len(secret that I know) + 1
	# After the first block has been decrypted, we need to reconstruct the length_plaintext
	# to 15, and add to it during the verification (if) the part_secret 
	length_to_crack = length_plaintext + junk + len(part_secret) + 1
	# Create plaintext
	plaintext = 'a' * length_plaintext
	# Ciphertext to compare
	ciphertext = self.receive_enc_pt(plaintext)
	# Let's create a charset of all possible ascii values (readable)
	charset = "qwertyuiopasdfghjklzxcvbnm"
	charset += charset.upper()
	charset += "_{}0123456789@!#$%^&*()_-+=/?.><,|" 

	# Time to bruteforce -\_('_')_/-
	for x in charset:
		ct = self.receive_enc_pt(plaintext + part_secret + x)
		if ciphertext[:length_to_crack] == ct[:length_to_crack]:
			return x
	return ''

Exploit

import sys
from pwn import *

class Oracle():
    def __init__(self, host, port):
        self.host = host
        self.port = port
        self.conn = remote(self.host, self.port)
    
    def receive_enc_flag(self):
        flag = self.conn.recvline()
        return to_byte(flag)

    def receive_enc_pt(self, pt):
        self.conn.recvuntil('something: ')
        self.conn.sendline(pt)
        self.conn.recvline()
        s = self.conn.recvline()
        return to_byte(s)

    def compute_bsize(self):
        plaintext = b''
        # aes-ecb(key, junk || unknown-string = flag || pad)
        initial_len = len(self.receive_enc_pt(plaintext))
        final_len = initial_len
        # aes-ecb(key, junk || plaintext || unknown-string = flag || pad)
        while final_len == initial_len:
            plaintext += 'a'
            final_len = len(self.receive_enc_pt(plaintext)) 
        return (final_len - initial_len)
    
    def compute_junk(self, blocksize):
        ciphertexts = []
        ciphertexts.append(self.receive_enc_pt('')[:blocksize])
        # Incrementing the plaintext of one 'a' at every iteration
        # There will be 2 consecutive first block of the ciphertexts
        # equal. From there I can deduce the size of the junk
        for i in range(1, 17):
            ciphertexts.append(self.receive_enc_pt('a' * i)[:blocksize])
            if ciphertexts[i] == ciphertexts[i - 1]:
                return 17 - i
        # 16 or 0 is indifferent!
        return 0

    def get_secret(self, blocksize, part_secret, junk):
        # Length of plaintext must be between 0 and 15, so % blocksize = 16
        length_plaintext = (blocksize - junk - (1 + len(part_secret))) % blocksize
        # Length to crack is always length_plaintext + len(secret that I know) + 1
        # After the first block has been decrypted, we need to reconstruct the length_plaintext
        # to 15, and add to it during the verification (if) the part_secret 
        length_to_crack = length_plaintext + junk + len(part_secret) + 1
        # Create plaintext
        plaintext = 'a' * length_plaintext
        # Ciphertext to compare
        ciphertext = self.receive_enc_pt(plaintext)
        # Let's create a charset of all possible ascii values (readable)
        charset = "qwertyuiopasdfghjklzxcvbnm"
        charset += charset.upper()
        charset += "_{}0123456789@!#$%^&*()_-+=/?.><,|" 

        # Time to bruteforce -\_('_')_/-
        for x in charset:
            ct = self.receive_enc_pt(plaintext + part_secret + x)
            if ciphertext[:length_to_crack] == ct[:length_to_crack]:
                return x
        return ''

def to_byte(s):
    # Remove \n\r
    return s[:-2].decode("hex")

def identify_ecb(ct, blocksize):
    blocks = [ct[i: i + blocksize] for i in range(0, len(ct), blocksize)]
    for i in range(0, len(blocks)):
        for j in range(i+1, len(blocks)-1):
            if blocks[i] == blocks[j]:
                return 1
    return None

def main():
    host = 'crypto.chal.csaw.io'
    port = '1003'
    oracle = Oracle(host, port)
    flag_enc = oracle.receive_enc_flag()

    # Compute blocksize of the cipher --> 16 
    blocksize = oracle.compute_bsize()
    log.info("blocksize : " + str(blocksize))

    # Compute junk size --> Random
    junk = oracle.compute_junk(blocksize)
    log.info("junk size : " + str(junk))

    # Check if the cryptosystem is using ECB --> YES
    enc_pt = oracle.receive_enc_pt('a' * 100)
    if identify_ecb(enc_pt, blocksize) == None:
        log.info("ecb : false\nleaving...")
        exit(1) 
    log.info("ecb : true")
    
    # Decrypt flag
    part_secret = ''
    for i in range(len(flag_enc)):
        char_secret = oracle.get_secret(blocksize, part_secret, junk)
        part_secret += char_secret
        sys.stdout.write("\r" + char_secret)
        sys.stdout.flush()
        if '}' in part_secret:
            sys.stdout.write("\n")
            break

if __name__ == '__main__':
    main()

Time to launch the exploit and…

Flag

flag{y0u_kn0w_h0w_B10cks_Are_n0T_r31iab13...}