SHA-1

SHA-1
	SHA-1
Име	SHA-1
Създател	Агенция за национална сигурност
Първо издание	1993 (SHA-0),; 1995 (SHA-1)
Серия	SHA-0, SHA-1, SHA-2, SHA-3
Сертифициране	Стандарт за обработка на информация – САЩ
Размер на извлечението	160 бита
Размер на блока	160 бита
Структура	Merkle–Damgård конструкция
Итерации	80
	През 2011 г. атака от Марк Стивънс може да открие хеш-колизии при сложност от 261 операции. Няма създадени реални колизии все още.

SHA-1 е криптографска хеш-функция създадена от Агенцията за национална сигурност на САЩ и публикувана от Националния институт за стандартизация (NIST) в САЩ като правителствен стандарт за обработка на информация.

Като всяка хеш-функция, SHA-1 превръща текст в единично извлечение с фиксирана дължина (наричано още хеш стойност или просто хеш). Изчислената хеш стойност най-често бива използвана за проверка на целостта на данни или защита на информация, например потребителски пароли или друга поверителна информация. Сигурността на една такава функция зависи изцяло на нейната възможност да създава уникални хеш стойности за различните съобщения.

SHA е съкращение на английски: Secure Hash Algorithm и означава Сигурен Хеширащ Алгоритъм. Този алгоритъм превръща съобщение (входен текст) с дължина до 2⁶⁴-1 бита в 160-битово извлечение представено като четиридесетцифрено шестнадесетично число.

Пример: SHA1(„съобщение“) = 078bef09f3d800de4434b257891834a145844f82.

Еволюция

Създадени са четири различно структурирани SHA алгоритъма: SHA-0, SHA-1, SHA-2, SHA-3.

SHA-1 е много подобен на SHA-0, но с някои промени, поради слабости на алгоритъма SHA-0, които могат да доведат до проблеми в сигурността на хеш-функцията.

SHA-1 е и най-използваният сред SHA алгоритмите, а също така е и част от някои приложения и протоколи.

През 2005 година са открити атаки на SHA-1, които показват, че алгоритъмът не е достатъчно сигурен за употреба. Затова NIST започва да изисква от федералните агенции да преминат към SHA-2 след 2010 година, именно заради слабостите.

Начин на работа

Алгоритъмът SHA-1, много прилича на алгоритъма MD5, тъй като и двата са произлезли от MD4.

Хеш-функцията взема входното съобщение и дописва битове, така че дължината на съобщението да стане такава, че при деление на дължината с 512 да получим остатък 448 (дължина mod 512 = 448).

Впоследствие съобщението се разделя на блокове, а всеки блок се състои от 512 бита или 16 32-битови думи (512 = 16*32).

Последните 64 бита на последния блок са запазени за дължината на оригиналното съобщение, за това трябва остатъкът от делението на дължината на 512 да бъде равна на 448, (тъй като 512–64 = 448).

Следователно най-голямото съобщение, което можем да хешираме, е с големина 2⁶⁴-1, тъй като това е най-голямото число, което може да бъде записано в 64 бита.

С цикъл обхождаме 80-те думи и чрез дефинирани 5 константни стойности и използвайки побитови операции с тях и стойности на думите, на всяко завъртане на обхождащия цикъл генерираме нови стойности за константите, а освен побитовите операции, стойностите на константите се разменят на всяка итерация.

Резултата от съобщението представлява тези 5 стойности и е с дължина 5*32 = 160 бита.

След като новото съобщение е разделено на 512 битови блокове, се вземат 16-те думи от всеки блок и се генерират още 64 думи (за да бъдат допълнени думите до 80), всяка нова дума е функция от предходните думи. Така имаме 80 думи (16 от съобщението) и 64 генерирани посредством предходните.

Псевдокод за реализация на SHA-1 алгоритъм:

 Всички променливи за 32 битови без знак (винаги положителни)  
 Използвани операции: 
 & – побитово и 
 | – побитово или 
 ^ – изключващо или 
 ~ – отрицание 
 лява ротация – преместване на най-левите n на брой бита най-отдясно  


