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 и означава Сигурен Хеширащ Алгоритъм. Този алгоритъм превръща съобщение (входен текст) с дължина до 264-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).

Следователно най-голямото съобщение, което можем да хешираме, е с големина 264-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 264 − 1 32 80 +, &, |, ^, ротация Да
SHA-1 Теоретична атака (260)
SHA-2 SHA-224
SHA-256
224
256
256 512 264 − 1 32 64 +, &, |, ^, >>, ротация Няма
SHA-384
SHA-512
SHA-512/224
SHA-512/256
384
512
224
256
512 1024 2128 − 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 е броят битове в извлечението, което алгоритъма създава, да намериш съобщение което съответства на въпросното извлечение, естествено може да бъде извършено с генериране на 2N извлечения (броят на всички възможни пермутации). Това се нарича атака с предварителна картина (на английски: Preimage attack) и може да зависи, а може и да не зависи от N и дадената изчислителна среда. Вторият критерий, намиране на две различни съобщения, които да имат едно и също извлечение в резултат от хеш-функцията, се нарича колизия (англ. collision). Изискват се средно само около 1,2*2N/2 изчисления, използвайки атака рожден ден (на английски: birthday attack), заради колизиите. По тази причина силата на една хеш функция обикновено се свежда до един симетричен шифър с дължина половината на дължината на извлеченията, които създава алгоритъма. SHA-1 първоначално е замислян да има 80-битова сила.

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

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

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

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

Атаки[редактиране | редактиране на кода]

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

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

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

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

SHA-0[редактиране | редактиране на кода]

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

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

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

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

Според резултатите за 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 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.