Повний перебір

Повний перебір (або метод "грубої сили", англ. brute force ) - Метод розв'язання математичних задач. Відноситься до класу методів пошуку рішення вичерпування всіляких варіантів [En] . Складність повного перебору залежить від кількості всіх можливих рішень задачі. Якщо простір рішень дуже велике, то повний перебір може не дати результатів протягом декількох років або навіть сторіч.

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

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


1. Метод вичерпання

1.1. Термінологія

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


1.2. Опис

"Метод вичерпування" включає в себе цілий клас різних методів. Зазвичай постановка задачі має на увазі розгляд кінцевого числа станів даної логічної системи з метою виявлення істинності логічного твердження допомогою незалежного аналізу кожного стану [1]. Методика доказу твердження складається з двох частин:

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

2. Характерні завдання, які вирішуються методом повного перебору

Хоча метод brute force в більшості прикладних завдань (особливо не пов'язаних зі зломом) на практиці не застосовується, є низка винятків. Зокрема, коли brute force все ж виявляється оптимальним, або являє собою початковий етап у розробці алгоритму, його використання виправдане. Прикладом оптимальності brute force є алгоритм оцінки часу обчислення цепочечних творів матриць, який не вдається прискорити в порівнянні з алгоритмом, заснованим на методі "грубої сили" [2]. Цей алгоритм використовується для вирішення класичної задачі динамічного програмування - визначення пріоритетів обчислень матричних добутків наступного вигляду: ~ A_1 A_2 A_3 ... A_n .


2.1. Приклад використання 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].


2.2. Зв'язок з концепцією "розділяй і володарюй"

Алгоритм швидкого сортування - заснований на парадигмі "розділяй і володарюй".

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

Іншим яскравим прикладом фундаментальної концепції теорії алгоритмів є принцип " розділяй і володарюй ". Ця концепція застосовна, коли система піддається поділу на безліч підсистем, структура яких аналогічна структурі вихідної системи [6]. В таких випадках підсистеми також піддаються розділенню, або є тривіальними [6]. Для таких систем тривіальної є початково поставлена ​​задача . Таким чином, реалізація концепції "поділяй і владарюй" має рекурсивний характер.

У свою чергу, рекурсія являє собою різновид повного перебору. Так, рекурсія застосовна лише для дискретних систем [En] [7]. Однак ця вимога відноситься не до станів даної системи, а до її субструктур [En] . Послідовне розгляд усіх рівнів дає вичерпне рішення задачі, поставленої для всієї дискретної системи.

У порівнянні з іншими прикладами повного перебору, особливістю методу рекурсії є те, що кінцеве рішення спирається не на одну-єдину тривіальну підсистему. У загальному випадку рішення формується на підставі цілого безлічі підсистем.

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


3. Атака методом "грубої сили"

Комп'ютер компанії EFF для виламування шифру DES. Маючи в розпорядженні 1856 мікросхем, зламував ключ DES всього за кілька діб. На фотографії видно двостороння плата "DES Cracker", що містить 64 мікросхеми "Deep Crack". Ціна всього обчислювального комплексу - $ 250 000

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

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


3.1. Приклад тривалості підбору паролів

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

Кількість знаків Кількість варіантів Стійкість Час перебору
1 36 5 біт менше секунди
2 1296 10 біт менше секунди
3 46656 15 біт менше секунди
4 1679616 21 біт 17 секунд
5 60466176 26 біт 10 хвилин
6 2176782336 31 біт 6:00
7 78364164096 36 біт 9 днів
8 2,821 109 9x10 12 41 біт 11 місяців
9 1,015 599 5x10 14 46 біт 32 роки
10 3,656 158 4x10 15 52 біта 1162 року
11 1,316 217 0x10 17 58 біт 41823 року
12 4,738 381 3x10 18 62 біта 1505615 років

Таким чином, паролі довжиною до 7 символів включно в загальному випадку не є надійними.


3.2. Засоби проведення 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.


3.3. Стійкість до атаки повного перебору

У процесі поліпшення системи інформаційної безпеки по відношенню до атаки повним перебором можна виділити два основних напрямки:

  1. підвищення вимог до ключів доступу від інформації, що захищається;
  2. підвищення надійності всіх вузлів системи безпеки.

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


