Алгоритми генерації та оцінки стійкості паролів (Delphi)

ДИПЛОМНА РОБОТА

"Алгоритми генерації та оцінки стійкості паролів"

Вступ

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

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

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

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

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

Заслуга конструювання довгих пceвдoвипадкових рядів з хорошими статистичними властивостями повністю належить криптографії. Для забезпечення безпеки комп’ютерних систем критично важливо мати алгоритми, що задовольняють такому критерію як непередбачуваність. Іншими словами, навіть знаючи алгоритм генератора й всі попередні елементи послідовності, повинне бути максимально трудомістким обчислення наступних елементів.

Ceкpeтні ключі є основою криптографічних перетворень, для яких, слідуючи правилу Кepкхoфa, стійкість хорошої шифрувальної системи визначається лише секретністю ключа. Однак, на практиці створення, розподіл і зберігання ключів рідко були складними технічно, хоч і дорогими завданнями.

Головна проблема класичної криптографії довгий час полягала в трудності генерування непередбачуваних двійкових послідовностей великої довжини із застосуванням короткого випадкового ключа. Для її вирішення широко використовуються генератори двійкових пceвдoвипадкових послідовностей. Суттєвий прогрес в розробці і аналізі цих генераторів був досягнутий лише на початку шістдесятих років.

Метою дипломної роботи є дослідження алгоритмів генерації та оцінки стійкості паролів. Розроблена система призначена для генерації криптостійких паролів з використанням двох типів алгоритмів — на основі псевдовипадкової послідовності та ключової фрази. Також розроблена система дозволяє визначити вагу стійкості пароля.

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

1. Постановка завдання

1.1 Найменування та галузь використання

Найменування розробки: система генерації та оцінки стійкості паролів.

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

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

1.2 Підстава для створення

Підставою для розробки є наказ № 55С-01 від 1 листопада 2011 р. по Криворізькому інституту КУЕІТУ.

Початок робіт: 03.11.11. Закінчення робіт: 03.05.12.

1.3 Характеристика розробленого програмного забезпечення

Система генерації та оцінки стійкості паролів була створена за допомогою середовища прискореної розробки програмного забезпечення Delphi. При розробці інтерфейсу користувача були використані компоненти пакету AlphaControls 2010.

Склад розробленої системи:

· password. exe — виконавчий файл системи;

· my. ini — ini-файл, що містить інформацію про поточні налаштування системи;

· NextAlpha. asz — skin-файл інтерфейсу системи;

· help. hlp — файл довідки.

1.4 Мета й призначення

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

1. генерація пароля на основі псевдовипадкової послідовності;

2. генерація пароля на основі ключової фрази;

3. оцінка стійкості пароля на основі алгоритму Password Strength Meter.

1.5 Загальні вимоги до розробки

Вимоги до програмного забезпечення:

· робота в середовищі операційних систем Windows 2000/XP/Vista/7;

· відсутність додаткових вимог до розміщення здійсненних файлів, простота та зрозумілість інтерфейсу користувача;

Мінімальні вимоги до апаратного забезпечення:

· IBM-сумісний комп’ютер, не нижче Pentium IІ, RAM-128Mb, SVGA-800*600*16bit;

· вільний простір на жорсткому диску не менш 2 Мб;

· монітор, клавіатура, маніпулятор типу «миша».

1.6 Джерела розробки

Джерелами розробки дипломної роботи є:

· технічне завдання на реалізацію проекту;

· довідкова література;

· наукова література;

· технічна література;

· програмна документація.

2. Огляд алгоритмів генерації псевдовипадкових послідовностей

2.1 Проблема генерації випадкових чисел в історичному аспекті

програмний пароль тестування алгоритм Протягом багатьох років ті, кому випадкові числа були необхідні для наукової праці, змушені були тягати кулі з урни, попередньо добре перемішавши їх, або кидати гральні кості, або розкладати карти. Таблиця, що містить більше 40 000 узятих навмання випадкових цифр зі звітів про перепис, була опублікована в 1927 році Л. X. К. Типпеттом.

З тих пор були побудовані механічні генератори випадкових чисел. Перша така машина була використана в 1939 році М. Ж. Кендаллом і Б. Бабінгтон-Смітом (В. Babington-Smith) для побудови таблиці, що містить 100 000 випадкових цифр. Комп’ютер Ferranti Mark I, уперше запущений в 1951 році, мав вбудовану програму, що використовувала резисторний генератор шуму та поставляла 20 випадкових бітів на суматор. Цей метод був запропонований А. М. Тьюрингом. В 1955 році. RAND Corporation опублікувала широко використовувані таблиці, у яких утримувався мільйон випадкових цифр, отриманих за допомогою інших спеціальних пристроїв. Відомий генератор випадкових чисел ERNIE застосовувався протягом багатьох років для визначення виграшних номерів британської лотереї.

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

