Вы возможно уже видели препринт опубликованный сегодня Ленстрой и др (обсуждение на хабре) о проблемах с энтропией в криптографических системах с открытыми ключами. Закир Дурумерик, Ерик Вустров, Алекс Халдерман, и Я (Надя Хенингер) ждали, чтобы раскрыть похожие результаты. Мы опубликуем полную статью после того, как все задействованные производители будут оповещены. А между тем мы хотим предоставить более полное объяснение того, что же реально происходит.
Мы смогли удалено скомпрометировать около 0.4 % от всех открытых ключей, используемых веб сайтами для SSL. Все скомпрометированные ключи были неправильно сгенерированы, с использованием предсказуемых «рандомных» чисел, которые к тому же ещё и иногда повторялись. Всего мы можем выделить два типа проблем: ключи, сгенерированные с предсказуемой рандомностью, и подмножество этих ключей, для которых нехватка рандомности позволяет атакующему быстро факторизовать открытый ключ и получить секретный ключ. Имея секретный ключ, атакующий сможет выдать себя за вебсайт и возможно сможет расшифровывать зашифрованный трафик направленый на этот сайт. Мы разработали программу которая за пару часов может факторизовать открытые ключи и выдавать секретные ключи для всех хостов уязвимых к этой атаке.
Тем не менее, не стоит паниковать, так как в основном проблема влияет на встраиваемые системы, такие как маршрутизаторы и VPN, и не касается полномасштабных серверов. (Во всяком случае это точно не причина терять доверенность к электронной коммерции, как это предполагает New York Times). К сожалению, мы нашли устройства с этой проблемой практически у каждого производителя и мы подозреваем, что около 200.000 устройств, представляющих 4.1% от всех ключей в наших данных, использовали плохую энтропию для генерации ключей. Любой найденный слабый ключ сгенерированный устройством предполагает, что весь класс этих устройств уязвим для атаки при должном анализе.
Мы не будем предоставлять полный список уязвимых устройств до того как мы свяжемся со всеми производителями, но используя уже опубликованные материалы можно довольно легко воспроизвести атаку. Поэтому мы сейчас работаем над веб сайтом, который позволит определить уязвимо ли ваше устройство.
Не волнуйтесь, ключ вашего банка скорее всего в безопасности.
SSL используется каждым большим сайтом в Интернете, но как показывает наш анализ, эти ключи не подвержены проблемам описанным в этом посте.
Так какие же системы в опасности? Почти все уязвимые ключи были сгенерированы и использовались во встраиваемых системах, таких как, маршрутизаторы и брандмауэры, и не использовались на вебсайтах для банков или e-mail. Только один из уязвимых SSL ключей был подписан центром сертификации и он уже истек. Также мы нашли несколько подписанных сертификатов использующих повторяющиеся ключи; некоторые из которых были сгенерированы уязвимыми устройствами, другие были поданы на подпись владельцами сайтов как заведомо слабые и для некоторых мы не можем придумать хорошее объяснение.
Всем известно что во встраиваемых системах есть проблемы с энтропией. Однако, до текущего времени не было понятно насколько эти проблемы были распространены в реальных устройствах, подключенных к интернету.
Генерация Ключей
Веб сайты и сетевые компьютеры используют криптосистемы с открытыми ключами для идентификации. Дальше мы будем говорить о типе идентификации, когда сервер предоставляет клиенту сертификат для того, чтобы удостоверить клиента что он именно тот к кому клиент хочет подключиться. Если атакующий знает секретный ключ, он может выдать себя за реальную систему или в большинстве случаев расшифровать трафик между клиентом и сервером.
RSA является чаще всего используемой криптосистемой для этих целей. Защита RSA криптосистемы построена на факторизации больших чисел. Открытый ключ RSA состоит из пары целых чисел: открытой экспоненты е и модуля N, являющимся произведением двух больших простых чисел p и q. Если противник сможет факторизовать N обратно в p и q, то он также сможет расшифровать любой текст зашифрованный открытым ключом. Однако, даже используя самые быстрые алгоритмы для факторизации, никто ещё не смог факторизовать 1024-битовый модуль.
Важной частью для безопасности ключа является наличие рандомных входных данных на стадии генерации ключа. Если в этих входных данных недостаточно энтропии, тогда атакующий сможет их угадать, и таким образом получить секретный ключ, без мучительной факторизации числа N.
На современных компьютерах и серверах, программы для генерации ключей используют рандомные входные данные полученные из множества физических источников (чаще всего при помощи операционной системы): движения мышки, клавиатуры, жесткого диска, сетевых событий и других не предсказуемых источников. Однако, если источников мало то будет не хватать энтропии, и ключ может оказаться уязвим для атаки. Собирание сильной энтропии и проверка её силы является очень сложной проблемой, которая породила много уязвимостей на протяжении многих лет.
Две версии проблемы
Для исследования насколько распространена эта проблема, мы просканировали все IPv4 адреса и собрали копии каждого SSL сертификата и ключа SSH. Собирание ключей и сертификатов заняло у нас меньше дня: сначала мы использовали стандартный nmap, чтобы найти хостов с соответствующими открытыми портами, а потом мы использовали свою оптимизированную программу для опроса этих хостов. Всего мы собрали 5,8 миллиона SSL сертификатов и 10 миллионов SSH ключей.
Как мы обнаружили, проблемы с энтропией приводят к двумя разным видам слабостей:
Повторяющиеся открытые ключи.
Около 1% всех RSA ключей встречались повторно, скорее всего из за проблем с энтропией. Если у двух устройств одинаковый открытый ключ, то у них также одинаковый секретный ключ. В действительности все устройства с одинаковым ключом находятся в одинаковом положении — атакующий может скомпрометировать слабейшие из этих устройств и получить ключи ко всем остальным. Уже давно было известно об этой проблеме, но до нынешнего момента, никто не документировал в открытой литературе насколько она распространена.
Мы вручную проверили, что 59.000 ключей были повторены из за проблем с энтропией, которые представляют около 1% всех сертификатов, или 2,6% все самостоятельно подписанных сертификатов. Мы также нашли что 4.6% всех устройств (585,000 сертификатов) использовали сертификаты установленные по умолчанию. И хотя эти устройства не использовали ключи сгенерированые с плохой энтропией, они подвержены такой же атаке, так как их секретные ключи одинаковы на всех моделях. Мы вручную проверили все эти ключи, потому что большое количество сайтов использует повторяющиеся ключи в правильных условиях и поэтому не предоставляет опасности для пользователя.
Факторизуемые открытые ключи.
Что более удивительно, мы обнаружили, что проблемы с энтропией могут позволить удаленному атакующему, без специального доступа, факторизовать значительную часть всех RSA ключей, используемых в Интернете. Мы смогли факторизовать 0,4% всех RSA ключей в SSL сертификатах. Для этого мы посчитали наибольший общий делитель (gcd) для всех пар модулей из открытых ключей RSA в Интернете.
Мы определили 1724 общих делителей, что позволило нам факторизовать 24.816 SSL ключей и 301 общих делителей для факторизации 2422 SSH ключей. Это значит, что мы смогли посчитать секретные ключи для почти 0.5% RSA ключей, используемых для SSL. Дальше мы объясним как наш расчет работает.
Конкретные уязвимые устройства
Встраиваемые системы часто генерируют криптографические ключи при первой загрузке, когда все их состояние может быть предопределено на заводе. Что может привести к таким проблемам с энтропией, как описано в этом исследовании.
Мы смогли использовать информацию из SSL сертификата для идентификации типа устройств которые склонны к генерации слабых ключей. Наверное также существует множество других устройств, ключи которых мы не смогли факторизовать, но которые все равно склонны к произведению слабых ключей и которые могут быть скомпрометированы упорным атакующим. Полный список уязвимых устройств которые мы смогли идентифицировать состоит из больше чем 30 производителей, включая почти всех больших производителей в индустрии. Типы устройств с проблемой включают брандмауэры, маршрутизаторы, VPN устройства, устройства для удалённой администрации серверов, принтеры, прожекторы, и VOIP телефоны.
Мы не будем перечислять имена устройств до того как мы оповестим, но ниже можно увидеть несколько примеров:
Брандмауэр Х:
52.055 хостов в наших SSL данных
6.730 с одинаковыми ключами
12.880 с факторизуемыми ключами
Маршрутизатор Y пользовательского уровня:
26.952 хостов в наших SSL данных
9.345 с одинаковыми ключами
4.792 с факторизуемыми ключами
Решение для удаленого доступа Z, для предприятий:
1.648 хостов в наших SSL данных
24 с одинаковыми ключами
0 с факторизуемыми ключами
Как это могло произойти?
Это не совсем очевидно, как проблемы с энтропией могут привести к проблемам с ключами которые легко факторизовать. Сейчас мы объясним почему так происходит для наших более любознательных читателей.
Вот как программист может сгенерировать модуль для RSA:
prgn.seed(seed)
p = prgn.generate_random_prime()
q = generate_random_prime()
N = p*q
Если зерно для генератора псевдослучайных чисел имеет предсказуемое значение, тогда несколько различных устройств могут иметь одинаковый модуль N, но мы не думаем что хорошие генератор псевдослучайных чисел могут произвести два разных модуля N, с общим одинаковым фактором.
Однако, некоторые реализации также добавляют дополнительною рандомность между генерацией простых чисел p и q, с идеей повышения безопасности:
prgn.seed(seed)
p = prgn.generate_random_prime()
prgn.add_randomness(bits)
q = generate_random_prime()
N = p*q
Если первое зерно было сгенерировано с плохой энтропией, это может привести к тому, что у нескольких устройств будут разные модули, состоящие из одинаковых факторов p и разных факторов q. Поэтому мы можем факторизовать оба модуля используя GCD: p = gcd(N1, N2).
Генерация ключей RSA в OpenSSL работает следующим образом: после каждого использования рандомных битов из пула энтропии для генерации простых чисел p и q, текущее время в секундах добавляется в пул. Многие, но не все, уязвимые ключи были сгенерированы с использованием OpenSSL и OpenSSH, который использует OpenSSL для генерации RSA ключей.
Вычисление GCD для всех пар ключей
Если любая пара RSA модулей N1 и N2 имеет один одинаковый фактор, то можно просто факторизовать оба модуля используя gcd. На моем настольном компьютерe операция вычисления gcd для двух 1024 RSA модулей занимает около 17 микро секунд.
Для людей склонных к математике, сейчас я объясню как мы можем использовать эту идею для факторизации большого количества ключей.
Простой подход к факторизации ключей включает в себя вычисление gcd для каждой пары RSA модулей. Но если оценить сколько времени эти вычисления займут то мы получим около 24 лет на моем настольном компьютерe.
Вместо этого, мы используем идею Дена Берстейна, опубликованную в Journal of Algorithms в 2005 году, которая позволяет факторизовать группу целых чисел во взаимно простые числа и которая позволит нам произвести наши вычисления всего за пару часов, с реализацией занимающей всего несколько строк в Python. Алгоритм не является большой тайной: большое количество опубликованных работ работало над улучшением алгоритма.
Главное математическое обозрение в этой проблеме это то, что мы можем вычислить gcd для модуля N1 вместе со всеми другими модулями используя следующее уравнение:
gcd(N1, N2 ... Nm) = gcd(N1, (N1 * N2 * ... Nm mod N1^2)/N1)
Большая проблема в том как заставить просчёт этого уравнения производиться быстро — заметьте что первым шагом этого вычисления является нахождение произведения всех ключей, числа состоящего из 729 миллионов цифр. Мы смогли добиться факторизации всех SSL данных за 18 часов на одноядерном процессоре и факторизации SSH данных за 4 часа на четырех ядерном процессоре.
Заключение
Это конечно проблема, но не та о которой стоит волноваться обычному пользователю. Однако, много работы предстоит производителям встраиваемых систем, и некоторые системные администраторы должны быть обеспокоены. Это должно послужить пробуждающим звонком для людей в области безопасности, и напоминанием нам всем о том, как уязвимости иногда прячутся на виду у всех.
Автор: leaper
