Алгоритм хеширования данных: просто о сложном
Криптографические хэш-функции распространены очень широко. Они используются для хранения паролей при аутентификации, для защиты данных в системах проверки файлов, для обнаружения вредоносного программного обеспечения, для кодирования информации в блокчейне (блок — основной примитив, обрабатываемый Биткойном и Эфириумом). В этой статье пойдет разговор об алгоритмах хеширования: что это, какие типы бывают, какими свойствами обладают.
В наши дни существует много криптографических алгоритмов. Они бывают разные и отличаются по сложности, разрядности, криптографической надежности, особенностям работы. Алгоритмы хеширования — идея не новая. Они появилась более полувека назад, причем за много лет с принципиальной точки зрения мало что изменилось. Но в результате своего развития хеширование данных приобрело много новых свойств, поэтому его применение в сфере информационных технологий стало уже повсеместным.
Что такое хеш (хэш, 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-выхода данных с расчетом на то, что вычислительные мощности атакующих не смогут эффективно вычислять коллизию.
И, несмотря на появление в будущем квантовых компьютеров, специалисты уверены, что правильные инструменты (то же хэширование) способны выдержать испытания временем, ведь ни что не стоит на месте. Дело в том, что с увеличением вычислительных мощностей снижается математическая формализация структуры внутренних алгоритмических хэш-конструкций. А квантовые вычисления наиболее эффективны лишь в отношении к вещам, имеющим строгую математическую структуру.
Понимание хеш-функций и безопасность паролей
Время от времени серверы и базы данных украдены или взломаны. Имея это в виду, важно гарантировать, что некоторые важные пользовательские данные, такие как пароли, не могут быть восстановлены. Сегодня мы собираемся изучить основы хеширования и то, что нужно для защиты паролей в ваших веб-приложениях.
Каждые несколько недель мы пересматриваем некоторые из любимых постов нашего читателя на протяжении всей истории сайта. Этот учебник был впервые опубликован в январе 2011 года.
1 отказ
Криптология — достаточно сложный предмет, и я ни в коем случае не эксперт. В этой области постоянно проводятся исследования, во многих университетах и службах безопасности.
В этой статье я постараюсь сделать все как можно более простым, представляя вам достаточно безопасный способ хранения паролей в веб-приложении.
2 Что делает «хеширование»?
Хеширование преобразует фрагмент данных (маленький или большой) в относительно короткий фрагмент данных, такой как строка или целое число.
Это достигается с помощью односторонней хэш-функции. «Односторонний» означает, что его очень трудно (или практически невозможно) повернуть вспять.
С md5() результатом всегда будет строка длиной 32 символа. Но он содержит только шестнадцатеричные символы; технически это также может быть представлено как 128-битное (16-байтовое) целое число. Вы можете использовать md5() намного длиннее строк и данных, и у вас все равно останется хеш такой длины. Уже один этот факт может дать вам подсказку о том, почему это считается «односторонней» функцией.
3 Использование хэш-функции для хранения паролей
Обычный процесс при регистрации пользователя:
И процесс входа в систему:
Как только мы выберем достойный метод хеширования пароля, мы собираемся реализовать этот процесс позже в этой статье.
Обратите внимание, что оригинальный пароль нигде не был сохранен. Если база данных украдена, логины пользователей не могут быть скомпрометированы, верно? Ну, ответ «это зависит». Давайте посмотрим на некоторые потенциальные проблемы.
4 Проблема № 1: Столкновение хэша
«Столкновение» хэша происходит, когда два разных входа данных генерируют один и тот же результирующий хэш. Вероятность этого зависит от того, какую функцию вы используете.
Как это можно использовать?
В качестве примера я видел несколько старых скриптов, которые использовали crc32 () для хэширования паролей. Эта функция генерирует 32-битное целое в результате. Это означает, что есть только 2 ^ 32 (то есть 4 294 967 296) возможных результатов.
Давайте хешируем пароль:
Теперь давайте примем на себя роль человека, который украл базу данных и имеет хеш-значение. Возможно, нам не удастся преобразовать 323322056 в «supersecretpassword», однако мы можем найти другой пароль, который преобразуется в то же значение хеша, с помощью простого сценария:
Немного о хэшах и безопасном хранении паролей
Upd. Если вы знаете, что такое BCrypt, можете дальше не читать. Если вы используете PHP 5.5+ то можете прочитать эту статью. Ниже же я изобрел свой велосипед, рабочий, но с двумя рулями, задний запасной. Молод был, горяч.
Привет, хабр! Сегодня, в процессе разработки системы аутентификации для своего проекта передо мной встал выбор — в каком виде хранить пароли пользователей в базе данных? В голову приходит множество вариантов. Самые очевидные:
Коллизия хеш-функций
Коллизия хеш-функции возникает, когда она выдает одинаковый результат на разные входные данные. Конечно же, вероятность этого достаточно мала, и зависит от длины хэша. Однако устаревшая (но до сих пор иногда используемая) функция crc32() возвращает в качестве хэша 32-битное целое число. Т.е., чтобы подобрать пароль к такому хэшу, по теории вероятности нужно получить 2^32 = 4 294 967 296 различных хэшей. Даже на моем бесплатном хостинге crc32 работает со скоростью порядка 350 000 раз в секунду — посчитайте сами сколько нужно секунд, чтобы взломать такой хэш 
Конечно же это не относится к md5() (128-битный хеш) и тем более sha1() (160-битный хеш). Использовать их коллизию практически невозможно, хотя есть одна статейка.
Радужные таблицы
Радужные таблицы состоят из хэшей наиболее часто употребляемых паролей — имен, дат рождения, названий животных и т.п. Эти таблицы могут включать миллионы, миллиарды значений, но работа с ними относительно быстра, и проверить хэш на соответствие одному из значений не составляет никакого труда. Частично, от них можно защититься с помощью «соли» или конструкций типа md5(sha1(md5($pass))).
Радужные таблицы. Часть 2
Статическая соль и тому подобные конструкции могут служить достаточно хорошо… пока структура этих конструкций и соль хранятся в тайне. Если же злоумышленник вызнает секрет хэширования — он с легкостью сможет модифицировать под него свою «радужную таблицу». А т.к. мы не можем абсолютно полагаться на систему защиты своего сервера, нужно искать другой вариант. Одним из решений может быть генерация уникальной соли для каждого юзера, что-то вроде:
Еще лучше генерировать совсем случайную соль, например так:
Конечно, уникальную соль придется вносить в базу данных, но даже получив доступ к ней, злоумышленник вряд ли сможет сгенерировать несколько миллионов радужных таблиц.
Скорость хэширования
Казалось бы — чем быстрее, тем лучше. Чем быстрее сгенерируется хэш, тем быстрее наш юзер сможет зарегистрироваться и начать уже приносить профит. Однако чем больше скорость хэширования, тем быстрее его сможет подобрать и хакер.
Современные ПК с мощными GPU, могут рассчитывать миллионы хэшей в секунду и больше. А это позволяет ломать пароли простым подбором, с помощью брутфорса-атак. Считаете что пароль в 8 символов достаточно безопасен? Если в пароле используются символы в нижнем и верхнем регистрах и цифры, то общее количество возможных символов составит 62 (26+26+10). Для пароля длиной в 8 символов, существует 62^8 различных комбинаций (порядка 218 триллионов). Со скоростью в 1 миллиард хэшей в секунду (достаточно маленькая для брутфорс-атаки), пароль будет сломан примерно за 60 часов. А для наиболее распространенной длины пароля в 6 символов, длительность расшифровки составит меньше двух минут.
Можно конечно пренебречь пользователями, использующими короткие и простые пароли, или заставить всех в добровольно-принудительном порядке использовать 10-символьные пароли, со знаками препинания и символами шумерской клинописи. Но лучше использовать более медленные функции хэширования. Например можно замедлить функцию хэша вручную в 1000 раз с помощью следующего кода:
Используя ее, вместо 60 часов, хакер будет ломать 8-символьный пароль около 7 лет. Более удобным вариантом замедления, является использование алгоритма Blowfish, реализованного в PHP через crypt(). Проверить доступность этого алгоритма можно с помощью if (CRYPT_BLOWFISH == 1) echo ‘it works!’; В PHP 5.3 Blowfish уже включен.
$2a — это указание на то, что будет использоваться алгоритм Blowfish
$10 — это сила замедления функции. В данном случае равна 2^10. Может принимать значения от 04 до 31
Используем ее на конкретном примере:
Такой код должен обеспечить максимальную безопасность — подобрать пароль нормальной сложности и длины (программными методами, конечно) практически невозможно.
Зачем нужны хэш функции, и как сохранить пароли в секрете
Время от времени хотим мы этого или нет, но происходят взломы серверов баз данных. Учитывая это, важно быть уверенным в том, что конфиденциальные данные, такие как пароли пользователей, не будут раскрыты. Сегодня, мы осветим тему хэширования и мер по защите паролей в вашем web приложении.
1. Пару слов перед тем, как начнём
Криптология это достаточно сложная тема в которой я далеко не эксперт. По сей день различные университеты и организации по безопасности занимаются исследованиями в этой области.
В этой статье я постараюсь излагаться как можно проще, на тему прочного метода хранения паролей в web-приложениях
2. Зачем нужно «Хэширование»?
Хеширование превращает данные в набор строковых и целочисленных элементов.
Это происходит благодаря одностороннему хэшированию. «Одностороннее» означает, что произвести обратное преобразование ну очень уж сложно или вовсе невозможно.
Самая распространённая хэш функция это md5():
Применяя md5(), вы всегда будете получать в качестве результата строку размером 32 символа. Но эти символы будут в шестнадцатеричном виде; технически хэш может представлять собой и 128-битовое целое. Вы можете помещать в функцию md5() строки и числа любой длины, но на выходе всегда будете получать результат в 32 символа. Уже только этот факт хорошее подтверждение тому, что это «односторонняя» функция.
3. Использование хэш функций для хранения паролей
Обычный процесс регистрации:
Процесс входа в систему:
Процесс хэширования пароля будет изложен далее в этой статье.
Заметьте, что оригинальное значение пароли нигде не сохранялось. Если база данных попадёт к злоумышленникам, то они не смогуть увидеть пароли, так? Да не совсем. Давайте посмотрим на потенциальные «дыры».
4. Проблема #1: Коллизии
“Коллизии” возникают тогда когда при хэшировании двух данных разного типа, получается один и тот же результат. Вообще-то это зависит от того какую функцию вы используете.
Как это можно использовать?
К примеру, я видел несколько устаревшие скрипты, где для хэширования пароля использовалась функция crc32(). Эта функция возвращает в качестве результат 32-битное целое. Это означает, что на выходе может быть только 2^32 (или 4,294,967,296) возможных вариантов.
Давайте захэшируем пароль:
Теперь, давайте поиграем в злодея, который украл базу данных вместе с хэшированным паролем. У нас нет возможности преобразовать 323322056 в ‘supersecretpassword’, однако, благодаря простому скрипту мы можем подобрать другой пароль, который в хэшированном виде будет точно такой же как и тот, который находится в базе:
Этому скрипту конечно нужно время, но в конце концов он вернёт строку. Теперь мы можем использовать строку, которую получили — вместо ‘supersecretpassword’ — что позволит нам зайти в систему от имени пользователя у которого был этот пароль.
Например вот этот скрипт через несколько мгновений возвратил мне строчку ‘MTIxMjY5MTAwNg==‘. Давайте протестируем:
Как это можно предотвратить?
В наши дни, даже на самом простом домашнем компьютере можно использовать миллиарды хэш функций в секунду. Поэтому нам нужна такая хэш функция, которая сгенерировала как можно большее значение.
К примеру можно использовать md5(), которая генерирует 128-битные хэши. Таким образом вариантов подбора становится намного больше 340,282,366,920,938,463,463,374,607,431,768,211,456. Пробег по всем итерациям с целью нахождения коллизии невозможен. Однако некоторым людям всё же удаётся найти «дыры» дополнительно об этом тут).
Sha1() это лучшая альтернатива т.к. она возвращает 160-битный хэш.
5. Проблема #2: Радужная таблица
Даже если мы разобрались с коллизиями, это не значит, что мы обезопасили себя со всех сторон.
Радужная таблица строится путём вычисления хэш-значения наиболее часто используемых слов и словосочетаний.
Такие таблицы могут содержать миллионы, а то и миллиарды строк.
К примеру, для создания такой таблицы можно пройтись по словарю и создать хэш для каждого слова. Так же можно создавать хэши для комбинации слов. Но и это не всё; вы можете так же вставлять цифры перед/после/между слов, и тоже записывать значение таких хэшей в таблицу.
Вот такие огромные Радужные Таблицы могут быть составлены и использованы.
Как это можно использовать:
Давайте представим, что у нас в руках база с десятками тысяч паролей. Особого труда не составит, чтобы сравнить их с значениями из Радужной таблицы. Конечно же не все пароли совпадут, но в конечном итоге парочка другая найдётся!
Как можно себя защитить:
Просто добавим «соли»:
Всё, что нужно сделать, это сконкатенировать “соль” и пароль перед хэшированием. Навряд ли в Радужных таблицах найдётся такое значение. Но мы всё ещё в опасности!
6. Проблема #3: И снова Радужные таблицы
Помните, что Радужные таблицы могут быть сформированы уже после того, как база будет украдена.
Как это можно использовать?
Если вы создали соль, то при краже базы она попадёт в руки злоумышленникам. Всё, что им останется сделать это сгенерировать новую Радужную таблицу с «солями», которые они получили из базы.
К примеру в Радужной таблице есть хэш строки “easypassword”. В новой Радужной таблице вместо прошлого значения у них будет содержаться строка “f#@V)Hu^%Hgfdseasypassword”. Когда они запустят скрипт, то снова могут получить некоторые совпадения.
Как защититься?
Мы можем использовать “уникальную соль” которая будет разной для каждого пользователя.
Дополнением к соли для того, чтоб она стала уникальной может стать id пользователя:
Это само собой подразумевает, что id пользователя никогда не будет меняться.
Так же мы можем сгенерировать случайную строку для каждого отдельного пользователя, чем получим «уникальную соль». Такую соль нужно хранить там же, где находится запись о пользователе.
Этот метод защищает нас от Радужных таблиц, т.к. у каждого пароля есть своя уникальная соль. Атакующему придётся создать 10 миллионов отдельных Радужных таблиц, что на практике невыполнимо.
7. Проблема #4: Скорость выполнения
Большинство функций хэширования разрабатывались, учитывая то, что они часто используются для расчёта контрольных сумм каких-то значений или файлов с проверкой целостности данных.
Как это использовать?
Как я говорил ранее, компьютер с мощной графической картой может высчитывать миллиарды хэшей за секунду. Злоумышленники могут применить «грубую силу», проверяя каждый единственно возможный пароль (проводя полный перебор всех возможных вариантов).
Если вы думаете, что пароль из 8 символов может устоять перед «грубой атакой», то представьте:
Для пароля длиной 6 символов та же самая операция будет длиться более 1 минуты.
Не стесняйтесь требовать от пользователей пароли длиной 9 или 10 символов, хотя это и будет их нервировать.
Как защищаться?
Используйте медленные хэш функции
Представьте себе, что вы используете хэш функцию, которая генерирует 1 миллион хэшей в секунду вместо 1 миллиарда. Атакующему предётся в 1000 раз дольше подбирать пароли. 60 часов превратятся в 7 лет!
Первый вариант самому создать такую функцию:
Или вы можете использовать алгоритм, который использует «cost параметр,» такой как BLOWFISH. В PHP, это может быть реализовано с помощью метода crypt().
Второй параметр в методе crypt() содержит значения, разделённые знаками доллара ($).
Первое значение это ‘$2a’, которое говорит, что мы будем использовать алгоритм BLOWFISH.
Второе значение ‘$10’. В этом случает это «cost параметр». Это параметр представляет собой количество итераций, которые будут производиться (10 => 2^10 = 1024 итераций.) Значение может быть от 04 до 31.
Давайте запустим пример:
В результате у нас получился хэш, который содержит алгоритм ($2a), cost параметр ($10), и соль длиной 22 символа. Всё остальное это хэш. Протестируем:
Если мы это запустим, то получим сообщение «Доступ разрешён!»
8. Собираем всё в кучу
Учитывая всё, что мы узнали, напишем класс:
Применяем при регистрации:
Использование при входе пользователя в систему:
9. Проверка на возможность использования Blowfish
Алгоритм Blowfish может и не быть реализован на всех системах, хоть и очень популярен. Проверка на возможность использования:
Однако, начиная с PHP 5.3, этот алгоритм встроен по умолчанию.
Заключение
Этого метода хэширования вполне достаточно для большинства web-приложений. Так же не забывайте: что вы в праве требовать минимальную длину пароля от своих пользователей. Вы так же можете перемешивать символы, цифры и специальные знаки.
Вопрос к вам: как вы хэшируете ваши пароли? Что думаете по поводу методов в данной статье?
5 последних уроков рубрики «PHP»
Фильтрация данных с помощью zend-filter
Когда речь идёт о безопасности веб-сайта, то фраза «фильтруйте всё, экранируйте всё» всегда будет актуальна. Сегодня поговорим о фильтрации данных.
Контекстное экранирование с помощью zend-escaper
Обеспечение безопасности веб-сайта — это не только защита от SQL инъекций, но и протекция от межсайтового скриптинга (XSS), межсайтовой подделки запросов (CSRF) и от других видов атак. В частности, вам нужно очень осторожно подходить к формированию HTML, CSS и JavaScript кода.
Подключение Zend модулей к Expressive
Expressive 2 поддерживает возможность подключения других ZF компонент по специальной схеме. Не всем нравится данное решение. В этой статье мы расскажем как улучшили процесс подключение нескольких модулей.
Совет: отправка информации в Google Analytics через API
Предположим, что вам необходимо отправить какую-то информацию в Google Analytics из серверного скрипта. Как это сделать. Ответ в этой заметке.
Подборка PHP песочниц
Подборка из нескольких видов PHP песочниц. На некоторых вы в режиме online сможете потестить свой код, но есть так же решения, которые можно внедрить на свой сайт.