Какие алгоритмы имеют обратное преобразование хеширование
Привет, друг. Мы с тобой уже рассмотрели немало тем в области работы сетей в целом, и информационной безопасности в частности. И очень часто в своих материалах я упоминал такие слова как криптография, шифрование, алгоритмы шифрования, хэши, ну и всякие словечки наподобие. И, вроде бы, в контексте эти слова были уместны и понятны. Но, я тут подумал, что, на самом деле мало кто понимает, что именно означают эти термины. А уж раскрыть концепцию и принципы работы всего этого — вообще смогут единицы.
И для начинающего, либо для любителя, это вполне нормально. А вот когда люди, считающие себя серьёзными хацкерами, либо анонимусами, с пеной у рта доказывают, что какой-то алгоритм уязвим и пользоваться им нельзя, при этом не могут даже приблизительно сформулировать что такое криптография, алгоритм шифрования, в чём суть уязвимости, а главное уязвимости к чему. Это вызывает снисходительную улыбку. Но ты ведь не хочешь таким быть, правда? Поэтому я решил кратко и, по возможности, понятно рассказать что такое криптография в целом, и шифрование в частности. Я постараюсь не углубляться в теоретические глубины. Потому что криптография бездонна, а сосредоточусь на практической части вопроса. Больше внимания посвящая именно алгоритмам шифрования.
Безопасное использование MD5
MD5 – до сих пор является одним из самых распространенных способов защитить информацию в сфере прикладных исследований, а также в области разработки веб-приложений. Хеш необходимо обезопасить от всевозможных хакерских атак.
Криптография и алгоритмы шифрования
И тут, человеки, как им свойственно, проявили немалую изобретательность. И понавыдумывали столько, что если захочешь во всём этом разобраться, то пару институтов придется закончить. Но мы не в институте. Да и нам не зачем в эти глубины вникать, а потому разберем основное.
В криптографии существует довольно много видов классификаций алгоритмов шифрования. Но, что бы не забивать себе голову, наиболее приемлемо выделить три основных вида:
- симметричное
- асимметричное
- хеширование
Прежде чем говорить о них по отдельности, давай определимся что самое важное в алгоритмах шифрования. И, ты наверняка подумал, что это надежность защиты данных, и это почти правильный ответ. Причем многие теоретики криптографии тоже отдают надежности первой место. А вот те кто на практике сталкиваются с шифрованием, знают, что надёжность конечно важна, но гораздо важнее соотношение надёжности и возможности использования шифра.
Что бы было понятней почему, поясню подробней. То что в народе называют надёжностью, в криптография называет криптостойкостью шифра. Другими словами это свойство шифра противостоять криптоанализу т.е. дешифрованию. А самих способов дешифррования существует ровно два — простой перебор и расшифровка на основе перехваченных данных.
И если с перебором всё более-менее понятно. Т.е. нужно подставлять, по очереди все возможные варианты. И соответственно чем больше вариантов существует тем более надёжен этот шифр. То с расшифровкой на основе перехваченных данных всё намного сложнее. При этом оба варианта вполне можно применять к одному и тому же шифру.
Абсолютно стойкие шифры
И возникает логичный вопрос. Если существуют абсолютно стойкие системы, то почему бы их не использовать? И проблема защиты информации будет решена. Но не тут-то было. Потому что абсолютно стойкие системы существуют только на бумаге. В виде теорем и прочей теоретической тошниловки. А использовать их на практике невозможно, в виду нереальной сложности и огромной стоимости шифрующего оборудования. Чтобы было понятней, даже государства, которые, казалось бы, обладают огромными ресурсами, не смогли до сих пор внедрить использование абсолютно стойких систем. Из этого всего, вполне логичным, будет вывод, что чем надежнее шифр тем труднее и дороже его использование в практических целях. А соответственно наиболее важна не надежность шифра, а возможность его применения. Т.е. соотношение надежности и цены.
Хеш-функции, основанные на делении
Первый метод заключается в том, что мы используем в качестве хеша остаток от деления на , где - это количество всех возможных хешей:
При этом очевидно, что при чётном значение функции будет чётным, при чётном , и нечётным — при нечётном, что может привести к значительному смещению данных в файлах. Также не следует использовать в качестве степень основания счисления компьютера, так как хеш-код будет зависеть только от нескольких цифр числа , расположенных справа, что приведет к большому количеству коллизий. На практике обычно выбирают простое — в большинстве случаев этот выбор вполне удовлетворителен.
Ещё следует сказать о методе хеширования, основанном на делении на полином по модулю два. В данном методе также должна являться степенью двойки, а бинарные ключи (k_. k_" />
) представляются в виде полиномов. В этом случае в качестве хеш-кода берутся значения коэффциентов полинома, полученного как остаток от деления на заранее выбранный полином степени :
При правильном выборе такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами. [3]
Криптография. Надёжность шифра
Это термины которыми обозначаются вероятности появления или не появления в тексте каких-либо символов. Но мы не будем углубляться в высшую математику и выводить формулы. Потому что нам это просто не нужно. А нужно понимать что значение взаимной информации всегда больше либо равно нулю. И исходя из этого получается, что если это значение равно нулю, то алгоритм можно считать абсолютно стойкими. Потому что сколько частей крептотекста не попало бы к злодею — расшифровать всё равно ничего не получиться. А если значение взаимной информации больше нуля, такие системы принято называть достаточно стойкими.
Хеширование
И третий, интересующий нас вид шифрования, это хеширование. Его ещё называют хеш-функция или функция свёртки. Это одностороннее шифрование. При котором, с использованием алгоритма хеширования, начальные данные, независимо от их длины, превращаются в битовую строку фиксированной длины. Именно эта битовая строка и называется хешем. Идеальным считается такой алгоритм хеширования, который делает невозможным обратное преобразование хеша в данные. Т.е. имея на руках хеш — невозможно узнать начальные данные.
При этом, для применения на практике, как раз начальные данные знать и не нужно. Нужно знать, что с использованием определенного алгоритма генерация хэша от какого-то текста создает тот же хэш. Соответственно, мы можем хранить например пароль, в виде хеша. И даже если его украдут — узнать пароль не смогут. А когда пользователь вводит пароль то хеш введенного пароля сверяется с сохраненным хешем, и если они совпали — значит пароль правильный. По такому же принципу может проверяться целостность файлов.
Самая главная проблема хеш-функций называется коллизией. Суть её в том что хеши не всегда уникальны. И иногда, правда очень редко, случаются ситуации, что два разных входных блока дают одинаковый хеш. Именно поэтому основной уязвимостью алгоритмов хеширования считается построение коллизий т.е. их искусственное создание. Для примера именно подобную уязвимость эксплуатировал червь Stuxnet в Windows. Он получал от системы абсолютно белый сертификат, таким способом становясь неуязвимым для антивирусов.
Примеры алгоритмов хеширования: MD4, MD5, SHA1, SHA2.
Ну, а на этом нашу ознакомительную экскурсию в мир криптографии можно считать оконченной. Теперь у тебя есть базовое понимание что такое криптография и алгоритмы шифрования. Но не забывай возвращаться, нам нужно узнать ещё очень много.
В Интернете опубликовано много полезных материалов, объясняющих различие методов преобразования информации, но интерес читателей к подобным темам не снижается. Рассмотрим термины шифрование, хеширование и кодирование данных на понятном пользовательском уровне.
Информационная энтропия
Энтропия
Надежность и сложность пароля в сфере информационных технологий обычно измеряется в терминах теории информации. Чем выше информационная энтропия, тем надежнее пароль и, следовательно, тем труднее его взломать.
Чем длиннее пароль и чем больше набор символов, из которого он получен, тем он надежнее. Правда вместо количества попыток, которые необходимо предпринять для угадывания пароля, принято вычислять логарифм по основанию 2 от этого числа, и полученное значение называется количеством «битов энтропии» в пароле. При увеличении длины пароля на один бит количество возможных паролей удвоится, что сделает задачу атакующего в два раза сложнее. В среднем, атакующий должен будет проверить половину из всех возможных паролей до того, как найдет правильный. В качестве наилучшей практики должно выполняться предварительное требование: приложение настаивает на том, чтобы пользователь использовал надежный пароль в процессе регистрации.
Кодирование данных
Код - это система условных обозначений или сигналов.
Кодирование данных - это представление информации системой условных обозначений отличной от той, в которой информация исходно представлена.
Самым простым примером кодирования данных является текст. Кодирование может производиться рукописным или машинописным способом на определённом языке речи. Далее можно произвести перекодирование текста документа способом перевода его на другой язык.
Кодированием является написание программы для ЭВМ или перевод программы на другой язык программирования.
Элементами кодируемой информации могут быть:
- буквы, слова и фразы естественного языка;
- различные символы (знаки препинания, арифметические и логические операции и др.);
- числа;
- аудиовизуальные образы;
- ситуации и явления;
- генетическая информация;
- и другие элементы.
Кодовые обозначения могут представлять собой буквы, числа, графические обозначения, электромагнитные импульсы, световые и звуковые сигналы, набор и сочетание химических молекул, и другое.
Кроме языка речи и программирования известными кодовыми системами являются: азбука Морзе , код Бодо , компьютерная кодировка символов ASCII и Unicodе , шрифты, системы штрих-кодов и др.
Системой кодов можно назвать распространённые устойчивые традиции, обряды, танцевальные системы, принятые в разных народностях.
Дополнительные материалы по теме этой статьи:
24 августа 2019 года.
автор: юрист Демешин Сергей Владимирович.
Участвуйте в обсуждении , пройдите опрос об интересных темах будущих публикаций (ссылка опроса в описании канала, также в описании указаны правила комментирования публикаций).
Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определенным алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Результат преобразования называется хешем.
Хеш-функции применяются в следующих случаях:
При поиске дубликатов в последовательностях наборов данных.
При построении уникальных идентификаторов для наборов данных.
При вычислении контрольных сумм от данных для последующего обнаружения в них ошибок, возникающих при хранении и передаче данных.
При сохранении паролей в системах защиты в виде хеш-кода (для восстановления пароля по хеш-коду требуется функция, являющаяся обратной по отношению к использованной хеш-функции).
С точки зрения математики, контрольная сумма является результатом хеш-функции, используемой для вычисления контрольного кода — небольшого количества бит внутри большого блока данных, например, сетевого пакета или блока компьютерного файла, применяемого для обнаружения ошибок при передаче или хранении информации. Значение контрольной суммы добавляется в конец блока данных непосредственно перед началом передачи или записи данных на какой-либо носитель информации. Впоследствии оно проверяется для подтверждения целостности данных. Популярность использования контрольных сумм для проверки целостности данных обусловлена тем, что подобная проверка просто реализуема в двоичном цифровом оборудовании, легко анализируется и хорошо подходит для обнаружения общих ошибок, вызванных наличием шума в каналах передачи данных.
Асимметричное шифрование
Асимметричное шифрование или шифрование с открытым ключом. В подобных системах используется два ключа — открытый и закрытый, математически связанные между собой. При этом открытый ключ не от кого не прячется. Может передаваться не защищенными каналами связи. И используется для шифрования данных и проверки электронной цифровой подписи.
А вот для генерации цифровой подписи и расшифровки данных используется закрытый т.е. секретный ключ. Простыми словами это работает так. Если мы хотим получить от кого-то некую секретную информацию, мы передаём ему открытый ключ, с использованием которого эта информация будет зашифрована. При этом мы не боимся что злодеи перехватят наш ключ. Ведь с ним можно только зашифровать данные, но не расшифровать.
Наиболее распространённые асимметричные алгоритмы шифрования:
Заключение
К сожалению, выяснилось, что алгоритм MD5 не способен отвечать данным требованиям. IETF (Internet Engineering Task Force) рекомендовала новым проектам протоколов не использовать MD5, так как исследовательские атаки предоставили достаточные основания для исключения использования алгоритма в приложениях, которым требуется устойчивость к различного рода коллизиям.
Хеши MD5 больше не считаются безопасными, и их не рекомендовано использовать для криптографической аутентификации.
Как я полагаю, многим известно о том, что с 2007 года Национальный институт стандартов и технологий США (NIST) проводит конкурс на разработку хэш-алгоритма для замены SHA-1, и семейства алгоритмов SHA-2. Однако данная тема, почему-то обделена вниманием на сайте. Собственно это и привело меня к вам. Предлагаю вашему вниманию цикл статей, посвященных хэш-алгоритмам. В этом цикле мы вместе изучим основы хэш-функций, рассмотрим самые именитые хэш-алгоритмы, окунемся в атмосферу конкурса SHA-3 и рассмотрим алгоритмы, претендующие на победу в нем, обязательно их потестируем. Так же по возможности будут рассмотрены российские стандарты хеширования.
О себе
Студент кафедры информационной безопасности.
О хэшировании
Здесь v — некоторая константа, часто ее называют инициализирующим вектором. Она выбирается
из различных соображений и может представлять собой секретную константу или набор случайных данных (выборку даты и времени, например).
При таком подходе свойства хэш-функции полностью определяются свойствами одношаговой сжимающей функции.
О статистических свойствах и требованиях
Как я уже говорил основным требованием к хэш-функциям является равномерность распределения их значений при случайном выборе значений аргумента. Для криптографических хеш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось. Это называется лавинным эффектом.
К ключевым функциям хэширования предъявляются следующие требования:
— невозможность фабрикации,
— невозможность модификации.
К бесключевым функциям предъявляют требования:
— однонаправленность,
— устойчивость к коллизиям,
— устойчивость к нахождению второго прообраза.
Это была теоретическая часть, которая пригодится нам в дальнейшем…
О популярных хэш-алгоритмах
Алгоритмы CRC16/32 — контрольная сумма (не криптографическое преобразование).
Алгоритмы MD2/4/5/6. Являются творением Рона Райвеста, одного из авторов алгоритма RSA.
Алгоритм MD5 имел некогда большую популярность, но первые предпосылки взлома появились еще в конце девяностых, и сейчас его популярность стремительно падает.
Алгоритм MD6 — очень интересный с конструктивной точки зрения алгоритм. Он выдвигался на конкурс SHA-3, но, к сожалению, авторы не успели довести его до кондиции, и в списке кандидатов, прошедших во второй раунд этот алгоритм отсутствует.
Алгоритмы линейки SHA Широко распространенные сейчас алгоритмы. Идет активный переход от SHA-1 к стандартам версии SHA-2. SHA-2 — собирательное название алгоритмов SHA224, SHA256, SHA384 и SHA512. SHA224 и SHA384 являются по сути аналогами SHA256 и SHA512 соответственно, только после расчета свертки часть информации в ней отбрасывается. Использовать их стоит лишь для обеспечения совместимости с оборудованием старых моделей.
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше , чем вариантов входного массива; существует множество массивов с разным содержимым, но дающих одинаковые хеш-коды — так называемые коллизии . Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
Существует множество алгоритмов хеширования с различными свойствами (разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.
Плюсы и минусы симметричного шифрования
Самыми главными плюсами симметричного шифрования является его скорость и простота реализации. За счёт этого оно хорошо подходит для хранения и обработки больших объёмов данных. На этом, собственно, плюсы — всё. Что касается минусов. Самая главная его проблема — это обмен ключами. Ведь у каждого участника должен быть один и тот же ключ. А его нужно как-то передать, по какому-то каналу связи. А это означает ровно одно — этот ключ можно перехватить. Соответственно даже самый лучший алгоритм надёжен ровно настолько на сколько надёжен канал передачи ключей. Кстати, из-за того что ключ известен каждой стороне, использование симметричного шифрования делает невозможным подтверждение аутентичности и авторства данных. Т.к. невозможно сформировать цифровую подпись.
Универсальное хеширование
Универсальным хешированием (англ. Universal hashing ) называется хеширование, при котором используется не одна конкретная хеш-функция, а происходит выбор из заданного семейства по случайному алгоритму. Использование универсального хеширования обычно обеспечивает низкое число коллизий. Универсальное хеширование имеет множество применений, например, в реализации хеш-таблиц и криптографии.
Описание
Предположим, что мы хотим отобразить ключи из пространства в числа . На входе алгоритм получает некоторый набор данных и размерностью , причем неизвестный заранее. Как правило целью хеширования является получение наименьшего числа коллизий, чего трудно добиться используя какую-то определенную хеш-функцию.
.
Хеширование строк переменной длины
Вышеизложенные методы применимы и в том случае, если нам необходимо рассматривать ключи, состоящие из нескольких слов или ключи переменной длины. Например можно скомбинировать слова в одно при помощи сложения по модулю или операции «исключающее или». Одним из алгоритмов, работающих по такому принципу является хеш-функция Пирсона.
Алгоритм можно описать следующим псевдокодом, который получает на вход строку и использует таблицу перестановок
Среди преимуществ алгоритма следует отметить:
- Простоту вычисления;
- Не существует таких входных данных, для которых вероятность коллизии наибольшая;
- Возможность модификации в идеальную хеш-функцию.
В качестве альтернативного способа хеширования ключей, состоящих из символов (x_. x_" />
), можно предложить вычисление
Шифрование данных
Шифрование - обратимое преобразование информации в целях сокрытия сведений от несанкционированного круга лиц.
Шифрование происходит на основе алгоритмов, известных передающей и принимающей сторонам. Процесс преобразования открытой информации в закрытый вид называется шифрование . Обратный процесс преобразования закрытой (зашифрованной) информации в открытый вид называется дешифрование .
Взламывание шифра с получением алгоритма шифрования и ключа шифрования (при наличии) называется криптоанализ .
Алгоритм шифрования может использовать ключ шифрования или обходиться без него. Ключи шифрования бывают открытыми и закрытыми .
Шифрование применяется для реализации средств криптографической защиты информации ( СКЗИ ) - средства защиты хранимой информации и средства защиты передаваемой информации.
Узнать подробнее о криптографии можно в ответах Яндекс.Знатоки по вопросу " Что такое криптография? "
Симметричное шифрование
В свою очередь, само симметричное шифрование можно разделить на два подвида. Это блочные и поточные шифры.
Мультипликативная схема хеширования
Второй метод состоит в выборе некоторой целой константы , взаимно простой с , где — количество представимых машинным словом значений (в компьютерах IBM PC " />
). Тогда можем взять хеш-функцию вида:
В этом случае, на компьютере с двоичной системой счисления, является степенью двойки и будет состоять из старших битов правой половины произведения .
Среди преимуществ этих двух методов стоит отметь, что они выгодно используют то, что реальные ключи неслучайны, например в том случае если ключи представляют собой арифметическую прогрессию (допустим последовательность имён «ИМЯ1», «ИМЯ2», «ИМЯ3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшает количество коллизий по сравнению со случайной ситуацией. [3]
Одной из вариаций данного метода является хеширование Фибоначчи, основанное на свойствах золотого сечения. В качестве здесь выбирается ближайшее к *w" />
целое число, взаимно простое с
Блочные и поточные шифры
Блочный шифр — информация шифруется блоками данных фиксированного размера. Как правило это степени 2 (64, 128 и т.д.). К каждому блоку ключ применяется в несколько раундов подстановки и перемешивания. Таким образом достигается увеличение несоответствия битов между блоками начальных и зашифрованных данных. Именно так работают большинство современных алгоритмов шифрования. Используя, для перемешивания и подстановки сеть Фейстеля или SP-сеть.
Поточный шифр — принцип работы тот же самый, что и у блочного. Только на шифруемый текст предварительно накладывается последовательность случайных чисел и информация шифруется не блоками, а побитово. Этот процесс, кстати, называется гаммированием. Так вот, если блочный шифр запустить в режиме гаммирования — получится потоковый. Правда если перегнуть с этой последовательностью случайных чисел — получишь абсолютно стойкий шифр — круто, но бесполезно.
Примеры наиболее распространённых симметричных шифров:
Хеширование данных
Криптографическая хеш-функция ( хеш ) - это математический алгоритм, преобразовывающий произвольный массив данных в состоящую из букв и цифр строку фиксированной длины.
Это определение означает, что с помощью алгоритма хеширования можно получить фиксированную строку цифр и букв, преобразовав текст произвольной длины. Полученный хеш можно хранить в качестве контрольного значения для проверки целостности преобразованных данных: если данные изменятся, то при повторном преобразовании их в хеш одинаковым алгоритмом получится другое значение.
Известными алгоритмами хеширования являются MD5, SHA-1 и SHA-2.
Основные принципы хеширования :
- при хешировании одинаковых данных получается одинаковое значение хеша (хеш-кода);
- разные данные преобразуются в разные хеш-коды (хеш-суммы);
- криптостойкость хеш-функции заключается в стойкости к восстановлению хешируемых данных и стойкости к коллизиям преобразования.
Одним из самых простых применений хеширования является хранение паролей (считается более защищённым способом, чем хранение паролей в явном виде).
С помощью хеширования в можно контролировать в различных сервисах распространение медиафайлов, сравнивая их хеш-коды, можно отслеживать целостность хранимых и передаваемых данных или детектировать защитным ПО вредоносные программы.
RainbowCrack
Это ещё один метод взлома хеша. Он основан на генерировании большого количества хешей из набора символов, чтобы по получившейся базе вести поиск заданного хеша.
Радужные таблицы состоят из хеш-цепочек и более эффективны, чем предыдущий упомянутый тип атак, поскольку они оптимизируют требования к хранению, хотя поиск выполняется немного медленнее. Радужные таблицы отличаются от хеш-таблиц тем, что они создаются с использованием как хеш-функций, так и функций редукции.
Цепочки хешей — метод для уменьшения требования к объёму памяти. Главная идея — определение функции редукции R, которая сопоставляет значениям хеша значения из таблицы. Стоит отметить, что R не является обращением хеш-функции.
Радужные таблицы являются развитием идеи таблицы хеш-цепочек. Функции редукции применяются по очереди, перемежаясь с функцией хеширования.
Использование последовательностей функций редукции изменяет способ поиска по таблице. Поскольку хеш может быть найден в любом месте цепочки, необходимо сгенерировать несколько различных цепочек.
Существует множество систем взлома паролей и веб-сайтов, которые используют подобные таблицы. Основная идея данного метода — достижение компромисса между временем поиска по таблице и занимаемой памятью. Конечно, использование радужных таблиц не гарантирует 100% успеха взлома систем паролей. Но чем больше набор символов, используемый для создания радужной таблицы, и чем продолжительнее хеш-цепочки, тем больше будет шансов получить доступ к базе данных исходных паролей.
Виды хеш-функций
Хорошая хеш-функция должна удовлетворять двум свойствам:
- Быстро вычисляться;
- Минимизировать количество коллизий
Предположим, для определённости, что количество ключей , а хеш-функция имеет не более различных значений:
В качестве примера «плохой» хеш-функции можно привести функцию с , которая десятизначному натуральном числу сопоставляет три цифры выбранные из середины двадцатизначного квадрата числа . Казалось бы значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа. [3]
Однако существует несколько более простых и надежных методов, на которых базируются многие хеш-функции.
Атаки переборного типа
Перебор по словарю — атака на систему защиты, применяющая метод полного перебора предполагаемых паролей, используемых для аутентификации, осуществляемого путём последовательного пересмотра всех слов (паролей в чистом виде) определённого вида и длины из словаря с целью последующего взлома системы и получения доступа к секретной информации.
Как видно из определения, атаки по словарю являются атаками полного перебора. Единственное отличие состоит в том, что данные атаки обычно более эффективны так как становится не нужным перебирать все комбинации символов, чтобы добиться успеха. Злоумышленники используют обширные списки наиболее часто используемых паролей таких как, имена домашних животных, вымышленных персонажей или конкретно характерных слов из словаря – отсюда и название атаки. Однако если пароль действительно уникален (не является комбинацией слов), атака по словарю не сработает. В этом случае использование атаки полного перебора единственный вариант.
Для полного перебора или перебора по словарю можно использовать программы PasswordsPro, MD5BFCPF, John the Ripper. Для перебора по словарю существуют готовые словари.
Добавление “соли” к паролю
Одна из наиболее распространенных причин успешных атак заключается в том, что компании не используют добавление соли к исходному паролю. Это значительно облегчает хакерам взлом системы с помощью атак типа радужных таблиц, особенно учитывая тот факт, что многие пользователи используют очень распространенные, простые пароли, имеющие одинаковые хеши.
Сольэто вторичный фрагмент информации, состоящий из строки символов, которые добавляются к открытому тексту (исходному паролю пользователя), а затем хешируется. Соление делает пароли более устойчивыми к атакам типа радужных таблиц, так как подобный пароль будет иметь более высокую информационную энтропию и, следовательно, менее вероятное существование в предварительно вычисленных радужных таблицах. Как правило, соль должна быть не менее 48 бит.
Криптография
Начнём, как и положено с начала. А в начале всего стоит криптография — это такая наука, причём очень древняя и очень сложная. Исторически сложилось, что основной целью криптографии можно выделить обеспечение конфиденциальности. Т.е. защиты информации от посторонних личностей. И эта цель не менее актуальна и сейчас. Но с развитием информационных технологий, а соответственно с развитием криптографии, начали появляться новые, но не менее важные цели этой науки. Например, к наиболее популярным можно отнести: аутентификацию. Т.е. проверку неизменности ключевых свойств объект (например авторство, дата создания, история изменений и т.д.) и целостность данных. Т.е. невозможность незаметного или не санкционированного изменения информации.
Развивалась криптография, развивались и методы, применяемые этой наукой для достижения результата. Если когда-то, давным-давно, достаточно было использовать алфавитный, а чуть позже цифровой шифр, и чем он был замудрённей тем и надёжней, потому что разгадывать его приходилось в ручную. То с появлением компьютеров, а соответственно серьёзных вычислительных мощностей, эти самые шифры канули в лету. Ввиду их абсолютной уязвимости к анализу и перебору для выявления закономерностей, а соответственно разгадыванию секретного ключа т.е. самого шифра. Этот процесс, кстати, принято называть криптоанализом.
Но кому-то очень умному пришло в голову использовать вычислительные мощности не только для разгадывания ключа, но и для самого шифрования. Именно так начали появляться алгоритмы шифрования в том понимании, в котором их знают сейчас.
Идеальное хеширование
Идеальной хеш-функцией (англ. Perfect hash function ) называется такая функция, которая отображает каждый ключ из набора в множество целых чисел без коллизий. В математических терминах это инъективное отображение.
Описание
Идеальное хеширование применяется в тех случаях, когда мы хотим присвоить уникальный идентификатор ключу, без сохранения какой-либо информации о ключе. Одним из наиболее очевидных примеров использования идеального (или скорее k-идеального) хеширования является ситуация, когда мы располагаем небольшой быстрой памятью, где размещаем значения хешей, связанных с данными хранящимися в большой, но медленной памяти. Причем размер блока можно выбрать таким, что необходимые нам данные, хранящиеся в медленной памяти, будут получены за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, в тех случаях, когда представление графа не умещается в основной памяти.
Уязвимости MD5
Перебор по словарю
При этом методы перебора по словарю и brute-force могут использоваться для взлома хеша других хеш-функций (с небольшими изменениями алгоритма). RainbowCrack требует предварительной подготовки радужных таблиц, которые создаются для заранее определённой хеш-функции. Поиск коллизий специфичен для каждого алгоритма. Рассмотрим каждый вид «взлома» по отдельности.
Плюсы и минусы асимметричного шифрования
При всех очевидных плюсах в системах с открытым ключом есть и минусы. И самый главный — это скорость. Асимметричное шифрование в несколько раз медленнее симметричного. Ну и, соответственно, вычислительные мощности нужны в разы больше. В связи с этими минусами, на практике обычно применяются гибридные системы шифрования. Они аккумулируют плюсы обоих систем. Т.е. массив данных шифруется симметричным алгоритмом, а сеансовый ключ шифруется асимметричным и передаётся в зашифрованном виде. Таким способом экономятся вычислительные мощности и появляется возможность безопасно передать ключ симметричного алгоритма.
Декодирование кода MD5
Иногда при работе с компьютером или поврежденными базами данных требуется декодировать зашифрованное с помощью MD5 значение хеша.
Удобнее всего использовать специализированные ресурсы, предоставляющие возможность сделать это online:
md5.web-max.ca данный сервис обладает простым и понятным интерфейсом. Для получения декодированного значения нужно ввести хеш и заполнить поле проверочной капчи;
Если присмотреться к значениям декодинга, то становится понятно, что процесс расшифровки почти не дает результатов. Эти ресурсы представляют собой одну или несколько объединенных между собой баз данных, в которые занесены расшифровки самых простых слов.
При этом данные декодирования хеша MD5 даже такой распространенной части пароля, как «админ», нашлись лишь в одной базе. Поэтому хеши паролей, состоящих из более сложных и длинных комбинаций символов, практически невозможно расшифровать.
Создание хеша MD5 является односторонним процессом. Поэтому не подразумевает обратного декодирования первоначального значения.
Как работает протокол?
Утилита md5sum, предназначенная для хеширования данных заданного файла по алгоритму MD5, возвращает строку. Она состоит из 32 цифр в шестнадцатеричной системе счисления (016f8e458c8f89ef75fa7a78265a0025).
То есть хеш, полученный от функции, работа которой основана на этом алгоритме, выдает строку в 16 байт (128) бит. И эта строка включает в себя 16 шестнадцатеричных чисел. При этом изменение хотя бы одного ее символа приведет к последующему бесповоротному изменению значений всех остальных битов строки.
В данном алгоритме предполагается наличие 5 шагов, а именно:
Вычисление в цикле
На втором шаге в оставшиеся 64 бита дописывают 64-битное представление длины данных до выравнивания. Сначала записывают младшие 4 байта. Если длина превосходит то дописывают только младшие биты. После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.
На третьем для вычислений используются четыре переменные размером 32 бита и задаются начальные значения в 16-ричном виде. В этих переменных будут храниться результаты промежуточных вычислений.
В итоге на 5-ом шаге мы получим результат вычислений, который находится в буфере это и есть хеш. Если выводить побайтово, начиная с младшего байта первой переменной и закончив старшим байтом последней, то мы получим MD5-хеш.
Коллизии MD5
MD5 был тщательно изучен криптографическим сообществом с момента его первоначального выпуска и до 2004 года демонстрировал лишь незначительные недостатки. Однако летом 2004 года криптографы Ван Сяоюнь и Фэн Дэнго продемонстрировали алгоритм способный генерировать MD5-коллизии с использованием стандартного вектора инициализации.
История
Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну (нем. Hans Peter Luhn ), предложившему хеш-кодирование в январе 1953 года.
В 1956 году Арнольд Думи (англ. Arnold Dumey ) в своей работе «Computers and automation» первым представил концепцию хеширования таковой, какой её знает большинство программистов сейчас. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число. [1]
Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона (англ. W. Wesley Peterson ) в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz ), в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.
В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ. Robert Morris ) опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».
До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Ершова использовалось слово «расстановка», а для коллизий использовался термин "конфликт" (Ершов использовал «расстановку» с 1956 года, в русскоязычном издании книги Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка»). Предлагалось также назвать метод русским словом «окрошка». Однако ни один из этих вариантов не прижился, и в русскоязычной литературе используется преимущественно термин «хеширование». [3]
Читайте также: