Как тестировать

Предварительное условие — установленные gcc и уязвимая версия OpenSSL.

Для ошибки в BN_mod_sqrt(): скомпилируйте с помощью gcc -o my_bad_sqrt my_bad_sqrt.c -lcrypto, запустите ./my_bad_sqrt и наблюдайте бесконечное зависание! :D

С сертификатом: выполните openssl x509 -in certs/cert.der.new -inform DER -text -noout в командной строке; это также вызывает зависание.

Попадание в цикл

Функция BN_mod_sqrt() реализует алгоритм Тонелли-Шенкса для нахождения квадратного корня по модулю, т.е. для заданных целого числа a и простого числа p возвращает значение r такое, что r^2 == a (mod p).

Анализируя коммит, который исправляет уязвимость, мы видим, что виновником является цикл, который находит наименьший индекс i, для которого b^(2^i)==1 (mod p), где b определено ранее в алгоритме.

Цикл изменён с

на

Во втором случае используется цикл for, ограниченный переменной e; в исходном коде, однако, есть только проверка случая i==e внутри цикла while.

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

1. при первом выполнении внешнего цикла добиться, чтобы i=1 в конце; для этого необходимо, чтобы b^2=1 (mod p).
2. таким образом, во время второго выполнения мы получим e=1, и если мы сможем попасть во внутренний цикл, проверка i==e всегда будет проваливаться.
3. если мы сможем всегда иметь t != 1 (mod p), то останемся в цикле навсегда.

Заметьте, что первые два шага могут произойти и при «нормальном» выполнении, т.е. с простым p. Однако, если p составное, мы можем также выполнить и третий шаг!

Немного математики

Алгоритм Тонелли-Шенкса работает, записывая p - 1 = 2^e * q с нечётным q. Это также порядок мультипликативной группы целых чисел по модулю p, и значения e и q будут многократно использоваться во время выполнения; однако, если p не простое, порядок мультипликативной группы не будет равен p-1, и это поможет нам попасть в бесконечный цикл.

В частности, b инициализируется как b = a^q (mod p), что означает, что если бы p было простым, то b имело бы порядок, являющийся степенью двойки, который мы затем найдём с помощью цикла.

Но если мы установим p = r * s, порядок мультипликативной группы будет (r-1)*(s-1) = r*s - r - s + 1 вместо r*s-1. Алгоритм использует значение q для получения элемента y порядка ровно 2^e; однако, когда p не простое, значение q не будет иметь особого смысла для порядка, поэтому элемент y не будет иметь порядок, равный степени двойки, по модулю p=r*s.

Поскольку в конце первого внешнего цикла b устанавливается как b = b*y^(e-i) (mod p), на второй итерации внутренний цикл будет пытаться найти значение i, для которого b^(2^i) == 1 (mod p), но потерпит неудачу, так как y больше не гарантированно имеет порядок степени двойки.

Эксплойт

Числа в эксплойте очень простые: мы берём r=17,s=41, что даёт p=r*s=697. Это означает, что вычисленные значения e и q будут p-1 = 2^3 * 87.

Затем мы выбираем a=696, что означает a == -1 (mod p) и также b == -1 (mod p) при инициализации. Это удовлетворяет шагу 1, устанавливая e=1 для следующего внешнего цикла.

Затем b будет установлено в элемент, порядок которого не является степенью двойки, и внутренний цикл застрянет, пытаясь найти i, для которого b^(2^i)==1 (mod p).

Создание опасного сертификата

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

Файлы этого раздела находятся в папке certs.

Создание обычного сертификата с явными параметрами кривой

Сначала нужно создать закрытый ключ EC. Поскольку мы хотим получить целевой сертификат с явными параметрами кривой, ключ также должен содержать явные параметры кривой.

Затем для удобства мы подписываем сертификат самому себе и выводим его в формате DER.

Давайте проверим информацию о сертификате. Он содержит явные параметры кривой, как и ожидалось.

Создание недействительного сертификата

Теперь нужно изменить значения этих параметров: Prime, A, B, Generator. Они удовлетворяют уравнению ниже

