1. Симметричное Шифрование
2. Криптографические хеш-функции
3. Message Authentication Code

Разберемся, что такое крипто хеш-функции; какими свойствами обладают такие функции; где и зачем используются; что такое proof of work; как он помогает от спамеров и как используется в биткоине; разберем основые функции: MD5, SHA-256, BLAKE2.

Криптографические хеш-функции

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

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

Можно сказать, что хеш сообщения – это криптографически стойкая контрольная сумма.

Хорошая криптографическая функция хеширования обладает следующи­ми свойствами:

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

Зачем нужны хеши сообщений?

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

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

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

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

Хеш-значения как основа HMAC

Хеш-­значения сообщений лежат в основе имитовставок (или кодов аутентичности сообщений) на основе функций хеширования (Hash-based Message Authentication Codes – HMAC). HMAC – это имитовставка (MAC), объединяющая секретный ключ и криптографическую хеш­-функцию с целью аутентификации данных.

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

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

Проверка пароля

В большинстве современных операционных систем и на веб­сайтах пароли не хранятся в открытом виде. Часто вместо пароля хранится его «подсолен­ный» хеш. Слово «подсоленный» означает, что перед хешированием к па­ролю добавлен модификатор – «соль», т.е. небольшой фрагмент случайных данных, длиной, скажем, 2 байта, который дописывается в начало или в ко­нец пароля, из­-за чего одинаковые пароли будут иметь разные хеши и вос­становить пароль по известному хешу будет труднее. Соль сама по себе не является секретом и обычно хранится вместе с хешем. Во время проверки пароль конкатенируется с солью и результат хешируется. Проверка считается успешной, если вычисленное хеш­-значение совпадает с хранимым.

Идентификатор содержимого

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

При верификации сертификата X.509 сертификат издателя ищут по имени и криптографическому хешу открытого ключа.

В современных системах управления исходным кодом, например Git и Mercurial, криптографические хеши ис­пользуются для однозначной идентификации хранимых объектов: файлов, фиксаций, ветвей и тегов. Такая схема идентификации заодно гарантирует целостность репозитория кода.

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

Блокчейн и криптовалюты

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

Доказательство выполнения работы (proof of work)

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

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

Допустим, что почтовый клиент под­ ключается к почтовому серверу и хочет отправить сообщение на один или несколько адресов. Сервер выдает клиенту задачи – по одной для каждого целевого адреса. Если клиент хочет отправить сообщение только на один или на небольшое число адресов, то ему придется выполнить немного вы­числений, что не станет для него большой проблемой. Но если спамер захочет разослать сообщения на миллион адресов, то объем вычислений окажется неподъемным.

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

Оценка стойкости криптографических функций хеширования

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

Уровень стойкости криптографической хеш-­функции – это вычислительная сложность коллизионной атаки. Уровень стойкости изменяется в битах, как и стойкость алгоритмов симметричного шифрования. Например, если для выполнения коллизионной атаки нужно вычислить 2^128 хешей, то ее стойкость равна 128 бит.

Стойкость криптографической функции хеширования зависит от размера вычисляемого ей хеша сообщения. Если размер хеша равен n бит, то макси­мальная сложность атаки будет равна 2n^2 для коллизионной атаки и 2^n для атаки нахождения прообраза.

Например, функция SHA-256 порождает хеши размером 256 бит, поэто­му сложность коллизионной атаки равна 2^128, сложность атаки нахождения прообраза равна 2^256, а уровень стойкости равен 128 бит.

Функции хеширования SHA-1 и SHA-0

Акроним SHA означает Secure Hash Algorithm (стойкий алгоритм хеши­рования).

SHA-1 – криптографическая функция хеширования, разработанная АНБ в 1990­х годах. Спецификация SHA-­1 впервые была опубликована в 1993 году. Однако вскоре после того спецификация была отозвана, потому что в алго­ритме обнаружились дефекты, влияющие на его стойкость. Пересмотренная спецификация SHA-­1 была опубликована в 1995 году, а алгоритм 1993 года получил неофициальное название SHA-­0.

SHA-1 порождает 160­-битовое хеш-­значение. Алгоритм работает быстро – примерно в два раза быстрее SHA-256. Он почти такой же быстрый, как предшествующий ему алгоритм MD5, а на современных процессорах даже быстрее благодаря аппаратному ускорению.

