Портал освітньо-інформаційних послуг «Студентська консультація»

  
Телефон +3 8(066) 185-39-18
Телефон +3 8(093) 202-63-01
 (093) 202-63-01
 studscon@gmail.com
 facebook.com/studcons

<script>

  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){

  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),

  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)

  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

 

  ga('create', 'UA-53007750-1', 'auto');

  ga('send', 'pageview');

 

</script>

Хеш-функція

Предмет: 
Інформатика
Тип роботи: 
Курсова робота
К-сть сторінок: 
28
Мова: 
Українська
Оцінка: 

є маленький недолік. Припустимо, відомо, що програму доведеться перебрати усі слова довжиною в 8 символів, що складаються з маленьких і великих латинських букв. Скільки часу це займе? Скільки всього таких слів? На першому місці може стояти будь-який з 26 * 2 = 52 символів. На 2, 3, 4, 5, 6, 7 і 8 - теж 52. Значить, всього таких слів буде: 52 * 52 * 52 * 52 * 52 * 52 * 52 * 52 = 528 = 53 * 1012. А якщо використовуються не тільки латинські букви? То це ще більше. Перебір всіх варіантів на звичайному персональному комп'ютері займе дуже багато часу. В Інтернеті можна знайти сайти, які по введеному хешу видають рядок, для якої буде точно такий же хеш. Ці сайти використовують базу даних з заздалегідь прорахованим хешом. Але в базах зберігаються не всіхеши, а тільки самі використовувані. Так що рекомендується використовувати в якості пароля абсолютно випадкову послідовність символів[17].

На даний момент існують кілька видів «злому» хешів MD5 — підбору повідомлення із заданим хешем:
  • Перебір по словником
  • Brute-force
  • RainbowCrack
  • Колізія хеш-функції
При цьому методи перебору по словнику і brute-force можуть використовуватися для злому хешу інших хеш-функцій (з невеликими змінами алгоритму). На відміну від них, RainbowCrack вимагає попередньої підготовки райдужних таблиць, які створюються для заздалегідь певної хеш-функції. Пошук колізій специфічний для кожного алгоритму[18].
Коротко розглянемо ці види «злому»:
Перебір по словнику – атака на систему захисту, що використовує метод повного перебору (англ. brute-force) передбачуваних паролів, які використовуються для аутентифікації, здійснюваного шляхом послідовного перегляду всіх слів (паролів в чистому вигляді або їх зашифрованих образів) певного виду і довжини зі словника з метою подальшого злому системи і отримання доступу до секретної інформації. Даний захід, в більшості випадків, має негативний характер, що суперечить моральним і законодавчим нормам[19].
Повний перебір (або метод «грубої сили», англ. Bruteforce) - метод вирішення математичних задач. Відноситься до класу методів пошуку рішення вичерпання всіляких варіантів. Складність повного перебору залежить від кількості всіх можливих рішень задачі. Якщо простір рішень дуже велике, то повний перебір може не дати результатів протягом декількох років або навіть століть.
Будь-яке завдання з класу NP може бути вирішена повним перебором. При цьому, навіть якщо обчислення цільової функції від кожного конкретного можливого рішення задачі може бути здійснено за поліноміальний час, в залежності від кількості всіх можливих рішень повний перебір може зажадати експоненціального часу роботи.
У криптографії на обчислювальної складності повного перебору ґрунтується оцінка крипостійкості шифрів. Зокрема, шифр вважається крипостійким, якщо не існує методу «злому» істотно більш швидкого ніж повний перебір всіх ключів. Криптографічні атаки, засновані на методі повного перебору, є найбільш універсальними, але і найдовшими[20].
RainbowCrack - комп'ютерна програма для швидкого злому хешей. Є реалізацією техніки Філіпа Окслінаfastertime-memorytrade-off. Вона дозволяє створити базу предсгенерованихLanManagerхешів, за допомогою якої можна майже миттєво зламати практично будь-який алфавітно-цифровий пароль.Хоча створення райдужних таблиць займає багато часу і пам'яті, наступний злом проводиться дуже швидко. Основна ідея даного методу - досягнення компромісу між часом пошуку по таблиці і займаної пам'яттю[21].
Колізією хеш-функції H називається два різних вхідних блока даних x і y таких, що H (x) = H (y).
Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму. У деяких окремих випадках, коли безліч різних вхідних даних звичайно, можна задати ін'єкційних хеш-функцію, за визначенням не має колізій. Однак для хеш-функцій, що приймають вхід змінної довжини і повертають хеш постійної довжини (таких як MD5), колізії зобов'язані існувати, оскільки хоча б для одного значення хеш-функції відповідне йому безліч вхідних даних (повний прообраз) буде нескінченне - і будь-які два набори даних з цієї безлічі утворюють колізію[22].
 
