Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

SHA-1



План:


Введення

Secure Hash Algorithm 1 - алгоритм криптографічного хешування. Описаний в RFC 3174. Для вхідного повідомлення довільної довжини (максимум 2 ^ {64} -1 біт, що дорівнює 2 ексабайт) алгоритм генерує 160-бітне хеш-значення, зване також дайджестом повідомлення. Використовується в багатьох криптографічних додатках і протоколах. Також рекомендований в якості основного для державних установ в США. Принципи, покладені в основу SHA-1, аналогічні тим, які використовувалися Рональдом Рівестом при проектуванні MD4.


1. Історія

В 1993 NSA спільно з NIST розробили алгоритм безпечного хешування (зараз відомий як SHA-0) (опублікований в документі FIPS PUB 180) для стандарту безпечного хешування. Однак незабаром NSA відкликало дану версію, пославшись на виявлену ними помилку, яка так і не була розкрита. І замінило його виправленої версією, опублікованою в 1995 в документі FIPS PUB 180-1. Ця версія і вважається тим, що називають SHA-1. Трохи згодом, на конференції CRYPTO в 1998 два французьких дослідника представили атаку на алгоритм SHA-0, яка не працювала на алгоритмі SHA-1 Можливо, це і була помилка, відкрита NSA.


2. Опис алгоритму

Одна ітерація алгоритму SHA1

SHA-1 реалізує хеш-функцію, побудовану на ідеї функції стиснення. Входами функції стиснення є блок повідомлення довжиною 512 біт і вихід попереднього блоку повідомлення. Вихід являє собою значення всіх хеш-блоків до цього моменту. Іншими словами хеш блоку M_i дорівнює h_i = f (M_i, h_ {i-1}) . Хеш-значенням всього повідомлення є вихід останнього блоку.


2.1. Ініціалізація

Вихідне повідомлення розбивається на блоки по 512 біт в кожному. Останній блок доповнюється до довжини, кратної 512 біт. Спочатку додається 1, а потім нулі, щоб довжина блоку стала рівною (512 - 64 = 448) біт. У що залишилися 64 біта записується довжина вихідного повідомлення в бітах. Якщо останній блок має довжину більше 448, але менше 512 біт, то додаток виконується таким чином: спочатку додається 1, потім нулі аж до кінця 512-бітного блоку; після цього створюється ще один 512-бітний блок, який заповнюється аж до 448 біт нулями , після чого в решту 64 біта записується довжина вихідного повідомлення в бітах. Доповнення останнього блоку здійснюється завжди, навіть якщо повідомлення вже має потрібну довжину.

Ініціалізувалися п'ять 32-бітових змінних.

 A = a = 0x67452301 B = b = 0xEFCDAB89 C = c = 0x98BADCFE D = d = 0x10325476 E = e = 0xC3D2E1F0 

Визначаються чотири нелінійні операції і чотири константи.

F_t (B, C, D) = (B \ wedge C) \ vee (\ neg {B} \ wedge D)K_t = 0x5A827999 0 ≤ t ≤ 19
F_t (B, C, D) = B \ oplus C \ oplus DK_t = 0x6ED9EBA1 20 ≤ t ≤ 39
F_t (B, C, D) = (B \ wedge C) \ vee (B \ wedge D) \ vee (C \ wedge D)K_t = 0x8F1BBCDC 40 ≤ t ≤ 59
F_t (B, C, D) = B \ oplus C \ oplus DK_t = 0xCA62C1D6 60 ≤ t ≤ 79

2.2. Головний цикл

Головний цикл итеративно обробляє кожен 512-бітний блок. Ітерація складається з чотирьох етапів по двадцять операцій в кожному. Блок повідомлення перетвориться з 16 32-бітових слів M_i в 80 32-бітових слів W_j за наступним правилом:

W_t = M_t при 0 ≤ t ≤ 15 
W_t = ( W_t -3 \ OplusW_t -8 \ OplusW_t -14 \ OplusW_t -16) << 1 при 16 ≤ t ≤ 79

тут << - це циклічний зсув вліво

 для t від 0 до 79 
temp = (a << 5) + F_t (B, c, d) + e + W_t + K_t
e = d
d = c
c = b << 30
b = a
a = temp

Після цього a, b, c, d, e додаються до A, B, C, D, E відповідно. Починається наступна ітерація.

Підсумковим значенням буде об'єднання п'яти 32-бітових слів в одне 160-бітове хеш-значення.


2.3. Псевдокод SHA-1