Генератор ERNIE міг бути убудований у комп’ютер, як в Ferranti Mark I, але це виявилося незручно, оскільки неможливо точно відтворити обчислення навітьвідразу по закінченні роботи програми; більше того, такі генератори часто давали збої, що було вкрай важко виявити.

Технологічний прогрес дозволив повернутися до використання таблиць в 90-ті роки, тому що мільярди тестованих випадкових байтів можна було розмістити на компакт-дисках. Дж. Марсалья (George Marsaglia) допоміг пожвавити табличний метод в 1995 році, підготувавши демонстраційний диск із 650 Мбайт випадкових чисел, при генеруванні яких запис шуму діодного ланцюга сполучалася з певним чином скомпонованою музикою в стилі «реп». (Він назвав це «білим і чорним шумом».)

Недосконалість перших механічних методів спочатку розбудило інтерес до одержання випадкових чисел за допомогою звичайних арифметичних операцій, закладених у комп’ютер. Джон фон Нейман (John von Neumann) першим запропонував такий підхід близько 1940 року. Його ідея полягала у тому, щоб піднести до квадрата попереднє випадкове число й виділити середні цифри. Метод середин квадратів фон Неймана фактично є порівняно бідним джерелом випадкових чисел, однак він послужив відправною точкою наступних досліджень у цій області.

2.2 Загальні характеристики генераторів псевдовипадкових чисел

ГПВЧ — алгоритм, що генерує послідовність чисел, елементи якої майже незалежний друг від друга й підкоряються заданому розподілу.

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

У більшості завдань прикладної математики, розв’язуваних стохастичними методами, винятково важливим є досить специфічна властивість «рівномірності розподілу» випадкових чисел, що генерують ГПВЧ. Специфічне тому, що воно радикально відрізняється від поняття, описуваного тим же терміном у математичній статистиці. Щоб не було подібної плутанини, термін «рівномірність розподілу» часто заміняють на «гарну розподіленість» і підкреслюють, що він ставиться саме до послідовності чисел («добре розподілена послідовність» або «well distributed sequence»). Як й у випадках з АГВЧ, коли хоча й неявно, але малося на увазі, що за апаратними засобами ГВЧ стоїть потужна й складна програмна підтримка, так й в обчислювальних застосуваннях ГПВЧ навіть над таким майже ідеальним генератором, як Mersenne Twister (Вихор Мерсенна), для одержання високих показників треба «надбудовувати» програмний прошарок, що формує з послідовності випадкових чисел добре розподілену послідовність.

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

Будь-який ГПВЧ із обмеженими ресурсами рано або пізно зациклюється — починає повторювати ту саму послідовність чисел. Довжина циклів ГПВЧ залежить від самого генератора й у середньому становить близько 2^n/2, де n — розмір внутрішнього стану в бітах, хоча лінійні конгруентні й LFSR-генератори мають максимальні цикли порядку 2ⁿ. Якщо ГПВЧ може сходитися до занадто коротких циклів, такий ГПВЧ стає передбачуваним й є непридатним.

Більшість простих арифметичних генераторів хоча й мають велику швидкість, але страждають від багатьох серйозних недоліків:

· занадто короткий період;

· послідовні значення не є незалежними;

· деякі біти «менш випадкові», чим інші;

· нерівномірний одномірний розподіл;

· зворотність.

Зокрема, алгоритм RANDU, що десятиліттями використовувався на мейнфреймах, виявився дуже поганим, що викликало сумнів у вірогідності результатів багатьох досліджень, що використали цей алгоритм.

Різновидом ГПВЧ є ГПВБ — генератори псевдо-випадкових біт, а так само різних потокових шифрів. ГПВБ, як і потокові шифри, складаються із внутрішнього стану (звичайно розміром від 16 біт до декількох мегабайт), функції ініціалізації внутрішнього стану ключем або насінням (англ. seed), функції відновлення внутрішнього стану й функції виводу. ГПВБ підрозділяються на прості арифметичні, зламані криптографічні й криптостойкі. Їхнє загальне призначення — генерація послідовностей чисел, які неможливо відрізнити від випадкових обчислювальними методами.

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

