Полный перебор

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов[en]. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

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

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

Метод исчерпывания[править | править исходный текст]

Терминология[править | править исходный текст]

В английском языке рассматриваемый в данной статье термин «brute-force» обычно относится к классу Хакерских атак. При этом более общее понятие, математический метод исчерпывания всевозможных вариантов для нахождения решения задачи, соответствует термину «Proof by exhaustion».

Описание[править | править исходный текст]

«Метод исчерпывания» включает в себя целый класс различных методов. Обычно постановка задачи подразумевает рассмотрение конечного числа состояний данной логической системы с целью выявления истинности логического утверждения посредством независимого анализа каждого состояния[1]. Методика доказательства утверждения состоит из двух частей:

  1. Доказательство возможности исчерпания всех состояний системы. Требуется показать, что любое конкретное состояние системы (например, значение доказываемого логического выражения) соответствует хотя бы одному из рассматриваемых кандидатов в решения.
  2. Поверка каждого варианта и доказательство того, что рассматриваемый вариант является или не является решением поставленной задачи.

Характерные задачи, решаемые методом полного перебора[править | править исходный текст]

Хотя метод brute force в большинстве прикладных задач (особенно не связанных со взломом) на практике не применяется, есть ряд исключений. В частности, когда brute force всё же оказывается оптимальным, либо представляет собой начальный этап в разработке алгоритма, его использование оправдано. Примером оптимальности brute force является алгоритм оценки времени вычисления цепочечных произведений матриц, который не удаётся ускорить по сравнению с алгоритмом, основанным на методе «грубой силы»[2]. Этот алгоритм используется для решения классической задачи динамического программирования — определения приоритетов вычислений матричных произведений следующего вида: ~A_1 A_2 A_3 ... A_n.

Пример использования brute force[править | править исходный текст]

Исходная задача заключается в вычислении данной цепочки (матричного произведения) за наименьшее время. Можно реализовать тривиальный последовательный алгоритм, вычисляющий искомое произведение. Поскольку матричное произведение является ассоциативной операцией, можно вычислить цепочечное произведение, произвольно выбирая пару элементов цепочки ~(A_i A_{i+1}), i=1..n-1 и заменяя её результирующей матрицей ~A^1_i \colon A^1_i = (A_i A_{i+1}). Если повторять описанную процедуру n-1 раз, то оставшаяся результирующая матрица ~A^{n-1}_k и будет ответом: ~A^{n-1}_k = (A^{n-2}_k A^{n-2}_{k+1}) = ... = A_1 A_2 A_3 ... A_n, k=1..n-1. Эта формула может быть проиллюстрирована следующим образом. Рассмотрим матричную цепочку: ~\left\langle A_1, A_2, A_3, A_4 \right\rangle. Существуют следующие 5 способов вычислить соответствующее этой цепочке произведение ~A_1 A_2 A_3 A_4:

~{\color{Violet}(}A_1 {\color{BurntOrange}(}A_2 {\color{BrickRed}(}A_3 A_4{\color{BrickRed})}{\color{BurntOrange})}{\color{Violet})},
~{\color{Violet}(}A_1 {\color{BurntOrange}(}{\color{BrickRed}(}A_2 A_3{\color{BrickRed})} A_4{\color{BurntOrange})}{\color{Violet})},
~{\color{Violet}(}{\color{BrickRed}(}A_1 A_2{\color{BrickRed})} {\color{BurntOrange}(}A_3 A_4{\color{BurntOrange})}{\color{Violet})},
~{\color{Violet}(}{\color{BurntOrange}(}A_1 {\color{BrickRed}(}A_2 A_3{\color{BrickRed})}{\color{BurntOrange})} A_4{\color{Violet})},
~{\color{Violet}(}{\color{BurntOrange}(}{\color{BrickRed}(}A_1 A_2{\color{BrickRed})} A_3{\color{BurntOrange})} A_4{\color{Violet})}.

Выбрав правильный порядок вычислений, можно добиться значительного ускорения вычислений. Чтобы убедиться в этом, рассмотрим простой пример цепочки из 3-х матриц. Положим, что их размеры равны соответственно 10 \times 100, 100 \times 5, 5 \times 50 . Стандартный алгоритм перемножения двух матриц размерами p \times q, q \times r требует время вычисления, пропорциональное числу pqr (число вычисляемых скалярных произведений)[3]. Следовательно, вычисляя цепочку в порядке ((A_1 A_2) A_3), получаем 10 \cdot 100 \cdot 5 = 5000 скалярных произведений для вычисления (A_1 A_2), плюс дополнительно 10 \cdot 5 \cdot 50 = 2500 скалярных произведений, чтобы вычислить второе матричное произведение. Общее число скалярных произведений: 7500. При ином выборе порядка вычислений получаем 100 \cdot 5 \cdot 50 = 25000 плюс 10\cdot 100 \cdot 50 = 50000 скалярных произведений, то есть 75000 скалярных произведений[3].

Таким образом, решение данной задачи может существенно сократить временные затраты на вычисление матричной цепочки. Это решение может быть получено полным перебором: необходимо рассмотреть все возможные последовательности вычислений и выбрать из них ту, которая при вычислении цепочки занимает наименьшее число скалярных произведений. Однако надо учитывать, что этот алгоритм сам по себе требует экспоненциальное время вычисления[2], так что для длинных матричных цепочек выигрыш от вычисления цепочки самым эффективным образом (оптимальная стратегия) может быть полностью потерян временем нахождения этой стратегии[4].

Связь с концепцией «разделяй и властвуй»[править | править исходный текст]

Алгоритм быстрой сортировки — основанный на парадигме «разделяй и властвуй».

В теории алгоритмов известны несколько широко применимых общих концепций. Метод полного перебора является одной из них. Фактически, полным перебором возможно воспользоваться в тех случаях, когда мы имеем дело с дискретной детерминированной системой, состояния которой могут быть легко проанализированы[5].

Другим ярким примером фундаментальной концепции теории алгоритмов является принцип «разделяй и властвуй». Эта концепция применима, когда система поддается разделению на множество подсистем, структура которых аналогична структуре исходной системы[6]. В таких случаях подсистемы также поддаются разделению, либо являются тривиальными[6]. Для таких систем тривиальной является исходно поставленная задача. Таким образом, реализация концепции «разделяй и властвуй» имеет рекурсивный характер.

В свою очередь, рекурсия представляет собой разновидность полного перебора. Так, рекурсия применима лишь для дискретных систем[en][7]. Однако это требование относится не к состояниям данной системы, а к ее субструктуре[en]. Последовательное рассмотрение всех уровней дает исчерпывающее решение задачи, поставленной для всей дискретной системы.

По сравнению с другими примерами полного перебора, особенностью метода рекурсии является то, что конечное решение опирается не на одну-единственную тривиальную подсистему. В общем случае решение формируется на основании целого множества подсистем.

Для следующих примеров классических задач, решаемых методом «разделяй и властвуй», полный перебор является либо единственным известным методом решения, либо изначальной реализацией, которая в дальнейшем была оптимизирована:

Атака методом «грубой силы»[править | править исходный текст]

Компьютер компании EFF для взламывания шифра DES. Имея в распоряжении 1 856 микросхем, взламывал ключ DES всего за несколько суток. На фотографии видна двусторонняя плата «DES Cracker», содержащая 64 микросхемы «Deep Crack». Цена всего вычислительного комплекса — $250 000

В криптографии на полном переборе основывается криптографическая атака методом «грубой силы»[en]. Её особенностью является возможность применения против любого практически используемого шифра[12] (об исключениях, то есть безопасности с точки зрения теории информации см. также шифроблокнот и en:Information-theoretically secure). Однако такая возможность существует лишь теоретически, зачастую требуя нереалистичные временные и ресурсные затраты. Наиболее оправдано использование атаки методом «грубой силы» в тех случаях, когда не удается найти слабых мест в системе шифрования, подвергаемой атаке (либо в рассматриваемой системе шифрования слабых мест не существует). При обнаружении таких недостатков разрабатываются методики криптоанализа, основанные на их особенностях, что способствует упрощению взлома.

Устойчивость к brute-force атаке определяет используемый в криптосистеме ключ шифрования. Так, с увеличением длины ключа сложность взлома этим методом возрастает экспоненциально. В простейшем случае шифр длиной в N битов взламывается, в наихудшем случае, за время, пропорциональное 2N[13][14]. Среднее время взлома в этом случае в два раза меньше и составляет 2N-1. Существуют способы повышения устойчивости шифра к «brute force», например запутывание (обфускация) шифруемых данных, что делает нетривиальным отличие зашифрованных данных от незашифрованных.

Пример продолжительности подбора паролей[править | править исходный текст]

В таблице представлено оценочное время полного перебора паролей в зависимости от их длины. Предполагается, что в пароле могут использоваться 36 различных символов (латинские буквы одного регистра + цифры), а скорость перебора составляет 100 000 паролей в секунду (класс атаки B, типичный для восстановления пароля из Кэша Windows (.PWL файлов) на Pentium 100)[15].

Кол-во знаков Кол-во вариантов Стойкость Время перебора
1 36 5 бит менее секунды
2 1296 10 бит менее секунды
3 46 656 15 бит менее секунды
4 1 679 616 21 бит 17 секунд
5 60 466 176 26 бит 10 минут
6 2 176 782 336 31 бит 6 часов
7 78 364 164 096 36 бит 9 дней
8 2,821 109 9x1012 41 бит 11 месяцев
9 1,015 599 5x1014 46 бит 32 года
10 3,656 158 4x1015 52 бита 1 162 года
11 1,316 217 0x1017 58 бит 41 823 года
12 4,738 381 3x1018 62 бита 1 505 615 лет

Таким образом, пароли длиной до 8 символов включительно в общем случае не являются надежными.

Средства проведения brute force атаки[править | править исходный текст]

Nvidia Tesla C2075 обладает 448 ядрами архитектуры CUDA, 6ГБ оперативной памяти типа GDDR5 и имеет пиковую производительность, равную 1030 Гфлопс при вычислениях с одинарной точностью.[16] Такие параметры делают эту систему подходящей для сложных вычислений, требуемых в brute force атаке.

Современные персональные компьютеры позволяют взламывать пароли полным перебором вариантов с эффективностью, проиллюстрированной в таблице выше. Однако, при оптимизации brute force, основанной на параллельных вычислениях, эффективность атаки можно существенно повысить[17]. При этом может потребоваться использование компьютера, адаптированного к многопоточным вычислениям. В последние годы широкое распространение получили вычислительные решения, использующие GPU, такие как Nvidia Tesla. С момента создания компанией Nvidia архитектуры CUDA в 2007 году, на базе которой построена система Tesla, появилось множество решений (см., например, Cryptohaze Multiforcer, Pyrit), позволяющих проводить ускоренный подбор ключей благодаря использованию таких технологий, как CUDA, ATI Stream Technology, OpenCL.

Устойчивость к атаке полного перебора[править | править исходный текст]

В процессе улучшения системы информационной безопасности по отношению к атаке полным перебором можно выделить два основных направления:

  1. повышение требований к ключам доступа от защищаемой информации;
  2. повышение надежности всех узлов системы безопасности.

Таким образом, невозможно достичь высокого уровня защиты, улучшая только один из этих параметров.[18]. Существуют примеры того, как система аутентификации, основанная на оптимальной сложности паролей, оказывалась уязвимой к копированию базы данных на локальный компьютер злоумышленника, после чего подвергалась brute force атаке с применением локальных оптимизаций и вычислительных средств, недоступных при удаленном криптоанализе[19]. Такое положение дел привело к тому, что некоторые эксперты по компьютерной безопасности начали рекомендовать более критически относится к таким стандартным инструкциям, призванным обеспечить надежную защиту, как использование максимально длинных паролей[20]. Ниже приведен список некоторых применяемых на практике методов[21][22][23] повышения надежности криптосистемы по отношению к brute force атаке:

Методы оптимизации полного перебора[править | править исходный текст]

Метод ветвей и границ[править | править исходный текст]

Для ускорения перебора метод ветвей и границ использует отсев подмножеств допустимых решений, заведомо не содержащих оптимальных решений[24].

Распараллеливание вычислений[править | править исходный текст]

Одним из методов увеличения скорости подбора ключа является распараллеливание вычислений. Существует два подхода к распараллеливанию[25]:

  • Первый подход — построение конвейера[25]. Пусть алгоритм соотношения E_k\ (x) = y можно представить в виде цепочки простейших действий (операций):  {O_1\ ,O_2,...,O_N} . Возьмём  N\ процессоров  {A_1\ ,A_2,...,A_N} , зададим их порядок и положим, что  i\  — ый процессор выполняет три одинаковые по времени операции:
    1. приём данных от  (i - 1)\  — го процессора;
    2. выполнение операции  O_i\ ;
    3. передача данных следующему  (i + 1)\ -му процессору.
    Тогда конвейер из  N\ последовательно соединённых, параллельно и синхронно работающих процессоров работает со скоростью  v/3\ , где  v\  — скорость выполнения одной операции одним процессором.
  • Второй подход состоит в том, что множество  K\ всех возможных ключей разбивается на непересекающиеся подмножества  {K_1\, K_2, ... , K_N} [25]. Система из  Q\ машин перебирает ключи так, что  i\  — ая машина осуществляет перебор ключей из множества  K_i\ , i = 1 .. Q . Система прекращает работу, если одна из машин нашла ключ. Самое трудное — это разделение ключевого множества. Но если каждый процессор начнёт вычисление с какого-то произвольного ключа, то время нахождения увеличится, а схема значительно упростится. Среднее число шагов в этом случае составляет  |K|/N\ , где  |K|\  — число элементов во множестве ключей, а  N\  — число процессоров.

