Ghost in the Shellcode CTF 2014 (pillowtalk)

Решения

http://broot.ca/gitsctf-pillowtalk-crypto-200 (Alex Weber)
https://systemoverlord.com/blog/2014/01/19/ghost-in-the-shellcode-2014-pillowtalk/ (System Overlord)
Назад к списку заданий

Задание (Crypto)

Question 5 - Pillowtalk
Points: 200
Find the key! File.

Подробное описание

Ниже представлен перевод решения от Alex Weber (мне понравился его рассказ, плюс я добавил некоторый код. Например, диссектор pillowtalk для Wireshark'а).

Кратко: повторное использование ключевой последовательности

Флаг: WhyDoFartsSmell?SoTheDeafCanEnjoyThemAlso.

Я редко (на крайняк) обращаюсь к дизассемблированию/отладке, но в этот раз я решил "была-не была" и задействовал IDA Pro больше, чем обычно. Да, местами я ошибался и неверно угадывал, но, в итоге узнал для себя кое-что новое и вообще прекрасно провел время, решая эту задачу.

Что мы имеем

Stripped (без отладочной информации) 64-битный Linux исполняемый фай и pcap-файл с перехваченным трафиком (чей-то подслушанный разговор, недаром задание называется "pillowtalk" - "беседа под одеялом").
Мы также знаем, что здесь используется некая криптография. На основании того, что задание из категории "crypto".

Я скачал архив TAR, открыл его, нашел в нем вышеупомянутый исполняемый файл и pcap-файл. Проверим бинарник командой file (переносы строк добавлены):

$ file ./pillowtalk-stripped
pillowtalk-stripped: ELF 64-bit LSB executable, x86-64, version 1 (SYSV),
dynamically linked (uses shared libs), for GNU/Linux 2.6.24,
BuildID[sha1]=0x660940b02c09984520b7cae79e4a3b5999452a58, stripped

Судя по имени, исполняемый файл лишен символьной информации, что явно затруднит его дизассемблирование.

Подсматривая за пакетами

Пока мои товарищи по команде занимались поиском читов в FPS/RPG игре, созданной организаторами соревнования, чтобы найти способ как можно быстрее отстрелять кабанов, я открыл pcap-файл в Wireshark и посмотрел, что у нас есть:

1.png

Я обрадовался, увидев OSPF-Lite , потому что раньше я сталкивался с OSPF на маршрутизаторах Cisco, и я уж подумал, может быть это проблема, связанная с алгоритмом Дейкстры или типа того. Само собой разумеется, задачка не имела ничего общего с OSPF , так что я зря надеялся.

Покопавшись, я выяснил, что Wireshark далее пакетов TCP/IP не мог ничего интерпретировать. Все, что я мог сказать - пакеты не имеют явной структуры. Я предположил, либо пакеты сжатые, либо зашифрованные, но не был уверен.

Чуть погодя, я заметил, что сообщениям предшествует четырехбайтное слово (порядок байт little-endian), поэтому получатель знает, сколько байт данных следует ожидать.

2.png

Изнутри

Перед погружением в дизассемблер, выясним, как работает программа, в общем, не углубляясь в детали. Такой шаг поможет нам быстрее разобраться в дизассемблированном коде. На мой взгляд, поиск уязвимости в коде программы, не ведая того, что делает сама программа, похожа на попытку менять масло в автомобиле, еще не зная, что такое автомобиль.

Запустив программу без аргументов, она сообщит нам, как с ней работать.

$ ./pillowtalk-stripped
pillowtalk-stripped: Usage: ./ pillowtalk-stripped [--connect host port] [--host port]

Как видим, программа может работать как в качестве клиента, так и сервера:

$ ./pillowtalk-stripped --host 5000
[+] Running in server mode.
        - Created socket
        - Socket bound to port 5000
        - Listening for connection

Запустив два экземпляра программы, один в качестве сервера, а другой как клиент, подключаемый к серверу, заметим, что программы начинают поочередно отсылать и получать ввод с клавиатуры, раз и навсегда установленным порядком. Иначе говоря:

  • Сервер ждет ввода с клавиатуры
  • Сервер посылает данные клиенту
  • Клиент получает данные и отображает их
  • Клиент ждет ввода с клавиатуры
  • Клиент посылает данные серверу
  • Сервер получает данные и отображает их
  • Повторить!

Теперь, когда мы знаем, как работает программа в общих деталях, приступим к изучению её протокола. Если мы возьмем netcat, то мы сможем имитировать клиентское подключение и увидеть, что делает сервер:

$ netcat 127.0.0.1 5000 | hexdump -C
00000000  78 8d 18 64 30 7c b7 c3 9b 8c 6a e9 ca bc 1c 76
00000010  37 5a 93 9c 70 f9 2a e2 97 61 a0 54 60 3b 39 2b

Мы видим, что по TCP-соединению сервер тут же отправляет нам 32 (видимо, случайных) байта.
Программа-сервер не принимает второе соединение, поэтому мы останавливаем и перезапускаем его. При следующем подключении клиента, полученные данные отличаются:

$ netcat 127.0.0.1 5000 | hexdump -C
00000000  be 7d 06 8d 53 f6 49 9e 05 fb b0 46 e3 0a e3 75
00000010  3f 10 6d 5b 6d 99 ef 6d a1 6e 35 0e 38 e0 9a 23

Возникает вопрос: откуда берутся случайные данные? Для ответа мы запустим наш сервер под наблюдением strace.

Погружаясь (We need to go deeper)

Утилита strace запускает программу как обычно, кроме того, она показывает все системные вызовы, выполняемые внутри исполняемого файла. strace - просто отличный способ быстро выяснить, насколько программа взаимодействует с внешним миром.

Мы запустим нашу программу в режиме сервера под strace (флаг "-х" дает команду выводить непечатаемые символы как hex-строки), а затем подключимся к ней (как клиент) с помощью netcat:

$ strace -x ./pillowtalk-stripped --host 5000
Создание сервера
…
write(1, "[+] Running in server mode.\n", 28[+] Running in server mode.) = 28
socket(PF_INET, SOCK_STREAM, IPPROTO_TCP) = 3
write(1, "\t- Created socket\n", 18    - Created socket)    = 18
setsockopt(3, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0
bind(3, {sa_family=AF_INET, sin_port=htons(5000), sin_addr=inet_addr("0.0.0.0")}, 16) = 0
write(1, "\t- Socket bound to port 5000\n", 29    - Socket bound to port 5000) = 29
listen(3, 20)                           = 0
write(1, "\t- Listening for connection\n", 28    - Listening for connection) = 28
accept(3, 0, NULL)                      = 4
write(1, "[+] Client connected\n", 21[+] Client connected)  = 21
…
Пришел запрос от клиента
open("/dev/urandom", O_RDONLY)          = 5
read(5, "\x0b\x5a\x18\x40\x6d\xd6\x47\x48\x6a\xf6\x0a\xfb\x5a\x8f\xec\xd1\x76\x7a\x2d\xfa\x8c\x1a\x6f\xa8\x3f\x27\x2d\xe3\x2f\x1b\xd9\x26"..., 4096) = 4096
close(5)                                = 0
sendto(4, "\x8c\xac\xe1\xb6\x38\x38\x8c\x83\x19\x13\x73\x88\x21\x27\x85\x6a\x8a\x81\xcc\x75\xa9\x45\x59\x8f\xca\x47\x81\x71\x7a\x43\xb5\x6d", 32, 0, NULL, 0) = 32
recvfrom(4,

Когда мы соединяемся с сервером через netcat, то видим, что сервер открывает "/dev/urandom" и читает 32 байта случайных данных, а затем отправляет 32 байта клиенту. Обратите внимание, 32 байта, отправляемых по сети, полностью отличаются от полученных случайных байт.

Очень любопытно!

Как всё происходит: программа в режиме сервера и клиента совершает одни и те же действия. Клиент устанавливает TCP-соединение, сервер считывает 32 байта случайных данных, "преобразует" их, и отправляет клиенту. Затем клиент делает то же самое, посылая свои "преобразованные" 32 байта на сервер.

Что случится, если мы удалим устройство "/dev/urandom" и заменим его ссылкой на "/dev/zero/" (т.е. программа всегда будет считывать 32 байта нулей)?

Оказывается, в этом случае данные, передаваемые по сети, будут всегда одинаковыми, независимо от режима, в котором находится программа (сервер или клиент). Кстати, данные не зависят и от других вещей таких, как UID и метка времени.

Учитывая, что pcap-файл содержит, казалось бы, случайные данные, я интуитивно догадался, что сервер и клиент выполнили процедуру "обмена ключами". Если бы слабость была в алгоритме обмена ключами, то мы могли бы взять две "половинки" из pcap-файла, чтобы получить общий ключ, и использовать его для расшифровки остальной части pcap-файла!

А теперь самое время перейти к IDA Pro.

Дизассемблируя

Запустив IDA Pro и, начиная с вызова функции accept ([+] Client connected), подтвердились мои наблюдения: клиент и сервер читают данные из /dev/urandom:

.text:0000000000400CF4 client_mode_requested:                  ; CODE XREF: sub_400BE0+A5j
.text:0000000000400CF4                                         ; sub_400BE0+F4j
.text:0000000000400CF4                 cmp     [rbp+server_mode], 0
.text:0000000000400CFB                 jz      server_mode_requested
.text:0000000000400D01                 movzx   edi, [rbp+port]
.text:0000000000400D05                 call    server_mode
.text:0000000000400D0A                 mov     [rbp+fd], eax
.text:0000000000400D0D                 jmp     read_devrandom
.text:0000000000400D12 ; ---------------------------------------------------------------------------
.text:0000000000400D12
.text:0000000000400D12 server_mode_requested:                  ; CODE XREF: sub_400BE0+11Bj
.text:0000000000400D12                 mov     rdi, [rbp+address]
.text:0000000000400D16                 movzx   esi, [rbp+port]
.text:0000000000400D1A                 call    client_mode
.text:0000000000400D1F                 mov     [rbp+fd], eax
.text:0000000000400D22
.text:0000000000400D22 read_devrandom:                         ; CODE XREF: sub_400BE0+12Dj
.text:0000000000400D22                 lea     rdi, filename   ; "/dev/urandom"
.text:0000000000400D2A                 lea     rsi, modes      ; "rb"

На самом деле, почти нет разницы между режимом сервера и клиента. По большей части выполняется общий кусок кода, что облегчает дальнейший анализ.

Далее, мы видим, что клиент и сервер вызывают одну и ту же функцию для "преобразования" своих случайных байт в данные для обмена. Непонятен один момент, в функцию передается еще один параметр – строка "\t" (всего лишь один символ табуляции).

.rodata:0000000000407640 tab             db 9,0

Учитывая, что это CTF задачка, у меня возникло ощущение, что этот параметр добавили для того, чтобы ввести нас в заблуждение. Поэтому я просто проигнорировал его.

.text:0000000000400D22 read_devrandom:                         ; CODE XREF: sub_400BE0+12D j
.text:0000000000400D22                 lea     rdi, filename   ; "/dev/urandom"
.text:0000000000400D2A                 lea     rsi, modes      ; "rb"
.text:0000000000400D32                 call    _fopen
.text:0000000000400D37                 mov     rsi, 20h        ; size
.text:0000000000400D41                 mov     rdx, 1          ; n
.text:0000000000400D4B                 lea     rdi, [rbp+random] ; ptr
.text:0000000000400D4F                 mov     [rbp+stream], rax
.text:0000000000400D53                 mov     rcx, [rbp+stream] ; stream
.text:0000000000400D57                 call    _fread
.text:0000000000400D5C                 mov     rdi, [rbp+stream] ; stream
.text:0000000000400D60                 mov     [rbp+unused], rax
.text:0000000000400D67                 call    _fclose
.text:0000000000400D6C                 lea     rdx, tab        ; "\t"
.text:0000000000400D74                 lea     rsi, [rbp+random]
.text:0000000000400D78                 lea     rdi, [rbp+buf]
.text:0000000000400D7C                 mov     [rbp+var_9D4], eax  ; Почему tab?
.text:0000000000400D82                 call    key_deriv

key_deriv вызывается дважды:

  • "Преобразовать" 32 байта случайных данных перед отправкой в сеть
  • Объединить исходные 32 байта и полученные 32 байта в ключ зашифрования-расшифрования

Функция key_deriv была эпической - я действительно не знал, как к ней подступиться. Она использовала чуть более 2 килобайт переменных на стеке, и довольно большие куски кода, которые, казалось, повторялись сотни раз, используя каждый раз различные переменные.

NB: Оглядываясь назад, я понимаю, что выбранное имя key_deriv было весьма неудачным для этой функции. Тем не менее, именно так я назвал ее при решении CTF, и я хочу рассказать историю так, как всё было, со всеми неловкостями и деталями!

Посмотрите на рисунок. Начиная с желтой стрелки и до конца синего прямоугольника (для тех, кто не сталкивался с IDA, синий цвет означает исполняемый код в программе). Всё правильно: всего лишь одна функция занимает около 80% исполняемого кода.

3.png

Исполняемый код размером в 36Kб. Конечно, не такой огромный, но для консольной программы Linux весьма много, чтобы разреверсить его!

Глядя на используемые инструкции, у меня было предчувствие, что этот обмен ключами основан на симметричной криптографии - то есть, применялась навороченная, сложная хэш-функция или блочный шифр для скрытия связи между передаваемыми данными и согласованным ключом вместо того, чтобы использовать, например, признанный алгоритм с открытым ключом RSA, или протокол Диффи-Хеллмана. Учитывая не безопасный (насколько я знаю) способ обмена симметричным ключом без высшей математики (используемой двумя вышеупомянутыми методами), отнюдь не так просто решить вопрос с расшифровкой с помощью вставок LD_PRELOAD. LD_PRELOAD - переменная окружения, с помощью которой вы можете указать системному компоновщику времени выполнения(ld.so), что он должен загрузить указанные библиотеки раньше других. В результате можно перехватывать какие-либо функции, и заменять их собственной реализацией.

Я решил, что, если я прав, и уязвимость находится в этой функции, то я должен вернуться к ней позже. А пока я еще не был готов спускаться в эту кроличью нору.

Переступив через кроличью нору

Далее по коду, я увидел, что 32 байта, возвращаемые key_deriv "расширяются" в 1024 байта последующими двумя функциями (sub_401290 и sub_4013B0). Затем эти 1024 байта ("ключевой поток" / "гамма" / keystream) объединялись (с помощью операции XOR) со строкой, введенной с клавиатуры, перед отправкой в сеть. Тем самым я получил сразу несколько ответов:

  • Псевдослучайные данные из pcap-файла являются шифрованными, а не сжатыми данными
  • Передача программами между собой 32-х байт, на самом деле, была процедурой обмена ключами
  • Шифрование – некий вид поточного шифра

Хотя размер функции генерации ключевого потока значительно меньше, чем функции key_deriv, я не тратил время, пытаясь понять её. Однако одна вещь заставила меня буквально подскочить:

sub_4013B0
…
.text:000000000040141B                 sar     eax, 1Fh
.text:000000000040141E                 shr     eax, 18h
.text:0000000000401421                 add     eax, ecx
.text:0000000000401423                 and     eax, 0FFFFFF00h

And (по адресу 401423) в сочетании со сдвигом shr (по адресу 40141E) приводил к потере одного байта информации в каждой итерации цикла. Я, было, решил, что это еще одна кроличья нора с некой хардкор-математикой, поэтому я не стал копать глубже.

Нечего и говорить, что это было абсолютной ошибкой, и я чувствую себя глупо при мысли о том, почему я пришел к такому выводу. Подробнее об этом позже.

Я снова решил пересмотреть часть кода, где ключевой поток объединялся с открытым текстом. В этот раз, я заметил слабость в алгоритме:

.text:0000000000401004                 mov     [rbp+count], 0  ; индекс на каждый байт в пакете данных
.text:000000000040100E                 mov     [rbp+var_A30], rax
.text:0000000000401015
.text:0000000000401015 encrypt:                                ; CODE XREF: sub_400BE0+481j
.text:0000000000401015                 mov     eax, [rbp+count]
.text:000000000040101B                 cmp     eax, [rbp+packet_size?]
.text:0000000000401021                 jnb     loc_401066      ; выйти из цикла
.text:0000000000401027                 mov     eax, [rbp+count]
.text:000000000040102D                 movzx   ecx, [rbp+rax+keystream]
.text:0000000000401035                 mov     eax, [rbp+count]
.text:000000000040103B                 movsx   edx, [rbp+rax+packet_buf?]
.text:0000000000401043                 xor     edx, ecx        ; шифрование одного байта
.text:0000000000401045                 mov     sil, dl
.text:0000000000401048                 mov     [rbp+rax+packet_buf?], sil
.text:0000000000401050                 mov     eax, [rbp+count]
.text:0000000000401056                 add     eax, 1          ; инкремент индекса
.text:000000000040105B                 mov     [rbp+count], eax
.text:0000000000401061                 jmp     encrypt

Суть потокового шифра основана на том факте, что ключевой поток никогда не повторяется. То есть, любая "часть" гаммы должна когда-либо использоваться для шифрования одной "части" открытого текста только один раз.

В этой программе, функция генерации ключевого потока вызывается только один раз: после обмена ключами. Затем эта гамма повторно применяется (reused) к каждому отдельному сообщению, когда-либо отправленному. Значит, ко всем сообщениям, что у нас есть, можно применить атаку "использование одного и того же ключа дважды" (reused key attack). Похожая задачка мне уже встречалась. И это было так же просто, как и сейчас.

Взлом и проникновение

Когда ключ в потоковом шифре используется неоднократно, то взломать такой шифр проще. Общий подход при нахождении ключа в таком случае состоит в том, чтобы выяснить, какой длины ключ, и где он начинает повторяться. Как мы знаем, длина ключевой последовательности составляет 1024 (0x400) байт. Это намного больше длины любого доступного нам сообщения из pcap-файла. Значит, мы никогда не увидим повторное использование ключевой последовательности в течение одного сообщения.

Однако, так как переменная count (смотрите кусок дизассемблированного кода выше) используется в качестве индекса как для гаммы, так и для данных пакетов, ключевая последовательность повторяется заново с каждым новым отправленным пакетом. Другими словами, n-й байт гаммы используется для шифрования n-го байта открытого текста в каждом сообщении, и что n-й байт ключевой последовательности один и тот же.

Предположим у нас есть три перехваченных криптограммы (в 16-тиричной кодировке):
AABBCCDDEE
112233445566778899
FFFFFFFF

Создадим новые криптограммы на основании нумерации байт (эдакая разбивка по "столбцам"). Возьмем сначала только первый байт от каждой криптограммы AA11FF, затем только второй байт BB22FF, затем третий - CC33FF и т.д. Каждая наша новая криптограмма зашифрована только одним байтом ключевой последовательности. И найти его просто. Достаточно получить все возможные расшифрованные варианты по всем значениям от 0 до 255. Ожидаемые расшифрованные символы должны быть "текстовые" (ASCII от 0x20 до 0x7A). Таким образом, мы находим возможные варианты одного байта ключевой последовательности, и мы можем расшифровать одну "колонку" перехваченных криптограмм.

Но этого мало. Без ручной работы здесь не обойтись. Полученные расшифрованные варианты обрабатываем по принципу частотного анализа (ищем часто используемые символы, слоги, триграммы и т.п; т.к. мы знаем, что сообщения должны быть написаны на английском языке).

В нашем случае даже немного проще. Т.к. для "захвата" сообщений с консоли используется функция fgets, то мы точно знаем, что последний символ каждого сообщения должен быть символ новой строки 0x0A. Обойдем все зашифрованные криптограммы, мы найдем значения байт ключевой последовательности, которые шифруют символ новой строки.

Кстати, самое первое сообщение будет расшифровываться как "hi\x0A".

Итак, наш алгоритм действий:

  • Получить криптограммы из pcap-файла
  • Найдем байты ключа для позиций символа новой строки
  • Создадим новые криптограммы и возможные символьные варианты для каждого значения байта ключа
  • Используя принципы частотного анализа, вручную восстанавливаем ключ
  • ???
  • Profit

Приблизительно после часа моих трудов над расшифровкой сообщений, организаторы выложили подсказку:

23:28 -!- RyanWithZombies changed the topic of #gits-ctf to:
[...] Pillowtalk: the giant function is "curve25519-donna"

В этот момент для меня стало очевидным две вещи:

  • Я обрадовался тому, что не стал тратить время на реверс этой огромной функции.
  • Я не знаю как отличить симметричную и асимметричную криптографию в дизассемблированном виде.

Продолжив ручную расшифровку текстов, я в итоге получил флаг, принесший 200 очков нашей команде.

Заключение

После CTF, у меня осталось два нерешенных вопроса: что за потоковый шифр использовался для генерации ключевой последовательности? для чего нужна строка, состоящая только из символа табуляции, в процедуре обмена ключами?

Я решил пересмотреть функции sub_401290 и sub_4013B0, участвующие в создании гаммы из утвержденного ключа. После рассмотрения sub_401290, меня привлек вот этот фрагмент кода:

.text:00000000004012AE fill_with_i:           
.text:00000000004012AE                 cmp     [rsp+count], 100h
.text:00000000004012B6                 jge     loc_4012E1
.text:00000000004012BC                 mov     eax, [rsp+count]
.text:00000000004012C0                 mov     cl, al
.text:00000000004012C2                 movsxd  rdx, [rsp+count]
.text:00000000004012C7                 mov     rsi, [rsp+var_8]
.text:00000000004012CC                 mov     [rsi+rdx], cl
.text:00000000004012CF                 mov     eax, [rsp+count]
.text:00000000004012D3                 add     eax, 1
.text:00000000004012D8                 mov     [rsp+count], eax
.text:00000000004012DC                 jmp     fill_with_i

Код линейно заполнял каждый элемент 256-гобайтного массива своим же индексом. Первый элемент устанавливается в 0, второй в 1, и т.д. Хотя во время CTF этот кусок кода для меня не был очевидным, но теперь стало ясно: я смотрел на первый этап (из двух) алгоритма RC4. Значит, первая функция sub_401290 устанавливает внутреннее 256-тибайтное состояние RC4, а вторая sub_4013B0 - использует его для создания произвольной длины (в данном случае, 0x400 байт) гаммы по спецификации RC4.

Для ответа на второй вопрос я почитал о функции curve25519-donna (curve25519 является эллиптической кривой, разработанный Дэном Бернштейном / Dan Bernstein, для быстрого развертывания ключей по алгоритму Диффи-Хеллмана) и нашел её реализацию на Github, где в README нашел следующее:

Для создания открытого ключа (public key), сделайте так:
  static const uint8_t basepoint[32] = {9};
  curve25519_donna(mypublic, mysecret, basepoint);

ASCII-код символа табуляции равен 9. Я думаю, что IDA интерпретировала массив basepoint как строку "\t". Это было легко!

Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License