У військових цілях й у польових умовах застосовуються тільки засекречені синхронні криптостойкі ГПВЧ (потокові шифри), блокові шифри не використаються. Прикладами відомих криптостойких ГПВЧ є RC4, ISAAC, SEAL, Snow, зовсім повільний теоретичний алгоритм Блюма, Блюма й Шуба, а так само лічильники із криптографічними кеш-функціями або криптостійкими блоковими шифрами замість функції виводу.

2.3 Випадкові числа й теорія імовірності

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

Приклади:

випробування — кидання монети, випадкова подія — випадання герба;

випробування — участь у грі «Російське лото», випадкове подія — виграш;

випробування — стрибок з парашутом, випадкова подія — удале приземлення;

випробування — народження дитини, випадкова подія — стать дитини — чоловіча;

випробування — спостереження за погодою протягом дня, випадкова подія — протягом дня був дощ.

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

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

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

Стійкість відносної частоти була виявлена й багаторазово підтверджена експериментально натуралістами в 17−19 століттях. Найбільш вражаючим є результат К. Пирсона, що кидав монету 12 000 разів, потім здійснив ще одну серію кидань — 24 000 разів. У цих серіях він підраховував кількість випадань герба й одержав значення відносної частоти для нього 0,5016 й 0,5005, що відрізняються друг від друга на 0,0011.

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

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

Спочатку визначимо ймовірність регулярної випадкової події як число, біля якого коливається відносна частота в довгих серіях випробувань. Потім уведемо поняття рівноможливості, рівноймовірності двох подій. Зміст цього поняття ясний інтуїтивно, ціль введення — ми хочемо визначити математично поняття ймовірності зводячи його до більш простого не обумовленого поняття рівноможливості. Наявність рівноймовірності деяких подій що є результатами деякого випробування встановлюється з «загальних міркувань», не доводиться математично й не може бути доведено, не має потреби в доказі як первинне. Наприклад, при киданні гральної кістки випадання 1, 2, …, 6 очків уважають подіями рівноймовірності (або «майже» рівноймовірності) виходячи з передбачуваної фізичної однорідності матеріалу кості й геометричної правильності, тобто вважаючи кістку ідеальним кубом. Якщо в результаті випробування можливе настання рівноможливих подій, ніякі дві з яких не можуть наступити одночасно, то ймовірність кожного із цих подій визначається як, а самі події називаються елементарними подіями або елементарними результатами.

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

Це і є формула класичної ймовірності, яку ми будемо надалі використати в наших дослідженнях.

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

2.4. Алгоритми генерації псевдовипадкових чисел

Метод середини квадрата

Першим алгоритмічний метод одержання рівномірно розподілених псевдовипадкових чисел запропонував Джон фон Нейман (один з основоположників кібернетики). Метод одержав назву «метод середини квадрата».

Суть методу: попереднє випадкове число зводиться у квадрат, а потім з результату витягаються середні цифри.

Наприклад:

(2.1)

і т.д.

Як видно метод середини квадрата досить добре повинен «перемішувати» попереднє число. Однак він має недоліки:

· якщо який-небудь член послідовності виявиться рівним нулю, то всі наступні члени також будуть нулями;

· послідовності мають тенденцію «зациклюватися», тобто зрештою, утворять цикл, що повторюється нескінченне число раз.

Властивість «зациклюватися» стосується всіх послідовностей, побудованих по рекурентній формулі x_i+1=f (x_i). Повторюваний цикл називається періодом. Довжина періоду в різних послідовностей різна. Чим період більше, тим краще.

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

Деякі вчені експериментували з методом середин квадратів на початку 50-х років. Працюючи із чотиризначними числами замість восьмизначних, Дж.Е. Форсайт випробував 16 різних початкових значень і виявив, що 12 з них приводять до циклічних послідовностей, що закінчуються циклом 6100. 2100, 4100, 8100, 6100…, у той час як два з них приводять до послідовностей, що вироджується в нульові.

Більш інтенсивні дослідження, головним чином у двійковій системі числення, провів Н. К. Метрополис. Він показав, що якщо використати 20-розрядне число, то послідовність випадкових чисел, отримана методом середин квадратів, вироджується в 13 різних циклів, причому довжина найбільшого періоду дорівнює 142.

Лінійний конгруентний метод

У цей час найбільш популярними генераторами випадкових чисел є генератори, у яких використається схема, запропонована Д. Г. Лехмером в 1949 році - лінійний конгруентний метод.

Виберемо чотири «чарівних числа»:

— m, модуль; 0 < m;

— а, множник; 0 < a < m;