Псевдокод алгоритму SHA-1 наступний:

 Зауваження: Всі використовувані змінні 32 біта.  Ініціалізація змінних:  h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0  Попередня обробка:  Приєднуємо біт '1 'до повідомлення Приєднуємо k бітів '0', де k найменше число ≥ 0 таке, що довжина отриманого повідомлення (в бітах) порівнянна по модулю 512 з 448 (length mod 512 == 448) Додаємо довжину вихідного повідомлення (до попередньої обробки) як ціле 64-бітове Big-endian число, в бітах.  У процесі повідомлення розбивається послідовно по 512 біт:  for перебираємо всі такі частини розбиваємо цей шматок на 16 частин, слів по 32-біта w [i], 0 <= i <= 15  16 слів по 32-біта доповнюються до 80 32-бітових слів:  for i from 16 to 79 w [i] = (w [i-3] xor w [i-8] xor w [i-14] xor w [i-16])  циклічний зсув вліво 1  Ініціалізація хеш-значень цієї частини:  a = h0 b = h1 c = h2 d = h3 e = h4  Основний цикл:  for i from 0 to 79 if 0 ≤ i ≤ 19 then f = (b and c) or ((not b) and d) k = 0x5A827999 else if 20 ≤ i ≤ 39 f = b xor c xor dk = 0x6ED9EBA1 else if 40 ≤ i ≤ 59 f = (b and c) or (b and d) or (c and d) k = 0x8F1BBCDC else if 60 ≤ i ≤ 79 f = b xor c xor dk = 0xCA62C1D6 temp = (a leftrotate 5) + f + e + k + w [i] e = dd = cc = b leftrotate 30 b = aa = temp  Додаємо хеш-значення цієї частини до результату:  h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e  Підсумкове хеш-значення:  digest = hash = h0 append h1 append h2 append h3 append h4 

