Unix-пароль Кена Томпсона

Автор оригинала: Leah Neukirchen
  • Перевод
Где-то в 2014 году в дампах исходного дерева BSD 3 я нашла файл /etc/passwd с паролями всех ветеранов, таких как Деннис Ричи, Кен Томпсон, Брайан В. Керниган, Стив Борн и Билл Джой.

Для этих хэшей использовался алгоритм crypt(3) на основе DES — известный своей слабостью (и с длиной пароля максимум 8 символов). Поэтому я подумала, что будет легко взломать эти пароли ради удовольствия.

Берём стандартные брутеры john и hashcat.

Довольно быстро я взломала много паролей, большинство из которых были очень слабыми (любопытно, что bwk использовал пароль /.,/.,, — его легко набрать на клавиатуре QWERTY).

Но пароль Кена не поддавался взлому. Даже полный перебор всех строчных букв и цифр (несколько дней в 2014 году) не дал результата. Поскольку алгоритм разработан Кеном Томпсоном и Робертом Моррисом, мне было интересно, в чём тут дело. Я также поняла, что, по сравнению с другими схемами хэширования паролей типа NTLM, crypt(3) довольно медленно брутится (возможно, и менее оптимизирован).

Неужели он использовал прописные буквы или даже специальные символы? (7-битный полный брутфорс займёт более двух лет на современном GPU).

В начале октября эту тему снова подняли в списке рассылки The Unix Heritage Society, и я поделилась своими результатами и разочарованием, что не смогла взломать пароль Кена.

Наконец, сегодня Найджел Уильямс раскрыл эту тайну:

От: Найджел Уильямс <nw@retrocomputingtasmania.com>
Тема: Re: [TUHS] Восстановление файлов /etc/passwd

Кен готов:

ZghOT0eRm4U9s:p/q2-q4!

Потребовалось более четырёх дней на AMD Radeon Vega64 в hashcat примерно на 930MH/с (знающие в курсе, что хэшрейт колеблется и снижается к концу).

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