3.2. Колізії MD5
 
Колізія хеш-функції - це отримання однакового значення функції для різних повідомлень і ідентичного початкового буфера. На відміну від колізій, псевдоколлізії визначаються як рівні значення хешу для різних значень початкового буфера, причому самі повідомлення можуть збігатися або відрізнятися. У MD5 питання колізій не вирішується[23].
У 1996 році Ганс Доббертін знайшов псевдоколлізіі в MD5, використовуючи певні ініціалізованні вектори, відмінні від стандартних. Виявилося, що можна для відомого повідомлення побудувати друге, таке, що воно буде мати такий же хеш, як і вихідне. C точки зору математики це означає: MD5 (IV, L1) = MD5 (IV, L2), де IV - початкове значення буфера, а L1 і L2 - різні повідомлення. Наприклад, якщо взяти початкове значення буфера:
A = 0x12AC2375
В = 0x3B341042
C = 0x5F62B97C
D = 0x4BA763E
і задати вхідний повідомлення
то, додаючи число 29 до певного 32-розрядного слова в блоковому буфері, можна отримати друге повідомлення з таким же хешем[24].
Тоді MD5 (IV, L1) = MD5 (IV, L2) = BF90E670752AF92B9CE4E3E1B12CF8DE.
У 2004 році китайські дослідники Ван Сяоюн (WangXiaoyun), Фен Денг (FengDengguo), Лай Сюецзя (LaiXuejia) і ЮйХунбо (YuHongbo) оголосили про виявлену ними уразливості в алгоритмі, що дозволяє за невеликий час (1 година на кластері IBM p690) знаходити колізії.
У 2005 році Ван Сяоюн і ЮйХунбо з університету Шаньдун в Китаї опублікували алгоритм, який може знайти дві різні послідовності в 128 байт, які дають однаковий MD5-хеш[25].
Кожен з цих блоків дає MD5-хеш, рівний 79054025255fb1a26e4bc422aef54eb4.
У 2006 році чеський дослідник Властіміл Клима опублікував алгоритм, що дозволяє знаходити колізії на звичайному комп'ютері з будь-яким початковим вектором (A, B, C, D) за допомогою методу, названого їм «туннелирование».
Алгоритм MD5 використовує ітераційний метод Меркле-Дамгарда, тому стає можливим побудова колізій з однаковим, заздалегідь обраним префіксом. Аналогічно, колізії виходять при додаванні однакового суфікса до двох різних префіксам, які мають однаковий хеш. У 2009 році було показано, що для будь-яких двох заздалегідь обраних префіксів можна знайти спеціальні суфікси, з якими повідомлення будуть мати однакове значення хешу. Складність такої атаки становить всього 239 операцій підрахунку хешу[26].
 
Метод Ван Сяоюн і ЮйХунбо
 
Метод Ван Сяоюн і ЮйХунбо використовує той факт, що MD5 побудований на ітераційному методі Меркле-Дамгарда. Поданий на вхід файл спочатку доповнюється, так щоб його довжина була кратна 64 байтам, після цього він ділиться на блоки по 64 байта кожен M0,M1,…,Mn-1.Далі обчислюється послідовність 16-байтних станів s0,…,snза правилом sf+1 = ƒ(sj,Mi), де ƒ- деяка фіксована функція. Початковий стан s0називається ініціалізовним вектором[27].
Метод дозволяє для заданого ініціалізованоговектора знайти дві пари М,М’ и N,N’, такі що ƒ(ƒ(s,M),M’)= ƒ(ƒ(s,N),N’). Важливо відзначити, що цей метод працює для будь-якого ініціалізованоговектора, а не тільки для вектора використовуваного за стандартом.
Ця атака є різновидом диференціальної атаки, яка, на відміну від інших атак цього типу, використовує цілочисельне віднімання, а не XOR в якості запобіжної різниці. При пошуку колізій використовується метод модифікації повідомлень: спочатку вибирається довільне повідомлення M0, далі воно модифікується за деякими правилами, сформульованим у розділі, після чого обчислюється диференціал хеш-функції, причому  =М0+dM0з ймовірністю 2-37. До М0і   застосовується функція стиснення для перевірки умов колізії; далі вибирається довільне M1,модифікується, обчислюється новий диференціал, рівний нулю з ймовірністю 2-30, а рівність нулю диференціала хеш-функції як раз означає наявність колізії. Виявилося, що знайшовши одну пару М0і  , можна змінювати лише два останніх слова в М0,тоді для знаходження нової пари М1і   потрібно всього близько 239 операцій хеширования.
Застосування цієї атаки до MD4 дозволяє знайти колізію менше ніж за секунду. Вона також може бути застосована до інших хеш-функцій, таких як RIPEMD і HAVAL[28].
 