К сожалению, SHA-­1 больше не считается стойким. Изначально было объявлено, что стойкость SHA-­1 равна 80 бит, что по современным стандартам уже небезопасно. А лучшая из известных атак еще и снижает его стойкость до 61 бита.

SHA-­1 был самым популярным криптографическим алгоритмом хеширования до того, как на первое место вышел SHA­-256. Он использовался в протоколах SSL, TLS, SSH и IPsec, сертификатах X.509, реализациях почто­вых систем Pretty Good Privacy (PGP) и Secure Multipurpose Mail Extension (S/MIME), алгоритме цифровой подписи Digital Signature Algorithm (DSA) и других областях.

Семейство функций хеширования SHA-2

Функции из семейства SHA-­2 разработаны Агентством национальной безопасности (АНБ) США и впервые опубликованы Национальным институтом стандартов и технологий (NIST) в 2001 году. В настоящее время функции из семейства SHA-­2 считаются стой­кими.

В семейство SHA-2 входит наиболее популярная на сегодня криптографи­ческая функция хеширования, SHA­-256.

SHA­-256 широко применяется. В настоящее время она используется по умолчанию в протоколе TLS, а также является функцией подписания по умолчанию для сертификатов X.509 и ключей SSH.

В нескольких криптова­лютах, включая биткойн, SHA­-256 применяется для проверки транзакций и доказательства выполнения работы.

Популярная система управления ис­ходным кодом Git переходит на хеши SHA­-256 в своей реализации блокчейна и для идентификации объектов. SHA-­256 используется во многих протоколах и программах, связанных с безопасностью, в т.ч. SSH, IPsec, DNSSEC, PGP и др.

Помимо SHA-­256, в семейство SHA-­2 входят следующие функции хеши­ рования:

• SHA­-224, модификация SHA­-256 с измененным вектором инициализации и усеченным выходом (224 бита).
• SHA­-512 – алгоритм похож на SHA­-256, но оперирует 64-битовыми, а не 32-­битовыми словами.
• SHA-­384, SHA­-512/256 и SHA­-512/224 – модификации SHA­512 с измененными векторами инициализации и усеченным выходом.

SHA­-256 и ее модификации оперируют 32-битовыми словами, а SHA-512 со своими модификациями 64-битовыми словами. Поэтому вычисление SHA-­256 в 2–4 раза быстрее, чем SHA-­512, на 32-­разрядных процессорах, тогда как на 64-­разрядных SHA-­512 работает примерно в 1,5 раза быстрее, чем SHA-­256.

Современные процессоры x86_64 производства Intel и AMD поддерживают расширения Intel SHA, ускоряющие процесс вычисления SHA-­256 и SHA­-1. Некоторые процессоры серии ARMv8, например Cortex A53, поддерживают криптографические расширения ARMv8, которые ускоряют процесс вы­числения SHA­-256 и SHA-­1, а также SHA­224.

Семейство криптографических функций SHA-3

В отличие от разработки SHA-­2 силами одного ведомства, алгоритмы для включения в SHA-3 выбирались по итогам конкурса. Так же в свое время был выбран алгоритм Advanced Encryption Standard (AES). NIST организовал такой конкурс, потому что имелись успешные атаки на предшественников SHA­-2 – алгоритмы SHA-1, SHA-0 и MD5, построенные на тех же принципах, что SHA­2; возникла нужда в функции хеширования, основанной на иных принципах.

Цель SHA­-3 – повысить разно­образие хороших алгоритмов хеширования сообщений и запастить готовой заменой SHA­-2 на случай, если возникнет такая необходимость.

Победителем конкурса SHA-­3 стал алгоритм Keccak, созданный группой бельгийских криптографов. Одним из них был Йоан Даймен, соавтор алго­ритма Rijndael (AES).

Алгоритм SHA-­3 Keccak медленнее SHA­-2, потому что содержит больше последовательных операций. Функция SHA3-­256 примерно в 1,5 раза мед­леннее, чем SHA­-256, а SHA3­-512 – в 2–4 раза медленнее SHA­-512, в зави­ симости от процессора.

Расширения системы команды, такие как расширения Intel SHA и криптографические расширения ARMv8, поддерживают только SHA-­2, но не SHA­-3.

