Атака грубой силой

Эта статья о криптоаналитическом методе. Информацию о методах с аналогичными названиями в других дисциплинах см. в разделе « Грубая сила» .

, созданная в 1998 году Electronic Frontier Foundation стоимостью 250 000 долларов США DES Машина для взлома , содержала более 1800 специальных чипов и могла подобрать ключ DES за считанные дни. На фотографии показана печатная плата DES Cracker, оснащенная 64 чипами Deep Crack с обеих сторон.

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

Атака методом перебора — это криптоаналитическая атака , которую теоретически можно использовать для попытки расшифровки любых зашифрованных данных (за исключением данных, зашифрованных теоретически безопасным способом). Такая атака может быть использована, когда невозможно воспользоваться другими слабыми местами в системе шифрования (если таковые имеются), которые могли бы облегчить задачу.

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

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

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

Основная концепция

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

пределы

Ресурсы, необходимые для грубой атаки, растут экспоненциально с увеличением размера ключа , а не линейно. Хотя экспортные правила США исторически ограничивали длину ключей 56-битными симметричными ключами (например, Data Encryption Standard ), эти ограничения больше не действуют, поэтому современные симметричные алгоритмы обычно используют более сильные в вычислительном отношении ключи длиной от 128 до 256 бит.

Существует физический аргумент в пользу того, что 128-битный симметричный ключ вычислительно защищен от атаки методом перебора. Предел Ландауэра , вытекающий из законов физики, устанавливает нижний предел энергии, необходимой для выполнения вычислений, равный kT   · ln 2 на бит, стираемый при вычислении, где T — температура вычислительного устройства в кельвинах , k — постоянная Больцмана. , а натуральный логарифм 2 составляет около 0,693 (0,6931471805599453). Ни одно необратимое вычислительное устройство не может потреблять меньше энергии, даже в принципе. Таким образом, чтобы просто просмотреть возможные значения 128-битного симметричного ключа (игнорируя фактические вычисления для его проверки), теоретически потребуется 2 ¹²⁸ − 1 бит переворачивается на обычном процессоре. Если предположить, что расчет происходит при комнатной температуре (≈300 К), предел фон Неймана-Ландауэра можно применить для оценки требуемой энергии как ≈10 ¹⁸ джоулей , что эквивалентно потреблению 30 гигаватт электроэнергии в течение одного года. Это равно 30×10 ⁹ Ш×365×24×3600 с = 9,46×10 ¹⁷ Дж или 262,7 ТВтч (около 0,1% годового мирового производства энергии ). Полное фактическое вычисление — проверка каждого ключа на предмет того, найдено ли решение — потребует во много раз большего объема. Более того, это просто потребность в энергии для езды по ключевому пространству; фактическое время, необходимое для переворота каждого бита, не учитывается, которое заведомо больше 0 (см. предел Бремермана ).

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

Современные графические процессоры хорошо подходят для повторяющихся задач, связанных с аппаратным взломом паролей.

коммерческие преемники правительственных решений ASIC По мере того, как стали доступны , также известные как пользовательские аппаратные атаки , две новые технологии доказали свою способность атаковать определенные шифры методом перебора. Одним из них является технология современных графических процессоров (GPU), другой — это технология программируемой вентильной матрицы (FPGA). Графические процессоры выигрывают от своей широкой доступности и соотношения цена-качество, а FPGA – от энергоэффективности на каждую криптографическую операцию. Обе технологии пытаются перенести преимущества параллельной обработки на атаки методом перебора. В случае графических процессоров — несколько сотен, а в случае FPGA — несколько тысяч процессоров, что делает их гораздо лучше подходящими для взлома паролей, чем обычные процессоры. Например, в 2022 году 8 графических процессоров Nvidia RTX 4090 были связаны вместе для проверки надежности пароля с помощью программного обеспечения Hashcat, и результаты показали, что 200 миллиардов восьмизначных комбинаций паролей можно циклически пройти за 48 минут.

Различные публикации в области криптографического анализа доказали энергоэффективность современной технологии FPGA, например, компьютер COPACOBANA FPGA Cluster потребляет ту же энергию, что и один ПК (600 Вт), но работает как 2500 ПК для определенных алгоритмов. Ряд фирм предоставляют аппаратные решения для криптографического анализа FPGA, от одной карты FPGA PCI Express до выделенных компьютеров FPGA. Шифрование WPA и WPA2 успешно подверглось атаке методом перебора, благодаря чему рабочая нагрузка снизилась в 50 раз по сравнению с обычными процессорами. и несколько сотен в случае FPGA.

Одна доска COPACOBANA с 6 спартанцами Xilinx — кластер состоит из 20 из них.

Расширенный стандарт шифрования (AES) позволяет использовать 256-битные ключи. Для взлома симметричного 256-битного ключа методом перебора требуется 2 ¹²⁸ раз больше вычислительной мощности, чем 128-битный ключ. Один из самых быстрых суперкомпьютеров 2019 года имеет скорость 100 петафлопс , что теоретически может проверить 100 миллионов (10 ¹⁴ ) Ключи AES в секунду (при условии 1000 операций на проверку), но все равно потребуется 3,67×10 ⁵⁵ лет, чтобы исчерпать 256-битное ключевое пространство.

