10-06-2023
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов[en]. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Любая задача из класса NP может быть решена полным перебором. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлена за полиномиальное время, в зависимости от количества всех возможных решений полный перебор может потребовать экспоненциального времени работы.
В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей. Криптографические атаки, основанные на методе полного перебора, являются самыми универсальными, но и самыми долгими.
Содержание |
В английском языке рассматриваемый в данной статье термин «brute-force» обычно относится к классу Хакерских атак. При этом более общее понятие, математический метод исчерпывания всевозможных вариантов для нахождения решения задачи, соответствует термину «Proof by exhaustion».
«Метод исчерпывания» включает в себя целый класс различных методов. Обычно постановка задачи подразумевает рассмотрение конечного числа состояний данной логической системы с целью выявления истинности логического утверждения посредством независимого анализа каждого состояния.[1] Методика доказательства утверждения состоит из двух частей:
Brute-force атака[en] — понятие из криптографии, вид криптоаналитической атаки. Основывается на методе поиска полным перебором. Особенностью данной атаки является возможность ее применения против любого практически используемого шифрования[2] (об исключениях, т. е. безопасности с точки зрения теории информации см. также en:Information-theoretically secure). Однако такая возможность существует лишь теоретически, зачастую требуя нереалистичные временные и ресурсные затраты. Наиболее оправдано использование атаки методом «грубой силы» в тех случаях, когда не удается найти слабых мест в системе шифрования, подвергаемой атаке (либо в рассматриваемой системе шифрования слабых мест не существует). При обнаружении таких недостатков разрабатываются методики криптографического анализа, основанные на их особенностях, что способствует упрощению взлома.
Устойчивость к brute-force атаке определяет используемый в криптосистеме ключ шифрования. Так, с увеличением длины ключа сложность взлома этим методом возрастает экспоненциально. В простейшем случае шифр длиной в N битов взламывается, в наихудшем случае, за время, пропорциональное 2N. Среднее время взлома в этом случае в два раза меньше и составляет 2N-1. Существуют способы повышения устойчивости шифра к «brute force», например запутывание обфускация шифруемых данных, что делаем нетривиальным отличие зашифрованных данных от незашифрованных.
Для ускорения перебора метод ветвей и границ использует отсев подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Для увеличения скорости подбора ключа используется распараллеливание вычислений. Существует два подхода к распараллеливанию:
Радужная таблица создается построением цепочек возможных паролей. Каждая цепочка начинается со случайного возможного пароля, затем подвергается действию хеш-функции и функции редукции. Данная функция преобразует результат хеш-функции в некоторый возможный пароль (например, если мы предполагаем, что пароль имеет длину 64 бита, то функцией редукции может быть взятие первых 64 бит хеша, побитовое сложение всех 64-битных блоков хеша и т. п.). Промежуточные пароли в цепочке отбрасываются и в таблицу записываются только первый и последний элементы цепочек. Создание таких таблиц требует больше времени, чем нужно для создания обычных таблиц поиска, но значительно меньше памяти (вплоть до сотен гигабайт, при объеме для обычных таблиц в N слов для радужных нужно всего порядка N2/3). При этом они требуют хоть и больше времени (по сравнению с обычными методами) на восстановление исходного пароля, но на практике более реализуемы (для построения обычной таблицы для 6-символьного пароля с байтовыми символами потребуется 2566 = 281 474 976 710 656 блоков памяти, в то время как для радужной — всего 2566·⅔ = 4 294 967 296 блоков).
Для восстановления пароля данное значение хеш-функции подвергается функции редукции и ищется в таблице. Если не было найдено совпадения, то снова применяется хеш-функция и функция редукции. Данная операция продолжается, пока не будет найдено совпадение. После нахождения совпадения цепочка, содержащая его, восстанавливается для нахождения отброшенного значения, которое и будет искомым паролем.
В итоге получается таблица, которая может с высокой вероятностью восстановить пароль за небольшое время.
В таблице представлено оценочное время полного перебора паролей в зависимости от их длины. Предполагается, что в пароле могут использоваться 36 различных символов (латинские буквы одного регистра + цифры), а скорость перебора составляет 100 000 паролей в секунду.[3]
Кол-во знаков | Кол-во вариантов | Стойкость | Время перебора |
---|---|---|---|
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 лет |
Таким образом, пароли длиной до 7 символов включительно в общем случае не являются надежными.
Bruteforce.