Как формируется hmac

HMAC (сокращение от англ. hash-based message authentication code , хеш-код аутентификации сообщений). Наличие способа проверить целостность информации, передаваемой или хранящийся в ненадежной среде является неотъемлемой и необходимой частью мира открытых вычислений и коммуникаций. Механизмы, которые предоставляют такие проверки целостности на основе секретного ключа, обычно называют кодом аутентичности сообщения (MAC). Как правило, МАС используется между двумя сторонами, которые разделяют секретный ключ для проверки подлинности информации, передаваемой между этими сторонами. Этот стандарт определяет MAC. Механизм, который использует криптографические хеш-функции в сочетании с секретным ключом называется HMAC.

Основная цель:

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

Разработчики: Хьюго Кравчик, Михир Беллар и Ран Каннетти.

Содержание

Описание

В последние годы наблюдается повышенный интерес к разработке MAC на основе криптографических хэш-функций, например, MD5, SHA-1 или RIPEMD-160. А мотивы этого интереса просты:

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

HMAC был выбран в качестве обязательной (англ. mandatory to implement ) при реализации MAC для IP-безопасности, и используется в других интернет-протоколах, таких, как Transport Layer Security (TLS, который вскоре заменит Secure Sockets Layer) и Secure Electronic Transaction (SET).

Принцип работы

На рисунке 1 показан общий алгоритм HMAC:

Если длина ключа К = b, то = K . Переходим сразу к шагу 4.
Если длина ключа K > b, то применяем функцию H к ключу K для получения L-байтовой строки. Добавить нули к левой части этой строки для создания b-байтовой строки .Переходим сразу к шагу 4.
Если длина ключа K < b то добавляем нули к левой части K для создания b-байтовой строки (например, если К имеет длину 20 байтов и b = 64, то к левой части К будет добавлено 44 нулевых байта 0x00).
$\oplus$ ipad — (xor побитовое исключающее ИЛИ) для получения b-байтового блока .
Сложить М с .
Применить Н к потоку, созданному на шаге 5.
$\oplus$ opad для получения b-байтового блока .
Сложить результат хеширования на шаге 6 с .
Применить функцию Н к потоку, созданному на шаге 8 и вывести результат.

или если выразить одной математической формулой : $\mathrm<HMAC>_K(m) = h\Bigg((K \oplus \mathrm<opad>) \| h\Big((K \oplus \mathrm<ipad>) \| m\Big)\Bigg)» width=»» height=»» /></p> <p>Более эффективная реализация возможна, как показано на рисунке 2. Где F является функция сжатия для хэш-функции, которая принимает в качестве аргументов: переменную N и блок длиной b байт, и производит разбиение блока в цепочку блоков с длиной каждого N байтов. Эти операции необходимо выполнить только в самом начале и каждый раз, когда ключ изменяется. В этой реализации, появляется только один дополнительный элемент — функция сжатия F для нормальной работы хэш-функции. Это реализация особенно целесообразна, если большинство сообщений, для которых вычисляется MAC , короткие.</p> <h3>HMAC параметры и обозначения</h3> <p>HMAC алгоритм использует следующие параметры:</p> <p><img decoding=$

b — размер блока (в байтах).
H — хэш-функция.
ipad — блок вида : (0x363636 . 3636). Повторяется b раз.
К — секретный ключ.
— это K после предварительной необходимой обработки для получения b-байтового ключа.
L — размер блока (в байтах) на выходе хэш-функции.
opad — блок вида : (0x5c5c5c . 5c5c). Повторяется b раз.
М — передаваемое сообщение. Длина сообщения N бит.

Криптографический ключ

L/2

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

Псевдокод

Следующий псевдокод показывает как HMAC может быть реализован:

Возможные реализации

Представленные ниже языки программирования были выбраны из-за наличия стандартных библиотек, поддерживающих данный алгоритм. Пример использования реализации алгоритма на языке Python [1] :

Одна из возможных реализаций алгоритма на языке PHP [2] :

Примеры

Продемонстрируем пример работы алгоритма для различных входных данных.

Первый параметр — 160-битный ключ. Второй параметр — передаваемое сообщение. На выходе мы получаем 160-битный код аутентификации.

Рассмотрим более подробно алгоритм HMAC на примере хэш-функции SHA-1 с 20-байтовым ключом:
Имеем: текстовое сообщение
Text: Hello World