Инициализиране на петте променливи: 
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

Подготовка за обработка:
добави бит '1' накрая на съобщението
добави последователност 0 ≤ k < 512 бита '0' накрая на съобщението така че да получим желаната дължина на съобщението (дължина mod 512 = 448)
добави дължината на оригиналното съобщение като 64-битово число в края на съобщението

Обработване на съобщението в 512-битовите парчета:
раздели на съобщението в 512-битови блокове
за всеки блок
    раздели блока в 16 32-битови думи w[i], 0 ≤ i ≤ 15

    Увеличаваме 16-те думи в 80 думи с дължина 32 бита:
    за i от 16 от 79
        w[i] = (w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]) лява ротация 1

    Инициализираме хеш стойности за този блок:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Основен цикъл:
    за i от 0 до 79
        ако 0 ≤ i ≤ 19 тогава
            f = (b & c) | ((~ b) & d)
            k = 0x5A827999
        ако 20 ≤ i ≤ 39
            f = b ^ c ^ d
            k = 0x6ED9EBA1
        ако 40 ≤ i ≤ 59
            f = (b & c) | (b & d) | (c & d)
            k = 0x8F1BBCDC
        ако 60 ≤ i ≤ 79
            f = b ^ c ^ d
            k = 0xCA62C1D6

        temp = (a лява ротация 5) + f + e + k + w[i]
        e = d
        d = c
        c = b лява ротация 30
        b = a
        a = temp

    Добавяме хешовете на този блок към резултата дотук:
    h0 = h0 + a
    h1 = h1 + b
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Създаваме крайния резултат
извлечение = хеш = h0 добави h1 добави h2 добави h3 добави h4

Сравнение на SHA Функциите

В таблицата, начално състояние означава „първоначалната хеш-сума“ след всяка компресия на блок от данни.

Алгоритъм и вариант		Размер на изхода (битове)	Начално състояние размер (битове)	Размер на блоковете (битове)	Максимално съобщение дължина (битове)	Дължина на думата (битове)	Итерации	Използвани операции	Намерени Колизии?
SHA-0		160	160	512	2⁶⁴ − 1	32	80	+, &, \|, ^, ротация	Да
SHA-1		160	160	512	2⁶⁴ − 1	32	80	+, &, \|, ^, ротация	Теоретична атака (2⁶⁰)
SHA-2	SHA-224 SHA-256	224 256	256	512	2⁶⁴ − 1	32	64	+, &, \|, ^, >>, ротация	Няма
SHA-2	SHA-384 SHA-512 SHA-512/224 SHA-512/256	384 512 224 256	512	1024	2¹²⁸ − 1	64	80	+, &, \|, ^, >>, ротация	Няма
SHA-3		224/256/384/512	1600 (5×5 масив от 64-битови думи)			64	24	&,^, ~, ротация	Няма

Приложение

Криптография

Различни форми на алгоритъма sha-1 са част от широко използвани приложения за сигурност и протоколи, между които са TLS и SSL, PGP, SSH, S/MIME и IPsec. Тези приложения също може да използват и MD5, тъй като и MD5 и SHA-1 произлизат от MD4.

Алгоритъмът се използва в конзолата Nintendo's Wii за валидиране при стартиране, но поради значителна слабост в имплементацията, чрез атака могат да бъдат преодолени системите за сигурност. В допълнение частни и търговски организации също биват съветвани и насърчавани да използват SHA-1. SHA-1 вече е премахнат от повечето правителствени приложения; според NIST „Федералните агенции трябва да спрат употребата на SHA-1 в приложения които изискват защита срещу колизии, веднага щом е възможно и трябва да използват алгоритми от семейството SHA-2 хеш-функции за тези приложения след 2010 година“.

SHА функциите се използват като основа за SHACAL блок шифърите.

