Алгоритмы хеширования: Алгоритм хеширования данных: просто о сложном

Содержание

Алгоритм хеширования данных: просто о сложном

Криптографические хэш-функции распространены очень широко. Они используются для хранения паролей при аутентификации, для защиты данных в системах проверки файлов, для обнаружения вредоносного программного обеспечения, для кодирования информации в блокчейне (блок — основной примитив, обрабатываемый Биткойном и Эфириумом). В этой статье пойдет разговор об алгоритмах хеширования: что это, какие типы бывают, какими свойствами обладают.

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

Что такое хеш (хэш, hash)?

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

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

И если во входных данных изменить хотя бы один символ, будет создан совершенно другой хэш.

Убедиться в этом можно на любом онлайн-генераторе. Набрав слово «Otus» и воспользовавшись алгоритмом sha1 (Secure Hashing Algorithm), мы получим хеш 7576750f9d76fab50762b5987739c18d99d2aff7. При изменении любой буквы изменится и результат, причем изменится полностью. Мало того, если просто поменять регистр хотя бы одной буквы, итог тоже будет совершенно иным: если написать «otus», алгоритм хэш-функции отработает со следующим результатом: 1bbd70dc1b6fc84e5617ca8703c72c744b3b4fc1. Хотя общие моменты все же есть: строка

всегда состоит из сорока символов.

В предыдущем примере речь шла о применении хэш-алгоритма для слова из 4 букв. Но с тем же успехом можно вставить слово из 1000 букв — все равно после обработки данных на выходе получится значение из 40 символов. Аналогичная ситуация будет и при обработке полного собрания сочинений Льва Толстого.

Криптостойкость функций хеширования

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

Проблемы хэшей

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

Цель хороших криптографических функций — максимально усложнить вероятность нахождения способов генерации входных данных, хешируемых с одинаковым значением. Как уже было сказано ранее, вычисление хэша не должно быть простым, а сам алгоритм должен быть устойчив к «атакам нахождения прообраза». Необходимо, чтобы на практике было чрезвычайно сложно (а лучше — невозможно) вычислить обратные детерминированные шаги, которые предприняты для воспроизведения созданного хешем значения.

Если S = hash (x), то, в идеале, нахождение x должно быть практически невозможным.

Алгоритм MD5 и его подверженность взлому

MD5 hash — один из первых стандартов алгоритма, который применялся в целях проверки целостности файлов (контрольных сумм). Также с его помощью хранили пароли в базах данных web-приложений. Функциональность относительно проста — алгоритм выводит для каждого ввода данных фиксированную 128-битную строку, задействуя для вычисления детерминированного результата однонаправленные тривиальные операции в нескольких раундах. Особенность — простота операций и короткая выходная длина, в результате чего MD5 является относительно легким для взлома. А еще он обладает низкой степенью защиты к атаке типа «дня рождения».

Атака дня рождения

Если поместить 23 человека в одну комнату, можно дать 50%-ную вероятность того, что у двух человек день рождения будет в один и тот же день. Если же количество людей довести до 70-ти, вероятность совпадения по дню рождения приблизится к 99,9 %. Есть и другая интерпретация: если голубям дать возможность сесть в коробки, при условии, что число коробок меньше числа голубей, окажется, что хотя бы в одной из коробок находится более одного голубя.

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

Когда разговор идет о сопротивлении коллизиям, то алгоритм MD5 действительно очень слаб. Настолько слаб, что даже бытовой Pentium 2,4 ГГц сможет вычислить искусственные хеш-коллизии, затратив на это чуть более нескольких секунд. Всё это в ранние годы стало причиной утечки большого количества предварительных MD5-прообразов.

SHA1, SHA2, SHA3

Secure Hashing Algorithm (SHA1) — алгоритм, созданный Агентством национальной безопасности (NSA). Он создает 160-битные выходные данные фиксированной длины. На деле SHA1 лишь улучшил MD5 и увеличил длину вывода, а также увеличил число однонаправленных операций и их сложность. Однако каких-нибудь фундаментальных улучшений не произошло, особенно когда разговор шел о противодействии более мощным вычислительным машинам. Со временем появилась альтернатива — SHA2, а потом и

SHA3. Последний алгоритм уже принципиально отличается по архитектуре и является частью большой схемы алгоритмов хеширования (известен как KECCAK — «Кетч-Ак»). Несмотря на схожесть названия, SHA3 имеет другой внутренний механизм, в котором используются случайные перестановки при обработке данных — «Впитывание» и «Выжимание» (конструкция «губки»).

Что в будущем?

Вне зависимости от того, какие технологии шифрования и криптографические новинки будут использоваться в этом направлении, все сводится к решению одной из двух задач: 1) увеличению сложности внутренних операций хэширования; 2) увеличению длины hash-выхода данных с расчетом на то, что вычислительные мощности атакующих не смогут эффективно вычислять коллизию.

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

Источники: • https://vc.ru/crypto/47132-algoritmy-heshirovaniya-prostoe-obyasnenie-slozhnogo; • https://www.kaspersky.ru/blog/the-wonders-of-hashing/3633/.

Как работает хэш-алгоритм SHA-2 (SHA 256)? Разбираем на примере

Автор Мария Багулина

SHA-2 (Secure Hash Algorithm 2) — одно из самых популярных семейств алгоритмов хеширования. В этой статье мы разберём каждый шаг алгоритма SHA-256, принадлежащего к SHA-2, и покажем, как он работает на реальном примере.

Что такое хеш-функция?

Если вы хотите узнать больше о хеш-функциях, можете почитать Википедию. Но чтобы понять, о чём пойдёт речь, давайте вспомним три основные цели хеш-функции:

обеспечить проверку целостности (неизменности) данных;
принимать ввод любой длины и выводить результат фиксированной длины;
необратимо изменить данные (ввод не может быть получен из вывода).

SHA-2 и SHA-256

SHA-2 — это семейство алгоритмов с общей идеей хеширования данных. SHA-256 устанавливает дополнительные константы, которые определяют поведение алгоритма SHA-2. Одной из таких констант является размер вывода. «256» и «512» относятся к соответствующим размерам выходных данных в битах.

Мы рассмотрим пример работы SHA-256.

SHA-256 «hello world». Шаг 1. Предварительная обработка

1. Преобразуем «hello world» в двоичный вид:

 01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100

2. Добавим одну единицу:

01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 1

3. Заполняем нулями до тех пор, пока данные не станут кратны 512 без последних 64 бит (в нашем случае 448 бит):

01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

4. Добавим 64 бита в конец, где 64 бита — целое число с порядком байтов big-endian, обозначающее длину входных данных в двоичном виде. В нашем случае 88, в двоичном виде — «1011000».

01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 10000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 01011000

Теперь у нас есть ввод, который всегда будет без остатка делиться на 512.

Шаг 2. Инициализация значений хеша (h)

Создадим 8 значений хеша. Это константы, представляющие первые 32 бита дробных частей квадратных корней первых 8 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19.

h0 := 0x6a09e667
h2 := 0xbb67ae85
h3 := 0x3c6ef372
h4 := 0xa54ff53a
h5 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Шаг 3. Инициализация округлённых констант (k)

Создадим ещё немного констант, на этот раз их 64. Каждое значение — это первые 32 бита дробных частей кубических корней первых 64 простых чисел (2–311).

0x428a2f98 0x71374491 0xb5c0fbcf 0xe9b5dba5 0x3956c25b 0x59f111f1 0x923f82a4 0xab1c5ed5
0xd807aa98 0x12835b01 0x243185be 0x550c7dc3 0x72be5d74 0x80deb1fe 0x9bdc06a7 0xc19bf174
0xe49b69c1 0xefbe4786 0x0fc19dc6 0x240ca1cc 0x2de92c6f 0x4a7484aa 0x5cb0a9dc 0x76f988da
0x983e5152 0xa831c66d 0xb00327c8 0xbf597fc7 0xc6e00bf3 0xd5a79147 0x06ca6351 0x14292967
0x27b70a85 0x2e1b2138 0x4d2c6dfc 0x53380d13 0x650a7354 0x766a0abb 0x81c2c92e 0x92722c85
0xa2bfe8a1 0xa81a664b 0xc24b8b70 0xc76c51a3 0xd192e819 0xd6990624 0xf40e3585 0x106aa070
0x19a4c116 0x1e376c08 0x2748774c 0x34b0bcb5 0x391c0cb3 0x4ed8aa4a 0x5b9cca4f 0x682e6ff3
0x748f82ee 0x78a5636f 0x84c87814 0x8cc70208 0x90befffa 0xa4506ceb 0xbef9a3f7 0xc67178f2

Шаг 4. Основной цикл

Следующие шаги будут выполняться для каждого 512-битного «куска» входных данных. Наша тестовая фраза «hello world» довольно короткая, поэтому «кусок» всего один. На каждой итерации цикла мы будем изменять значения хеш-функций h0–h7, чтобы получить окончательный результат.

Шаг 5. Создаём очередь сообщений (w)

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

01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000

2. Добавляем ещё 48 слов, инициализированных нулями, чтобы получить массив w[0…63]:

01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
...
...
00000000000000000000000000000000 00000000000000000000000000000000

3. Изменяем нулевые индексы в конце массива, используя следующий алгоритм:

For i from w[16…63]:
- s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] righthift 3)
- s1 = (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] righthift 10)
- w [i] = w[i-16] + s0 + w[i-7] + s1

Давайте посмотрим, как это работает для w[16]:

w[1] rightrotate 7:
  01101111001000000111011101101111 -> 11011110110111100100000011101110
w[1] rightrotate 18:
  01101111001000000111011101101111 -> 00011101110110111101101111001000
w[1] rightshift 3:
  01101111001000000111011101101111 -> 00001101111001000000111011101101

s0 = 11011110110111100100000011101110 XOR 00011101110110111101101111001000 XOR 00001101111001000000111011101101

s0 = 11001110111000011001010111001011

w[14] rightrotate 17:
  00000000000000000000000000000000 -> 00000000000000000000000000000000
w[14] rightrotate19:
  00000000000000000000000000000000 -> 00000000000000000000000000000000
w[14] rightshift 10:
  00000000000000000000000000000000 -> 00000000000000000000000000000000

s1 = 00000000000000000000000000000000 XOR 00000000000000000000000000000000 XOR 00000000000000000000000000000000

s1 = 00000000000000000000000000000000

w[16] = w[0] + s0 + w[9] + s1

w[16] = 01101000011001010110110001101100 + 11001110111000011001010111001011 + 00000000000000000000000000000000 + 00000000000000000000000000000000

// сложение рассчитывается по модулю 2^32

w[16] = 00110111010001110000001000110111

Это оставляет нам 64 слова в нашей очереди сообщений (w):

01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
00110111010001110000001000110111 10000110110100001100000000110001
11010011101111010001000100001011 01111000001111110100011110000010
00101010100100000111110011101101 01001011001011110111110011001001
00110001111000011001010001011101 10001001001101100100100101100100
01111111011110100000011011011010 11000001011110011010100100111010
10111011111010001111011001010101 00001100000110101110001111100110
10110000111111100000110101111101 01011111011011100101010110010011
00000000100010011001101101010010 00000111111100011100101010010100
00111011010111111110010111010110 01101000011001010110001011100110
11001000010011100000101010011110 00000110101011111001101100100101
10010010111011110110010011010111 01100011111110010101111001011010
11100011000101100110011111010111 10000100001110111101111000010110
11101110111011001010100001011011 10100000010011111111001000100001
11111001000110001010110110111000 00010100101010001001001000011001
00010000100001000101001100011101 01100000100100111110000011001101
10000011000000110101111111101001 11010101101011100111100100111000
00111001001111110000010110101101 11111011010010110001101111101111
11101011011101011111111100101001 01101010001101101001010100110100
00100010111111001001110011011000 10101001011101000000110100101011
01100000110011110011100010000101 11000100101011001001100000111010
00010001010000101111110110101101 10110000101100000001110111011001
10011000111100001100001101101111 01110010000101111011100000011110 
10100010110101000110011110011010 00000001000011111001100101111011
11111100000101110100111100001010 11000010110000101110101100010110

Шаг 6. Цикл сжатия

