Neste desafio, exploramos o conceito de cifração com chaves com geração inadequada. O desafio consiste em decifrar um criptograma cifrado com uma chave fraca, visto que a segurança deste conceito depende inteiramente da impossibilidade de adivinhar a chave.
Para realizar o desafio, foi nos fornecido o seguinte excerto cifrado:
ca67bf155d4a1eb428fa6f82c02204e325efa970308e
Além disso, foi-nos fornecido o seguinte nonce:
533175e178a82db290be5201e49690aa
Sabemos que a flag está cifrada no criptograma, e que a chave utilizada para cifrar a flag foi gerada de forma má. O objetivo é recuperar a flag.
O programa utilizado para criar foi nos fornecido, e é o seguinte:
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
import os
KEYLEN = 16
def gen():
offset = 3 # Hotfix to make Crypto blazing fast!!
key = bytearray(b'\x00'*(KEYLEN-offset))
key.extend(os.urandom(offset))
return bytes(key)
def enc(k, m, nonce):
cipher = Cipher(algorithms.AES(k), modes.CTR(nonce))
encryptor = cipher.encryptor()
cph = b""
cph += encryptor.update(m)
cph += encryptor.finalize()
return cph
def dec(k, c, nonce):
cipher = Cipher(algorithms.AES(k), modes.CTR(nonce))
decryptor = cipher.decryptor()
msg = b""
msg += decryptor.update(c)
msg += decryptor.finalize()
return msgAnalisando este código, podemos ver que a chave é gerada de forma aleatória apenas nos últimos 3 bytes, sendo os primeiros 13 bytes sempre iguais a 0. Isto significa que a chave é muito mais fraca do que deveria ser, pois apenas 3 bytes são aleatórios.
Graças a este erro, apenas existem 2^24 chaves possíveis, o que possibilita um ataque de força bruta.
Para decifrar o criptograma, criamos um script que gera todas as chaves possíveis e tenta decifrar o criptograma com cada uma delas. Se o resultado começar por flag{, então a chave é a correta.
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from itertools import product
# Info fornecida
nonce = bytes.fromhex("533175e178a82db290be5201e49690aa")
ciphertext = bytes.fromhex("ca67bf155d4a1eb428fa6f82c02204e325efa970308e")
# Função de decifração AES-CTR
def decrypt_with_key(key, ciphertext, nonce):
cipher = Cipher(algorithms.AES(key), modes.CTR(nonce))
decryptor = cipher.decryptor()
return decryptor.update(ciphertext) + decryptor.finalize()
# Brute force
def brute_force_find_flag():
KEYLEN = 16
prefix = b'\x00' * (KEYLEN - 3)
for suffix in product(range(256), repeat=3):
key = prefix + bytes(suffix)
plaintext_candidate = decrypt_with_key(key, ciphertext, nonce)
print(plaintext_candidate)
if plaintext_candidate.startswith(b'flag{'):
print(f"Found flag: {plaintext_candidate.decode()}")
return plaintext_candidate.decode()
brute_force_find_flag()Após cerca de 1-2 minutos, o script encontrou a flag:
Found flag: flag{treyiucuftabpoev}
Esta task pretende calcular experimentalmente quão grande teria de ser o offset da geração de chave para que um computador não conseguisse decifrar o criptograma em 10 anos.
Para esta experiência, utilizamos o computador portátil de um dos membros do grupo, um Asus VivoBook com um processador AMD Ryzen 7 5700U e 16GB de RAM.
Alteramos o script de decriptação para calcular quantas chaves por segundo o computador consegue testar em média.
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from itertools import product
import time
# Info fornecida
nonce = bytes.fromhex("533175e178a82db290be5201e49690aa")
ciphertext = bytes.fromhex("ca67bf155d4a1eb428fa6f82c02204e325efa970308e")
# Função de decifração AES-CTR
def decrypt_with_key(key, ciphertext, nonce):
cipher = Cipher(algorithms.AES(key), modes.CTR(nonce))
decryptor = cipher.decryptor()
return decryptor.update(ciphertext) + decryptor.finalize()
# Brute force
def brute_force_find_flag():
KEYLEN = 16
prefix = b'\x00' * (KEYLEN - 3)
attempts = 0 # guardamos o número total de tentativas
start_time = time.time() # início do cronómetro
for suffix in product(range(256), repeat=3):
key = prefix + bytes(suffix)
plaintext_candidate = decrypt_with_key(key, ciphertext, nonce)
attempts += 1 # incremento de tentativas
# retiramos o print para não sobrecarregar o output
if plaintext_candidate.startswith(b'flag{'):
end_time = time.time() # fim do cronómetro
elapsed_time = end_time - start_time # tempo total
attempts_per_second = attempts / elapsed_time # média de tentativas por segundo
print(f"Found flag: {plaintext_candidate.decode()}")
print(f"Average attempts per second: {attempts_per_second:.2f}")
return plaintext_candidate.decode()
brute_force_find_flag()Após correr o script até encontrar a flag, obtivemos o seguinte resultado:
Average attempts per second: 56018.54
Com este valor, podemos calcular quantas chaves o computador consegue testar em 10 anos.
10 anos = 31,536,000 segundos
31,536,000 * 56018.54 = 1,766,600,677,000 chaves
Para calcular o offset necessário, basta calcular o logaritmo na base 256 do número de chaves testadas em 10 anos.
log_256(1,766,600,677,000) ≈ 5.5
Portanto, o offset necessário para que o computador não consiga decifrar o criptograma em 10 anos é de pelo menos 6 bytes.
Esta task explora a ideia do autor decidir usar um nonce com apenas 1 byte e não o partilhar na rede.
Se o nonce for de 1 byte, existem apenas 256 valores possíveis para ele. Isto implica que o atacante tem de testar as 256 opções possíveis para o nonce sempre que tentar uma chave.
Esta alteração aumentaria o número de tentativas necessárias para decifrar o criptograma.
2^8 * 2^24 = 2^32 possibilidades
Como vimos na task anterior, o computador utilizado consegue testar cerca de 56,000 chaves por segundo. Portanto, o tempo necessário para testar todas as combinações seria:
2^32 / 56018.54 ≈ 76670 segundos ≈ 21 horas
Concluímos que, mesmo com a complicação extra do nonce, o criptograma seria decifrado em menos de 1 dia. Ou seja, não foi lá grande ideia por parte do autor... outra vez...