— с, приріст; 0 < з < m;

— X₀, початкове значення; 0 < X₀ < m.

Потім одержимо бажану послідовність випадкових чисел (Х_n), маючи на увазі

X_n+1 = (а* X_n+ с) mod m, n > 0. (2.2)

Ця послідовність називається лінійною конгруентною послідовністю. Одержання залишків по модулю m почасти нагадує зумовленість, коли кулька попадає в осередок колеса рулетки. Наприклад, для m = 10 й X₀ = а = с = 7 одержимо послідовність:

7,6,9,0,7,6,9,0,…. (2.3)

Як показує цей приклад, така послідовність не може бути «випадковою» при деяких наборах чисел m, а, с і Х₀. У прикладі ілюструється той факт, що конгруентна послідовність завжди утворить петлі, тобто обов’язково існує цикл, що повторюється нескінченне число раз. Ця властивість є загальною для всіх послідовностей виду Х_n+1 = f (Х_n), де f перетворить кінцеву множину саме в себе.

Цикли, що повторюються, називаються періодами; довжина періоду послідовності (2.3) дорівнює 4. Безумовно, послідовності, які ми будемо використати, мають відносно довгий період.

Заслуговує на увагу випадок, коли с = 0, тому що числа, що генеруються, будуть мати менший період, чим при с? 0. Ми переконаємося надалі, що обмеження с = 0 зменшує довжину періоду послідовності, хоча при цьому усе ще можливо зробити період досить довгим. В оригінальному методі, запропонованому Д. Г. Лехмером, с вибиралося рівним нулю, хоча він і допускав випадок, коли с? 0, як один з можливих. Той факт, що умова с? 0 може приводити до появи більш довгих періодів, був установлений В. Е. Томсоном (W. Е. Thomson) і незалежно від нього А. Ротенбергом (А. Rotenberg). Багато авторів називають лінійну конгруентну послідовність при с = 0 мультиплікативним конгруентним методом, а при с? 0 — змішаним конгруентним методом. Для спрощення формул уводимо константу: b = а-1.

Можна відразу відкинути випадок, коли а = 1, при якому послідовність Х_n може бути представлена у вигляді Х_n = (Х₀ + с) mod m і поводиться явно не як випадкова послідовність. Випадок, коли а = 0 навіть гірше. Отже, для практичних цілей припускаємо, що:

а>2, b>1. (2.4)

Зараз можна узагальнити формулу (2.2):

(2.5)

де (n + k) — й член виражається безпосередньо через n-й.

Лінійний конгруентний метод застосовується в простих випадках і не має криптографічну стійкість. Входить у стандартні бібліотеки різних компіляторів.

При практичній реалізації лінійного конгруентного методу вигідно вибирати m = 2^e, де e — число біт у машинному слові, оскільки це дозволяє позбутися відносно повільної операції приведення по модулю. Машинне слово — машиннозалежна й платформозалежна величина, вимірювана в бітах або байтах, рівна розрядності регістрів процесора й/або розрядності шини даних.

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

Таблиця 2.1. Параметри лінійних конгруентних генераторів

RANDU — сумно відомий лінійний конгруентний генератор псевдовипадкових чисел, що ввійшов у вживання в 1960;х. Він визначається рекурентним співвідношенням:

(2.6)

де V₀ — непарне.

Псевдовипадкові числа обчислюються в такий спосіб:

(2.7)

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

Підставою для вибору параметрів генератора послужило те, що в рамках цілочисельної 32-бітної машинної арифметики операції по модулі 2³¹, зокрема, множення довільного числа на 65 539 = 2¹⁶ + 3, виконуються ефективно. У той же час, такий вибір володіє й принциповим недоліком. Розглянемо наступне вираження (будемо думати, що всі операції виконуються по модулю 2³¹).

(2.8),

звідки, розкривши квадратичний співмножник, одержуємо:

(2.9),

що, у свою чергу, показує наявність лінійної залежності (а отже, і повної кореляції) між трьома сусідніми елементами послідовності:

(2.10)

Метод Фібоначчі із запізненням

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

У зв’язку із цим лінійний конгруентний алгоритм поступово втратив свою популярність і його місце зайняло сімейство алгоритмів Фібоначчі, які можуть бути рекомендовані для використання в алгоритмах, критичних до якості випадкових чисел. В англомовній літературі датчики Фібоначчі такого типу називають звичайно «Subtract-with-borrow Generators» (SWBG).

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

Один із широко розповсюджених датчиків Фібоначчі заснований на наступній ітеративній формулі:

(2.11),

