Sha1 это что: Sha-1 | Контроль Разума

Содержание

разница между SHA-1, SHA-2 и SHA-256 алгоритмами хеширования

SHA-1, SHA-2, SHA-256, SHA-384 – что всё это значит!? Если вы слышали о «SHA» в множестве его форм, но до сих пор полностью не уверены в том, что означает эта аббревиатура или почему это так важно, то мы попытаемся пролить немного света на эту тему сегодня.

Прежде чем мы коснемся самого SHA, нам нужно узнать, что такое хеш, рассмотреть, как SSL-сертификаты используют хеш для формирования цифровых подписей. Это важные концепции, которые важны для понимания до того, чем вы сможете разобраться, что такое SHA-1 и SHA-2. Давайте начнем.

Алгоритм хеширования — это математическая функция, которая сокращает данные до фиксированного размера. Так, например, если бы мы взяли предложение «Быстрая Коричневая Лиса Прыгает Через Ленивую Собаку» И прогнали его через специальный алгоритм хеширования, известный как CRC32, мы бы получили следующий результат: «07606bb6». Этот результат называется хеш или хеш-значением. Иногда хеширование называют односторонним шифрованием. Хеш удобен, когда компьютеру нужно идентифицировать, сравнивать или иными способами выполнять вычисления в файлах и строках данных. Компьютеру проще сначала вычислить хеш, а затем сравнить значение, нежели сравнивать исходные файлы.

Одним из ключевых свойств алгоритмов хеширования является детерминизм. Любой компьютер в мире, который понимает алгоритм хеширования, который вы выберете, может локально вычислить хеш предложения из нашего примера и получить тот же самый ответ. Алгоритмы хеширования используются всевозможными способами – они используются для хранения паролей, в базах данных и т.д. Существуют сотни алгоритмов хеширования и все они имеют конкретные цели – некоторые из них оптимизированы для определенных типов данных, другие для обеспечения высокой скорости, третьи – безопасности и т.д. В сегодняшнем разборе нас интересует только SHA алгоритм. SHA расшифровывается как Защитный алгоритм хеширования – его название уже говорит само за себя – он используется для криптографической защиты. Криптографические хеш-алгоритмы производят необратимые и уникальные хеши. Необратимость состоит в том, что, если бы у вас был только хеш, вы не смогли бы его использовать, чтобы выяснить, каков был исходный фрагмент данных, поэтому исходные данные остаются безопасными и неизвестными. Уникальность означает, что две разных части данных никогда не могут превратиться в один и тот же хеш – в следующем разделе объясним, почему это так важно.

Примечание: чтобы было легче читать и понимать эту статью, мы используем примеры в виде строк данных и алгоритмов хеширования, которые значительно короче, чем то, что на самом деле используется на практике. Хеши, которые вы видели в этой статье, не являются хешами SHA любого типа.

Цифровые подписи

Теперь, когда мы знаем, что такое хеш, мы можем объяснить, как он используется в SSL-сертификатах. Протокол SSL/TLS используется для обеспечения безопасной передачи данных с одного устройства на другое через Интернет. Для краткости создается впечатление, что SSL часто понимается, как шифрование. Однако не забывайте, что SSL обеспечивает также аутентификацию. В файле сертификата SSL задается необходимая информация, которая необходима для аутентификации. Или, другими словами, SSL-сертификаты связывают определенный открытый ключ с идентификатором. Запомните, что SSL/TLS протокол способствует соединению с использованием асимметричного шифрования. Это означает, что есть два ключа шифрования, каждый из которых обрабатывает половину процесса: открытый ключ для шифрования и закрытый для дешифровки. Каждый сертификат SSL содержит открытый ключ, который может использоваться для шифрования данных клиентом, а владелец указанного SSL-сертификата надежно хранит закрытый ключ на своем сервере, который они используют для дешифрования данных и делает их доступными для чтения. В конечном счете, основной целью асимметричного шифрования является безопасный обмен ключами.

Асимметричные ключи требуют большой вычислительной мощности, поэтому они также используют (и все еще безопасно) небольшие симметричные ключи для фактической части соединения. Таким образом, клиент генерирует сеансовый ключ, шифрует его копию и отправляет ее на сервер, где он может быть расшифрован и использован для связи в течение всего времени соединения (или до его поворота). Именно поэтому аутентификация невероятно важна для обеспечения того, чтобы SSL/TLS фактически обеспечивал значимую безопасность. Представьте, что ваш компьютер не имел бы надежного способа узнать, кому принадлежит ключ шифрования, который вы использовали?

Шифрование ключа сеанса с помощью такого ключа не будет полезным, потому как вы не знаете, кто владеет соответствующим закрытым ключом, который его расшифрует. В конце концов, шифрование данных малопригодно, если вы отправляете его непосредственно злоумышленнику, посреднику злоумышленника на другом конце провода.

Цифровые подписи являются важной частью того, как SSL-сертификаты предоставляют аутентификацию. Когда выдается сертификат, он подписывается цифровой подписью центром сертификации (CA), выбранным вами в качестве поставщика сертификатов (например, Sectigo, Thawte, Geotrust и т.д.). Эта подпись обеспечивает криптографическое доказательство того, что центр сертификации подписал сертификат SSL, что сертификат не был изменен или воспроизведен. Что еще более важно, подлинная подпись является криптографическим доказательством того, что информация, содержащаяся в сертификате, была проверена доверенной третьей стороной.

Теперь давайте поговорим о том, как цифровая подпись создается, применяется, прикрепляется – выберите удобную терминологию. Асимметричные ключи, о которых мы упоминали ранее, используются снова, но с целью подписи не зашифрованных данных. Математически подписание включает в себя просмотр того, как объединяются данные и ключи (мы не будем заходить слишком далеко в дебри по поводу того, как создаются подписи, потому что они быстро усложняются. Если вас это интересует, Джошуа Дэвис написал отличную статью о том, как работают цифровые подписи). Чтобы упростить работу компьютеров, но все же надежно создать и проверить эти подписи, центр сертификации сначала хеширует файл сертификата и подписывает полученный хеш. Это более эффективно, чем подписание всего сертификата. Эти цифровые подписи затем предоставляют необходимое доказательство того, что предоставленный вам сертификат является достоверным сертификатом, выданным доверенным центром сертификации на соответствующий веб-сайт. Никаких трюков. Никакой имитации. Никаких манипуляций с файлом сертификата SSL/TLS не происходит. Цифровые подписи невероятно чувствительны — любое изменение файла приведет к изменению подписи.

Если бы мы взяли наш пример из предыдущего раздела и сделали его полностью строчным («быстрая коричневая лиса прыгает через ленивую собаку»), получившийся хеш был бы совсем другим. Это означает, что итоговая подпись этого хеша также будет отличаться. Даже изменение одного бита многотысячного гигабайтного документа приведет к совершенно другому хешу. Это делает невозможным для злоумышленников изменение законного сертификата или создание мошеннического сертификата, который выглядит законным. Другой хеш означает, что подпись больше недействительна, и ваш компьютер узнает об этом, когда аутентифицирует сертификат SSL. Если на вашем компьютере обнаружена недопустимая подпись, это приведет к ошибке и полностью предотвратит небезопасное соединение.

SHA-1 и SHA-2

Теперь, когда нами заложенфундамент ваших знаний, можем переходить к звезде сегодняшнего шоу. Как уже говорилось выше, SHA – это защитный алгоритм хеширования. SHA-1 и SHA-2 – это две разные версии этого алгоритма. Они различаются в конструкциях (как создается хеш из исходных данных) и в битовой длине подписи. Вам следует воспринимать SHA-2, как преемника SHA-1. В первую очередь, люди сосредоточены на бит-длине, как на важном различии. SHA-1 — это 160-битный хеш. SHA-2, на самом деле, является «семейством» хешей и имеет множество длин, наиболее популярной из которых является 256-бит. Разнообразие хешей SHA-2 может привести к путанице, поскольку сайты и авторы обозначают их по-разному. Если вы видите «SHA-2», «SHA-256» или «SHA-256 бит», эти имена относятся к одной и той же вещи. Если вы видите «SHA-224», «SHA-384» или «SHA-512», это относится к чередованию бит-длины SHA-2. Вы также можете увидеть, что некоторые сайты выписывают как алгоритм, так и длину бита, например «SHA-2 384.». Но это неприятно, как заставлять людей называть себя по имени и отчеству, когда вы просите их представиться.

SSL-индустрия выбрала SHA в качестве своего алгоритма хеширования для цифровых подписей

С 2011 по 2015 год SHA-1 был основным алгоритмом. Растущее число исследований, показывающих недостатки SHA-1, вызвало переоценку. Фактически, Google даже зашел так далеко, что создал конфликт SHA-1 (когда две части разрозненных данных создают одно и то же значение хеш-функции). Таким образом, с 2016 года SHA-2 является новым стандартом. Если вы получаете сегодня сертификат SSL/TLS, он должен использовать эту подпись. Иногда вам будут встречаться сертификаты, использующие SHA-2 384-бита. Реже будут встречаться 224-битные типы, поскольку они не одобрены для использования с публично доверенными сертификатами, или 512-битные типы, которые очень редко поддерживаются программным обеспечением. SHA-2, вероятно, останется актуальным еще не меньше, чем на 5 лет. Тем не менее, можно ожидать и некоторую атаку на алгоритм, которая вызвала бы более ранний переход. Вот хеш SHA-1 и SHA-2 сертификата SSL сайта выглядят так: Это то, о чем и шла речь. Возможно, это не так много, но цифровые подписи невероятно важны для обеспечения безопасности SSL\TLS.