В основе атаки методом перебора лежит предположение, что для генерации ключей было использовано все ключевое пространство, что основано на эффективном генераторе случайных чисел , и что в алгоритме или его реализации нет дефектов. Например, ряд систем, которые первоначально считались невозможными для взлома методом грубой силы, тем не менее были взломаны , потому что ключевое пространство для поиска оказалось намного меньше, чем первоначально предполагалось, из-за отсутствия энтропии в их псевдослучайном числе. генераторы . К ним относятся Netscape реализация Secure Sockets Layer (SSL) (взломанная Яном Голдбергом и Дэвидом Вагнером в 1995 году) и для Debian / Ubuntu версия OpenSSL , обнаруженная в 2008 году как имеющая недостатки. Подобный недостаток реализованной энтропии привел к взлому кода Enigma .

Переработка учетных данных

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

Невзламываемые коды

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

Контрмеры

В случае автономной атаки, когда злоумышленник получил доступ к зашифрованному материалу, можно попробовать комбинации клавиш без риска обнаружения или вмешательства. В случае онлайн- атак администраторы баз данных и каталогов могут применять контрмеры, такие как ограничение количества попыток ввода пароля, введение временных задержек между последовательными попытками, увеличение сложности ответа (например, требование ответа CAPTCHA или использование многофакторной аутентификации). аутентификация ) и/или блокировка учетных записей после неудачных попыток входа в систему. Администраторы веб-сайта могут запретить определенному IP-адресу использовать больше заранее определенного количества попыток ввода пароля для любой учетной записи на сайте. Кроме того, платформа MITRE D3FEND предоставляет структурированные рекомендации по защите от атак методом перебора путем реализации таких стратегий, как фильтрация сетевого трафика, развертывание ложных учетных данных и аннулирование кэшей аутентификации.

Обратная атака методом перебора

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

См. также

• Майнинг биткойнов
• Длина криптографического ключа
• Distributed.net
• Радуйся, Мэри Клауд
• Функция вывода ключей
• MD5CRK
• Метасплоит Экспресс
• Атака по побочному каналу
• МИГАЮТ и ВЕРЮТСЯ
• Расстояние уникальности
• Факторинговый вызов RSA
• Безопасная оболочка

Ссылки

• Адлеман, Леонард М .; Ротемунд, Пол В.К .; Роуэйс, Сэм ; Уинфри, Эрик (10–12 июня 1996 г.). О применении молекулярных вычислений к стандарту шифрования данных . Материалы второго ежегодного собрания по компьютерам на основе ДНК . Принстонский университет .
• Взлом DES – секреты исследования шифрования, политики прослушивания телефонных разговоров и проектирования чипов . Фонд электронных границ . 1998. ISBN  1-56592-520-3 .
• Бернетт, Марк; Фостер, Джеймс К. (2004). Взлом кода: безопасность веб-приложений ASP.NET . Сингресс. ISBN  1-932266-65-8 .
• Диффи, В.; Хеллман, Мэн (1977). «Исчерпывающий криптоанализ стандарта шифрования данных NBS». Компьютер . 10 : 74–84. дои : 10.1109/см.1977.217750 . S2CID   2412454 .
• Грэм, Роберт Дэвид (22 июня 2011 г.). «Взлом паролей, майнинг и графические процессоры» . erratasec.com . Проверено 17 августа 2011 г.
• Эллис, Клэр (март 2005 г.). «Исследование загадки» . Плюс журнал.
• Камерлинг, Эрик (12 ноября 2007 г.). «Elcomsoft представляет усовершенствованное средство восстановления пароля графического процессора (GPU)» . Симантек .
• Кингсли-Хьюз, Адриан (12 октября 2008 г.). «ElcomSoft использует графические процессоры NVIDIA для ускорения атаки методом перебора WPA/WPA2» . ЗДНет .
• Ландауэр, Л. (1961). «Необратимость и тепловыделение в вычислительном процессе» . Журнал исследований и разработок IBM . 5 (3): 183–191. дои : 10.1147/рд.53.0183 . Архивировано из оригинала 3 марта 2016 года.
• Паар, Кристоф; Пельцль, Ян; Пренил, Барт (2010). Понимание криптографии: Учебник для студентов и практиков . Спрингер. ISBN  978-3-642-04100-6 .
• Рейнард, Роберт (1997). Взломщик секретных кодов II: Справочник криптоаналитика . Джексонвилл, Флорида: Smith & Daniel Marketing. ISBN  1-889668-06-0 . Проверено 21 сентября 2008 г.
• Ристич, Иван (2010). Справочник по модбезопасности . Злющая утка. ISBN  978-1-907117-02-2 .
• Виега, Джон ; Мессье, Мэтт; Чандра, Правир (2002). Сетевая безопасность с OpenSSL . О'Рейли. ISBN  0-596-00270-Х . Проверено 25 ноября 2008 г.
• Винер, Майкл Дж. (1996). «Эффективный поиск ключей DES». Практическая криптография для сетевых сетей данных . В. Столлингс, редактор IEEE Computer Society Press.
• «Техническое предупреждение кибербезопасности TA08-137A: уязвимость генератора случайных чисел OpenSSL в Debian/Ubuntu» . Группа готовности к компьютерным чрезвычайным ситуациям США (CERT). 16 мая 2008 года. Архивировано из оригинала 16 сентября 2008 года . Проверено 10 августа 2008 г.
• «Как математики АНБ помогли выиграть Вторую мировую войну» . Агентство национальной безопасности . 15 января 2009 г. Архивировано из оригинала 7 марта 2009 г.

Внешние ссылки

• Конкурс по взлому DES-III, спонсируемый RSA
• Демонстрация устройства перебора, предназначенного для подбора пароля заблокированных iPhone под управлением iOS 10.3.3
• Как мы взломали шифры кодовой книги - эссе команды-победителя конкурса « Кодовая книга»