Комментарии 70
Т.е. хэши паролей разработчиков утекали даже в те времена.
длиной пароля максимум 8 символов
ZghOT0eRm4U9s:p/q2-q4!
это как?
Я лично тупил смотря на хеш :)
Сне интересно: почему ни кто еще не посчитал все возможные хеши для crypt(3)?
Если подбор пароля это 4 дня, то за пару месяцев можно сосчитать все возможные комбинации… А если запараллелить...
или запустить в облаке....
Просто повезло получить результат за 4 дня (не было заглавных букв, например).
На самом деле, если посчитать общее количество всех возможных хэшей, то их количество будет весьма циклопическим.
Радужная таблица позволяет «схлопнуть» исходную таблицу в тысячи (сотни тысяч, миллионы) раз. Да, считать перед поиском по таблице придётся, но по сравнению с исходной задачей — расчётов совсем немного потребуется.
Причём а) написана очень давно и б) в английской версии этой странной арифметики нет.
Принцип таблицы очень простой: строится цепочка из N пар пароль-хэш, но сохраняются только «края» — самый первый пароль и самый последний хэш. С учётом того, что N может равняться и миллиону, «степень сжатия» получается довольно большая.
При подборе по этой таблице, правда, перед тем, как искать совпадения по файлу, придётся просчитать все N возможных вариантов (там даже N квадрат получается в итоге). Но посчитать хэш даже миллиард раз — это не 2^8, это сильно быстрее.
Я думаю, как-то так и выводится N^(2/3). При более компактных таблицах, наверное, выходит что поиск занимает дольше, чем прямой перебор.
А во-вторых, от 8-символьного пароля (кстати, кто-нибудь подскажет — у unix'а времён Кена Томпсона в пароле могли быть символы с кодами >= 0x80 ?) мы как-то незаметно переместились к 100500-байтным паролям.
от 8-символьного пароля… мы как-то незаметно переместились к 100500-байтным паролямНе надо этих преувеличений, я рассматривал (для примера!) именно 8-10-байтные а не 8-символьные пароли. Для простоты я подразумевал 8-битные байты. Нет никаких проблем подставить в формулы 6-7-битные байты — получится то же самое, что 6-9-байтные пароли с 8ми-битными байтами.
Мои рассчёты — это оценка сверху, на самом деле радужные таблицы, видимо, ещё менее эффективны, т.к. их размер тоже ограничен из-за коллизий, что я не учитывал.
сам автор (Philippe Oechslin) и приводит оценку
На первой странице он рассказывает о работе Хелмана — там тоже таблица, но из-за особенностей функции редукции у Ошлина получился значительный выигрыш.
Вы сами-то читали
Я, было дело, по основам этой работы софину писал. Табличка для 6-байтового пароля была полсотни гигабайт, считалось за пару минут.
Кажется, спор вышел полезный. Без него Вы бы вряд-ли полезли дальше википедии…
Табличка для 6-байтового пароля была полсотни гигабайтВы же понимаете, что такое нелинейная сложность? Philippe Oechslin пишет, что им потребовалось 13.7 секунд что бы найти в таблице один пароль длинной менее 5 байт!
Кроме того для построения rainbow table нужно примерно в 10 раз больше расчетов чем для однократного прямого перебора. Т.е. окупится только если подбирать более чем 10 паролей.
Скажите, какой по вашему минимальный разумный размер raindow-table, если число перебираемых паролей равно N?
Перечитал википедию. Окей, беру свои слова обратно. Там сравниваются таблица Ошлина и таблица Хеллмана. И радужная таблица выходит на треть компактнее, всё как и описано у автора.
Проблема только в том, что N вместо размера таблицы (как оно описано в википедии) стало количеством возможных паролей (как оно посчитано у вас, с какими-то невообразимыми результатами).
радужная таблица выходит на треть компактнееТам не так написано, не на треть. X^1 и X^(2/3) отличаются не на треть.
Штука в том, что ещё у Хеллмана таблица не содержала все возможные пароли. Конкретно та таблица Хеллмана, что рассматривает Ошлин в примере, в тысячи раз меньше, чем число возможных паролей.
отличаются не на треть
Тьфу, конечно же. Извините.
Вопрос в том, как связан размер таблицы и число паролей, пусть даже угадываемых.
Я имею в виду, что в Хеллман придумал способ "составим цепочку хэш -> пароль -> хэш ->… -> хэш -> пароль, и сохраним первый хэш и последний пароль". Но он использовал только одну функцию редукции (это стрелка "хэш->пароль"). Ошлин через 23 года усовершенствовал этот способ, значительно сократив число коллизий: для каждого шага в цепочке была своя функция редукции. Ну и красивый термин попутно придумал.
Вопрос в том, как связан размер таблицы и число паролей, пусть даже угадываемых.
Размер таблицы (в парах хэш-пароль) = число возможных паролей / длину строки (повторюсь, строка 100000 с нынешними вычислителями — совсем не длинная) * коэффициент избыточности (тут начинается тервер, т.к. 100% гарантии нахождения пароля не получается. Возьмём цифру с потолка 5).
Что-то я иронию плохо улавливаю.
В 2003 году практичной длиной строки было 4666 (пруф см. выше). В 2019 году практичной длиной строки можно считать 100000 (придётся верить мне на слово).
2^password_bit_length/100000*password_bit_length*const, то есть не менее 2^(7byte*8bit/byte)/100000*7byte*2=10TB для 7-байтного пароля, для 8-байтного — 3 PB.Зачем верить Вам на слово
… и следующей же строчкой — данные, которые я же и предоставил. Ну отлично просто.
Ладно. От идеи "схлопнуть N паролей в N^(2/3) записей" мы, кажется, уже окончательно отдалились, и то хорошо.
От идеи «схлопнуть N паролей в N^(2/3) записей» мы, кажется, уже окончательно отдалились, и то хорошо.Мы — это кто? Ошлин как-то от этой оценки в своей статье не спишит отказываться. Я пожалуй с ним соглашусь.
Снова спрошу, какая Ваша оценка? Как связаны размер таблицы, оптимальная длина цепочки и размер пароля? Формулу пожалуйста, откуда она берётся… Предлагаю начать с оптимальной длины цепочки.
Именно для таких случаев люди придумали соленые хэши
сорок тысяч обезьян в ж...
– Значит, вот что… У меня тоже ключ несложный. Но вот какие-то слова тебе могут показаться незнакомыми… если что, так по буквам уточни. И вообще… ты на смысле не фиксируйся.
Чингиз явно настораживается.
– Ну… шутки у меня такие, дурацкие. Сленг, ненормативная лексика… ты парень-то большой…
– Быстрее! – В голосе Темного Дайвера появляется легкая угроза.
– Если что, так потом я тебя к психологу на прием свожу…
– Ты из каких слов ключ составил? – шипит Чингиз.
Падла вздыхает и почему-то понижает голос:
– Короче, слушай… буквы чередуются, первая строчная, вторая прописная, третья строчная и так далее… пробелов нет вообще. Набирай отстраненно…
И он произносит свой ключ.
Секунд десять в библиотеке висит гробовая тишина. Темный Дайвер стоит, застыв как изваяние, и краска заливает его лицо.
Дополню (для тех, кто не найдет на шахматной доске вертикаль "q"): это ход, записанный в старой английской описательной нотации (descriptive notation — она была популярна до 80-х годов в англоязычных странах, но сейчас почти не используется), где вертикали обознаались не буквами по порядку, а названиями фигур, которые в начальном положении на них стоят. Соответственно, Q — значит queen, т.е. королева или же ферзь. То есть, в "нашей" современной нотации (т.н. алгебраической — algebraic notation) ход будет записываться как d2-d4 (либо d7-d5, если это ход черных — "у них" каждый игрок нумеровал горизонтали от себя).
Да, именно так.
P – пешка (pawn)
N или Kt – конь (knight, букв. рыцарь)
B – слон (bishop, букв. епископ)
R – ладья (rook)
Q – ферзь (queen, королева)
K – король (king)
Ферзевой-королевский. KB — вертикаль королевского слона, QB — вертикаль ферзёвого слона и т. п.
Но если было и так понятно, то и не писали. Например, вместо Kt-QB3 (ход белым конем на c3 или черным на c6) пишут Kt-B3, если на KB3 (f3 или f6) конем пойти нельзя. Или еще пример: достаточно написать PxP, если пешку пешкой можно съесть только одним способом, если же нет, то указывали вертикаль одной из пешек по типу BPxP (слоновая пешка ест пешку) или PxKKtP (пешка ест коневую пешку на королевском фланге (т.е. пешку "g")).
Ну это же классика: https://xkcd.com/936/ (и на русском: https://xkcd.ru/936/)
Несколько первых ходов какого-нибудь дебютного варианта:
e4e5Nf3Nc6Bb5
d4d5c4e6Nf3
f4e6g4?Qh4#!
Хотя, строго говоря, все эти пароли можно рассматривать как словарные.
Подам этому кому-то ещё одну идею: используя буквенные обозначения нот, добавить в базу все существующие музыкальные мелодии. Вперёд и с песней :)
Можно стихи длинными аббревиатурами записывать.
Можно химические формулы юзать.
А есть еще топонимы всякие интересные
Тебе снится рыбалка у коралловых рифов,
Неизвестный герой древнегреческих мифов.
Молекулярная физика, энергия атома,
Обнаженная женщина, киллер с лопатой.
Новогодняя елка, орбитальная станция,
Мыльница с музыкой, радио с танцами,
смайл, в общем
Лея женщина, а так перевод интересный
Доправьте текст, там автор местами все ещё мужчина: "… и я поделился своими результатами и разочарованием, что не смог взломать пароль Кена". Нелегко, нелегко даётся нашей индустрии мысль о том, что женщины тоже существуют :)
Потребовалось более четырёх дней на AMD Radeon Vega64 в hashcatСтало на этой видюхе можно любой 8-ми-знак взломать, даже от контроллера домена, не самого последнего уровня, скажем 2016?
Unix-пароль Кена Томпсона