Esse desafio apareceu como a challenge de criptografia de nível intermediário no CTF da Nahamcon de 2025. O desafio consiste em aplicar o ataque Bleichenbacher em uma implementação do RSA com padrão PKCS #1.5 através de métodos HTTPS.
O material principal do desafio é um site bastante simples: apenas um sistema de registro e login, junto com um “verificador de cookies” ao qual se tem acesso após o login na conta do administrador ser realizado.
O código fonte do site está separado em duas partes: um arquivo
app.py onde o backend do site está descrito e um arquivo
encryption.py onde fica a parte de criptografia. Além
disso, temos acesso a uma chave criptográfica pública
public_key.pem que nos permite criptografar textos
arbitrários.
Lendo o app.py, percebemos na route /login
que, ao realizar login no site com o username 'admin' e a
senha 'admin' corretamente (quanta criatividade), o app
obtém a flag e a encripta com uma função encrypt()
importada do arquivo encryption.py. A flag encriptada então
é concedida ao usuário na forma de um cookie chamado
secret, que pode ser visto com as ferramentas de
desenvolvimento do navegador (F12 no firefox, na aba “storage”).
Além do cookie secret, um outro cookie chamado
session pode ser observado, que apenas registra a conta em
que o usuário está atualmente logado. Esse cookie é necessário para
acessar a página de verificação de cookies.
Analisando o encryption.py, vemos que a função
encrypt() usa o algoritmo RSA especificado pelo módulo
PKCS1_v1_5 da biblioteca Cryptodome. Essa implementação usa
um padrão antigo de especificações de padding adicionais ao protocolo
RSA padrão que é usado para inserir aleatoriedade no criptotexto do
protocolo.
Basicamente, por mais que a cifra RSA seja muito segura, ela possui uma falha importante: o fato de que ela é perfeitamente determinística, ou seja, textos idênticos são criptografados em códigos idênticos. Como esse padrão pode revelar para um invasor informações em relação ao segredo compartilhado, um protocolo adicional é utilizado para que o criptotexto seja aleatório.
Acontece que esse protocolo adicional precisa de que o texto a ser
encriptado esteja em uma formatação específica. O mais importante para
nós é que os dois primeiros bytes do texto devem ser exatamente
00 e 01, e é esse o padrão que será abusado
por nós na resolução do desafio.
Abrindo a página do módulo PKCS1_v1_5 na documentação do
Cryptodome, nos deparamos com um alerta de que essa implementação foi
deprecada por ser insegura contra ataques de timing, citando o artigo
“Chosen ciphertext attacks against protocols based on the RSA
encryption standard PKCS #1” de Daniel Bleichenbacher como
exemplo.
O ataque Bleichenbacher é um chamado “ataque por oráculo”. Um oráculo é essencialmente uma função que retorna verdadeiro ou falso para uma informação específica do protocolo, com eficiência. No caso do ataque Bleichenbacher, o oráculo responde verdadeiro ou falso em relação à formatação adequada do texto criptografado ao padrão PKCS#1.5. Ou seja, se um texto criptografado é submetido para o oráculo, ele irá decriptografar o texto e responder verdadeiro se ele estiver de acordo com o padrão, e falso caso contrário.
Em contextos gerais, isso pode ser feito cronometrando o tempo de
máquina no processo de decriptografia. No nosso caso isso não é
necessário pois, não a toa, a route '/cookie' do site faz
exatamente esse papel: quando um usuário com uma flag de sessão adequada
envia um texto criptografado com a chave pública do protocolo, a route
retorna 'The secret is all good!' quando o texto decriptado
está de acordo com o padrão e 'The secret is not all good!'
caso contrário.
Com esse oráculo definido, o ataque consiste essencialmente em submeter ao oráculo diversos textos criptografados escolhidos meticulosamente a partir da flag encriptada, esperando que algum deles esteja de acordo com o padrão. Quando um texto de acordo for encontrado, teremos determinado que a mensagem da flag se encontra em um intervalo específico.
Repetindo isso, podemos paulatinamente reduzir este intervalo de possíveis mensagens até que o intervalo seja unitário e, portanto, tenhamos finalmente a flag. Para direções mais específicas, veja o artigo original ou a implementação abaixo.
Após alguma pesquisa, encontramos uma boa implementação do ataque Bleichenbacher no github: link. Essa implementação foi adaptada para o nosso caso específico por questões de tempo, mas implementar o ataque Bleichenbacher do zero não é muito difícil e é um exercício clássico, recomendado ao leitor que deseja se aprofundar no assunto.
Para comunicar com o site - isso é, enviar textos criptografados e
obter a resposta do oráculo - utilizamos a biblioteca
requests, que é capaz de realizar a troca através de
métodos HTML. Dessa forma, a função oracle() da
implementação original foi substituida por um snippet que
atribui os cookies adequados a um dicionário, usa a biblioteca requests
para obter a informação da route /cookie utilizando os
cookies no dicionário através do método GET. A função então retorna
True ou False dependendo do retorno do
site.
Além disso, substituímos a variável global CT pela flag
encriptada obtida com o login no administrador e obtivemos a chave
pública (composta pelas variáveis globais N e
E) a partir do arquivo public_key.pem,
fazendo
from Crypto.PublicKey import RSA
key = RSA.importKey(open('public_key.pem').read())
print(key.n)
print(key.e)O código final obtido foi
#! /usr/bin/env python3
# Copyright (C) 2019 Karim Kanso. All Rights Reserved.
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
import cryptography.hazmat.primitives.asymmetric.rsa as rsa
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import serialization
import binascii
import math
import textwrap
import requests
N = 120683333603624757893641046934577511226843768244012132972282979153753488033635390572150689597610255481939401840223183741171171364046175014175384685510752228906525962162283786000346053779210799417709613727372516851827591055038801449653686434040511781341380599703397079155901185621695921330832552673808524393101
E = 65537
CT = bytes.fromhex('572ff14cd898df03a9e4311e41eb4fbc1b0343272d85a678dceff8b1afa7fbd74ba51ef48728eae606d3585c12a699382183d073637ce260319ec15b0a89abcb4cdf6dc1184831399b9616f30c6337444774d75ec76883ddd9fa3a20752e307fb93979550010efa65b33afbf7eedd81713f59b65830d6a5b4386443ad65bbe19')
url = 'http://challenge.nahamcon.com:30429/cookie'
def local_setup(newkey=False):
def oracle(ct):
cookie = ct.hex()
cookies={'secret' : cookie, 'session' : 'eyJpZCI6MSwidXNlcm5hbWUiOiJhZG1pbiJ9.aDH03g.SsszTbkaeHrG5IHU5wqCzxDaw2s'}
r = requests.get(url, cookies=cookies)
txt = r.text
if txt == 'The secret is not all good!':
print(f'{oracle_ctr} False!!')
return False
elif txt == 'The secret is all good!':
print(f'{oracle_ctr} True!!')
return True
else:
print(f'{oracle_ctr} ERROR!')
return False
return CT, oracle, E, N
# these two defs avoid rounding issues with floating point during
# division (especially with large numbers)
def ceildiv(a, b):
return -(-a // b)
def floordiv(a, b):
return (a // b)
oracle_ctr = 0
def main():
print('Bleichenbacher RSA padding algorithm')
print(' for more info see 1998 paper.')
print()
# setup parameters, change local_setup with alternative
# implementation, such as an oracle that uses a real server
ct, oracle, e, n = local_setup(newkey=True)
# byte length of n
k = int(ceildiv(math.log(n,2), 8))
# convert ciphertext from bytes into integer
c = int.from_bytes(ct, 'big')
# lift oracle defition to take integers
def oracle_int(x):
global oracle_ctr
oracle_ctr = oracle_ctr + 1
if oracle_ctr % 100000 == 0:
print("[{}K tries] ".format(oracle_ctr // 1000), end='', flush=True)
return oracle(x.to_bytes(k, 'big'))
# define B as size of ciphertext space
# as first two bytes are 00 02, use 2^(keysize - 16)
B = pow(2, 8 * (k-2))
# precompute constants
_2B = 2 * B
_3B = 3 * B
multiply = lambda x, y: (x * pow(y, e, n)) % n
# should be identity as c is valid cipher text
c0 = multiply(c, 1)
assert c0 == c
i = 1
M = [(_2B, _3B - 1)]
s = 1
# ensure everything is working as expected
if oracle_int(c0):
print('Oracle ok, implicit step 1 passed')
else:
print('Oracle fail sanity check')
exit(1)
while True:
if i == 1:
print('start case 2.a: ', end='', flush=True)
ss = ceildiv(n, _3B)
while not oracle_int(multiply(c0, ss)):
ss = ss + 1
print('done. found s1 in {} iterations: {}'.format(
ss - ceildiv(n, _3B),ss))
else:
assert i > 1
if len(M) > 1:
print('start case 2.b: ', end='', flush=True)
ss = s + 1
while not oracle_int(multiply(c0, ss)):
ss = ss + 1
print('done. found s{} in {} iterations: {}'.format(
i, ss-s, ss))
else:
print('start case 2.c: ', end='', flush=True)
assert len(M) == 1
a, b = M[0]
r = ceildiv(2 * (b * s - _2B), n)
ctr = 0
while True:
# note: the floor function below needed +1 added
# to it, this is not clear from the paper (see
# equation 2 in paper where \lt is used instead of
# \lte).
for ss in range(
ceildiv(_2B + r * n, b),
floordiv(_3B + r * n, a) + 1):
ctr = ctr + 1
if oracle_int(multiply(c0, ss)):
break
else:
r = r + 1
continue
break
print('done. found s{} in {} iterations: {}'.format(i, ctr, ss))
# step 3, narrowing solutions
MM = []
for a,b in M:
for r in range(ceildiv(a * ss - _3B + 1, n),
floordiv(b * ss - _2B, n) + 1):
m = (
max(a, ceildiv(_2B + r * n, ss)),
min(b, floordiv(_3B - 1 + r * n, ss))
)
if m not in MM:
MM.append(m)
print('found interval [{},{}]'.format(m[0],m[1]))
# step 4, compute solutions
M = MM
s = ss
i = i + 1
if len(M) == 1 and M[0][0] == M[0][1]:
print()
print('Completed!')
print('used the oracle {} times'.format(oracle_ctr))
# note, no need to find multiplicative inverse of s0 in n
# as s0 = 1, so M[0][0] is directly the message.
message = M[0][0].to_bytes(k, 'big')
print('raw decryption: {}'.format(
binascii.hexlify(message).decode('utf-8')))
if message[0] != 0 or message[1] != 2:
return
message = message[message.index(b'\x00',1) + 1:]
print('unpadded message hex: {}'.format(
binascii.hexlify(message).decode('utf-8')))
try:
print('unpadded message ascii: {}'.format(
message.decode('utf-8')))
except UnicodeError:
pass
return
if __name__ == "__main__":
main()Esse programa foi executado por cerca de 3 ou 4 horas, sempre tomando cuidado para manter a challenge correndo para o que o site não caisse. No fim das contas, foram feitas 30387 queries ao oráculo até que finalmente obtivemos a flag, concluindo o desafio.