Бэкдор

• сложно обнаружить;
• можно использовать многократно;
• легко отрицать — выглядит, как ошибка, и в случае обнаружения разработчик может сослаться на то, что допустил эту ошибку случайно и злого умысла не имел;
• эксплуатируем только при знании секрета — только тот, кто знает, как активируется бэкдор, может им воспользоваться;
• защищён от компрометации предыдущими использованиями — даже если бэкдор был обнаружен, то невозможно установить, кем он до этого эксплуатировался и какой информацией завладел злоумышленник;
• сложно повторить — даже если бэкдор был кем-то найден, то его невозможно будет использовать в другом коде или в другом устройстве.

• слабая устойчивость алгоритма к криптоанализу;
• специально подобранные константы — алгоритм может стать неустойчивым к криптоанализу при выборе определённых значений констант, используемых в его работе;
• сложность в безопасной реализации — это означает, что безопасная реализация алгоритма работает слишком медленно, и все будут использовать небезопасный вариант, что и выгодно злоумышленнику.

Данный генератор был разработан в АНБ и стандартизован в качестве криптографически стойкого генератора псевдослучайных чисел национальным институтом стандартов и технологий США NIST в 2006 году. Однако уже в 2007 году независимыми исследователями было высказано предположение, что в этот алгоритм мог быть встроен бэкдор.[3][4][5]

Иллюстрация работы алгоритма согласно спецификации АНБ[6]:

Данный алгоритм использует эллиптические кривые. ${\displaystyle P}$ — генератор группы точек на эллиптической кривой, ${\displaystyle Q}$ — точка на эллиптической кривой — константа, определённая стандартом, как она была выбрана неизвестно. Параметры самой кривой также заданы стандартом.

Принцип работы:

Уравнение кривой

${\displaystyle y^{2}=(x^{3}+ax+b){\bmod {p}}}$

можно переписать в виде ${\displaystyle x=\varphi (x,y){\bmod {p}}}$ и записать следующие выражения для работы алгоритма:

${\displaystyle r_{i}=\varphi (s_{i}*P)}$ , ${\displaystyle t_{i}=\varphi (r_{i}*Q)}$ , ${\displaystyle s_{i+1}=\varphi (r_{i}*P)}$

${\displaystyle s_{i}}$ — внутреннее состояние генератора на текущем шаге

${\displaystyle s_{i+1}}$ — внутреннее состояние генератора на следующем шаге

${\displaystyle t_{i}}$ — выход генератора на текущем шаге

Предполагаемый бэкдор:

Так как ${\displaystyle p}$ — простое число, то существуют такое число ${\displaystyle e}$, что ${\displaystyle e*Q=P}$. Нахождение ${\displaystyle e}$ — вычислительно сложная задача дискретного логарифмирования на эллиптической кривой, для решения которой на сегодняшний день не существует эффективных алгоритмов. Но если предположить, что злоумышленник знает ${\displaystyle e}$ , то получается следующая атака: Если ${\displaystyle x=t_{i}}$ — очередной выход генератора, и если существует такое ${\displaystyle y}$, что ${\displaystyle y^{2}\equiv (x^{3}+ax+b){\bmod {p}}}$, то точка ${\displaystyle A=(x,y)}$, лежит на кривой и для неё выполняется следующее равенство: ${\displaystyle A=r_{i}*Q}$. Зная число ${\displaystyle e}$ можно вычислить: ${\displaystyle s_{i+1}=\varphi (e*A)=\varphi (e*r_{i}*Q)=\varphi (r_{i}*P)}$. Таким образом, злоумышленник, знающий число ${\displaystyle e}$, может не только вычислить следующий выход генератора, но и быстро перебрать все возможные внутренние состояния генератора и восстановить его начальное внутреннее состояние. Согласно независимым исследованиям[7][2], при знании ${\displaystyle e}$ достаточно всего 30 байт выходной последовательности генератора, чтобы простым перебором ${\displaystyle 2^{15}}$ значений восстановить его начальное внутреннее состояние. По мнению исследователей, такая уязвимость может быть расценена как бэкдор.

Исследователями компании Яндекс была обнаружена уязвимость в реализации протокола TLS в одном из программных продуктов Apple[2]. По их мнению, данная ошибка вполне может оказаться бэкдором, намеренно встроенным в алгоритм кем-то из разработчиков.

Участок кода с ошибкой:

static DSStatus SSLVerifySignedServerKeyExchnge(....)
{
     DSStatus err;
     ....
     if ((err = SSLHashSHA1.update(&hashCtx, &signedParams)) != 0)
          goto fail;
          goto fail;
     if ((SSHashSHA1.final(&hashCtx, &hashOut)) != 0)
          goto fail;
     ....
     fail:
          ....
          return err;
}