Инициализируем переменные a, b, c, d, e, f, g, h и установим их равными текущим значениям хеша соответственно. h0, h2, h3, h4, h5, h5, h6, h7.
Запустим цикл сжатия, который будет изменять значения a…h . Цикл выглядит следующим образом:

for i from 0 to 63
- S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
- ch = (e and f) xor ((not e) and g)
- temp1 = h + S1 + ch + k[i] + w[i]
- S0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
- maj = (a and b) xor (a and c) xor (b and c)
- temp2 := S0 + maj
- h = g
- g = f
- f = e
- e = d + temp1
- d = c
- c = b
- b = a
- a = temp1 + temp2

Давайте пройдём первую итерацию.32:

a = 0x6a09e667 = 01101010000010011110011001100111
b = 0xbb67ae85 = 10111011011001111010111010000101
c = 0x3c6ef372 = 00111100011011101111001101110010
d = 0xa54ff53a = 10100101010011111111010100111010
e = 0x510e527f = 01010001000011100101001001111111
f = 0x9b05688c = 10011011000001010110100010001100
g = 0x1f83d9ab = 00011111100000111101100110101011
h = 0x5be0cd19 = 01011011111000001100110100011001

e rightrotate 6:
  01010001000011100101001001111111 -> 11111101010001000011100101001001
e rightrotate 11:
  01010001000011100101001001111111 -> 01001111111010100010000111001010
e rightrotate 25:
  01010001000011100101001001111111 -> 10000111001010010011111110101000
S1 = 11111101010001000011100101001001 XOR 01001111111010100010000111001010 XOR 10000111001010010011111110101000
S1 = 00110101100001110010011100101011

e and f:
    01010001000011100101001001111111
  & 10011011000001010110100010001100 =
    00010001000001000100000000001100
not e:
  01010001000011100101001001111111 -> 10101110111100011010110110000000
(not e) and g:
    10101110111100011010110110000000
  & 00011111100000111101100110101011 =
    00001110100000011000100110000000
ch = (e and f) xor ((not e) and g)
   = 00010001000001000100000000001100 xor 00001110100000011000100110000000
   = 00011111100001011100100110001100

// k[i] is the round constant
// w[i] is the batch
temp1 = h + S1 + ch + k[i] + w[i]
temp1 = 01011011111000001100110100011001 + 00110101100001110010011100101011 + 00011111100001011100100110001100 + 1000010100010100010111110011000 + 01101000011001010110110001101100
temp1 = 01011011110111010101100111010100

a rightrotate 2:
  01101010000010011110011001100111 -> 11011010100000100111100110011001
a rightrotate 13:
  01101010000010011110011001100111 -> 00110011001110110101000001001111
a rightrotate 22:
  01101010000010011110011001100111 -> 00100111100110011001110110101000
S0 = 11011010100000100111100110011001 XOR 00110011001110110101000001001111 XOR 00100111100110011001110110101000
S0 = 11001110001000001011010001111110

a and b:
    01101010000010011110011001100111
  & 10111011011001111010111010000101 =
    00101010000000011010011000000101
a and c:
    01101010000010011110011001100111
  & 00111100011011101111001101110010 =
    00101000000010001110001001100010
b and c:
    10111011011001111010111010000101
  & 00111100011011101111001101110010 =
    00111000011001101010001000000000
maj = (a and b) xor (a and c) xor (b and c)
    = 00101010000000011010011000000101 xor 00101000000010001110001001100010 xor 00111000011001101010001000000000 
    = 00111010011011111110011001100111

temp2 = S0 + maj
      = 11001110001000001011010001111110 + 00111010011011111110011001100111
      = 00001000100100001001101011100101

h = 00011111100000111101100110101011
g = 10011011000001010110100010001100
f = 01010001000011100101001001111111
e = 10100101010011111111010100111010 + 01011011110111010101100111010100
  = 00000001001011010100111100001110
d = 00111100011011101111001101110010
c = 10111011011001111010111010000101
b = 01101010000010011110011001100111
a = 01011011110111010101100111010100 + 00001000100100001001101011100101
  = 01100100011011011111010010111001

Все расчёты выполняются ещё 63 раза, изменяя переменные а…h. В итоге мы должны получить следующее:

h0 = 6A09E667 = 01101010000010011110011001100111
h2 = BB67AE85 = 10111011011001111010111010000101
h3 = 3C6EF372 = 00111100011011101111001101110010
h4 = A54FF53A = 10100101010011111111010100111010
h5 = 510E527F = 01010001000011100101001001111111
h5 = 9B05688C = 10011011000001010110100010001100
h6 = 1F83D9AB = 00011111100000111101100110101011
h7 = 5BE0CD19 = 01011011111000001100110100011001

a = 4F434152 = 001001111010000110100000101010010
b = D7E58F83 = 011010111111001011000111110000011
c = 68BF5F65 = 001101000101111110101111101100101
d = 352DB6C0 = 000110101001011011011011011000000
e = 73769D64 = 001110011011101101001110101100100
f = DF4E1862 = 011011111010011100001100001100010
g = 71051E01 = 001110001000001010001111000000001
h = 870F00D0 = 010000111000011110000000011010000

Шаг 7. Изменяем окончательные значения

После цикла сжатия, но ещё внутри основного цикла, мы модифицируем значения хеша, добавляя к ним соответствующие переменные a…h.32.

h0 = h0 + a = 10111001010011010010011110111001
h2 = h2 + b = 10010011010011010011111000001000
h3 = h3 + c = 10100101001011100101001011010111
h4 = h4 + d = 11011010011111011010101111111010
h5 = h5 + e = 11000100100001001110111111100011
h5 = h5 + f = 01111010010100111000000011101110
h6 = h6 + g = 10010000100010001111011110101100
h7 = h7 + h = 11100010111011111100110111101001

Шаг 8. Получаем финальный хеш

И последний важный шаг — собираем всё вместе.

digest = h0 append h2 append h3 append h4 append h5 append h5 append h6 append h7
       = B94D27B9934D3E08A52E52D7DA7DABFAC484EFE37A5380EE9088F7ACE2EFCDE9

Готово! Мы выполнили каждый шаг SHA-2 (SHA-256) (без некоторых итераций).

Алгоритм SHA-2 в виде псевдокода

Если вы хотите посмотреть на все шаги, которые мы только что сделали, в виде псевдокода, то вот пример:

Пояснения:
 Все переменные беззнаковые, имеют размер 32 бита и при вычислениях суммируются по модулю 232
 message — исходное двоичное сообщение
 m — преобразованное сообщение

Инициализация переменных
 (первые 32 бита дробных частей квадратных корней первых восьми простых чисел [от 2 до 19]):
h0 := 0x6a09e667
h2 := 0xbb67ae85
h3 := 0x3c6ef372
h4 := 0xa54ff53a
h5 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Таблица констант
(первые 32 бита дробных частей кубических корней первых 64 простых чисел [от 2 до 311]):
k[ 0..63 ] :=
   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

Предварительная обработка:
m := message ǁ [единичный бит]
m := m ǁ [k нулевых бит], где k — наименьшее неотрицательное число, такое что 
                 (L + 1 + K) mod 512 = 448, где L — число бит в сообщении (сравнима по модулю 512 c 448)
m := m ǁ Длина(message) — длина исходного сообщения в битах в виде 64-битного числа
            с порядком байтов от старшего к младшему