Более высокий хеш может обеспечить большую безопасность, поскольку возможны более вероятные комбинации. Помните, что одна из важных функций алгоритма криптографического хеширования заключается в том, что он создает уникальные хеши. Опять же, если два разных значения или файла могут создать один и тот же хеш, то это то, что мы называем конфликтом. Безопасность цифровых подписей может быть гарантирована только при условии, что конфликтов не происходит. Конфликты опасны потому, что они позволяют двум файлам создавать одну и ту же подпись, поэтому, когда компьютер проверяет подпись, она может показаться действительной, даже если файл никогда не был подписан.

Сколько хешей?

Если алгоритм хеширования должен создавать уникальные хеши для каждого возможного ввода, сколько всего возможных хешей? Бит имеет два возможных значения: 0 и 1. Возможное количество уникальных хешей может быть выражено как количество возможных значений увеличенных на количество бит. Для SHA-256 имеется 2 ²⁵⁶ возможных комбинаций. Итак, 2 ²⁵⁶ комбинаций. Сколько это? Ну, это огромное количество. Шутки в сторону. Это делает цифры, подобные триллиону и септилию, ничтожными. Это намного превышает количество зерен песка в мире. Чем больше число возможных хешей, тем меньше вероятность того, что два значения создадут один и тот же хеш. Обратите внимание, что большая длина бит вовсе не означает, что алгоритм хеширования производит более безопасный хэш. Построение алгоритма также невероятно важно — поэтому индустрия SSL использует алгоритмы хеширования, специально разработанные для криптографической защиты.

Переход на SHA-2

В 2015 году индустрия SSL прошла «переход на SHA-2». Это включало повторную выдачу тысяч существующих сертификатов, чтобы новые файлы могли быть созданы и подписаны с SHA-2. Это также связано с крупными обновлениями программного обеспечения для выпуска, которым работают централизованные доверенные центры сертификации (их десятки). Как и ожидалось, были сбои. Крайний срок для выдачи новых SSL сертификатов с SHA-1 был назначен на 31 декабря 2015. По большей части, выдача была осуществлена к назначенному сроку. С тех пор было сделано несколько ошибок, и произошло несколько особых случаев. Но за последние три года сертификаты SHA-1 почти полностью исчезли. Сегодня, если вы столкнулись с сертификатом SHA-1, вы увидите предупреждение.

В Google Chrome все сертификаты SHA-1, срок действия которых истекал в 2016 году, не показывали зеленый замок в защищенных соединениях и вместо этого отображали тот же значок, что и незащищенное HTTP-соединение. Вы можете щелкнуть на значок, чтобы получить более конкретную информацию о том, почему он отображается, если есть другие причины, не связанные с подписью. Браузеры обрабатывали подписанные сертификаты SHA-1, срок действия которых истекал в 2017 году с более интенсивным предупреждением. Это связано с тем, что безопасность подписи напрямую связана с тем, как долго она действительна.

Сегодня, в 2018 году, Google просто суммарно удаляет незащищенные сайты, оставляя только напоминание о них в качестве предупреждения другим, кто может осмелиться совершить те же ошибки.

Обеспечение безопасности подписей

По прошествии времени атаки на криптографию станут лучше, а мощность компьютерной обработки станет дешевле. Это делает действительную подпись SHA-2 менее безопасной в 2020 году, чем в 2016 году. По этой причине выбирать придется еще более сильный алгоритм, чем это необходимо, чтобы краткосрочные улучшения не привели к компрометации безопасности в будущем. Для алгоритма хеширования нереально не оставаться в безопасности на протяжении десятилетия.

Отраслевые эксперты и исследователи безопасности во всем мире постоянно анализируют алгоритмы SHA-2 и другие криптографические алгоритмы хеширования, поэтому будьте уверены, что SSL-сертификаты будут иметь надежные и безопасные цифровые подписи на протяжении какого-то времени. Это не означает, что криптографы будут просто сидеть и ждать, пока не возникнет проблема. Преемник SHA-2, удобно названный SHA-3, уже создан. Когда придет время сделать другой коммутатор, индустрия SSL может использовать SHA-3 в качестве своего следующего выбора, или сможет воспользоваться совершенно другим алгоритмом.

Требуются годы, чтобы правильно исследовать и проверять новые криптографические стандарты, а затем разрабатывать программное обеспечение, которое их поддерживает. Надеюсь, это обнадеживает, потому что вы знаете, что индустрия всегда, по крайней мере, на один шаг впереди.

SHA-1 — Википедия

SHA-1
Разработчики	NSA совместно с NIST
Создан	1995
Опубликован	1995
Предшественник	SHA-0^[d]
Преемник	SHA-2
Размер хеша	160 бит
Число раундов	80
Тип	хеш-функция

Secure Hash Algorithm 1 — алгоритм криптографического хеширования. Описан в RFC 3174. Для входного сообщения произвольной длины (максимум 264−1{\displaystyle 2^{64}-1} бит, что примерно равно 2 эксабайта) алгоритм генерирует 160-битное (20 байт) хеш-значение, называемое также дайджестом сообщения, которое обычно отображается как шестнадцатиричное число, длиной в 40 цифр. Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учреждений в США. Принципы, положенные в основу SHA-1, аналогичны тем, которые использовались Рональдом Ривестом при проектировании MD4.

История

В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1. Позже, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA.

Описание алгоритма

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

SHA-1 реализует хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами хеш блока Mi{\displaystyle M_{i}} равен hi=f(Mi,hi−1){\displaystyle h_{i}=f(M_{i},h_{i-1})}. Хеш-значением всего сообщения является выход последнего блока.

Инициализация

Исходное сообщение разбивается на блоки по 512 бит в каждом. Последний блок дополняется до длины, кратной 512 бит. Сначала добавляется 1 (бит), а потом нули, чтобы длина блока стала равной (512 — 64 = 448) бит. В оставшиеся 64 бита записывается длина исходного сообщения в битах (в big-endian формате). Если последний блок имеет длину более 448, но менее 512 бит, то дополнение выполняется следующим образом: сначала добавляется 1 (бит), затем нули вплоть до конца 512-битного блока; после этого создается ещё один 512-битный блок, который заполняется вплоть до 448 бит нулями, после чего в оставшиеся 64 бита записывается длина исходного сообщения в битах (в big-endian формате). Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину.

Инициализируются пять 32-битовых переменных.

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

Определяются четыре нелинейные операции и четыре константы.

Ft(m,l,k)=(m∧l)∨(¬m∧k){\displaystyle F_{t}(m,l,k)=(m\wedge l)\vee (\neg {m}\wedge k)}	Kt{\displaystyle K_{t}} = 0x5A827999	0≤t≤19
Ft(m,l,k)=m⊕l⊕k{\displaystyle F_{t}(m,l,k)=m\oplus l\oplus k}	Kt{\displaystyle K_{t}} = 0x6ED9EBA1	20≤t≤39
Ft(m,l,k)=(m∧l)∨(m∧k)∨(l∧k){\displaystyle F_{t}(m,l,k)=(m\wedge l)\vee (m\wedge k)\vee (l\wedge k)}	Kt{\displaystyle K_{t}} = 0x8F1BBCDC	40≤t≤59
Ft(m,l,k)=m⊕l⊕k{\displaystyle F_{t}(m,l,k)=m\oplus l\oplus k}	Kt{\displaystyle K_{t}} = 0xCA62C1D6	60≤t≤79

Главный цикл

Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит из четырёх этапов по двадцать операций в каждом. Блок сообщения преобразуется из 16 32-битовых слов Mi{\displaystyle M_{i}} в 80 32-битовых слов Wj{\displaystyle W_{j}} по следующему правилу:

Wt=Mt{\displaystyle W_{t}=M_{t}}                                      при 0≤t≤15
Wt{\displaystyle W_{t}} = (Wt{\displaystyle W_{t}}_-3⊕{\displaystyle \oplus } Wt{\displaystyle W_{t}}_-8⊕{\displaystyle \oplus } Wt{\displaystyle W_{t}}_-14⊕{\displaystyle \oplus } Wt{\displaystyle W_{t}}_-16) << 1     при 16≤t≤79

здесь << — это циклический сдвиг влево

для t{\displaystyle t} от 0 до 79 
temp = (a<<5) + Ft{\displaystyle F_{t}}(b,c,d) + e + Wt+Kt{\displaystyle 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-битное хеш-значение.

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

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

 Замечание: Все используемые переменные 32 бита.

Инициализация переменных:
h0 = 0x67452301
h2 = 0xEFCDAB89
h3 = 0x98BADCFE
h4 = 0x10325476
h5 = 0xC3D2E1F0

Предварительная обработка:
Присоединяем бит '1' к сообщению
Присоединяем k битов '0', где k наименьшее число ≥ 0 такое, что длина получившегося сообщения
(в битах) сравнима по модулю  512 с 448 (length mod 512 == 448)
Добавляем длину исходного сообщения (до предварительной обработки) как целое 64-битное
Big-endian число, в битах.

В процессе сообщение разбивается последовательно по 512 бит:
for перебираем все такие части
    разбиваем этот кусок на 16 частей, слов по 32-бита (big-endian) 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 = h2
    c = h3
    d = h4
    e = h5

    Основной цикл:
    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 then
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59 then
            f = (b and c) or (b and d) or (c and d)
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79 then
            f = b xor c xor d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Добавляем хеш-значение этой части к результату:
    h0 = h0 + a
    h2 = h2 + b 
    h3 = h3 + c
    h4 = h4 + d
    h5 = h5 + e

Итоговое хеш-значение(h0, h2, h3, h4, h5 должны быть преобразованы к big-endian):
digest = hash = h0 append h2 append h3 append h4 append h5

Вместо оригинальной формулировки 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)

