Радужная таблица — это предварительно вычисленная таблица для кэширования выходных данных криптографической хэш-функции , обычно для взлома хэшей паролей. Пароли обычно хранятся не в виде обычного текста, а в виде хэш-значений. Если такая база данных хэшированных паролей попадает в руки злоумышленников, они могут использовать предварительно вычисленную радужную таблицу для восстановления текстовых паролей. Распространенной защитой от этой атаки является вычисление хэшей с использованием функции деривации ключа , которая добавляет « соль » к каждому паролю перед его хэшированием, при этом разные пароли получают разные соли, которые хранятся в виде обычного текста вместе с хешем.
Радужные таблицы являются практическим примером компромисса между пространством и временем : они используют меньше времени обработки компьютера и больше памяти, чем атака методом перебора , которая вычисляет хэш при каждой попытке, но требуют больше времени обработки и меньше памяти, чем простая таблица, которая хранит хэш каждого возможного пароля.
Радужные таблицы были изобретены Филиппом Охслином [1] как применение более раннего, более простого алгоритма Мартина Хеллмана . [2]
Для аутентификации пользователя пароли хранятся либо в виде открытого текста , либо в виде хэшей . Поскольку пароли, хранящиеся в виде открытого текста, легко украсть, если доступ к базе данных будет скомпрометирован, базы данных обычно хранят вместо этого хэши. Таким образом, никто — включая систему аутентификации — не может узнать пароль, просто посмотрев на значение, хранящееся в базе данных.
Когда пользователь вводит пароль для аутентификации, для него вычисляется хэш, который затем сравнивается с сохраненным хешем для этого пользователя. Аутентификация не проходит, если два хеша не совпадают; более того, аутентификация также не пройдет, если в качестве пароля будет введено хэшированное значение, поскольку система аутентификации хэширует его второй раз.
Узнать пароль из хеша — значит найти строку, которая при вводе в хеш-функцию создаст тот же хеш. Это то же самое, что инвертировать хеш-функцию.
Хотя атаки методом грубой силы (например, атаки по словарю ) могут использоваться для попытки инвертировать хэш-функцию, они могут стать неосуществимыми, когда набор возможных паролей достаточно велик. Альтернативой методу грубой силы является использование предварительно вычисленных таблиц цепочек хэшей. Радужные таблицы — это особый вид таких таблиц, которые преодолевают определенные технические трудности.
Термин «радужные таблицы» впервые был использован в первоначальной статье Охслина. Этот термин относится к способу использования различных функций редукции для повышения успешности атаки. Оригинальный метод Хеллмана использует много маленьких таблиц с различной функцией редукции каждая. Радужные таблицы намного больше и используют различную функцию редукции в каждом столбце. Когда для представления функций редукции используются цвета, в радужной таблице появляется радуга. Рисунок 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. Однако следует отметить, что функция сокращения на самом деле не является обратной функцией хэш-функции, а скорее другой функцией с переставленными доменом и кодоменом хэш-функции. Чередуя хэш-функцию с функцией редукции, формируются цепочки чередующихся паролей и хэш-значений. Например, если бы P было набором строчных буквенных 6-символьных паролей, а хэш-значения были бы длиной 32 бита, цепочка могла бы выглядеть следующим образом:
Единственное требование к функции редукции — возможность возвращать значение «обычного текста» определенного размера.
Для генерации таблицы мы выбираем случайный набор начальных паролей из P, вычисляем цепочки некоторой фиксированной длины k для каждой из них и сохраняем только первый и последний пароль в каждой цепочке. Первый пароль называется начальной точкой , а последний — конечной точкой . В приведенном выше примере цепочки «aaaaaa» будет начальной точкой, а «kiebgt» — конечной точкой, и ни один из других паролей (или хэш-значений) не будет сохранен.
Теперь, имея хэш-значение h для инвертирования (нахождения соответствующего пароля), вычислите цепочку, начинающуюся с h , применяя R, затем H, затем R и т. д. Если в какой-либо точке значение соответствует одной из конечных точек в таблице, соответствующая начальная точка позволяет воссоздать полную цепочку. Существует высокая вероятность того, что эта цепочка будет содержать значение h , и если это так, то непосредственно предшествующее значение в цепочке — это пароль p , который мы ищем.
Например, если задан хэш 920ECF10 , его цепочку можно вычислить, сначала применив R:
Поскольку « kiebgt » является одной из конечных точек в нашей таблице, соответствующий начальный пароль « aaaaaa » позволяет следовать по его цепочке до тех пор, пока не будет достигнуто значение 920ECF10 :
Таким образом, пароль — « sgfnyd » (или другой пароль с тем же значением хэша).
Однако следует отметить, что эта цепочка не всегда содержит хэш-значение h ; может случиться так, что цепочка, начинающаяся с h , сольется с цепочкой, имеющей другую начальную точку. Например, цепочка хэш-значения FB107E70 , также приводит к kiebgt :
Затем выполняется цепочка, сгенерированная соответствующим начальным паролем " aaaaaa ", пока не будет достигнуто значение FB107E70 . Поиск завершится без достижения значения FB107E70 , поскольку это значение не содержится в цепочке. Это называется ложной тревогой . В этом случае совпадение игнорируется, а цепочка h расширяется в поисках другого совпадения. Если цепочка h расширяется до длины k без подходящих совпадений, то пароль не был создан ни в одной из цепочек.
Содержимое таблицы не зависит от инвертируемого хэш-значения. Оно создается один раз и затем многократно используется для поиска без изменений. Увеличение длины цепочки уменьшает размер таблицы. Однако это также увеличивает время, необходимое для выполнения поиска, и это компромисс между временем и памятью радужной таблицы. В простом случае цепочек из одного элемента поиск выполняется очень быстро, но таблица становится очень большой. Как только цепочки становятся длиннее, поиск замедляется, но размер таблицы уменьшается.
Простые хеш-цепочки имеют несколько недостатков. Наиболее серьезный, если в какой-либо точке две цепочки сталкиваются (создают одно и то же значение), они сольются, и, следовательно, таблица не будет охватывать столько же паролей, несмотря на то, что были заплачены те же вычислительные затраты на генерацию. Поскольку предыдущие цепочки не хранятся полностью, это невозможно эффективно обнаружить. Например, если третье значение в цепочке 3 совпадает со вторым значением в цепочке 7, две цепочки будут охватывать почти ту же последовательность значений, но их конечные значения не будут одинаковыми. Хэш-функция H вряд ли будет создавать коллизии, поскольку обычно считается важной функцией безопасности не делать этого, но функция сокращения R, из-за ее необходимости правильно охватывать вероятные открытые тексты, не может быть устойчивой к коллизиям .
Другие трудности вытекают из важности выбора правильной функции для R. Выбор R в качестве идентичности немного лучше, чем подход грубой силы. Только когда у злоумышленника есть хорошее представление о вероятных открытых текстах, он сможет выбрать функцию R, которая гарантирует, что время и пространство используются только для вероятных открытых текстов, а не для всего пространства возможных паролей. По сути, R направляет результаты предыдущих вычислений хэша обратно в вероятные открытые тексты, но это преимущество сопряжено с недостатком, что R, скорее всего, не произведет все возможные открытые тексты в классе, который злоумышленник хочет проверить, что лишит злоумышленника уверенности в том, что никакие пароли не пришли из выбранного им класса. Также может быть сложно разработать функцию R, которая соответствовала бы ожидаемому распределению открытых текстов. [2]
Радужные таблицы эффективно решают проблему коллизий с обычными хеш-цепочками, заменяя одну функцию сокращения R последовательностью связанных функций сокращения R 1 через R k . Таким образом, для того, чтобы две цепочки столкнулись и слились, они должны достичь одного и того же значения на одной и той же итерации : следовательно, конечные значения в этих цепочках будут идентичны. Последний проход постобработки может отсортировать цепочки в таблице и удалить любые «дубликаты» цепочек, которые имеют те же конечные значения, что и другие цепочки. Затем генерируются новые цепочки для заполнения таблицы. Эти цепочки не являются бесколлизионными (они могут на короткое время перекрываться), но они не будут сливаться, что радикально сокращает общее количество коллизий. [ необходима цитата ]
Использование последовательностей функций редукции изменяет способ выполнения поиска: поскольку интересующее нас хэш-значение может быть найдено в любом месте цепочки, необходимо сгенерировать k различных цепочек. Первая цепочка предполагает, что хэш-значение находится в последней позиции хэша, и просто применяет R k ; следующая цепочка предполагает, что хэш-значение находится в предпоследней позиции хэша, и применяет R k −1 , затем H, затем R k ; и так далее до последней цепочки, которая применяет все функции редукции, чередуясь с H. Это создает новый способ создания ложной тревоги: неправильное «предположение» о позиции хэш-значения может напрасно оценить цепочку.
Хотя радужные таблицы должны следовать большему количеству цепочек, они компенсируют это меньшим количеством таблиц: простые таблицы цепочек хэшей не могут вырасти больше определенного размера, не становясь быстро неэффективными из-за слияния цепочек; чтобы справиться с этим, они поддерживают несколько таблиц, и каждый поиск должен искать по каждой таблице. Радужные таблицы могут достичь аналогичной производительности с таблицами, которые в k раз больше, что позволяет им выполнять в k раз меньше поисков.
Радужные таблицы используют усовершенствованный алгоритм с другой функцией сокращения для каждой «ссылки» в цепочке, так что при возникновении коллизии хэшей в двух или более цепочках цепи не будут объединяться до тех пор, пока коллизия не произойдет в одной и той же позиции в каждой цепочке. Это увеличивает вероятность правильного взлома для заданного размера таблицы за счет возведения в квадрат количества шагов, необходимых для поиска, поскольку процедура поиска теперь также должна проходить по индексу первой функции сокращения, используемой в цепочке. [1]
Радужные таблицы специфичны для хэш-функции, для которой они были созданы, например, таблицы MD5 могут взламывать только хэши MD5. Теория этого метода была изобретена Филиппом Охслином [3] как быстрая форма компромисса времени/памяти , [1] которую он реализовал в взломщике паролей Windows Ophcrack . Позднее была разработана более мощная программа RainbowCrack , которая может генерировать и использовать радужные таблицы для различных наборов символов и алгоритмов хэширования, включая LM hash , MD5 и SHA-1 .
В простом случае, когда функция редукции и хеш-функция не имеют коллизий, при наличии полной радужной таблицы (той, которая гарантирует нахождение соответствующего пароля по любому хешу) размер набора паролей | P |, время T , которое потребовалось для вычисления таблицы, длина таблицы L и среднее время t, необходимое для нахождения пароля, соответствующего данному хешу, напрямую связаны: [ необходима цитата ]
Таким образом, пароль из 8 строчных букв и цифр (| P | ≃ 3×10 12 ) будет легко обрабатываться на персональном компьютере, в то время как пароль из 16 строчных букв и цифр (| P | ≃ 10 25 ) будет совершенно не поддаваться обработке.
Радужная таблица неэффективна против односторонних хэшей, которые включают большие соли . Например, рассмотрим хэш пароля, который генерируется с помощью следующей функции (где " + " — оператор конкатенации ):
saltedhash(password) = hash(password + salt)
Или
saltedhash(password) = hash(hash(password) + salt)
Значение соли не является секретным и может быть сгенерировано случайным образом и сохранено вместе с хэшем пароля. Большое значение соли предотвращает атаки с предварительным вычислением, включая радужные таблицы, гарантируя, что пароль каждого пользователя хэшируется уникально. Это означает, что два пользователя с одним и тем же паролем будут иметь разные хэши паролей (при условии использования разных солей). Чтобы добиться успеха, злоумышленнику необходимо предварительно вычислить таблицы для каждого возможного значения соли. Соль должна быть достаточно большой, в противном случае злоумышленник может создать таблицу для каждого значения соли. Для старых паролей Unix , которые использовали 12-битную соль, это потребовало бы 4096 таблиц, что значительно увеличивает стоимость для злоумышленника, но не непрактично с терабайтными жесткими дисками. Методы SHA2-crypt и bcrypt , используемые в Linux , BSD Unix и Solaris , имеют соли размером 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 Manager и NT LAN Manager (основанный на MD4 ), а также не содержит соли, что делает его одной из самых популярных генерируемых таблиц. Радужные таблицы стали реже использоваться с 2020 года, поскольку соление стало более распространенным, а атаки методом подбора на основе графических процессоров стали более практичными. Однако радужные таблицы доступны для восьми- и девятисимвольных паролей NTLM . [10]
![{\displaystyle {\color {Красный}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Фиолетовый}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/609e4ea6eac3f25b5982f3c9c6ccdaead642540d)
![{\displaystyle {\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Фиолетовый}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5d0f08a2a5598244e082b88810425f16b660270)
![{\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{ \;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96219a92ee1b95f41144e0498463f884939d996a)
![{\displaystyle {\mathtt {FB107E70}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {0EE80890}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Фиолетовый}{\mathtt {kiebgt}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91cb90a3ee395b1ffaea3e25ae60d03cf331ba5c)