Далее сообщение обрабатывается последовательными порциями по 512 бит:
разбить сообщение на куски по 512 бит
для каждого куска
    разбить кусок на 16 слов длиной 32 бита (с порядком байтов от старшего к младшему внутри слова): w[ 0..15 ]


    Сгенерировать дополнительные 48 слов:
    для i от 16 до 63
        s0 := (w[i-15] rightrotate  7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift  3)
        s1 := (w[i- 2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
        w[i] := w[i-16] + s0 + w[i-7] + s1

    Инициализация вспомогательных переменных:
    a := h0
    b := h2
    c := h3
    d := h4
    e := h5
    f := h5
    g := h6
    h := h7

    Основной цикл:
    для i от 0 до 63
        S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
        ch := (e and f) xor ((not e) and g)
        temp1 := h + S1 + ch + k[i] + w[i]
        S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
        maj := (a and b) xor (a and c) xor (b and c)
        temp2 := S0 + maj
 
        h := g
        g := f
        f := e
        e := d + temp1
        d := c
        c := b
        b := a
        a := temp1 + temp2

    Добавить полученные значения к ранее вычисленному результату:
    h0 := h0 + a
    h2 := h2 + b
    h3 := h3 + c
    h4 := h4 + d
    h5 := h5 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h

Получить итоговое значение хеша SHA-2:
digest := hash := h0 append h2 append h3 append h4 append h5 append h5 append h6 append h7

Перевод статьи «How SHA-2 Works Step-By-Step (SHA-256)»

Алгоритмы хеширования — простое объяснение сложного | by GT Blockchain Investments | GT Blockchain Investments

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

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

Даже изменение одного символа во входных данных приведет к совершенно другому хэшу.

Криптографические хэши используются везде, от хранения паролей до систем проверки файлов. Основная идея состоит в том, чтобы использовать детерминированный алгоритм (алгоритмический процесс, который выдает уникальный и предопределенный результат для задачи входных данных), который принимает один вход и создает строку фиксированной длины каждый раз. То есть, использование одного и того же ввода всегда приводит к одному и тому же результату. Детерминизм важен не только для хэшей, но и для одного бита, который изменяется во входных данных, создавая совершенно другой хэш. Проблема с алгоритмами хэширования — неизбежность коллизий. То есть, тот факт, что хэши являются строкой фиксированной длины, означает, что для каждого ввода, который мы можем себе представить, есть другие возможные входы, которые приведут к тому же хэшу. Коллизия — это плохо. Это означает, что, если злоумышленник может создавать коллизии, он может передавать вредоносные файлы или данные, как имеющие правильный и неправильный хэш и скрываться под правильным хешем. Цель хорошей хэш-функции состоит в том, чтобы сделать чрезвычайно сложным для злоумышленников найти способы генерации входных данных, которые хешируются с одинаковым значением. Вычисление хэша не должно быть слишком простым, так как это облегчает злоумышленникам искусственное вычисление коллизий. Алгоритмы хэширования должны быть устойчивы к «атакам нахождения прообраза». То есть, получая хеш, было бы чрезвычайно сложно вычислить обратные детерминированные шаги, предпринятые для воспроизведения значения, которое создало хэш (т.е нахождение прообраза).

Учитывая S = hash (x), найти X должно быть почти невозможно.

Напомним, что «хорошие» алгоритмы хэширования имеют следующие свойства:

Изменение одного бита во входных данных должно создать эффект изменения всего хеша;
Вычисления хеша не должно быть слишком простым, высокая сложность нахождения прообраза;
Должен иметь очень низкую вероятность коллизии;

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

Что такое «Атака дня рождения?»

Вы когда-нибудь слышали о том, что если вы поместите 23 человека в комнату, есть 50% шанс, что у двух из них будет один и тот же день рождения? Доведение числа до 70 человек в комнате дает вам 99,9% шанс. Если голуби рассажены в коробки, причем число голубей больше числа коробок, то хотя бы в одной из клеток находится более одного голубя. То есть фиксированные ограничения на выход означают, что существует фиксированная степень перестановок, на которых можно найти коллизию

По крайне мере, один отсек будет иметь внутри 2-ух голубей.

На самом деле MD5 настолько слаб к сопротивлению к коллизиям, что простой бытовой Процессор Pentium 2,4 ГГц может вычислить искусственные хэш-коллизии в течение нескольких секунд. Кроме того, его широкое использование в более ранние дни текущей сети создало тонны утечек MD5 предварительных прообразов в интернете, которые можно найти с помощью простого поиска Google их хэша.

Различия и развитие алгоритмов хеширования Начало: SHA1 и SHA2

NSA (Агентство национальной безопасности) уже давно является пионером стандартов алгоритмов хэширования, с их первоначальным предложением алгоритма Secure Hashing Algorithm или SHA1, создающий 160-битные выходы фиксированной длины. К сожалению, SHA1 просто улучшил MD5, увеличив длину вывода, количество однонаправленных операций и сложность этих односторонних операций, но не дает каких-либо фундаментальных улучшений против более мощных машин, пытающихся использовать различные атаки. Так как мы можем сделать что-то лучше?

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

В 2006 году Национальный институт стандартов и технологий (NIST) запустил конкурс, чтобы найти альтернативу SHA2, которая будет принципиально отличаться в своей архитектуре, чтобы стать стандартом. Таким образом, SHA3 появился как часть большой схемы алгоритмов хэширования, известной как KECCAK (произносится Кетч-Ак). Несмотря на название, SHA3 сильно отличается своим внутренним механизмом, известным как «конструкция губки», которая использует случайные перестановки для «Впитывания» и «Выжимания» данных, работая в качестве источника случайности для будущих входов, которые входят в алгоритм хэширования.

Хеширование и proof-of-work

Когда дело дошло до интеграции алгоритма хеширования в блокчейн протоколы, биткоин использовал SHA256, в то время как Ethereum использовал модифицированный SHA3 (KECCAK256) для своего PoW. Однако важным качеством выбора хэш-функции для блокчейна с использованием доказательства работы является эффективность вычислений указанного хэша. Алгоритм хеширования биткойна SHA256 может быть вычислен достаточно просто с помощью специализированного оборудования, известного как специализированные интегральные схемы (или ASIC). Много было написано об использовании ASIC в майнинг пуле и о том, как они делают протокол направленным на централизацию вычислений. То есть доказательство работы стимулирует группы вычислительно эффективных машин объединяться в пулы и увеличивать то, что мы обозначаем “хэш-мощностью”, или мерой количества хэшей, которые машина может вычислить за интервал времени. Ethereum, выбрал модифицированный SHA3 известный как KECCAK 256. Кроме того, алгоритм PoW в Ethereum — Dagger-Hashimoto, должен был быть трудно вычисляемым для аппаратного обеспечения.

Почему биткоин использует двойное шифрование SHA256?

Биткойн имеет интересный способ хэширования данных с помощью SHA256, поскольку он выполняет две итерации алгоритма в своем протоколе. Обратите внимание: это не контрмера для атак на день рождения, так как ясно, что если hash (x) = hash (y), то hash (hash (x)) = hash (hash (y)). Вместо этого двойной SHA256 используется для смягчения «Атаки удлинения сообщения — тип атаки на хэш-функцию, заключающейся в добавлении новой информации в конец исходного сообщения». Атака опасна тем, что можно поменять запрос, а соответственно выполнить то, за что этот запрос отвечает (например, перевод денег)

Ethereum 2.0 и BLAKE

SHA3 не был единственным прорывом, который вышел из конкурса хеширования NIST в 2006 году. Несмотря на то, что SHA3 выиграл, алгоритм, известный как BLAKE, занял второе место. Для реализации шардинга Ethereum 2.0 использует более эффективное. Алгоритм хэширования BLAKE2b, который является высокоразвитой версией BLAKE от конкурентов, интенсивно изучается за его фантастическую эффективность по сравнению с KECCAK256 при сохранении высокой степени безопасности. Вычисление BLAKE2b фактически в 3 раза быстрее, чем KECCAK на современном процессоре.

Будущее алгоритмов хэширования

Кажется, что независимо от того, что мы делаем, мы просто либо (1) увеличиваем сложность внутренних хеш-операций, либо (2) увеличиваем длину хеш-выхода, надеясь, что компьютеры атакующих не будут достаточно быстрыми, чтобы эффективно вычислять ее коллизию. Мы полагаемся на двусмысленность предварительных прообразов односторонних операций для обеспечения безопасности наших сетей. То есть цель безопасности алгоритма хеширования состоит в том, чтобы сделать как можно более сложным для любого, кто пытается найти два значения, которые хешируются на один и тот же вывод, несмотря на то, что существует бесконечное количество возможных столкновений. «Как насчет будущего квантовых компьютеров? Будут ли алгоритмы хэширования безопасными?» Короткий ответ и текущее понимание заключаются в том, что да, алгоритмы хэширования выдержат испытание временем против квантовых вычислений. То, что квантовые вычисления смогут сломать, — это те проблемы, которые имеют строгую математическую структуру, основанную на аккуратных трюках и теории, такой как шифрование RSA. С другой стороны, алгоритмы хэширования имеют менее формальную структуру во внутренних конструкциях. Квантовые компьютеры действительно дают повышенную скорость в вычислении неструктурированных проблем, таких как хэширование, но в конце концов, они все равно будут грубо атаковать так же, как компьютер сегодня попытается это сделать. Независимо от того, какие алгоритмы мы выбираем для наших протоколов, ясно, что мы движемся к вычислительно-эффективному будущему, и мы должны использовать наше лучшее суждение, чтобы выбрать правильные инструменты для работы и те, которые, мы надеемся, выдержат испытание временем.

Алгоритмы хэширования. Инфраструктуры открытых ключей

Шифрование и хеширование

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

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

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

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

Очевидно, что сравнивать можно не только пароли, а любые данные переданные на вход.

Наиболее распространенная функция хеширования, известна всем программистам — это MD5. Данный алгоритм производит 16-битное значение хэша, обычно выражаемое 32-х значным шестнадцатеричным числом.

Более сложные, но не менее распространенные алгоритмы хеширования, это серия SHA. Из этой серии нам наиболее интересен SHA-256, он производит 32-х битные значени хеша.

Именно на этом алгоритме хеширования построен классический биткоин. Стоит отметить, что алгоритм был разработан в США в Агентстве Национальной Безопасности (АНБ).

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

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

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

У шифрования на основе открытых ключей есть два ключа — открытый и закрытый. Открытый ключ шифрует данные, закрытый — расшифровывает их.

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

Алгоритм шифрования AES явлется стандартом, когда речь заходит о способе симметричного шифрования и рекомендуется для большинства случаев (шифруется 256 битным размером ключа). PGP — наиболее популярный алгоритм шифрования на основе открытых ключей. Однако в биткоине ипользуется алгоритм шифрования на основе открытых ключей — ECDSA.

Практическое применение. В каждой криптовалюте используется свой определенный алгоритм шифрования (хеширования). Некоторые криптовалюты могут поддерживать несколько протоколов сразу. Эти параметры учитывается при разработке и настройке ПО для майнингового оборудования.

Чтобы программа для майнинга работала корректно с конкретной криптовалютой, она должна иметь поддержку заданного алгоритма.

В описании к ПО алгоритмы шифрования (хеширования) могут иметь различные названия, типа как: «алгоритм», «алгоритм майнинга», «алгоритм шифрования», «алгоритм хеширования», «протокол» и т. п.

Примеры криптовалют и их алгоритмы

Название	Тикер	Алгоритм и особенности
Bitcoin	BTC	SHA-256 Позволяет использовать специализированное оборудование (асики), что приводит к резкому увеличению сложности и уменьшению децентрализации.
Bitcoin Cash	BCH
Litecoin	LTC	Scrypt В отличии от SHA-256 эффективнее использует ресурсы компьютера (в частности память), однако этот алгоритм также можно использовать на асиках (Scrypt-ASIC)
Dash	DASH	X11 (X13, X15) Цифра в названии говорит о количестве ступеней хеширования с различными хэш-функциями. Это повышает надежность и анонимность криптовалюты.
Ethereum	ETH	Ethash (старое название Dagger Hashimoto) Этот алгоритм использует альтернативные версии алгоритмов SHA3-256 и SHA3-512. Благодаря этому майнинг «эфира» происходит гораздо быстрее и дешевле, чем биткойна.
Ethereum Classic	ETC
Monero	XMR	CryptoNight Протокол CryptoNote работает на основе кольцевых подписей. При передаче Monero происходит перемешивание транзакций, что обеспечивает высокую анонимность.
Bitcore	BTX	Timetravel 10 Bitcore является гибридным форком bitcoin, сочетает в себе всю криптографическую технологию Bitcoin, но при этом использует новую цепь блоков и алгоритм timetravel10, устойчивый к асикам, но позволяющий майнить на видеокартах
SIBCoin	SIB	X11Gost (X11ГОСТ) Алгоритм хеширования: X11Gost, внутри цепочки X11 добавлена отечественная, утвержденная ФСБ в качестве отечественного стандарта, хеш функция «Стрибог» (ГОСТ Р 34.11-2012).
Zcash	ZEC	Equihash Equihash базируется криптографической концепции, которая носит название «Обобщенная проблема дня рождения». Устайчив к майнингу на асиках (ASIC)

Выбор безопасного размера ключа и алгоритмов хэширования

Алгоритмы, размер ключа и цифровые сертификаты

Резюме

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

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

Как обычно и бывает, если копнуть поглубже, то все оказывается немного более сложным. В случае цифровых сертификатов действует и ряд других факторов. Например, какова квалификация третьей стороны, их методы работы, криптографические алгоритмы, использованные для формирования цифрового сертификата?

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

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

История

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

Устойчивость и эффективность работы алгоритма RSA зависит от размера ключа, чем больше ключ тем устойчивее и медленнее шифрование. Прогресс в области криптоанализа привел к увеличению размера ключей, используемых с алгоритмом, что повысило требования к вычислительным мощностям, нужных для поддержания достаточной устойчивости алгоритма. Проблема заключается в том, что при каждом удвоении размера RSA-ключа, время затрачиваемое на дешифровку ключа увеличивается в 6-7 раз.

Поэтому в январе 2011 года доверенные центры авторизации решили принять в работу рекомендации NIST (Национального института стандартов и технологий) и обеспечивать все новые RSA-сертификаты ключами с длиной не менее 2048 бит. В 1998 году компания GlobalSign одной из первых в качестве центра авторизации реализовала ключи с размером 2048 бит в своих цифровых сертификатах, с тех пор центры сертификации стремились следовать этим рекомендациям.

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

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

Будущее

За последнее десятилетие медленно но верно в обиход входят два новых алгоритма SHA-2 и ECC. Алгоритм ECC обладает большей эффективностью чем RSA при сохранении того же уровня устойчивости. SHA-2 имеет 3 версии, в каждой из которых последовательно реализуются все большие длины ключей, что позволяет устранить текущие риски и обеспечивает достаточно длительный период времени, в который можно безопасно использовать данный алгоритм.

Хотя Форум CA/B еще не включил алгоритм SHA-256 в список базовых требований, Microsoft и Google установили для отрасли ключевую дату (январь 2017 года), после которой они перестанут доверять сертификатам SHA-1, выданным от общественных корневых сертификатов. GlobalSign отслеживает текущую ситуацию в области центров сертификации и браузеров, а также форумы по безопасности, и уже выполняет ряд активных шагов для того, чтобы начать поддержку сертификатов SSL SHA-256 с марта 2014 года.

Что следует учитывать

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

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

Сторонние поставщики, использующие алгоритмы SHA2 и RSA 2048-бит, будут обеспечивать безопасные решения как минимум ближайшие десять лет. Что важно учитывать при выборе поставщика, так это время, когда поставщик стал использовать подобные стандарты в своей работе. В компании GlobalSign данный стандарт безопасности использовался за 10 лет до выхода в свет рекомендаций NIST, что позволяло компании быть на острие прогресса.

Хеш четкий и хеш нечеткий. Как средства защиты ловят и классифицируют малварь

Содержание статьи

Создатели вредоносных программ используют массу разных методов, чтобы скрыть свои творения от антивирусных средств и статических-динамических анализаторов. Однако и антивирусы не лыком шиты: для поиска «родственных» семплов они используют продвинутые алгоритмы хеширования. Сегодня мы расскажем, как работают эти алгоритмы, — с подробностями и наглядными примерами.

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

Этот повторно используемый код может быть собран заново с помощью другого компилятора, из него могут быть удалены или, наоборот, в него могут быть добавлены новые функции. Обновляются некоторые библиотеки, меняется распределение кода внутри файла (при этом применяются новые компоновщики, пакеры, обфускация и так далее). Смысл таких преобразований — придать хорошо знакомой антивирусу вредоносной программе новый вид. В этом случае видоизмененная версия вируса какое-то время останется необнаруженной. Тем не менее существуют способы детектирования такого рода переупаковок и модификаций.

Эти техники обнаружения зачастую используются для анализа большого массива данных и поиска в нем общих элементов. Практическими примерами использования похожих техник могут быть глобально распределенные базы знаний, такие как Virus Total и базы антивирусных компаний, а также подходы Threat Intelligence.

Хеш «четкий»

Ханс Петер Лун из IBM еще в 1940-е разрабатывал системы для анализа информации, в том числе исследовал вопросы хранения, передачи и поиска текстовых данных. Это привело его к созданию алгоритмов преобразования, а затем и к хешированию информации в качестве способа поиска телефонных номеров и текста. Так индексация и концепция «разделяй и властвуй» сделали свои первые шаги в области вычислительной техники.

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

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

аутентификация;
электронная подпись;
обнаружение вредоносного ПО (как файлов, так и их маркеров компрометации).

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

Что такое хеш

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

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

MD5, SHA-1 и SHA-256 — наиболее популярные криптографические алгоритмы вычисления хеша, которые часто используются в детектировании вредоносного ПО. Еще совсем недавно вредонос опознавали только по сигнатуре (хешу) исполняемого файла.

Но в современных реалиях недостаточно знать просто хеш объекта, так как это слабый индикатор компрометации (IoC). IoC — это все артефакты, на основе которых может быть выявлен вредонос. Например, используемые им ветки реестра, подгружаемые библиотеки, IP-адреса, байтовые последовательности, версии ПО, триггеры даты и времени, задействованные порты, URL.

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

«Пирамида боли» Дэвида Бьянко

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

Как же определить схожесть между разными образцами малвари одного семейства?

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

«Нечеткий» хеш — SSDeep

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

Нечеткое хеширование — это метод, при котором программа, такая как, например, SSDeep, вычисляет кусочные хеши от входных данных, то есть использует так называемое контекстно вызываемое кусочное хеширование. В англоязычных источниках этот метод называется context triggered piecewise hashing (CTPH aka fuzzy hashing).

На самом деле классификаций нечетких хешей довольно много. Например, по механизму работы алгоритмы делятся на piecewise hashing, context triggered piecewise hashing, statistically improbable features, block-based rebuilding. По типу обрабатываемой информации их можно разделить на побайтовые, синтаксические и семантические. Но если речь заходит о нечетких хешах, то это, как правило, CTPH.

Алгоритм SSDeep разработан Джесси Корнблюмом для использования в компьютерной криминалистике и основан на алгоритме spamsum. SSDeep вычисляет несколько традиционных криптографических хешей фиксированного размера для отдельных сегментов файла и тем самым позволяет обнаруживать похожие объекты. В алгоритме SSDeep используется механизм скользящего окна rolling hash. Его еще можно назвать рекурсивным кусочным хешированием.

Часто CTPH-подобные хеши лежат в основе алгоритмов локально чувствительных хешей — locality-sensitive hashing (LSH). В их задачи входит поиск ближайших соседей — approximate nearest neighbor (ANN), или, проще говоря, похожих объектов, но с чуть более высокоуровневой абстракцией. Алгоритмы LSH используются не только в борьбе с вредоносным ПО, но и в мультимедиа, при поиске дубликатов, поиске схожих генов в биологии и много где еще.

Алгоритм SSDeep

Как работает SSDeep? На первый взгляд, все довольно просто:

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

Virus Total использует SSDeep, который выполняет нечеткое хеширование на загружаемых пользователями файлах. Пример — по ссылке.

Virus Total использует SSDeep

Итак, рубрика э-э-эксперименты! Возьмем по 18 образцов исполняемых файлов нашумевших вирусяк: среди них — MassLogger (имена образцов будут начинаться с аббревиатуры ML), Agent Tesla (AT) и Emotet (EMO). Только вот где мы найдем такое количество малвари? Да на базаре.

Теперь давай посмотрим, что же мы загрузили для испытаний. Agent Tesla — это .NET-кейлоггер и RAT, подробнее о нем рассказано вот в этой статье. Emotet — банковский троян с возможностью червеобразного распространения. При запуске сразу определяет, что работает не в виртуалке, иначе завершается. MassLogger, как и Agent Tesla, представляет собой кейлоггер. При этом он входит в топ-5 по популярности лета и осени 2020 года. Они оба используют механизм доставки вредоносных программ GuLoader, который загружает зашифрованную полезную нагрузку, лежащую на обычных платформах для обмена файлами.

Мы будем работать с .EXE-семплами, у каждого из испытуемых объектов уникальная криптографическая хеш-сумма SHA-1. Перечислим их все (команда для любителей Linux: shasum ML):

f59a138da63769720e61e37fe52030774472db19 ML1.exe bd57fd4002228352bf60186562d0dde87f4f33e5 ML2.exe 89ebb9ff3ab6c9a3330e798036bb81cec29c417f ML3.exe e9029f66cc313a41b22cb922da7f52a899ac166c ML4.exe 1dde9710a0d780b42678f41bbc949c82f13a74af ML5.exe 8c635bc0aaf4214024cf7342d5f186ebf6171652 ML6.exe 3cb9d16fa0bf3d72f12bf844e0a293d818512c54 ML7.exe 619480abce06d5221c1dd430233fa19ff7f863b5 ML8.exe ab1aed403d37d2f90f2a59505b0724927790841e ML9.exe 65e9d26cf5e6742bdf0a772f6c9692ec533aded7 ML10.exe 3e5b239ddab79130b5b8ffe623c6272d365774d8 ML11.exe c53e68fe71b695e2c7fb6c05aedb422bf5856f7b ML12.exe 6c610f5675f7fb4d78ca2b6e4be9ff43ba47c929 ML13.exe 10cf5e8f60ddac43813e5b8880aa84805e4a30d8 ML14.exe d7a1665e425fe63054c5c836b3807f58da43948a ML15.exe 98e0a38ab5db61a6eb7b50f4e09556af7f46978d ML16.exe 2c2010e2fa02f4c70ea9dd5083026d0138f655d5 ML17.exe 67ee652bc805fc8f5c9c653785b4d82baae0f78e ML18.exe

С использованием SSDeep рассчитаем кусочный хеш каждого из файлов и сохраним результат в файле командой ssdeep MassLogger/* > ML.ssd. На выходе получим следующее:

ssdeep,1.1—blocksize:hash:hash,filename

24576: uf+B91xtspzq6wqAkSq+EQsnn3OF7dAhaG0K uUKp15AkSTsn3BH0K ML1.exe 24576: DoYHyzf8WEE0us0U5xDO/qLaVGbwfyXQHHNG ECcFEE0Px2qLaVuwagA ML2.exe 12288: OnaPI5TFAYwISkHXqrzcTo4BRzsWnLu8nbFNgreeWhBdgkuAgb6DxlPH9p+iq3T4 OnaQvwImc04Hdu8n5NgjMd26D3+lwt ML3.exe 12288: lDi43RqqJKN07vvaRfdjSGM/lBp62o53T7Q+Xu9BwckDj9F2Tzhs0kf3PYeD0d8t l2UTYy7vQaDiTXuvRMxF2xr6QeIdOV ML4.exe 24576: tGDh2aKoqw13WhVUSQK3+dUrSU4O5kddtp+Gyce 4Dx8h0USQKudUry0ite ML5.exe 12288: bOr02ehwuCC3t9DDnHSHoCdK5fskDfccfUt0IY81e0cXNi/Zb0kk1uuCucUXnwHY 6A2nuhe1dGPD06y0KbT/L8pnuusZdBE ML6.exe 24576: uA2nuhe1dGPD06y/C0UfDcBbcIt/nTh/WeFcLQ7 uvu8d8Aq+BR18eMQ7 ML7.exe 24576: 7Lo4IwxEo1796aAkBWvn7kGg9b5rrd9S/9+ 4nzamn7Hg9bJd92 ML8.exe 24576: NGDh2aKoqw13WhVUSM6j3xwra6hPG2VM+sJRcFpoprV89 YDx8h0USMU3xwO6NTsJymG ML9.exe 24576: KA2nuhe1dGPD06yxaG2acKrXOfIWkV353 Kvu8d8AqlhkV53 ML10.exe 24576: NGDh2aKoqw13WhVUS27LIQ/34mXyx7pxrkkQiD YDx8h0US273f4mXyBpxrkkQiD ML11.exe 24576: 2MOfNQm+7K/rTpVF2RiMKt34x/rrMt2I132fq 5uGKDrF2RiMW34/nf ML12.exe 24576: aA2nuhe1dGPD06yMSW+M8OxwhFTTLMyQkxN avu8d8AMS9MLwffMGxN ML13.exe 24576: dGDh2aKoqw13WhVUSDukbAEXF5Ujj1J21g IDx8h0USKkESqj1L ML14.exe 24576: CA2nuhe1dGPD06yg199oT5gzUmRVUhxfNw Cvu8d8Ag19q+Um0hxNw ML15.exe 12288: m5EaSrUQ9JakMtlDQ8zJQAqpLMyp84JiIQbTVru1YS+Fi75McDxH01YJf mGaSrUipM88zJ8My8IGTdSAil7tJ ML16.exe 24576: OD7tjHvlHj0eU30aD5Q6/0FW//V17rmBlKLsNTy4z OntjPlY3xluFw/V9rmOLsZR ML17.exe 12288: zOr02ehwuCC3t9DDnHSHoCdK5fskDfccfUtlLAQ8H5AbDarsd9Qg9Iu13SOMirut SA2nuhe1dGPD06ylLAQjbj9IyMira ML18.exe

Выглядит пугающе, правда? Давай сравним объекты между собой (в выводе мы предварительно удалили дубли, оставив уникальные совпадения между семплами). Для этого используем следующую команду:

ssdeep -m ML.ssd -s MassLogger/* > ML_COMPARE.txt

В выводе команды правый столбец — процент совпадения между семплами.

| ML10.exe matches ML.ssd:ML13.exe | (49) | | ML10.exe matches ML.ssd:ML15.exe | (49) | | ML10.exe matches ML.ssd:ML18.exe | (49) | | ML10.exe matches ML.ssd:ML6.exe | (47) | | ML10.exe matches ML.ssd:ML7.exe | (49) | | ML11.exe matches ML.ssd:ML14.exe | (49) | | ML11.exe matches ML.ssd:ML5.exe | (54) | | ML11.exe matches ML.ssd:ML9.exe | (52) | | ML13.exe matches ML.ssd:ML15.exe | (50) | | ML13.exe matches ML.ssd:ML18.exe | (50) | | ML13.exe matches ML.ssd:ML6.exe | (50) | | ML13.exe matches ML.ssd:ML7.exe | (50) | | ML14.exe matches ML.ssd:ML5.exe | (47) | | ML14.exe matches ML.ssd:ML9.exe | (47) | | ML15.exe matches ML.ssd:ML18.exe | (49) | | ML15.exe matches ML.ssd:ML6.exe | (47) | | ML15.exe matches ML.ssd:ML7.exe | (46) | | ML18.exe matches ML.ssd:ML6.exe | (60) | | ML18.exe matches ML.ssd:ML7.exe | (49) | | ML5.exe matches ML.ssd:ML9.exe | (49) | | ML6.exe matches ML.ssd:ML7.exe | (55) |

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

Связи исследуемых семплов

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

Сразу изобразим граф связности для образцов Agent Tesla. Не будем перечислять хеш-суммы образцов, а сразу приступим к сравнению: сначала файлов между собой, затем с семплами MassLogger.

Граф связности для образцов Agent Tesla

Для Agent Tesla также обнаружено два семейства взаимосвязанных семплов и десять воинов-одиночек. Что дальше? Сравним SSDeep-хеши MassLogger с объектами Emotet. Пусто, нет совпадений. А если с Agent Tesla? Строим граф.

Сравнение MassLogger с Agent Tesla

Бинго! Совпадения есть, и взаимопроникновение фрагментов кода семейств Agent Tesla и MassLogger доказано.

Однако не всегда у исследователя достаточно семплов и образцов вредоносов других семейств — например, для семейства Emotet. На графе видно, что из всех 18 объектов 13 так или иначе связаны между собой, а семплы EMO3, EMO9, EMO11, EMO15 и EMO18 не нашли «друзей», и их мы отражать на рисунке не станем.

Взаимосвязи объектов на графе

Итак, что же в итоге у нас получилось? У групп MassLogger есть пять объектов, связанных с объектами Agent Tesla. Почему так вышло? Во-первых, это два кейлоггера, у них есть пересечения в функциональности. Во-вторых, они оба используют один и тот же загрузчик. В каждом из тестов находились связи (то есть сходства) между объектами более чем на 50%. Иными словами, из 18 образцов так или иначе были связаны между собой как минимум девять. Среди семплов нашлись по меньшей мере две группы связанных объектов, а у Emotet — сразу три группы. Теперь давай рассмотрим другой тип хеш-функций, и, возможно, мы найдем новые взаимосвязи.

Хеш импортируемых библиотек — imphash

Imphash расшифровывается как import hash — «хеш импортов», то есть всех импортируемых программой библиотек, прописанных в исполняемом файле Windows Portable Executable (PE). Чтобы вычислить imphash, все импортированные библиотеки и связанные с ними функции выгружаются в строковом формате, объединяются, а затем криптографически хешируются. Virus Total также высчитывает по этому алгоритму хеш для PE-файлов.

Virus Total также использует imphash

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

Перейдем к практике и найдем взаимосвязи среди наших исследуемых групп объектов. Начнем с MassLogger. Появились ли новые связи? Да, мы получили три группы связанных объектов — их imphash идентичны!

Три новые группы связанных объектов с общими imphash

Изобразим общие imphash файлов в виде графа. Тут со всеми объектами получается полносвязный граф, так что не суди строго, если какого-то ребра графа не будет! 🙂

Общие imphash файлов

Сравним с предыдущим графом из секции экспериментов с SSDeep.

Сравнение графов

Теперь объединим два получившихся графа в группы по их вершинам.

Объединим оба графа

Получается, что среди 18 образцов MassLogger не нашли себе «друзей» всего три объекта: ML1, ML2 и ML4, а это всего 17% от общего количества. Таким образом, используя две техники, мы выявили и подтвердили взаимосвязи вредоносных семплов и их «группировки».

Далее разберем остальные семейства вредоносных файлов. Agent Tesla по imphash разделился на две большие группы.

Деление Agent Tesla по imphash

Сравним с предыдущим графом из секции тестов с SSDeep.

Сравнение графа с предыдущим

Объединим два получившихся графа в группы по их вершинам.

Объединяем два графа в группы по их вершинам

Imphash дополнил связи, которые были выявлены на этапе тестирования с SSDeep, и продемонстрировал более целостную картину. Идентичный с левой группой imphash присутствует в образцах группы MassLogger — ML5, ML9, ML11 и ML14.

Далее рассмотрим группу малвари Emotet.

Группа Emotet

Сравни с предыдущим графом из секции тестов с SSDeep. Напомним, что семплы EMO3, EMO9, EMO11, EMO15 и EMO18 не нашли себе «друзей» в прошлом тесте.

Объединим два получившихся графа в группы по их вершинам.

Сравним графы, объединив их по вершинам

Опа! Недаром червь Emotet получил такое распространение. В наш тест попали довольно хитрые образцы, у которых, судя по всему, в явном виде не присутствует таблица импортов, а следовательно, отсутствует imphash. Скорее всего, в них используется одна из техник, которые мы перечисляли в разделе об этом типе хеширования.

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

Алгоритм хеширования

— обзор

Работа с алгоритмами хеширования

0 9000 Информация утечка, повреждение данных, атаки типа «злоумышленник в середине», атаки методом перебора

Резюме:	Алгоритмы хеширования — это односторонние функции, используемые для проверки целостности данных
Угрозы:

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

▪: Они принимают входные данные любой длины и производят выходные данные фиксированной длины.
▪: Они должны быть эффективными и быстрыми для вычислений.
▪: Их невозможно инвертировать с вычислительной точки зрения.
▪: Они не должны допускать столкновений.

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

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

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

.NET Framework поддерживает алгоритмы хеширования, показанные в таблице 4.3.

Таблица 4.3. Алгоритмы хеширования, доступные в .NET Framework

Имя	Класс	Длина хэша
MD5	MD5CryptoServiceProvider	128 бит
SHA-12910A SHA-12910	160 бит
SHA-256	SHA256 Управляемый	256 бит
SHA-384	SHA384 Управляемый	384 бит	0
SHA-512 512 бит

Алгоритм MD5, определенный в RFC 1321, вероятно, является наиболее известной и широко используемой хеш-функцией.Это самый быстрый из всех алгоритмов хеширования .NET, но он использует меньшее 128-битное хеш-значение, что делает его наиболее уязвимым для атак в долгосрочной перспективе. Было показано, что MD5 имеет некоторые частичные коллизии и вряд ли сможет противостоять будущим атакам по мере увеличения возможностей оборудования. Тем не менее, на данный момент это наиболее часто используемый алгоритм хеширования.

SHA — это алгоритм, разработанный Агентством национальной безопасности (NSA) и опубликованный NIST как FIPS PUB 180. Разработанный для использования со стандартом цифровой подписи (DSS), SHA выдает 160-битное хеш-значение.

Исходная спецификация SHA, опубликованная в 1993 году, была вскоре отозвана АНБ и заменена пересмотренной версией FIPS PUB 180-1, обычно называемой SHA-1. АНБ отозвало исходную спецификацию, чтобы исправить ошибку в исходной. алгоритм, снижающий его криптографическую безопасность. Однако АНБ никогда не сообщало подробностей об этой уязвимости, что побудило исследователей внимательно изучить оба алгоритма. Из-за такого тщательного изучения SHA-1 считается достаточно безопасным.

NIST с тех пор опубликовал три варианта SHA-1, которые производят более крупные хэши: SHA-256, SHA-384 и SHA-512. Хотя при больших размерах хэша эти алгоритмы должны быть более безопасными, они не подвергались такому анализу, как SHA-1. Тем не менее, длина хеш-кода важна для защиты от перебора и атак по случаю дня рождения.

Взлом кода…

Об атаках на день рождения

Атаки на день рождения основаны на уникальной проблеме с алгоритмами хеширования, основанными на концепции, называемой парадоксом дня рождения.Эта головоломка основана на том факте, что в комнате из 183 человек вероятность того, что кто-то из них разделит ваш день рождения, составляет 50 процентов. Однако, если вы хотите с 50-процентной вероятностью найти двух людей, у которых совпадают дни рождения, вам, на удивление, понадобится всего 23 человека в комнате. Для хеш-функций это означает, что намного легче найти любые два совпадения, если вам все равно, какие они есть. Можно предварительно вычислить хэши для заданной длины пароля, чтобы определить, возникают ли какие-либо конфликты.

Проверка целостности

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

TIP

Для проверки целостности загружаемых файлов многие веб-сайты предоставляют сумму MD5, а также подпись суммы PGP. Сумма MD5 проверяет целостность, а подпись PGP подтверждает подлинность суммы MD5.

Хэши полезны, если вы сохраняете их конфиденциальность для проверки данных, например файлов cookie. Например, предположим, что вы записываете файл cookie в браузер клиента и сохраняете хэш этого файла cookie в своей базе данных. Когда клиент возвращает этот файл cookie позже, вы можете вычислить хэш и сравнить его с хешем, хранящимся в базе данных, чтобы убедиться, что он не изменился.Поскольку ASP.NET хранит токены сеанса и проверки подлинности полностью в файле cookie, а не на сервере, он вычисляет хэш данных cookie и шифрует как данные, так и хеш. Этот зашифрованный результат кодируется и сохраняется в файле cookie на стороне клиента. Когда клиент возвращает данные cookie, сервер расшифровывает строку и проверяет хэш. Таким образом, ASP.NET защищает хэш и конфиденциальность данных.

Еще один способ сделать хэши более безопасными — использовать алгоритм хеширования с ключом .Хэши с ключами похожи на обычные хеши, за исключением того, что они основаны на секретном ключе. Чтобы проверить хеш или создать поддельный хеш, вам необходимо знать этот ключ. .NET Framework предоставляет два алгоритма хеширования с ключом:

▪: HMACSHA1 Эта функция создает код аутентификации сообщения на основе хэша на основе алгоритма хеширования SHA-1. HMACSHA1 объединяет исходное сообщение и секретный ключ и использует SHA-1 для создания хэша. Затем он снова объединяет этот хеш с секретным ключом и создает второй хеш SHA-1.Как и SHA-1, алгоритм HMACSHA1 создает 160-битный хэш.
▪: MACTripleDES Этот алгоритм использует TripleDES для шифрования сообщения, отбрасывая все, кроме последних 64 бит зашифрованного текста.

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

Рисунок 4.17. Ключевое хеширование с использованием HMACSHA1: C #

Рисунок 4.18. Ключевое хеширование с использованием HMACSHA1: VB.NET

Хеширование паролей

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

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

Другая проблема с хешами заключается в том, что одни и те же данные всегда будут давать один и тот же хеш. Это может стать проблемой, если кто-то когда-либо получит хэши, потому что он может использовать предварительно вычисленный словарь хэшей для мгновенного обнаружения общих паролей. Чтобы предотвратить эту ситуацию, мы можем добавить к паролю соль, чтобы каждый раз обеспечивать новый хэш. Соль должно быть большим случайным числом, уникально сгенерированным для этой цели.Вам не нужно хранить соль в секрете, поэтому вы можете сохранить соль вместе с самим хешем.

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

Рисунок 4.19. Хеширование с использованием соли: C #

Рисунок 4.20. Хеширование с использованием соли: VB.NET

Вы могли подумать, что соль похожа на IV. Фактически, это, по сути, тот же метод, который служит той же цели. Обратите внимание, что по функциям он аналогичен алгоритму хеширования с ключом, а функция с ключом, такая как HMACSHA1, является отличной заменой кода на рис. 4.20. Чтобы использовать хэш с ключом, просто используйте соль вместо ключа, а в противном случае следуйте образцу кода на рисунке 4.19.

Политика безопасности

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

Примеры работы алгоритмов хеширования

Вот полное изложение того, что такое алгоритмы хеширования и как они работают.

Если бы криптография была телом, ее алгоритм хеширования был бы ее сердцем. Если бы криптография была автомобилем, ее алгоритм хеширования был бы ее двигателем. Если бы «Криптография» была фильмом, ее алгоритм хеширования был бы главным героем. Если бы криптография была Солнечной системой, ее алгоритмом хеширования было бы Солнце.Ладно, это слишком далеко, но вы ведь поняли? Прежде чем мы перейдем к тому, что такое алгоритм хеширования, почему он существует и как он работает; важно понимать, где находятся его гайки и болты. Начнем с Хеширование .

Что такое хеширование?

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

Используя выбранный алгоритм хеширования, данные сжимаются до фиксированного размера. Давайте разберемся в этом на примере. Если мы возьмем предложение «Ослы живут долго» и применим к нему хеш-алгоритм joaat , мы получим 6e04f289 . Это значение известно как хэш .

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

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

(Примечание. Здесь мы использовали алгоритм хеширования joaat , поскольку он короткий и легкий для понимания. Современные алгоритмы намного сложнее и длиннее.)

Функция хеширования: ядро алгоритма хеширования

«За каждым успешным человеком -А есть замечательная женщина.»- Граучо Маркс

« За каждым успешным алгоритмом хеширования стоит отличная хеш-функция ». — Мы это только что придумали.

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

Длина вывода или хеш-функции зависит от алгоритма хеширования.Вообще говоря, самые популярные алгоритмы или функции хеширования имеют длину хеширования от 160 до 512 бит.

А теперь перейдем к тому, чего вы так долго ждали.

Что такое алгоритм хеширования? Как это работает?

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

Размер блока (ов) данных отличается от одного алгоритма к другому. Но для конкретного алгоритма он остается прежним. Например, SHA-1 принимает сообщение / данные только блоками по 512 бит. Таким образом, если сообщение имеет длину точно 512 бит, хеш-функция запускается только один раз (80 раундов в случае SHA-1). Точно так же, если сообщение 1024-битное, оно делится на два блока по 512-бит, и хеш-функция запускается дважды.Однако в 99% случаев сообщение не будет кратным 512 битам. Для таких случаев (почти во всех случаях) используется метод Padding . Используя метод заполнения, все сообщение делится на блоки данных фиксированного размера. Хеш-функция повторяется столько раз, сколько блоков данных. Вот как это делается:

Как показано выше, блоки обрабатываются по одному. Выход первого блока данных подается как вход вместе со вторым блоком данных. Следовательно, вывод второго подается вместе с третьим блоком и так далее.Таким образом, делая окончательный вывод объединенным значением всех блоков. Если вы измените один бит в любом месте сообщения, изменится все значение хеш-функции. Это называется «лавинным эффектом».

: Глава 13. Алгоритмы хеширования :: Часть III: Криптография .NET :: Безопасность программирования .NET :: Программирование :: Электронные учебники.org

Хеширование алгоритм создает хэш-код, также называемый «дайджест сообщения» или «отпечаток сообщения». Как мы объяснено в главе 12, хэш-коды имеют ограниченное использовать для безопасности связи, потому что Ева может заменить оба хэш-код и сообщение, которое получает Боб, но они являются важным элементом цифровых подписей, которые мы обсуждаем в Главе 16.

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

13.1.1 Создание хеш-кода

На В основе алгоритма хеширования лежит математическая функция, которая работает на двух блоках данных фиксированного размера для создания хэш-кода, как показано на Рисунок 13-1.

Рисунок 13-1. Хеш-функция работает с блоками данных фиксированного размера

Мы разбиваем сообщение Алисы на блоки, которые являются того же размера, что и вход для хеш-функции. Размер каждых данных блок варьируется в зависимости от алгоритма, но блоки имеют тенденцию быть small — алгоритмы, включенные в.NET Framework сломать сообщения в блоки по 512 или 1024 бит. Дизайн хеша функция различается для каждого алгоритма хеширования, но все они разделяют тот же базовый подход.

Алгоритм определяет «начальное число» значение, которое передается в хеш-функцию вместе с первым блоком данных сообщения, таким образом создавая наш первый хэш-код. Возьмите этот хэш-код и загрузите его в хеш-функцию вместе со вторым блоком данных сообщения, создавая второй хэш код.Загрузите второй хэш-код в функцию вместе с третий блок сообщения и повторить процесс хеширования блока данных вместе с хэш-кодом предыдущего блока, пока вы не получите обработал все данные сообщения, как показано на рисунке 13-2.

Рисунок 13-2. Создание хэш-кода путем «сцепления» хэш-функции

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

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

13.1.2 Пределы сообщений

Существует ограничение на размер сообщения, которое алгоритм хеширования может обработать до того, как хеш-код перестанет безопасный. Очень большое сообщение вызывает начальные байты данных сообщения чтобы иметь меньшее влияние на хэш-код, чем байты в конце сообщения. Это означает, что Еве легче найти сообщение с тем же хеш-кодом, что Алиса отправила Бобу, потому что у нас увеличили вероятность найти два сообщения с немного разные начальные байты, которые приводят к тому же хэш-коду.

Проблема возникает из-за того, что хеш-функция вызывается очень много раз. для больших сообщений, например, сообщение размером 1 ГБ вызовет хэш-функция должна вызываться более 6 000 000 раз. Так много хеширования операции уменьшают «пульсацию» эффект «

Большинство алгоритмов хеширования накладывают ограничение на размер сообщения 2 ⁶⁴ бит. Этот предел не является практическим. внимание к большинству проектов, но может быть проблемой при расчете хэш-коды для данных, генерируемых за длительный период.Некоторые алгоритмы способен обрабатывать 2 ¹²⁸ бит данных надежно.

Все алгоритмы хеширования в .NET Framework могут обрабатывать лимиты сообщений не менее 2 ⁶⁴ бит, которые достаточно для большинства проектов. Однако мы рекомендуем вам нести ограничение, которое следует учитывать при рассмотрении алгоритмов хеширования, предоставляемых третьи лица.

13.1.3 Длина хэш-кода

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

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

Можно создать бесконечное количество разных сообщений, а там являются лишь конечным числом возможных хэш-кодов; следовательно, он должен можно найти пару сообщений, которые производят один и тот же хеш код. В этом разделе мы рассмотрим безопасность 64-битного хеш-кода. который до недавнего времени считался очень безопасным.

Для Евы, чтобы найти сообщение, которое производит тот же хэш-код, что и Алиса. отправил Бобу, мы ожидаем, что ей придется создать и протестировать 2 ⁶⁴ (18,446,744,073,709,551,616) разные сообщения, прежде чем она найдет совпадение (предположим, что хэш-коды равномерно распределены).Если Ева может проверять 50 сообщений в секунду (примерно можно добиться с помощью наших настольных ПК), то на нее уйдет 11,6 миллиардов лет, чтобы проверить достаточно сообщений. Если бы Ева смогла получить доступ очень мощные компьютеры, она могла бы проверить 10 миллионов сообщений каждую секунду, но мы все равно ожидаем, что она получит 58 494 лет, чтобы найти совпадение. Это основная безопасность хэш-кодов; реально, Ева не может ждать почти 60000 лет, а это означает, что поиск подходящего сообщения для определенного хэш-кода — это «вычислительно неосуществимо «фраза, которая используется криптографы, чтобы означать «возможно, но чрезвычайно вряд ли.«

Однако, если Ева может контролировать содержание обоих сообщений, она гораздо проще найти два совпадающих хэш-кода, известных как коллизия сообщений. Если Ева захочет найти любую пару сообщений, которые создают одно и то же хеш-код, то ей остается только создать и протестировать 2 ³² разных сообщений, прежде чем она получит вероятность найти два таких же совпадения выше 50%. На самом деле, если она может проверять 50 сообщений в секунду, она, вероятно, найдет совпадение в менее 3 лет, что намного меньше, чем 11.6 миллиардов лет это потребуется для обработки 2 ⁶⁴ сообщений. Если Ева может проверять 10 миллионов сообщений в секунду, она, скорее всего, найти пару сообщений чуть более чем за 7 минут.

У Евы теперь есть пара сообщений, которые она написала, оба из которых в результате получится тот же хэш-код. Она не может использовать эти сообщения, чтобы беспокоить Алиса и Боб, потому что она вряд ли заставит Алису хешировать любой из ее сообщения и отправьте их Бобу. Однако Ева может использовать следующие атака с целью обмануть Джо, который должен ей немного денег:

Ева создает две версии сообщения.Первое сообщение дает указание Банк Джо должен заплатить Еве 100 долларов, то есть сумму, которую он в долгу перед ней. Второе сообщение инструктирует банк Джо заплатить Еве 1000000 долларов.
Ева генерирует 2 ³² вариантов безобидное сообщение путем внесения незначительных редакционных изменений, которые не повлиять на смысл сообщения (например, добавление пробелов или вкладки или изменение форматирования).
Ева также генерирует 2 ³² ее вариаций нечестное сообщение.Поскольку она контролирует содержание обоих сообщений, шансы на то, что она найдет версию безобидного сообщение и нечестное сообщение с тем же хеш-кодом лучше чем 50%.
Ева отправляет безобидное сообщение Джо, который создает хэш-код и подписать его цифровой подписью (подробнее см. главу 16). информация о цифровых подписях). Джо отправляет подписанный хэш-код Еве, чтобы она могла передать подписанное сообщение его банку.
Ева представляет свое нечестное сообщение банку Джо вместе с подписанным хэш-кодом.Банк проверяет цифровую подпись и обнаруживает, что хэш-код совпадает с сообщением и что Джо подписал это. Ева смогла подделать подпись, не обучаясь Секретные ключи Джо.

К счастью, по крайней мере для Джо, большинство банков не удовлетворило бы запрос на миллионов долларов таким образом. Тем не менее, Ева смогла создать поддельное сообщение с очень небольшими усилиями, если Джо использовал 64-битный хэш-код для его подписи, Ева потребовала бы где-то от 7 минут до 3 лет на создание сообщений.Подобный поиск столкновений — это «день рождения» атаки и резко снижает эффективность алгоритма хеширования, заставляющего вас обрабатывать хеш код, как если бы он составлял только половину его реальной длины.

Сколько человек должно быть в комнате, прежде чем вероятность одного из они разделяют ваш день рождения больше 50%? Ответ — 183. Сколько человек должно быть в комнате, прежде чем вероятность любые два человека, у которых один день рождения, более 50%? Ответ — 23.Легче найти любой общий день рождения, чем найти конкретный.

Ева полагается на возможность создать два сообщения, которые производят тот же хеш-код, зная, что это проще, чем пытаться найти соответствует конкретному сообщению от Алисы. Любая атака по этим линиям это «атака на день рождения».

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

13.1.4 Алгоритмы хеширования .NET Framework

.NET Framework включает классы для пяти разные алгоритмы хеширования, хотя четыре из них близко связанных, будучи вариациями одной и той же базовой предпосылки для создания хеша коды разной длины.В Таблице 13-1 перечислены Доступны алгоритмы хеширования.

Таблица 13-1. Сводка алгоритмов хеширования .NET Framework
MD5	512	2 ⁶⁴	128
SHA-1	512	2 ⁶⁴	160
SHA-256	512	2 ⁶⁴	256
SHA-384	1024	2 ¹²⁸	384
SHA-512	1024	2 ¹²⁸	512

Разработанный в 1991 году, MD5 использовался во всех видах систем и является неотъемлемой частью многих стандартов связи безопасность.MD означает «Сообщение Digest «, а MD5 стал пятым таким алгоритмом, Ривест задумал.

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

Агентство национальной безопасности (АНБ) разработало Алгоритм безопасного хеширования (SHA) в 1993 году, и Национальный институт стандартов и технологий (NIST) опубликовал его как Федеральный стандарт обработки информации (FIPS) 180, разрешение его использования в государственных проектах.АНБ отозвало стандарт вскоре после публикации, заменив его на SHA-1, который содержал небольшая модификация хеш-функции.

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

NIST опубликовал FIPS 180-2 в 2001 году, который определяет SHA-256, Алгоритмы SHA-384 и SHA-512, названные по длине хеша код, который производит каждый. Эти новые алгоритмы представляют собой вариации SHA-1, но они появились достаточно недавно, чтобы их криптографическая безопасность остается открытым.

Прежде чем выбирать алгоритм, подумайте, сколько вы знаете об алгоритме. для использования в проекте.Например, хотя SHA-256, SHA-384 и SHA-512 имеют более длинные хэш-коды, MD5 и 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 расшифровывается как Secure Hash Algorithm — его название раскрывает его цель — он предназначен для криптографической безопасности.

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

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

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

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

Протокол SSL / TLS используется для обеспечения безопасной передачи данных от одного устройства к другому через Интернет. Для краткости кажется, что SSL часто называют «шифрованием». Но не забывайте, что SSL также обеспечивает аутентификацию . Файл сертификата SSL должен предоставить информацию, необходимую для аутентификации.Или, другими словами, сертификаты SSL привязывают определенный открытый ключ к личности.

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

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

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

Цифровые подписи — важная часть того, как сертификаты SSL обеспечивают аутентификацию.Когда сертификат выдается, он подписывается цифровой подписью Центром сертификации (ЦС), который вы выбрали в качестве поставщика сертификатов (например, Sectigo, DigiCert и т. Д.). Эта подпись обеспечивает криптографическое доказательство того, что CA подписал сертификат 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 сегодня, он должен использовать эту подпись как минимум .

Иногда вы будете видеть сертификаты, использующие 384-битный SHA-2. Вы редко встретите 224-битный вариант, который не одобрен для использования с общедоступными сертификатами, или 512-битный вариант, который менее широко поддерживается программным обеспечением.

SHA-2, вероятно, будет использоваться не менее пяти лет. Однако может быть обнаружена некоторая неожиданная атака на алгоритм, которая вызовет более ранний переход.

Вот как выглядит хэш SHA-1 и SHA-2 SSL-сертификата нашего веб-сайта:

Расчет изображения и хэша с MD5File.com
Итак, да. В этом вся суета. Может показаться, что это не так уж и много, но цифровые подписи невероятно важны для обеспечения безопасности SSL / TLS.
Более крупный битовый хэш может обеспечить большую безопасность, поскольку существует больше возможных комбинаций. Помните, что одна из важных функций алгоритма криптографического хеширования — это создание уникальных хэшей.Опять же, если два разных значения или файла могут создавать один и тот же хэш, вы создаете то, что мы называем коллизией .
Безопасность цифровых подписей может быть гарантирована только до тех пор, пока не произойдет коллизий. Коллизии чрезвычайно опасны, потому что они позволяют двум файлам создавать одну и ту же подпись, поэтому, когда компьютер проверяет подпись, она может оказаться действительной, даже если этот файл никогда не был подписан.
Сколько хешей?
Если предполагается, что алгоритм хеширования генерирует уникальные хеши для каждого возможного ввода, сколько всего возможных хешей существует?
Бит имеет два возможных значения: 0 и 1.Возможное количество уникальных хэшей может быть выражено как количество возможных значений, возведенных в число битов. Для SHA-256 существует 2 ²⁵⁶ возможных комбинаций.
Итак, 2 ²⁵⁶ комбинаций. Сколько это? Ну это огромное количество. Шутки в сторону. Это посрамляет такие цифры, как триллион и септиллион. Это намного превышает количество песчинок в мире.
Чем больше количество возможных хешей, тем меньше вероятность того, что два значения создадут один и тот же хеш.
Существует (технически) бесконечное количество возможных входов [1], но ограниченное количество выходов. Таким образом, в конце концов, каждый алгоритм хеширования, в том числе и безопасный, вызывает коллизию. Но нас больше всего беспокоит, насколько легко это будет сделать. SHA-1 был признан небезопасным, поскольку из-за его размера и конструкции было возможно вызвать столкновение.
Обратите внимание, что большая длина в битах не означает, что , а не , автоматически означает, что алгоритм хеширования создает более безопасные хэши.Построение алгоритма также невероятно важно, поэтому в индустрии SSL используются алгоритмы хеширования, специально разработанные для криптографической безопасности.
Переход к SHA-2
В 2015 году отрасль SSL пережила «переход на SHA-2». Это включало повторную выдачу тысяч существующих сертификатов, чтобы можно было создавать новые файлы и подписывать их с помощью SHA-2. Это также включало серьезные обновления программного обеспечения выдачи, которое работает в общедоступных центрах сертификации (их десятки).Как и ожидалось, была небольшая икота.
Крайний срок для выпуска новых сертификатов SSL с хешами SHA-1 — 31 декабря ^st, 2015. По большей части отрасль придерживается этого срока. С тех пор было сделано несколько ошибок, и было разрешено несколько особых случаев.
Но за последние три года сертификаты SHA-1 практически исчезли. Сегодня, если вы столкнетесь с сертификатом SHA-1, вы увидите безошибочное предупреждение. Это нарастает.В Google Chrome для всех сертификатов SHA-1, срок действия которых истекает в 2016 году, не отображался зеленый замок в защищенных соединениях, а вместо этого отображался тот же значок, что и при незащищенном HTTP-соединении. Вы можете щелкнуть значок, чтобы получить более конкретную информацию о том, почему он отображается, если есть другие причины, не связанные с подписью.
Если вы сегодня видели сертификат SHA-1 в своем браузере, вот как он будет выглядеть (в Google Chrome). Чтобы увидеть, как эта страница выглядит в вашем браузере, посетите https: // sha1-2016.badssl.com
Браузеры обрабатывали подписанные сертификаты SHA-1, срок действия которых истекает в 2017 году, более строгим предупреждением. Это связано с тем, что безопасность подписи напрямую зависит от того, как долго она действительна.
Теперь, в 2018 году, Google просто казнит владельца сайта и оставляет его труп в качестве предупреждения для других, которые могут осмелиться совершить те же грехи.
Обеспечение безопасности подписей
Со временем атаки на криптографию будут улучшаться, а вычислительная мощность компьютеров станет дешевле.Это делает действительную подпись SHA-2 менее безопасной в 2020 году, чем в 2016 году. По этой причине выбор алгоритма будет гораздо более жестким, чем это необходимо немедленно, чтобы краткосрочные улучшения не привели к снижению безопасности. Нет ничего невозможного в том, чтобы конкретный алгоритм хеширования оставался безопасным в течение десяти лет.
Отраслевые эксперты и исследователи безопасности по всему миру постоянно анализируют SHA-2 и другие алгоритмы криптографического хеширования, поэтому будьте уверены, что текущие сертификаты SSL будут иметь надежные и безопасные цифровые подписи на какое-то время.
Это не означает, что криптографы будут просто сидеть и ждать, пока не возникнет проблема. Преемник SHA-2, получивший удобное название SHA-3, уже доработан. Когда пришло время сделать еще один переход, отрасль SSL может использовать SHA-3 в качестве следующего выбора или может обратиться к совершенно другому алгоритму.
Требуются годы, чтобы должным образом исследовать и проверить новые криптографические стандарты, а затем разработать программное обеспечение, которое их поддерживает. Надеюсь, это обнадеживает, знать, что отрасль всегда как минимум на шаг впереди.
Время от времени нам нравится повторно хешировать наш лучший старый контент в надежде, что он понравится нашим новым читателям. Эта статья, изначально написанная Винсентом Линчем 29 июня 2016 года, была обновлена и отредактирована Патриком Ноэ за 2018 год.

Обзор алгоритма хеширования
: типы, методологии и использование
Алгоритм хеширования — это математическая функция, которая искажает данные и делает их нечитаемыми.
Алгоритмы хеширования — это односторонние программы, поэтому текст не может быть расшифрован и декодирован кем-либо еще.И в этом суть. Хеширование защищает данные в состоянии покоя, поэтому даже если кто-то получит доступ к вашему серверу, хранящиеся на нем элементы останутся нечитаемыми.
Хеширование также может помочь вам доказать, что данные не были скорректированы или изменены после того, как автор закончил с ними. А некоторые люди используют хеширование, чтобы помочь им разобраться в огромных массивах данных.
Что такое алгоритм хеширования?
Существуют десятки различных алгоритмов хеширования, и все они работают по-разному. Но в каждом из них люди вводят данные, и программа изменяет их в другой форме.
Всего алгоритмов хеширования:
Математический. В основе работы алгоритма лежат строгие правила, которые нельзя нарушить или изменить.
Униформа. Выберите один тип алгоритма хеширования, и данные любого количества символов, пропущенные через систему, будут появляться с длиной, предопределенной программой.
Согласованный. Алгоритм делает только одно (сжимает данные) и ничего больше.
В одну сторону. После преобразования алгоритмом вернуть данные в исходное состояние практически невозможно.
Важно понимать, что хеширование и шифрование — это разные функции. Вы можете использовать их вместе друг с другом. Но не используйте эти термины как синонимы.
Как работает алгоритм хеширования?
Можно создать алгоритм, используя не что иное, как диаграмму, калькулятор и базовые знания математики.Но большинство людей используют компьютеры для помощи.
Большинство алгоритмов хеширования следуют этому процессу:
Создайте сообщение. Пользователь определяет, что следует хешировать.
Выберите тип. Существуют десятки алгоритмов хеширования, и пользователь может решить, какой из них лучше всего подходит для этого сообщения.
Введите сообщение. Пользователь вводит сообщение в компьютер, на котором запущен алгоритм.
Запустить хеш. Система преобразует сообщение, которое может иметь любую длину, до заранее определенного размера в битах. Обычно программы разбивают сообщение на серию блоков одинакового размера, и каждый из них последовательно сжимается.
Хранить или делиться. Пользователь отправляет хэш (также называемый «дайджестом сообщения») предполагаемому получателю, или хешированные данные сохраняются в этой форме.
Процесс сложный, но работает очень быстро. Через секунды хеш будет завершен.
Для чего используются алгоритмы хеширования?
Самый первый алгоритм хеширования, разработанный в 1958 году, использовался для классификации и организации данных. С тех пор разработчики обнаружили десятки вариантов использования этой технологии.
Ваша компания может использовать алгоритм хеширования для:
Хранение паролей. Вы должны вести учет всех комбинаций имени пользователя и пароля, которые люди используют для доступа к вашим ресурсам. Но если хакер получит доступ, украсть незащищенные данные очень просто.Хеширование гарантирует, что данные хранятся в зашифрованном виде, поэтому их труднее украсть.
Цифровые подписи. Небольшой кусочек данных доказывает, что заметка не была изменена с того момента, как она покидает почтовый ящик пользователя и попадает в ваш почтовый ящик.
Документооборот. Алгоритмы хеширования могут использоваться для аутентификации данных. Автор использует хеш для защиты документа, когда он готов. Хеш работает как знак одобрения.
Получатель может сгенерировать хэш и сравнить его с исходным.Если они равны, данные считаются подлинными. Если они не совпадают, документ был изменен.
Управление файлами. Некоторые компании также используют хэши для индексации данных, идентификации файлов и удаления дубликатов. Если в системе тысячи файлов, использование хешей может значительно сэкономить время.
Примеры алгоритмов хеширования
Может быть трудно понять, что делают эти специализированные программы, не увидев их в действии.
Представьте, что мы хотим хешировать ответ на секретный вопрос. Мы спросили: «Где был ваш первый дом?» Нам дают ответ: «На крыше жилого дома в Квинсе». Вот как выглядят хеши с:
MD5 : 72b003ba1a806c3f94026568ad5c5933
SHA-256 : f6bf870a2a5bb6d26ddbeda8e903f3867f729785a36f89bfae896776777d50af
Теперь представьте, что мы задали тот же вопрос другому человеку, и он ответил: «Чикаго.»Вот как выглядят хеши с:
MD-5 : 9cfa1e69f507d007a516eb3e9f5074e2
SHA-256 : 0f5d983d203189bbffc5f686d01f6680bc6a83718a515fe42639347efc92478e
Обратите внимание, что в исходных сообщениях разное количество символов. Но алгоритмы каждый раз создают хэши постоянной длины.
Обратите внимание, что хеши полностью искажены. Практически невозможно понять, что они говорят и как работают.
Объяснение популярных алгоритмов хеширования
Многие программы разных типов могут преобразовывать текст в хэш, и все они работают немного по-разному.
Общие алгоритмы хеширования включают:
МД-5. Этот — один из первых алгоритмов, получивших широкое признание. Он был разработан в 1991 году и в то время считался чрезвычайно безопасным.
С тех пор хакеры обнаружили, как расшифровать алгоритм, и они могут сделать это за секунды.Большинство экспертов считают, что это небезопасно для широкого использования, так как его очень легко разорвать.
РИПЭМД-160. Дайджест сообщения оценки примитивов целостности RACE (или RIPEMD-160) был разработан в Бельгии в середине 1990-х годов. Он считается чрезвычайно безопасным, поскольку хакеры еще не совсем поняли, как его взломать.
SHA. Алгоритмы семейства SHA считаются немного более безопасными. Первые версии были разработаны правительством США, но другие программисты основывались на исходных фреймворках и сделали более поздние версии более строгими и трудными для взлома.В общем, чем больше число после букв «SHA», тем более поздний выпуск и более сложная программа.
Например, SHA-3 включает в себя источники случайности в коде, что значительно затрудняет взлом, чем те, что были раньше. По этой причине в 2015 году он стал стандартным алгоритмом хеширования.
Водоворот. В 2000 году дизайнеры создали этот алгоритм на основе Advanced Encryption Standard. Это также считается очень безопасным.
Правительство может больше не участвовать в написании алгоритмов хеширования. Но власти действительно должны сыграть свою роль в защите данных. Программа проверки криптографических модулей, частично выполняемая Национальным институтом стандартов и технологий, проверяет криптографические модули. Компании могут использовать этот ресурс, чтобы убедиться, что они используют безопасные и эффективные технологии.
Сколько вы должны знать о хешировании?
Если вы работаете в сфере безопасности, вам важно знать все тонкости защиты.Хеширование — это ключевой способ гарантировать, что важные данные, включая пароли, не будут украдены кем-то, у кого есть средства причинить вам вред.
Частным лицам также может быть полезно понимание концепций хеширования. Например, если вы когда-либо хотели участвовать в биткойнах, вы должны хорошо разбираться в хешировании. Ваши торговые партнеры активно используют эту технологию, поскольку используют ее в процессах блокчейна.
Но если математика, лежащая в основе алгоритмов, сбивает с толку, не волнуйтесь. Большинство компьютерных программ берут на себя тяжелую работу по вычислениям.
В Okta мы также упрощаем защиту ваших данных. У нас есть сложные программы, которые могут защитить вас от хакеров и обеспечить бесперебойную работу вашей работы.
И мы всегда готовы ответить на вопросы и помочь, когда вам понадобится помощь. Связаться с нами, чтобы узнать больше.
Список литературы
Ханс Петер Лун и рождение алгоритма хеширования. (Январь 2018). IEEE Spectrum.
Алгоритмы хеширования. Центр знаний IBM.
Генератор хэшей MD5. Инструменты Дэна.
Генератор хэшей SHA-256. Инструменты Дэна.
Функция криптографического хеширования. Википедия.
Программа проверки криптографических модулей. Национальный институт стандартов и технологий.
алгоритмов безопасного хеширования | Блестящая вики по математике и науке
Secure Hash Algorithm 1 , или SHA-1, был разработан в 1993 году государственным агентством стандартов США Национальным институтом стандартов и технологий (NIST). Он широко используется в приложениях и протоколах безопасности, включая TLS, SSL, PGP, SSH, IPsec и S / MIME.{64} 264 бита и создание 160-битного хэш-значения, известного как дайджест сообщения . Обратите внимание, что сообщение ниже представлено в шестнадцатеричной системе счисления для компактности.
Существует два метода шифрования сообщений с использованием SHA-1. Хотя один из методов сохраняет обработку шестидесяти четырех 32-битных слов, его выполнение более сложное и требует много времени, поэтому простой метод показан в примере ниже. В конце выполнения алгоритм выводит блоки из 16 слов, где каждое слово состоит из 16 бит, всего 256 бит.
Псевдокод
Предположим, сообщение «abc» должно быть закодировано с использованием SHA-1, при этом сообщение «abc» в двоичном формате имеет значение
.
01100001 01100010 0110001101100001 \ 01100010 \ 0110001101100001 01100010 01100011
, а в шестнадцатеричном —
616263.616263.616263.
1) Первым шагом является инициализация пяти случайных строк шестнадцатеричных символов, которые будут служить частью хэш-функции (показано в шестнадцатеричном формате):
H0 = 67DE2A01h2 = BB03E28Ch3 = 011EF1DCh4 = 9293E9E2h5 = CDEF23A9.\ begin {выровнено} H_0 & = 67DE2A01 \\ H_1 & = BB03E28C \\ H_2 & = 011EF1DC \\ H_3 & = 9293E9E2 \\ H_4 & = CDEF23A9. \ end {выровнен} H0 h2 h3 h4 h5 = 67DE2A01 = BB03E28C = 011EF1DC = 9293E9E2 = CDEF23A9.
2) Затем сообщение дополняется добавлением 1, за которым следует достаточное количество нулей, пока сообщение не станет 448 битов. Длина сообщения, представленная 64 битами, затем добавляется в конец, создавая сообщение длиной 512 бит:
Заполнение строки «abc» в битах, завершающееся длиной строки, которая составляет 24 бита.
3) Полученный выше дополненный ввод, MMM, затем делится на 512-битные блоки, и каждый блок далее делится на шестнадцать 32-битных слов, W0… W15W_0… W_ {15} W0… W15. В случае «abc» есть только один фрагмент, так как всего сообщение меньше 512 бит.
4) Для каждого фрагмента начните 80 итераций iii, необходимых для хеширования (80 — это определенное число для SHA-1), и выполните следующие шаги для каждого фрагмента, Mn: M_n: Mn:
Для итераций с 16 по 79, где 16≤i≤7916 \ leq i \ leq 7916≤i≤79, выполните следующую операцию: W (i) = S1 (W (i − 3) ⊕W (i − 8) ⊕W (i − 14) ⊕W (i − 16)), W (i) = S ^ 1 \ big (W (i -3) \ oplus W (i-8) \ oplus W (i-14) \ oplus W (i-16) \ big), W (i) = S1 (W (i − 3) ⊕W (i − 8 ) ⊕W (i − 14) ⊕W (i − 16)), где XOR, или ⊕ \ oplus⊕, представлено следующим сравнением входных данных xxx и y: y: y:
Например, если iii равно 16, выбраны слова W (13), W (8), W (2), W (0) W (13), W (8), W (2), W ( 0) W (13), W (8), W (2), W (0), а на выходе — новое слово, W (16) W (16) W (16), поэтому выполняется XOR, или ⊕ \ oplus⊕, операция над этими словами даст следующее:
Вт (0) Вт (0) Вт (0) 01100001 01100010 01100011 1000000001100001 \ 01100010 \ 01100011 \ 1000000001100001 01100010 01100011 10000000
Вт (2) Вт (210 Вт (2) 00000000 00000000 0000000000000000 \ 00000000 \ 00000000 \ 0000000000000000 00000000 00000000 00000000
W (8) W (8) W (8) 00000000 00000000 00000000 0000000000000000 \ 00000000 \ 00000000 \ 0000000000000000 00000000 00000000 00000000
W (13 ) W (13) W (13) 00000000 00000000 00000000 0000000000000000 \ 00000000 \ 00000000 \ 0000000000000000 00000000 00000000 00000000
⊕ \ oplus ⊕
W (16) W (16) W (16) 01100001 01100010 01100011 1000000001100001 \ 01100010 \ 01100011 \ 1000000001100001 01100010 01100011 10000000
Круговой сдвиг
Теперь операция циклического сдвига Sn (X) S ^ n (X) Sn (X) в слове XXX на nnn битов, где nnn является целым числом от 000 до 323232, определяется как
Sn (X) = (X << n) ИЛИ (X >> 32 − n), S ^ n (X) = (X << n) \ quad \ textbf {OR} \ quad (X >> 32- n), Sn (X) = (X << n) ИЛИ (X >> 32 − n),
, где X << nX << nX << n - операция сдвига влево , полученная отбрасыванием крайних левых nnn битов XXX и дополнением результата nnn нулями справа.n \ big (W (i) \ big), Sn (W (i)), где W (i) W (i) W (i) равно 10010,10010,10010, даст 010010100101001, поскольку крайний правый бит 000 равен переместился в левую часть струны. Следовательно, W (16) W (16) W (16) в итоге будет
.
11000010 11000100 11000111 000000000.11000010 \ 11000100 \ 11000111 \ 000000000.11000010 11000100 11000111 000000000.
5) Теперь сохраните хеш-значения, определенные на шаге 1, в следующих переменных:
A = H0B = h2C = h3D = h4E = h5. \ Begin {выровнено} A & = H_0 \\ B & = H_1 \\ C & = H_2 \\ D & = H_3 \\ E & = H_4.{30} (В) \\ В & = А \\ A & = ТЕМП. \ end {выровнен} EDCBA = D = C = S30 (B) = A = TEMP.
7) Сохраните результат хеширования фрагмента в общем значении хеш-функции всех фрагментов, как показано ниже, и перейдите к выполнению следующего фрагмента:
H0 = H0 + Ah2 = h2 + Bh3 = h3 + Ch4 = h4 + Dh5 = h5 + E. \ Begin {выровнено} H_0 & = H_0 + A \\ H_1 & = H_1 + B \\ H_2 & = H_2 + C \\ H_3 & = H_3 + D \\ H_4 & = H_4 + E. \ end {align} H0 h2 h3 h4 h5 = H0 + A = h2 + B = h3 + C = h4 + D = h5 + E.
8) В качестве последнего шага, когда все фрагменты обработаны, дайджест сообщения представляется как 160-битная строка, состоящая из логического оператора OR , ∨ \ lor∨, из 5 хешированных значений:
HH = S128 (H0) ∨ S96 (h2) ∨ S64 (h3) ∨ S32 (h4) ∨ h5.{32} (H_3) \ \ lor \ H_4.HH = S128 (H0) ∨ S96 (h2) ∨ S64 (h3) ∨ S32 (h4) ∨ h5.
Таким образом, строка «abc» становится хеш-значением, аналогичным a9993e364706816aba3e25717850c26c9cd0d89d .
Если строка изменится на «abcd», например, хешированное значение будет совершенно другим, поэтому злоумышленники не смогут сказать, что оно похоже на исходное сообщение. Хеш-значение для abcd — 81fe8bfe87576c3ecb22426f8e57847382917acf .
Функции, используемые в алгоритме
В SHA-1 используется последовательность логических функций, в зависимости от значения iii, где 0≤i≤790 \ leq i \ leq 790≤i≤79, и от трех 32-битных слов B, C и D , чтобы получить 32-битный вывод.Следующие уравнения описывают логические функции, где ¬ \ neg¬ — это логическое НЕ , ∨ \ lor∨ — логическое OR , ∧ \ land∧ — логическое AND , а ⊕ \ oplus⊕ — логическое. XOR:
f (i; B, C, D) = (B ∧ C) ∨ ((¬B) ∧D) для 0≥i≥19f (i; B, C, D) = B ⊕ C ⊕ D для 20≥i ≥39f (i; B, C, D) = (B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D) для 40≥i≥59f (i; B, C, D) = B⊕ C ⊕ D для 60≥i≥79. \ Begin {align} f (i; B, C, D) \ & = \ (B \ \ land \ C) \ lor \ big ((\ neg B) \ land D \ big) && \ text {for} \ 0 \ geq i \ geq 19 \\\\ f (i; B, C, D) \ & = \ B \ \ oplus \ C \ \ oplus \ D && \ text {for} \ 20 \ geq i \ geq 39 \\\\ f (i; B, C, D) \ & = \ (B \ \ land \ C) \ \ lor \ (B \ \ land \ D) \ lor \ (C \ \ land \ D) && \ text {для } \ 40 \ geq i \ geq 59 \\\\ f (i; B, C, D) \ & = \ B \ oplus \ C \ \ oplus \ D && \ text {for} \ 60 \ geq i \ geq 79.\ end {align} f (i; B, C, D) f (i; B, C, D) f (i; B, C, D) f (i; B, C, D) = (B ∧ C) ∨ ((¬B) ∧D) = B ⊕ C ⊕ D = (B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D) = B⊕ C ⊕ D для 0≥i≥19 для 20 ≥i≥39 для 40≥i≥59 для 60≥i≥79.
Кроме того, в формулах используется последовательность постоянных слов, показанная ниже в шестнадцатеричном формате:
K (i) = 5A827999, где 0≤i≤19K (i) = 6ED9EBA1, где 20≤i≤39K (i) = 8F1BBCDC, где 40≤i≤59K (i) = CA62C1D6, где 60≤i≤79 . \ begin {выровнено} K (i) & = 5A827999, && \ text {где} \ 0 \ leq i \ leq 19 \\\\ K (i) & = 6ED9EBA1, && \ text {где} \ 20 \ leq i \ leq 39 \\\\ K (i) & = 8F1BBCDC, && \ text {где} \ 40 \ leq i \ leq 59 \\\\ K (i) & = CA62C1D6, && \ text {где} \ 60 \ leq i \ leq 79.\ end {align} K (i) K (i) K (i) K (i) = 5A827999, = 6ED9EBA1, = 8F1BBCDC, = CA62C1D6, где 0≤i≤19, где 20≤i≤39, где 40≤i ≤59, где 60≤i≤79.
Несмотря на то, что SHA-1 все еще широко используется, криптоаналитики в 2005 году смогли найти уязвимости в этом алгоритме, которые нанесли ущерб его безопасности. Эти уязвимости проявились в форме алгоритма, который быстро находит коллизии с разными входами, что означает, что два разных входа отображаются в один и тот же дайджест ^[4].
No related posts.

Вт (0) Вт (0) Вт (0)	01100001 01100010 01100011 1000000001100001 \ 01100010 \ 01100011 \ 1000000001100001 01100010 01100011 10000000
Вт (2) Вт (210	Вт (2) 00000000 00000000 0000000000000000 \ 00000000 \ 00000000 \ 0000000000000000 00000000 00000000 00000000
W (8) W (8) W (8)	00000000 00000000 00000000 0000000000000000 \ 00000000 \ 00000000 \ 0000000000000000 00000000 00000000 00000000
W (13 ) W (13) W (13)	00000000 00000000 00000000 0000000000000000 \ 00000000 \ 00000000 \ 0000000000000000 00000000 00000000 00000000
	⊕ \ oplus ⊕
W (16) W (16) W (16)	01100001 01100010 01100011 1000000001100001 \ 01100010 \ 01100011 \ 1000000001100001 01100010 01100011 10000000