где p — это Prime, a — параметр A, b — параметр B. p, a, b вместе определяют кривую. Разжатие точки означает вычисление координаты Y по соответствующей координате X.

Очевидно, что необходимо использовать операцию извлечения квадратного корня по модулю, которая вызовет BN_mod_sqrt().

Основываясь на работе drago-96, мы берём p=697, x^3+ax+b=696. Затем нам нужно выбрать подходящие a, b, x, удовлетворяющие второму уравнению. Здесь мы берём x=8, a=23, b=0.

Хорошо, теперь можно приступить к редактированию сертификата. Ручное редактирование структуры ASN.1 — ужасное занятие. Я использовал инструмент xxd, чтобы преобразовать сертификат в шестнадцатеричный формат, а затем отредактировал его с помощью vim. После завершения редактирования преобразовал обратно с помощью xxd -r.

Я не нашёл более удобного инструмента. Если кто-то знает такой инструмент, пожалуйста, поделитесь в комментариях.

Шаги создания примерно следующие:

1. Изменить значения Prime, A, B, Generator
   1. Изменить Prime на 697, т.е. 0x2b9 в шестнадцатеричном виде
   2. Изменить A на 23, т.е. 0x17 в шестнадцатеричном виде
   3. Изменить B на 0
   4. Изменить координату X Generator на 8, т.е. 0x020008 (или 0x030008) при кодировании в сжатом формате
2. Поскольку OpenSSL проверяет формат заполнения ASN1_INTEGER, Prime не должен содержать ведущие нулевые байты, поэтому нужно изменить длину Prime
3. Аналогично, OpenSSL сравнивает длину Prime с длиной строки точки, поэтому длина координаты X Generator должна совпадать с длиной Prime. Именно поэтому мы устанавливаем Generator как 030008, а не 0308.
4. Поскольку структура ASN.1 сертификата вложена, все длины внешних объектов также должны быть исправлены.
5. Обратите внимание, что после выполнения xxd -r в конце файла может появиться нежелательный символ новой строки (0x0a). Удалите его.

Теперь давайте посмотрим на структуру ASN.1 обычного сертификата. Части, отмеченные красной линией, нужно изменить.

Длины до и после модификации приведены ниже:

Использование ASN1-шаблонов

Обновлено 2020-03-21:

Намного проще использовать инструмент asn1template, написанный wllm-rbnt.

Клонируйте репозиторий:

Сгенерируйте DER-шаблон из этого сертификата:

Затем измените упомянутые выше параметры:

Преобразуйте обратно в DER-кодированный ASN1 с помощью ASN1_generate_nconf(3):

Результат cert_new.der эквивалентен версии, отредактированной вручную.

Итак, мы успешно создали недействительный сертификат. Давайте посмотрим новую структуру ASN.1

Все красные части были изменены, и сертификат корректно декодируется DER.

Тестирование с недействительным сертификатом

Теперь попробуем разобрать сертификат. Если всё ожидаемо, процесс войдёт в бесконечный цикл.

Как показано, %CPU процесса openssl равен 100, и стек вызовов находится внутри BN_mod_sqrt().

Если злоумышленник отправит такой созданный сертификат при установке SSL-соединения с сервером, сервер войдёт в бесконечный цикл, что вызовет DoS-атаку.

Создание сертификата, альтернативный способ

Мы попробуем создать сертификат с помощью библиотеки OpenSSL C libcrypto.

Как мы видели, нужно использовать кривую с составным основным полем и кодировать точки в сжатой форме, чтобы при разборе попасть в ошибку в BN_mod_sqrt().

Это можно сделать, установив кривую y^2 = x^3 + 1*x + 694 (mod 697) с генератором (1, 132); это вызовет BN_mod_sqrt() с теми же параметрами, что и в my_bad_sqrt.

Выполнение gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_group создаст файл my_bad_group.der, который содержит ECparams в формате DER.

Попытка разобрать эти параметры с помощью OpenSSL приведёт к бесконечному циклу: openssl ecparam -in my_bad_group.der -inform der.

... WIP ...