Что такое радужные таблицы?

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

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

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

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

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

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

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

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

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

1. Один и тот же вход всегда генерирует одно и то же хэш-значение, и это единственный способ, при котором значение может функционировать как контрольная сумма. Идентичен ли введенный пароль тому, что сохранен в базе данных? Система может предоставить доступ только в том случае, если оба хэш-значения одинаковы.
2. Хеш-значение всегда должно быть уникальным, поэтому разные записи не могут генерировать одно и то же хеш-значение. Только таким образом функция может убедиться, что был введен правильный пароль. Поскольку количество возможных хэш-значений ограничено, а количество возможных записей — нет, такие коллизии нельзя исключить. Современные хэш-функции и хэши достаточной длины максимально снижают риск.
3. Хеш-значения не могут быть пересчитаны: оригинальное содержимое никогда не может быть получено из самого хеш-значения. Именно поэтому хэш-значения нельзя расшифровать, как это иногда туманно утверждается. Вместо этого хэш-значения можно только постичь.
4. Хэш-функции должны быть относительно сложными — но не слишком: для обеспечения безопасности алгоритм не может работать слишком быстро, поскольку это также облегчит работу злоумышленникам. Преобразование также не должно быть слишком сложным, поскольку его все равно придется применять на практике.

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

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

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

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

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

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

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

Сокращения необходимо проводить по порядку: если предположить, что цепочка была построена с помощью сокращений R₁, R₂и R₃тогда вы начнете поиск с функции R₃. Если это не принесет результатов, то начните с R₂ а затем перейдите к R₃и так далее. Внутри таблицы различные функции редукции могут быть обозначены цветами, что приводит к разноцветной радуге с соответствующим количеством итераций — и, соответственно, названием.

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

Объяснение: Введенный пароль — k. В данном случае m — это любой множитель (в данном примере 2000). Обычно для A задается величина золотого сечения (0,618). Modulo (mod) извлекает остаток от деления, выполненного в данном случае на 1. Гауссовы скобки округляют результат до целого числа в конце, если это необходимо. Результат h(k) — это хэш-значение h для входа k.

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

Поскольку наше хэш-значение состоит из четырех цифр, мы заполняем начало цифрой 0: 0408.

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

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

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

Теперь не все хэш-значения доступны в таблице. Если бы, например, вы знали, что за хэш-значением 1888 стоит пароль, вы бы сейчас поискали в созданной радужной таблице и обнаружили, что это значение не отображается в таблице, а скрыто в цепочке. Теперь вам нужно уменьшить значение, в результате чего получается 88. Это значение также не является частью таблицы, поэтому вы пересчитаете хэш-значение (0768) и уменьшение (68). Соответствующее хэш-значение 0048 находится в третьей строке. Но пароль в той же строке (03) не относится непосредственно к хэш-значению, так что это только начало цепочки.

Однако он является хорошей отправной точкой для следующего вычисления: из 03 можно вычислить хэш-значение 1708. Это уменьшает 08 и строит новое хэш-значение: 1888 — целевое хэш-значение. Таким образом, пароль 08 принадлежит этому значению.

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

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

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

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

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

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

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

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

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

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