Радужные таблицы[править | править исходный текст]

Предпосылки к появлению[править | править исходный текст]

Компьютерные системы, которые используют пароли для аутентификации, должны каким-то образом определять правильность введенного пароля. Тривиальное решение данной проблемы — хранить список всех допустимых паролей для каждого пользователя, но такой подход не является безопасным. Одним из более предпочтительных подходов является криптографической хеш-функции от парольной фразы. Радужная таблица представляет собой оптимизацию этого метода[26]. Основным ее преимуществом является значительное уменьшение количества используемой памяти[27][26].

Использование[править | править исходный текст]

Радужная таблица создается построением цепочек возможных паролей. Каждая цепочка начинается со случайного возможного пароля, затем подвергается действию хеш-функции и функции редукции. Данная функция преобразует результат хеш-функции в некоторый возможный пароль (например, если мы предполагаем, что пароль имеет длину 64 бита, то функцией редукции может быть взятие первых 64 бит хеша, побитовое сложение всех 64-битных блоков хеша и т. п.). Промежуточные пароли в цепочке отбрасываются и в таблицу записываются только первый и последний элементы цепочек. Создание таких таблиц требует больше времени, чем нужно для создания обычных таблиц поиска, но значительно меньше памяти (вплоть до сотен гигабайт, при объеме для обычных таблиц в N слов для радужных нужно всего порядка N2/3)[27]. При этом они требуют хоть и больше времени (по сравнению с обычными методами) на восстановление исходного пароля, но на практике более реализуемы (для построения обычной таблицы для 6-символьного пароля с байтовыми символами потребуется 2566 = 281 474 976 710 656 блоков памяти, в то время как для радужной — всего 2566·⅔ = 4 294 967 296 блоков).

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

В итоге получается таблица, которая может с высокой вероятностью восстановить пароль за небольшое время[28].

Инциденты[править | править исходный текст]

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

Атака «Энигмы»[править | править исходный текст]

Функционирующая восстановленная версия «бомбы» в музее Блетчли-парк. Каждый из барабанных роторов имитирует работу соответствующего ротора Энигмы. Всего используется 36 эквивалентных узлов Энигмы. В правой части средней полки находятся три идентификационных ротора. Восстановление «бомбы» стало возможным в 2008 году благодаря трудам Джона Харпера[en][29], а церемонию первого запуска возглавил покровитель Британского компьютерного общества[en], Эдвард, герцог Кентский.

Изобретенная в 1918 году шифровальная машина, названная «Энигма», широко использовалось немецким военно-морским флотом начиная с 1929 года. В течение дальнейших нескольких лет система модифицировалась, а с 1930 года активно использовалась немецкой армией и правительством в процессе Второй мировой войны[30].

Первые перехваты сообщений, зашифрованных с кодом Энигмы относятся к 1926 году. Однако прочитать сообщения долгое время не могли. На протяжении всей Второй мировой шло противостояние между польскими и германскими криптографами. Поляки, получая очередной результат по взлому немецкой криптосистемы, сталкивались с новыми трудностями, которые привносили германские инженеры, постоянно модернизирующие систему «Энигма». Летом 1939 года, когда неизбежность вторжения в Польшу стала очевидна, бюро передало результаты своей работы английской и французской разведкам[31].

Дальнейшая работа по взлому была организована в Блетчли-парке. Основным инструментом криптоаналитиков стала дешифровальная машина «Бомба». Её прототип был создан польскими математиками накануне Второй мировой войны для министерства обороны Польши. На основе этой разработки и при непосредственной поддержке её создателей в Англии был сконструирован более «продвинутый» агрегат.

Теоретическую часть работы выполнил Алан Матисон Тьюринг[32]. Его работы по криптографическому анализу алгоритма, реализованного в шифровальной машине «Энигма», основывался на более раннем криптоанализе предыдущих версий этой машины, которые были выполнены в 1938 году польским криптоаналитиком Марианом Реевским. Принцип работы разработанного Тьюрингом дешифратора состоял в переборе возможных вариантов ключа шифра и попыток расшифровки текста, если была известна структура дешифруемого сообщения или часть открытого текста[33].

С современной точки зрения шифр «Энигмы» был не очень надёжным, но только сочетание этого фактора с наличием множества перехваченных сообщений, кодовых книг, донесений разведки, результатов усилий военных и даже террористических атак позволило «вскрыть» шифр[31].

После войны Черчилль, из соображений безопасности, приказал разрушить эти машины.