4. Методи оптимізації повного перебору

4.1. Метод гілок і меж

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

4.2. Розпаралелювання обчислень

Одним з методом збільшення швидкості підбору ключа є розпаралелювання обчислень. Існує два підходи до розпаралелювання [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 \ - Число процесорів.

4.3. Райдужні таблиці

4.3.1. Передумови до появи

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


4.3.2. Використання

Райдужна таблиця створюється побудовою ланцюжків можливих паролів. Кожна ланцюжок починається з випадкового можливого пароля, потім піддається дії хеш-функції та функції редукції. Ця функція перетворює результат хеш-функції в деякий можливий пароль (наприклад, якщо ми припускаємо, що пароль має довжину 64 біта, то функцією редукції може бути взяття перших 64 біт хешу, побітове додавання всіх 64-бітових блоків хешу і т. п.) . Проміжні паролі в ланцюжку відкидаються і в таблицю записуються тільки перший і останній елементи ланцюжків. Створення таких таблиць вимагає більше часу, ніж потрібно для створення звичайних таблиць пошуку, але значно менше пам'яті (аж до сотень гігабайт, при обсязі для звичайних таблиць в N слів для райдужних потрібно всього порядку N 2/3) [27]. При цьому вони вимагають хоч і більше часу (в порівнянні із звичайними методами) на відновлення вихідного пароля, але на практиці більш реалізовувані (для побудови звичайної таблиці для 6-символьного пароля з вантовими символами потрібно 256 6 = 281 474 976 710 656 блоків пам'яті, в той час як для райдужної - всього 256 6 ⅔ = 4294967296 блоків).

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

У підсумку виходить таблиця, яка може з високою ймовірністю відновити пароль за невеликий час [28].


5. Інциденти

Хоча будь-який захист інформаційної системи повинна, в першу чергу, бути надійною по відношенню до атаки методом "грубої сили", випадки успішного застосування даної атаки зловмисниками досить поширені.

5.1. Атака "Енігми"

Функціонуюча відновлена ​​версія "бомби" в музеї Блетчлі-парк. Кожен з барабанних роторів імітує роботу відповідного ротора Енігми. Всього використовується 36 еквівалентних вузлів Енігми. У правій частині середньої полиці знаходяться три ідентифікаційних ротора. Відновлення "бомби" стало можливим в 2008 році завдяки працям Джона Харпера [En] [29], а церемонію першого запуску очолив покровитель Британського комп'ютерного товариства [En] , Едвард, герцог Кентський.

Винайдена в 1918 році шифрувальна машина, названа "Енігма", широко використовувалося німецьким військово-морським флотом починаючи з 1929 року. Протягом подальших декількох років система модифікувалася, а з 1930 року активно використовувалася німецькою армією і урядом в процесі Другої світової війни [30].

Перші перехоплення повідомлень, зашифрованих з кодом Енігми відносяться до 1926 року. Однак прочитати повідомлення довгий час не могли. Протягом всієї Другої світової йшло протистояння між польськими та німецькими криптографами. Поляки, отримуючи черговий результат по взлому німецької криптосистеми, стикалися з новими труднощами, які привносили німецькі інженери, постійно модернізують систему "Енігма". Влітку 1939, коли неминучість вторгнення в Польщу стала очевидна, бюро передало результати своєї роботи англійської та французької розвідкам [31].

Подальша робота по злому була організована в Блетчлі-парку. Основним інструментом криптоаналітиків стала дешифровальной машини "Бомба". Її прототип був створений польськими математиками напередодні Другої світової війни для міністерства оборони Польщі. На основі цієї розробки та при безпосередній підтримці її творців в Англії був сконструйований більш "просунутий" агрегат.

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

З сучасної точки зору шифр "Енігми" був не дуже надійним, але тільки поєднання цього чинника з наявністю безлічі перехоплених повідомлень, кодових книг, донесень розвідки, результатів зусиль військових та навіть терористичних атак дозволило "розкрити" шифр [31].

Після війни Черчілль, з міркувань безпеки, наказав зруйнувати ці машини.


5.2. Уразливість протоколу WPS

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


5.3. Масовий злом домашніх мереж за допомогою 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 і зламує стільникові телефони

Література