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

(Приготовьтесь к ванильной Java!)

Сроки атаки

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

Конечно, в реальной системе вы бы сравнили хеши или около того, но давайте будем простыми. Что мы хотели бы сделать, так это взломать этот объект, чтобы найти секретный пароль.

Топология String, созданная нашим объектом CredentialCheck, группирует ландшафт строк следующим образом:

  • Одноэлементные строки (кроме S) такие же базовые, как и SECRET PASSWOR, потому что все они не имеют правильного размера
  • S не хуже, чемSICRET PASSWORD, так как они оба терпят неудачу после проверки первого символа
  • SECRET HEJEOPO примерно в 6 раз лучше, чем SICRET PASSWORD

и так далее… Это верно с точки зрения объекта CredentialCheck и дает прекрасный пример системы, уязвимой для атаки по времени. Думая, что было бы полезно вернуться как можно быстрее, мы не предоставляем алгоритм с постоянным временем. Согласно входной тестовой строке, системе требуется больше или меньше операций для выполнения своей задачи. Это косвенная информация о реальном пароле.

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

Первое испытание брут-форсом

Использование затраченного времени для измерения - основная идея атаки по времени, но она дает гораздо больше вариаций в измерениях! Следующий тест методом грубой силы, в котором мы усреднили время выполнения на 1.000.000 попыток, говорит за нас:

Лучшим кандидатом, который мы получили, является AXBQCPTNOEHSTNND, который не имеет ничего общего с нашим паролем. Этот алгоритм уже имеет длину 1.000.000 * 26 * 16 (~ 2²⁹) раза. Брутто-форсирование каждой комбинации строк размером 16 со средним значением 1000 будет 1000 * 26¹³, то есть немного больше, чем 2⁸⁵ операций.

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

Генетический алгоритм

Наш MeasuredCredentialCheck дает нам тестовую функцию, которая измеряет качество объекта String: чем ниже оценка, тем лучше String; и минимум достигается только для секретного пароля.

Мы думаем о String как о биологических объектах с генетической ДНК, управляемой массивом символов. Чтобы взломать себя, мы реализуем эволюционный (генетический) алгоритм. Идея состоит в том, чтобы создать популяцию этих биологических нитей и имитировать на ней биологическую эволюцию.

Оценка, которую получает био-струна в тесте MeasuredCredentialCheck, показывает ее способность к воспроизведению. Воспроизведение био-струны называется кроссинговером. После воспроизведения наших цепочек мы также мутируем их ДНК, чтобы сохранить биоразнообразие среди населения.

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

Какой бы выбор мы ни сделали, при разработке генетических алгоритмов следует помнить о некоторых основных принципах:

  • Биологическое разнообразие действительно важно: не обязательно смягчать эффект мутаций.
  • Воспроизведение следует производить с осторожностью: слишком большое воспроизводство может замедлить процесс обучения, давая плохим конкурентам слишком большую эффективность в процессе эволюции.
  • Особое внимание следует уделить вымиранию населения. Сохранение постоянной численности популяции - хорошая идея для начала.

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

Общий план нашего генетического алгоритма

При разработке нашего генетического алгоритма мы постараемся упростить задачу.

Как вы можете видеть (я надеюсь, потому что я очень люблю делать код менее подробным, чем средняя Java!), Учитывая совокупность String, которая, как предполагается, отсортирована по эффективности (сначала лучшие), следующая совокупность спроектирована как

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

Первое условие гарантирует, что лучшие кандидаты вернутся в результирующую совокупность. Это должно немного ускорить процесс (мы настроили фанатов!). Кроссовер и мутации не происходят каждый раз: объект NaturalSelection оперирует ими случайным образом. Когда он что-то делает, он делает это в соответствии со следующими алгебраическими правилами:

Опять же, я думаю, что вложил в код достаточно любви, чтобы сделать его кристально ясным: мутация берет случайное количество символов в строке ДНК и изменяет их случайным образом. Пересечение (a,b) берет первый сегмент a и использует его для замены первых элементов b соответственно. Мы выбрали этот переход, потому что заподозрили (подшиваем), что объект CredentialCheck закодирован как есть (например, мы украли информацию из github).

Теперь, когда мы знаем, как работает естественный отбор, мы можем разработать план эволюции:

И снова, я думаю, что здесь происходит, должно быть ясно: учитывая начальную случайную популяцию, мы оцениваем ее (поколение 0) и запускаем эволюционный процесс: вычисляем следующее поколение и останавливаемся, если найдено что-то идеальное, или ждем истечения времени ожидания.

Результат

Результат довольно интересный. Тест атаки проходит следующим образом:

Мы начали с довольно небольшой совокупности (2⁹ = 512) для каждого размера строки от 1 до 19 включительно. Таким образом, общая численность населения составляет 9728 человек (~ 2¹³). Истекшее время атаки указано только для информации.

Стоимость генетического алгоритма примерно определяется как O(n log(n) * m), где n - размер популяции, а m - количество итераций. Здесь у нас около 2²⁹ для 1.000, но мы увидим, что оптимальное значение составляет около 200. Само собой разумеется, что мы не оптимизировали наш дизайн (например, тестирование паролей длиной менее 8 не очень полезно).

Запуск этого алгоритма дает следующие результаты:

Как видите, старт довольно сложный и медленный. Красным цветом мы выделили два поколения, у которых лучшие конкуренты (!) - очень короткие струны. Зеленым цветом мы выделили два поколения, в которых приставка «SEC» уже встречалась у лучшего конкурента.

Мы достигли оптимальной конфигурации в поколении 190, примерно через 1,2 секунды (многократный запуск алгоритма может дать только ~ 100 поколений!). Красным цветом мы заметили интересное шумное поведение виртуальной машины Java. Как видите, лучшие конкуренты для тех поколений ничем не хуже одноэлементной строки!

Мы думаем, что это связано с чрезвычайной стохастической природой имеющихся у нас измерений. По-прежнему интересно видеть, что, хотя эти плохие, но все же лучшие исполнители существуют в той же пропорции, что и другие, общая картина быстро восстанавливается до чего-то, закрытого для СЕКРЕТНОГО ПАРОЛЯ.

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

Фактически, есть популяция через некоторое время, где мы могли бы отметить, что процент оптимальных конкурентов увеличивается примерно на 20%.

В информационных целях, вот еще один прогон с геометрической информацией в терминах расстояния Левенштейна:

Предотвращение временной атаки

Хорошо, теперь, когда мы успешно взломали себя, как мы можем защитить себя? Что ж, обычно бывает довольно сложно защитить систему от атаки по времени, потому что и компилятор, и среда выполнения могут использовать инструкции end-fast. Это также может происходить из-за арифметических операций в процессоре и связанных с ним вещей.

Первым шагом может быть усиление объекта CredentialCheck, чтобы он закончил с постоянным счетчиком инструкций:

Запустить наш алгоритм на этом сервисе не получится:

Значит ли это, что мы в безопасности? Я не знаю. Но, может быть, мы в большей безопасности, чем раньше!

Заключительные слова

Вот как я потратил некоторое время, развлекаясь, имитируя временную атаку с помощью подхода генетического алгоритма. Хотя установка не идеальна, я надеюсь, что она пробудит у вас любопытство по той или иной теме, и что вы с удовольствием читали код Java.

Код находится в свободном доступе на моем гитхабе (/ Judekeyser / Genetictimingattack), если вам интересно, как все устроено.

Любой конструктивный отзыв приветствуется.

Ваше здоровье!