~~~~~~~~~~~~~~~~~~~~ Arc.Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~ 
Номер скриншота №:
✰ 1E63F5068A441B84720E556AA0AB8110__1718991960 ✰
Заголовок документа оригинал.:
✰ Rainbow table - Wikipedia ✰
Заголовок документа перевод.:
✰ Радужный стол — Википедия ✰
Снимок документа находящегося по адресу (URL):
✰ https://en.wikipedia.org/wiki/Rainbow_table ✰
Адрес хранения снимка оригинал (URL):
✰ https://arc.ask3.ru/arc/aa/1e/10/1e63f5068a441b84720e556aa0ab8110.html ✰
Адрес хранения снимка перевод (URL):
✰ https://arc.ask3.ru/arc/aa/1e/10/1e63f5068a441b84720e556aa0ab8110__translat.html ✰
Дата и время сохранения документа:
✰ 22.06.2024 10:57:14 (GMT+3, MSK) ✰
Дата и время изменения документа (по данным источника):
✰ 21 June 2024, at 20:46 (UTC). ✰ 

~~~~~~~~~~~~~~~~~~~~~~ Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~~ 
Сервисы Ask3.ru: 
 Архив документов (Снимки документов, в формате HTML, PDF, PNG - подписанные ЭЦП, доказывающие существование документа в момент подписи. Перевод сохраненных документов на русский язык.)https://arc.ask3.ruОтветы на вопросы (Сервис ответов на вопросы, в основном, научной направленности)https://ask3.ru/answer2questionТоварный сопоставитель (Сервис сравнения и выбора товаров) ✰✰
✰ https://ask3.ru/product2collationПартнерыhttps://comrades.ask3.ru


Совет. Чтобы искать на странице, нажмите Ctrl+F или ⌘-F (для MacOS) и введите запрос в поле поиска.
Arc.Ask3.ru: далее начало оригинального документа

Радужный стол — Википедия Jump to content

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

Из Википедии, бесплатной энциклопедии

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

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

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

Предыстория [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблицы Rainbow зависят от хеш-функции, для которой они были созданы, например, таблицы 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 hash , более старом алгоритме хеширования, используемом Microsoft, общедоступны. Хэш LM особенно уязвим, поскольку пароли длиной более 7 символов разбиваются на две части, каждая из которых хэшируется отдельно. Выбор пароля длиной пятнадцать символов и более гарантирует, что LM-хеш не будет сгенерирован. [9]

Общее использование [ править ]

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

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

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

  1. ^ Перейти обратно: а б с Окслин, П. (2003). «Ускорение криптоаналитического компромисса между временем и памятью» (PDF) . Достижения криптологии — КРИПТО 2003 . ЛНКС . Том. 2729. стр. 617–630. дои : 10.1007/978-3-540-45146-4_36 . ISBN  978-3-540-40674-7 .
  2. ^ Перейти обратно: а б Хеллман, М. (1980). «Криптоаналитический компромисс между временем и памятью» (PDF) . Транзакции IEEE по теории информации . 26 (4): 401–406. CiteSeerX   10.1.1.120.2463 . дои : 10.1109/TIT.1980.1056220 . ISSN   0018-9448 . S2CID   552536 .
  3. ^ «LASEC — Лаборатория безопасности и криптографии: доктор Филипп Окслин — Исследования» . Faculté I&C – Школа компьютерных и коммуникационных наук . Март 2004 года.
  4. ^ Перейти обратно: а б Александр, Стивен (июнь 2004 г.). «Защита паролем для современных операционных систем» (PDF) . Авторизоваться . 29 (3). Ассоциация ЮСЕНИКС .
  5. ^ Фергюсон, Нилс; Брюс Шнайер (2003). Практическая криптография . Индианаполис: Джон Уайли и сыновья. ISBN  978-0-471-22357-3 .
  6. ^ Провос, Нильс ; Мазьер, Давид (6 июня 1999 г.). «Схема паролей, адаптируемая к будущему» (PDF) . Материалы программы FREENIX: Ежегодная техническая конференция USENIX 1999 г. Монтерей, Калифорния, США: Ассоциация USENIX.
  7. ^ Манбер, У. (1996). «Простая схема, позволяющая сделать пароли, основанные на односторонних функциях, гораздо труднее взломать» (PDF) . Компьютеры и безопасность . 15 (2): 171–176. CiteSeerX   10.1.1.102.2597 . дои : 10.1016/0167-4048(96)00003-X . Архивировано из оригинала (PDF) 6 мая 2016 г. Проверено 28 августа 2015 г.
  8. ^ Келси, Дж .; Шнайер, Б .; Холл, К.; Вагнер, Д. (1998). «Безопасное применение ключей с низкой энтропией» (PDF) . Информационная безопасность . ЛНКС . Том. 1396. с. 121. дои : 10.1007/BFb0030415 . ISBN  978-3-540-64382-1 .
  9. ^ «Как запретить Windows хранить хэш вашего пароля диспетчера локальной сети в Active Directory и локальных базах данных SAM» . Майкрософт . 24 сентября 2021 г.
  10. ^ «Пример современного использования радужного стола» . Rainbowcrackalack.com . Позитронная безопасность. 26 февраля 2021 г.

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

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец оригинального документа.
Arc.Ask3.Ru
Номер скриншота №: 1E63F5068A441B84720E556AA0AB8110__1718991960
URL1:https://en.wikipedia.org/wiki/Rainbow_table
Заголовок, (Title) документа по адресу, URL1:
Rainbow table - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть, любые претензии не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, денежную единицу можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)