Дипломная работа: Розробка імовірнісної моделі криптографічних протоколів

Імовірнісний простір повинен містити випадковий вибір, зроблений Учасником і Зловмисником, а також внутрішню випадкову операцію алгоритму шифрування. Відзначимо, що відповідь Зловмисника залежить не тільки від зашифрованого тексту оклику с*, але і від двох підібраних початкових повідомлень (m0, m1). Тільки тому його відповідь можна вважати результатом «осмисленого вгадування» («educated guess»).

Слід відмітити, що Зловмисник має додаткову можливість для того, щоб поліпшити результати свого вгадування: Учасник підкида деальну монету. Формула обчислення переваги (2.1.1) не указує явно на те, як Зловмисник може скористатися цим фактом, хоча неявно відомо, що кожна з імовірності, що входить у формулу (2.1.1), ніколи не перевищить , наприклад, імовірность події с* = Yk(m0) складає рівно . Необхідно явно вказати, як саме Зловмисник використовує додатковий ключ у формулі обчислення переваги. Застосовуючи умовну імовірность і помічаючи, що імовірность обох результатів при підкиданні ідеальної монети рівна , можна переписати формулу (2.1.1) в наступному вигляді

Adv = |Prob[0 ¬ Зловмисник(с* = Yk(m0))] –

- Prob[0 ¬ Зловмисник(с*=Yk(m1))]|.                                             (2.2)

Згідно з правилами гри Зловмиснику не дозволяється давати відповіді, які відрізняються від 0 та 1, тому неправильна відповідь є подією, додатковою по відношенню до правильної відповіді. З цього випливає наступна формула

Adv = |Prob[0 ¬ Зловмисник(с* = Yk(m0))] –

- (1 – Prob[0 ¬ Зловмисник(с*=Yk(m0))] )|.

Тобто

       Prob[0 ¬ Зловмисник(с* = Yk(m0))] =  ± Adv.                                 (2.3)

Формула (2.3) часто застосовується для виразу переваги алгоритму при вгадуванн результатів підкидання ідеальної монети. Отже, якщо Adv = 0, то випадкова відповідь Зловмисника має такий самий розподіл, як і результати підкидання деальної монети. Проте слід враховувати, що перевага завжди більше нуля. Очевидно, що формула (2.1.3) також справедлива, якщо в результатах жеребкування всі нулі замінити одиницями.

З формули (2.3) виходить, що перевага Зловмисника ніколи не перевищує , оскільки імовірність завжди лежить в інтервалі [0,1]. Дійсно, якщо Учасник шифру обидва початкові тексти з імовірністю , перевагу Adv, що задана формулою (2.1), є різниця імовірност сумісних подій і ніколи не перевищує . Можна відмітити, що формула (2.1.3) виглядає так, ніби Учасник підкидає несиметричну монету, наприклад, Учасник з імовірністю  шифрує повідомлення m0 і з імовірністю  -  повідомлення m1.

Досліджувана криптосистема стійка по відношенню до ігрової атаки, якщо експеримент Yk(m0) не можливо відрізнити від експерименту Yk(m1). Це  означає, що при будь-якій значущій перевазі Adv не повинно снувати жодного поліноміального алгоритму розпізнавання. Інакше кажучи, перевага, з якою Зловмисник може розрізняти результати шифрування, повинна бути дуже малою величиною в порівнянні з параметром безпеки схеми шифрування, яким, як правило, є довжина ключа шифрування. Можна вважати, що перевага будь-якого поліноміального алгоритму розпізнавання, що вживається Зловмисником, задається функцією, що повільно росте, залежною від об'єму обчислювальних ресурсів. Тут термін «повільно росте» означає, що, навіть якщо Зловмисник різко збільшить об'єм своїх обчислювальних ресурсів, перевага збільшиться украй трохи.

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

2.2. Стійкість криптографічних протоколів

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

-  використання слабких криптографічних алгоритмів і некоректна реалізація деяких його складових;

-  некоректна логіка роботи криптопротокола;

-  некоректне використання криптографічних алгоритмів.

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

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

-   атака з відомим ключем. Зловмисник, одержавши ключ попередньої сесії, намагається дізнатися ключ нової сесії;

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

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

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

-  підміна повідомлень. Проводиться шляхом заміни під час роботи криптопротокола повідомлень або даних.

Як приклад успішної атаки такого типу розглянемо криптопротокол розподілу секретних сеансових ключів між двома учасниками нформаційного обміну. Авторами цього методу є Нідхем і Шредер. Уразливість цього криптопротоколуа вперше була виявлена Денінгом і Сакко. Кожен учасник даного протоколу повинен розділити знання свого секретного ключа з сервером аутентифікації. Протокол складається з наступних кроків:

1. А → S: А, В, Na. Учасник А посилає запит серверу S, в якому він указує, що необхідно встановити сеанс зв'язку з учасником В. У даному запиті присутні наступні значення:

- А і В – імена або ідентифікатори учасників;

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

2. S → A: { Na, В, Кab, { Кab, А}Kbs}Kas.Сервер відповіда повідомленням, зашифрованим на секретному ключі сервер-учасник А (Кas), в якому знаходиться сеансовий ключ (Кab), а також ще одна копія цього ключа, зашифрованого на секретному ключі сервер-учасник В (Кbs).

