Введення в криптосистеми, Криптографія, Security & Hack, статті

Введення


Існують два основні підходи, застосовуваних у системах захисту інформації. Перший побудований на скруті прямого або непрямого аналізу алгоритму шляхом застосування оригінальних прийомів програмування (використання недокументованих функцій, спеціальних анти-налагоджувальних прийомів). Такий підхід широко застосовується в умовно-безкоштовних програмах, проте, вкрай неефективний. Він володіє поганим співвідношенням накладних витрат на створення \ розтин захисту і крім того не забезпечує навіть мінімальної безпеки. Більшість подібних програм ламаються в плині від декількох хвилин до декількох днів.


Сьогодні більшість комерційних захистів засноване на криптографічних протоколах, а тому виглядає неломаемимі. “Виглядає” тому, що розробники не враховують різницю між теоретичними моделями та практичною реалізацією. Детальніше перелік основних помилок в популярних системах викладено Павлом Семьянова в статті “Чому криптосистеми ненадійні”. Тут відзначу лише наступні – так, дійсно, дуже багато використовуються криптосистеми ненадійні, і практично всі мають нижню межу можливості розв’язання набагато гірше паспортної.


Крім того, зазвичай такі оцінки виходять з припущення, що зловмисник буде просто перебирати послідовно всі паролі один за іншим. Наївно, не так-ли? Лобова атака на сучасних обчислювальних потужностях персональних комп’ютерів сьогодні просто неможлива. Наскільки небудь задовільні результати можуть бути отримані тільки при об’єднанні десятків тисяч комп’ютерів.


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


На жаль, зараз багато хто (з дозволу сказати) недохакери не володіють навіть мінімальними математичними знаннями. Більш того, академічну математику закидають камінням, звинувачуючи останню в повній марності для прикладних і системних програмістів. На жаль, це криза нашого (та й не тільки нашого) освіти.


І проблема не в математиці, а в людях, які не можуть побачити в рядках формул живої реалізації. Було б хвастощами з мого боку обіцяти заповнити прогалини знань читача. Ніхто крім його самого йому не допоможе. Моїм завданням буде показати практичні реалізації, і дати необхідний теоритической мінімум для їх обгрунтування. Можливо це відкриє багатьом у світі сухих формул необмежені перспективи їх застосування?


Незважаючи на те, що перша частина є неминучим теоретичним введенням в ній всі положення будуть розглянуті на прикладах конкретних реалізацій. Для цього необхідно вибрати платформу. Привчаючи читача до детального (“Низкоуровнего”) мислення я вибираю асемблер. Рідше буду використовувати IDA Сі і MS VC. Шанувальники Паскаля і Делфі повинні будуть робити свій вибір самостійно. В усякому разі без знання асемблера вивчення і захист програм в більшості випадків неможлива. Ця книга не навчить вас основам асемблера і розрахована на вже підготовленого читача.


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


Справжній хакер ніколи не відмовить собі задоволення копання не тільки в надрах коду, але і літератури (не важливо, паперовій або електронній). Спокуса використовувати готові схеми і рішення “AS IS” гідний тільки комерційних кракерами (поставив злом на потік і заробляють гроші на експлуатації часто чужих ідей і інструментів). Я не хочу вдаватися в етичну полеміку і задаватися одвічним питанням “що таке добре і що таке погано?” Так чи інакше це є. Будь закінчена технологія не вимагає для використання розуміння її функціонування. Втілена в конкретний програмний код, вона стає в руках вандалів руйнівним програмним зброєю. Вихід із ситуації “методом Страуса “неможливий. Сьогодні обчислювальна техніка вже не контролюється і така програма буде створена і поширена якщо не одним, так іншим человеком.Распространеніе технологій та інструментів для зломів і атак не є актом вандалізму, а навпаки зазначенням на вразливість існуючих систем, спонукаючи до виправлення останніх.


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


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


Передбачається, що існуючі “дірки” будуть виправлені, і весь інструментарій, що міститься на компакт диску виявиться марним в руках вандалів.


Це не відноситься до теоретичних викладок, “відв’язати” від конкретних платформ і реалізацій. На щастя, малоймовірно, що б вандали дали собі працю глибоко розібратися в останніх. У кожному разі відомо, що навіть технічне освіта культурно виховує людину. Знання дають людині чудовий полігон для самовираження, в якому розчиняється бажання капості ближньому своєму.

Хеши. Односторонні функції


Вся сучасна криптографія заснована на використанні методів хешування. Метод хешування дозволяє зберігати безліч елементів множини А в лінійному масиві Х. Як правило, число елементів А багато більше, ніж Х. Математично це можна записати:

