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

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

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

Фон

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

Этимология

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

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

Для цепочек хеширования, отличных от упомянутых здесь, см. цепочка хеширования.

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

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

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

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

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

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

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

С "Kiebgt"является одной из конечных точек в нашей таблице, затем мы берем соответствующий начальный пароль"аааааа"и следуйте его цепочке до достижения 920ECF10:

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

${\displaystyle T=|P|}$

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

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

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

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

saltedhash (пароль) = хеш (пароль + соль)

Или же

saltedhash (пароль) = хеш (хеш (пароль) + соль)

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

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

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

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

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

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

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

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

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

Примечания

1. Охслин, П. (2003). «Сделать более быстрый криптоаналитический компромисс между временем и памятью» (PDF). Достижения в криптологии - CRYPTO 2003. LNCS. 2729. С. 617–630. Дои:10.1007/978-3-540-45146-4_36. ISBN  978-3-540-40674-7.
2. Хеллман, М.Э. (1980). «Криптоаналитический компромисс времени и памяти» (PDF). IEEE Transactions по теории информации. 26 (4): 401–406. CiteSeerX  10.1.1.120.2463. Дои:10.1109 / TIT.1980.1056220.
3. Lasecwww.epfl.ch
4. Александр, Стивен (июнь 2004 г.). «Защита паролем для современных операционных систем» (PDF). Авторизоваться. USENIX Ассоциация. 29 (3).
5. Фергюсон, Нилс; Брюс Шнайер (2003). Практическая криптография. Индианаполис: Джон Уайли и сыновья. ISBN  978-0-471-22357-3.
6. Провос, Нильс; Мазьер, Давид (6 июня 1999 г.). «Схема паролей, адаптируемая к будущему» (PDF). Труды FREENIX Track: Ежегодная техническая конференция USENIX 1999 г.. Монтерей, Калифорния, США: Ассоциация USENIX.
7. Манбер, У. (1996). «Простая схема, позволяющая значительно усложнить взлом паролей на основе односторонних функций» (PDF). Компьютеры и безопасность. 15 (2): 171–176. CiteSeerX  10.1.1.102.2597. Дои:10.1016 / 0167-4048 (96) 00003-X.
8. Келси, Дж.; Шнайер, Б.; Холл, Ц .; Вагнер, Д. (1998). «Безопасные приложения ключей с низкой энтропией» (PDF). Информационная безопасность. LNCS. 1396. п. 121. Дои:10.1007 / BFb0030415. ISBN  978-3-540-64382-1.
9. Как запретить Windows хранить хэш вашего пароля LAN Manager в Active Directory и локальных базах данных SAM, Microsoft

Рекомендации

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

внешняя ссылка

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