Примеры

Ниже приведены примеры хешей 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

Криптоанализ

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

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

При решении методом «грубой силы»:

первая задача требует в среднем 2^160/2 = 2⁸⁰ операций, если использовать атаку Дней рождения.
вторая требует 2¹⁶⁰ операций.

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

В январе 2005 года Винсент Рэймен и Elisabeth Oswald опубликовали сообщение об атаке на усечённую версию SHA-1 (53 раунда вместо 80), которая позволяет находить коллизии меньше, чем за 2⁸⁰ операций.

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

О методе авторы пишут:

Мы представляем набор стратегий и соответствующих методик, которые могут быть использованы для устранения некоторых важных препятствий в поиске коллизий в 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³³ операций.

В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 2⁶³ операций.
В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном.

Кристоф де Каньер и Кристиан Рехберг позже представили усовершенствованную версию атаки на SHA-1, за что были удостоены награды за лучшую статью на конференции ASIACRYPT 2006. Ими была представлена двух-блоковая коллизия на 64-раундовый алгоритм с вычислительной сложностью около 2³⁵ операций.^[2]

Существует масштабный исследовательский проект, стартовавший в технологическом университете австрийского города Грац, который : «… использует компьютеры, соединенные через Интернет, для проведения исследований в области криптоанализа. Вы можете поучаствовать в проекте загрузив и запустив бесплатную программу на своем компьютере.»^[3]

Хотя теоретически SHA-1 считается взломанным (количество вычислительных операций сокращено в 2^80-63 = 131 072 раза), на практике подобный взлом неосуществим, так как займёт пять миллиардов лет.

Бурт Калински, глава исследовательского отдела в «лаборатории RSA» предсказывает, что первая атака по нахождению прообраза будет успешно осуществлена в ближайшие 5—10 лет.

Ввиду того, что теоретические атаки на SHA-1 оказались успешными, NIST планирует полностью отказаться от использования SHA-1 в цифровых подписях.^[4]

Из-за блочной и итеративной структуры алгоритмов, а также отсутствия специальной обработки в конце хеширования, все хеш-функции семейства SHA уязвимы к атакам удлинением сообщения и коллизии при частичном хешировании сообщения.^[5] Эти атаки позволяют подделывать сообщения, подписанные только хешем — SHA(message||key){\displaystyle SHA(message||key)} или SHA(key||message){\displaystyle SHA(key||message)} — путём удлинения сообщения и пересчёту хеша без знания значения ключа. Простейшим исправлением, позволяющим защититься от этих атак, является двойное хеширование — SHAd(message)=SHA(SHA(0b||message)){\displaystyle SHA_{d}(message)=SHA(SHA(0^{b}||message))} (0b{\displaystyle 0^{b}} — блок нулей той же длины, что и блок хеш-функции).

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

SHAppening

8 октября 2015 Marc Stevens, Pierre Karpman, и Thomas Peyrin опубликовали атаку на функцию сжатия алгоритма SHA 1, которая требует всего 2⁵⁷ вычислений.

Реальный взлом: SHAttered (нахождение коллизий)

23 февраля 2017 года специалисты из Google и CWI объявили о практическом взломе алгоритма, опубликовав 2 PDF-файла с одинаковой контрольной суммой SHA-1. Это потребовало перебора 9*10¹⁸ вариантов, что заняло бы 110 лет на 1 GPU^[7].

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4.

Сходства:

Четыре этапа.
Каждое действие прибавляется к ранее полученному результату.
Размер блока обработки, равный 512 бит.
Оба алгоритма выполняют сложение по модулю 2³², они рассчитаны на 32-битную архитектуру.

Различия:

В SHA-1 на четвёртом этапе используется та же функция f, что и на втором этапе.
В MD5 в каждом действии используется уникальная прибавляемая константа. В SHA-1 константы используются повторно для каждой из четырёх групп.
В SHA-1 добавлена пятая переменная.
SHA-1 использует циклический код исправления ошибок.
В MD5 четыре сдвига, используемые на каждом этапе, отличаются от значений, используемых на предыдущих этапах. В SHA на каждом этапе используется постоянное значение сдвига.
В MD5 четыре различных элементарных логических функции, в SHA-1 — три.
В MD5 длина дайджеста составляет 128 бит, в SHA-1 — 160 бит.
SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25 % медленнее, чем MD5 на той же аппаратуре.

Брюс Шнайер делает следующий вывод : «SHA-1 — это MD4 с добавлением расширяющего преобразования, дополнительного этапа и улучшенным лавинным эффектом. MD5 — это MD4 с улучшенным битовым хешированием, дополнительным этапом и улучшенным лавинным эффектом.»

Сравнение с ГОСТ Р 34.11-94

Ряд отличительных особенностей ГОСТ Р 34.11-94:

При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S-блоках, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий алгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1.
Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2¹²⁸, что во много раз превосходит 2⁸⁰для SHA-1.

Сравнение с другими SHA

В таблице, «промежуточный размер хеша» означает «размер внутренней хеш-суммы» после каждой итерации.

Вариации алгоритма		Размер выходного хеша (бит)	Промежуточный размер хеша (бит)	Размер блока (бит)	Максимальная длина входного сообщения (бит)	Размер слова (бит)	Количество раундов	Используемые операции	Найденные коллизии
SHA-0		160	160	512	2⁶⁴ − 1	32	80	+,and, or, xor, rotl	Есть
SHA-1		160	160	512	2⁶⁴ − 1	32	80	+,and, or, xor, rotl	2⁵² операций
SHA-2	SHA-256/224	256/224	256	512	2⁶⁴ − 1	32	64	+,and, or, xor, shr, rotr	Нет
SHA-2	SHA-512/384	512/384	512	1024	2¹²⁸ − 1	64	80	+,and, or, xor, shr, rotr	Нет

Использование

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

SHA-1 является наиболее распространенным из всего семейства SHA и применяется в различных широко распространенных криптографических приложениях и алгоритмах.

SHA-1 используется в следующих приложениях:

S/MIME — дайджесты сообщений.
SSL — дайджесты сообщений.
IPSec — для алгоритма проверки целостности в соединении «точка-точка».
SSH — для проверки целостности переданных данных.
PGP — для создания электронной цифровой подписи.
Git — для идентификации каждого объекта по SHA-1-хешу от хранимой в объекте информации.
Mercurial — для идентификации ревизий
BitTorrent — для проверки целостности загружаемых данных.

SHA-1 является основой блочного шифра SHACAL.

Отказ от использования

Компания Google давно выразила своё недоверие SHA-1, особенно в качестве использования этой функции для подписи сертификатов TLS. Ещё в 2014 году, вскоре после публикации работы Марка Стивенса, группа разработчиков Chrome объявила о постепенном отказе от использования SHA-1.

С 25 апреля 2016 года Яндекс. Почта перестала поддерживать старые почтовые программы, использующие SHA-1.^[8]

См. также

Примечания

Литература

Ссылки

SHA-1 — Википедия. Что такое SHA-1

SHA-1
Разработчики	NSA совместно с NIST
Создан	1995
Опубликован	1995
Предшественник	SHA-0^[d]
Преемник	SHA-2
Размер хеша	160 бит
Число раундов	80
Тип	хеш-функция

История

Описание алгоритма

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

Инициализация

Инициализируются пять 32-битовых переменных.

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

Определяются четыре нелинейные операции и четыре константы.

Ft(m,l,k)=(m∧l)∨(¬m∧k){\displaystyle F_{t}(m,l,k)=(m\wedge l)\vee (\neg {m}\wedge k)}	Kt{\displaystyle K_{t}} = 0x5A827999	0≤t≤19
Ft(m,l,k)=m⊕l⊕k{\displaystyle F_{t}(m,l,k)=m\oplus l\oplus k}	Kt{\displaystyle K_{t}} = 0x6ED9EBA1	20≤t≤39
Ft(m,l,k)=(m∧l)∨(m∧k)∨(l∧k){\displaystyle F_{t}(m,l,k)=(m\wedge l)\vee (m\wedge k)\vee (l\wedge k)}	Kt{\displaystyle K_{t}} = 0x8F1BBCDC	40≤t≤59
Ft(m,l,k)=m⊕l⊕k{\displaystyle F_{t}(m,l,k)=m\oplus l\oplus k}	Kt{\displaystyle K_{t}} = 0xCA62C1D6	60≤t≤79

Главный цикл

Wt=Mt{\displaystyle W_{t}=M_{t}}                                      при 0≤t≤15
Wt{\displaystyle W_{t}} = (Wt{\displaystyle W_{t}}_-3⊕{\displaystyle \oplus } Wt{\displaystyle W_{t}}_-8⊕{\displaystyle \oplus } Wt{\displaystyle W_{t}}_-14⊕{\displaystyle \oplus } Wt{\displaystyle W_{t}}_-16) << 1     при 16≤t≤79

здесь << — это циклический сдвиг влево