и 20-байтовый ключ в шестнадцатеричном виде
Key:
0x707172737475767778797a7b7c7d7e7f80818283

K_0

1 шаг:
Дополняем Key нулевыми байтами до размера блока SHA-1(64 байта)
:
70717273 74757677 78797a7b 7c7d7e7f
80818283 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

2 шаг:
Побитовое исключающее ИЛИ
K_0 $\oplus$ ipad:
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636

$\oplus$

3 шаг:
Конкатенация исходного сообщения с результатом на шаге 2
(Key ipad)||text:
46474445 42434041 4e4f4c4d 4a4b4849
b6b7b4b5 36363636 36363636 36363636
36363636 36363636 36363636 36363636
36363636 36363636 36363636 36363636
48656c6c 6f20576f 726c64

$\oplus$

4 шаг:
Применим SHA-1 к результату, созданному на шаге 3
Hash((Key ipad)||text):
0d42b899 d804e19e bfd86fc4 4f414045 dfc9e39a

5 шаг:
Побитовое исключающее ИЛИ
K_0 $\oplus$ opad:
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c

6 шаг:
Конкатенация результата хеширования на шаге 4 с результатом на шаге 5
( K_0 $\oplus$ opad) || Hash((Key $\oplus$ ipad)||text):
2c2d2e2f 28292a2b 24252627 20212223
dcdddedf 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
5c5c5c5c 5c5c5c5c 5c5c5c5c 5c5c5c5c
0d42b899 d804e19e bfd86fc4 4f414045
dfc9e39a

7 шаг:
Применим SHA-1 к результату, созданному на шаге 6
HMAC(Key, Text) = Hash(( K_0 $\oplus$ opad) || Hash((Key $\oplus$ ipad)||text)):
2e492768 aa339e32 a9280569 c5d02626 2b912431
получили 20 байтовый HMAC(Key, Text)

Вопросы использования

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

Безопасность

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

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

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

1 Введение

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

1.1 Текущее положение

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

1.2 Моральное обязательство

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

2 Надлежащие методы хэширования

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

2.1 Соль хороша для вас

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

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

2.2 Функции получения ключей

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

2.2.1 PBKDF2

PBKDF2 (Password-Based Key Derivation Function 2 или Функция Получения Ключа На Основе Пароля 2) – это функция получения ключа, разработанная RSA Laboratories, используемая для получения стойких ключей на основе хэша. Она работает путем применения псевдослучайной хэш-функции (вроде SHA-256, SHA-512, и т. д.) к строке, в нашем случае – к паролю, вместе с солью и повторением этого процесса большое число раз. Данный процесс может быть обобщен следующей диаграммой:

Мы уже обсудили вопрос соли, однако, стоит отметить, что минимальная длина рекомендуемой соли для PBKDF – 128 бит. Спецификация 1 PBKDF утверждает, что SHA-1 2 является утвержденной PRF (псевдослучайной функцией) для алгоритма. Однако, в 2005 году стало ясно, что SHA-1 – относительно слабая функция 3 и не должна использоваться как HMAC. В ваших интересах использовать достаточно сильный HMAC, чтобы выдержать полный перебор, специальные атаки и потенциальные будущие проблемы дизайна (вроде взлома алгоритма или вычислительной достижимости). Важно отметить разницу между хэшем и HMAC – хэш не связан с аутентификацией сообщения. Он связан только с целостностью данных. HMAC обычно используется для подписи сообщений при хэшировании их с солью, уникальной для ее владельца. HMAC также можно использовать для генерации очень сильных хэшей. Проблема в том, что при известной соли HMAC столь же легко взломать полным перебором. Здесь на выручку приходит PBKDF2, реализующая итеративный HMAC, который увеличивает безопасность и время взлома каждого отдельного хэша. Давайте взглянем на псевдокод этого процесса:

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

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

2.2.2 ARC4PBKDF2

Я (bwall) некоторое время обыгрывал в уме идею динамической энтропии. PBKDF2 кажется хорошей площадкой для ее внедрения. Данная идея заключается в том, чтобы сделать энтропию алгоритма шифрования изменяющейся в ходе шифрования. Она происходит из ограничений некоторых систем быстрого взлома хэшей, которые имеют тенденцию жестко оптимизировать определенные процессы вроде применения энтропии. Чтобы бороться с этим, мы можем добавить относительно быстрый процесс создания дополнительной энтропии, который потребует дополнительных вычислений в ходе взлома хэша и возможного удаления некоторых оптимизаций. В ARC4PBKDF2 поток шифра ARC4 инициализируется ключом, затем данный шифр используется для шифрования открытого текста перед его использованием в HMAC в каждой итерации, продолжая тот же поток и также шифруя результат HMAC. Этот поток ARC4 должен быть единым для всего процесса, чтобы добавить сложности и в без того трудный для взлома метод хэширования. Далее представлен пример реализации на C#.

