Радужная таблица

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

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

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

• 1 Предпосылки
• 2 Этимология
• 3 Предварительно вычисленные цепочки хешей
• 4 Радужные таблицы
  • 4.1 Пример
• 5 Защита от радужных таблиц
• 6 Обычное использование
• 7 См. Также
• 8 Примечания
• 9 Ссылки
• 10 Внешние ссылки

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

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

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

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

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

Термин «Радужные таблицы» был впервые использован в первоначальной статье доктора Охслина. Термин относится к способу использования различных функций сокращения для увеличения вероятности успеха атаки. В оригинальном методе Хеллмана используется множество небольших таблиц с разными функциями редукции. Таблицы 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. Обратите внимание, однако, что функция сокращения на самом деле не является инверсией хэш-функции, а скорее другой функцией с замененным доменом и codomain хеш-функции. Путем чередования хеш-функции с функцией сокращения формируются цепочки чередующихся паролей и хеш-значений. Например, если бы P был набором паролей из 6 букв в нижнем регистре, а значения хеш-функции были длиной 32 бита, цепочка могла бы выглядеть следующим образом:

$aaaaaa\; \to \; H\; 281\; DAF\; 40\; \to \; R\; sgfnyd\; \to \; H\; 920\; ECF\; 10\; \to \; R\; kiebgt\; \{\backslash \; displaystyle\; \{\backslash \; color\; \{Red\}\; \{\backslash \; mathtt\; \{aaaaaa\}\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; H\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{281DAF40\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\; \{\backslash ;\; R\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{sgfnyd\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; H\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{920ECF10\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; R\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; color\; \{Violet\}\; \{\backslash \; mathtt\; \{kiebgt\}\}\}\}$

Единственное требование для функции сокращения - иметь возможность возвращать "простой текст "значение в определенном размере.

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

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

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

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

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

$aaaaaa\; \to \; H\; 281\; DAF\; 40\; \to \; R\; sgfnyd\; \to \; H\; 920\; ECF\; 10\; \{\backslash \; displaystyle\; \{\backslash \; color\; \{Red\}\; \{\backslash \; mathtt\; \{aaaaaa\}\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; H\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{281DAF40\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; R\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{sgfnyd\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; H\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{920ECF10\}\}\}$

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

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

$FB\; 107\; E\; 70\; \to \; R\; bvtdll\; \to \; H\; 0\; EE\; 80890\; \to \; R\; kiebgt\; \{\backslash \; displaystyle\; \{\backslash \; mathtt\; \{FB107E70\}\; \}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; R\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{bvtdll\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; H\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; mathtt\; \{\; 0EE80890\}\}\; \backslash ,\; \{\backslash \; xrightarrow\; [\{\backslash ;\; R\; \backslash ;\}]\; \{\}\}\; \backslash ,\; \{\backslash \; color\; \{Violet\}\; \{\backslash \; mathtt\; \{kiebgt\}\}\}\}$

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

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

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

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

Радужные таблицы эффективно решают проблему коллизий с обычными хеш-цепочками, заменяя единственную функцию сокращения R с последовательностью связанных функций редукции с R 1 по 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) создается цепочка и на каждой итерации сравнивается хэш с целевым хешем. Тест действителен, и мы находим хеш-коды в цепочке. Текущий пароль (культура) - это тот пароль, который создал всю цепочку: атака успешна.

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

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

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

$T\; =\; |\; P\; |\; \{\backslash \; displaystyle\; T\; =\; |\; P\; |\}$

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

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

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

saltedhash (пароль) = hash (пароль + соль)

Или

saltedhash (пароль) = hash (hash (пароль) + salt)

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

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

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

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

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

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

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

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

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