для t{\displaystyle t} от 0 до 79 
temp = (a<<5) + Ft{\displaystyle F_{t}}(b,c,d) + e + Wt+Kt{\displaystyle 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-битное хеш-значение.

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

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

 Замечание: Все используемые переменные 32 бита.

Инициализация переменных:
h0 = 0x67452301
h2 = 0xEFCDAB89
h3 = 0x98BADCFE
h4 = 0x10325476
h5 = 0xC3D2E1F0

Предварительная обработка:
Присоединяем бит '1' к сообщению
Присоединяем k битов '0', где k наименьшее число ≥ 0 такое, что длина получившегося сообщения
(в битах) сравнима по модулю  512 с 448 (length mod 512 == 448)
Добавляем длину исходного сообщения (до предварительной обработки) как целое 64-битное
Big-endian число, в битах.

В процессе сообщение разбивается последовательно по 512 бит:
for перебираем все такие части
    разбиваем этот кусок на 16 частей, слов по 32-бита (big-endian) 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 = h2
    c = h3
    d = h4
    e = h5

    Основной цикл:
    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 then
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59 then
            f = (b and c) or (b and d) or (c and d)
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79 then
            f = b xor c xor d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Добавляем хеш-значение этой части к результату:
    h0 = h0 + a
    h2 = h2 + b 
    h3 = h3 + c
    h4 = h4 + d
    h5 = h5 + e

Итоговое хеш-значение(h0, h2, h3, h4, h5 должны быть преобразованы к big-endian):
digest = hash = h0 append h2 append h3 append h4 append h5

(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)

Примеры

Ниже приведены примеры хешей 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

Криптоанализ

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

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

При решении методом «грубой силы»:

первая задача требует в среднем 2^160/2 = 2⁸⁰ операций, если использовать атаку Дней рождения.
вторая требует 2¹⁶⁰ операций.

О методе авторы пишут:

Мы представляем набор стратегий и соответствующих методик, которые могут быть использованы для устранения некоторых важных препятствий в поиске коллизий в 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.

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

SHAppening

Реальный взлом: SHAttered (нахождение коллизий)

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4.

Сходства:

Четыре этапа.
Каждое действие прибавляется к ранее полученному результату.
Размер блока обработки, равный 512 бит.
Оба алгоритма выполняют сложение по модулю 2³², они рассчитаны на 32-битную архитектуру.

Различия:

В SHA-1 на четвёртом этапе используется та же функция f, что и на втором этапе.
В MD5 в каждом действии используется уникальная прибавляемая константа. В SHA-1 константы используются повторно для каждой из четырёх групп.
В SHA-1 добавлена пятая переменная.
SHA-1 использует циклический код исправления ошибок.
В MD5 четыре сдвига, используемые на каждом этапе, отличаются от значений, используемых на предыдущих этапах. В SHA на каждом этапе используется постоянное значение сдвига.
В MD5 четыре различных элементарных логических функции, в SHA-1 — три.
В MD5 длина дайджеста составляет 128 бит, в SHA-1 — 160 бит.
SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25 % медленнее, чем MD5 на той же аппаратуре.

Сравнение с ГОСТ Р 34.11-94

Ряд отличительных особенностей ГОСТ Р 34.11-94:

При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S-блоках, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий алгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1.
Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2¹²⁸, что во много раз превосходит 2⁸⁰для SHA-1.

Сравнение с другими SHA

В таблице, «промежуточный размер хеша» означает «размер внутренней хеш-суммы» после каждой итерации.

Вариации алгоритма		Размер выходного хеша (бит)	Промежуточный размер хеша (бит)	Размер блока (бит)	Максимальная длина входного сообщения (бит)	Размер слова (бит)	Количество раундов	Используемые операции	Найденные коллизии
SHA-0		160	160	512	2⁶⁴ − 1	32	80	+,and, or, xor, rotl	Есть
SHA-1		160	160	512	2⁶⁴ − 1	32	80	+,and, or, xor, rotl	2⁵² операций
SHA-2	SHA-256/224	256/224	256	512	2⁶⁴ − 1	32	64	+,and, or, xor, shr, rotr	Нет
SHA-2	SHA-512/384	512/384	512	1024	2¹²⁸ − 1	64	80	+,and, or, xor, shr, rotr	Нет

Использование

SHA-1 используется в следующих приложениях:

S/MIME — дайджесты сообщений.
SSL — дайджесты сообщений.
IPSec — для алгоритма проверки целостности в соединении «точка-точка».
SSH — для проверки целостности переданных данных.
PGP — для создания электронной цифровой подписи.
Git — для идентификации каждого объекта по SHA-1-хешу от хранимой в объекте информации.
Mercurial — для идентификации ревизий
BitTorrent — для проверки целостности загружаемых данных.

SHA-1 является основой блочного шифра SHACAL.

Отказ от использования

С 25 апреля 2016 года Яндекс. Почта перестала поддерживать старые почтовые программы, использующие SHA-1.^[8]

См. также

Примечания

Литература

Ссылки

Sha1 — это… Что такое Sha1?

Криптографическая хеш-функция
Название	SHA-1
Разработчик	NSA совместно с NIST
Создан	1995
Опубликован	1995
Размер хеша	160 бит
Число раундов	80
Тип	хеш-функция

Secure Hash Algorithm 1 — алгоритм криптографического хеширования. Описан в RFC 3174. Для входного сообщения произвольной длины (максимум 2⁶⁴ − 1 бит) алгоритм генерирует 160-битное хеш-значение, называемое также дайджестом сообщения. Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учреждений в США. Принципы, положенные в основу SHA-1, аналогичны тем, которые использовались Рональдом Ривестом при проектировании

Содержание

История

В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1. Немного спустя, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA.

Описание алгоритма

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

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

Инициализация

Исходное сообщение разбивается на блоки по 512 бит в каждом. Последний блок дополняется до длины, кратной 512 бит. Сначала добавляется 1 а потом нули, чтобы длина блока стала равной 512 — 64 бит. В оставшиеся 64 бита записывается длина исходного сообщения в битах. Дополнение последнего блока осуществляется всегда, даже если сообщение уже имеет нужную длину. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Инициализируются пять 32-битовых переменных.

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

Определяются четыре нелинейные операции и четыре константы.

	K_t = 0x5A827999	0≤t≤19
	K_t = 0x6ED9EBA1	20≤t≤39
	K_t = 0x8F1BBCDC	40≤t≤59
	K_t = 0xCA62C1D6	60≤t≤79

Главный цикл

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

W_t = M_t                                      при 0≤t≤15
W_t = (W_t_-3W_t_-8W_t_-14W_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-битное хеш-значение.

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

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

Замечание: Все используемые переменные 32 бита.

Инициализация переменных:
h0 = 0x67452301
h2 = 0xEFCDAB89
h3 = 0x98BADCFE
h4 = 0x10325476
h5 = 0xC3D2E1F0

Предварительная обработка:
Присоединяем бит '1' к сообщению
присоединяем k битов '0', где k наименьшее число ≥ 0 такое что длина получившегося сообщения(в битах) сравнима с 448 (mod 512)
добавленная длина сообщения в битах, (после предварительной обработки), в битах.

В процессе сообщение разбивается последовательно по 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 = h2
    c = h3
    d = h4
    e = h5

    Основной цикл:
    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 d
            k = 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 d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Добавляем хеш-значение этой части к результату:
    h0 = h0 + a
    h2 = h2 + b 
    h3 = h3 + c
    h4 = h4 + d
    h5 = h5 + e

Итог конечное хеш-значение:
digest = hash = h0 append h2 append h3 append h4 append h5

(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)

Примеры

Ниже приведены примеры хешей SHA-1. Для всех сообщений подразумевается использование кодировки панграммы на русском:

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

Криптоанализ

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

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

При решении методом «грубой силы»:

вторая задача требует 2¹⁶⁰ операций.
первая же требует в среднем 2^160/2 = 2⁸⁰ операций, если использовать парадокс дней рождения.

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

В феврале 2005 года Сяоюнь Ван, Йицунь Лиза Йинь и Хунбо Ю представили атаку на полноценный SHA-1, которая требует менее 2⁶⁹ операций.

О методе авторы пишут:

Мы представляем набор стратегий и соответствующих методик, которые могут быть использованы для устранения некоторых важных препятствий в поиске коллизий в 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, 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³³ операций.

В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 2⁶³ операций. В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном.

Существует масштабный исследовательский проект, стартовавший в технологическом университете австрийского города Грац, который : «… использует компьютеры соединенные через Интернет, для проведения исследований в области криптоанализа. Вы можете поучаствовать в проекте загрузив и запустив бесплатную программу на своем компьютере.»^[3]

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

Бурт Калински, глава исследовательского отдела в «лаборатории RSA» предсказывает, что первая атака по нахождению прообраза будет успешно осуществлена в ближайшие 5-10 лет.

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

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

И MD4.

Сходства:

Четыре этапа.
Каждое действие прибавляется к ранее полученному результату.
Размер блока обработки равный 512 бит.
Оба алгоритма выполняют сложение по модулю 2³², они рассчитаны на 32-битную архитектуру.

Различия:

В SHA-1 на четвертом этапе используется та же функция f, что и на втором этапе.
В
В SHA-1 добавлена пятая переменная.
SHA-1 использует циклический код исправления ошибок.
В SHA на каждом этапе используется постоянное значение сдвига.
В
В
SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5 на той же аппаратуре.

Брюс Шнайер делает следующий вывод : «SHA-1 — это MD5 — это

Сравнение с ГОСТ Р 34.11-94

Ряд отличительных особенностей ГОСТ Р 34.11-94:

При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S — боксах, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий алгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1.
Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2¹²⁸, что во много раз превосходит 2⁸⁰для SHA-1.
Скорость обработки данных для SHA-1 — 48.462*2²⁰ байт/с, а для ГОСТ Р 34.11-94 — 9.977*2²⁰ байт/с.

Сравнение с другими SHA

В таблице, «промежуточный размер хеша» означает «размер внутренней хеш-суммы» после каждой итерации.

Вариации алгоритма		Размер выходного хеша (бит)	Промежуточный размер хеша (бит)	Размер блока (бит)	Максимальная длина входного сообщения (бит)	Размер слова (бит)	Количество раундов	Используемые операции	Найденные коллизии
SHA-0		160	160	512	2⁶⁴ − 1	32	80	+,and,or,xor,rotl	Есть
SHA-1		160	160	512	2⁶⁴ − 1	32	80	+,and,or,xor,rotl	2⁵² операций
	32	64	+,and,or,xor,shr,rotr	Нет
	SHA-512/384	512/384	512	1024	2¹²⁸ − 1	64	80	+,and,or,xor,shr,rotr	Нет

Использование

SHA-1 используется в следующих приложениях:

SHA-1 является основой блочного шифра

Примечания

↑ Finding Collisions in the Full SHA-1 (англ.). — Статья китайских исследователей о взломе SHA-1.
↑ Finding SHA-1 Characteristics: General Results and Applications (англ.).
↑ SHA-1 Collision Search Graz (англ.). — Исследовательский проект технологического университета Граца.
↑ NIST Comments on Cryptanalytic Attacks on SHA-1 (англ.). — Официальный комментарий NIST по поводу атак на SHA-1.
↑ NIST Hash Competition (англ.). — Конкурс на разработку SHA-3.

Ссылки

Литература

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
Нильс Фергюсон, Брюс Шнайер Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — С. 432. — ISBN 0-471-22357-3

Wikimedia Foundation.
2010.

SHA1 — это… Что такое SHA1?

Криптографическая хеш-функция
Название	SHA-1
Разработчик	NSA совместно с NIST
Создан	1995
Опубликован	1995
Размер хеша	160 бит
Число раундов	80
Тип	хеш-функция

Содержание

История

В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1. Немного спустя, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA.

Описание алгоритма

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

Инициализация

Инициализируются пять 32-битовых переменных.

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

Определяются четыре нелинейные операции и четыре константы.

	K_t = 0x5A827999	0≤t≤19
	K_t = 0x6ED9EBA1	20≤t≤39
	K_t = 0x8F1BBCDC	40≤t≤59
	K_t = 0xCA62C1D6	60≤t≤79

Главный цикл

W_t = M_t                                      при 0≤t≤15
W_t = (W_t_-3W_t_-8W_t_-14W_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-битное хеш-значение.

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

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

Замечание: Все используемые переменные 32 бита.

Инициализация переменных:
h0 = 0x67452301
h2 = 0xEFCDAB89
h3 = 0x98BADCFE
h4 = 0x10325476
h5 = 0xC3D2E1F0

Предварительная обработка:
Присоединяем бит '1' к сообщению
присоединяем k битов '0', где k наименьшее число ≥ 0 такое что длина получившегося сообщения(в битах) сравнима с 448 (mod 512)
добавленная длина сообщения в битах, (после предварительной обработки), в битах.

В процессе сообщение разбивается последовательно по 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 = h2
    c = h3
    d = h4
    e = h5

    Основной цикл:
    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 d
            k = 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 d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Добавляем хеш-значение этой части к результату:
    h0 = h0 + a
    h2 = h2 + b 
    h3 = h3 + c
    h4 = h4 + d
    h5 = h5 + e

Итог конечное хеш-значение:
digest = hash = h0 append h2 append h3 append h4 append h5

(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)

Примеры

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

Криптоанализ

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

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

При решении методом «грубой силы»:

вторая задача требует 2¹⁶⁰ операций.
первая же требует в среднем 2^160/2 = 2⁸⁰ операций, если использовать парадокс дней рождения.

О методе авторы пишут:

Мы представляем набор стратегий и соответствующих методик, которые могут быть использованы для устранения некоторых важных препятствий в поиске коллизий в 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, 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.

В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 2⁶³ операций. В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном.

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

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

И MD4.

Сходства:

Четыре этапа.
Каждое действие прибавляется к ранее полученному результату.
Размер блока обработки равный 512 бит.
Оба алгоритма выполняют сложение по модулю 2³², они рассчитаны на 32-битную архитектуру.

Различия:

В SHA-1 на четвертом этапе используется та же функция f, что и на втором этапе.
В
В SHA-1 добавлена пятая переменная.
SHA-1 использует циклический код исправления ошибок.
В SHA на каждом этапе используется постоянное значение сдвига.
В
В
SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5 на той же аппаратуре.

Брюс Шнайер делает следующий вывод : «SHA-1 — это MD5 — это

Сравнение с ГОСТ Р 34.11-94

Ряд отличительных особенностей ГОСТ Р 34.11-94:

При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S — боксах, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий алгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1.
Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2¹²⁸, что во много раз превосходит 2⁸⁰для SHA-1.
Скорость обработки данных для SHA-1 — 48.462*2²⁰ байт/с, а для ГОСТ Р 34.11-94 — 9.977*2²⁰ байт/с.

Сравнение с другими SHA

В таблице, «промежуточный размер хеша» означает «размер внутренней хеш-суммы» после каждой итерации.

Вариации алгоритма		Размер выходного хеша (бит)	Промежуточный размер хеша (бит)	Размер блока (бит)	Максимальная длина входного сообщения (бит)	Размер слова (бит)	Количество раундов	Используемые операции	Найденные коллизии
SHA-0		160	160	512	2⁶⁴ − 1	32	80	+,and,or,xor,rotl	Есть
SHA-1		160	160	512	2⁶⁴ − 1	32	80	+,and,or,xor,rotl	2⁵² операций
	32	64	+,and,or,xor,shr,rotr	Нет
	SHA-512/384	512/384	512	1024	2¹²⁸ − 1	64	80	+,and,or,xor,shr,rotr	Нет

Использование

SHA-1 используется в следующих приложениях:

SHA-1 является основой блочного шифра

Примечания

↑ Finding Collisions in the Full SHA-1 (англ.). — Статья китайских исследователей о взломе SHA-1.
↑ Finding SHA-1 Characteristics: General Results and Applications (англ.).
↑ SHA-1 Collision Search Graz (англ.). — Исследовательский проект технологического университета Граца.
↑ NIST Comments on Cryptanalytic Attacks on SHA-1 (англ.). — Официальный комментарий NIST по поводу атак на SHA-1.
↑ NIST Hash Competition (англ.). — Конкурс на разработку SHA-3.

Ссылки

Литература

Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
Нильс Фергюсон, Брюс Шнайер Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — С. 432. — ISBN 0-471-22357-3

Wikimedia Foundation.
2010.

1 — это… Что такое SHA-1?

Криптографическая хеш-функция
Название	SHA-1
Создан	1995
Опубликован	1995
Размер хеша	160 бит
Число раундов	80
Тип	хеш-функция

Secure Hash Algorithm 1 — алгоритм криптографического хеширования. Описан в RFC 3174. Для входного сообщения произвольной длины (максимум бит, что равно 2 эксабайта) алгоритм генерирует 160-битное хеш-значение, называемое также дайджестом сообщения. Используется во многих криптографических приложениях и протоколах. Также рекомендован в качестве основного для государственных учреждений в США. Принципы, положенные в основу SHA-1, аналогичны тем, которые использовались Рональдом Ривестом при проектировании MD4.

История

В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1. Немного спустя, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1 Возможно, это и была ошибка, открытая NSA.

Описание алгоритма

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

SHA-1 реализует хеш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хеш-блоков до этого момента. Иными словами хеш блока равен . Хеш-значением всего сообщения является выход последнего блока.

Инициализация

Исходное сообщение разбивается на блоки по 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

Определяются четыре нелинейные операции и четыре константы.

Главный цикл

Главный цикл итеративно обрабатывает каждый 512-битный блок. Итерация состоит из четырех этапов по двадцать операций в каждом. Блок сообщения преобразуется из 16 32-битовых слов в 80 32-битовых слов по следующему правилу:

                                      при 0≤t≤15
 = (_-3_-8_-14_-16) << 1     при 16≤t≤79

здесь << — это циклический сдвиг влево

для от 0 до 79 
temp = (a<<5) + (b,c,d) + e + 
e = d 
d = c 
c = b<<30                                
b = a 
a = temp

После этого a, b, c, d, e прибавляются к A, B, C , D , E соответственно. Начинается следующая итерация.

Итоговым значением будет объединение пяти 32-битовых слов в одно 160-битное хеш-значение.

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

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

Замечание: Все используемые переменные 32 бита.

Инициализация переменных:
h0 = 0x67452301
h2 = 0xEFCDAB89
h3 = 0x98BADCFE
h4 = 0x10325476
h5 = 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 = h2
    c = h3
    d = h4
    e = h5

    Основной цикл:
    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 d
            k = 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 d
            k = 0xCA62C1D6

        temp = (a leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Добавляем хеш-значение этой части к результату:
    h0 = h0 + a
    h2 = h2 + b 
    h3 = h3 + c
    h4 = h4 + d
    h5 = h5 + e

Итоговое хеш-значение:
digest = hash = h0 append h2 append h3 append h4 append h5

(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)

Примеры

Ниже приведены примеры хешей 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

Криптоанализ

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

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

При решении методом «грубой силы»:

вторая задача требует 2¹⁶⁰ операций.
первая же требует в среднем 2^160/2 = 2⁸⁰ операций, если использовать атаку Дней рождения.

В январе 2005 года Vincent Rijmen и Elisabeth Oswald опубликовали сообщение об атаке на усечённую версию SHA-1 (53 раунда вместо 80), которая позволяет находить коллизии меньше, чем за 2⁸⁰ операций.

О методе авторы пишут:

Мы представляем набор стратегий и соответствующих методик, которые могут быть использованы для устранения некоторых важных препятствий в поиске коллизий в 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.

В августе 2005 года на CRYPTO 2005 эти же специалисты представили улучшенную версию атаки на полноценный SHA-1, с вычислительной сложностью в 2⁶³ операций. В декабре 2007 года детали этого улучшения были проверены Мартином Кохраном.

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

Из-за блочной и итеративной структуры алгоритмов, а также отсутствия специальной обработки в конце хеширования, все хеш-функции семейства SHA уязвимы к атакам удлинением сообщения и коллизии при частичном хешировании сообщения.^[5] Эти атаки позволяют подделывать сообщения, подписанные только хешем — или — путём удлинения сообщения и пересчёту хеша без знания значения ключа. Простейшим исправлением, позволяющим защититься от этих атак, является двойное хеширование — ( — блок нулей той же длины, что и блок хеш-функции).

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

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4.

Сходства:

Четыре этапа.
Каждое действие прибавляется к ранее полученному результату.
Размер блока обработки равный 512 бит.
Оба алгоритма выполняют сложение по модулю 2³², они рассчитаны на 32-битную архитектуру.

Различия:

В SHA-1 на четвертом этапе используется та же функция f, что и на втором этапе.
В MD5 в каждом действии используется уникальная прибавляемая константа. В SHA-1 константы используются повторно для каждой из четырех групп.
В SHA-1 добавлена пятая переменная.
SHA-1 использует циклический код исправления ошибок.
В MD5 четыре сдвига, используемые на каждом этапе отличаются от значений, используемых на предыдущих этапах. В SHA на каждом этапе используется постоянное значение сдвига.
В MD5 четыре различных элементарных логических функции, в SHA-1 — три.
В MD5 длина дайджеста составляет 128 бит, в SHA-1 — 160 бит.
SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25 % медленнее, чем MD5 на той же аппаратуре.

Сравнение с ГОСТ Р 34.11-94

Ряд отличительных особенностей ГОСТ Р 34.11-94:

При обработке блоков используются преобразования по алгоритму ГОСТ 28147—89;
Обрабатывается блок длиной 256 бит, и выходное значение тоже имеет длину 256 бит.
Применены меры борьбы против поиска коллизий, основанном на неполноте последнего блока.
Обработка блоков происходит по алгоритму шифрования ГОСТ 28147—89, который содержит преобразования на S-блоках, что существенно осложняет применение метода дифференциального криптоанализа к поиску коллизий алгоритма ГОСТ Р 34.11-94. Это существенный плюс по сравнению с SHA-1.
Теоретическая криптостойкость ГОСТ Р 34.11-94 равна 2¹²⁸, что во много раз превосходит 2⁸⁰для SHA-1.

Сравнение с другими SHA

В таблице, «промежуточный размер хеша» означает «размер внутренней хеш-суммы» после каждой итерации.

Вариации алгоритма		Размер выходного хеша (бит)	Промежуточный размер хеша (бит)	Размер блока (бит)	Максимальная длина входного сообщения (бит)	Размер слова (бит)	Количество раундов	Используемые операции	Найденные коллизии
SHA-0		160	160	512	2⁶⁴ − 1	32	80	+,and, or, xor, rotl	Есть
SHA-1		160	160	512	2⁶⁴ − 1	32	80	+,and, or, xor, rotl	2⁵² операций
SHA-2	SHA-256/224	256/224	256	512	2⁶⁴ − 1	32	64	+,and, or, xor, shr, rotr	Нет
SHA-2	SHA-512/384	512/384	512	1024	2¹²⁸ − 1	64	80	+,and, or, xor, shr, rotr	Нет

Использование

SHA-1 используется в следующих приложениях:

S/MIME — дайджесты сообщений.
SSL — дайджесты сообщений.
IPSec — для алгоритма проверки целостности в соединении «точка-точка».
SSH — для проверки целостности переданных данных.
PGP — для создания электронной цифровой подписи.
Git — для идентификации каждого объекта по SHA-1-хешу от хранимой в объекте информации.
Mercurial — для идентификации ревизий
BitTorrent — для проверки целостности загружаемых данных.

SHA-1 является основой блочного шифра SHACAL.

Примечания

См. также

Ссылки

Литература

🔒 Учебное пособие по алгоритму хеширования SHA1 с примерами использования — Information Security Squad

SHA1 — это алгоритм хеширования, созданный Агентством национальной безопасности (АНБ).

Хеш-алгоритм SHA1 обычно используется в приложениях безопасности и целостности данных.

SHA-1 создан в 1995 году как преемник SHA-0.

И SHA1, и SHA-1 одно и тоже.

SHA1 это алгоритм хеширования или дайджеста сообщений, где он генерирует 160-битное уникальное значение из входных данных.

Размер входных данных не имеет значения, поскольку SHA1 всегда генерирует хеш сообщения одинакового размера, который составляет 160 бит.

Это может показаться очень запутанным, но алгоритм предназначен именно для этого.

SHA1 больше не безопасен

SHA1 используется для обеспечения целостности и безопасности данных.

В особенности после 2005 года существует множество различных атак на алгоритм SHA1.

Первый публичные коллизиии опубликованы в 2017 году, и после этого SHA1 не считается безопасным.

В настоящее время для безопасности используются алгоритмы семейства SHA2.

Атака коллизий — это просто другое входное значение, которое может генерировать такое же выходное хеш-значение, которое обманывает системы безопасности.

Инструменты SHA1

В настоящее время существует множество инструментов, и даже некоторые из них есть в интернет для создания хеш-значений SHA1.

По следующему адресу вы можете найти инструмент, который поддерживает множество различных алгоритмов хеширования и кодирования.

https://emn178.github.io/online-tools/sha1.html

Инструменты для взлома SHA1

Есть также некоторые инструменты взлома, которые могут легко взломать популярные слова и пароли.

В частности, системы Linux, Network и Windows используют SHA1 для хеширования и скрытия паролей, но это можно легко взломать с помощью следующих сайтов для взлома.

https://hashkiller.co.uk/Cracker/SHA1

Скажем, мы хотим взломать хэш пароля 717de03c9158ae10675c659c2fe8b27b71d50073 и найти пароль пользователя.

Мы будем использовать следующий онлайн-взломщик SHA1 и предоставим хэш, который мы хотим взломать.

Мы также можем предоставить несколько хэшей SHA1 построчно.

Мы можем увидеть, что открытый текст хэшей — crackme123, который показан в результате взлома зеленым цветом.

Использование SHA1 на Linux

Дистрибутивы Linux, такие как Ubuntu, Debian, Mint, Kali, Fedora и CentOS, предоставляют команду sha1sum, которая может вычислить сумму SHA1 для любого файла.

Использование SHA1 в PHP

Язык программирования PHP предоставляет встроенную функцию вычисления SHA1 с именем sha1 ().

Нам просто нужно предоставить данные или текст, для которого мы можем вычислить хэш.

В этом примере мы вычислим хеш «crackme123».

$str=«crackme123»;

$str_hash = sha1($str);

echo $str_hash;

Использование SHA1 в Python

Python также обеспечивает поддержку алгоритма хеширования SHA1 с модулем / библиотекой hashlib.

Сначала мы импортируем hashlib, а затем используем функцию sha1 (), предоставляя данные или текст, для которого мы хотим вычислить хэш.

В этом примере мы вычислим хеш «crackme».

import hashlib

str=«crackme»

str_hash=hashlib.sha1(str.encode())

print(str_hash)

print(str_hash.hexdigest())

SHA1 или MD5 ?

MD5 — еще один популярный алгоритм хеширования, созданный до SHA1.

Но они использовались в 1990-х и 2000-х годах и были альтернативой друг другу.

В этой части мы сравним алгоритмы хэширования SHA1 и MD5.

Скорость: MD5 имеет меньше сложных алгоритмов, которые делают его быстрее, чем SHA1
Безопасность: SHA1 имеет более сложный алгоритм, который делает его более безопасным, чем MD5.
Имя: SHA1 обозначает Secure Hash Algorithm, где MD5 обозначает Message Digest
Размер хэша: SHA1 создает 160-битный хэш / дайджест сообщения, где MD5 создает 128-битный хэш / дайджест сообщения.
Популярность: MD5 был более популярным, чем SHA1, но в последнее десятилетие он также потерял свою популярность.
Примеры использования: MD5 обычно используется в устройствах с аппаратным ограничением, таких как коммутатор, маршрутизатор, где SHA1 используется в более сильных устройствах, таких как компьютеры.

Криптоанализ SHA-1 — Schneier о безопасности

Криптоанализ SHA-1

Во вторник я написал в блоге о новом криптоаналитическом результате — первой атаке на SHA-1 быстрее, чем грубая сила. Я писал о SHA и необходимости его замены в сентябре прошлого года. Помимо деталей нового нападения, все, что я сказал тогда, остается в силе. Я процитирую эту статью, при необходимости добавив новые материалы.

Односторонние хэш-функции — это криптографическая конструкция, используемая во многих приложениях.Они используются в сочетании с алгоритмами с открытым ключом как для шифрования, так и для цифровых подписей. Они используются при проверке целостности. Они используются при аутентификации. У них есть всевозможные приложения в большом количестве разных протоколов. Односторонние хеш-функции — это не просто алгоритмы шифрования, но и рабочие лошадки современной криптографии.
В 1990 году Рон Ривест изобрел хеш-функцию MD4. В 1992 году он улучшил MD4 и разработал другую хеш-функцию: MD5. В 1993 году Агентство национальной безопасности опубликовало хеш-функцию, очень похожую на MD5, под названием SHA (Secure Hash Algorithm).Затем в 1995 году, сославшись на недавно обнаруженную слабость, которую оно отказалось раскрывать, АНБ внесло изменения в SHA. Новый алгоритм получил название SHA-1. Сегодня самой популярной хэш-функцией является SHA-1, а MD5 все еще используется в старых приложениях.
Односторонние хеш-функции должны иметь два свойства. Во-первых, они в одну сторону. Это означает, что взять сообщение и вычислить хеш-значение легко, но невозможно взять хеш-значение и воссоздать исходное сообщение. (Под «невозможным» я имею в виду «не может быть выполнено в разумные сроки.Два, они без столкновений. Это означает, что невозможно найти два сообщения с одинаковым хеш-значением. Криптографические аргументы в пользу этих двух свойств тонки, и я предлагаю любопытным читателям узнать больше в моей книге Applied Cryptography .
Нарушение хэш-функции означает показ того, что одно из этих свойств — или оба — неверны.

Ранее на этой неделе три китайских криптографа показали, что SHA-1 не свободен от коллизий. То есть они разработали алгоритм обнаружения коллизий быстрее, чем брутфорс.

SHA-1 создает 160-битный хэш. То есть каждое сообщение хешируется до 160-битного числа. Учитывая, что существует бесконечное количество сообщений, хеширующих каждое возможное значение, существует бесконечное количество возможных конфликтов. Но поскольку количество возможных хешей настолько велико, вероятность найти один случайно ничтожно мала (точнее, один из 2 ⁸⁰). Если вы хэшируете 2 ⁸⁰ случайных сообщений, вы найдете одну пару с одинаковым значением хеширования. Это метод «грубой силы» поиска коллизий, и он зависит исключительно от длины хеш-значения.«Нарушение» хэш-функции означает возможность быстрее находить коллизии. Так и поступили китайцы.

Они могут найти коллизии в SHA-1 в 2 ⁶⁹ вычислениях, что примерно в 2000 раз быстрее, чем грубая сила. В настоящее время это практически осуществимо с учетом современных технологий. Это подтверждают два сопоставимых массовых вычисления.

В 1999 году группа криптографов построила взломщик DES. Он смог выполнить 2 ⁵⁶ операций DES за 56 часов.Сборка машины стоила 250 тысяч долларов, хотя дубликаты могли быть сделаны в диапазоне от 50 до 75 тысяч долларов. Если экстраполировать эту машину с использованием закона Мура, то можно сказать, что аналогичная машина, построенная сегодня, может выполнить 2 ⁶⁰ вычислений за 56 часов и 2 ⁶⁹ вычислений за три с четвертью года. Или машина стоимостью от 25 до 38 миллионов долларов может выполнить 2 ⁶⁹ вычислений за те же 56 часов.

Что касается программного обеспечения, то основным сопоставимым критерием является поиск ключей 2 ⁶⁴, выполненный распределенным.net и завершившийся в 2002 году.В одной статье об этом говорится: «В ходе конкурса в нем приняли участие 331 252 пользователя, которые позволили использовать неиспользуемые циклы процессора для обнаружения ключей. Спустя 1757 дней (4,81 года) участник из Японии обнаружил ключ к победе ». Закон Мура означает, что сегодня вычисления занимали бы четверть времени — или потребовали бы четверть количества компьютеров — поэтому сегодня вычисление 2 ⁶⁹ заняло бы в восемь раз больше времени или потребовало бы в восемь раз больше компьютеров.

Величина этих результатов зависит от того, кто вы. Если вы криптограф, это большое дело. Хотя эти результаты не являются революционными, они являются значительным достижением в данной области. Методы, описанные исследователями, вероятно, будут иметь другие приложения, и в результате мы сможем лучше разрабатывать безопасные системы. Так развивается наука криптографии: мы учимся разрабатывать новые алгоритмы, взламывая другие алгоритмы. Кроме того, алгоритмы АНБ считаются своего рода инопланетной технологией: они исходят от высшей расы без каких-либо объяснений.Любой успешный криптоанализ против алгоритма NSA — интересная точка данных в извечном вопросе о том, насколько они действительно хороши в этом.

Для обычного пользователя Интернета эта новость не повод для паники. Никто не собирается в ближайшее время взламывать цифровые подписи или читать зашифрованные сообщения. После этих заявлений электронный мир стал не менее безопасным, чем был раньше.

Но в АНБ есть старая поговорка: «Атаки всегда улучшаются; они никогда не становятся хуже.«Подобно тому, как атака на этой неделе основывается на других статьях, описывающих атаки на упрощенные версии SHA-1, SHA-0, MD4 и MD5, другие исследователи будут опираться на этот результат. Атака на SHA-1 будет продолжать совершенствоваться, поскольку другие читают о ней и разрабатывают более быстрые трюки, оптимизации и т. Д. И закон Мура будет продолжать развиваться, делая даже существующие атаки более быстрыми и доступными.

Джон Каллас, технический директор PGP, сказал об этом лучше всего: «Пора идти, но не бежать к пожарным выходам.Вы не видите дыма, но пожарная сигнализация сработала ». Это в основном то, что я сказал в августе прошлого года.

Нам всем пора отказаться от SHA-1.
К счастью, есть альтернативы. Национальный институт стандартов и технологий уже разработал стандарты для более длинных и более сложных хэш-функций: SHA-224, SHA-256, SHA-384 и SHA-512. Это уже государственные стандарты, и их уже можно использовать. Это хорошая временная возможность, но я бы хотел увидеть больше.
Я бы хотел, чтобы NIST организовал всемирное соревнование за новую хеш-функцию, как это было сделано для нового алгоритма шифрования AES, который заменит DES.NIST должен объявить о разработке алгоритмов и провести серию аналитических раундов, в ходе которых сообщество анализирует различные предложения с целью установления нового стандарта.
Большинство имеющихся у нас хеш-функций и все те, которые широко используются, основаны на общих принципах MD4. Очевидно, мы многое узнали о хэш-функциях за последнее десятилетие, и я думаю, что мы можем начать применять эти знания для создания чего-то еще более безопасного.

Хеш-функции — наименее изученный криптографический примитив, а методы хеширования гораздо менее развиты, чем методы шифрования.Регулярно при хешировании получаются удивительные криптографические результаты. У меня есть статья, написанная с Джоном Келси, в которой описывается алгоритм поиска вторых прообразов с помощью SHA-1 — метод, который обобщается почти на все другие хэш-функции — в вычислениях 2 ¹⁰⁶: намного меньше, чем вычисления 2 ¹⁶⁰ для грубой силы. Эта атака является полностью теоретической и даже отдаленно не практичной, но она демонстрирует, что нам еще многое предстоит узнать о хешировании.

Перечитав то, что я написал в сентябре прошлого года, становится ясно, что я ожидал, что это произойдет, но не так быстро и не так впечатляюще.Китайские криптографы заслуживают высокой оценки за свою работу, и нам нужно приступить к работе по замене SHA.

Теги: аутентификация, криптоанализ, криптография, хеши, SHA-1, подписи

Отправлено 18 февраля 2005 г., 23:24 •
126 комментариев

SHA1 (+ Salt) дешифратор — пароль SHA-1, хэш

Поиск инструмента

SHA-1

Инструмент для расшифровки / шифрования с помощью SHA1. Хэш SHA-1 — это отпечаток из 40 символов (шестнадцатеричный), который предназначен для идентификации исходных данных и гарантии их целостности, что полезно в криптографии.

Результаты

SHA-1 — dCode

Тег (и): функция хеширования, современная криптография

dCode и вы

dCode является бесплатным, а его инструменты являются ценным подспорьем в играх, математике, геокэшинге, головоломках и задачах, которые нужно решать каждый день!
Предложение? обратная связь? Жук ? идея ? Запись в dCode !

SHA-1 декодер

SHA1 кодировщик

Инструмент для расшифровки / шифрования с помощью SHA1.Хэш SHA-1 — это отпечаток из 40 символов (шестнадцатеричный), который предназначен для идентификации исходных данных и гарантии их целостности, что полезно в криптографии.

Ответы на вопросы

Как зашифровать с использованием алгоритма безопасного хеширования (SHA-1)?

Encryption рассчитывает числовой отпечаток из 40 шестнадцатеричных символов. Алгоритм использует нелинейные функции, вот 3 основных:

$$ C (x, y, z) = (x \ wedge y) \ vee (\ lnot x \ wedge z) \\ P (x, y , z) = x \ oplus y \ oplus z \\ M (x, y, z) = (x \ wedge y) \ vee (x \ wedge z) $$

С частями $ x, y, z $ строка для кодирования или фиксированные значения среди 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0…

Пример: dCode зашифрован с помощью посадочного места 15fc6eed5ed024bfb86c4130f998dde437f528ee.

Как расшифровать хеш SHA-1?

Поскольку шифрование — это хеширование, основанное на нелинейных функциях, не существует метода дешифрования . Это означает, что для получения пароля, соответствующего хешу sha-1 , нет другого выбора, кроме как попробовать все возможные пароли!

Технически эта операция займет несколько тысяч лет даже на самых мощных компьютерах в мире.Однако список паролей, используемых в реальной жизни, более ограничен, и появляется возможность предварительно рассчитать наиболее вероятные отпечатки пальцев.

dCode использует свои базы данных слов (10 миллионов потенциальных паролей) для ускорения этой обработки. Однако, если пароль является редким или сочетается с солёным, он, вероятно, не будет найден.

Как распознать зашифрованный текст SHA-1?

Какие варианты шифра SHA-1?

Поиск в базе данных можно усложнить, добавив соль к слову (префикс или суффикс, или и то, и другое).В самом деле, если заранее вычислить отпечатки всех слов уже сложно, но возможно, то становится еще труднее предварительно вычислить со всеми возможными префиксами и суффиксами.

Пример: SHA1 (dCode) = 15fc6eed5ed024bfb86c4130f998dde437f528ee, но SHA1 (dCodeSUFFIX) = 9b63fcb31388acee8879018244a3d107033890, который рекомендуется дважды

Что такое радужный стол?

Радужная таблица — это база данных слов со всеми предварительно вычисленными хэшами, которая хранится для ускорения и возможности распараллеливания вычислений отпечатков пальцев.

Что означает SHA1?

SHA1 означает алгоритм безопасного хеширования

Когда был изобретен SHA1?

Агентством национальной безопасности в 1995 г.

Задайте новый вопрос

Исходный код

dCode сохраняет право собственности на исходный код онлайн-инструмента SHA-1.За исключением явной лицензии с открытым исходным кодом (обозначенной CC / Creative Commons / free), любой алгоритм, апплет или фрагмент (конвертер, решатель, шифрование / дешифрование, кодирование / декодирование, шифрование / дешифрование, переводчик) или любая функция (преобразование, решение, дешифрование / encrypt, decipher / cipher, decode / encode, translate), написанных на любом информатическом языке (PHP, Java, C #, Python, Javascript, Matlab и т. д.), доступ к данным, скриптам или API не будет бесплатным, то же самое для SHA- 1 для автономного использования на ПК, планшете, iPhone или Android!

Нужна помощь?

Пожалуйста, заходите в наше сообщество в Discord для получения помощи!

Вопросы / комментарии

Сводка

Инструменты аналогичные

Поддержка

Форум / Справка

Рекламные объявления

Ключевые слова

sha1, sha, хеш, безопасный, алгоритм, пароль, двойной, соль, соленый

Ссылки

Источник: https: // www.dcode.fr/sha1-hash

.Криптоалгоритм

SHA1, лежащий в основе интернет-безопасности, может упасть к 2018 году

Принцип обнаружения коллизий в криптографических алгоритмах, таких как MD5 и SHA1.

Широко используемый криптографический алгоритм, используемый для защиты конфиденциальных веб-сайтов, программного обеспечения и корпоративных серверов, достаточно слаб, чтобы хорошо финансируемые преступники могли взломать его в следующие шесть лет, сказал криптограф.

Прогноз об алгоритме SHA1, недавно опубликованный в списке рассылки хэш-функций, спонсируемом Национальным институтом стандартов и технологий, основан на расчетах, которые, по признанию автора и других криптографов, являются приблизительными.Математические вычисления также включают несколько предположений, которые никоим образом не являются достоверными. В то же время возможность выполнить надежную «атаку коллизии» на SHA1 имела бы катастрофические последствия для безопасности Интернета.

Подобные атаки с коллизией на более слабом алгоритме MD5 демонстрируют, насколько ужасным и масштабным может быть нанесенный в результате ущерб. Шпионское вредоносное ПО Flame, которое США и Израиль, как полагают, использовали для слежки за уязвимыми иранскими сетями, использовало такой эксплойт для взлома механизма Microsoft Windows Update, чтобы вредоносная программа могла распространяться с компьютера на компьютер внутри зараженной сети.Отдельно, в 2008 году группа компьютерных ученых и исследователей в области безопасности использовала эту технику для создания основного сертификата уровня защищенных сокетов, который мог бы аутентифицировать практически любой веб-сайт по их выбору.

SHA1 значительно более устойчив к атакам коллизий, чем MD5, при которых два разных источника открытого текста генерируют один и тот же зашифрованный текст или цифровую подпись. В результате центры сертификации SSL, компании-разработчики программного обеспечения и большинство других организаций, заботящихся о безопасности, прекратили использование MD5 в пользу SHA1 или, еще лучше, SHA2, который считается еще более сильным.(Буквально на этой неделе NIST обозначил алгоритм, известный как Keccak, как SHA3.) Криптографы давно предполагали, что эти более продвинутые алгоритмы постигнет та же участь, что и MD5, поскольку скорость обработки компьютеров становится все выше. Поскольку SHA1 является основным элементом цифровых сертификатов, удостоверяющих подлинность веб-сайтов, коммерческого программного обеспечения и учетных данных, используемых для администрирования корпоративных серверов, практическая атака на него в ближайшее время может привести к ужасным последствиям.

«Когда это произойдет, это будет катастрофой, потому что SHA1 есть повсюду», — сказал Мэтью Грин, профессор, специализирующийся на криптографии в Университете Джонса Хопкинса.«Вы могли бы быть Microsoft, вы могли бы быть Google, если бы вы смогли провести атаку на SHA1».

Некоторые положения Федерального стандарта обработки информации в настоящее время требуют использования SHA1.

SHA1 и другие алгоритмы хеширования генерируют цифровой отпечаток, который теоретически уникален для каждого отдельного файла или текстового ввода, который они подписывают. Когда основной открытый текст изменяется даже незначительными способами, подпись изменяется. Алгоритмы используются криптографически, чтобы доказать отсутствие несанкционированных изменений на веб-сайтах или в программном коде.Атаки на основе коллизий подрывают эту гарантию, позволяя злоумышленникам подделывать криптографические подписи, предоставляемые алгоритмом.

Основываясь на приблизительных расчетах Джесси Уокера, сотрудника Intel и разработчика алгоритма, занявшего второе место SHA3, известного как Skein, SHA1 может упасть раньше, чем многие ожидали. Он пришел к такому выводу, основываясь на продолжающемся росте скорости вычислений и появлении облачных сервисов, таких как Amazon EC2, которые позволяют людям арендовать стандартные серверы всего за 4 цента в час.

«Таким образом, коллизионная атака вполне укладывается в рамки того, что синдикат организованной преступности может практически выделить к 2018 году, а университетский исследовательский проект — к 2021 году», — написал Уокер, согласно расшифровке стенограммы, включенной в сообщение в блоге коллеги-криптографа Брюса Шнайера. Далее Уокер заявил, что его предположения не учитывают использование графических процессоров и другого оптимизированного оборудования, поэтому «необходимость перехода от SHA-1 для функций защиты от столкновений, вероятно, более актуальна, чем эта обратная связь. анализ конверта подсказывает.«

Оценка

Уокера также основана на предположении, что коллизионная атака с использованием SHA1 будет основана на методе, изложенном ранее в этом году Марком Стивенсом, криптографом из Centrum Wiskunde & Informatica в Амстердаме. Если злоумышленники придумают более эффективный метод проведения коллизионной атаки — как это сделали криптографы мирового класса, стоящие за Flame, — это также может стать фактором, который ускорит падение SHA1. Оценка также предполагает, что закон Мура, наблюдение о том, что вычислительная мощность ~~speed~~ удваивается примерно каждые 18 месяцев, будет сохраняться в обозримом будущем.

«Дело в том, — заключил Шнайер, — что мы в сообществе должны начать миграцию с SHA-1 на SHA-2 / SHA-3 прямо сейчас».

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

— хеш Sha1 из нескольких хешей sha1 -> Безопасно ли идентифицировать файл?

Переполнение стека

Около
Продукты
Для команд

Переполнение стека
Общественные вопросы и ответы
Переполнение стека для команд
Где разработчики и технологи делятся частными знаниями с коллегами
Вакансии
Программирование и связанные с ним технические возможности карьерного роста
Талант
Нанимайте технических специалистов и создавайте свой бренд работодателя
Реклама
Обратитесь к разработчикам и технологам со всего мира
О компании

Загрузка…

.
No related posts.

Ноябрь 2024
Пн	Вт	Ср	Чт	Пт	Сб	Вс
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Sha1 это что: Sha-1 | Контроль Разума | Fandom

разница между SHA-1, SHA-2 и SHA-256 алгоритмами хеширования

Цифровые подписи

SHA-1 и SHA-2

SSL-индустрия выбрала SHA в качестве своего алгоритма хеширования для цифровых подписей

Сколько хешей?

Переход на SHA-2

Обеспечение безопасности подписей

SHA-1 — Википедия

История

Описание алгоритма

Инициализация

Главный цикл

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

Примеры

Криптоанализ

SHAppening

Реальный взлом: SHAttered (нахождение коллизий)

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

Сравнение с ГОСТ Р 34.11-94

Сравнение с другими SHA

Использование

Отказ от использования

См. также

Примечания

Литература

Ссылки

SHA-1 — Википедия. Что такое SHA-1

История

Описание алгоритма

Инициализация

Главный цикл

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

Примеры

Криптоанализ

SHAppening

Реальный взлом: SHAttered (нахождение коллизий)

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

Сравнение с ГОСТ Р 34.11-94

Сравнение с другими SHA

Использование

Отказ от использования

См. также

Примечания

Литература

Ссылки

Sha1 — это… Что такое Sha1?

Содержание

История

Описание алгоритма

Инициализация

Главный цикл

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

Примеры

Криптоанализ

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

Сравнение с ГОСТ Р 34.11-94

Сравнение с другими SHA

Использование

Примечания

Ссылки

Литература

SHA1 — это… Что такое SHA1?

Содержание

История

Описание алгоритма

Инициализация

Главный цикл

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

Примеры

Криптоанализ

Сравнение SHA-1 с другими алгоритмами

Сравнение с MD5

Сравнение с ГОСТ Р 34.11-94

Сравнение с другими SHA

Использование

Примечания