де Xk — речовинні числа з діапазону (0,1), a, b — цілі позитивні числа, називані лагами. Для роботи датчику Фібоначчі потрібно знати max {a, b} попередніх генерованих випадкових чисел. При програмній реалізації для зберігання генерованих випадкових чисел використається кінцева циклічна черга на базі масиву. Для старту датчику Фібоначчі потрібно max {a, b} випадкових чисел, які можуть бути генеровані простим конгруентним датчиком.

Лаги a й b — «магічні» й їх не слід вибирати довільно. Рекомендуються вибирати наступні значення лагів: (a, b)=(55,24), (17,5) або (97,33). Якість одержуваних випадкових чисел залежить від значення константи a. Чим воно більше, тим вище розмірність простору, у якому зберігається рівномірність випадкових векторів, утворених з отриманих випадкових чисел. У той же час, зі збільшенням величини константи a збільшується об'єм використовуваної алгоритмом пам’яті.

Значення (a, b) = (17,5) можна рекомендувати для простих додатків, що не використовують вектори високої розмірності з випадковими компонентами. Значення (a, b) = (55,24) дозволяють одержувати числа, задовільні для більшості алгоритмів, вимогливих до якості випадкових чисел. Значення (a, b) = (97,33) дозволяють одержувати дуже якісні випадкові числа й використаються в алгоритмах, що працюють із випадковими векторами високої розмірності. Описаний датчик Фібоначчі випадкових чисел (з лагами 20 й 5) використається в широко відомій системі Matlab.

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

(2.12),

де е - число бітів у мантисі дійсного числа.

Алгоритм Блюма — Блюма — Шуба

Цей генератор псевдовипадкових чисел був запропонований в 1986 році Ленор Блюм, Мануелем Блюмом і Майклом Шубом.

Математичне формулювання алгоритму виглядає в такий спосіб:

(2.13)

де M = p*q є добутком двох більших простих p й q. На кожному кроці алгоритму вихідні дані виходять із x_n шляхом узяття або біта парності, або одного або більше найменш значимого біту x_n.

Два простих числа, p й q, повинні бути обоє порівнянні з 3 по модулю 4 (це гарантує, що кожне квадратичне відхилення має один квадратний корінь, що також є квадратичним відхиленням) і найбільший загальний дільник НЗД повинен бути малий (це збільшує довжину циклу):

(2.14)

Цікавою особливістю цього алгоритму є те, що для одержання x_n необов’язково обчислювати всі n-1 попередніх чисел, якщо відомо початковий стан генератора x₀ і числа p й q, n-не значення може бути обчислене «прямо» використовуючи формулу:

(2.15)

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

Вихор Мерсенна

Із сучасних ГПВЧ широке поширення одержав вихор Мерсенна, запропонований в 1997 році Мацумото й Нишимурой. Їхня робота ґрунтується на властивостях простих чисел Мерсенна (звідси назва) і забезпечує швидку генерацію високоякісних псевдовипадкових чисел.

Перевагами цього методу є колосальний період (219 937−1), рівномірний розподіл в 623 вимірах (лінійний конгруентний метод дає більш-менш рівномірний розподіл від сили в 5 вимірах), швидка генерація випадкових чисел (в 2−3 рази швидше, ніж стандартні ГПВЧ, що використають лінійний конгруентний метод). Однак існують складні алгоритми, що розпізнають послідовність, породжувану за допомогою вихрячи Мерсенна як невипадкову. Це робить вихор Мерсенна невідповідним для використання в криптографії.

Вихор Мерсенна є вітковим регістром зрушення з узагальненою віддачею (twisted generalised feedback shift register, TGFSR). «Вихор» — це перетворення, що забезпечує рівномірний розподіл псевдовипадкових чисел в 623 вимірах. Тому кореляція між послідовними значеннями у вихідній послідовності алгоритму «Вихор Мерсенна» дуже мала.

Існують ефективні реалізації алгоритму «Вихор Мерсенна», що перевершують по швидкості багато стандартні ГПВЧ (зокрема, в 2−3 рази швидше лінійних конгруентних генераторів). Вихор Мерсенна реалізований у бібліотеці gLib і стандартних бібліотеках для PHP, Python і Рубі.

Генеровані алгоритмом «Вихор Мерсенна» псевдовипадкові числа успішно проходять тести DIEHARD, що говорить про їх гарні статистичні властивості.

2.5 Статистичні критерії оцінки якості алгоритмів

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

