Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Фон [ править ]

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

Этимология [ править ]

Иллюстрация Rainbow Table, представленная на Crypto 2003

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

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

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

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

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

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

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

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

Но 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. Это создает новый способ создания ложной тревоги: если мы «угадываем» положение хеш-значения неправильно, мы можем без нужды оценивать цепочку.

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

Пример [ править ]

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

Простая радуга search.svg

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

Таблицы Rainbow специфичны для хэш-функции, для которой они были созданы, например, таблицы MD5 могут взламывать только хеши MD5. Теория этого метода была изобретена Philippe Oechslin [3] в качестве быстрой формы компромиссом времени / памяти , [1] , который он реализован в Windows , взломщик паролей Ophcrack . Позже была разработана более мощная программа RainbowCrack, которая может генерировать и использовать радужные таблицы для различных наборов символов и алгоритмов хеширования, включая LM-хэш , 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-крипт и 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 год использование радужных таблиц сократилось, поскольку соление стало более распространенным, а атаки методом грубой силы на основе графического процессора стали более практичными. Однако таблицы Rainbow доступны для паролей NTLM из восьми и девяти символов . [10]

См. Также [ править ]

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

Примечания [ править ]

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

Ссылки [ править ]

  • Охслин, Филипп (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