Как и многие специалисты по ИБ, я очень люблю разминать мозг различными головоломками. Идеальным для меня является формат CTF, позволяющий проверить свои знания и толику нестандартного мышления на различных типах задач.
Сегодня я хочу рассказать о первой из трёх задач из категории Crypto с прошлогоднего CTF HTB «Cyber Apocalypse». Задачи на криптографию моя отдельная любовь, поскольку позволяют нетрадиционно взглянуть как на привычные криптографические алгоритмы, так и на неудачные попытки их использования. Особенно интересно искать уязвимость в самописных алгоритмах. Последнее наиболее опасно в реальной жизни, поскольку некоторые разработчики уверены, что уж они то смогут как минимум правильно реализовать известный алгоритм, а не тянуть за собой OpenSSL. Некоторые даже стараются написать свой собственный алгоритм и тем самым обеспечить надежную защиту данных!
Множество CTF задач разной сложности обычно позволяют быстро развенчать этот миф)
Задача первая. Android-in-the-middle
За что я люблю CTF от HTB, там каждая задачка это одновременно и красивая история, и небольшая подсказка в названии.
Начнём сегодня с простой задачи категории "Easy". Судя по названию, здесь есть явная отсылка к MITM атаке.
Код задачи лежит под катом. Если захотите повторить решение или найти свой вариант в ожидании выхода статей - вот исходный код всех трёх задач на Я.Диске.
Задача состоит всего из одного файла.
source.py
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
import random
import socketserver
import signal
FLAG = "HTB{--REDACTED--}"
DEBUG_MSG = "DEBUG MSG - "
p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2
class Handler(socketserver.BaseRequestHandler):
def handle(self):
signal.alarm(0)
main(self.request)
class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
def sendMessage(s, msg):
s.send(msg.encode())
def recieveMessage(s, msg):
sendMessage(s, msg)
return s.recv(4096).decode().strip()
def decrypt(encrypted, shared_secret):
key = hashlib.md5(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
message = cipher.decrypt(encrypted)
return message
def main(s):
sendMessage(s, DEBUG_MSG + "Generating The Global DH Parameters\n")
sendMessage(s, DEBUG_MSG + f"g = {g}, p = {p}\n")
sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")
sendMessage(s, DEBUG_MSG + "Generating The Public Key of CPU...\n")
c = random.randrange(2, p - 1)
C = pow(g, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n")
sendMessage(s, DEBUG_MSG + "Public Key is: ???\n\n")
M = recieveMessage(s, "Enter The Public Key of The Memory: ")
try:
M = int(M)
except:
sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
exit()
sendMessage(s, "\n" + DEBUG_MSG + "The CPU Calculates The Shared Secret\n")
shared_secret = pow(M, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")
encrypted_sequence = recieveMessage(
s, "Enter The Encrypted Initialization Sequence: ")
try:
encrypted_sequence = bytes.fromhex(encrypted_sequence)
assert len(encrypted_sequence) % 16 == 0
except:
sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
exit()
sequence = decrypt(encrypted_sequence, shared_secret)
if sequence == b"Initialization Sequence - Code 0":
sendMessage(s, "\n" + DEBUG_MSG +
"Reseting The Protocol With The New Shared Key\n")
sendMessage(s, DEBUG_MSG + f"{FLAG}")
else:
exit()
if __name__ == '__main__':
socketserver.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
server.serve_forever()
Большая часть задач на CTF имеют схожую структуру. Они поднимают сервер на 1337 порту и ждут подключения. Большинство не требует даже наличия веб-браузера, достаточно любимого консольного клиента вроде telnet или netcat.
Прежде чем лезть в дебри кода, я рекомендую всегда просто запустить код и ввести в него различные данные, что позволяет получить беглое представление о том как работает программа.
└─$ nc localhost 1337
DEBUG MSG - Generating The Global DH Parameters
DEBUG MSG - g = 2, p = 10177459997049772558637057109490700048394574760284564283959324525695097805837401714582821820424475480057537817583807249627119267268524840254542683041588432363128111683358536204391767254517057859973149680238170237977230020947732558089671785239121778309357814575486749623687357688511361367822815452806637006568922401890961240475060822815400430220536180181951862931844638638933951683988349468373510128406899660648258602475728913837826845743111489145006566908004165703542907243208106044538037004824530893555918497937074663828069774495573109072469750423175863678445547058247156187317168731446722852098571735569138516533993
DEBUG MSG - Calculation Complete
DEBUG MSG - Generating The Public Key of CPU...
DEBUG MSG - Calculation Complete
DEBUG MSG - Public Key is: ???
Enter The Public Key of The Memory: 100000000
DEBUG MSG - The CPU Calculates The Shared Secret
DEBUG MSG - Calculation Complete
Enter The Encrypted Initialization Sequence: 1111111111111111
DEBUG MSG - Unexpected Error Occured
В данном случае речь явно идет об алгоритме Diffie–Hellman. Сошлюсь на очень хорошее и подробное описание в английской Википедии. Русский перевод, к сожалению, уступает оригиналу. Значения, выделенные красным, являются секретными, а синие - открытыми.
Теперь подробно рассмотрим работу кода.
У нас есть два заранее известных параметра p и g
p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2
После чего генерируется секретный ключ c и ключ С, который мы должны отдать второму абоненту. Однако, здесь этот ключ нам не отдают, иначе задача была бы тривиальным обменом ключами по алгоритму DH. На картинке это шаг 2, когда Alice должна отдать нам A = g^a mod p. В коде задачи это переменная С.
sendMessage(s, DEBUG_MSG + "Generating The Public Key of CPU...\n")
c = random.randrange(2, p - 1)
C = pow(g, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n")
sendMessage(s, DEBUG_MSG + "Public Key is: ???\n\n")
Дальше нас просят ввести свой ключ М (это шаг 3 в алгоритме, когда мы должны отдать B). Значение должно быть целым числом, иначе нам вернут ошибку и программа завершится.
M = recieveMessage(s, "Enter The Public Key of The Memory: ")
try:
M = int(M)
except:
sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
exit()
Теперь финальная часть алгоритма DH. Вычисление общего секрета. Это шаг 4 алгоритма.
sendMessage(s, "\n" + DEBUG_MSG + "The CPU Calculates The Shared Secret\n")
shared_secret = pow(M, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")
Здесь, в идеальном мире, мы тоже должны были бы вычислить общий секрет, но нам не отдали ключ С, поэтому о его значении мы можем только догадываться) В этом и состоит задача CTF. Как воздействовать на алгоритм DH, чтобы получить значение общего секрета? Дальше он понадобится нам для получения флага.
Флаг получается очень просто. Мы должны отдать фразу "Initialization Sequence - Code 0" зашифрованную алгоритмом AES в режиме ECB на общем ключе шифрования. Если в результате расшифровки на общем ключе (который мы не знаем) фраза совпадёт с ожидаемой, сервер вернёт нам значение флага. Вроде всё просто, но нужно как-то узнать ключ С, который нам не отдали. Или нет?
def decrypt(encrypted, shared_secret):
key = hashlib.md5(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
message = cipher.decrypt(encrypted)
return message
...........
encrypted_sequence = recieveMessage(
s, "Enter The Encrypted Initialization Sequence: ")
try:
encrypted_sequence = bytes.fromhex(encrypted_sequence)
assert len(encrypted_sequence) % 16 == 0
except:
sendMessage(s, DEBUG_MSG + "Unexpected Error Occured\n")
exit()
sequence = decrypt(encrypted_sequence, shared_secret)
if sequence == b"Initialization Sequence - Code 0":
sendMessage(s, "\n" + DEBUG_MSG +
"Reseting The Protocol With The New Shared Key\n")
sendMessage(s, DEBUG_MSG + f"{FLAG}")
else:
exit()
Еще раз вернёмся к коду и алгоритму DH. Единственный параметр (не считая зашифрованного сообщения), на который мы можем воздействовать, это ключ M.
Общий секрет shared_secret, и он же ключ шифрования, считается как M в степени c по модулю p.
sendMessage(s, "\n" + DEBUG_MSG + "The CPU Calculates The Shared Secret\n")
shared_secret = pow(M, c, p)
sendMessage(s, DEBUG_MSG + "Calculation Complete\n\n")
Однако, параметр c мы не знаем, поскольку он является случайным числом в диапазоне (2, p-1)
c = random.randrange(2, p - 1)
C = pow(g, c, p)
Защита DH строится на том, что ключ M считается так же, как ключ С, т.е. это число g возведенное в заведомо неизвестную большую степень по модулю p. Однако, здесь мы можем напрямую манипулировать данным значением!
Существуют всего 2 значения, которые предсказуемо ведут себе при возведении в любую (неизвестную нам) степень. Это 0 (ноль) и 1 (единица). Т.е. если в качестве ключа M мы отдадим значение 0 или 1, то shared_secret всегда будет равен 0 или 1!
Осталось решить задачу с шифрованием нужной строки и получение её в виде hex_encoded, как ожидает программа.
Чтобы было понятнее, откуда в итоге у нас берется shared_secret, код немного избыточный и включает в себя оригинальную генерацию параметра c.
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
import hashlib
import random
p = 0x509efab16c5e2772fa00fc180766b6e62c09bdbd65637793c70b6094f6a7bb8189172685d2bddf87564fe2a6bc596ce28867fd7bbc300fd241b8e3348df6a0b076a0b438824517e0a87c38946fa69511f4201505fca11bc08f257e7a4bb009b4f16b34b3c15ec63c55a9dac306f4daa6f4e8b31ae700eba47766d0d907e2b9633a957f19398151111a879563cbe719ddb4a4078dd4ba42ebbf15203d75a4ed3dcd126cb86937222d2ee8bddc973df44435f3f9335f062b7b68c3da300e88bf1013847af1203402a3147b6f7ddab422d29d56fc7dcb8ad7297b04ccc52f7bc5fdd90bf9e36d01902e0e16aa4c387294c1605c6859b40dad12ae28fdfd3250a2e9
g = 2
def encrypt(text, shared_secret):
key = hashlib.md5(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc_message = cipher.encrypt(text)
return enc_message
c = random.randrange(2, p - 1)
M = 1
shared_secret = pow(M, c, p)
shared_sequence = encrypt(b"Initialization Sequence - Code 0", shared_secret)
print("Encrypted Initialization Sequence is: " + shared_sequence.hex() + '\n\n')
После запуска мы получаем значение, которое нужно просто отдать серверу и получить флаг!
Какие выводы можно сделать отсюда? Реализуя даже очень известные алгоритмы, не забывайте добавлять проверки на валидность получаемых значений. В алгоритме DH ключ никогда не должен вырождаться и быть равным 1 или 0. Если бы такая проверка существовала в коде, то задача была бы уже нерешаемой.
UPD. В комментариях справедливо говорят, что при M=p-1 решение тоже можно угадать с вероятностью 50%, т.к. shared_secret будет равен либо 1 либо p-1.
gchebanov
Неправда ваша, если взять например
M=p-1
, то вариантов дляpow(M,c,p)
всего два:1
иp-1
, шанс угадать 50%.gchebanov
Сразу докину, на случай если напишите что это частный случай и его тоже надо добавить в список на проверку, после чего задача станет нерешаемой.
При
в примерно 1/4 всех случаев генерации
c
плюс задачка на подумать, как я получил эти значения.
HappyGroundhog Автор
Да я больше чем уверен, что таких "частных" случаев там еще больше чем достаточно...
Однажды попадалась интересная задача на CTF, где нужно было ввести число, которое одновременно должно было бы быть и простым и не простым числом. Я решить не смог. Там одна из проверок была "библиотечной" функцией, т.е. гарантированно реализована правильно, а вторая уже самописная реализация одного из алгоритмов сита для проверки простого числа, которая тоже имела некоторые "частные случаи" и в некоторых случаях ошибочно считала простым числом. Естественно речь шла о простых числах достаточной длины.
HappyGroundhog Автор
Хм. А вы действительно правы, спасибо! Интересное поведение) Вот поэтому я и не считаю себя достаточно разбирающимся в криптографии. Значит есть еще вариант решения этого CTF, но с 50% вероятностью.
gchebanov
Небольшая подсказка: есть вариант и с вероятностью
0.222...%
!HappyGroundhog Автор
Спасибо) Серьёзная математика не самая сильная моя сторона, потому я обычно ломаюсь уже на задачах про элиптические кривые.