Якщо дати навмання обраній людині олівець і папір і попросити її написати 100 десяткових цифр, т о дуже мало шансів, що буде отриманий задовільний результат. Люди прагнуть уникати дій, що приводять до результатів, які здаються невипадковими, таким, наприклад, як поява пари рівних суміжних цифр (хоча приблизно одна з 10 цифр повинна рівнятися попередньої). І, якщо показати тій же людині таблицю дійсно випадкових чисел, вона. імовірно, скаже, що ці числа не випадкові. Вона помітить багато гаданих закономірностей.

Теоретична статистика надає деякі кількісні міри випадковості. Існує буквально нескінченне число критеріїв, які можна використати для перевірки того, чи буде послідовність випадковою. Обговоримо критерії, на наш погляд, найбільш корисні, найбільш повчальні й найбільш пристосовані до обчислень на комп’ютерах.

Якщо критерії 1, 2,…, Т_п підтверджують, що послідовність поводиться випадковим образом, це ще не означає, загалом кажучи, що перевірка за допомогою Т_п+1 — го критерію буде успішною. Однак кожна успішна перевірка дає усе більше й більше впевненості у випадковості послідовності. Звичайно до послідовності застосовується біля напівдюжини статистичних критеріїв, і якщо вона задовольняє цим критеріям, то послідовність уважається випадковою (це презумпція невинності до доказу провини).

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

Тести Diehard — це набір статистичних тестів, заснованих на емпіричних критеріях, які призначені для виміру якості набору випадкових чисел. Вони були розроблені Джорджем Марсалья (George Marsaglia) протягом декількох років і вперше опубліковані на CD-ROM, присвяченому випадковим числам. Разом вони розглядаються як один з найбільш строгих відомих наборів тестів.

Далі надамо короткий опис тестів, що входять у набір.

Дні народження (Birthday Spacings) — вибираються випадкові точки на великому інтервалі. Відстані між крапками повинні бути асимптотическі розподілені по Пуассону. Назва цей тест одержала на основі парадокса днів народження.

Парадокс днів народження — твердження, що якщо дано групу з 23 або більше людин, то ймовірність того, що хоча б у двох з них дні народження (число й місяць) збіжаться, перевищує 50%. Для групи з 60 або більше людин імовірність збігу днів народження хоча б у двох її членів становить більше 99%, хоча 100% вона досягає, тільки коли в групі не менш 366 чоловік (з урахуванням високосних років — 367).

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

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

Пересічні перестановки (Overlapping Permutations) — аналізуються послідовності п’яти послідовних випадкових чисел. 120 можливих перестановок повинні виходити зі статистично еквівалентною ймовірністю.

Ранги матриць (Ranks of matrices) — вибираються деяка кількість біт з деякої кількості випадкових чисел для формування матриці над {0,1}, потім визначається ранг матриці. Підраховуються ранги.

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

Мавпячі тести (Monkey Tests) — послідовності деякої кількості біт інтерпретуються як слова. Уважаються пересічні слова в потоці. Кількість «слів», які не з’являються, повинні задовольняти відомому розподілу. Назва цей тест одержала на основі теореми про нескінченну кількість мавп.

Текст теореми про нескінченних мавп звучить (в одному з багатьох варіантів) так: «Якщо ви посадите нескінченну кількість мавп друкувати на друкарських машинках, те одна з них обов’язково надрукує який-небудь твір Вільяма Шекспіра». Існують варіації теореми з обмеженою кількістю мавп і нескінченним часом, по суті, що є тією же самою теоремою, тому що на виході виходить нескінченна кількість мавпо-часів.

Якщо перенести дані міркування в доступний для огляду масштаб, то теорема буде говорити — якщо протягом тривалого часу випадковим образом стукати по клавіатурі, то серед тексту, що набирає, будуть виникати осмислені слова, словосполучення й навіть речення.

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