3. А → B: { Кab, А}Кbs Учасник В розшифровує дане повідомлення, оскільки йому відомий ключ Кbs; в результаті він одержує ключ Кab.

4. B → A: {Nb}Kab. Дане повідомлення учасник В посилає для того, щоб переконатися, що А волод ключем Кab, і показати учаснику А своє знання Кab.

5.  А → B: {Nb – 1} Кab. Учасник А доводить своє володіння ключем Кab, і на цьому протокол закінчує свою роботу, в результаті учасники А і В одержують загальний секретний сеансовий ключ Кab.

Уразливість даного криптопротокола полягає в тому, що якщо сеансовий ключ К1ab з попередньої сесії був скомпрометований, то зловмисник (позначимо його через З), що дістав можливість контролю мережевого трафіку на кроці 3 нової (нескомпрометованої) сесії, перехоплює повідомлення (А → В: { Кab, A}Kbs) замість нього посилає повідомлення (З → В: { К1ab, A}Кbs). Учасник B відповідає повідомленням (B → A: {Nb}К1ab), вважаючи, що А бажає встановити з ним нову сесію з ключем К1ab. З, одержуючи дане повідомлення, розшифровує його і відправляє В повідомлення (З →  В: {Nb – 1}К1ab). Таким чином, З встановлю сесію з В від імені А.

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

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

Для прикладу проведемо доказ стійкості криптопротокола «уявний покер». Для початку необхідно розглянути сам протокол.

Для того, щоб зіграти в покер, гравці А і Б спочатку повинні чесно роздати карти. Слово «чесно» означає, що при роздач карт А і Б повинні дотримуватися чотирьох правил.

1. Всі карти повинні роздаватися з однаковою мовірністю (тобто рівномірно), причому одна і та ж карта не повинна опинитися у двох різних гравців одночасно.

2. А і Б повинні знати карти, якими вони володіють, а інші гравці не повинні знати, які карти знаходяться на руках х партнерів.

3. А і Б повинні підозрюватися в шахрайстві і порушенні правил протоколу.

4. А і Б повинні мати можливість перевіряти, чи чесно була зіграна попередня гра.

Ідея, що лежить в основі уявного покеру, поляга в застосуванні шифру, що володіє властивістю комутативності. Застосовуючи такий шифр, А і Б можуть двічі шифрувати повідомлення, використовуючи свої секретні ключі, і повинні двічі розшифровувати його. Хай

С = ЕХ( М) і М = DX(C)

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

                   М = DA(DB(EA(EB(M)))) = DB(DA(EB(EA(M)))).                         (2.4)

Іншими словами, вихідне повідомлення можна відновити шляхом подвійного розшифрування незалежно від порядку шифрування.

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

Протокол чесної роздачі карт при грі в уявний покер.

Попередні умови:

А і Б погодили комутативний шифр, що володіє властивістю (2.4), згенерували свої секретні ключі шифрування. Колода складається з трьох карт: М1, М2 і М3.

 Мета:

Чесна роздача по одній карті кожному гравцю за правилами 1 – 4  .

1.  А шифрує три карти таким чином: Сі = ЕА( М), де і = 1,2,3. Він посилає Б ці три зашифрован тексти у випадковому порядку. (Передача зашифрованих текстів у випадковому порядку еквівалентна перетасовуванню колоди.)

2.  Б випадковим чином витягує один із зашифрованих текстів. Позначимо його через С. Потім він двічі шифрує його як СС = ЕВ( С), випадковим чином витягує інший текст, позначений як С¢ , і посила зашифровані тексти СС і С¢  А. ( Символи СС позначають карту, що належить Б , а символ С¢ -  карту, видану А. Зашифрована карта, що залишилася, ігнорується.)

3.  А розшифровує тексти СС і С¢. Результат розшифрування тексту С¢  позначає його карту, а розшифрування тексту СС, що позначається як С¢¢ , - карту Б. Текст С¢¢  повертається Б.

4.  Б розшифровує текст С¢¢  і  узнає свою карту.

Аналіз стійкості.

Після виконання протоколу складається наступна ситуація.

 •  Оскільки на першому кроці А тасує колоду, обидва гравці з однаковою мовірністю одержують одну з карт, що належать множині {M1, M2, M3}. Потрібно звернути увагу на те, що А прагне добре перетасувати колоду, щоб Б не одержав переваги. Отже, перша умова чесно роздачі виконана.

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

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

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

Хай N - загальний модуль в криптосистемі RSA. А і Б знають розкладання числа N на множники. Позначимо через (еА, dA) показники ступенів, використані при шифруванні і розшифруванні А, а через (еВ, dВ) – показники, що вживаються Б. Знання розкладання числа N на прості множники дозволяє А (Б) знайти число еА  по заданому числу dA (число еВ – по заданому числу dВ) за допомогою порівняння

                                           еХ dХ = 1(mod j(N))                                           (2.5)

 де символ X позначає гравця А або В, j(N) – функція Ейлера. Для користувача X одержуємо наступні формули.

ЕХ( М)=( mod N),

DХ( М)= ( mod N).

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11