Пока участники квеста готовятся к финальным испытаниям, а снег потихоньку тает в городах, расскажем для тех, кто пропустил начало, о пройденных этапах интерактивного хакатона, и что ждать от финала.
Напомним, с чего всё началось: участники уже раскрыли секрет «Загадочной визитки», которую разобрали до последнего волокна и в результате залетели в блокчейн, а далее и в межпланетную файловую систему с новой порцией загадок.
Подробнее о первом этапе прохождения в прошлой статье.
Мини-оглавление:
Разбор задание 3.1
Разбор задания 3.2
Кому пельменей?
Смешные моменты
Итак, что же ждало участников дальше?
Для того чтобы попасть во вторую часть квеста, необходимо было написать в матрицу и получить дальнейшие указания от нашего загадочного John Roe.
▍ Задание 3.1
Вскоре после написания сообщения
@phuuki4uta:matrix.org получим пару файлов: code-XXXXX.pyc и code-XXXXX.pyc.sig (где XXXXX — 5 цифр) вместе с сообщением «I am a colleague of John Doe. He've passed something for you. Good luck!«. Как и прежде проверим подпись при помощи .sig-файла, и при помощи утилиты file выясним, что в файле .pyc байт-код программы на Python 3.7. Вооружимся xdis и дизассемблируем код:Что же, и правда похоже на операции виртуальной машины интерпретатора CPython, эталонной реализации языка Python. Также заметим, что имена функций и переменных по-видимому обфусцированы для затруднения анализа.Дизассемблированный код# Python bytecode 3.7.0 (3394) # Timestamp in code: 0 (1970-01-01 03:00:00) # Source code size mod 2**32: 1357 bytes # Method Name: <module> # Filename: code-XXXXX.py # Argument count: 0 # Keyword-only arguments: 0 # Number of locals: 0 # Stack size: 6 # Flags: 0x00000040 (NOFREE) # First Line: 3 # Constants: # 0: <Code3 code object wies3 at 0x7f699aa41840, file code-XXXXX.py>, line 3 # 1: 'wies3' # 2: 0 # 3: 3 # 4: 268435455 # 5: 1 # 6: 2 # 7: 4 # 8: 2033349222 # 9: 859399546 # 10: 1914726229 # 11: 545537777 # 12: 4259271294 # 13: 3762695033 # 14: 2530072744 # 15: 1774340374 # 16: 314947544 # 17: 'Ciphertext = ' # 18: 'Plaintext = ?' # 19: None # Names: # 0: wies3 # 1: roh3s # 2: AssertionError # 3: ieng8 # 4: kiiv4 # 5: op7bi # 6: len # 7: print 3: 0 LOAD_CONST (<Code3 code object wies3 at 0x7f699aa41840, file code-XXXXX.py>, line 3) 2 LOAD_CONST ('wies3') 4 MAKE_FUNCTION (Neither defaults, keyword-only args, annotations, nor closures) 6 STORE_NAME (wies3) 31: 8 LOAD_CONST (0) 10 LOAD_CONST (0) 12 LOAD_CONST (0) 14 LOAD_CONST (0) 16 BUILD_LIST 4 18 STORE_NAME (roh3s) 32: 20 LOAD_NAME (roh3s) 22 LOAD_CONST (3) 24 BINARY_SUBSCR 26 LOAD_CONST (268435455) 28 BINARY_AND 30 LOAD_CONST (0) 32 COMPARE_OP (!=) 34 POP_JUMP_IF_TRUE (to 40) 36 LOAD_GLOBAL (AssertionError) 38 RAISE_VARARGS (exception instance) 35: >> 40 LOAD_CONST (0) 42 LOAD_CONST (0) 44 LOAD_CONST (0) 46 LOAD_CONST (0) 48 BUILD_LIST 4 50 STORE_NAME (ieng8) 36: 52 LOAD_NAME (ieng8) 54 LOAD_CONST (3) 56 BINARY_SUBSCR 58 LOAD_CONST (268435455) 60 BINARY_AND 62 LOAD_CONST (0) 64 COMPARE_OP (!=) 66 POP_JUMP_IF_TRUE (to 72) 68 LOAD_GLOBAL (AssertionError) 70 RAISE_VARARGS (exception instance) 39: >> 72 LOAD_CONST (0) 74 LOAD_CONST (0) 76 LOAD_CONST (0) 78 LOAD_CONST (0) 80 LOAD_CONST (0) 82 BUILD_LIST 5 84 STORE_NAME (kiiv4) 40: 86 LOAD_NAME (kiiv4) 88 LOAD_CONST (0) 90 BINARY_SUBSCR 92 LOAD_CONST (0) 94 COMPARE_OP (!=) 96 POP_JUMP_IF_FALSE (to 146) 98 LOAD_NAME (kiiv4) 100 LOAD_CONST (1) 102 BINARY_SUBSCR 104 LOAD_CONST (0) 106 COMPARE_OP (!=) 108 POP_JUMP_IF_FALSE (to 146) 110 LOAD_NAME (kiiv4) 112 LOAD_CONST (2) 114 BINARY_SUBSCR 116 LOAD_CONST (0) 118 COMPARE_OP (!=) 120 POP_JUMP_IF_FALSE (to 146) 122 LOAD_NAME (kiiv4) 124 LOAD_CONST (3) 126 BINARY_SUBSCR 128 LOAD_CONST (0) 130 COMPARE_OP (!=) 132 POP_JUMP_IF_FALSE (to 146) 134 LOAD_NAME (kiiv4) 136 LOAD_CONST (4) 138 BINARY_SUBSCR 140 LOAD_CONST (0) 142 COMPARE_OP (!=) 144 POP_JUMP_IF_TRUE (to 150) >> 146 LOAD_GLOBAL (AssertionError) 148 RAISE_VARARGS (exception instance) 42: >> 150 LOAD_CONST (2033349222) 152 LOAD_CONST (859399546) 154 BUILD_LIST 2 156 STORE_NAME (op7bi) 44: 158 LOAD_NAME (wies3) 160 LOAD_NAME (op7bi) 162 LOAD_NAME (len) 164 LOAD_NAME (op7bi) 166 CALL_FUNCTION (1 positional argument) 168 LOAD_NAME (roh3s) 170 CALL_FUNCTION (3 positional arguments) 172 POP_TOP 45: 174 LOAD_NAME (wies3) 176 LOAD_NAME (op7bi) 178 LOAD_NAME (len) 180 LOAD_NAME (op7bi) 182 CALL_FUNCTION (1 positional argument) 184 LOAD_NAME (ieng8) 186 CALL_FUNCTION (3 positional arguments) 188 POP_TOP 47: 190 LOAD_NAME (op7bi) 192 LOAD_CONST (1914726229) 194 LOAD_CONST (545537777) 196 BUILD_LIST 2 198 COMPARE_OP (==) 200 POP_JUMP_IF_TRUE (to 206) 202 LOAD_GLOBAL (AssertionError) 204 RAISE_VARARGS (exception instance) 49: >> 206 LOAD_NAME (wies3) 208 LOAD_NAME (kiiv4) 210 LOAD_NAME (len) 212 LOAD_NAME (kiiv4) 214 CALL_FUNCTION (1 positional argument) 216 LOAD_NAME (roh3s) 218 CALL_FUNCTION (3 positional arguments) 220 POP_TOP 50: 222 LOAD_NAME (wies3) 224 LOAD_NAME (kiiv4) 226 LOAD_NAME (len) 228 LOAD_NAME (kiiv4) 230 CALL_FUNCTION (1 positional argument) 232 LOAD_NAME (ieng8) 234 CALL_FUNCTION (3 positional arguments) 236 POP_TOP 52: 238 LOAD_NAME (kiiv4) 240 LOAD_CONST (4259271294) 242 LOAD_CONST (3762695033) 244 LOAD_CONST (2530072744) 246 LOAD_CONST (1774340374) 248 LOAD_CONST (314947544) 250 BUILD_LIST 5 252 COMPARE_OP (==) 254 EXTENDED_ARG (256) 256 POP_JUMP_IF_TRUE (to 262) 258 LOAD_GLOBAL (AssertionError) 260 RAISE_VARARGS (exception instance) 53: >> 262 LOAD_NAME (print) 264 LOAD_CONST ('Ciphertext = ') 266 LOAD_NAME (kiiv4) 268 CALL_FUNCTION (2 positional arguments) 270 POP_TOP 54: 272 LOAD_NAME (print) 274 LOAD_CONST ('Plaintext = ?') 276 CALL_FUNCTION (1 positional argument) 278 POP_TOP 280 LOAD_CONST (None) 282 RETURN_VALUE # Method Name: wies3 # Filename: code-XXXXX.py # Argument count: 3 # Keyword-only arguments: 0 # Number of locals: 7 # Stack size: 6 # Flags: 0x00000003 (NEWLOCALS | OPTIMIZED) # First Line: 3 # Constants: # 0: None # 1: <Code3 code object fie1z at 0x7f699aa415a0, file code-XXXXX.py>, line 5 # 2: 'wies3.<locals>.fie1z' # 3: <Code3 code object xaeg4 at 0x7f699aa417b0, file code-XXXXX.py>, line 8 # 4: 'wies3.<locals>.xaeg4' # 5: 0 # 6: 562984899 # 7: 1 # 8: 6 # 9: 52 # 10: 2 # 11: 3 # Varnames: # fau0m, tuki6, ooch0, fie1z, xaeg4, oon0j, zae3u # Positional arguments: # fau0m, tuki6, ooch0 # Local variables: # 3: fie1z # 4: xaeg4 # 5: oon0j # 6: zae3u # Cell variables: # 0: aph7a # 1: coh1p # 2: di5ei # 3: eing8 # 4: ik4so # 5: ooch0 5: 0 LOAD_CLOSURE (aph7a) 2 LOAD_CLOSURE (coh1p) 4 LOAD_CLOSURE (di5ei) 6 LOAD_CLOSURE (eing8) 8 LOAD_CLOSURE (ik4so) 10 LOAD_CLOSURE (ooch0) 12 BUILD_TUPLE 6 14 LOAD_CONST (<Code3 code object fie1z at 0x7f699aa415a0, file code-XXXXX.py>, line 5) 16 LOAD_CONST ('wies3.<locals>.fie1z') 18 MAKE_FUNCTION (closure) 20 STORE_FAST (fie1z) 8: 22 LOAD_CONST (<Code3 code object xaeg4 at 0x7f699aa417b0, file code-XXXXX.py>, line 8) 24 LOAD_CONST ('wies3.<locals>.xaeg4') 26 MAKE_FUNCTION (Neither defaults, keyword-only args, annotations, nor closures) 28 STORE_FAST (xaeg4) 11: 30 LOAD_FAST (fau0m) 32 LOAD_CONST (0) 34 BINARY_SUBSCR 36 STORE_DEREF (aph7a) 12: 38 LOAD_CONST (0) 40 STORE_DEREF (ik4so) 13: 42 LOAD_CONST (562984899) 44 STORE_FAST (oon0j) 14: 46 LOAD_FAST (fau0m) 48 LOAD_FAST (tuki6) 50 LOAD_CONST (1) 52 BINARY_SUBTRACT 54 BINARY_SUBSCR 56 STORE_DEREF (di5ei) 15: 58 LOAD_CONST (6) 60 LOAD_CONST (52) 62 LOAD_FAST (tuki6) 64 BINARY_FLOOR_DIVIDE 66 BINARY_ADD 68 STORE_FAST (zae3u) 16: 70 SETUP_LOOP (to 230) >> 72 LOAD_FAST (zae3u) 74 LOAD_CONST (0) 76 COMPARE_OP (>) 78 POP_JUMP_IF_FALSE (to 228) 17: 80 LOAD_FAST (zae3u) 82 LOAD_CONST (1) 84 INPLACE_SUBTRACT 86 STORE_FAST (zae3u) 18: 88 LOAD_FAST (xaeg4) 90 LOAD_DEREF (ik4so) 92 LOAD_FAST (oon0j) 94 BINARY_ADD 96 CALL_FUNCTION (1 positional argument) 98 STORE_DEREF (ik4so) 19: 100 LOAD_FAST (xaeg4) 102 LOAD_DEREF (ik4so) 104 LOAD_CONST (2) 106 BINARY_RSHIFT 108 CALL_FUNCTION (1 positional argument) 110 LOAD_CONST (3) 112 BINARY_AND 114 STORE_DEREF (eing8) 20: 116 LOAD_CONST (0) 118 STORE_DEREF (coh1p) 21: 120 SETUP_LOOP (to 184) >> 122 LOAD_DEREF (coh1p) 124 LOAD_FAST (tuki6) 126 LOAD_CONST (1) 128 BINARY_SUBTRACT 130 COMPARE_OP (<) 132 POP_JUMP_IF_FALSE (to 182) 22: 134 LOAD_FAST (fau0m) 136 LOAD_DEREF (coh1p) 138 LOAD_CONST (1) 140 BINARY_ADD 142 BINARY_SUBSCR 144 STORE_DEREF (aph7a) 23: 146 LOAD_FAST (xaeg4) 148 LOAD_FAST (fau0m) 150 LOAD_DEREF (coh1p) 152 BINARY_SUBSCR 154 LOAD_FAST (fie1z) 156 CALL_FUNCTION (0 positional arguments) 158 BINARY_ADD 160 CALL_FUNCTION (1 positional argument) 162 DUP_TOP 164 STORE_DEREF (di5ei) 166 LOAD_FAST (fau0m) 168 LOAD_DEREF (coh1p) 170 STORE_SUBSCR 24: 172 LOAD_DEREF (coh1p) 174 LOAD_CONST (1) 176 INPLACE_ADD 178 STORE_DEREF (coh1p) 180 JUMP_ABSOLUTE (to 122) >> 182 POP_BLOCK 25: >> 184 LOAD_FAST (fau0m) 186 LOAD_CONST (0) 188 BINARY_SUBSCR 190 STORE_DEREF (aph7a) 26: 192 LOAD_FAST (xaeg4) 194 LOAD_FAST (fau0m) 196 LOAD_FAST (tuki6) 198 LOAD_CONST (1) 200 BINARY_SUBTRACT 202 BINARY_SUBSCR 204 LOAD_FAST (fie1z) 206 CALL_FUNCTION (0 positional arguments) 208 BINARY_ADD 210 CALL_FUNCTION (1 positional argument) 212 DUP_TOP 214 STORE_DEREF (di5ei) 216 LOAD_FAST (fau0m) 218 LOAD_FAST (tuki6) 220 LOAD_CONST (1) 222 BINARY_SUBTRACT 224 STORE_SUBSCR 226 JUMP_ABSOLUTE (to 72) >> 228 POP_BLOCK 28: >> 230 LOAD_CONST (None) 232 RETURN_VALUE # Method Name: fie1z # Filename: code-XXXXX.py # Argument count: 0 # Keyword-only arguments: 0 # Number of locals: 0 # Stack size: 5 # Flags: 0x00000013 (NESTED | NEWLOCALS | OPTIMIZED) # First Line: 5 # Constants: # 0: None # 1: 5 # 2: 2 # 3: 3 # 4: 4 # Free variables: # 0: aph7a # 1: coh1p # 2: di5ei # 3: eing8 # 4: ik4so # 5: ooch0 6: 0 LOAD_DEREF (di5ei) 2 LOAD_CONST (5) 4 BINARY_RSHIFT 6 LOAD_DEREF (aph7a) 8 LOAD_CONST (2) 10 BINARY_LSHIFT 12 BINARY_XOR 14 LOAD_DEREF (aph7a) 16 LOAD_CONST (3) 18 BINARY_RSHIFT 20 LOAD_DEREF (di5ei) 22 LOAD_CONST (4) 24 BINARY_LSHIFT 26 BINARY_XOR 28 BINARY_ADD 30 LOAD_DEREF (ik4so) 32 LOAD_DEREF (aph7a) 34 BINARY_XOR 36 LOAD_DEREF (ooch0) 38 LOAD_DEREF (coh1p) 40 LOAD_CONST (3) 42 BINARY_AND 44 LOAD_DEREF (eing8) 46 BINARY_XOR 48 BINARY_SUBSCR 50 LOAD_DEREF (di5ei) 52 BINARY_XOR 54 BINARY_ADD 56 BINARY_XOR 58 RETURN_VALUE # Method Name: xaeg4 # Filename: code-XXXXX.py # Argument count: 1 # Keyword-only arguments: 0 # Number of locals: 1 # Stack size: 2 # Flags: 0x00000053 (NOFREE | NESTED | NEWLOCALS | OPTIMIZED) # First Line: 8 # Constants: # 0: None # 1: 4294967295 # Varnames: # vaeh7 # Positional arguments: # vaeh7 9: 0 LOAD_FAST (vaeh7) 2 LOAD_CONST (4294967295) 4 BINARY_AND 6 RETURN_VALUE
Дизассемблер — это конечно хорошо, но ведь прогресс на них не остановился, и с декомпилятором наперевес восстановим практически идентичный натуральному исходный код, который читать значительно легче:
Проанализировав код, выясним следующее:Декомпилированный код# Python bytecode 3.7.0 (3394) # Embedded file name: code-XXXXX.py # Size of source mod 2**32: 1357 bytes def wies3(fau0m, tuki6, ooch0): def fie1z(): return (di5ei >> 5 ^ aph7a << 2) + (aph7a >> 3 ^ di5ei << 4) ^ (ik4so ^ aph7a) + (ooch0[(coh1p & 3 ^ eing8)] ^ di5ei) def xaeg4(vaeh7): return vaeh7 & 0xFFFFFFFF aph7a = fau0m[0] ik4so = 0 oon0j = 562984899 di5ei = fau0m[(tuki6 - 1)] zae3u = 6 + 52 // tuki6 while zae3u > 0: zae3u -= 1 ik4so = xaeg4(ik4so + oon0j) eing8 = xaeg4(ik4so >> 2) & 3 coh1p = 0 while coh1p < tuki6 - 1: aph7a = fau0m[(coh1p + 1)] di5ei = fau0m[coh1p] = xaeg4(fau0m[coh1p] + fie1z()) coh1p += 1 aph7a = fau0m[0] di5ei = fau0m[tuki6 - 1] = xaeg4(fau0m[(tuki6 - 1)] + fie1z()) roh3s = [0, 0, 0, 0] assert roh3s[3] & 0x0FFFFFFF != 0 ieng8 = [0, 0, 0, 0] assert ieng8[3] & 0x0FFFFFFF != 0 kiiv4 = [0, 0, 0, 0, 0] if not (kiiv4[0] != 0 and kiiv4[1] != 0 and kiiv4[2] != 0 and kiiv4[3] != 0 and kiiv4[4] != 0): raise AssertionError op7bi = [2033349222, 859399546] wies3(op7bi, len(op7bi), roh3s) wies3(op7bi, len(op7bi), ieng8) assert op7bi == [1914726229, 545537777] wies3(kiiv4, len(kiiv4), roh3s) wies3(kiiv4, len(kiiv4), ieng8) assert kiiv4 == [4259271294, 3762695033, 2530072744, 1774340374, 314947544] print('Ciphertext = ', kiiv4) print('Plaintext = ?')
- Функция wies3 по-видимому реализует некое шифрование, и её аргументы — открытый текст, его длина и ключ. Такой вывод можно сделать, динамически проанализировав её, да и строки «Ciphertext»/«Plaintext» рядом с выводом одного из её аргументов в конце программы намекают на это;
- Assert-ы намекают на задуманные значения или диапазоны значений, затёртых из кода данных;
- У нас есть два неизменных ключа, они задаются переменными roh3s и ieng8, и применяются они последовательно, т.е. шифрование выполняется два раза: сначала на ключе roh3s, а затем — на ieng8. Заданные их значения и assert-ы намекают на формат затёртых из кода ключей: 4 32-битных слова, первые 3 из которых нулевые, а в последнем слове ненулевыми являются последние 28 бит;
- Также у нас есть два шифротекста, заданных assert-ами в переменных op7bi и kiiv4, и для первого из них есть и открытый текст, заданный в изначальном значении op7bi;
- Требуется найти открытый текст для шифротекста из kiiv4.
Функция шифрования невелика, и можно обратить её вручную, однако если проанализировать её далее или воспользоваться данной в чате подсказкой «если совсем запутались и устали — может заварите чаю?» — то можно выяснить, что в соответствии с заветами Брюса Шнайера в форме «don’t roll your own crypto« функция шифрования реализует вполне существующий алгоритм XXTEA, потомок изначального шифра TEA, применённый когда-то компанией Microsoft в своем Xbox (интересно, что в этом случае он был применён неудачно в качестве хеш-функции, что привело к взлому игровой консоли, но это совсем другая история).
Алгоритм достаточно компактен, не имеет публично известных уязвимостей, каким-либо образом способствующих его взлому (т.е. достаточно надёжен), и сравнительно быстр; однако подбирать 28×2 = 56 бит ключей занятие всё равно мягко говоря небыстрое (на Core i5 это бы заняло около 548 лет). Учитывая метод шифрования, а именно двойное шифрование на различных ключах — можно вспомнить про замечательный метод «встреча посередине», или «meet in the middle», который позволит нам значительно сократить вычислительную сложность перебора с 228×228 до 228+228, но конечно не бесплатно, а за счет памяти. В памяти мы будем сохранять результаты шифрования на первом ключе, и пробуя расшифровать на втором ключе будем искать в памяти совпадающий шифротекст, вот так:
Для ускорения можно взять готовую библиотеку, реализующую шифр XXTEA в качестве модуля Python, который написан на C, не забыв только пересобрать её, заменив стандартную константу delta равную 0x9E3779B9 на заданную в коде программы 0x218E77C3. Примерная реализация будет такой:
import xxtea
for firstKeyPart in range(0, 2**28):
fullKey = (b'\x00' * 12) + firstKeyPart.to_bytes(4, byteorder='little')
cipherText = xxtea.encrypt(givenPlainText, fullKey, padding=False)
encryptionTable[cipherText] = firstKeyPart
for secondKeyPart in range(0, 2**28):
fullKey = (b'\x00' * 12) + secondKeyPart.to_bytes(4, byteorder='little')
cipherText = xxtea.decrypt(givenCipherText, fullKey, padding=False)
if cipherText in encryptionTable:
print("Key 1: ", (b'\x00' * 12) + encryptionTable[cipherText])
print("Key 2: ", fullKey)
break
Реализация подобной хеш-таблицы в Python потребляет около 28 ГБ ОЗУ, чего не каждый себе может позволить. Поэтому для сокращения её потребления можно пойти на хитрость — разделить первый цикл (где формируется таблица шифротекстов и идёт подбор первого ключа) на несколько частей (2, 4, 8, 16 — сколько потребуется), создавая как бы «окно», содержащее лишь часть таблицы.
Второй же цикл (для второго ключа) в таком случае следует оставить как есть, целиком, поскольку благодаря равновероятному, криптографически-»хорошему» распределению полученных промежуточных шифротекстов по битовому пространству совершенно необязательно что в ином случае «окна» бы сошлись. Так, например, если разделить на 4 части — потребуется только около 7.5 ГБ ОЗУ, что уже гораздо реалистичнее (в аргументах программы как раз можно увидеть начальное и конечное значение текущего «окна» первого ключа):
Если и это непозволительно большой объём — можно разделить не на 4, а на 8 частей, и так далее уменьшая количество требуемой оперативной памяти, конечно ценой более долгого подбора. Компромисс времени выполнения и памяти в действии! При разделении на 4 части каждая часть на 1 ядре Core i5 выполнилась за 18 минут, и таким образом полный подбор занял бы 72 минуты (все ещё значительно лучше чем 548 лет), а если реализовать и распределение по ядрам — то конечно и ещё быстрее.
В результате для приведённого примера найдутся ключи 0x0000000000000000000000007257BEB и 0x0000000000000000000000002E3E626, а следом за ними и открытый текст 616E7377 65723A6B 39423132 3851746C 46566944 (держим в уме, что XXTEA здесь оперирует 32-битными словами), или «answer:k9B128QtlFViD». Если отправить полученный ответ John Roe в matrix, то можно получить следующее задание.
▍ Задание 3.2
В качестве следующего задания получаем файлы text-XXXXX.txt и соответствующая ему подпись. Внутри файла увидим что-то подобное:
Намётанный глаз безошибочно определит характерные «ТекстbD+7BojXe2BbTH8Q0h+Ni3e9JKGXZcHcgDdIydgwfsRW+IiUWMlvubnJKVS/H4wc
1D6fLsYt9dOVyTkwpTVTtj3n9tEj0QaAzQOgqfXReNVWl7w0nt8qitlk68uLY3xC
rySFDhJoPxA0jmKEaPW4G+l5Ri6es4kA23XKtbf8EqOvAX3Tafy0AT3v5MNyBVDJ
cdpl1e+08ETYPLVLymt5pv/UReGSIlEuZ/aiOrikrWjMJCMiXfzjxT6Yi/wW+dOD
9BgJc/OsEAGbrvBZ3LYhJZ+QOpUDPy0IFh4u8A24NEJx+hA0V/PDOxYcNQ3ePvtf
IJOMHdcGLh8c6/tM9u21JBLdOdmwm+ZUFbYTPr9nT0Brwtqj8Jqplkf++i/6gIT6
Z6mcNftenDCuRgTkGJCypmsKlVzH/TESjrZGPQSO1/clsylGRhDogVq3BoddGXsP
+vTzfhm48AdXETY3psD+LB9+QQgo1D5b8pRamKUD8ekid74eitKKt8dHGVNeV1JG
MIIG4wIBAAKCAYEArMqFwTxD2SUd/zMlIp9LDX1/pRFQ/WU9reebFam0jdLwMv7Q
Q5bNIGS1cDbVzUCcpEGp5TlOiTijJTCzcv5AGHq0Fniii/HMSQVTLsPTzYabN2I4
4EXs9dxZHyncnOqwN66JYeOk5IAT8hlcQDydyviov0oBVaB6JvJ9tCGkOKmfohlZ
T4oWULLnBzX+1Q65HBPG5emxIXFLFRInqr3pFmqCni8HTa2v67Hx7r+vtabQZjfl
IMVyCO+pfxL9LukqQHoGSRxYLrhg6h/WYvrf4LGTOxWVIiLUys4+LdVgN+ONDA6a
fzoMuEN04fiF9Pz7wc4PNXMN1DfWbnGxry38DYLeTZWHE/7TpP5YXS7g9I9dchEr
jMBQUo29qYwqu0nsOGLPY3D0gck7HdwgrNPIMTKEISOif5FB16FV9cAKxwgkx3UP
48xd7cpG/L9xbPsx6aGXuEfnn++XzUsw8YOdRDz+cmLgLoH6J56KnGSRIdbeC4b/
kY6LYK/1nGgRWlk/AgMBAAECggGAZfMocBcqwRhRVp3Kr17lXZRKmA5bhucROWaJ
7oIu8e8fojcOkpKLfS1ukEMKawxQX+oOYB0r5XLxb6QIfTTehJMBZrDO11tXeU4X
AmSwt3dQZaEihdE8OuREAUsly7/9MR1eGc/DHr8jBZlJAO3C/Fsy1YrItsj0yb4R
xRKEXppWgcILHA8Rk5O7FFobfYIuXg6dMFJuHJlH/6qylN9wg7VcVBDTclWkkqBv
arrW5YsDMwyPuIJHAlbF3yBJGkCfoEK/QlvmKRvjabGIu43w2g6lp3ZVYZtUZQgy
YG5hsyylONnukEf/FbBi21OgDWfXey5FPQ97KHLZJrxrjkna6rhwzFiCJsQgutbc
XahjElJY/hn/9JP5co9FgGlk+aZ/bofJLQ5urMSFMm7NgCD7aWRQx6Zkcow899Gg
KBFgNZdVWdj3lkAELO6NZSSpRDNxiaFb59aplIOj6bq3QwUuHSWtpO3gCuvn6EZU
ohDyvUDa6fbtX/hHx2MGbofxb
MIIG» в середине текста, которые декодируются из Base64 как 0x30 0x82 0x06. В нотации ASN.1 0x30 знаменует начало последовательности (sequence) данных, 0x82 (0x82-0x80 = 2) говорит о том, что длина поля длины этих данных – 2 байта, и старший байт длины равен 0x06. Декодируем полученные байты специализированным декодером dumpasn1 (или воспользуемся онлайн-инструментом) и разберём их полностью:
Картинка кликабельна
Помечено:В копируемом виде<30 82 06 E3> 0 1763: SEQUENCE { <02 01> 4 1: INTEGER 0 (0x00) <02 82 01 81> 7 385: INTEGER 00 AC CA 85 C1 3C 43 D9 25 1D FF 33 25 22 9F 4B 0D 7D 7F A5 11 50 FD 65 3D AD E7 9B 15 A9 B4 8D D2 F0 32 FE D0 43 96 CD 20 64 B5 70 36 D5 CD 40 9C A4 41 A9 E5 39 4E 89 38 A3 25 30 B3 72 FE 40 18 7A B4 16 78 A2 8B F1 CC 49 05 53 2E C3 D3 CD 86 9B 37 62 38 E0 45 EC F5 DC 59 1F 29 DC 9C EA B0 37 AE 89 61 E3 A4 E4 80 13 F2 19 5C 40 3C 9D CA F8 A8 BF 4A 01 55 A0 7A 26 F2 7D B4 21 A4 38 A9 9F A2 19 59 4F 8A 16 50 B2 E7 07 35 FE D5 0E B9 1C 13 C6 E5 E9 B1 21 71 4B 15 12 27 AA BD E9 16 6A 82 9E 2F 07 4D AD AF EB B1 F1 EE BF AF B5 A6 D0 66 37 E5 20 C5 72 08 EF A9 7F 12 FD 2E E9 2A 40 7A 06 49 1C 58 2E B8 60 EA 1F D6 62 FA DF E0 B1 93 3B 15 95 22 22 D4 CA CE 3E 2D D5 60 37 E3 8D 0C 0E 9A 7F 3A 0C B8 43 74 E1 F8 85 F4 FC FB C1 CE 0F 35 73 0D D4 37 D6 6E 71 B1 AF 2D FC 0D 82 DE 4D 95 87 13 FE D3 A4 FE 58 5D 2E E0 F4 8F 5D 72 11 2B 8C C0 50 52 8D BD A9 8C 2A BB 49 EC 38 62 CF 63 70 F4 81 C9 3B 1D DC 20 AC D3 C8 31 32 84 21 23 A2 7F 91 41 D7 A1 55 F5 C0 0A C7 08 24 C7 75 0F E3 CC 5D ED CA 46 FC BF 71 6C FB 31 E9 A1 97 B8 47 E7 9F EF 97 CD 4B 30 F1 83 9D 44 3C FE 72 62 E0 2E 81 FA 27 9E 8A 9C 64 91 21 D6 DE 0B 86 FF 91 8E 8B 60 AF F5 9C 68 11 5A 59 3F <02 03> 396 3: INTEGER 65537 (0x10001) <02 82 01 80> 401 384: INTEGER 65 F3 28 70 17 2A C1 18 51 56 9D CA AF 5E E5 5D 94 4A 98 0E 5B 86 E7 11 39 66 89 EE 82 2E F1 EF 1F A2 37 0E 92 92 8B 7D 2D 6E 90 43 0A 6B 0C 50 5F EA 0E 60 1D 2B E5 72 F1 6F A4 08 7D 34 DE 84 93 01 66 B0 CE D7 5B 57 79 4E 17 02 64 B0 B7 77 50 65 A1 22 85 D1 3C 3A E4 44 01 4B 25 CB BF FD 31 1D 5E 19 CF C3 1E BF 23 05 99 49 00 ED C2 FC 5B 32 D5 8A C8 B6 C8 F4 C9 BE 11 C5 12 84 5E 9A 56 81 C2 0B 1C 0F 11 93 93 BB 14 5A 1B 7D 82 2E 5E 0E 9D 30 52 6E 1C 99 47 FF AA B2 94 DF 70 83 B5 5C 54 10 D3 72 55 A4 92 A0 6F 6A BA D6 E5 8B 03 33 0C 8F B8 82 47 02 56 C5 DF 20 49 1A 40 9F A0 42 BF 42 5B E6 29 1B E3 69 B1 88 BB 8D F0 DA 0E A5 A7 76 55 61 9B 54 65 08 32 60 6E 61 B3 2C A5 38 D9 EE 90 47 FF 15 B0 62 DB 53 A0 0D 67 D7 7B 2E 45 3D 0F 7B 28 72 D9 26 BC 6B 8E 49 DA EA B8 70 CC 58 82 26 C4 20 BA D6 DC 5D A8 63 12 52 58 FE 19 FF F4 93 F9 72 8F 45 80 69 64 F9 A6 7F 6E 87 C9 2D 0E 6E AC C4 85 32 6E CD 80 20 FB 69 64 50 C7 A6 64 72 8C 3C F7 D1 A0 28 11 60 35 97 55 59 D8 F7 96 40 04 2C EE 8D 65 24 A9 44 33 71 89 A1 5B E7 D6 A9 94 83 A3 E9 BA B7 43 05 2E 1D 25 AD A4 ED E0 0A EB E7 E8 46 54 A2 10 F2 BD 40 DA E9 F6 ED 5F F8 47 C7 63 06 6E 87 F1 Error: Unexpected EOF, 3 bytes missing. Error: Inconsistent object length, 981 bytes difference. } Error: Inconsistent object length, 980 bytes difference.
- зелёным – тип записи; 30 – последовательность (sequence), 02 – целое число (integer);
- голубым – длина длины значения записи, указывается как «количество байт + 0x80»;
- синим – значение длины записи;
- полужирным чёрным – само значение.
С учётом этого мы видим последовательность из 4х целых чисел: нуля, длинного значения, значения 65535 и частичного длинного значения, которому не хватает 3х байт. Также по заголовку последовательности видим, что вся последовательность должна быть длиной 1763 байта, а у нас только 786 байт. Самые внимательные уже могли заметить, что вообще-то у нас есть ещё 6 бит от символа «b» в исходном base64, и вот они: 0b011011. Они ещё сослужат нам свою службу позже.
Те из нас, кто когда-нибудь пробовал посмотреть, что же скрывается в «белиберде» между «-----BEGIN RSA PRIVATE KEY-----» и соответствующей закрывающей последовательности конечно уже поняли, к чему всё идёт. Да, всё верно, вся структура до боли напоминает приватный ключ алгоритма RSA, а точнее – RSA-3072 (обратим внимание на длину модуля n в 3072 бита).
Если мы сгенерируем ключ такой же длины командой
openssl genrsa -out private_key.pem 3072, то получим пример для сравнения. В нём мы увидим и все недостающие нам числа, они записываются в последовательности в таком порядке:- версия (обычно задаётся как 0);
- модуль (n);
- открытая экспонента (e);
- секретная экспонента (d);
- простое число (p);
- простое число (q);
- параметр для ускорения вычислений (dp);
- параметр для ускорения вычислений (dq);
- параметр для ускорения вычислений (qInv).
В нашем частичном ключе есть версия (задана как 0), модуль (n, полностью), открытая экспонента (e, полностью, равна 65535), и частичная секретная экспонента (d, не хватает 3×8-6 = 18 бит из 3072 бит, указанных в заголовке этого целого числа). Вспомним, как вообще выполняется шифрование и расшифровка в RSA, и какие параметры нам действительно необходимы.
Шифрование:
Расшифровка:
Для шифрования нужны e и n, и они у нас есть в полном виде. А вот для расшифровки кроме n нужна ещё секретная экспонента d, которая у нас есть лишь частично. Благо, что 218 – всего лишь 262144 комбинации, и поэтому мы можем достаточно быстро подобрать нехватающие биты d, в качестве критерия правильности используя процедуру расшифровки, зашифровав любое понравившееся число (например 863) и пытаясь расшифровать его с очередным d, в случае совпадения исходного открытого текста и расшифрованного текста – нехватающие биты d успешно подобраны. Так, например, если мы будем использовать первую же попавшуюся реализацию RSA на Python, то код может выглядеть как-то так:
Для приведённого примера код найдёт нехватающие биты, а именно в виде тех самых трёх нехватающих байтов их можно записать как 0x6D 0xBD 0x61. Далее при желании можно восстановить и p и q, а из них – и полный исходный ключ со всеми параметрами:Кодdef rsa_encrypt(pk, plaintext): key, n = pk cipher = pow(plaintext, key, n) return cipher def rsa_decrypt(pk, ciphertext): key, n = pk plain = pow(ciphertext, key, n) return plain e = 65537 n = 0x00ACCA85C13C43D9251DFF3325229F4B0D7D7FA51150FD653DADE79B15A9B48DD2F032FED04396CD2064B57036D5CD409CA441A9E5394E8938A32530B372FE40187AB41678A28BF1CC4905532EC3D3CD869B376238E045ECF5DC591F29DC9CEAB037AE8961E3A4E48013F2195C403C9DCAF8A8BF4A0155A07A26F27DB421A438A99FA219594F8A1650B2E70735FED50EB91C13C6E5E9B121714B151227AABDE9166A829E2F074DADAFEBB1F1EEBFAFB5A6D06637E520C57208EFA97F12FD2EE92A407A06491C582EB860EA1FD662FADFE0B1933B15952222D4CACE3E2DD56037E38D0C0E9A7F3A0CB84374E1F885F4FCFBC1CE0F35730DD437D66E71B1AF2DFC0D82DE4D958713FED3A4FE585D2EE0F48F5D72112B8CC050528DBDA98C2ABB49EC3862CF6370F481C93B1DDC20ACD3C83132842123A27F9141D7A155F5C00AC70824C7750FE3CC5DEDCA46FCBF716CFB31E9A197B847E79FEF97CD4B30F1839D443CFE7262E02E81FA279E8A9C649121D6DE0B86FF918E8B60AFF59C68115A593F dPart = (0x65F32870172AC11851569DCAAF5EE55D944A980E5B86E711396689EE822EF1EF1FA2370E92928B7D2D6E90430A6B0C505FEA0E601D2BE572F16FA4087D34DE84930166B0CED75B57794E170264B0B7775065A12285D13C3AE444014B25CBBFFD311D5E19CFC31EBF2305994900EDC2FC5B32D58AC8B6C8F4C9BE11C512845E9A5681C20B1C0F119393BB145A1B7D822E5E0E9D30526E1C9947FFAAB294DF7083B55C5410D37255A492A06F6ABAD6E58B03330C8FB882470256C5DF20491A409FA042BF425BE6291BE369B188BB8DF0DA0EA5A77655619B54650832606E61B32CA538D9EE9047FF15B062DB53A00D67D77B2E453D0F7B2872D926BC6B8E49DAEAB870CC588226C420BAD6DC5DA863125258FE19FFF493F9728F45806964F9A67F6E87C92D0E6EACC485326ECD8020FB696450C7A664728C3CF7D1A028116035975559D8F79640042CEE8D6524A944337189A15BE7D6A99483A3E9BAB743052E1D25ADA4EDE00AEBE7E84654A210F2BD40DAE9F6ED5FF847C763066E87F1 << 6) | 0b011011 publicKey = (e, n) encryptedPlain = rsa_encrypt(publicKey, 863) for keyPart in range(0, 2**18): dFull = (dPart << 18) | keyPart privateKey = (dFull, n) decryptedPlain = rsa_decrypt(privateKey, encryptedPlain) if decryptedPlain == 863: print hex(dFull) break
А затем и расшифровать первую часть полученного текстового документа (не забыв раскодировать её) командойВосстановленный ключ-----BEGIN RSA PRIVATE KEY----- MIIG4wIBAAKCAYEArMqFwTxD2SUd/zMlIp9LDX1/pRFQ/WU9reebFam0jdLwMv7Q Q5bNIGS1cDbVzUCcpEGp5TlOiTijJTCzcv5AGHq0Fniii/HMSQVTLsPTzYabN2I4 4EXs9dxZHyncnOqwN66JYeOk5IAT8hlcQDydyviov0oBVaB6JvJ9tCGkOKmfohlZ T4oWULLnBzX+1Q65HBPG5emxIXFLFRInqr3pFmqCni8HTa2v67Hx7r+vtabQZjfl IMVyCO+pfxL9LukqQHoGSRxYLrhg6h/WYvrf4LGTOxWVIiLUys4+LdVgN+ONDA6a fzoMuEN04fiF9Pz7wc4PNXMN1DfWbnGxry38DYLeTZWHE/7TpP5YXS7g9I9dchEr jMBQUo29qYwqu0nsOGLPY3D0gck7HdwgrNPIMTKEISOif5FB16FV9cAKxwgkx3UP 48xd7cpG/L9xbPsx6aGXuEfnn++XzUsw8YOdRDz+cmLgLoH6J56KnGSRIdbeC4b/ kY6LYK/1nGgRWlk/AgMBAAECggGAZfMocBcqwRhRVp3Kr17lXZRKmA5bhucROWaJ 7oIu8e8fojcOkpKLfS1ukEMKawxQX+oOYB0r5XLxb6QIfTTehJMBZrDO11tXeU4X AmSwt3dQZaEihdE8OuREAUsly7/9MR1eGc/DHr8jBZlJAO3C/Fsy1YrItsj0yb4R xRKEXppWgcILHA8Rk5O7FFobfYIuXg6dMFJuHJlH/6qylN9wg7VcVBDTclWkkqBv arrW5YsDMwyPuIJHAlbF3yBJGkCfoEK/QlvmKRvjabGIu43w2g6lp3ZVYZtUZQgy YG5hsyylONnukEf/FbBi21OgDWfXey5FPQ97KHLZJrxrjkna6rhwzFiCJsQgutbc XahjElJY/hn/9JP5co9FgGlk+aZ/bofJLQ5urMSFMm7NgCD7aWRQx6Zkcow899Gg KBFgNZdVWdj3lkAELO6NZSSpRDNxiaFb59aplIOj6bq3QwUuHSWtpO3gCuvn6EZU ohDyvUDa6fbtX/hHx2MGbofxbb1hAoHBAOVsPoFwTJk3Qdlekkdb8Z4v8CKZXdDs jLKOvGunmjrxSptb0s/zrAZYtjL4/lvuS9xzDX6DdGxPlISta6sBnu6LDoD0hrnH BBG+qn6rOvFqgKGcz5HpcQcWOyk39n/RMFvVRuCJ+Hh0GQyyAAzHwRXfabmODlyC /tLBSKg+N72V7GdWLPecFuPmrt6YF3u3WPUq8RTeFKxJc8yq1uoQtCO2ADDoTR3T jCC1wHJM9B+2QweuAGBmqgv7pYt8e3T/cwKBwQDAzs9LIi1lB28Of2qGncNHnubE 72FKlj0TbKmOezEz6DhkyYFcV+Lr6mxoCXAgzdPCQWVexepVujiv3fIamBV72Bbz aonFgeJHONoktm+S++ZRexJy/OnKky7SHLcjbfmcQpdxB5Xf8l6IM1EsaSreNNHs jhwxxmt02YmfslZXOfQLY88lVsrirYeEBAj7UsxXq/mmp1T7qjdMc/YnkYQi6Xy3 PytUm45VacbaACvqj6tV7d5w91Bspt/aKqOaNAUCgcAgjXpU/W0w9EE4qY2R6H7h FiY5ko9YPKg+Ebi0gcSFhoUyhBXmgcmv4NiBZQkaXDaRYhXRFK/pSmVlagHz8rft WvfE3m1bYNy389jXPk6PwK/dvpVJO9lYyxO75n/oZPM6pIl5BLqnxLllLsCJD7La +qdSt9Bb2g50Mw6vKJzaHrK7euPIgnJRBgNb/DKg0EQkDWLFtjkytP1kVf1GmvYk dweR6PRAPisM3R0gWsDs2vyp00ukYgzQxHUZ1KDj2fcCgcB2LEuRWVlJWs0Orbm0 2G0gMJxwh+ext3OnvCoQUiFOFz65R2gqGRPUVNIs0dwPvxfTMBHZjKSb9o9X+0iw VBaW2VL3zoyyqXDvBkFtzwODqzD3L9+W6rzAlIVV8pOs+3LJ+2amuGd74yldgVZ3 Sd4kY2tm+ZL+Twb9j3dykfOpcrPJZ1tHH3MqjAFLQM3gfFcSRS22n0jPFvzdtxVg GyhJ3aG7DtSX/t+2Kibe5swD8BqriCeWRX7dmUoKhafQk6ECgcEAibMBzXrXa/rx SK4EogYqXqnBfxLFrun/E2xBCSOSkb37nEvlaavunDUuFvLey5+xYxCUENSQ2WRZ AJR+oDVRuktW95YvJC2x5XaxuWreMejbXIwhEGkCjXjWZzvl7VeL3IlUNeAuUp+1 8vwtcaX3pqUWEpjV9b51lPRFjX8hBPsRpa2wHo5+gyrfRMZ3OtRsrduc963zlQN7 jlc5RnMsUd1mAECUhhWU2f4n2d9Xzot/QoAuGoa4mnzTVReuaBcy -----END RSA PRIVATE KEY-----
openssl rsautl -decrypt -in encrypted.txt -inkey priv.pem, и снова получить ответ answer:WBfilGenxrLUdZ67qwYj. Отправляем полученную инфу Johnу и дальше… ждём :)
Подсказкой к следующему заданию была онлайн-игра, основанная на известной игре сокобан – чтобы попасть в неё, ожидаемо надо было пройти предыдущие задания и прислать правильные ответы Джону.
Кому пельменей?
Всем настолько запала в душу идея с «пельменями от рувдс», что мы даже задумались – быть может стоит расширить свою линейку мерча :)
В итоговом посте мы обязательно разберём все самые безумные идеи от квестующихся (как они себя окрестили) и сам механизм квеста.
Впереди участников ждет самая активная фаза заданий, приключения и мега движ. Игрокам предстоит объединиться, ведь выигрыш — 142 857 рублей заберёт команда лучших.
Тем, кто всё ещё наблюдает за происходящим со стороны – не стоит затягивать своё вступление в игру – на этот раз времени мало…
Всего несколько дней… или часов?
Присоединиться к обсуждению решения насущных задач соревнования можно в нашем уютном телеграм чате, или же создать свой и обсуждать идеи там.
По традиции завершаем материал небольшой подборкой смешных скринов от участников, для которых пельмени и черепок Юрий стали культовыми мемами квеста:
Больше смешных скринов
