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