Замість оригінальної формулювання FIPS PUB 180-1 наведені такі еквівалентні вирази і можуть бути використані на комп'ютері f в головному циклі:

 (0 ≤ i ≤ 19): f = d xor (b and (c xor d))  (Альтернатива 1)  (0 ≤ i ≤ 19): f = (b and c) xor ((not b) and d)  (Альтернатива 2)  (0 ≤ i ≤ 19): f = (b and c) + ((not b) and d)  (Альтернатива 3)  (40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))  (Альтернатива 1)  (40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))  (Альтернатива 2)  (40 ≤ i ≤ 59): f = (b and c) + (d and (b xor c))  (Альтернатива 3)  (40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (Альтернатива 4) 

3. Приклади

Нижче наведені приклади хешів SHA-1. Для всіх повідомлень мається на увазі використання кодування UTF-8.

Хеш панграмми російською:

 SHA-1 ("У хащах півдня жив би цитрус? Так, але фальшивий екземпляр!") = 9e32295f 8225803b b6d5fdfc c0674616 a4413c1b 

Хеш панграмми англійською:

 SHA-1 ("The quick brown fox jumps over the lazy dog") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 
 SHA-1 ("sha") = d8f45903 20e1343a 915b6394 170650a8 f35d6926 

Невелика зміна вихідного тексту (одна буква у верхньому регістрі) призводить до сильного зміни самого хешу. Це відбувається внаслідок лавинного ефекту.

 SHA-1 ("Sha") = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640 

Навіть для порожнього рядка обчислюється нетривіальне хеш-значення.

 SHA-1 ("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709 

4. Криптоаналіз

Криптоаналіз хеш-функцій спрямований на дослідження вразливості до різного виду атакам. Основні з них:

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

При вирішенні методом "грубої сили" :

  • друга задача вимагає 2160 операцій.
  • перша ж вимагає в середньому 2 160/2 = 2 80 операцій, якщо використовувати атаку Днів народження.

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

У січні 2005 Vincent Rijmen і Elisabeth Oswald опублікували повідомлення про атаку на усічену версію SHA-1 (53 раунду замість 80), яка дозволяє знаходити колізії менше, ніж за 2 80 операцій.

У лютому 2005 Сяоюнь Ван, Іцюнь Ліза Інь і Хунбо Юй (Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu) представили атаку на повноцінний SHA-1, яка вимагає менше 2 69 операцій.

Про метод автори пишуть:

Ми представляємо набір стратегій і відповідних методик, які можуть бути використані для усунення деяких важливих перешкод у пошуку колізій у SHA-1. Спочатку ми шукаємо близькі до колізії диференціальні шляху, які мають невеликий "вага Хаммінга" в "векторі перешкод", де кожен 1-біт представляє 6-крокову локальну колізію. Потім ми відповідним чином коректуємо диференціальний шлях з першого етапу до іншого прийнятного диференціального шляху, щоб уникнути неприйнятних послідовних і усічених колізій. Врешті-решт ми перетворимо два одноблокових близьких до колізії диференціальних шляху в один двухблоковий колізійний шлях з подвоєною обчислювальною складністю. [1]

Оригінальний текст (Англ.)

We introduce a set of strategies and corresponding techniques that can be used to remove some major obstacles in collision search for SHA-1. Firstly, we look for a near-collision differential path which has low Hamming weight in the "disturbance vector" where each 1-bit represents a 6-step local collision. Secondly, we suitably adjust the differential path in the first round to another possible differential path so as to avoid impossible consecutive local collisions and truncated local collisions. Thirdly, we transform two one-block near-collision differential paths into a twoblock collision differential path with twice the search complexity.

Також вони заявляють:

Зокрема, наш аналіз заснований на оригінальній диференціальної атаці на SHA-0, "near-collision" атаці на SHA-0, мультіблоковой методикою, а також методикам модифікації початкового повідомлення, використаних при атаках пошуку колізій на HAVAL-128, MD4, RIPEMD і MD5.

Оригінальний текст (Англ.)

In particular, our analysis is built upon the original differential attack on SHA-0, the near collision attack on SHA-0, the multi-block collision techniques, as well as the message modification techniques used in the collision search attacks on HAVAL-128 , MD4, RIPEMD and MD5.

Стаття з описом алгоритму була опублікована в серпні 2005 на конференції CRYPTO.

У цій же статті автори опублікували атаку на усічений SHA-1 (58 раундів), яка дозволяє знаходити колізії за 2 33 операцій.

У серпні 2005 на CRYPTO 2005 ці ж фахівці представили покращену версію атаки на повноцінний SHA-1, з обчислювальною складністю в 2 63 операцій. У грудні 2007 деталі цього поліпшення були перевірені Мартіном Кохраном.

Крістоф де Каньер і Крістіан Рехберг пізніше представили удосконалену версію атаки на SHA-1, за що були удостоєні нагороди за кращу статтю на конференції ASIACRYPT 2006. Ними була представлена ​​двох-блокова колізія на 64-раундовий алгоритм з обчислювальною складністю близько 2 35 операцій. [2]

Існує масштабний дослідницький проект, що стартував в технологічному університеті австрійського міста Грац, який: "... використовує комп'ютери, з'єднані через Інтернет, для проведення досліджень в області криптоаналізу. Ви можете взяти участь у проекті завантаживши та запустивши безкоштовну програму на своєму комп'ютері. " [3]

Хоча теоретично SHA-1 вважається зламаним (кількість обчислювальних операцій скорочено в 2 80-63 = 131 000 разів), на практиці подібний злом нездійсненний, тому що займе п'ять мільярдів років.

Бурт Калінскі, голова дослідницького відділу в "лабораторії RSA" пророкує, що перша атака по знаходженню прообразу буде успішно здійснена в найближчі 5-10 років.

З огляду на те, що теоретичні атаки на SHA-1 виявилися успішними, NIST планує повністю відмовитися від використання SHA-1 в цифрових підписах. [4]

Через блокової і итеративной структури алгоритмів, а також відсутність спеціальної обробки в кінці хешування, все хеш-функції сімейства SHA уразливі до атак подовженням повідомлення та колізії при частковому хешуванні повідомлення. [5] Ці атаки дозволяють підробляти повідомлення, підписані тільки хешем - SHA (message | | key) або SHA (key | | message) - Шляхом подовження повідомлення та перерахунку хешу без знання значення ключа. Найпростішим виправленням, що дозволяє захиститися від цих атак, є подвійне хеширование - SHA_d (message) = SHA (SHA (0 ^ b | | message)) ( 0 ^ b - Блок нулів тієї ж довжини, що і блок хеш-функції).

2 листопада 2007 NIST анонсувало конкурс з розробки нового алгоритму SHA-3, який триватиме до 2012. [6]


5. Порівняння SHA-1 з іншими алгоритмами

5.1. Порівняння з MD5

І MD5, і SHA-1 є, по суті, поліпшеними продовженнями MD4.

Подібності:

  1. Чотири етапи.
  2. Кожна дія додається до раніше отриманого результату.
  3. Розмір блоку обробки рівний 512 біт.
  4. Обидва алгоритми виконують складання по модулю 2 32, вони розраховані на 32-бітну архітектуру.

Відмінності:

  1. У SHA-1 на четвертому етапі використовується та ж функція f, що і на другому етапі.
  2. В MD5 в кожній дії використовується унікальна прибавляемая константа. У SHA-1 константи використовуються повторно для кожної з чотирьох груп.
  3. У SHA-1 додана п'ята змінна.
  4. SHA-1 використовує циклічний код виправлення помилок.
  5. В MD5 чотири зсуву, використовувані на кожному етапі відрізняються від значень, використовуваних на попередніх етапах. В SHA на кожному етапі використовується постійне значення зсуву.
  6. В MD5 чотири різних елементарних логічних функції, в SHA-1 - три.
  7. В MD5 довжина дайджесту становить 128 біт, в SHA-1 - 160 біт.
  8. SHA-1 містить більше раундів (80 замість 64) і виконується на 160-бітному буфері в порівнянні з 128-бітовим буфером MD5. Таким чином, SHA-1 повинен виконуватися приблизно на 25% повільніше, ніж MD5 на тій же апаратурі.

Брюс Шнайер робить наступний висновок: "SHA-1 - це MD4 з додаванням розширює перетворення, додаткового етапу і поліпшеним лавинним ефектом. MD5 - це MD4 з поліпшеним бітовим хешуванням, додатковим етапом і поліпшеним лавинним ефектом. "


5.2. Порівняння з ГОСТ Р 34.11-94

Ряд відмінних особливостей ГОСТ Р 34.11-94 :

  1. При обробці блоків використовуються перетворення за алгоритмом ГОСТ 28147-89;
  2. Обробляється блок довжиною 256 біт, і вихідне значення теж має довжину 256 біт.
  3. Застосовані заходи боротьби проти пошуку колізій, заснованому на неповноту останнього блоку.
  4. Обробка блоків відбувається за алгоритмом шифрування ГОСТ 28147-89, який містить перетворення на S-блоках, що істотно ускладнює застосування методу диференціального криптоаналізу до пошуку колізій алгоритму ГОСТ Р 34.11-94. Це істотний плюс порівняно з SHA-1.
  5. Теоретична криптостойкость ГОСТ Р 34.11-94 дорівнює 2128, що у багато разів перевершує 2 80 для SHA-1.

5.3. Порівняння з іншими SHA

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

Варіації алгоритму Розмір вихідної хешу (біт) Проміжний розмір хешу (біт) Розмір блоку (біт) Максимальна довжина вхідного повідомлення (біт) Розмір слова (біт) Кількість раундів Використовувані операції Знайдені колізії
SHA-0 160 160 512 2 64 - 1 32 80 +, And, or, xor, rotl Є
SHA-1 160 160 512 2 64 - 1 32 80 +, And, or, xor, rotl 2 52 операцій
SHA-2 SHA-256/224 256/224 256 512 2 64 - 1 32 64 +, And, or, xor, shr, rotr Немає
SHA-512/384 512/384 512 1024 2128 - 1 64 80 +, And, or, xor, shr, rotr Немає

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

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

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

SHA-1 використовується в наступних програмах:

  • S / MIME - дайджести повідомлень.
  • SSL - дайджести повідомлень.
  • IPSec - для алгоритму перевірки цілісності в з'єднанні "точка-точка".
  • SSH - для перевірки цілісності переданих даних.
  • PGP - для створення електронного цифрового підпису.
  • Git - для ідентифікації кожного об'єкта по SHA-1-хешу від збереженої в об'єкті інформації.
  • Mercurial - для ідентифікації ревізій
  • BitTorrent - для перевірки цілісності даних, що завантажуються.

SHA-1 є основою блочного шифру SHACAL.


Примітки

  1. Finding Collisions in the Full SHA-1 - www.infosec.sdu.edu.cn / uploadfile / papers / Finding Collisions in the Full SHA-1.pdf (Англ.) . - Стаття китайських дослідників про злом SHA-1.
  2. Finding SHA-1 Characteristics: General Results and Applications - dx.doi.org/10.1007/11935230_1 (Англ.) .
  3. SHA-1 Collision Search Graz - boinc.iaik.tugraz.at (Англ.) . - Дослідницький проект технологічного університету Граца.
  4. NIST Comments on Cryptanalytic Attacks on SHA-1 - csrc.nist.gov / groups / ST / hash / statement.html (Англ.) . - Офіційний коментар NIST з приводу атак на SHA-1.
  5. Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering - www.schneier.com / book-ce.html (Англ.) . , John Wiley & Sons, 2010. ISBN 978-0-470-47424-2
  6. NIST Hash Competition - csrc.nist.gov/groups/SMA/ispab/documents/minutes/2008-06/HashCompetition-June2008_BBurr-JKelsey.pdf (Англ.) . - Конкурс на розробку SHA-3.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
SHA-2
© Усі права захищені
написати до нас