Радужный стол - Rainbow table

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

Радужные таблицы были изобретены Филиппом Окслином как приложение более раннего, более простого алгоритма Мартина Хеллмана .

Фон

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

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

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

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

Этимология

Термин «радужные таблицы» впервые был использован в первоначальной статье доктора Охслина. Этот термин относится к способу использования различных функций сокращения для увеличения вероятности успеха атаки. В оригинальном методе Хеллмана используется множество небольших таблиц с разными функциями редукции. Таблицы Rainbow намного больше и используют разные функции сокращения в каждом столбце. Когда для представления функций редукции используются цвета, в радужной таблице появляется радуга. Рисунок 2 статьи доктора Охслина содержит черно-белое изображение, иллюстрирующее взаимосвязь этих разделов. В своей презентации на конференции Crypto 2003 доктор Охслин добавил цвет к графике, чтобы сделать ассоциацию радуги более ясной. Улучшенная графика, представленная на конференции, показана справа.

Предварительно вычисленные хеш-цепочки

Предположим, у нас есть хэш-функция паролей H и конечный набор паролей P. Цель состоит в том, чтобы предварительно вычислить структуру данных, которая при любом выходе h хеш-функции может либо найти элемент p в P, что H ( p ) = h , или определить, что такого p нет в P. Самый простой способ сделать это - вычислить H ( p ) для всех p в P, но тогда для сохранения таблицы требуется Θ (| P | n ) бит пространства, где | P | - размер набора P, а n - размер вывода H, что недопустимо для больших | P |. Хеш-цепочки - это способ уменьшить это требование к пространству. Идея заключается в том , чтобы определить сокращение функции R , которая отображает значения хэш обратно в значения в Р. Отметим, однако, что функция подавления не на самом деле обратная хэш - функции, а другая функция с выгружена домена и кообласть из хеш-функция. Путем чередования хеш-функции с функцией сокращения формируются цепочки чередующихся паролей и хеш-значений. Например, если бы P был набором паролей из 6 букв в нижнем регистре и хеш-значений длиной 32 бита, цепочка могла бы выглядеть следующим образом:

${\ displaystyle {\ color {Red} {\ mathtt {aaaaaa}}} \, {\ xrightarrow [{\; H \;}] {}} \, {\ mathtt {281DAF40}} \, {\ xrightarrow [{ \; R \;}] {}} \, {\ mathtt {sgfnyd}} \, {\ xrightarrow [{\; H \;}] {}} \, {\ mathtt {920ECF10}} \, {\ xrightarrow [{\; R \;}] {}} \, {\ color {Фиолетовый} {\ mathtt {kiebgt}}}}$

Единственное требование к функции сокращения - это возможность возвращать значение «обычного текста» определенного размера.

Чтобы сгенерировать таблицу, мы выбираем случайный набор начальных паролей из P, вычисляем цепочки некоторой фиксированной длины k для каждого из них и сохраняем только первый и последний пароль в каждой цепочке. Первый пароль называется начальной точкой, а последний - конечной точкой . В приведенном выше примере цепочки «aaaaaa» будет начальной точкой, а «kiebgt» будет конечной точкой, и ни один из других паролей (или хеш-значений) не будет сохранен.

Теперь, имея хэш-значение h, которое мы хотим инвертировать (найти соответствующий пароль), вычислим цепочку, начинающуюся с h , применив R, затем H, затем R и так далее. Если в какой-то момент мы наблюдаем значение, соответствующее одной из конечных точек в таблице, мы получаем соответствующую начальную точку и используем ее для воссоздания цепочки. Есть большая вероятность, что эта цепочка будет содержать значение h , и если да, то непосредственно предшествующее значение в цепочке - это пароль p, который мы ищем.

Например, если нам дан хэш 920ECF10 , мы вычислим его цепочку, сначала применив R:

${\ displaystyle {\ mathtt {920ECF10}} \, {\ xrightarrow [{\; R \;}] {}} \, {\ color {Violet} {\ mathtt {kiebgt}}}}$

Поскольку « kiebgt » является одной из конечных точек в нашей таблице, мы затем берем соответствующий начальный пароль « aaaaaa » и следуем по его цепочке, пока не будет достигнут 920ECF10:

${\ displaystyle {\ color {Red} {\ mathtt {aaaaaa}}} \, {\ xrightarrow [{\; H \;}] {}} \, {\ mathtt {281DAF40}} \, {\ xrightarrow [{ \; R \;}] {}} \, {\ mathtt {sgfnyd}} \, {\ xrightarrow [{\; H \;}] {}} \, {\ mathtt {920ECF10}}}$