public byte[] Hash(byte[] input) < ARC4 rc4 = new ARC4(ARC4Key);
byte[] derived = new HMACSHA256(Salt).ComputeHash(rc4.CryptBytes(input));
byte[] temp = derived; for (int x = 0; x < Iterations; x++) < temp = rc4.CryptBytes(new
HMACSHA256(temp).ComputeHash(rc4.CryptBytes(input)));
for (int y = 0; y < derived.Length; y++) < derived[y] ^= temp[y]; >> return derived; >

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

2.2.3 bcrypt

Bcrypt – адаптивная хэш-функция, появившаяся в 1999 году. Она немного походит на PBKDF2, но действует более сложным образом. Первую работу, связанную с данной функцией, опубликованную Наелсом Провосом и Дэвидом Мазьересом, можно найти здесь. Она очень подробно объясняет тонкости алгоритма и его реализацию. Для наших целей будет достаточно краткого обзора с примером.

По сути, bcrypt – это блочный шифр Blowfish 4 , используемый в режиме ECB, с более сложным алгоримом подготовки ключей (особенно, что касается S-блоков). Это позволяет алгоритму быть стойким к возможным будущим атакам и существенно более адаптивным. Реализация алгоритма использует 128-битную соль и усовершенствованный алгоритм, известный, как eksblowfish или expensive key schedule blowfish. Заголовок функции bcrypt выглядит так:

bcrypt(cost, salt, pwd)

Здесь cost – контроллер подготовки ключей (задает ресурсоемкость фазы подготовки ключей), salt – 128-битное значение, а pwd – текстовый (до 56 байтов) ключ, используемый для шифрования по алгоритму Blowfish.

Существует пара действительно удивительных, полезных вещей, касающихся bcrypt и заслуживающих обсуждения. Одна из них – то, что алгоритму НЕОБХОДИМА соль. Хотя соль сама по себе не сохранит ваш украденный SQL-дамп, она увеличит его стойкость. Вторая – то, что алгоритм является (я использовал этот термин уже несколько раз) адаптивным. Время подготовки ключей может быть всего порядка одной миллисекунды или таким большим, как вы захотите. Замечательный факт состоит в том, что для сервера почти безразлично, что проверка пароля занимает 3 секунды вместо 0.3, но для атакующего такое увеличение сложности – абсолютный хаос. Это также позволяет напрямую бороться с экспоненциальным наращиванием вычислительных мощностей (известным, как закон Мура), поскольку со временем вы можете постепенно изменять значение переменной cost, чтобы увеличить сложность паролей.

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

public string bcrypt(int cost, byte[] salt, byte[] password)
< byte[] state = EksBlowFishSetup(cost, salt, password);
string ciphertext = "OrpheanBeholderScryDoubt"; for (int i = 0; i < 64; ++i)
< ciphertext = EncryptECB(state, ciphertext); >
return cost.ToString() + BitConverter.ToString(salt) + ciphertext; >

Вышеприведенный код довольно прост. Сначала значение переменной state устанавливается алгоритмом EksBlowFish – данная стадия является наиболее емкой по времени. Далее идет цикл получения шифртекста, изначально имеющего значение 192-битной магической строки (почти всегда равной "OrpheanBeholderScryDoubt"), путем многократного шифрования шифртекста из предыдущей итерации в режиме ECB вместе со значением переменной state. Итоговый результат – статическая 192-битная конкатенация стоимости, соли и результирующего шифртекста.

3 Заключение

Рассмотренные методы значительно увеличивают время, требуемое для взлома хэшей. Не существует предлога не использовать упомянутые эти методы для хранения паролей. Мы понимаем, что оперирование хэшами может быть сложным, особенно, если вы не понимаете их как следует. Мы в Ballast Security работаем над решением этой проблемы, чтобы даже те, кто не имеет понятия, как обезопасить пароли, смогли бы сделать это ценой минимальных усилий.
Похожие публикации:

Как формируется hmac