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

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

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

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

Метод исчерпыванияПравить

ТерминологияПравить

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

ОписаниеПравить

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

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

См. также: Теория доказательств и Кризис оснований математики

Характерные задачи, решаемые методом полного перебораПравить

Хотя полный перебор в большинстве прикладных задач (особенно не связанных со взломом шифров) на практике не применяется, есть ряд исключений. В частности, когда полный перебор всё же оказывается оптимальным либо представляет собой начальный этап в разработке алгоритма, его использование оправдано. Примером оптимальности полного перебора является алгоритм оценки времени вычисления цепочечных произведений матриц, который не удаётся ускорить по сравнению с алгоритмом, основанным на методе «грубой силы». Этот алгоритм используется для решения классической задачи динамического программирования — определения приоритетов вычислений матричных произведений следующего вида: $A_1{A}_2{A}_3\cdots <!--\; \cdots \; -->A_n$$A_{1}A_{2}A_{3}\cdots A_{n}$ .

Пример использования полного перебораПравить

Исходная задача заключается в вычислении данной цепочки (матричного произведения) за наименьшее время. Можно реализовать тривиальный последовательный алгоритм, вычисляющий искомое произведение. Поскольку матричное произведение является ассоциативной операцией, можно вычислить цепочечное произведение, произвольно выбирая пару элементов цепочки $(A_i{A}_{i+1}),i=\mathrm{1..}n-<!--\; -\; -->1$$(A_{i}A_{i+1}),i=1..n-1$  и заменяя её результирующей матрицей $A_i^1:<!--\; :\; -->A_i^1=(A_i{A}_{i+1})$$A_{i}^{1}\colon A_{i}^{1}=(A_{i}A_{i+1})$ . Если повторять описанную процедуру $n-<!--\; -\; -->1$$n-1$  раз, то оставшаяся результирующая матрица $A_k^{n-<!--\; -\; -->1}$$A_{k}^{n-1}$  и будет ответом: $A_k^{n-<!--\; -\; -->1}=(A_k^{n-<!--\; -\; -->2}{A}_{k+1}^{n-<!--\; -\; -->2})=\dots <!--\; \dots \; -->=A_1{A}_2{A}_3\cdots <!--\; \cdots \; -->A_n,k=\mathrm{1..}n-<!--\; -\; -->1$$A_{k}^{n-1}=(A_{k}^{n-2}A_{k+1}^{n-2})=\ldots =A_{1}A_{2}A_{3}\cdots A_{n},k=1..n-1$ . Эта формула может быть проиллюстрирована следующим образом. Рассмотрим матричную цепочку: $⟨A_1,A_2,A_3,A_4⟩$$\left\langle A_{1},A_{2},A_{3},A_{4}\right\rangle$ . Существуют следующие 5 способов вычислить соответствующее этой цепочке произведение $A_1{A}_2{A}_3{A}_4$$A_{1}A_{2}A_{3}A_{4}$ :

$(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})},$ 

$(A_1((A_2{A}_3)A_4)),$${\color {Violet}(}A_{1}{\color {BurntOrange}(}{\color {BrickRed}(}A_{2}A_{3}{\color {BrickRed})}A_{4}{\color {BurntOrange})}{\color {Violet})},$ 

$((A_1{A}_2)(A_3{A}_4)),$${\color {Violet}(}{\color {BrickRed}(}A_{1}A_{2}{\color {BrickRed})}{\color {BurntOrange}(}A_{3}A_{4}{\color {BurntOrange})}{\color {Violet})},$ 

$((A_1(A_2{A}_3))A_4),$${\color {Violet}(}{\color {BurntOrange}(}A_{1}{\color {BrickRed}(}A_{2}A_{3}{\color {BrickRed})}{\color {BurntOrange})}A_{4}{\color {Violet})},$ 

$(((A_1{A}_2)A_3)A_4).$${\color {Violet}(}{\color {BurntOrange}(}{\color {BrickRed}(}A_{1}A_{2}{\color {BrickRed})}A_{3}{\color {BurntOrange})}A_{4}{\color {Violet})}.$ 

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

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

Связь с концепцией «разделяй и властвуй»Править

 

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

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

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

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

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

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

• Поиск наибольшей подстроки
• Цепочечное произведение матриц
• Задача поиска ближайшего соседа
• Обнаружение коллизий хеш-функций

