Анализ возможностей массового аудита на основе утечки хешей из LinkedIn

    Неделю назад утекла база хешей с LinkedIn, для других это событие может быть примечательным само по себе, но для меня, в первую очередь, это означает возможность провести анализ современных возможностей взлома паролей. И я не собираюсь рассказывать о том сколько раз слово «password» было встречено среди паролей и о том, сколько времени занимает перебор шестисимвольных комбинаций. Скорее буду пугать пользователей тем, насколько сложные пароли можно «взломать» за несколько часов. А программистам расскажу как это возможно эффективно реализовать, и в качестве небольшого подарка приложу программу, которую я написал для массового аудита. Присутствует и некоторый ликбез по использованию радужных таблиц с простыми выводами.

    И так, за час удалось «восстановить» около 2.5 миллионов паролей на средней рабочей конфигурации, без специальных словарей и радужных таблиц. Среди найденных паролей присутствуют 16-символьные алфавитно-цифровые комбинации, и далеко не в единственном экземпляре.

    Но начнем по порядку. Представьте, что вам попадается база из 6.5 миллионов пресных хешей (уникальных всего 5 787 239), какие способы восстановить максимальное количество паролей за разумное (скажем 7 дней) время существуют?

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

    Почему? Возьмем набор хиленьких радужных таблиц размером в сотню гигабайт, которые способны с вероятностью в 98% восстановить любой пароль до 8 алфавитно-цифровых символов одного регистра. К слову, такие таблицы можно сгенерить где-то за пару месяцев на довольно-таки мощной машине, но пусть они у нас уже будут, как некий божественный дар.

    Время, необходимое на поиск пароля к одному хеш-значению по таким таблицам — около минуты. За это время необходимо выполнить chain_length операций хеширования, редукции и поиска по тем самым 100Gb.

    Возможности оптимально искать сразу несколько паролей к разным хеш-значениям — не существует; для каждого хеша требуется строить отдельную радужную цепочку и искать ее в таблице. Таким образом, нам понадобится примерно 5.7 миллионов минут на поиск.

    Это где-то 10 лет. Поэтому, наш божественный дар в данном случае нельзя считать и скромным подарком.

    Однако хороший набор радужных таблиц поможет восстановить пароль к одному хеш-значению за минуты (при учете тех же скромных ограничений в 8-9 символов длины).

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

    Нужно взять каждую строчку из набора {a..z0..9}^8, посчитать ее хеш, и поискать в базе хеш-значений, которые в данном случае LinkedIn заботливо нам предоставил.

    И поиск — операция, которую в данном случае довольно легко оптимизировать. Забегая вперед, в своей программе я добился O(1) поиска даже на таких больших базах.

    В основе поиска лежит простая фильтрация, — не пытаться искать те хеши, которые мы заведомо не найдем. Создаем массив битовых значений (checkup) размером SIZE, где-то сотню мегабайт и строим функцию, которая отображает хеш-значение в индекс этого массива. Как ни странно, такой объект тоже называется хеш-функцией, только не криптографической, и частенько его называют сверткой. Для каждого хеша из LinkedIn мы вычисляем свертку, и записываем «1» в соответствующие биты массива checkup.

    При переборе, считаем от полученного значения свертку == j, смотрим checkup[j], если там 0, то смысла искать такое значение в наборе нет (это проверяется за O(1)). Иначе — используем двоичный поиск, который справляется уже за O(log(N)).

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

    То есть, для массового взлома даже прямой перебор выгоднее таблиц!

    Но мы бы хотели справиться и с паролями длиннее 8 символов и на помощь нам приходят словари. Словари это очень круто! Они содержат те пароли, которые уже были чьими-то, и вероятность оказаться среди наших — у них гораздо выше, чем у случайных строчек. А если еще и добавить некоторый набор правил замены — то можно творить чудеса. При этом скорость такого перебора будет сравнима со скоростью прямого перебора.

    Но есть один недостаток — словари должны откуда-то взяться. То есть выборка слов не должна быть случайной, а должна быть следствием некоторого анализа. И скачав словарь с просторов Глобальной Сети, вы можете получить полное «барахло», эффективность перебора по которому будет ниже прямого перебора (я вот, например, специально впишу туда строки, которые вряд ли кто-то поставит как пароль).

    Сделай сам

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

    Шаг первый. Запускаем прямой перебор по набору всех символов, которые возможно ввести с клавиатуры, длиной до 5-6 символов. В сущности, у нас нет задачи получить все пароли такой длины, просто хочется получить некоторое количество, сотни тысяч — для дальнейшего анализа. Если 6 символов — слишком короткая длина, то можно взять 7-8, опять же, нам не требуется исчерпать весь диапазон для перебора.

    Главное, чтобы поработало минут 5-10.

    Итак, мы нашли некоторые пароли. Теперь можно провести частотный анализ, выделив наиболее вероятные комбинации символов, идущих подряд. Например, «pass» одна из таких комбинаций, а на LinkedIn и «link» тоже.

    Шаг второй. Запускаем перебор по конкатенации словаря частых комбинаций самого с собой. Сейчас я просто напоминаю, но если суть не ясна, рекомендую почитать мою предыдущую заметку.

    Пусть тоже поработает минут 5-10, и заметьте, находить пароли оно будет гораздо резвее, чем в прошлый раз.

    И шаг третий. Набрав «критическую массу» найденных паролей, скажем десятую часть от всех, повторяем частотный анализ и снова запускаем перебор, по полученным словарям. Теперь уже можно не останавливать — он свое дело сделает.

    На настоящий момент перебор у меня работает уже часа два без остановки, и находит «на глаз» где-то 50-100 паролей в секунду.

    А вот пример полученного словаря: dl.dropbox.com/u/243445/md5h/relevant.txt
    Вы можете проверить безопасность своего пароля, попытавшись «собрать его из кусочков» словаря.
    Если достаточно четырех или меньше кусочков — он плохой, меняйте.

    Что удалось «сломать»

    linkedinmel1234, andrea71103245, hockey101155239, magmag624222, carlito5657224, linda@790212, supercow779212, jesus143mary143, linkedin#239133, linkedinpassword123, thepassword1776000, 13051987159000, meatballstew123, latenightbreeze, whatthedillyo, friendofkellyg, hannah11emily9, linkedin7barry5, linkedin.passwd, linkedinrocksforeva, philip23marcus, 54fordpickup, nabe1959@, ge0rgin@, #1dust67, logic123tree456, ramgopal@123456, Jk971423, tiger!376400, ...

    UPD вот скрин с посчитанной статистикой для найденных паролей (могу обсчитать еще какие-нибудь параметры, если нужны):



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

    Программа

    Как и обещал — вот программа, которой удалось это сделать. И кстати, вы свободны в попытках повторить результат (или добиться лучшего).

    Исходники: dl.dropbox.com/u/243445/md5h/src.7z
    Бинарник: dl.dropbox.com/u/243445/md5h/MD5BLAST.exe

    Не удивляйтесь, что он называется MD5-, а не SHA- ибо, в качестве заготовки я взял свою программу, о которой уже рассказывал.

    Все так же необходим CUDA Toolkit: developer.nvidia.com/cuda-toolkit-32-downloads#Windows

    Скорость перебора по словарям для SHA1 на GTX460 при наличии 5.7 млн уникальных хешей в списке — более 60 mpwd/s. И не ругайте «низкую» скорость — это же:
    * SHA1;
    * 5.7 миллионов хешей для поиска;
    * конкатенация словаря из строк произвольной длины.

    Аналогов с более высокой скоростью для данной задачи пока все равно нет.

    Чтобы запустить перебор нужно сохранить хеши в файле hash_list.txt, словарь в файл words.txt и вызвать:
    MD5Blast words.txt 3 0.0
    где 3 — максимальная степень (количество конкатенаций словаря), а 0.0 — начальный прогресс в процентах.
    Для шага 1 из вышеописанной схемы, в words.txt должны быть все вводимые с клавиатуры знаки, по одному на каждую строчку:
    a
    b
    c
    ...

    Чтобы получить список релеватных комбинаций:
    MD5Blast _found.txt relevant.txt 1.0 4.0 16.0
    где первый файл — исходный для анализа, второй — для записи результатов (да, немного не Unix-way),
    а оставшиеся три параметра — адаптивные пороги частоты для двух, трех, и четырехсимвольных комбинаций соответственно (выше число — меньше комбинаций в результате, с ними можно экспериментировать).

    Небольшие выводы

    • Радужные таблицы при массовом взломе — бесполезны;
    • Длина пароля, наличие спецсимволов, его бессмысленность, разные регистры — по отдельности не составляют безопасность;
    • Хешировать пароли без использования соли — все равно что хранить половину из них в открытом тексте (учимся на своих ошибках);
    • Частотный анализ позволяет генерировать неплохие словари «из ничего».
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 123

      +5
      Отлично. Один говорит, что соль не решает всех проблем, теперь и сложные пароли, оказывается, ни фига не спасают… Давайте устроим открытый интернет — без паролей, без защиты любых конфиденциальных данных?

      P.S. пошёл менять пароли...
        +2
        Принцип «слабого звена», если накосячит или пользователь или программист — то «безопасность» пропадает.

        Действительно надежной система авторизации может быть только при условиях:
        — хороших, сложных и псевдослучайных паролях пользователей (ну и нельзя давать поставить пароль «themybigpassword», уверяя пользователя, что он надежный);
        — грамотность пользователя (в контексте фишинга и других социальных атак);
        — использование соли (или других техник, мешающих массовой атаке);
        — недоступность базы с хеш-значениями извне.

        нарушаем хотя бы одно из них — получаем проблемы.
          +2
          Хорошо. Рассмотрим 2 варианта.

          1. Я пользователь. Весь из себя грамотный и образованный. Ставлю пароль вида «fjD$vE^b4#N7%f9U$Id;4O2». Где гарантия, что он не хранится в открытом виде в таблице, которую можно увести простым SQL Inject? Или мне ставить простой пароль, чтоб, если уведут, было не жалко?
          2. Я разработчик. Предусмотрел всё, что только можно — sha512(crypt(md5(pass)).salt.md5(reg_date)), все порты закрыты, каждый байт в базу — intval или mysql_real_escape_string. Где гарантия, что юзер не поставил пароль 1QaZ2wSx#edc? Или мне к проверке сложности пароля прикручивать словарь на пару гигов?
            +2
            Вы абсолютно правы. У вас, как у пользователя — вообще никаких гарантий, вы же не знаете, что внутри системы творится.

            Если вы разработчик, то у вас есть возможность повлиять на пользователя, скажем в форме «придумай пароль» проверять, нельзя ли его пароль составить из слов частотного словаря. Не панацея, но значительное улучшение.
              +3
              да, как раз дело в том, что частотный словарь, он небольшой совсем, те 2.5 миллиона получились благодаря словарю всего на 40кб, полученному после первых двух шагов.

              40кб таскать в веб-форме, думаю, допустимо.
                0
                Хммм. А вот это дельное предложение. Пожалуй, я займусь такой системкой на досуге…
                  0
                  Даже обновил немного статью, благодаря вашему комментарию, — теперь там есть словарь и идея как проверять пароли.
                    0
                    Когда-то была такая штука, как Cracklib (http://sourceforge.net/projects/cracklib/) — ее можно было легко подключить к своему софту, чтобы проверять введенные пользователем пароли на стойкость. Её даже довольно активно использовали. Не знаю, как у нее сейчас дела.
                    +1
                    Блин, а потом на каждый сайт придумывать пароли, которые никогда не запоминаются, а все время приходится пользоваться «Забыл пароль».
                    Абсолютно не вариант, все что ни связано с деньгами или почтой (центральным источником для восстановления паролей), не должно требовать сложные пароли.
                      +1
                      А может лучше придумывать пароль за пользователя? Это будет меньше раздражать пользователей, чем попытка придумать пароль подходящий под требования политики безопасности.
                        +1
                        Я так и делаю :) Нафига юзеру мозг выносить, захочет потом сам поменяет.

                        А пароль в открытом! виде высылаю ему на почту, потому как считаю что если злоумышленник получит доступ к вашей почте, НЕ ЗАВИСИМО от применяемых методих безопастности, он все равно сможет с легкостью получить ваш пароль а с ним и доступ к супер охраняемой системе с вашими данными.

                        Есть исключения: можно не юзать почту а вместо этого использовать СМС или еще что либо… но это сути не меняет. В любом случае это слишком сути не меняет.

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

                          Ведь он может его записать на бумажке и положить перед монитором. Но эти риски разработчик уже никак не может закрыть.

                          Можно, конечно, поступить как-то иначе. Например, задать при регистрации 100500 анкетных вопросов и затем спрашивать у пользователя при каждом логине повторные ответы на эти вопросы. Если 10 из 10 совпадут — наш человек. Разумеется, вопросы должны быть такие, чтобы ответы в своем наборе максимально разнились у разных пользователей.
                        –2
                        вопрос — разве хеши не будут сильно отличатся в этих случаях?

                        1QaZ2wSx#edc -> sha512(crypt(md5(pass)).salt.md5(reg_date))
                        1QaZ2wSx#edc -> md5(pass)

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

                        то есть при подборе мы сравниваем только с оригинальным предполагаемым md5 или я не до понял, поясните плиз?
                          0
                          Если украли базу, то соль злоумышленник тоже знает. Программу нужно будет модифицировать, но насколько я понял, это не значительно усложнит скорость обработки. Сам алгоритм злоумышленник знает всегда, это должно быть принято по-умолчанию.
                            –2
                            Стоп, как же он знает алгоритм, если увели только базу да и еще ТОЛЬКО хеши, когда соль например может генерироваться из даты добавления, как в примере.
                              +1
                              3-ий раз в этом топике повторяется эта фраза: en.wikipedia.org/wiki/Security_through_obscurity
                                0
                                Я наверное недопонимаю смысл фразы, поясните пожалуйста мне как она относится к конкретному примеру?
                                  +4
                                  В информационной безопасности принято считать, что у злоумышленника всегда есть доступ к вашим алгоритмам и исходным кодам, не важно как он это сделал, не важно как сильно вы их прячете. Это по-умолчанию, никого не волнует как он туда получит доступ и получит вообще.

                                  От части по этой же причине не рекомендуется писать собственные криптографические функции. Security through obscurity — одна с наиболее частых ошибок новичков в ИБ.
                                0
                                Обычно считается, что раз увели базу, то и к исходникам доступ есть. В общем когда делаете защиту, считайте, что у злоумышленника есть снимок диска(ов) (не такая уж редкая ситуация, когда бэкап уводят).
                                  0
                                  Все, теперь понял спасибо. Тогда нужно делать соль через открытый ключ, который будет выдаваться пользователю на руки, то есть вбить необходимо будет два пароля. основной и ключ для генерирования соли.
                                    0
                                    Зачем так усложнять всем жизнь? Если выдавать сертификаты, то есть RSA, но как вы в таком случае будете восстанавливать утерянные сертификаты или что будет, если server-side копия нагнётся?
                                      0
                                      Как и раньше — восстановление пароля, основной + ключ, РСА — вполне, но выдавать сертификат юзеру помоему геммор, а усложнение даст большой прирост в защищенности, если использовать хотя бы на ресурсах с конфиденциальной и потенциально востребованной взломщиками инфой, ведь кредит в банке тоже не по пропускам дают, везде где имеет место риск — сложность это благо.
                                        0
                                        Тем не менее пользователю прийдётся хранить где-то соль (в уме вряд-ли)… Я бы таким сервисом не пользовался :). Если вам критична безопасность — сделайте двухэтапную верификацию по СМС. Но вводить тех же два рандомных пароля, так давайте попросим 3 пароля, а потом 4…

                                        Методы в духе sha512(crypt(md5(pass)).salt.md5(salt)) вполне работают, если продумать некоторые ньюансы.
                                          –2
                                          Солью на сайте может быть комбинация или слово — легко запоминающееся, например «Введите девичью фамилию матери», думаю запомнить такую соль проблем мало у кого составит =), конечно такого рода соль попадает в разряд словарных, но додумать идею вполне возможно, кстати той же солью может служить номер-серия паспорта )). А для верификации по смс придется арендовать трафик.
                                            –2
                                            Кстати как вариант со статичной солью например просить пользователя вводить произвольное число от 1 до 9999, каждая цифра будет значить место символа поле которого была подставлена, пусть статичная, соль, соответственно сила пасворда увеличивается многократно, а запомнить простое число опять таки не составляет труда.
                                              0
                                              Вы лишь усложняете жизнь пользователям :). Можно сделать миллион проверок, но кто этим будет пользоваться? Используйте классические, отработанные методики. Не думаю, что у вас проект требует параноидального подхода к авторизации.
                                                –2
                                                Как видно из опыта ЛастФм и ЛинкедИн классические методики посасывают xD

                                                А усложнение жизни, повторюсь неминуемо, взять хотя бы ту же капчу, которую я к слову не всегда разбираю с первого раза, но капча необходима. Соответственно если сущность необходима то она должна быть.

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

                                              Главная проблема паролей — их малая длина, словарность и использование одинаковых паролей на разных ресурсах. Девичья фамилия матери относительно малая и словарная, у номера серии паспорта ограниченный алфавит и даже не все символы случайны, так что можно тоже считать относительно малой и отчасти словарной, ну а использоваться точно будут одни на разных ресурсах.
                                        0
                                        Тогда проще пользователю выдать вместо пароля его логин, подписанный его закрытым ключом, который вообще нигде не хранится (удаляется сразу после подписи), а в базе хранить открытый. Злоумышленник получив доступ на чтение к базе и вообще серверу не сможет ни выдать себя за пользователя при обычной аутентификации, ни как-то использовать открытый ключ. Вернее ему можно будет восстановить закрытый ключ и/или подпись известного ему логина по известному ему открытому ключу, но тут отпадает проблема «простых паролей» — закрытый ключ и подпись по определению псевдослучайные и никаких атак по словарю быть не может в принципе… Вопрос как заставить пользователей «запоминать» подписи не в один десяток, а то и сотню символов.
                                          0
                                          Я даже придумал генерировать изображение как ключ )))) либо по изображению пользователя генерировать )))
                                            0
                                            Поздравляю с изобретением системы инвайтов на хабре ^^.
                                              0
                                              Ахахах, да когда пришла в глову мысль я о том же подумал )))
                                  0
                                  К слову, криптование результата md5(...) — плохое решение, т.к. то, что внутри — бесконечно, а вот результатов md5 конечное количество.
                                    0
                                    И в итоге мы приходим к коллизиям первого рода, но на практике…
                                      0
                                      Мне вот тоже интересно. Все кричат про коллизии, но кто их видел на самом деле? Какова вероятность коллизии? Какова вероятность того, что коллизией к паролю, состоящему из 8-15 символов, набираемых с клавиатуры, будет строка, также состоящая из 1-15 символов, набираемых с клавиатуры? Это еще возможно, если 32-битную CRC32 использовать, но при 128-битной MD5...?

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

                                      Так что уникальная для каждого пользователя соль, специальные медленные хэш-функции, ну и нормальные пароли, естественно.
                                        0
                                        Согласен, поиск коллизии стремится к утопии. А вот как нам демонстрирует автор «Со статистикой хрен поспоришь» (с), поэтому главная задача уйти от систематики любым доступным путем, но при этом не потеряться в сложности конечного решения. Ну и так или иначе классика всегда морально устаревает. Думаю хорошим вариантом будет авторизация по сетчатке глаза xD
                                      0
                                      Результатов любой хэш-функции конечное множество. (с) К.О.
                                        0
                                        Об этом речь.
                                          0
                                          Так какие предложения?
                                            0
                                            Не использовать результаты более слабого хеширования в аргументах более «сильного».

                                            Объясню на примере что я имею в виду (если не прав, поправьте, пожалуйста):
                                            1. Количество хешей sha1 значительно больше, чем md5.
                                            2. Т.е. используя в качестве аргумента sha1 хеш md5 мы урезаем количество итоговых хешей sha1.

                                            Т.е. предположение о том, что md5(md5()) более стойко, чем md5() — неверно.
                                              0
                                              предположение о том, что md5(md5()) более стойко, чем md5() — неверно.
                                              Правильно. Но так делают не для повышения стойкости, а для увеличения времени, затрачиваемого на вычисление. Конечно, если итерации всего 2, то и говорить не о чем, но если их миллион?

                                              Более вероятные коллизии из-за уменьшения мощности исходного множества значений? А если так: md5(pass|md5(pass|md5(pass|salt))), всего 500000 раз? Мощность исходного множества не уменьшается, ведь pass присутствует в каждой итерации, а значит и вероятность коллизий не увеличивается.
                                                0
                                                По поводу замедления:
                                                неужели повторное хеширование хоть сколько-то значимо замедляет работу?
                                                На мой взгляд, если цель замедлить, то корректнее использовать другие способы.
                                                  0
                                                  PBKDF2 основан именно на многократном хэшировании.

                                                  Если Вы не 2 раза применили функцию, а, скажем, 500 раз, или 100000 раз, то конечно замедляет.
                                  –2
                                  На самом деле самая правильная защита от перебора — лимитирование количества обращений к механизму аутентификации (например — 10/5 минут). Тогда отбрутфорсить не получиться совсем.
                                    +5
                                    здесь другая ситуация, у нас уже есть хеши с сервера.

                                    если предположить, что никакого доступа к ним невозможно, то да, лимитирование, очевидно будет плюсом к защите.
                                    +2
                                    Ммм, а если использовать какой-нибудь bcript со скоростью не более, к примеру, 100 паролей в секунду. Мне кажется, чтобы забрутить хотябы такое — «5263613», уйдёт целый день. Я не прав? А сервер, скорее всего, и не ощутит повышения нагрузки. Т.е. компромисс есть.
                                      0
                                      Можно считерствовать — при регистрации юзера не давать ему вводить пароль, а сгенерировать его самостоятельно, а потом сообщить: вот твой пароль, запиши и пользуйся. Кто-то сменит сразу, конечно, но шансы на нормальный пароль всё-таки увеличиваются.
                                        0
                                        Некоторые сервисы вообще не дают возможность поставить пользовательский пароль. По «сменить пароль» или «забыли пароль» тупо высылается новый.
                                      0
                                      возьмите банки. Они уже все давно придумали
                                    +1
                                    Собственно, советов два: либо длинные фразные пароли «Glory has to be a remote-sensing Earth-orbiting observatory», либо фонетические пароли:

                                    yerUghaHycs1
                                    Min3drekI
                                    Eceblec1
                                    (сгенерировано apg)
                                      +2
                                      Думаю, пока рано с советами, я дам возможность перебору поработать еще пару дней (пока он часа 3 крутится) и постараюсь сформулировать общие закономерности, но эти три пароля не выглядят уж очень случайно, второй например проверил и
                                      Min — есть в базе, 3 и l — символы, drek — есть в базе релевантных (полученных из анализа LinkedIn), то есть такой пароль — это словарь^4 и предположительное время на его взлом — меньше суток.
                                        0
                                        Хм. А это были _случайные_ пароли, сгенерированные утилитой apg.

                                        Если что, вот ещё несколько:

                                        RikGigh3
                                        Uddorzoat4
                                        UfEecaxDuAl1
                                        eupAmcevot3
                                        houcVad8
                                          0
                                          А как на счет таких pIgsjrNWJuTCBfrWR6H4x3br ?
                                            0
                                            Никаких проблем. Теперь учите.
                                              +1
                                              Зачем учить? Есть чему это запоминать.
                                                –3
                                                Пароли, которые «Запоминают» в специальной программе — ущербное решение. Правильное — открытый/закрытый ключ, сертификат.

                                                Я, например, по хостам хожу именно с ключом. И он всяко длиннее вашего скромного «перепароля»/«недоключа».

                                                Что-то типа такого:
                                                AAAAB3NzaC1yc2EAAAADAQABAAABAQCwNNkwEnlLZhVzo9wDkyPW182NmUQpfn7vey+weblcWXsnMf6ECfLWow6jLgr4XjxNfr92CnvnkmFGS2ZjGLZVv/48PkLampkROKVN2JIsZFL1W2FcyOEJSaFkPsegfVeyh1/ApKf/6OEDvr1poT3SEKkbhXUJCQGhAwsaN4SyZZAsrDGwYnsNn93/YYLCBeoqNVj3XDBDHBdsNfO5qwoxlRMKG1Km4muUz30AWmbU7dpnwRUoZKRaCJ1MwY1z4RRPMOJ2t6H4yw8M148L6FkmmMyYxeIzuyfvhLnKj9POqLfXOHRXero0yU1nKazvXRDnmI6eTpsLWG5k3QJyEHDn
                                                  +9
                                                  Я, например, по хостам хожу именно с ключом также.

                                                  Можете до усрачки гнуть пальцы со своими правильными ключами/сертификатами. Только на скольких сайтах вы сможете по ним авторизоваться?
                                                    0
                                                    При аутентификации всегда всегда надо выбирать компромисс между удобством и безопасностью. Пускай сертификаты надёжнее логина с паролем, но менее удобны на практике. Главный недостаток — системы использующие сертификаты не допускают простого способа его восстановить. Я вот сейчас настраиваю удаленный сервер, генерирую пару ключей, но не представляю что делать если потеряю свой закрытый ключ или просто нужно будет зайти на сервер не из дома. Пока в голове только один сценарий — накатывать систему заново и восстанавливать базу из бэкапов или срочно бежать домой. Или держать второй сервер, где хранить закрытые ключи и аутентифицироваться на нём по паролю. А есть ли смысл тогда?
                                                      0
                                                      Кстати, а почему у вас вход не по сертификату? Пренебрегаете безопасностью? Пренебрегаете безопасностью? :)
                                                        +1
                                                        >> Только на скольких сайтах вы сможете по ним авторизоваться?
                                                        И с любого ж компьютера | телефона | планшета? без лишних телодвижений?
                                                  +2
                                                  Вспоминается мне девушка, которая в своих паролях использовала функции — и запомнить не трудно, и криптостойкость, вроде как, не плохая (хотя, конечно, зависит от выбранной функции).

                                                  Что думаете по этому поводу?

                                                  p.s.
                                                  Пример навскидку:
                                                  f(x^2)=Ey^x+1
                                                  –1
                                                  тогда уж лучше в виде «А роза упала на лапу могвая» — в английской раскладке. Запоминаются легко,
                                                    +5
                                                    И абсолютно не набираются, например, с экранной клавиатуры какого-нибудь планшета или тем паче 123-клавиатуры телефона. В жизни всякое случается, и такой пароль для банка или почты может оказаться очень печален.
                                                      +1
                                                      Кроме того, смена раскладки всего лишь удвояет время перебора паролей, таблицы давно существуют и используются.
                                                        0
                                                        Для банка вообще грешно использовать аутентификацию только по паролю, мне например для входа в банк нужно ввести 2 пароля + код с токена.
                                                        0
                                                        У паролей — русских символов в английской раскладке есть огромный минус: если клавиатура не содержит русских символов, то такой пароль не ввести и самому, если не помнить наизусть, под какой латинской буквой расположена соответствующая русская.
                                                          0
                                                          гм… у меня как раз клавиатура без русской раскладки, как то привык не смотреть на кнопки во время набора.
                                                            0
                                                            Наберёте этот же пароль с клавиатуры смартфона/планшета или экранной клавиатуры? :)
                                                              0
                                                              да, переключая раскладку туда-сюда
                                                                +1
                                                                image

                                                                А так?
                                                                  0
                                                                  не имею привычки вводить пароль на устройствах, в которых я не уверен.
                                                                    0
                                                                    В терминалах РЖД, например, алфавитный порядок. И там не сильно много альтернативных вариантов (кроме стояния в очереди с гастерами в окошко к тётечке, печатающей одним пальцем).

                                                                    А смена клавиатуры на устройстве сразу вводит его в класс «неуверенных»?
                                                                      +1
                                                                      на своем устройстве я могу поставить любую клавиатуру. а для остальных только индивидуальные пароли, которые можно набрать на этом устройстве
                                                                0
                                                                да, смогу, если клавиатура йцукен.
                                                              0
                                                              Для этого есть «клавиатура для паролей»: нажимаем русские буквы, получаем в английской раскладке.
                                                          –3
                                                          Получается, что пароли, написанные транслитом в этом случае лучше? Или я не прав?
                                                            +3
                                                            если вы единственный — кто так делает, то возможно. но это слишком простое правило, и если его будет использовать много людей — то автоматически релеватные комбинации пополнятся и им.

                                                            Например ghb — попало в словарь релевантных (для LinkedIn). Вряд ли имелось в виду g-h-b, скорее русское «при».
                                                              +1
                                                              Принципиальной разницы нет. Существуют словари, состоящие из таких паролей.
                                                              +4
                                                              bcrypt от такого перебора, по идее, спасёт.
                                                                0
                                                                Пользуясь случаем хочу задать вопрос. Например алгоритм для хранения паролей — sha512 с примерно 500 000 раундами (приходами). И вот утекает база с такими паролями. Что могу предпринять хакеры чтобы вскрыть пароли (будем считать что к-во раундов неизвестно)?
                                                                  +2
                                                                  Можно ваш сайт с одной машины досить без перерыва с таким подходом к безопасности, хе-хе-хе (тот же брутфорс завалит сервер всерьёз и надолго)
                                                                  Считаю что пароль + соль в 1 проход более чем надёжная защита.
                                                                  +1
                                                                  неизвестное количество раундов — это Security through obscurity

                                                                  Не стоит на это закладываться. Но да, массовый перебор будет соответственно в миллион раз медленнее — и на ближайшие пару лет взломщиков это остановит.

                                                                  Но да, нагрузка на сервер при этом возрастает ужасно, и для высоконагруженного решения — идея не приемлема.

                                                                  Пароль + соль, а лучше сразу bcrypt — значительно надежнее/удобнее.
                                                                    +1
                                                                    Кстати такое количетсво повторных хэширований здорово увеличит вероятность коллизий.
                                                                      0
                                                                      На хабре была статья, которая это опровергает :).

                                                                      habrahabr.ru/post/100301/
                                                                        +2
                                                                        за опровержение эту статью считать нельзя: теоретическая выкладка завязана на сюръективность хеш-функций, а это свойство не доказано.

                                                                        А для усеченного md5 хеша могут действовать другие правила, нежели для полного, опять же, доказательство идентичности свойств отсутствует.

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

                                                                        Но я и обратного утверждать не буду :)
                                                                          0
                                                                          Даже если верить всем выкладкам, то 500 000 раундов увеличит вероятность коллизий в минимум ~250 000 раз
                                                                            0
                                                                            Зачем делать это 500000 раз? Чтобы при регистрации или авторизации сервер ложился и без ддоса? :)
                                                                              0
                                                                              Вот я и не знаю зачем :) То есть понятно зачем — осложнить брутфорс злоумышленнику — но, имхо, в обычных условиях массовых сервисов это оверхид, который себе дороже выйдет. Соли достаточно для усложнения целевых атак (готовые таблицы не подойдут), уникальной соли — для массовых (для каждого юзера нужна «таблица»).
                                                                                0
                                                                                Ну можно ведь пройтись хеш-функцией в раундов 20, что очень незначительно повысит вероятность коллизии (а именно коллизии над уведённой базой будет искать лишь сумасшедший, ибо потенциально этот перебор займёт коллосальное количество времени), но в то же время программы перебора паролей будут делать это в 20 раз медленнее (20 недель вместо одной).
                                                                                  0
                                                                                  Можно, но без соли этого делать не стоит по любому.
                                                                                    +1
                                                                                    Я абсолютно с этим согласен, хорошие практики нужно комбинировать…
                                                                                      +1
                                                                                      Криптография такая хитрая штука, что комбинация может оказаться слабее компонентов. Так что бездумно комбинировать тоже не стоит.
                                                                                        +1
                                                                                        [И тут мы начинаем меняться правильными фразами, к которым не подкопаешься, чтобы выглядеть умнее ^^.]
                                                                                          0
                                                                                          :)
                                                                          0
                                                                          Да, но ведь современные рекомендованные функции вывода ключа завязаны именно на большом количестве итераций обычных хэш-функций. Та же PBKDF2 — основана на большом количестве итераций для замедления ее вычисления, а она ведь хорошо исследована криптоаналитиками.

                                                                          И потом, если на каждой итерации использовать пароль, т.е. не md5(md5(md5(pass|salt))), а md5(pass|md5(pass|md5(pass|salt))), разве это также увеличит вероятность коллизий? Ведь в таком случае мы просто увеличиваем длину ключа неким значением, а не сужаем исходное множество.
                                                                            0
                                                                            разве это также увеличит вероятность коллизий?

                                                                            Неизвестно (лично мне :) ). А так в криптографии принято исходить из худшего сценария это вы, как предлагающий этот метод, должны доказать, что такой вариант не увеличивает вероятность коллизий. Причём если для md5(md5(md5(pass|salt))) доказать такое увеличение легко просто исходя из определения любой хэш функции, то для md5(pass|md5(pass|md5(pass|salt))) доказывать неувеличение нужно именно для md5 — вдруг она весьма чувствительна к последним 32 символам?
                                                                              0
                                                                              Ну функция MD5 исследована достаточно хорошо, и ее чувствительность к последним 32 символам исходной строки, вроде как, не выявлена. Хотя мы говорим, в общем-то, не о MD5, а о подходе вообще.

                                                                              А если говорить, как принято в криптографии, то я Вам так и скажу: нет оснований считать, что такой подход увеличивает вероятность коллизий ;) А теперь Вы можете искать уязвимости. И лишь когда найдете их, да еще и продемонстрируете на практике атаку на предложенный алгоритм, вот тогда те, кто такой подход уже используют, может быть, подумают, что пора бы переходить на другой метод. Обычно так бывает (взять тот же AES, в котором есть целая куча теоретических уязвимостей, пока не реализуемых на практике).
                                                                          +1
                                                                          >Что могу предпринять хакеры чтобы вскрыть пароли (будем считать что к-во раундов неизвестно)?

                                                                          Могут перед скачиванием базы создать пользователя с известным паролем, а после получения базы вычислить количество раундов.
                                                                            –1
                                                                            А если количество раундов будет зависеть от имени пользователя (или ещё и от других данных: фазы луны в момент регистрации, высоты горы, начинающейся на первую букву имени)? И пусть эта функция также неизвестна злоумышленнику, либо же в слитой базе недостаёт данных для её вычисления.
                                                                              +3
                                                                              Ни в коем случае не предполагайте, что злоумышленник не знает ваш алгоритм. Выше писали — Security through obscurity.
                                                                          +4
                                                                          Свертка — элегантно. Остальное — эвристика. Но свертка — это да, это пять.
                                                                            0
                                                                            Вот что с людьми делает отсутствие соли :) Я правильно понял, что ваша программа добилась бы гораздо меньших результатов при случайном солении?

                                                                            Видимо панацея — медленный надёжный алгоритм + соль средних размеров. Конечно от брута пароля 874512 это не спасёт, но тратить на такой примитив от 6 часов до недели будет уже не каждый «злоумышленник». А для нормальных паролей (~= 9eA8ye03ReSHTlma), я полагаю, потребуется кластер на пару месяцев.

                                                                            Честно говоря, не понимаю, почему радужные таблицы такие медленные. Я думал это отсортированный массив вида ключ=хеш => пароль, по которому можно пройтись бинарным поиском. А бинарному поиску, поидее, плевать сколько там терабайт хешей. Их не сортируют что-ли?
                                                                              0
                                                                              Радужная таблица называется радужной не просто так, а из-за использования специального «радужного» формата, который позволяет экономить место на диске. Ну и терабайт в оперативу не положишь, а по диску даже бинарный поиск не шибко шустр.
                                                                              0
                                                                              Кстати в тему о утечках, пришло сегодня от хостера:
                                                                              Здравствуйте, уважаемый клиент.

                                                                              Уведомляем Вас о том, что нами был заменен применяемый метод шифрования паролей, в связи с чем изменены пароли к следующим FTP-входам Вашего аккаунта my_account


                                                                              Интересно, насколько это поможет и спохватились ли другие хостеры
                                                                                0
                                                                                Спасибо за ценное исследование. Означает ли вывод из него, что наиболее надёжным паролем будет являться пароль максимальной длины, сгенерированный случайным образом по максимальному множеству знаков?
                                                                                  0
                                                                                  Да, и я думаю это и раньше было известно :)

                                                                                  зато теперь можно увидеть какие пароли точно нельзя считать надежными.
                                                                                  0
                                                                                  Ключи, ключи, и еще раз боооольшие длинные ключи.
                                                                                    0
                                                                                    1. Не могли бы вы пояснить, откуда берётся минута для проверки одного хэша по радужной таблице? Казалось бы там должно быть в (длина цепочки) раз медленнее чем у вас.
                                                                                    2. Почему вы используете бинарный поиск? Ведь хэш-таблица должна быть гораздо быстрее (о(1))? Фактически, в текущем варианте вы вначале используете неполную хэш-таблицу, а затем двоичный поиск.
                                                                                    3. Ваш метод на самом деле — это и есть атака по словарю, только динамически генерируемому, так?
                                                                                      0
                                                                                      1. Если таблицы отсортированы и у них есть индекс, то найти одно значение можно за десятки миллисекунд (предполагаем, что индекс уже в памяти, а вот к конкретному месту в файле уже придется обращаться), всего таких операций на одно значение нужно 5000 (в моем случае) — дает минуту (приблизительно, т.к. сильно зависит от параметров железа, вдруг все таблицы в память влезают?).

                                                                                      2. потому что хеш таблица хорошо работает, только если она слабо заполнена (<30%), что в случае 5.7 миллионов элементов (*8 байт) требует больше памяти, чем есть на моей видяхе. А по первым результатам хеш-поиск на основном ядре при оптимальных параметрах сливает бинарному на видеокарте.

                                                                                      3. ну это и не «мой метод», просто разновидность частотного анализа, немного упрощенная для эффективной реализации.
                                                                                      0
                                                                                      Будет забавно, если применяя разнообразные методы (мне кажется значительная часть sec-аналитиков взялась за эти хеши) будут вскрыты 100% использованных паролей, несмотря на сложность и длину. Ну или хотя бы все придуманные человеком, кроме совсем уж случайных наоборов по 15-20 символов.
                                                                                        0
                                                                                        Аналогичный пост про античатовскую базу паролей был год назад:
                                                                                        habrahabr.ru/post/122633/
                                                                                        Там за 8 часов восстановили 77% паролей по MD5-хэшам.
                                                                                          0
                                                                                          Спасибо большое за статью, подчерпнул для себя несколько новых фактов.

                                                                                          Самый главный вывод, который я для себя сделал — пароли на кирилице для сайтов вне рунета будут гораздо устойчивее паролей на латинице.
                                                                                            +1
                                                                                            Неправильный вывод вы сделали.
                                                                                              0
                                                                                              Почему нет? При прочих равных, шансов, что пароль на кирилице подберут по хешу, меньше, чем такой же пароль на латинице — кирилические символы и в алфавит с меньшей вероятностью попадут, и в словарь частотных сочетаний куски кирилических паролей будут меньше попадать из-за того, что таких паролей сильно меньше.
                                                                                                0
                                                                                                Словари — это дело времени. Да и большинство людей споткнется, когда получит в руки клавиатуру без кириллической раскладки.

                                                                                                Генерируйте лучше длинные пароли, это эффективнее использования национальных символов.
                                                                                            +1
                                                                                            Ваш битовый массив — это же фильтр Блума, если я правильно понял?
                                                                                              0
                                                                                              ого, спасибо, не знал как называется. Как видно, все полезное уже давно придумали :)
                                                                                              0
                                                                                              После прочтения статьи меня посетила мысль. Скоро на просторах Сети появится единая база паролей и их различных хешей. Она будет пополняться этим и другими подобными методами после каждого крупного взлома. Через какое-то время она будет содержать, скажем, 80% всех паролей, которые кто-либо в мире использовал на каких-либо сервисах.

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

                                                                                                По-моему, это, мягко говоря, ложь. Существующие No-SQL key-value хранилища данных (например, Project voldemort) имеют гораздо большую производительность. На один запрос будет уходить гораздо меньше секунды, с учётом указанного объёма. Возможно даже десятки миллисекунд.
                                                                                                  0
                                                                                                  Читать конечно никто не заставляет, но вы ошибаетесь. Не в существовании быстрых хранилищ, а в том насколько они быстрые должны быть — десятки миллисекунд (точнее «десяток») * 5000 запросов (на один хеш) как раз и дают минуту.
                                                                                                    0
                                                                                                    Я когда о производительности радужных таблиц начал читать, тоже первым делом подумал: «О чем эти парни говорят, база данных — это же так бистро?!» Но немного почитав по теме, например, соответствующую статью в Вики, я понял, что радужная таблица — это не простая база данных типа (пароль, хэш_пароля).

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

                                                                                                  Only users with full accounts can post comments. Log in, please.