h: А ->
{0,x-1}


Це читається функція h відображає кожен елемент А в індекс безлічі Х. Оскільки число елементів А як правило набагато більше Х, то функція h напевно неін’ектівна. Однак, можливе існування такого інтервалу на області визначення функції, в межах якого вона стає ін’ектівной. Це означає, що тільки для одного елемента А існує індекс x1. Функція буде ін’ектівной і в тому випадку, якщо жоден елемент А не відображається на інтервал {X1, x2} за умови, що останній не дорівнює нулю. У будь-якому іншому випадку на кожен індекс безлічі Х відображається більше одного елемента А. Це так звана колізія хеш-функції. Реверс хеш функції полягає в пошуку всіх відображаються на даний індекс елементів. Для будь-якого кінцевого безлічі А це здійсненне завдання, яке найбільш просте рішення має на ін’ектівних інтервалах хеш-множини.


Давайте зупинимося на ін’ектівних інтервалах. Неможливо практичне використання хеш-перетворень без розуміння їх значення. Як приклад розглянемо наступну задачу: нехай нам потрібно ефективний алгоритм порівняння рядків, припустимо, для синтаксичного аналізатора. Просте посимвольно порівняння зажадає значної пам’яті для зберігання образів рядків. Уявімо все можливе безліч рядків в даній розрядній сітці масивом S, тоді ми можемо хеш-перетворенням привести його до безлічі b {0,0 xFF}. Зрозуміло b багато менше S і вимагає для зберігання значно менше пам’яті.


Розглянемо практичну реалізацію для деякого безлічі команд ‘IF’, ‘THEN’, ‘BEGIN’, ‘END’. Виберемо найпростішу хеш функцію посимвольно складаються елементи рядка. Це погана хеш-функція і нижче ми пояснимо чому, але для нашого прикладу її буде достатньо.


Для початку потрібно побудувати хеш таблицю значень для всіх елементів множини S. Скористається для цього програмою file :/ / CD :/ SRC/hash00.exe – “Хеш-калькулятор”. Розглянемо її ключовий фрагмент:

        BYTE GetHash(CString s0)
{
BYTE hash=0;
for (int a=0;a<s0.GetLength();a++) hash = hash + s0 [a]; / / Обчислюємо хеш-суму
return hash;
}

Ми посимвольно складаємо елементи безлічі символів s0, отримуючи в результаті деякий елемент з безлічі calc {0,0 xFF}. Як неважко бачити на кожен елемент безлічі calc відображається не більше, ніж один елемент S. Звідси в заданих рамках функція calc = calc + s0 [a] ін’ектівна. Отже для заданого індексу єдиним чином визначається елемент S. Цим доводиться коректність роботи хеш-аналізатора.


