Полный перебор (или метод «грубой силы», ) — метод решения математических задач. Относится к классу . Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Любая задача из класса NP может быть решена полным перебором. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлено за полиномиальное время, в зависимости от количества всех возможных решений полный перебор может потребовать экспоненциального времени работы.
В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей. Криптографические атаки, основанные на методе полного перебора, являются самыми универсальными, но и самыми долгими.
Метод исчерпывания
Терминология В английском языке рассматриваемый в данной статье термин «brute-force» обычно относится к классу хакерских атак. При этом более общее понятие, математический метод исчерпывания всевозможных вариантов для нахождения решения задачи, соответствует термину «Proof by exhaustion».
Описание «Метод исчерпывания» включает в себя целый класс различных методов. Обычно постановка задачи подразумевает рассмотрение конечного числа состояний данной логической системы с целью выявления истинности логического утверждения посредством независимого анализа каждого состояния. Методика доказательства утверждения состоит из двух частей:
Доказательство возможности исчерпания всех состояний системы. Требуется показать, что любое конкретное состояние системы (например, значение доказываемого логического выражения) соответствует хотя бы одному из рассматриваемых кандидатов в решения. Проверка каждого варианта и доказательство того, что рассматриваемый вариант является или не является решением поставленной задачи.
Характерные задачи, решаемые методом полного перебора Хотя полный перебор в большинстве прикладных задач (особенно не связанных со взломом шифров) на практике не применяется, есть ряд исключений. В частности, когда полный перебор всё же оказывается оптимальным либо представляет собой начальный этап в разработке алгоритма, его использование оправдано. Примером оптимальности полного перебора является алгоритм оценки времени вычисления цепочечных произведений матриц, который не удаётся ускорить по сравнению с алгоритмом, основанным на методе «грубой силы». Этот алгоритм используется для решения классической задачи динамического программирования — определения приоритетов вычислений матричных произведений следующего вида: .
Пример использования полного перебора Исходная задача заключается в вычислении данной цепочки (матричного произведения) за наименьшее время. Можно реализовать тривиальный последовательный алгоритм, вычисляющий искомое произведение. Поскольку матричное произведение является ассоциативной операцией, можно вычислить цепочечное произведение, произвольно выбирая пару элементов цепочки и заменяя её результирующей матрицей . Если повторять описанную процедуру раз, то оставшаяся результирующая матрица и будет ответом: . Эта формула может быть проиллюстрирована следующим образом. Рассмотрим матричную цепочку: . Существуют следующие 5 способов вычислить соответствующее этой цепочке произведение :
Выбрав правильный порядок вычислений, можно добиться значительного ускорения вычислений. Чтобы убедиться в этом, рассмотрим простой пример цепочки из 3-х матриц. Положим, что их размеры равны соответственно . Стандартный алгоритм перемножения двух матриц размерами требует время вычисления, пропорциональное числу (число вычисляемых скалярных произведений). Следовательно, вычисляя цепочку в порядке , получаем скалярных произведений для вычисления , плюс дополнительно скалярных произведений, чтобы вычислить второе матричное произведение. Общее число скалярных произведений: 7500. При ином выборе порядка вычислений получаем плюс скалярных произведений, то есть 75000 скалярных произведений.
Таким образом, решение данной задачи может существенно сократить временные затраты на вычисление матричной цепочки. Это решение может быть получено полным перебором: необходимо рассмотреть все возможные последовательности вычислений и выбрать из них ту, которая при вычислении цепочки занимает наименьшее число скалярных произведений. Однако надо учитывать, что этот алгоритм сам по себе требует экспоненциальное время вычисления, так что для длинных матричных цепочек выигрыш от вычисления цепочки самым эффективным образом (оптимальная стратегия) может быть полностью потерян временем нахождения этой стратегии.
Связь с концепцией «разделяй и властвуй»
В теории алгоритмов известны несколько широко применимых общих концепций. Метод полного перебора является одной из них. Фактически, полным перебором возможно воспользоваться в тех случаях, когда мы имеем дело с дискретной детерминированной системой, состояния которой могут быть легко проанализированы.
Другим ярким примером фундаментальной концепции теории алгоритмов является принцип «разделяй и властвуй». Эта концепция применима, когда система поддается разделению на множество подсистем, структура которых аналогична структуре исходной системы. В таких случаях подсистемы также поддаются разделению, либо являются тривиальными. Для таких систем тривиальной является исходно поставленная задача. Таким образом, реализация концепции «разделяй и властвуй» имеет рекурсивный характер.
В свою очередь, рекурсия представляет собой разновидность полного перебора. Так, рекурсия применима лишь для дискретных систем. Однако это требование относится не к состояниям данной системы, а к её . Последовательное рассмотрение всех уровней дает исчерпывающее решение задачи, поставленной для всей дискретной системы.
По сравнению с другими примерами полного перебора, особенностью метода рекурсии является то, что конечное решение опирается не на одну-единственную тривиальную подсистему. В общем случае решение формируется на основании целого множества подсистем.
Для следующих примеров классических задач, решаемых методом «разделяй и властвуй», полный перебор является либо единственным известным методом решения, либо изначальной реализацией, которая в дальнейшем была оптимизирована: Поиск наибольшей подстроки; Цепочечное произведение матриц; Задача поиска ближайшего соседа; Обнаружение коллизий хеш-функций.
Атака методом «грубой силы»
В криптографии на полном переборе основывается криптографическая атака методом «грубой силы», или брутфорс () — взлом пароля путём перебора всех возможных вариантов ключа. Её особенностью является возможность применения против любого практически используемого шифра (об исключениях, то есть безопасности с точки зрения теории информации см. также шифроблокнот и Теоретико-информационная стойкость). Однако такая возможность существует лишь теоретически, зачастую требуя нереальные временные и ресурсные затраты. Если пространство решений слишком большое, то данный вид атаки может не дать результатов в течение нескольких лет или даже веков. Наиболее оправдано использование атаки методом «грубой силы» в тех случаях, когда не удается найти слабых мест в системе шифрования, подвергаемой атаке (либо в рассматриваемой системе шифрования слабых мест не существует). При обнаружении таких недостатков разрабатываются методики криптоанализа, основанные на их особенностях, что способствует упрощению взлома.
Устойчивость к brute-force атаке определяет используемый в криптосистеме ключ шифрования. Так, с увеличением длины ключа сложность взлома этим методом возрастает экспоненциально. В простейшем случае шифр длиной в N битов взламывается, в наихудшем случае - за время, пропорциональное 2N. Среднее время взлома в этом случае в два раза меньше и составляет 2N-1. Существуют способы повышения устойчивости шифра к «brute force», например запутывание (обфускация) шифруемых данных, что делает нетривиальным отличие зашифрованных данных от незашифрованных.
Криптографические атаки, основанные на методе «грубой силы», являются наиболее универсальными, но в то же время наиболее медленными. Используются в основном начинающими хакерами. Эффективны для несложных алгоритмов шифрования и ключей длиной до 64 бит. Для современных ключей длиной от 128 бит (иногда для ключа факторизируется большое число из 200 цифр), неэффективны. Любой пароль может быть подобран путём полного перебора. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлено за полиномиальное время, в зависимости от количества всех возможных решений атака может потребовать экспоненциального времени работы.
Распараллеливание вычислений Для увеличения скорости подбора ключа используется распараллеливание вычислений. Существует два вида распараллеливания:
построение алгоритма. Пусть алгоритм можно представить в виде цепочки простейших действий (операций). Пусть — количество процессоров, в которых запрограммирован порядок. Процессоры выполняют работу:
-ый процессор выполняет три одинаковые по времени операции:
получение данных от -го процессора выполнение операции передача данных -му процессору.
Эта операция может занять всего сотую долю секунды. Тогда соединённых параллельно и синхронно работающих процессоров работают со скоростью (так как всего три операции), где — скорость выполнения одной операции одним процессором.
разбивание на множества. Множество всех возможных ключей — разбивается на непересекающиеся подмножества. Система с процессорами перебирает ключи так, что, например, -ая машина осуществляет перебор ключей из подмножества . Система прекращает работу, если одна машина подобрала правильный ключ. Но если каждый процессор начнёт вычисление не с первого возможного ключа, время перебора может увеличиться, но алгоритм упростится. Среднее число подборов в этом случае составит , где — число элементов во множестве ключей, а — число процессоров.
Обратные атаки «грубой силой» При обратной атаке с использованием метода грубой силы один (обычно общий) пароль проверяется на несколько имён пользователей. В этом случае также применяется распараллеливание, но процессоры должны проверить, есть ли у другого пользователя такой пароль. В такой стратегии злоумышленник обычно не старается взломать аккаунт одного конкретного пользователя. Против обратных атак устанавливается политика паролей, которая запрещает использование одинаковых паролей.
Пример продолжительности подбора паролей В таблице представлено оценочное время полного перебора паролей в зависимости от их длины. Предполагается, что в пароле могут использоваться 36 различных символов (латинские буквы одного регистра + цифры), а скорость перебора составляет 100 000 паролей в секунду (класс атаки B, типичный для восстановления пароля из кэша Windows (.PWL файлов) на Pentium 100).
Кол-во знаковКол-во вариантовСтойкостьВремя перебора 1365 битменее секунды 2129610 битменее секунды 346 65615 битменее секунды 41 679 61621 бит17 секунд 560 466 17626 бит10 минут 62 176 782 33631 бит6 часов 778 364 164 09636 бит9 дней 82,821 109 9x101241 бит11 месяцев 91,015 599 5x101446 бит32 года 103,656 158 4x101552 бита1162 года 111,316 217 0x101758 бит41 823 года 124,738 381 3x101862 бита1 505 615 лет
Таким образом, пароли длиной до 8 символов включительно в общем случае не являются надёжными. Для современных компьютеров этот показатель гораздо выше. Так, 64-битный ключ (пароль) перебирается на современном компьютере примерно за 2 года и перебор легко может быть распределен между множеством компьютеров.
Пример продолжительности подбора паролей N 2
(С учетом значительного прогресса в вычислительной технике последних лет)
Используются цифры (0-9) большие и малые буквы (A-Z,a-z) латинского алфавита и специальные символы, 94 разных символа.