MD5 и SHA-1 хеш алгоритми

MD5 (от „message-digest“) криптографският алгоритъм е създаден през 1991 г. от проф. Роналд Райвест и за първи път е публикуван през април 1992 г. Целта му е да замени компрометирания MD4 алгоритъм, който не е достатъчно сигурен. В последствие се оказва, че и MD5 не отговаря на съвременните изисквания за сигурност и може да бъде разбит.

MD5 е построен върху конструкцията на Merkle–Damgård и генерира шестнайстично число със фиксиран размер от 32 символа (128 бита) за входящо съобщение с произволна дължина. Идеята е да се създаде уникален идентификатор за съобщението, който да гарантира неговата истинност.

Например:

MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6

Дори малка промяна, напр. добавя не точка в края на входящото съобщение би трябвало да генерира нов уникален идентификатор:

MD5("The quick brown fox jumps over the lazy dog.") = e4d909c290d0fb1ca068ffaddf22cbd0

Дължината на входящото съобщение не е регламентирана. Може да се създаден хаш сума и за нулево съобщение:

MD5("") = d41d8cd98f00b204e9800998ecf8427e

Входящото съобщение се разбива на 512-битови блокове. Последният блок се допълва с необходимия брой нули. Единичната операция е показана на илюстрацията по-долу. Извършват се 64 такива операции, групирани по 16 в 4 цикъла.

MD5 работи с четири 32-битови думи, обозначени с A, B, C и D, и инициализирани с константи. F е нелинейна функция, еднаква за всеки цикъл. Тя работи с думите B, C и D, като прилага върху тях логически операции XOR, AND, OR и NOT. Възможни са общо четири различни функции. Mi е 32-битов блок от входящото съобщение, а Ki е 32-битова константа, уникална за всяка операция. s представлява побитова ротация наляво със s позиции, а  е събиране по модул 232:

 

Още през 1996 г. е открита възможностите за колизии, т. е. две различни съобщения да имат една и съща хеш сума. Десетина години по-късно, с напредъка на изчислителната техника, генерирането на фалшиви хешове или разбиване им вече е реалност. През 2013 г. Xie Tao, Fanbao Liu, and Dengguo Feng демонстрират колизионна атака, проведена на обикновен компютър, като генерирането на фалшиф хеш е протекло за секунди.

В момента MD5 все още се използва широко за проверка на интегритета на данните, напр. проверка за частично сваляне, но не и за отговорни приложения като SSL сертификати.

SHA-1 („secure hash algorithm“)е криптографска хеш функция, разработена от щатската Национална агенция за сигурност (NSA). Първата версия SHA-0 е публикувана през 1993, а приетата за Национален стандарт SHA-1 - през 1995 г. През 2005 г. е установено, че SHA-1 не е достатъчно надежден алгоритъм и се преминава към коренно различаващия се SHA-2. През 2012 година въз основата на нов алгоритъм („Keccak“) се стандартизира SHA-3. Микрософт спира поддръжката на SHA-1 в продуктите си от 2017 г.

SHA-1 генерира 160-битово шестнайстично число с фиксирана дължина от 40 символа (32 при MD5). SHA-1 се отличава от SHA-0 по една побитова ротация в компресионната функция, което според NSA увеличава сигурността на алгоритъма. SHA-2, в зависимост от версията си, генерира 256 или 512 битов изход. Засега не са известни успешни атаки срещу SHA-2.

Както и при MD5, SHA-1 работи с 32-битови думи, но тук те са 5: A, B, C, D и F. При SHA-0, SHA-1 и SHA-2/512 се правят 80 цикъла, а при SHA-2/256 - 64. При SHA-0 и SHA-1 се използват операциите add, and, or, xor, rotate и mod, а при SHA-2 - add, and, or, xor, rotate, mod и shift.

Една итерация със SHA-1 изглежда така:

A, B, C, D и E са 32-битови думи, F е нелинейна функция, която варира, n означава побитова ротация наляво на n позиции, като n  се променя при всяка операция, Wt е дума от съобщението при цикъл t, а Kt е константа на цикъла, валидна за цикъл t, а  е събиране по модул 232.

Изходът от функцията изглежда така:

SHA1("The quick brown fox jumps over the lazy dog") = 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12

Смяната на един символ, напр. „dog“ на „cog“ генерира нов хеш:

SHA1("The quick brown fox jumps over the lazy cog") = de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3

Входящото съобщение може да бъде и с нулева дължина:

SHA1("") = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

SHA-1 е стандартен алгоритъм, който се използва при протоколи и приложения като TLS and SSL, PGP, SSH, S/MIME, and IPsec. Също така се използва в системи за следене на версиите като Git, Mercurial и Monotone за идентификация на версията и проверка на интегритета на данните.

Щатските държавни служби са задължени от закона да използват SHA-1 и SHA-2 алгоритмите, като след 2010 г. постепенно се преминава към използване само на SHA-2. SHA-1 се използва само за  валидиране на важна некласифицирана информация, въпреки че след 2005 г. са отбелязани само частични успехи в рабиването на SHA-1. Най-големият успех е постигнат през 2012 г., когато за разбиването на единичен хеш са използвани облачни сървъри и цената на атаката е била около 2,8 млн долара.

Източници

MD5

Fast Collision Attack on MD5

RFC 1321

Cryptanalysis of MD5 & SHA-1

SHA-1

SHS

FIPS 180-3

The Keccak sponge function family

Comparison of cryptographic hash functions