SHA-1 и SHA-2 са сигурните хеширащи алгоритми които се изискват по закон в някои правителствени приложения в САЩ, включително използване съвместно други криптографски алгоритми и протоколи, за защита на чувствителна, некласифицирана информация

Валидация на данни

SHA-1 хеширане се използва и в различни системи за контрол на версиите като Git, Mercurial и Monotone за да разпознават различните версии и за да засичат загуби на данни или подправяне.

В сорс контрол системата Git, SHA-1 се използва не за сигурност, а за проверка на данните, с цел установяване на промени в тях.

Криптоанализ и валидиране

За една хеш функция, където N е броят битове в извлечението, което алгоритъма създава, да намериш съобщение което съответства на въпросното извлечение, естествено може да бъде извършено с генериране на 2^N извлечения (броят на всички възможни пермутации). Това се нарича атака с предварителна картина (на английски: Preimage attack) и може да зависи, а може и да не зависи от N и дадената изчислителна среда. Вторият критерий, намиране на две различни съобщения, които да имат едно и също извлечение в резултат от хеш-функцията, се нарича колизия (англ. collision). Изискват се средно само около 1,2*2^N/2 изчисления, използвайки атака рожден ден (на английски: birthday attack), заради колизиите. По тази причина силата на една хеш функция обикновено се свежда до един симетричен шифър с дължина половината на дължината на извлеченията, които създава алгоритъма. SHA-1 първоначално е замислян да има 80-битова сила.

Криптографите са създали двойки съобщения, създаващи колизии за SHA-0, и също така открили алгоритми, които създават SHA-1 колизии с много по-малко от очакваните 2⁸⁰ изчисления.

От гледна точка на практическата сигурност, заплахата на тези нови атаки, всъщност е това че те може да проправят път на много по-ефикасни такива. Дали такъв ще бъде сценарият, все още предстои да разберем, но преминаването към по-силни хеширащи фунцкии се смята за разумно. Някои от приложенията, които използват хеш-функции, например запазване на пароли, са минимално засегнати от атаки базирани на колизии. Създаването на парола, която да е валидна за даден акаунт, изисква атака с предварителна картина (англ. Preimage attack), а също така и достъп до хеша на оригиналната парола, което може или не може да бъде тривиално. Обръщане на криптирането на паролата (пример да вземеш парола за акаунта на потребител другаде) не е възможно с тези атаки. (Въпреки всичко, дори сигурно хеширане на пароли не би могло да предотврати brute-force атаки (генериране на възможни комбинации) срещу слаби пароли.)

В контекста на подписване на документи, атакуващия не може просто да пресъздаде подпис от съществуващ документ – атакуващият трябва да издаде чифт документи, един безвреден и един зловреден, а също така да накара притежателя на частния ключ да подпише безвредния документ. Има практически условия, в които това е възможно; до края на 2008 година, беше възможно да се създаде фалшив SSL сертификат, използвайки MD5 колизии.