Атака методом «грубой силы»Править

 

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

В криптографии на полном переборе основывается криптографическая атака методом «грубой силы», или брутфорс (англ. Brute-force attack) — взлом пароля путём перебора всех возможных вариантов ключа. Её особенностью является возможность применения против любого практически используемого шифра (об исключениях, то есть безопасности с точки зрения теории информации см. также шифроблокнот и Теоретико-информационная стойкость). Однако такая возможность существует лишь теоретически, зачастую требуя нереальные временные и ресурсные затраты. Если пространство решений слишком большое, то данный вид атаки может не дать результатов в течение нескольких лет или даже веков. Наиболее оправдано использование атаки методом «грубой силы» в тех случаях, когда не удается найти слабых мест в системе шифрования, подвергаемой атаке (либо в рассматриваемой системе шифрования слабых мест не существует). При обнаружении таких недостатков разрабатываются методики криптоанализа, основанные на их особенностях, что способствует упрощению взлома.

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

Криптографические атаки, основанные на методе «грубой силы», являются наиболее универсальными, но в то же время наиболее медленными. Используются в основном начинающими хакерами. Эффективны для несложных алгоритмов шифрования и ключей длиной до 64 бит. Для современных ключей длиной от 128 бит (иногда для ключа факторизируется большое число из 200 цифр), неэффективны. Любой пароль может быть подобран путём полного перебора. При этом, даже если вычисление целевой функции от каждого конкретного возможного решения задачи может быть осуществлено за полиномиальное время, в зависимости от количества всех возможных решений атака может потребовать экспоненциального времени работы.

Распараллеливание вычисленийПравить

Для увеличения скорости подбора ключа используется распараллеливание вычислений. Существует два вида распараллеливания:

• построение алгоритма. Пусть алгоритм можно представить в виде цепочки простейших действий (операций). Пусть $N$$N$  — количество процессоров, в которых запрограммирован порядок. Процессоры выполняют работу:

$i$$i$  -ый процессор выполняет три одинаковые по времени операции:

1. получение данных от $(i-<!--\; -\; -->1)$$(i-1)$  -го процессора
2. выполнение операции
3. передача данных $(i+1)$$(i+1)$  -ому процессору.

Эта операция может занять всего сотую долю секунды. Тогда $N$$N$  соединённых параллельно и синхронно работающих процессоров работают со скоростью $v/3$$v/3$  (так как всего три операции), где $v$$v$  — скорость выполнения одной операции одним процессором.

• разбивание на множества. Множество всех возможных ключей — $K$$K$  разбивается на непересекающиеся подмножества. Система с $Q$$Q$  процессорами перебирает ключи так, что, например, $i$$i$  -ая машина осуществляет перебор ключей из подмножества $K_i,i=\mathrm{1...}Q$$K_{i},i=1...Q$ . Система прекращает работу, если одна машина подобрала правильный ключ. Но если каждый процессор начнёт вычисление не с первого возможного ключа, время перебора может увеличиться, но алгоритм упростится. Среднее число подборов в этом случае составит $|K|/Q$$|K|/Q$ , где $K$$K$  — число элементов во множестве ключей, а $Q$$Q$  — число процессоров.

Обратные атаки «грубой силой»Править

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

Пример продолжительности подбора паролейПравить

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

Кол-во знаков	Кол-во вариантов	Стойкость	Время перебора
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 символов включительно в общем случае не являются надежными. Для современных компьютеров этот показатель гораздо выше. Так, 64-битный ключ (пароль) перебирается на современном компьютере примерно за 2 года и перебор легко может быть распределен между множеством компьютеров.

Средства проведения атакиПравить

 

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

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

Устойчивость к атаке полного перебораПравить

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

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

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

• Защита базы данных от копирования.
• Хеширование паролей на веб-сервере.
• Применение корректно настроенного межсетевого экрана, например, iptables.
• Другие средства, препятствующие быстрой проверке корректности ключа, например, Captcha, а также запрет или тайм-аут аутентификации пользователя.

Методы оптимизации полного перебораПравить

Метод ветвей и границПравить

Основная статья: Метод ветвей и границ

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

Распараллеливание вычисленийПравить

Основная статья: Параллельные вычисления

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