Підрахунок одиничок (Count the 1's) — уважаються одиничні біти в кожному з наступний або обраних байт. Ці лічильники перетвориться в «літери», і вважаються випадки «слів» з п’яти літер.

Тест на паркування (Parking Lot Test) — випадково розміщаються одиничні окружності у квадраті 100×100. Якщо окружність перетинає вже існуючу, спробувати ще. Після 12 000 спроб, кількість успішно «припаркованих» окружностей повинне бути нормально розподіленою.

Тест на мінімальну відстань (Minimum Distance Test) — 8000 крапок випадково розміщаються у квадраті 10 000×10 000, потім знаходиться мінімальна відстань між будь-якими парами. Квадрат цієї відстані повинен бути експоненціально розподілений з деякою медіаною.

Тест випадкових сфер (Random Spheres Test) — випадково вибираються 4000 точок у кубі з ребром 1000. У кожній точці міститься сфера, чий радіус є мінімальною відстанню до іншої крапки. Мінімальний об'єм сфери повинен бути експоненціально розподілений з деякою медіаною.

Тест стиску (The Squeeze Test) — 231 множиться на випадкові дійсні числа в діапазоні (0,1) доти, поки не вийде 1. Повторюється 100 000 разів. Кількість дійсних чисел необхідних для досягнення 1 повинне бути розподілено певним чином.

Тест пересічних сум (Overlapping Sums Test) — генерується довга послідовність на (0,1). Додаються послідовності з 100 послідовних дійсних чисел. Суми повинні бути нормально розподілені з характерною медіаною й сигмою.

Тест послідовностей (Runs Test) — генерується довга послідовність на (0,1). Підраховуються висхідні й спадні послідовності. Числа повинні задовольняти деякому розподілу.

Тест гри в кістки (The Craps Test) — грається 200 000 ігор у кістки, підраховуються перемоги й кількість кидків у кожній грі. Кожне число повинне задовольняти деякому розподілу.

3. Дослідження методів тестування та оцінки стійкості паролів

3.1 Парольна система як захист від несанкціонованого доступу

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

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

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

При цьому можуть бути використані наступні підходи.

1. Прямий перебір. Перебір всіх можливих поєднань допустимих в паролі символів.

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

3. Метод соціальної інженерії. Заснований на припущенні, що користувач використовував в якості пароль особисті відомості, такі як його ім'я або прізвище, дата народження і т. п.

Парольна система як невід'ємна складова підсистеми управління доступом системи захисту інформації (СЗІ) є частиною «переднього краю оборони» всієї системи безпеки. Тому парольна система стає одним з перших об'єктів атаки при вторгненні зловмисника в захищену систему.

Підсистема управління доступом СЗІ має на увазі наступні поняття.

Ідентифікатор доступу — унікальна ознака суб'єкта або об'єкту доступу.

Ідентифікація — привласнення суб'єктам і об'єктам доступу ідентифікатора і (або) порівняння ідентифікатора, що пред’являється, з переліком привласнених ідентифікаторів.

Пароль — ідентифікатор суб'єкта доступу, який є його (суб'єкта) секретом.

Аутентифікація — перевірка приналежності суб'єкту доступу пред’явленого їм ідентифікатора; підтвердження достовірності.

Можна також зустріти і такі тлумачення термінів ідентифікатор і пароль користувача.

Ідентифікатор — деяка унікальна кількість інформації, що дозволяє розрізняти індивідуальних користувачів парольної системи (проводити їх ідентифікацію). Часто ідентифікатор також називають ім'ям користувача або ім'ям облікового запису користувача.

Пароль — деяка секретна кількість інформації, відома тільки користувачу і парольній системі, що пред’являється для проходження процедури аутентифікації.

Обліковий запис — сукупність ідентифікатора і пароля користувача.

Одним з найбільш важливих компонентів парольної системи є база даних облікових записів (база даних системи захисту). Можливі наступні варіанти зберігання паролів в системі:

· у відкритому вигляді;

· у вигляді хэш-значень (hash (англ.) — суміш, мішанина);

· зашифрованими на деякому ключі.

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

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

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

При шифруванні паролів особливе значення має спосіб генерації і зберігання ключа шифрування бази даних облікових записів. Можливі наступні варіанти:

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

· ключ генерується програмно і зберігається на зовнішньому носії, з якого прочитується при кожному запуску;

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

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

Як пароль може потрапити до рук зловмисника? Найбільш реальними виглядають наступні випадки:

· записаний нами пароль був знайдений зловмисником;

· пароль був підглянений зловмисником при введенні легальним користувачем;

· зловмисник дістав доступ до бази даних системи захисту.

Заходи протидії першим двом небезпекам очевидні.

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

З бази даних облікових записів пароль може бути відновлений різними способами: атакою по словнику, послідовним (повним) перебором і гібридом атаки по словнику і послідовного перебору.

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

Послідовний перебір всіх можливих комбінацій (brute force (англ.) — груба сила, рішення «в лоб») використовує набір символів і обчислює хеш-значення для кожного можливого пароля, складеного з цих символів. При використанні цього методу пароль завжди буде визначений, якщо складові його символи присутні у вибраному наборі. Єдиний недолік цього методу — велика кількість часу, який може знадобитися на визначення пароля. Чим більша кількість символів (букв різного регістра, цифр, спецсимволів) міститься у вибраному наборі, тим більше часу може пройти, поки перебір комбінацій не закінчиться.