Нижче наведено фрагмент реально працюючого емулятора віртуального процесора
GetMe01 (file://CD:\CrackMe\GetMe01.asm).

 LEA SI, Buffer; Буфер виконавчих команд
start_r: ; <————————————–¬ CALL GetHashe; Обчислення хеш-суми черговий команди | CALL CallIt; Виклик обробника для даної команди | MOV SI, DI; Позиціонування покажчика команд |
CALL Seek ; ^ ¦
JMP short start_r ; –[uncond]——————————
GetHashe PROC NEAR PUSH SI; Зберігаємо віртуальний покажчик команд XOR AX, AX; AH == суматор
gh_Repeat: ; <————————————–¬ LODSB; Беремо черговий елемент безлічі s0 | ADD AH, AL; Додаємо в суматор | XOR AL, ‘:’; Перевірка на кінець команди |
JNZ gh_Repeat ; –([SI]==’:’)—————————
POP DI ; si–>di; return SI
RETN ; –\
ENDP
Seek PROC NEAR
s_repeat: ; <————————————–¬ LODSB; Взяти наступний символ | OR AL, AL; Перевірити на рівність нулю |
JNZ s_repeat ; –([SI]==NULL)————————–
RETN ; –\
ENDP
CallIt Proc NEAR PUSH SI; Зберегти SI LEA SI, TableOfRange; Таблиця покажчиків на обробники
XCHG AX,BX ; BH == AL
ci_rep: ; <————————————–¬ LODSB; Читаємо чергову хеш-суму | OR AL, AL; Кінець таблиці? | JZ _err; – досягнуто кінець таблиці -> | CMP AL, BH; Хеш знайдено? | LODSW; Читаємо чергове зміщення обробника |
JNZ ci_rep ; –(!Hash)——————————- XCHG AX, BX; BX == AX == зсув обробника POP SI; Відновити SI CALL BX; Викликати обробник даної команди
RET ; –\
_err:; Виняткова ситуація. Невірна команда MOV AH, 9; Друк рядка MS-DOS LEA DX, errr; Зсув друкується рядка
INT 21h ; MOV AH, 4Ch; Завершення роботи
INT 21h ; –\
errr DB ‘Невідома команда’, 0Dh, 0Ah, ‘$’
ENDP
; ////////////////////////////////////////////////////////////////////////// ; / / ТАБЛИЦЯ підтримувати команду і ВІДПОВІДНИМ ІМ Оброблювач
; //————————————————————————
TableOfRange: DB 0EFh; Хеш-сума команди DW Offset Proc1; Обробник цієї команди
DB 0E3h
DW offset Proc2
DB 79h
DW offset Proc3
DB 0E6h
DW offset Proc4
DB 01h
DW offset Proc5
DB 0D1h
DW offset Proc7
DB 054h
DW offset Proc8
DB 0ADh
DW offset Proc9 DB 0; Кінець таблиці
Buffer:; Буфер виконавчих команд

Даний приклад зберігає восьмібітних хеш суму кожної команди. Отже незалежно від довжини використовуваних команд для зберігання потрібно всього N байт пам’яті (де N – число команд), що істотно менше обсягу необхідного для повного зберігання тих же самих команд. Теоретично восьмібітних хеш-сума може вмістити до 0xFF +1 команд. Однак, практично запропонована реалізація при додаванні деякого числа команд виявиться непрацездатною. Це трапиться коли двом різним командам буде відповідати одна і та ж хеш-сума. В такому випадку математики говорять про колізії хеш-функції. Отже на вибраному інтервалі хеш функція ставати неін’ектівной і для розглянутої задачі непридатною.


Здавалося б, раз безліч S набагато більше A, то будь-яка хеш функція на повній області визначення S виявиться неін’ектівной. Насправді число елементів S практично завжди багато менше його потужності. Наприклад в безліч слів російської мови представляється безліччю послідовностей від одного до десяти і більше символів, але загальне число існуючих слів свідомо менше 0xFFFFFFFF. Тому можливе існування 32-бітної ін’ектівной хеш функції для синтаксичного аналізатора російської мови.


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


Найбільш часто використовується і добре вивчений мультиплікаційний метод відображення. Математично його можна виразити як h (S [x]) = C * S [x] mod N, де N – це число елементів хеш-множини або іншими словами його потужність. С – будь-яка константа з інтервалу [0, N). При C = 1 ця формула набуває вигляду h (S [x]) = S [x] mod N і є самостійним хеш перетворенням, званим методом залишку. Даний алгоритм так само широко використовується і для генерації псевдовипадкових чисел. І не дивно, адже генератори випадкових чисел є нічим іншим як хеш-перетворенням!


Інший, що знайшла популярність, є надзвичайно потужна функція CRC 32 (Crc16). Розшифровується це як cyclic redundancy check (код циклічного контролю) і в першу чергу покликана підтверджувати неспотвореної вибраної числової послідовності. Це ще одна область застосування хеш-перетворень. У самому ділі це все теж хеш-порівняння. Звичайно, існує певна ймовірність таких спотворень, які не відіб’ються на хеш-суми, але вона досить невелика за умови хорошого розсіювання та чутливості до незначних змін обраного хеш-перетворення.


CRC 32 це багато разів апробована, швидкодіюча якісна хеш-функція дає чудовий результат. Для більшості послідовностей вона буде ін’ектівна. Так, наприклад, багато текстові редактори реалізують синтаксичну “підсвічування” саме на основі CRC32, не викликаючи при цьому колізій.


Розглянемо алгоритм цієї функції. Цілу беззнакову 32-х бітову змінну инициализируем значенням 0FFFFFFFFh. Далі множимо на 2 аргумент функції і значення CRC. Якщо старші біти виявляться не рівні, тоді CRC = CRC XOR 0xEDB88320. І так до останнього біта аргументу. Якщо аргумент строкою (або будь-яка інша послідовність), то операції проводяться над подвійними словами. У канонічному варіанті в кінці циклу вимагають інвертувати всі біти CRC, але це грає роль виключно для сумісності результатів, отриманого різними функціями, і ніяк не позначається на якості. “Магічне число” 0xEDB88320 є стандартний поліном, міняти який не слід, тому що це погіршить якість функції.


Може виникнути така ситуація, коли необхідне число елементів хеш-множини буде помітно менше, ніж 2 ^ 32. Уникнути зайвих витрат можна помноживши результат сам на себе і взявши N старших біт так, що б 2 ^ N було по можливості близько до бажаному. Сенс цієї операції в тому, що б отримати бітову послідовність чутливу до всіх бітам значення CRC.


Розглянемо тепер застосування хеш-перетворень в криптографії. Однією з завдань останньої є перевірка достовірності пароля. Для цього використовують особливі хеш-функції. Чому особливі ми зрозуміємо, розглянувши принцип дії криптосистем. Нехай є деяка криптографічний функція F, розшифровує паролем p послідовність Ai в послідовність Aj.


     p
F(Ai) ——> Aj

Зрозуміло тільки для одного-єдиного p ми отримаємо вихідну послідовність Aj, а для всіх інших p – “сміття”. Яким способом можна упевнитися в тому, що отримана Aj і є шукана послідовність? (При умови, що самій послідовності в наявність не є). Можна зберегти фрагмент вихідної послідовності і потім звірити його з отриманим результатом. Однак, це робить можливою атаку з відкритого тексту на шифр, крім того дуже ненадійно, тому що не гарантується що збіг одного фрагмента забезпечує збігом всієї послідовності.


Ось тут-то на допомогу і приходить хеш-перетворення. Ми можемо обчислити CRC32 для вихідного тексту. Порівнюючи його з CRC32 Aj ми можемо перевірити правильність розшифровки. Оскільки Aj напевно більше 2 ^ 32, то хеш-функція виявиться неін’ектівной і хеш-значення абсолютно не дасть жодного уявлення про вихідної послідовності.


Однак, цей спосіб досить повільний. Набагато швидше порівнювати хеш-суми паролів. Але! Враховуючи число можливих паролів можна прийти до висновку, що з великою ймовірністю обрана хеш функція може виявитися ін’ектівной! Отже, реверсувати останню ми отримаємо вихідний пароль. Це робить уразливими багато захисту, що використовують даний алгоритм.


Вище ми згадували спеціальні хеш-функції. Розвиток криптографії привело до дослідженню так званих односторонніх функцій. У багатьох некомпетентних джерелах змішують поняття хеш і односторонніх функцій. Насправді вони вивчаються різними розділами математики і володіють різними властивостями. Однак, серед них є й такі, які задовольняють двом критеріям відразу. Або інакше кажучи, є односторонні хеш-перетворення. Строго кажучи на сьогоднішній день не знайдено жодної ідеальної односторонньої функції. Більше того, до цих пір не доведено, що такі функції існують. Тому ми будемо говорити лише про наближених до цього реалізаціях.


Функція f: X -> Y називається односторонньою, якщо f (x) може бути легко обчислена для будь-якого елементу X, тоді для всіх елементів Y обчислення такого аргументу f для якого f (x) = y нерозв’язних полиномиально. Це показує, що CRC32 не є односторонньою функцією і, незважаючи на поширену думка, підлягає реверсування. Оскільки для кожного значення х CRC32 існує нескінченна безліч вірних аргументів А, таких що F: CRC32 (A) = x, то отримання безлічі відповідних аргументів А ‘нам не дає жодних натяків для знаходження в ньому шуканого елемента. Саме цим і викликана безпечність широкого (І між іншим не виправданого) застосування CRC32 в криптографії. Однобічність цієї функції тримається лише на її неін’ектівності. Однак, як було показано вище, можливе існування такого інтервалу I на якому обрана хеш функція є ін’ектівной. Практично у всіх популярних криптосистемах не робиться жодних спроб перевірки приналежності хешіруемих даних до цього інтервалу. Більш того, для будь-якого кінцевого перерахованого безлічі Z можливий як прямий (перед обчислений), так і зворотний реверс хеш-функції. CRC32 успішно звертається полиномиально. У результаті часто ставати уразливим місцем криптозахисті.


Розглянемо табличне реверсування. Для цього обчислимо CRC32 кожного елемента перерахованого безлічі Z і порівняємо її та вихідної. Серед отриманих елементів знаходиться принаймні один дійсний пароль. Безліч Z в нашому випадку це безліч можливих паролів. Неважко вирахувати, що навіть для восьмісімвольних паролів потрібно принаймні 4 ^ 8 (або 2 ^ 16) байт пам’яті для хеш-сум і ще більше для зберігання образу паролів. Крім того це зажадає дуже великого числа ітерацій.


Тому особливий інтерес представляє зворотний полінормальний алгоритм. Зауважимо відразу – він є полінормальним тільки для кінцевих перерахованих множин. А виглядає для кожного біта оберненого аргументу так:

   b == !Hibit(xor (crc32,0xEDB88320)) | Hibit(crc32)

Тобто припустимо, що кожен біт аргументу може бути як нулем, так і одиницею. Перевіримо обидва результату на приналежність до безлічі Z і відкинемо непотрібні. Якщо обидва значення належать Z, то запам’ятовуємо обидва і далі обчислюємо залишилися біти для обох з них і так до тих пір поки не буде відкинутий останній елемент, як не належить до безлічі Z. Інакше кажучи ми будуємо бінарне дерево. Дуже легко підрахувати необхідну кількість ітерацій для знаходження все можливих паролів. Крім того для цієї ситуації застосовні всі ефективні алгоритми, що працюють з двійковими деревами. Збалансоване двійкове дерево дозволить ефективно реверсувати crc32 навіть у разі великого розсіяння елементів Z. Інакше кажучи ми можемо швидко перевірити не є-ли цей хеш контрольної сумою якого-небудь словникового слова. Зворотне перетворення зробить це істотно швидше прямого перебору безлічі словникових слів. Детальніше операції з двійковими деревами викладені в книзі Майкла Ласло “Обчислювальна геометрія та комп’ютерна графіка на C + +” (Москва БИНОМ 1997) або в багатьох інших виданнях. Дуже рекомендую ознайомитися з конспектами лекцій Манфрейда Броя “ІНФОРМАТИКА” Діалог-Міфи 1998 рік.


А ми не будемо на цьому більше затримувати уваги і розглянемо алгоритми генерації будь-якої заданої послідовності ключів. Атака перебором це один з варіантів розтину односторонніх хеш функцій. Всі криптосистеми будуються з урахуванням того, що повний перебір ключів займе свідомо недосяжний проміжок часу. Ситуації з вибором короткого пароля ми безжально відкинемо. Не те що Якби вони були досить рідкісні, але сподіватися на це дуже ризиковано і не гарантовано, що дані спроби взагалі увінчаються успіхом. Проте, в ряді випадків можливий обмежений перебір ключів. Так наприклад, в архіватор rar ранніх версій будь пароль перетворювався в 80 бітову хеш-послідовність. Таким чином перебором 2 ^ 80 варіантів можна було розкрити будь-який, як завгодно довгий пароль. З іншого боку, для паролів, що складаються менше ніж з восьми символом необхідно було перебрати набагато менші число варіантів. Таким чином нам потрібно побудувати послідовність всіх можливих варіантів для перебору. Вона буде дуже велика, але цілком вирішувана за прийнятний час.


Щоб навчитися будувати ефективні алгоритми необхідно хоча б коротенько ознайомитися з теорією формальних мов. Поняття формальної мови вимагає розгляду алфавіту. Алфавітом є кінцеве перераховане безліч A. Безліч всіх кінцевих послідовностей елементів А називається формальним мовою. Мови оперують словами. Для заданої множини A послідовність елементів x1 .. xn належить A утворює слово довжини n, яке записується як . Безліч всіх слів дорівнює AxAx … xA, що прийнято записувати як A *. Для кожного слова формального мови існує відображення length: A ‘-> N, де N – довжина слова.


Таким чином нашим завданням буде перерахувати безліч слів формального мови. Безліч слів різних мов можна об’єднати в одне загальне безліч. Цю операцію доводиться дуже часто при атаках на криптоалгоритми. В нашому прикладі ми повинні об’єднати безліч паролів і безліч ключів і розподілити так, що б по можливості слова виявилися відсортовані за ймовірністю збіги з істинним паролем (ключем). Це помітно ускладнює алгоритм, але надзвичайно підвищує його ефективність. Часто крипостійкість системи виявиться недостатньою, щоб протистояти такій хитрій атаці.


Для початку розглянемо найпростіший алгоритм генерації паролів побудований на послідовному множині. Повний вихідний текст знаходиться на file :/ / CD :/ SRC / parole.asm, а нижче наводиться лише ключовий фрагмент. Запропонований алгоритм є втіленням простоти і при цьому спритно працює і досить гнучкий, щоб надалі міг бути застосований для довільних перерахованих множин.

 MOV AH, 9h; телетайпного виведення LEA SI, Password; Початковий пароль MOV DX, SI; для f.9/Int 21h NextPassword:,> Генерація наступного пароля <- ¬ XOR BX, BX; З нульового розряду | CheckOver:,> Перевірка на переповнення <---- ¬ | INC Byte Ptr DS: [SI + BX]; Збільшуємо перший зліва символ | | CMP Byte Ptr DS: [SI + BX], 'z'; Вихід за припустимі межі? | | JB WritePassword; - {Ні перенесення} ----------------- + MOV Byte Ptr [SI + BX], ''; Скидаємо текшая розряд | | INC BX; Перенесення на наступний розряд | |
        JMP     Short CheckOver         ; ---------------------------------¦ WritePassword:,> Висновок пароля на екран |
INT 21h ; ^ ¦
JMP SHORT NextPassword ; ———————————- Password DB 8 Dup (”); <- початковий пароль DB 13, 10, '$'; <- кінець рядка

Той же алгоритм витончено виражається одним рядком на мові програмування С
(file://CD:/SRC/PA E/Pae.cpp):

         while ((pasword[index++]++)>’z’) pasword[index-1]=’ ‘;

Математичний зміст зводиться до послідовного перебору всіх елементів безлічі [”, ‘z’] шляхом додавання одиниці з урахуванням перенесення. Тобто інакше можна цю функцію можна назвати як INC x – де x число практично необмеженої розрядності.


Даний алгоритм належить до найпростіших, але для практичного застосування не годиться. Нам необхідно перебирати паролі з довільного безлічі символів. Даний приклад працює на єдиному інтервалі [x1, xn] лінійного безлічі C.


Ось тут нам і знадобиться математика! Справді ускладнювати алгоритм немає ніякої потреби, достатньо лише відобразити лінійне безліч C на перераховане
Z.


  f
C —> Z

При цьому така операція дає нам необмежену гнучкість. Елементами перерахованого безлічі можуть бути літери, групи літер, а так само цілі слова. Таким чином запропонований алгоритм дозволяє повністю абстрагуватися від використовуваного типу даних.


Розглянемо наступний аспект. Як правило паролі складаються не з рівноймовірно символів. Хороша перебирає програма повинна це враховувати. Чи може це забезпечити запропонований алгоритм? Розглянемо таку функцію відображення f, яка відображає більш одного індексу C на один і той же елемент Z. Таким чином, задаючи ймовірність його появи в генерується пароль. Зазначимо, однак, що при цьому зростуть накладні витрати. Нехай маємо для елемента c1 і с2, які відображаються на один і той же елемент z1. Тоді ми отримаємо двічі один і той же пароль z1. Зазвичай цим можна знехтувати, тому що частка дубльованих паролів несуттєва. Але коли вона досягне декількох відсотків від загальної числа, то розумно буде запам’ятовувати все зустрілися паролі і ігнорувати повторні. Двійкове дерево забезпечує прийнятну швидкість пошуку.


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


Як приклад наведемо вдосконалений алгоритм з відображенням виконуваних функцією xlat (file :/ / CD :/ SRC/Parole01.asm).

 Next: MOV AL, Byte Ptr DS: [SI + BP]; Взяти елемент psw XLAT; Відобразити його на мнж. alf MOV [DI + BP], AL; Записати результат
INC Byte ptr [SI + BP]; Наступний
CALL WritePassword; Вивести пароль
CMP [SI + BP], CL; Перевірка на переповнення
JB Repeat

Тепер використовується алфавіт може складатися з будь-якого безлічі символів. Зазначимо, що запропонована реалізація не найефективніша. Є безліч інших цікавих алгоритмів. На якомусь одному з них ми зупинятися не будемо, тому що це було б занадто утомливо і не цікаво.


Тепер можна атакувати будь-яку односторонню функцію перебираючи всі допустимі аргументи і заносячи їх у таблицю, після заповнення якої можна знайти все аргументи А, для яких справедливо f: a = key, де key відомий результат функції. Якщо вибрана функція ін’ектівна, і існує не більше одного аргументу для заданого кey, то в побудові таблиці немає ніякої необхідності. Перший збігається аргумент і буде шуканим.


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


Чи можлива ефективна атака на RSA і подібні системи? Над проблемою розкладання чисел на прості співмножники безуспішно билися багато знаменитих математики. Але до цих пір не доведено, що це не можливо. Бути може і серед хакерів знайдеться математичний геній який вирішить цю проблему? Але поки ж нічого крім перебору запропонувати не вдається. Єдиним виходом є не повний, а самоорганізується табличний пошук. Можливе створення спеціалізованого чипа, що займається таким перебором. Множення дуже проста операція, тому вона легко реалізується апаратно, і такий чіп може дуже дешево коштувати.


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


Як не парадоксально, але використання хороших хеш-функцій зменшує число можливих паролів, полегшуючи роботу зломщика. Використання поганих – дає про вихідному паролі інформацію по якій його можливо частково відновити. Тому, ніякі хеш функції не можна використовувати для “згортки” з пароля. Наприклад RAR не перевіряє пароль на валідність, а звіряє CRC розшифрованих даних. Це не дає ніякої інформації про вихідний паролі, але повільно працює. З іншого боку у всіх швидких алгоритмів шифрування (хвалебні повідомлення про яких періодично з’являються в різних джерелах) є істотний недолік – швидкий перебір збільшує шанси лобової атаки.


Розглянемо ще одну область застосування хеш функцій. Нехай у нас є деякий пароль p, який “зашитий” в електронному ключі або введений користувачем. Порівнювати пароль типу if (UserPassword! = MyPassword) abort (); не можна тому це дуже просто ламається. Можна розшифрувати паролем деякий фрагмент коду або використовувати його як константу. За умови що для шифрування обрана кріптосктойкая схема пароль не можна знайти ніяк крім перебором всіх возможних.Контроль правильності введення можна забезпечити за допомогою контрольних сум. Ця схема дуже надійна, але в більшості програм реалізована з помилками. Як уже здогадався читач, контрольна сума знімається з пароля, а не з розшифрованих даних. Але це далеко не найдурніша помилка! В цілях безпеки ел. ключ не повинен повідомляти пароль в “прямому” вигляді. З нього знімається хеш-сума, яка і передається для розшифровки. Таким чином, ми маємо два значення різних хеш функцій. Перше для контролю правильності пароля, друге – для розшифровки. Ми отримуємо систему двох рівнянь рішенням якого буде перетин двох множин реверсувати хеш-перетворень. Це скорочує безліч перебираються паролів аж до єдиного. Такий підхід застосуємо в разі ідеальних хеш функцій. Іншим рішенням буде спроба обчислити другий контрольний суму з першої.


Поширеною помилкою є і використання “довгих” crc, порівнянних з довгою пароля. Читач може сам підрахувати скільки можливих восьми-символьних паролів має одне і те ж значення 32-бітної контрольки суми. Однак використання більш коротких хеш-сум збільшує ймовірність того, що невірний пароль буде сприйнятий як правильний.


Популярна система Novell NetWare 3.x-4.x використовувала уразливий алгоритм. Суть його зводилася до того, що з пароля, знімалася хеш-сума з якої потім порівнювався вводиться пароль. Ця функція була оборотна. Таким чином можна отримати БЕЗЛІЧ паролів, які все сприймалося системою як вірні.


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


Реально ж рідкісні фірми можуть дозволити собі аналіз подібного рівня. Зазвичай обмежуються побіжним оглядом. До чого це призводить ми вже маємо можливість спостерігати.


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


Однак, як приклад реверсіруем популярні хеш функції. Існує досить універсальний покроковий алгоритм. Суть його в наступному – для кожного допустимого символу виконуємо хеш-зворотну операцію. Отриманий результат рекурсивно звертаємо до отримання послідовності заданої довжини.


Нижче наведено спрощений алгоритм для отримання всіх допустимих паролів для заданої хеш-суми посимвольного підрахунку суми всіх елементів (див. функцію GetHashe в прикладі ‘GetMe01’).

      ReHashe(unsigned char hashe)
{
for (unsigned char a=’A’;a<‘a’;a++)
{
if (!hashe-=a) return;
ReHashe(hashe);
}
}

Даний приклад не рекомендується запускати. Легко довести, що для будь-якого hashe існує нескінченна безліч ключів, таких що f (key) == hashe. Реально розрядність паролів обмежена ємністю стека. При вичерпанні останнього виникне виняткова ситуація і виконання програми буде аварійно завершено.


Більш того, легко довести, що даний приклад може “провалитися” в нескінченний рекурсивний спуск. Нехай hash – непарне число, а A – парне. Тоді hash-a ніколи не дорівнюватиме нулю.


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


Не менш очевидний недолік запропонованого алгоритму, що видаються їм паролі не розсортовані по довжині. Необхідно, що б використовуваний алгоритм починав з коротких паролів переходячи до більш довгим.


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


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


У ряді випадків використання універсальних алгоритмів виявляється неприйнятно і тоді для кожної функції розробляється власний унікальний алгоритм.


Спробуємо кількісно виразити очікуване число паролів для іншої популярної функції hashe (A) = a1 xor a2 xor a3 … xor an. Для початку доведемо що будь-якого a, рівного x1 xor x2 існують тільки дві пари x1 і x2 за умови, що X [0,1]. Як відомо з Булевського алгебри операція xor може бути представлена наступної логічної матрицею.

        xor ¦  0   1
—-+————
0 ¦ 0 1
¦
1 ¦ 1 0
¦

Ми бачимо, що для кожного значення функції існують рівно дві пари x1, x2, що й потрібно було довести. Тому очікуване число паролів буде 2 ^ n де N розрядність хеш-суми. Розрядність пароля при цьому не вище розрядності хеш-суми. Тобто ми просто провели просте побітове звернення функції xor. Для восьмібітной хеш-суми це число дорівнює 0x100! Тобто значення хешу нам абсолютно нічого не дає, тому що x1 і x2 можуть бути будь-якими! Однак, x1x2 це 2 ^ 16 варіантів, тобто знання хеш суми все ж дозволяє скоротити число перебираються паролів в 0x100 раз. Непогано, але навіть цей результат можна поліпшити. Безліч допустимих символом пароля, як правило багато менше 0x100. Нехай очікуваний пароль складається тільки з символів ‘A’ .. ‘Z’. Тоді для існує не більше 2 ^ 5 можливих пар x1 і x2!


Останнім ми розглянемо реверс мультиплікаційного алгоритму. Нехай A = CX mod N, тоді X = k * N / C + A, де k! = 0. Але в межах [0, N) мультиплікаційна функція ін’ектівна! Для доказу цього згадати, що будь-яке число можна представити як x * n + y єдиним чином.


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


Всі наведені хеш-функції не є однобічними і значно зменшують число можливих паролів. Зовсім інакше справа йде з односторонніми функціями, що використовуються в криптостійкий системах. Здавалося б, раз звернення їхня справа безнадійна, то в цьому місці глави можна ставити крапку і навіть не намагатися займатися завідомо нерозв’язною проблемою. Почасти це вірно. Дійсно, незворотність більшості функцій сумнівів не викликає, але інші, відмінні від звернення шляху часто залишаються неврахованими і не закритими, зайвий раз підтверджуючи слабкість більшості реалізацій. Часто односторонні функції обчислюються дуже швидко. Таким чином, вигідніше спочатку послідовним перебором всіх можливих паролі, що дають заданий хеш. Після атакувати шифр заданим безліччю паролів. Всі “сильні” криптостійкі алгоритми як правило дуже повільні. Саме це і перешкоджає атаці. Так наприклад на P-120 швидкість перебору UNIX – MD5 не перевищує 200 паролів \ сек. Тоді як багато хеш-функції до 300.000 і вище! Односпрямованість сама по собі не рятує функцію. Так, реверс не можливий, але пряма атака (тобто послідовний перебір всіх аргументів до збігу зі значенням функції) ефективніше прямої атаки на шифр. Втім, не варто спокушатися. Вельми ймовірно, що не дивлячись на грубі помилки реалізації криптосистеми злом буде лежати за межею можливого часу. Ну знайдемо ми пароль не за більйон, а за десять років, Так, ймовірно, і міркують конструктори захистів. Адже в цих міркування вкралася помилка! На чому тримається криптосистема? На малойскорості перебору паролів і великій кількості підходящим під хеш ключів. За умови використання безглуздого пароля хакеру залишилося б тільки розвести руками. Проте, користувачі схильні вибирати осмислені паролі. Якщо такий зустрітися в множині підходящим під хеш паролів, то у подальшій атаці на систему, можливо вже не буде потреби! Час витрачений на атаку в такому випадку визначається тільки швидкістю виконання хеш-перетворення! Запропонований механізм дуже близький до словникової атаці, і заснований на “слабких” паролі. Пошук “Осмисленого” пароля представляє вибірку всіх паролів, що включають в себе по принаймні трьох-символьний фрагмент словникового слова і відсортований в убуванні довжини підрядка.


Існує принаймні ще одне вразливе місце, введене в деякі кріптостімеми, під тиском уряду. Це так звані “майстер-паролі”, Передбачається, що вони повинні бути відомі виключно спец-службам і не можуть бути знайдені інакше, як методом перебору. Дивно, але зустрічаються словникові майстер-паролі. Так, наприклад, AWARD_SW. Забавно, що коли навіть користувачі починають усвідомлювати слабкість словникових паролів і адміністратори використовують щось на зразок t% 7Nh6i @ SrF наймогутніша зброя (адже воно дає доступ до ВСІМ паролів) так вразливе для атаки. Однак, криптографи воліють використовувати замість майстер-паролів односторонні функції з секретом. Це означає, що насправді ніякі вони не односторонні і існує просте зворотне рішення. Але от тільки знайти його представляє не менш просту задачу, ніж атакувати пароль.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*