В качестве компенсации замедления SHA-­3 авторы разработали замет­но более быстрые функции SHAKE128 и SHAKE256. Строго говоря, это не функции хеширования, а функции с удлиняемым результатом(Extendable Output Function – XOF). Такие функции могут генерировать хеш-­значения произвольной длины и служить основой для функций хеширования.

Впоследствии те же авторы представили функцию с удлиняемым результатом KangarooTwelve (K12), основанную на Keccak, но с уменьшенным чис­лом раундов (12 вместо 24), которая к тому же может вычисляться параллель­ но на многоядерных процессорах.

Семейство функций хеширования MD

Семейство MD включает четыре функции: MD2, MD4, MD5 и MD6. Функций MD1 и MD3 не существует. Официальной информации о том, куда они де­лись, нет, но ходят слухи, что алгоритм MD1 был патентованным и широкой публике никогда не был доступен, а алгоритм MD3 был экспериментальным, и в конечном итоге автор от него отказался.

Акроним MD означает Message Digest (хеш­значение сообщения). MD5 (равно как SHA-1 и SHA-2) основан на построении Меркла–Дамгора, которое тоже можно сократить до MD.

MD ­функции спроектировал знаменитый криптограф Рональд Ривест, тот самый, что изобрел симметричные шифры RC – RC2, RC4 и RC5.

MD5 – самая известная функция из семейства MD. MD5 предшествует SHA­-1 и разделяет многие математические идеи с SHA­-1 и SHA-­2. MD5 была очень широко распространена, пока ей на смену не пришла SHA­-1.

Интересно, что в протоколах SSL 3.0, TLS 1.0 и TLS 1.1 использовалась комбинация MD5 и SHA-1, потому что трудно найти блок данных, для которого имеет место коллизия MD5 и SHA-1 одновременно.

Семейство функций хеширования BLAKE2

Семейство криптографических функций BLAKE2 разработано международной группой криптографов в 2012 году. Оно основано на потоковом шифре ChaCha.

BLAKE2 включает несколько функций хеширования. Функция BLAKE2s порождает 256-­битовое хеш­-значение, а BLAKE2b – 512-­битовое. Их стойкость к коллизиям до сих пор равна 128 и 256 бит соответственно. Запас стойкости у функций BLAKE2 больше, чем у функций SHA-2, и аналогичен функциям SHA-3.

Функции BLAKE2 известны своим быстродействием. BLAKE2s и BLAKE2b быстрее MD5, SHA-1, SHA-2 и SHA-3 на старых процессорах без аппаратно­го ускорения.

На новых процессорах с аппаратным ускорением, например Intel Skylake или новее, SHA-1 самая быстрая, но BLAKE2s и BLAKE2b все равно быстрее функций из семейства SHA-2, а именно SHA-256 и SHA-512.

У семейства функций BLAKE2 есть последователь: функция BLAKE3, об­народованная в 2020 году. Она поддерживает хеш-­значения произвольного размера, большего или равного 256 битам. BLAKE3 в несколько раз быстрее BLAKE2 и допускает массовое распараллеливание, потому что основана на дереве Меркла.

Другие криптографические хеш-функции

ГОСТ94 – российский стандарт криптографической функции хеширования, с которого гриф секретности был снят в 1994 году. Он основан на блочном шифре ГОСТ89 и порождает 256­-битовое хеш­значение. На смену ГОСТ94 пришла функция хеширова­ния Стрибог, опубликованная в 2012 году и известная также под названием ГОСТ2012, или ГОСТ12.

SM3 – китайская криптографическая функция хеширования, опублико­ванная в 2010 году. С точки зрения структуры и стойкости она похожа на SHA­-256. Ее криптостойкость равна 128 бит. SM3 является национальным стандартом КНР с 2016 года.

Whirlpool – криптографическая функция, основанная на блочном шифре AES. Ее спроектировали Винсент Рэймен (один из соавторов AES) и Пауло Баррето.

RIPEMD-160 – функция хеширования, спроектированная группой бель­гийских криптографов в 1996 году, наиболее популярная из семейства RIPEMD.

MDC-2 – функция хеширования, в которой для порождения 128-­битового хеш-­значения используется симметричный блочный шифр с размером бло­ка 64 бит. MDC­2 означает Modification Detection Code 2 (код обнаружения модификаций 2).

---

Комментарии в Telegram-группе!