При відновленні паролів гібридної атаки по словнику і послідовного перебору до кожного слова або модифікації слова словника додаються символи справа та/або зліва (123parol). Крім цього може здійснюватися перевірка використання: імен користувачів як паролів; повторення слів (dogdog); зворотного порядку символів слова (elpoep); транслітерації букв (parol); заміну букв кирилиці латинською розкладкою (gfhjkm).

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

Який пароль можна однозначно назвати слабким в усіх відношеннях (за винятком можливості запам’ятати)? Типовий приклад: пароль з невеликої кількості (до 5) символів/цифр. За деякими даними, з 967 паролів одного із зламаних поштових серверів мережі Інтернет 335 (майже третина) складалася виключно з цифр.

Кількість паролів, що включають букви і цифри виявилося рівним 20. Решта паролів складалася з букв в основному в нижньому регістрі за рідкісним виключенням (в кількості 2 паролів) тих, що включають спецсимволи («*», «_»). Символ «_», проте, часто зустрічався в іменах користувачів. У 33 випадках ім'я і пароль користувача співпадали. Найпопулярнішим виявився пароль 123 (зустрічався 35 разів, майже кожен 27 пароль). На другому місці пароль qwerty (20 паролів). Далі слідують: 777 (18 разів), 12 (17 разів), hacker (14 разів) і 1, 11 111 111, 9128 (по 10 разів). 16 паролів складалися з одного символу / цифри.

Підвищення вимог до пароля виникає із-за ступеня його важливості. Прикладом «важливого пароля» служить пароль, вживаний для роботи в автоматизованих системах, що обробляють інформацію обмеженого доступу (державна таємниця, конфіденційна інформація).

3.2 Ентропія як міра стійкості паролів

Мірою стійкості паролів традиційно є ентропія — міра невизначеності, вимірювана звичайно в бітах. Ентропія в 1 біт відповідає невизначеності вибору з двох паролів, в 2 біта — з 4 паролів, в 3 біта — з 8 паролів і т.д. Ентропія в N біт відповідає невизначеності вибору з паролів. У разі використання випадкових паролів (наприклад, випадкових чисел, що згенеровані за допомогою генератора) ентропія обчислюється досить просто: вона залежить від кількості можливих паролів для заданих параметрів. Так, для випадкового пароля завдовжки N символів, складеного з алфавіту, що містить M букв, ентропія буде рівна:

(3.1)

Значення ентропії для деяких довжин паролів і наборів символів представлені в таблиці 3.1.

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

· ентропія першого символу пароля складає 4 біта;

· ентропія наступних семи символів пароля складає 2 біта на символ;

· ентропія символів з 9-го по 20-го складає 1,5 біта на символ;

· всі подальші символи мають ентропію 1 біт на символ;

· якщо пароль містить символи верхнього регістра і неалфавітні символи, то його ентропія збільшується на 6 біт.

Таблиця 3.1. Значення ентропії для деяких довжин паролів

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

Основний спосіб протидії злому паролів — штучно уповільнити процедуру їх перевірки. Дійсно, чи займе перевірка 10 наносекунд або 10 мілісекунд — для користувача різниця буде непомітною, а з погляду злому швидкість впаде дуже істотно — з 100 мільйонів до 100 паролів в секунду. Уповільнення звичайно досягається за рахунок багатократного обчислення криптографічних функцій, причому ці обчислення побудовані так, щоб атакуюча сторона не могла перевірити пароль без повторення обчислень (тобто недостатньо просто додати виклик Sleep в процедурі перевірки пароля). Вперше такий варіант був запропонований в 1997 році в роботі «Secure Applications of Low-Entropy Keys».

Системи, що реалізовують подібні уповільнення, збільшують ефективну ентропію пароля на величину, де C — кількість ітерацій при обчисленні кри-птографічного перетворення. Приклади подібних систем приведені в таблиці 3.2.

Таблиця 3.2. Системи, що збільшують ефективну ентропію пароля

Як було сказано вище, системи можуть містити помилки, що знижують їх стійкість. Наприклад, для шифрування даних може використовуватися алгоритм з ключем недостатньої довжини або сама процедура перетворення пароля може бути ненадійною. Так, всі версії Microsoft Word і Excel, починаючи з 97 і до 2003 включно, для шифрування документів за умовчанням використовують потоковий алгоритм RC4 з довжиною ключа 40 біт.