Очень рада, что тайна разрешилась, а результат такой приятный.
Поддержать автора
Поделиться публикацией

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 70

    0

    Т.е. хэши паролей разработчиков утекали даже в те времена.

      +5
      Раньше об этом особо и не думали
        +28

        И сейчас тоже не особо думают.

          +4
          Утечки были, есть и будут всегда. Как раз именно угрозы утечек баз данных паролей породили подход к хранению хэша пароля с солью. Но от короткого пароля, плохого хэша и соли ничего не защитит.
      +19
      длиной пароля максимум 8 символов

      ZghOT0eRm4U9s:p/q2-q4!

      это как?
        +60
        хеш: ZghOT0eRm4U9s
        пароль: p/q2-q4!
          +4
          понял
          0
          это пара хеш: пароль
            +4
            Слева от двоеточия — хэш, после — пароль.
            (Я буду обновлять комментарии)
              +14
              Как хорошо, что перед отправкой ответа решил обновить страницу:)
              +39
              Лучше как-то более явно выделить сам пароль: p/q2-q4!.
              Я лично тупил смотря на хеш :)
                +4

                НЛО прилетело и опубликовало эту надпись здесь

                0

                Сне интересно: почему ни кто еще не посчитал все возможные хеши для crypt(3)?
                Если подбор пароля это 4 дня, то за пару месяцев можно сосчитать все возможные комбинации… А если запараллелить...

                  –1

                  или запустить в облаке....

                    +6
                    Возможно потому, что их быстрее пересчитать, чем загружать с диска/по сети? 930MH/с — это 12*930*10^6 byte/s = 11.16 GBps. Конечно, посчитанные хеши можно отсортировать, что бы их быстрее было искать, но их всё равно придётся где-то хранить, а это 11.16 GB/s * 4*24*60*60s ~= 4 PB.
                      +1

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

                        0
                        Верно. Справедливости ради, rainbow tables позволяют сэкономить место и для 8-байтовых паролей понадобится всего 256^(8*2/3) byte = 7 терабайт. Но даже 10-значный пароль уже потребует rainbow table размером в 11 петабайт…
                          0
                          Вы как-то неправильно считаете.
                          Радужная таблица позволяет «схлопнуть» исходную таблицу в тысячи (сотни тысяч, миллионы) раз. Да, считать перед поиском по таблице придётся, но по сравнению с исходной задачей — расчётов совсем немного потребуется.
                            0
                            Радужная таблица, как я понимаю, позволяет схлопнуть N паролей в N^(2/3) записей. Именно это я и рассчитал. При чём я исходил из того, что понадобится всего 1 байт на запись, а это недооценка. На самом деле для радужной таблицы восьмибайтного пароля понадобится не 7 ТБ, а минимум в 6 раз больше.
                              0
                              Хотел было отправить Вас в википедию, а там именно эта ерунда и написана.
                              Причём а) написана очень давно и б) в английской версии этой странной арифметики нет.

                              Принцип таблицы очень простой: строится цепочка из N пар пароль-хэш, но сохраняются только «края» — самый первый пароль и самый последний хэш. С учётом того, что N может равняться и миллиону, «степень сжатия» получается довольно большая.

                              При подборе по этой таблице, правда, перед тем, как искать совпадения по файлу, придётся просчитать все N возможных вариантов (там даже N квадрат получается в итоге). Но посчитать хэш даже миллиард раз — это не 2^8, это сильно быстрее.
                                0
                                Допустим, мы хотим, что бы поиск по радужной таблице занимал не более чем 10 секунд на 1м GPU. При 930MH/с выходит, что максимальная длинна цепочки радужной таблицы — sqrt(10*2*930*10^6)=136382. Для десятибайтового пароля число паролей = 256^10. Одна запись в таблице будет занимать не менее 6 байт. Размер радужной таблицы: 6*256^10/136382 = 53.2 ексабайта. Для 8ми-байтового пароля выходит 811.5 терабайт, для 7ми-байтового — 3.2 терабайта. Если у нас 8ми-байтовый пароль и мы готовы ждать поиска по радужной таблице целый час — её размер будет не менее 42.8 Терабайт.
                                Я думаю, как-то так и выводится N^(2/3). При более компактных таблицах, наверное, выходит что поиск занимает дольше, чем прямой перебор.
                                  0
                                  У вас несколько ошибок в рассуждениях. Во-первых, вы верите всяким непроверенным данным (что мне, что википедии). В работе изобретателя этих таблиц (ссылка есть в той же википедии, кстати) есть более развёрнутые расчёты (и по определению — правильные) сложности вычислений и размеров таблиц. И да, тем всё несколько сложнее (к тому же, всё зависит от вероятности найти искомый пароль — метод «берём и выбрасываем 99% информации» явно подразумевает потери информации).
                                  А во-вторых, от 8-символьного пароля (кстати, кто-нибудь подскажет — у unix'а времён Кена Томпсона в пароле могли быть символы с кодами >= 0x80 ?) мы как-то незаметно переместились к 100500-байтным паролям.
                                    0
                                    Я Вам не верю, я с Вами наоборот, не соглашаюсь. А так, если говорите, что у меня в рассчётах ошибки, называйте их, иначе это похоже на уход от темы. По сути давайте. Википедии поверил потому, что интуитивно то, что там написано выглядит правдоподобно, и я не видел смысла самому перепроверять достоверность — это не такой принципиально важный для меня вопрос. Если даже это неверно — я никак не пострадаю. Если в вики ошибка — приведите конкретную правильную оценку, а не пустое «у Вас неправильно, правильно в другом месте».
                                    от 8-символьного пароля… мы как-то незаметно переместились к 100500-байтным паролям
                                    Не надо этих преувеличений, я рассматривал (для примера!) именно 8-10-байтные а не 8-символьные пароли. Для простоты я подразумевал 8-битные байты. Нет никаких проблем подставить в формулы 6-7-битные байты — получится то же самое, что 6-9-байтные пароли с 8ми-битными байтами.
                                    Мои рассчёты — это оценка сверху, на самом деле радужные таблицы, видимо, ещё менее эффективны, т.к. их размер тоже ограничен из-за коллизий, что я не учитывал.
                                      0
                                      Кстати, сам автор (Philippe Oechslin) и приводит оценку в N^(2/3). Вы сами-то читали приведенную Вами работу, прежде чем обвинять википедию и меня в излишней доверчивости?
                                        0
                                        сам автор (Philippe Oechslin) и приводит оценку

                                        На первой странице он рассказывает о работе Хелмана — там тоже таблица, но из-за особенностей функции редукции у Ошлина получился значительный выигрыш.

                                        Вы сами-то читали

                                        Я, было дело, по основам этой работы софину писал. Табличка для 6-байтового пароля была полсотни гигабайт, считалось за пару минут.
                                        Кажется, спор вышел полезный. Без него Вы бы вряд-ли полезли дальше википедии…
                                          0
                                          Спор показал пока что лишь то, что Вы так и не привели корректную оценку, но википедию уже попытались дискредитировать. Оценка википедии подтвердилась в статье Philippe Oechslin.
                                          Табличка для 6-байтового пароля была полсотни гигабайт
                                          Вы же понимаете, что такое нелинейная сложность? Philippe Oechslin пишет, что им потребовалось 13.7 секунд что бы найти в таблице один пароль длинной менее 5 байт!
                                          Кроме того для построения rainbow table нужно примерно в 10 раз больше расчетов чем для однократного прямого перебора. Т.е. окупится только если подбирать более чем 10 паролей.

                                          Скажите, какой по вашему минимальный разумный размер raindow-table, если число перебираемых паролей равно N?
                                            +1

                                            Перечитал википедию. Окей, беру свои слова обратно. Там сравниваются таблица Ошлина и таблица Хеллмана. И радужная таблица выходит на треть компактнее, всё как и описано у автора.
                                            Проблема только в том, что N вместо размера таблицы (как оно описано в википедии) стало количеством возможных паролей (как оно посчитано у вас, с какими-то невообразимыми результатами).

                                              0
                                              Похоже, Вам все же нужно ещё раз перечитать ту статью, что Вы привели. Как по-вашему связаны размер таблицы и число возможных паролей? У Philippe Oechslin есть ответ ;).
                                              радужная таблица выходит на треть компактнее
                                              Там не так написано, не на треть. X^1 и X^(2/3) отличаются не на треть.
                                                0

                                                Штука в том, что ещё у Хеллмана таблица не содержала все возможные пароли. Конкретно та таблица Хеллмана, что рассматривает Ошлин в примере, в тысячи раз меньше, чем число возможных паролей.


                                                отличаются не на треть

                                                Тьфу, конечно же. Извините.

                                                  0
                                                  Что Вы имеете ввиду под «все возможные»? Что не все символы учитываются? Или что вероятность нахождения пароля не 100%? Если первое, это не меняет сути т.к. просто отнимает 1/8-2/8 от числа байт. Если второе, то это несущественно т.к. в rainbow table этот показатель без особых затруднений доходит до 99% и даже 99.9%.
                                                  Вопрос в том, как связан размер таблицы и число паролей, пусть даже угадываемых.
                                                    0

                                                    Я имею в виду, что в Хеллман придумал способ "составим цепочку хэш -> пароль -> хэш ->… -> хэш -> пароль, и сохраним первый хэш и последний пароль". Но он использовал только одну функцию редукции (это стрелка "хэш->пароль"). Ошлин через 23 года усовершенствовал этот способ, значительно сократив число коллизий: для каждого шага в цепочке была своя функция редукции. Ну и красивый термин попутно придумал.


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

                                                    Размер таблицы (в парах хэш-пароль) = число возможных паролей / длину строки (повторюсь, строка 100000 с нынешними вычислителями — совсем не длинная) * коэффициент избыточности (тут начинается тервер, т.к. 100% гарантии нахождения пароля не получается. Возьмём цифру с потолка 5).

                                                      0
                                                      Остался последний логический шаг: какие практические ограничения есть на длину строки?
                                                        0

                                                        Что-то я иронию плохо улавливаю.
                                                        В 2003 году практичной длиной строки было 4666 (пруф см. выше). В 2019 году практичной длиной строки можно считать 100000 (придётся верить мне на слово).

                                                          0
                                                          Зачем верить Вам на слово, если Ошлин всё посчитал, а вики повторила? Да и длина цепочки 100000 — это мало. При 100000 размер таблицы будет 2^password_bit_length/100000*password_bit_length*const, то есть не менее 2^(7byte*8bit/byte)/100000*7byte*2=10TB для 7-байтного пароля, для 8-байтного — 3 PB.
                                                            0
                                                            Зачем верить Вам на слово

                                                            … и следующей же строчкой — данные, которые я же и предоставил. Ну отлично просто.


                                                            Ладно. От идеи "схлопнуть N паролей в N^(2/3) записей" мы, кажется, уже окончательно отдалились, и то хорошо.

                                                              0
                                                              это какие? Я эти формулы в первых же рассчётах использовал. Число 100000 я просто подставил, что бы Вы увидели, откуда взялось N^(2/3), а 100000 — это Ваше число с потолка, которое не значит ничего и не имеет смысла.
                                                              От идеи «схлопнуть N паролей в N^(2/3) записей» мы, кажется, уже окончательно отдалились, и то хорошо.
                                                              Мы — это кто? Ошлин как-то от этой оценки в своей статье не спишит отказываться. Я пожалуй с ним соглашусь.
                                                              Снова спрошу, какая Ваша оценка? Как связаны размер таблицы, оптимальная длина цепочки и размер пароля? Формулу пожалуйста, откуда она берётся… Предлагаю начать с оптимальной длины цепочки.
                        +2

                        Именно для таких случаев люди придумали соленые хэши

                          0
                          Ещё чуть-чуть, и Вы изобретёте rainbow tables ;-)
                          +13
                          сорок тысяч обезьян в ж...
                            +4
                            – Значит, вот что… У меня тоже ключ несложный. Но вот какие-то слова тебе могут показаться незнакомыми… если что, так по буквам уточни. И вообще… ты на смысле не фиксируйся.
                            Чингиз явно настораживается.
                            – Ну… шутки у меня такие, дурацкие. Сленг, ненормативная лексика… ты парень-то большой…
                            – Быстрее! – В голосе Темного Дайвера появляется легкая угроза.
                            – Если что, так потом я тебя к психологу на прием свожу…
                            – Ты из каких слов ключ составил? – шипит Чингиз.
                            Падла вздыхает и почему-то понижает голос:
                            – Короче, слушай… буквы чередуются, первая строчная, вторая прописная, третья строчная и так далее… пробелов нет вообще. Набирай отстраненно…
                            И он произносит свой ключ.
                            Секунд десять в библиотеке висит гробовая тишина. Темный Дайвер стоит, застыв как изваяние, и краска заливает его лицо.
                              +4
                              Кстати, а пароль Падлы угадали или нет? СЛ же конкурс устраивал по этому поводу, помнится.
                                0
                                Подписался на комментарии ;)
                                  +1
                                  Насколько я помню автор признавался, что его не существует вообще. Есть только это странное описание
                                    0
                                    Кажется, ему этот вопрос задают почти на каждой встрече с читателями. Последнее, что я слышал (пару лет назад) — до сих пор варианты присылают, он их показывает своему знакомому (прототипу Падлы), но т.к. в реальности этого ключа никогда не существовало, то пока лучшего не нашлось ;)
                                  0
                                  Сорок тысяч обезьян в жопу сунули банан
                                  +23

                                  Дополню (для тех, кто не найдет на шахматной доске вертикаль "q"): это ход, записанный в старой английской описательной нотации (descriptive notation — она была популярна до 80-х годов в англоязычных странах, но сейчас почти не используется), где вертикали обознаались не буквами по порядку, а названиями фигур, которые в начальном положении на них стоят. Соответственно, Q — значит queen, т.е. королева или же ферзь. То есть, в "нашей" современной нотации (т.н. алгебраической — algebraic notation) ход будет записываться как d2-d4 (либо d7-d5, если это ход черных — "у них" каждый игрок нумеровал горизонтали от себя).

                                    +2
                                    Помню, в школьные годы имел дело с шахматной программой (консольной, естественно) для мини-ЭВМ семейства PDP-11. Там ходы полагалось вводить именно в такой вот описательной нотации. Пришлось освоить ;)
                                      0

                                      Вообще, если приноровиться, то она особо и не сложнее алгебраической.

                                      +2
                                      А p получается обозначение пешки «Pawn»?!
                                        +2

                                        Да, именно так.
                                        P – пешка (pawn)
                                        N или Kt – конь (knight, букв. рыцарь)
                                        B – слон (bishop, букв. епископ)
                                        R – ладья (rook)
                                        Q – ферзь (queen, королева)
                                        K – король (king)

                                          0
                                          А как быть с парными фигурами? Слон, Ладья, Конь? Как они именовались? Чёрный-белый, левый-правый? Ферзевой-королевский? Или ещё как-то?
                                            +1

                                            Ферзевой-королевский. KB — вертикаль королевского слона, QB — вертикаль ферзёвого слона и т. п.

                                              0
                                              Благодарю
                                                0

                                                Но если было и так понятно, то и не писали. Например, вместо Kt-QB3 (ход белым конем на c3 или черным на c6) пишут Kt-B3, если на KB3 (f3 или f6) конем пойти нельзя. Или еще пример: достаточно написать PxP, если пешку пешкой можно съесть только одним способом, если же нет, то указывали вертикаль одной из пешек по типу BPxP (слоновая пешка ест пешку) или PxKKtP (пешка ест коневую пешку на королевском фланге (т.е. пешку "g")).

                                        +20
                                        Вот и поди пойми все вопросы о сложностях паролей. Восемь символов ради фана брутилось кучей людей с 2014 года, а в результате оказалось, что это не случайный набор символов, а осознанное, имеющее смысл значение, каких все рекомендуют избегать по причине упрощённого их взлома.
                                        +1
                                        Хороший способ придумывать запоминающиеся пароли, если вы шахматист.
                                        Несколько первых ходов какого-нибудь дебютного варианта:

                                        e4e5Nf3Nc6Bb5
                                        d4d5c4e6Nf3
                                        f4e6g4?Qh4#!

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

                                              Подам этому кому-то ещё одну идею: используя буквенные обозначения нот, добавить в базу все существующие музыкальные мелодии. Вперёд и с песней :)

                                                0
                                                Ещё есть аккорды же.
                                                Можно стихи длинными аббревиатурами записывать.
                                                Можно химические формулы юзать.
                                                А есть еще топонимы всякие интересные
                                            0
                                            Вы их опубликовали — и потому их уже точно можно рассматривать как словарные.
                                            +6
                                            > q2-q4

                                            Тебе снится рыбалка у коралловых рифов,
                                            Неизвестный герой древнегреческих мифов.
                                            Молекулярная физика, энергия атома,
                                            Обнаженная женщина, киллер с лопатой.

                                            Новогодняя елка, орбитальная станция,
                                            Мыльница с музыкой, радио с танцами,


                                            смайл, в общем
                                              +1
                                              R-Kt4xВ
                                                +6

                                                Лея женщина, а так перевод интересный

                                                  0
                                                  да, это английский, я недавно перевод оттуда на испанский с такой же ошибкой исправлял…
                                                  +4
                                                  Кен Томпсон в том же списке рассылки еще и оставил свои поздравления ;)
                                                    +3

                                                    Доправьте текст, там автор местами все ещё мужчина: "… и я поделился своими результатами и разочарованием, что не смог взломать пароль Кена". Нелегко, нелегко даётся нашей индустрии мысль о том, что женщины тоже существуют :)

                                                      0
                                                      Потребовалось более четырёх дней на AMD Radeon Vega64 в hashcat
                                                      Стало на этой видюхе можно любой 8-ми-знак взломать, даже от контроллера домена, не самого последнего уровня, скажем 2016?

                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                      Самое читаемое