• Первый подход — построение конвейера. Пусть алгоритм соотношения $E_k(x)=y$$E_{k}\ (x)=y$  можно представить в виде цепочки простейших действий (операций): $O_1,O_2,...,O_N$${O_{1}\ ,O_{2},...,O_{N}}$ . Возьмём $N$$N\$  процессоров $A_1,A_2,...,A_N$${A_{1}\ ,A_{2},...,A_{N}}$ , зададим их порядок и положим, что $i$$i\$  — ый процессор выполняет три одинаковые по времени операции:
  1. приём данных от $(i-<!--\; -\; -->1)$$(i-1)\$  — го процессора;
  2. выполнение операции $O_i$$O_{i}\$ ;
  3. передача данных следующему $(i+1)$$(i+1)\$  -му процессору.

  Тогда конвейер из $N$$N\$  последовательно соединённых, параллельно и синхронно работающих процессоров работает со скоростью $v/3$$v/3\$  , где $v$$v\$  — скорость выполнения одной операции одним процессором.

• Второй подход состоит в том, что множество $K$$K\$  всех возможных ключей разбивается на непересекающиеся подмножества $K_1{K}_2,...,K_N$${K_{1}\,K_{2},...,K_{N}}$ . Система из $Q$$Q\$  машин перебирает ключи так, что $i$$i\$  — ая машина осуществляет перебор ключей из множества $K_i,i=\mathrm{1..}Q$$K_{i}\ ,i=1..Q$ . Система прекращает работу, если одна из машин нашла ключ. Самое трудное — это разделение ключевого множества. Но если каждый процессор начнёт вычисление с какого-то произвольного ключа, то время нахождения увеличится, а схема значительно упростится. Среднее число шагов в этом случае составляет $|K|/N$$|K|/N\$ , где $|K|$$|K|\$  — число элементов во множестве ключей, а $N$$N\$  — число процессоров.

Радужные таблицыПравить

Основная статья: Радужная таблица

Предпосылки к появлениюПравить

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

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

См. также: Space-time tradeoff

ИспользованиеПравить

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

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

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

ИнцидентыПравить

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

Атака «Энигмы»Править

 

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

Основные статьи: Криптоанализ «Энигмы» и Turing Bombe

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

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

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

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

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

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

Уязвимость протокола WPSПравить

Основная статья: Wi-Fi Protected Setup

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

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

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

В 2010 году на конференции DEFCON18 был представлен беспилотный летательный аппарат WASP, предназначенный для массового сбора статистики по домашним Wi-Fi сетям. БПЛА оснащён компактным бортовым компьютером под управлением BackTrack Linux, Одной из его функций называлась возможность автоматического взлома паролей беспроводных сетей посредством brute force.

См. такжеПравить

• Перебор делителей
• Метод ветвей и границ
• Комбинаторный поиск

ЛитератураПравить

• Reid, D. A. et al.,. Proof in Mathematics Education: Research, Learning, and Teaching. — John Wiley & SSense Publishersons, 2010. — P. 266. — ISBN 978-9460912443.
• Paar, Christof et al.,. Understanding Cryptography: A Textbook for Students and Practitioners. — Springer, 2010. — P. 1292. — ISBN 3-642-04100-0.
• Thomas H. Cormen et al.,. Introduction to Algorithms. — MIT Press, 2001. — P. 1292. — ISBN 978-0-262-03384-8.
• V. Chvátal^[en] et al.,. Selected combinatorial research problems. — Technical Report STAN-CS-72-292. — Computer Science Department, Stanford University, 1972.
• Шнайер, Брюс. Liars and Outliers^[en]: Enabling the Trust that Society Needs to Thrive. — John Wiley & Sons, 2012. — ISBN 978-1-118-14330-8.
• Воеводин В. В. и др.,. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. — P. 608. — ISBN 5-94157-160-7.
• Land, A. H. et al.,. An automatic method of solving discrete programming problems (англ.) // Econometrica : журнал. — 1960. — Vol. 28, no. 3. — P. 497—520. — doi:10.2307/1910129.
• Hellman, M. E.. A cryptanalytic time-memory trade off (англ.) // IEEE Transactions on Information Theory : журнал. — IEEE, IT-26:401–406, 1980. — Iss. Lecture Notes in Computer Science.
• Oechslin, Philippe. Making a Faster Cryptanalytical Time-Memory Trade-Off (англ.) // Advances in Cryptology: Proceedings of CRYPTO : журнал. — 23rd Annual Международная конференция по криптологии^[en], Санта-Барбара (Калифорния), США: Springer, 2003. — Iss. Lecture Notes in Computer Science. — ISBN 3-540-40674-3. Архивировано 26 сентября 2007 года.
• Ларин, Д. А., к. т. н. и др.,. Вторая мировая война в эфире: некоторые аспекты операции «Ультра» (рус.) // Защита информации. Инсайд : журнал. — 2007. Архивировано 20 января 2014 года.
• Черняк, Леонид. Тайны проекта Ultra (рус.) // Открытые системы : журнал. — 2003. — № 07—08.
• Херли, Кормак. So Long, And No Thanks for the Externalities: The Rational Rejection of Security Advice by Users (англ.) // New Security Paradigms Workshop : сборник. — Microsoft Research ACM 978-1-60558-845-2/09/09, 2009.
• Рэй, Билл. Wi-Fi Protected Setup easily unlocked by security flaw (англ.) // The Register : портал. — 2011.

