In this CTF challenge, we are given the source code for a remote instance:
import binascii
import itertools
import os
from hashlib import sha512
key = os.urandom(32)
def xor(a: bytes, b: bytes) -> bytes:
return bytes([(aa ^ bb) for (aa, bb) in zip(a, b)])
def encrypt(key: bytes, nonce: bytes, data: bytes) -> bytes:
res = []
block_size = 512 // 8
for i, block in enumerate(itertools.batched(data, block_size)):
counter = f"{i:010}".encode()
keystream = sha512(key + nonce + counter).digest()
res.append(xor(keystream, bytes(block)))
return b''.join(res)
def get_ciphertext(nonce: bytes) -> bytes:
data = open("flag.bmp", 'rb').read()
return encrypt(key, nonce, data)
def main():
for i in range(2):
nonce = binascii.unhexlify(input("nonce:"))
print(binascii.hexlify(get_ciphertext(nonce)).decode())
if __name__ == '__main__':
main()
as well as an example_flag.bmp image.
The encryption service implements a custom stream cipher using SHA512. We have the ability to encrypt the flag.bmp file with a chosen nonce. The plaintext data is split into blocks of size 64, and for each block, a keystream is generated and XORed with the block:
\[\large \begin{align} \nonumber keystream_{i} &= SHA512(key \space \| \space nonce \space \| \space ctr_{i}) \\ \nonumber ct _{i} &= keystream_{i} \oplus block_{i} \end{align}\]Using SHA512 in this fashion is dangerous, as it opens up the possibility for a length extension attack. A length extension attack allows a user to calculate the hash $Hash(secret \space | \space message)$ if the length of the secret is known, and the message is known. If we can generate the hash (keystream) for each of the predictable counters, even without knowing the key, we can decrypt the encrypted flag image. In our case, this message is comprised of the chosen nonce and the known counter. In addition to this, SHA512 includes some internal padding since it handles 128-byte chunks at a time.
We begin by sending an empty nonce b'' in the first round. The encryption service will generate a keystream by hashing:
We have a 32 byte key and a 10 byte counter, which means we have 86 bytes of padding being hashed. This $keystream_{0}$ will be a vital piece of information later. We can denote this keystream or hash as $H_{0}$. On the second (and last) query, we set the nonce to $(ctr_{0} \space | \space padding)$. The encryption service will then generate a keystream by hashing:
\[\large keystream_{0} = SHA512(key \space \| \space ctr_{0} \space \| \space padding_{0} \space \| \space ctr_{i} \space \| \space padding_{i})\]Now, the data to be hashed has surpassed 128 bytes in length. Internally, SHA512 will digest the first block $key \space | \space ctr_{0} \space | \space padding_{0}$, update the internal state, then digest the second block $ctr_{i} \space | \space padding_{i}$. The updated internal state will be $H_{0}$. If we are able to recover this $H_{0}$, we can set the known internal state of a SHA512 copy locally, and process each $i$ possible second blocks. This way, we are able to recover all keystreams and hence decrypt the encrypted flag by XOR.
The attack hinges on knowing $H_{0}$ or rather $keystream_{0}$. By sending in an empty nonce to the encryption service, we receive
\[\large ct_{0} = pt_{0} \oplus H_{0}\]If we knew the first plaintext block of the flag, then $H_{0}$ would be recoverable. Luckily for us, the challenge gave us an example_flag.bmp file:
xxd -p -l 64 example_flag.bmp
424dee3b0000000000003600000028000000c40000001a00000001001800
00000000b83b000000000000000000000000000000000000ffffffffffff
ffffffff
The BMP header consists of magic bytes, dimension fields, size fields, and some ffffffffff pixel values at the end (white pixels). This is all predictable information, as the flag will most likely have the same dimensions, the same size (can be verified by the ciphertext size) and also include white pixels in that position. Therefore, with high likelihood, the first plaintext block of the example flag, and the actual flag, is the same.
This way, we can recover $H_{0}$:
known_plain = bytes.fromhex(
"424dee3b0000000000003600000028000000c40000001a00000001001800"
"00000000b83b000000000000000000000000000000000000ffffffffffff"
"ffffffff"
)
io.recvuntil(b"nonce:")
io.sendline(b"") # empty nonce
cipher0 = bytes.fromhex(io.recvline().decode().strip()) # get ciphertext
state_ints = [int.from_bytes(xor(cipher0[i:i+8],known_plain[i:i+8])) for i in range(0, BLOCK_SIZE, 8)] # xor
$H_{0}$ is split up into state_ints to be later processed as the SHA512 internal state. From here, we can prepare the second step. Padding in SHA2 is structured like so:
\x80 + many \x00 + 16-byte length field
We recall that we have 86 bytes of padding, since the counter is 10 bytes and the key is 32 bytes. With the \x80 padding “header” and the 16 byte length field, we are left with 69 null-bytes. We construct the padding and nonce like so:
KEY_LEN = 32
CTR_LEN = 10
first_ctr = b"0" * CTR_LEN
pad = b"\x80" + b"\x00"*69 + ((KEY_LEN + CTR_LEN)*8).to_bytes(16)
nonce = first_ctr + pad
After sending the nonce, we receive the corresponding encrypted flag.bmp. This data has to be handled in blocks of 64. For each block, we generate the predictable counter $ctr_{i}$, then we generate it’s corresponding padding (now 118 bytes since the second block consists of just the counter), before the block is fed to the internal SHA512 copy with the state_ints from $H_{0}$:
def second_block(counter):
total_bits = (KEY_LEN + CTR_LEN + len(pad) + CTR_LEN) * 8
return counter + b"\x80" + b"\x00"*101 + total_bits.to_bytes(16)
for block_index in range(0, len(cipher), BLOCK_SIZE):
counter = f"{block_index//BLOCK_SIZE:010}".encode()
ks_words = sha512_compress(second_block(counter), state_ints)
keystream = b"".join(word.to_bytes(8) for word in ks_words)
The sha512_compress() functions is a boilerplate SHA512 implementation in python from here: https://github.com/KelCodesStuff/Cryptographic-Algorithms/blob/42441605679ee0aa9ad94611c21512cab93ea559/src/sha512.py
With the keystream for each block, we are able to easily recover the plaintext bytes through XOR. The complete plaintext byte-array is written to flag.bmp, which reveals the flag:
ecsc25{never_cross_the_streams}
import struct
# sha512 implementation from https://github.com/KelCodesStuff/Cryptographic-Algorithms/blob/42441605679ee0aa9ad94611c21512cab93ea559/src/sha512.py
K = [
0x428a2f98d728ae22, 0x7137449123ef65cd, 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc,
0x3956c25bf348b538, 0x59f111f1b605d019, 0x923f82a4af194f9b, 0xab1c5ed5da6d8118,
0xd807aa98a3030242, 0x12835b0145706fbe, 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2,
0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 0x9bdc06a725c71235, 0xc19bf174cf692694,
0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65,
0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5,
0x983e5152ee66dfab, 0xa831c66d2db43210, 0xb00327c898fb213f, 0xbf597fc7beef0ee4,
0xc6e00bf33da88fc2, 0xd5a79147930aa725, 0x06ca6351e003826f, 0x142929670a0e6e70,
0x27b70a8546d22ffc, 0x2e1b21385c26c926, 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df,
0x650a73548baf63de, 0x766a0abb3c77b2a8, 0x81c2c92e47edaee6, 0x92722c851482353b,
0xa2bfe8a14cf10364, 0xa81a664bbc423001, 0xc24b8b70d0f89791, 0xc76c51a30654be30,
0xd192e819d6ef5218, 0xd69906245565a910, 0xf40e35855771202a, 0x106aa07032bbd1b8,
0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8,
0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3,
0x748f82ee5defb2fc, 0x78a5636f43172f60, 0x84c87814a1f0ab72, 0x8cc702081a6439ec,
0x90befffa23631e28, 0xa4506cebde82bde9, 0xbef9a3f7b2c67915, 0xc67178f2e372532b,
0xca273eceea26619c, 0xd186b8c721c0c207, 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178,
0x06f067aa72176fba, 0x0a637dc5a2c898a6, 0x113f9804bef90dae, 0x1b710b35131c471b,
0x28db77f523047d84, 0x32caab7b40c72493, 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c,
0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 0x5fcb6fab3ad6faec, 0x6c44198c4a475817,
]
def right_rotate(value, n):
return ((value >> n) | (value << (64 - n))) & 0xffffffffffffffff
def sha512_compress(chunk, hash_state):
if len(chunk) < 128:
chunk += b'\x00' * (128 - len(chunk))
w = [0] * 80
w[:16] = struct.unpack('>16Q', chunk)
for i in range(16, 80):
s0 = right_rotate(w[i - 15], 1) ^ right_rotate(w[i - 15], 8) ^ (w[i - 15] >> 7)
s1 = right_rotate(w[i - 2], 19) ^ right_rotate(w[i - 2], 61) ^ (w[i - 2] >> 6)
w[i] = (w[i - 16] + s0 + w[i - 7] + s1) & 0xffffffffffffffff
a, b, c, d, e, f, g, h = hash_state
for i in range(80):
s1 = right_rotate(e, 14) ^ right_rotate(e, 18) ^ right_rotate(e, 41)
ch = (e & f) ^ (~e & g)
temp1 = (h + s1 + ch + K[i] + w[i]) & 0xffffffffffffffff
s0 = right_rotate(a, 28) ^ right_rotate(a, 34) ^ right_rotate(a, 39)
maj = (a & b) ^ (a & c) ^ (b & c)
temp2 = (s0 + maj) & 0xffffffffffffffff
h = g
g = f
f = e
e = (d + temp1) & 0xffffffffffffffff
d = c
c = b
b = a
a = (temp1 + temp2) & 0xffffffffffffffff
hash_state = [(x + y) & 0xffffffffffffffff for x, y in zip(hash_state, [a, b, c, d, e, f, g, h])]
return hash_state
from pwn import remote, xor
HOST, PORT = "shactr.ecsc25.hack.cert.pl", 5203
BLOCK_SIZE = 64
KEY_LEN = 32
CTR_LEN = 10
# xxd -p -l 64 example_flag.bmp
known_plain = bytes.fromhex(
"424dee3b0000000000003600000028000000c40000001a00000001001800"
"00000000b83b000000000000000000000000000000000000ffffffffffff"
"ffffffff"
)
file_size = 0x3bee
io = remote(HOST, PORT)
io.recvuntil(b"nonce:")
io.sendline(b"")
cipher0 = bytes.fromhex(io.recvline().decode().strip())
state_ints = [int.from_bytes(xor(cipher0[i:i+8],known_plain[i:i+8])) for i in range(0, BLOCK_SIZE, 8)]
first_ctr = b"0" * CTR_LEN
# 0x80 + many 0x00 + 16 bytes length-field
pad = b"\x80" + b"\x00"*69 + ((KEY_LEN + CTR_LEN)*8).to_bytes(16)
nonce = first_ctr + pad
io.recvuntil(b"nonce:")
io.sendline(nonce.hex().encode())
cipher = bytes.fromhex(io.recvline().decode().strip())
io.close()
# ctr(i) \| padding
def second_block(counter):
total_bits = (KEY_LEN + CTR_LEN + len(pad) + CTR_LEN) * 8
# 0x80 + many 0x00 + 16 bytes length-field
return counter + b"\x80" + b"\x00"*101 + total_bits.to_bytes(16)
plaintext = bytearray(len(cipher))
for block_index in range(0, len(cipher), BLOCK_SIZE):
counter = f"{block_index//BLOCK_SIZE:010}".encode()
ks_words = sha512_compress(second_block(counter), state_ints)
keystream = b"".join(word.to_bytes(8) for word in ks_words)
for byte_index, (ct_byte, keystream_byte) in enumerate(zip(cipher[block_index:block_index+BLOCK_SIZE], keystream)):
plaintext[block_index + byte_index] = ct_byte ^ keystream_byte
open("flag.bmp", "wb").write(plaintext)
print("flag.bmp written")