Уязвимость протокола WPS[править | править исходный текст]

В 2007 году группа компаний, входящих в организацию Wi-Fi Alliance, начали продажу беспроводного оборудования для домашних сетей с поддержкой нового стандарта Wi-Fi Protected Setup. Среди производителей беспроводных маршрутизаторов, поддерживающих данную технологию, были такие крупные компании, как Cisco/Linksys, Netgear, Belkin и D-Link. Стандарт WPS был призван существенно упростить процесс настройки беспроводной сети и ее использования для людей, не обладающих широкими знаниями в области сетевой безопасности. Однако, к концу 2011 года были опубликованы сведения о серьезных уязвимостях в WPS, которые позволяли злоумышленнику подобрать PIN-код[34] беспроводной сети всего за несколько часов, обладая вычислительными ресурсами обыкновенного персонального компьютера[35]. В данный момент Координационный центр CERT не рекомендует производителям выпускать новое оборудование, поддерживающее данную технологию.[36]

Массовый взлом домашних сетей посредством WASP[править | править исходный текст]

В 2010 году на конференции DEFCON18 был представлен беспилотный летательный аппарат, предназначенный для массового сбора статистики по домашним Wi-Fi сетям. Аппарат, оснащенный компактным бортовым компьютером под управлением BackTrack Linux, получил название WASP (Wireless Aerial Surveillance Platform)[37]. Одной из его функций называлась возможность автоматического взлома паролей беспроводных сетей посредством brute force[38][39]. В 2011 году на конференциях DEFCON19 и Black Hat авторы WASP представили[40] улучшенную версию беспилотника. В частности, это дало возможность использовать вычислительные ресурсы удаленного компьютера при подборе паролей[41].

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Ried & Knipping, 2010, p. 133
  2. 1 2 3 Cormen, 2001, p. 372
  3. 1 2 Cormen, 2001, Произведение матричных цепочек, pp. 370-372
  4. Cormen, 2001, p. 377
  5. Cormen, 2001, Раздел 4. Метод «разделяй и властвуй», pp. 65-67
  6. 1 2 Cormen, 2001, p. 65
  7. Cormen, 2001, p. 66
  8. Knuth, 1972, Избранные исследовательские задачи в комбинаторике
  9. Cormen, 2001, Проблема LCS: нахождение наибольшей общей подпоследовательности, p. 392
  10. Cormen, 2001, Поиск ближайшей пары точек, p. 1039
  11. SchneierOnSecurity, Коллизии в алгоритме хеширования SHA-1
  12. Paar, 2010, p. 7
  13. Cormen, 2001
  14. Knuth, 1972
  15. www.lockdown.co.uk, Скорость восстановления паролей
  16. Tesla, Параметры Tesla C2075 на сайте производителя
  17. Ku, Проведение brute-force атаки посредством видеокарт Nvidia и AMD
  18. Pothier, 2010, Смена пароля может быть бесполезным действием на пути к обеспечению информационной безопасности
  19. Weiss, "Сильный" пароль это относительное понятие
  20. Cormac, 2009, Рациональный отказ от безопасности
  21. Gil, Что такое взлом методом Brute Force?
  22. 1 2 McGlinn, Хеширование паролей в PHP
  23. 1 2 Zernov, Защита от bruteforce средствами iptables
  24. Land, 1960, Автоматический метод решения задач дискретного программирования
  25. 1 2 3 Воеводин, 2002, Параллельные вычисления
  26. 1 2 Oechslin, 2003, p. 1
  27. 1 2 Hellman, 1980, p. 401
  28. Hellman, 1980, p. 405
  29. Harper, Проект восстановления «Британской бомбы»
  30. larin-shankin, 2007, Вторая мировая война в эфире: некоторые аспекты операции «Ультра»
  31. 1 2 chernyak, 2003, Тайны проекта Ultra
  32. Ellsbury, «Энигма» и «Бомба»
  33. groteck.ru, Машина Turing Bombe
  34. Liebowitz1, Домашние беспроводные маршрутизаторы подвержены атаке brute-force
  35. Ray, 2009, Недостаточная безопасность протокола WPS
  36. CERT, Протокол WPS подвержен brute-force
  37. WASP, Официальный сайт проекта WASP
  38. Greenberg, Летающий беспилотник взламывает пароли от беспроводных сетей
  39. Humphries, WASP: летающий беспилотник-разведчик, взламывающий сети Wi-Fi
  40. Tassey, Анонс презентации WASP на сайте DEFCON
  41. Liebowitz2, Летающий беспилотник ворует пароли от сетей Wi-Fi и взламывает сотовые телефоны

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]