Поради блоковете информация и итеративната структура на алгоритмите, а също така и липсата на допълнителни крайни стъпки, SHA функциите са уязвими на атаки с увеличаване на дължината (англ. length-extension) и колизии на част от съобщението (англ. partial-message collision). Тези атаки позволяват на нападателя да създаде съобщение чрез хеш с ключ – SHA(съобщение||ключ) или SHA(ключ||съобщение) – чрез увеличаването на съобщението и преизчисляването на хеш извлечението без да знаем ключа. Най-лесният начин на защита срещу тези атаки е да хешираме два пъти SHA_d(съобщение) = SHA(SHA(0^b||съобщение) (дължината на 0^b (нулевия блок) е равна на големината на блока в хеш функцията)

Атаки

В началото на 2005 година е създадена атака върху редуцирана версия на SHA-1 – с 53 итерации вместо 80 – която намира колизии с по-малко от 2⁸⁰ изчислителни операции.

През февруари 2005 е създадена атака, която може да намери колизии в пълната версия на SHA-1, с по-малко от 2⁶⁹ изчисления. Тази атака впоследствие е била подобрена с възможност за намиране на колизии при 2⁶³.

През 2006 е открита дву-блокова колизия за SHA-1 с 64 итерации, намерена чрез неоптимизирани методи с 2³⁵ изчисления на компресираща функция. Тази атака е увеличена до 73 итерации (от 80) през 2010 атаки. За да бъдат открити реални колизии в пълната версия с 80 итерации на хеш-функцията, обаче, се изискват огромни количества процесорно време.

До 2012 година, най-ефективната атака срещу SHA-1 се счита тази на Марк Стивънс с приблизителна стойност от 2.77 милиона долара, за да се открие една хеш стойност чрез наемане на изчислителна мощ от клауд сървъри (англ. cloud servers).

В началото на месец февруари 2017 г. изследователи и учени от компанията Google и CWI Amesterdam (изследователски център в областта на математиката и теоретична компютърна наука) обявяват, че успешно са създали колизия на SHA - 1 алгоритъм. Те успешно създават два PDF файла и двата с имплементирани JPG файлове, като и двата файла са с една и съща SHA - 1 стойност. Целият проект отнема 9,223,372,036,854,775,808 SHA - 1 компилации.

SHA-0

На конференцията „КРИПТО“ през 1998 г., двама френски изследователи – Florent Chabaud и Antoine Joux, представят атака на SHA-0: колизии могат да бъдат открити с комплексност 2⁶¹, по-малко от 2⁸⁰ за идеалната хеш функция от същия размер.

През 2004 г. са открити близки колизии за SHA-0 – две съобщения които хешират приблизително еднаква стойност. В този случай, 142 от 160 бита са равни. Открита е също пълна колизия на SHA-0, сведена до 62 от общо 80 итерации.

Впоследствие през същата година е представена пълна колизия на SHA-0 алгоритъма, чрез обобщаване на атаката от 1998. Открива се, че колизията има комплексност 2⁵¹ и отнема около 80 000 CPU часа на суперкомпютър (Еквивалентно на 13 дни непрекъсната работа на компютъра).

По време на конференцията „КРИПТО“ през 2004 г. са представени предварителни резултати за атаки по MD5, SHA-0 и други хеширащи функции. Комплексността на атаката по SHA-0 е 2⁴⁰, значително по-добра от предходните.

Според резултатите за SHA-0, някои експерти препоръчват плановете за използването на SHA-1 в новите крипто-системи да бъдат преразгледани. След „КРИПТО“ 2004 резултатите са публикувани, а NIST обявява, че планира постепенно премахване на SHA-1 от 2010, за сметка на SHA-2 варианта.

Инструменти за SHA хеширане

Множество инструменти за SHA-1 хеширане могат да бъдат намерени онлайн, а също така и вградени в по-разпространените езици за програмиране.

Примерна реализация на употреба на хеширащ инструмент в езика C#

// Примера изисква библиотеката "System.Security.Cryptography"
    static void Main()
    {
        string input = "съобщение";                                         // дефиниране на съобщението което ще се хешира
        byte[] inputByteArray = Encoding.UTF8.GetBytes(input);              // превръщане на съобщението в масив от байтове

        SHA1 sha = new SHA1CryptoServiceProvider();                         // инициализация на обект от клас за SHA-1 хеширане

        byte[] hash = sha.ComputeHash(inputByteArray);                      // изчисляване на хеш стойността
        string hashString = BitConverter.ToString(hash);                    // превръщане на хеш стойността в символен низ (string)

        Console.WriteLine(hashString);                                      // отпечатване на хеш стойността
    }

Примерна реализация на езика PHP

<?php
 $str = "Съобщение";       // дефиниране на съобщението което ще се хешира
 echo sha1($str);          // отпечатване на изчислената хеш стоност — sha1($str)
 ?>

Външни препратки

Тази страница частично или изцяло представлява превод на страницата SHA-1 в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.