Таким образом, пароль - « sgfnyd » (или другой пароль с таким же хеш-значением).

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

${\ displaystyle {\ mathtt {FB107E70}} \, {\ xrightarrow [{\; R \;}] {}} \, {\ mathtt {bvtdll}} \, {\ xrightarrow [{\; H \;}] {}} \, {\ mathtt {0EE80890}} \, {\ xrightarrow [{\; R \;}] {}} \, {\ color {Violet} {\ mathtt {kiebgt}}}}$

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

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

Простые цепочки хеширования имеют несколько недостатков. Наиболее серьезно, если в какой-то момент две цепочки сталкиваются (производят одно и то же значение), они объединяются, и, следовательно, таблица не будет охватывать столько паролей, несмотря на то, что для генерации были заплачены одинаковые вычислительные затраты. Поскольку предыдущие цепочки не хранятся полностью, это невозможно эффективно обнаружить. Например, если третье значение в цепочке 3 совпадает со вторым значением в цепочке 7, две цепочки будут охватывать почти одинаковую последовательность значений, но их окончательные значения не будут одинаковыми. Маловероятно, что хеш-функция H вызовет коллизии, поскольку ее игнорирование обычно считается важной функцией безопасности, но функция сокращения R из-за ее необходимости правильно покрывать вероятные открытые тексты не может быть устойчивой к коллизиям .

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

Радужные столы

Радужные таблицы эффективно решают проблему коллизий с обычными цепочками хеширования, заменяя единственную функцию редукции R последовательностью связанных функций редукции с R ₁ по R _k . Таким образом, чтобы две цепочки столкнулись и слились, они должны получить одно и то же значение на одной итерации : следовательно, окончательные значения в этой цепочке будут идентичны. Заключительный проход постобработки может отсортировать цепочки в таблице и удалить любые «повторяющиеся» цепочки, которые имеют такие же конечные значения, как и другие цепочки. Затем создаются новые цепочки для заполнения таблицы. Эти цепочки не свободны от коллизий (они могут ненадолго перекрываться), но они не будут сливаться, что резко снижает общее количество коллизий.

Использование последовательностей функций редукции меняет способ выполнения поиска: поскольку интересующее хеш-значение может быть найдено в любом месте цепочки, необходимо сгенерировать k различных цепочек. Первая цепочка предполагает, что хеш-значение находится в последней хеш-позиции, и просто применяет R _k ; следующая цепочка предполагает, что значение хеш-функции находится в предпоследней позиции хеш-функции, и применяет R _{k -1} , затем H, затем R _k ; и так далее до последней цепочки, которая применяет все функции сокращения, чередующиеся с H. Это создает новый способ создания ложной тревоги: если мы «угадываем» положение хеш-значения неправильно, мы можем без нужды оценивать цепочку.

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

Пример

1. Начиная с хэша («re3xes») на изображении ниже, вычисляется последнее сокращение, использованное в таблице, и проверяется, отображается ли пароль в последнем столбце таблицы (шаг 1).
2. Если тест не проходит ( rambo не отображается в таблице), вычисляется цепочка с двумя последними редукциями (эти два сокращения представлены на шаге 2).

   Примечание. Если этот новый тест снова не проходит, выполняется 3 сокращения, 4 сокращения и т. Д., Пока не будет найден пароль. Если ни одна цепочка не содержит пароля, атака не удалась.

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

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

Таблицы Rainbow специфичны для хэш-функции, для которой они были созданы, например, таблицы MD5 могут взламывать только хеши MD5. Теория этой техники была изобретена Филиппом Окслином как быстрая форма компромисса между временем и памятью , которую он реализовал в программе для взлома паролей Windows Ophcrack . Позже была разработана более мощная программа RainbowCrack, которая может генерировать и использовать радужные таблицы для различных наборов символов и алгоритмов хеширования, включая LM-хэш , MD5 и SHA-1 .

В простом случае, когда функция сокращения и хеш-функция не конфликтуют, учитывая полную радужную таблицу (та, которая гарантирует, что вы найдете соответствующий пароль с любым хешем), размер набора паролей | P |, время T, которое потребовалось для вычисления таблицы, длина таблицы L и среднее время t, необходимое для поиска пароля, соответствующего заданному хешу, напрямую связаны:

${\ Displaystyle T = | P |}$

${\ displaystyle t = {\ frac {| P |} {2L}}}$

Таким образом, 8-значный регистр буквенно-цифровых паролей в нижнем регистре (| P | ≃ 3 × 10 ¹² ) будет легко обрабатываться с помощью персонального компьютера, в то время как регистр 16-значных буквенно-цифровых паролей в нижнем регистре (| P | ≃ 10 ²⁵ ) будет совершенно неразрешим.