ВИСНОВКИ
 
Підбиваючи підсумки слід зазначити що хеш-функція MD5 успішною та досить популярною функцією, але з часом вона стала вразливою і зараз є багато способів її взлому. На даний момент, для захисту даних, варто задуматися про використання однієї з криптографічних хеш-функцій SHA2 або SHA3 (як тільки опублікують відповідний стандарт). Також не варто використовувати функції хешування безпосередньо. Завжди треба намагатися використовувати «сіль» і комбінувати різні алгоритми. Також потрібно обирати складні паролі довжиною як мінімум вісім символів. Звичайно, це не захистить від злому на 100%, але хоча б ускладнить життя зловмисникам.
 
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
 
  1. Алгоритм шифрования MD5// Компьтерная газета – Режим доступу:http://www.nestor.minsk.by/kg/index.html
  2. Що таке MD5, як отримати MD5-хеш// Гаджет експерт– Режим доступу:http://gadget-explorer.com/articles/shho-take-md5-yak-otrimati-md5-hesh/
  3. MD5// Криптография– Режим доступу:http://kriptografea.narod.ru/MD5.html
  4. Криптографические методы защиты// Информационные технологии и системы – Режим доступу:https://sites.google.com/site/anisimovkhv/learning/kripto/lecture/tema9
  5. MD5// Википедия – Режим доступу:https://ru.wikipedia.org/wiki/MD5
  6. Колисниченко Д.Н. PHP и MySQL. Разработка веб-приложений. – 5-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2015. – 592с.
  7. Хэш-функцияMD5// Хабрахабр– Режим доступу:https://habrahabr.ru/sandbox/26876/
  8. Хеширование и расшифровкаMD5// Сайтостроение от А до Я– Режим доступу:http://www.internet-technologies.ru/articles/article_2346.html
  9. ХэшфункцияMD5// Инфостарт– Режим доступу:https://infostart.ru/public/96713/
  10. Все методывзломаMD5// Хакер.ру– Режим доступу:https://xakep.ru/2013/10/13/md5-hack/
  11. Шнайер Б. Прикладнаякриптография. Протоколы, алгоритмы, исходныетексты на языкеСи – М.: «Триумф», 2002.
  12. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы крипто-графии. Учебноепособие. – М.: «Гелиос АРВ», 2001.
  13. Чмора А.Л. Современнаяприкладнаякриптография. – М.: «Гелиос АРВ», 2002.
  14. Введение в криптографию / Подобщ. ред. В.В. Ященко. – 3-е изд., доп. – М.: МЦНМО, «ЧеРо», 2000.
  15. Саломаа А. Криптография с открытым ключом / Пер. с англ. – М.: Мир, 1996.
  16. Столингс В. Криптография и защитасетей. Принципы и практика. 2-е изд. – М.: Издательскийдом «Вильямс», 2001.
  17. Лидл Р., Нидеррайтер Г. Конечные поля, т. 1,2. – М.: Мир, 1998.
  18. Menezes A.J., van Oorcshot P.C., Vanstone S.A. Handbook of Applied Cryptography. – CRC Press, 1997. (http://www.cacr.math.uwaterloo.ca/hac/).
  19. Диффи У., Хеллман М.Э. Защищенность и имитостойкость. Введение в криптографию. - ТИИЭР, т.67, №3, 1979. 
  20. Молдовян Н. А. Криптография: от примитивов к синтезу алгоритмов. - СПб: BHV-Петербург, 2004.
  21. Шеннон К. Работы по теорииинформации и кибернетике. — М.: ИЛ, 1963.
  22. Историякриптографии. А.В. Бабаш, Г.П. Шанкин. - М.: "ГелиосАРВ", 2001 г.
  23. Агибалов Г.П. Избранныетеоремы начального курсакриптографии: Учебноепособие. – Томск: Изд-во НТЛ, 2005. – 116 с.
  24. Асосков А.В и др. Поточныешифры. – М.: Кудиц-образ, 2003. – 336 с.
  25. Брассар Ж. Современнаякриптология. — М.: ПОЛИМЕД, 1999.
  26. Проскурин Г.В. Принципы и методызашитыинформации. — М.: МИЭМ, 1997
  27. Столлингс В. Криптография и защитасетей. Принципы и практика. 2-е изд. — М: Вильямс, 2001.
  28. A. Menezes, P. vanOorschort, S. Vanstone, HandbookofAppliedCryptography – CRC Press, Inc., 1997
Фото Капча