Слышали про одноразовый блокнот? Говорят, эту систему невозможно взломать! Однако это совсем не значит, что прочитать флаг тоже нельзя...
nc crypto.letoctf.org 6789
Флаг: LetoCTF{kN0w_y0uR_r4nDom}
По ссылке доступен исходник сервиса, к которому нам дали доступ.
Сервис представляет из себя простую программу, которая шифрует флаг и показывает результат шифрования.
# impossible
t40MXFO=|7g7{JaN#cDhS5dqu>}m<Jzt
# enough? (y/n): n
4@!HPfx|!w11Bu40g6VzG3K;D-5J%NLi
# enough? (y/n): y
# ok.
Нас пытаются убедить в том, что расшифровка флага невозможна. Попробуем это проверить.
#!/usr/bin/python3
from os import urandom
from signal import alarm
from base64 import b85encode, _b85alphabet
FLAG = b'***' # redacted
LIFETIME = 30
class OTP(object):
def __init__(self, alphabet):
self._alphabet = alphabet
def encrypt(self, plaintext, key):
ciphertext = bytes(self._shift(c, o) for c, o in zip(plaintext, key))
return ciphertext
def _shift(self, char, offset):
index = self._alphabet.index(char)
index += offset
index %= len(self._alphabet)
return self._alphabet[index]
def encrypt_forever():
secret = b85encode(FLAG)
cipher = OTP(_b85alphabet)
while True:
key = urandom(len(secret))
yield cipher.encrypt(secret, key)
def main():
alarm(LIFETIME)
print('# impossible')
for x in encrypt_forever():
print(x.decode())
if input('# enough? (y/n): ') != 'n':
break
print('# ok.')
if __name__ == '__main__':
main()
Исходный код программы очень простой. В бесконечном цикле она выводит зашифрованный флаг и спрашивает у пользователя, достаточно ли ему шифртекстов (или нужно продолжить шифровать).
Перед самим шифрованием программа кодирует флаг в base85. Используемый шифр — одноразовый блокнот. Этот шифр при правильном использовании обладает абсолютной криптостойкостью, но раз нам дали такой таск, логично предположить, что где-то в реализации шифра есть ошибка.
За три первых дня таск решило всего 3 человека, поэтому был опубликован хинт:
В ребусе скрыта подсказка — "biased random", что можно перевести на русский как "смещённый рандом". Посмотрим внимательно на использование случайных чисел в коде.
Для получения случайных байтов используется функция os.urandom
. Затем байты делятся с остатком на 85 (размер алфавита), и каждый символ исходного текста циклически сдвигается по алфавиту на остаток от этого деления. В этом месте стоит проверить, безопасно ли использовать остаток от деления при генерации случайных чисел. После недолгого поиска можно обнаружить, что нет!
Остаток от деления влияет на вероятность появления каждого числа. Если проверить каждый байт из диапазона от 0 до 255, то числа от 1 до 84 встретятся 3 раза, а число 0 — целых 4!
>>> from collections import Counter
>>> Counter(x % 85 for x in range(256))
Counter({0: 4, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3, 7: 3, 8: 3, 9: 3, 10: 3, 11: 3, 12: 3, 13: 3, 14: 3, 15: 3, 16: 3, 17: 3, 18: 3, 19: 3, 20: 3, 21: 3, 22: 3, 23: 3, 24: 3, 25: 3, 26: 3, 27: 3, 28: 3, 29: 3, 30: 3, 31: 3, 32: 3, 33: 3, 34: 3, 35: 3, 36: 3, 37: 3, 38: 3, 39: 3, 40: 3, 41: 3, 42: 3, 43: 3, 44: 3, 45: 3, 46: 3, 47: 3, 48: 3, 49: 3, 50: 3, 51: 3, 52: 3, 53: 3, 54: 3, 55: 3, 56: 3, 57: 3, 58: 3, 59: 3, 60: 3, 61: 3, 62: 3, 63: 3, 64: 3, 65: 3, 66: 3, 67: 3, 68: 3, 69: 3, 70: 3, 71: 3, 72: 3, 73: 3, 74: 3, 75: 3, 76: 3, 77: 3, 78: 3, 79: 3, 80: 3, 81: 3, 82: 3, 83: 3, 84: 3})
Это происходит из-за того, что 256 % 85 == 1
.
Мы можем использовать эту ошибку, чтобы получить флаг. Так как смещение 0 получается чаще всего, то самый встречающийся символ на каждом месте — это оригинальный символ base85-закодированного флага. Осталось только зашифровать флаг достаточное количество раз, чтобы нужные символы выделялись среди остальных.
Полный код эксплоита:
#!/usr/bin/python3
import re
from pwn import process, remote
from base64 import b85decode
from collections import Counter
LOCAL = False
def collect(io, size):
io.recvline()
io.sendline(b'n\n' * size + b'y')
data = io.recvuntil(b'# ok.')
return re.findall(b'enough\? \(y/n\): (.*?)\n', data)
def main(io):
size = 31337
cts = collect(io, size)
length = len(cts[0])
flag = ''
for i in range(length):
counter = Counter(ct[i] for ct in cts)
flag += chr(counter.most_common()[0][0])
print(b85decode(flag))
if __name__ == '__main__':
if LOCAL:
io = process('./babyOTP.py')
else:
io = remote('crypto.letoctf.org', 6789)
main(io)
io.close()
Поездку победителю марафона обеспечивает компания Positive Technologies!
Как вы могли заметить, на протяжении прошедших недель у нас разгорелась нешуточная борьба за первое место — господа @kekov и @rinagert512 все четыре недели дышат друг другу в затылок. У вас есть ровно месяц, чтобы вклиниться в эту битву!
Текущий скорборд:
1. rinagert512 - 1030 PTS
2. kekov - 997 PTS
3. maximadrian - 585 PTS
4. falamous - 549 PTS
5. revker - 450 PTS
6. GabrielFreak - 436 PTS
7. LockeeLamora - 367 PTS
8. k0lt1ra - 328 PTS
9. Rmk1337 - 278 PTS
10. kamikadzem22 - 268 PTS
11. None - 226 PTS
12. jkoimni - 215 PTS
13. ajanshd - 184 PTS
14. rozetkinrobot - 142 PTS
15. None - 128 PTS
16. None - 126 PTS
17. khabarov_oleg - 123 PTS
18. awawa0_0 - 121 PTS
19. None - 118 PTS