Защита от радужных таблиц

Радужная таблица неэффективна против односторонних хешей, содержащих большие соли . Например, рассмотрим хэш пароля, который создается с помощью следующей функции (где « + » - оператор конкатенации ):

saltedhash(password) = hash(password + salt)

Или

saltedhash(password) = hash(hash(password) + salt)

Значение соли не является секретным и может быть сгенерировано случайным образом и сохранено с хешем пароля. Большое значение соли предотвращает атаки перед вычислением, в том числе радужные таблицы, путем обеспечения уникального хеширования пароля каждого пользователя. Это означает, что два пользователя с одним и тем же паролем будут иметь разные хэши паролей (при условии, что используются разные соли). Чтобы добиться успеха, злоумышленник должен предварительно вычислить таблицы для каждого возможного значения соли. Соль должна быть достаточно большой, иначе злоумышленник может составить таблицу для каждого значения соли. Для старых паролей Unix, которые использовали 12-битную соль, это потребовало бы 4096 таблиц, что значительно увеличило бы стоимость для злоумышленника, но не непрактично с терабайтными жесткими дисками. SHA2-крипт и Bcrypt методы , используемые в- Linux , BSD Unixes и Solaris -Иметь соли 128 бит. Эти большие значения соли делают атаки с предварительным вычислением на эти системы невозможными практически для любой длины пароля. Даже если бы злоумышленник мог генерировать миллион таблиц в секунду, ему все равно потребовались бы миллиарды лет, чтобы сгенерировать таблицы для всех возможных солей.

Еще один метод, который помогает предотвратить атаки с предварительным вычислением, - это растягивание ключа . Когда используется растяжение, соль, пароль и некоторые промежуточные хеш-значения проходят через базовую хеш-функцию несколько раз, чтобы увеличить время вычислений, необходимое для хеширования каждого пароля. Например, MD5-Crypt использует цикл из 1000 итераций, который многократно передает соль, пароль и текущее промежуточное значение хеш-функции обратно в базовую хеш-функцию MD5. Хэш пароля пользователя - это объединение значения соли (которое не является секретным) и окончательного хеша. Дополнительное время незаметно для пользователей, потому что им приходится ждать лишь доли секунды каждый раз, когда они входят в систему. С другой стороны, растяжение снижает эффективность атак грубой силы пропорционально количеству итераций, поскольку оно уменьшает количество попыток, которые злоумышленник может выполнить за определенный период времени. Этот принцип применяется в MD5-Crypt и в bcrypt. Это также значительно увеличивает время, необходимое для построения предварительно вычисленной таблицы, но в отсутствие соли это нужно сделать только один раз.

Альтернативный подход, называемый усилением ключа , расширяет ключ случайной солью, но затем (в отличие от растяжения ключа) надежно удаляет соль. Это вынуждает как злоумышленника, так и законных пользователей выполнить поиск солевого значения методом перебора. Хотя в статье, в которой описывалось растяжение клавиш, упоминалась эта более ранняя техника и было намеренно выбрано другое название, термин «усиление клавиш» теперь часто (возможно, неправильно) используется для обозначения растяжения клавиш.

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

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

Общее использование

Почти все дистрибутивы и варианты Unix , Linux и BSD используют хеши с солью, хотя многие приложения используют только хеш (обычно MD5 ) без соли. Семейство Microsoft Windows NT / 2000 использует методы хеширования LAN Manager и NT LAN Manager (на основе MD4 ) и также не содержит соли, что делает их одной из наиболее часто генерируемых таблиц. С 2020 года использование радужных таблиц сократилось, так как соление стало более распространенным, а атаки методом грубой силы на основе графического процессора стали более практичными. Однако таблицы Rainbow доступны для паролей NTLM из восьми и девяти символов .

Смотрите также

• A5 / 1
• Атака грубой силой
• DistrRTgen
• Алгоритм кенгуру Полларда

Примечания

использованная литература

• Охслин, Филипп (17 августа 2003 г.). «Делая более быстрый криптоаналитический компромисс времени и памяти». Сделать более быстрый криптоаналитический компромисс между временем и памятью (PDF) . Достижения в криптологии: материалы 23-й ежегодной международной конференции по криптологии CRYPTO 2003 . Конспект лекций по информатике. 2729 . Санта-Барбара, Калифорния , США: Спрингер. С. 617–630. DOI : 10.1007 / 978-3-540-45146-4_36 . ISBN 978-3-540-40674-7.

внешние ссылки

• Страница Ophcrack от Филиппа Окслина Оригинальное исследование радужной таблицы
• Криптография в Curlie