СсылкиПравить

• The Brute Force algorithm  (неопр.). Катанийский университет (2007). — Оригинальная реализация алгоритма на языке Си. Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Зернов, Владимир. Защита от bruteforce средствами iptables  (рус.). OpenNET (9 июня 2010). Дата обращения: 30 ноября 2012. Архивировано 16 октября 2012 года.
• Шнайер, Брюс. Cryptanalysis of SHA-1 (англ.). schneier.com (18 февраля 2005). — «a new cryptanalytic result — the first attack faster than brute-force against SHA-1». Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Вайс, Аарон. 'Strong' Passwords May Not Be All They're Cracked Up to Be (англ.). esecurityplanet.com (27 апреля 2010). Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Harper, John. The British Bombe: The Rebuild Project (англ.) (недоступная ссылка — история) (2008). Архивировано 19 декабря 2012 года.
• Ellsbury, Graham. The Enigma and the Bombe (англ.) (недоступная ссылка — история) (2007). Архивировано 19 декабря 2012 года.
• Британские энтузиасты воссоздали дешифратор «Энигмы»  (рус.) (13 сентября 2006). Архивировано из оригинала 29 июня 2012 года.
• Ку, Эндрю. Nvidia Versus AMD: Brute-Force Attack Performance (англ.). Tom’s Hardware (20 июня 2011). Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• МакГлин, Джеймс. Password Hashing (англ.). PHP Security Consortium (2005). Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Vulnerability Note VU#723755 (англ.) (недоступная ссылка — история). Координационный центр CERT (27 декабря 2011). — «WiFi Protected Setup (WPS) PIN brute force vulnerability». Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• The Rabbit-Hole (англ.). — Официальный сайт проекта WASP, на котором можно найти инструкции по сборке беспилотника в домашних условиях.. Дата обращения: 30 ноября 2012. Архивировано 26 ноября 2012 года.
• Гринберг, Энди. Flying Drone Can Crack Wi-Fi Networks, Snoop On Cell Phones (англ.). Forbes (28 июля 2011). Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Хамфрис, Мэттью. WASP: The Linux-powered flying spy drone that cracks Wi-Fi & GSM networks (англ.). www.geek.com^[en] (29 июля 2011). Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Тасси, Майк; Перкинс, Рик.: Wireless Aerial Surveillance Platform (англ.). www.defcon.org (2011). Дата обращения: 30 ноября 2012. Архивировано 25 октября 2012 года.
• Либовиц, Мэтт. Home Wi-Fi Routers Vulnerable to Brute-Force Hack (англ.) (недоступная ссылка — история). SecurityNewsDaily^[en] (2011). Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Либовиц, Мэтт. Flying Drone Steals Wi-Fi Passwords, Hacks Cellphones (англ.) (недоступная ссылка — история). SecurityNewsDaily (2011). Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Гил, Паул. What Is 'Brute Force' Hacking? (англ.). About.com. Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Password Recovery Speeds (англ.). 2009. — Скорость восстановления паролей.  — «How long will your password stand up». Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.
• Get even faster graphics and visualization (англ.). Nvidia. — Параметры Tesla c2075 на сайте производителя.. Дата обращения: 30 ноября 2012. Архивировано 1 декабря 2012 года.