Как можно видеть, после первого оператора if стоят две строчки goto fail, и вторая строчка выполняется всегда, независимо от результата if. Таким образом процедура проверки сертификата проходит не полностью. Злоумышленник, знающий об этой уязвимости, может подделать сертификат и пройти проверку подлинности. Это позволит ему организовать атаку типа «Человек посередине», тем самым вмешаться в защищённое соединение между клиентом и сервером. Исследователи, обнаружившие данную ошибку в реализации, не могут точно сказать, намеренно она была сделана или случайно. Вполне возможно, что это бэкдор, встроенный в алгоритм кем-то из разработчиков.

Очень многие современные криптографические алгоритмы используют при своей работе определённый набор внутренних констант. Как правило, эти константы задаются стандартом и выбираются из соображений криптографической стойкости к известным на данный момент видам криптоанализа. Но выбор констант при стандартизации алгоритма теоретически может быть использован разработчиками и со злым умыслом: например, для создания определённых уязвимостей и бэкдоров в алгоритме.

В качестве такого примера использования констант можно привести недавние исследовательские работы на тему так называемого «вредоносного хеширования»[8][9], где авторам удалось построить коллизии для криптографической хеш-функции SHA1 путём модификации её раундовых констант. Отметим, что предложенная авторами исследования атака не является атакой на саму хеш-функцию SHA1, она позволяет лишь находить коллизии при условии возможности изменения раундовых констант и только для определённых типов файлов.

Краткое описание SHA1:

SHA1 — современная раундовая хеш-функция. Алгоритм хеширования следующий:

• Инициализируются 32-битные значения ${\displaystyle a=h_{0},b=h_{1},c=h_{2},d=h_{3},e=h_{4}}$
• Входное сообщение разбивается на блоки длиной 512 бит
• Каждый блок сообщения обрабатывается и дополняется специальным образом, по алгоритму, определённому в стандарте
• Полученный блок сообщения хэшируется в 4 этапа по 20 раундов в каждом, причём для каждого этапа используется своя константа ${\displaystyle K_{1},K_{2},K_{3}}$ или ${\displaystyle K_{4}}$
• Выходом функции для каждого блока будут новые значения ${\displaystyle a,b,c,d,e}$, которые добавляются к результату: ${\displaystyle h_{0}=h_{0}+a,h_{1}=h_{1}+b,h_{2}=h_{2}+c,h_{3}=h_{3}+d,h_{4}=h_{4}+e}$
• Итоговым результатом хеширования будет 160-битное значение полученное конкатенацией пяти 32-битных значений ${\displaystyle h_{0},h_{1},h_{2},h_{3},h_{4}}$ после обработки последнего блока сообщения.

Построение коллизий:

Целью рассматриваемой атаки является нахождение таких констант ${\displaystyle K_{1},K_{2},K_{3},K_{4}}$ и таких сообщений ${\displaystyle M_{1}}$ и ${\displaystyle M_{2}}$ , что ${\displaystyle Hash(M_{1})=Hash(M_{2})}$. Данная атака модифицирует только первые 512 бит (1-й блок) сообщений, для которых требуется построить коллизию. Алгоритм базируется на уже известной разностной атаке на SHA1, предложенной в 2005 году[10][11] и имеющей сложность порядка ${\displaystyle 2^{69}}$ операций, что делает её трудноосуществимой на практике. Поэтому до настоящего времени ни одной реальной коллизии для SHA1 найдено не было.

Но в случае создания вредоносного варианта SHA1 злоумышленник может варьировать не только блоки сообщений ${\displaystyle M_{1}}$ и ${\displaystyle M_{2}}$, но и раундовые константы ${\displaystyle K_{1},K_{2},K_{3},K_{4}}$. Согласно исследованиям[9], это сильно снижает сложность атаки до порядка ${\displaystyle 2^{48}}$ операций и делает построение таких коллизий реальной задачей которую можно выполнить на нескольких компьютерах. Таким образом, авторам исследования удалось построить одноблоковые коллизии для многих известных типов файлов.

Одноблоковая коллизия:

${\displaystyle M_{1}}$ и ${\displaystyle M_{2}}$ — первые блоки сообщений (512 бит), которые отличаются между собой, но дают одинаковую хеш-сумму

${\displaystyle Content}$ — остальное содержимое, которое одинаково для обоих файлов

С помощью описанной атаки были созданы два sh-скрипта, которые при выборе ${\displaystyle K_{1}=5a827999~,~K_{2}=88e8ea68~,~K_{3}=578059de~,~K_{4}=54324a39}$ дают одинаковую хеш-сумму SHA1, но работают по-разному.

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