Генератор/валидатор паролей по результатам взлома LinkedIn

в 2:03, , рубрики: брутфорс, генератор паролей, информационная безопасность, перебор, частотный анализ, метки: , , , ,

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

Надежность vs доверие

Изначально хотел оформить идею как некий Веб-сервис, однако одумался; грамотный пользователь должен сперва задуматься, куда может попасть его возможный пароль, а для сетевых технологий — этот вопрос без очевидного ответа, и есть все поводы не доверять подобным сервисам вообще. Вы только закончили ввод пароля, а AJAX'ом он уже утянут и сохранен на сервере. Нет, уж, спасибо.

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

Поэтому сам предлагаю программу в исходных кодах (на C#, исходя из того, что на разработку не хотелось тратить больше пары часов) и настоятельно рекомендую собирать ее из исходников.

Генерация паролей

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

Для преобразования есть довольно-таки стандартное решение, сводящееся к вызову хеш-функции, как эффективной свертки пула энтропии (то есть неких случайных значений):

        string generatePassword(string charset, int length)
        {
            byte[] result;
            SHA1 sha = new SHA1CryptoServiceProvider();
            result = sha.ComputeHash(seed); // <--- текущий пул энтропии

            // create password
            StringBuilder output = new StringBuilder();
            for (int i = 0; i < result.GetLength(0) && output.Length < length; i++)
                output.Append(charset[result[i] % charset.Length]);

            // update seed
            for (int i = 0; i < result.GetLength(0); i++)
                addToSeed(result[i]);

            return output.ToString();
        }

Сами случайные значения можно набирать разными способами:

  • аппаратные решения,
  • окружение системы (значения в памяти, свойства процессов),
  • получение данных от интернет-сервисов,
  • взаимодействие с пользователем.

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

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

        void handleMouseData(int x, int y)
        {
            /* store information in seed array */
            addToSeed(x);
            addToSeed(y);
            addToSeed(ticks());
        }

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

        int ticks()
        {
            long timer;
            if (QueryPerformanceCounter(out timer) == false)
            {
                // high-performance counter not supported
                throw new Win32Exception();
            }

  /* ignore significant bits due its stability - we prefer using fast-changing low bits only */
            return (int)timer;
        }

Счетчик QueryPerformanceCounter имеет разное разрешение в зависимости от системы, а его значение меняется в зависимости от текущей загрузки процессора, количества процессов, факта context switch. Одна величина, которая, хоть и имеет прогнозируемый рост, но в конкретных числах его выразить очень сложно.

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

Генератор/валидатор паролей по результатам взлома LinkedIn

Оценка времени на взлом

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

  • скорость функции проверки,
  • мощность алфавита,
  • количество символов.

Мощность алфавита — это минимальное (с разумным критерием описания) множество, содержащее символы конкретного пароля. Как правило это наборы вида:

  • маленькие буквы,
  • заглавные буквы,
  • цифры,
  • спецзнаки.

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

double bruteforceCombinations = Math.Pow(26 * upper + 26 * lower + 10 * numeric + specials.Length * special, pwd.Length);

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

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

И теперь, собственно, главное — оценка времени атаки декомпозицией.

Это не так сложно, необходимо просто вычислить минимальное разбиение нашего пароля на слова некоторого словаря релевантных комбинаций (достаточно часто встречающиеся подстроки) == длина пароля. И вычислить «мощность» словаря == количество слов в нем. Итоговое количество комбинаций — все так же «мощность» в степени длины.

Если наш пароль вида «Good123Password» — то он раскладывается на «Good», «123», «Password» — которые очень распространены по отдельности и время на перебор всего лишь «в три раза больше, чем почти ничего».

Вопрос, конечно, заключается в качестве такого словаря, но опять же, любой вариант — лучше чем ничего. Я приложил к программе словарь, полученный после аудита на LinkedIn, составленный из самых частых комбинаций, встреченных в 2.5 миллионах найденных паролей. Сам словарь — всего 40 килобайт.

Результаты

Ссылка на программу и исходники: dl.dropbox.com/u/243445/md5h/pwdmaster.zip

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

Автор: sic

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js