Как создать действительно случайный и доказуемо безопасный пароль

https://medium.com/@flimshaw/how-to-make-an-actually-random-password-5c0da8fc1f21
  • Перевод


Менеджеры паролей, такие как KeePass, 1Password и множество других, в значительной степени решают эту проблему. С их помощью вы можете генерировать уникальный и безопасный пароль для каждого сайта, который вы посещаете. Но такой менеджер защищен ровно настолько, насколько безопасен главный пароль, который вы используете для доступа к нему. Вы должны быть уверены, что его достаточная случайность и неугадываемость подтверждена количественными измерениями, а не только тем, что вы воспринимаете его случайным по причине наличия нескольких цифр или восклицательных знаков. Если нам требуется истинная случайность, нам понадобится кое-что специальное.

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



Бросание игральной кости позволяет получить случайное число от 1 до 6, которое даёт нам 2,58 бита информации.

Основоположник теории информации Клод Шеннон определил информацию, как снятую неопределенность. Точнее сказать, получение информации — необходимое условие для снятия неопределенности. Неопределенность возникает в ситуации выбора. Задача, которая решается в ходе снятия неопределенности — уменьшение количества рассматриваемых вариантов (уменьшение разнообразия), и в итоге выбор одного соответствующего ситуации варианта из числа возможных. Снятие неопределенности дает возможность принимать обоснованные решения и действовать. В этом управляющая роль информации.

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



В действительности нет нецелых, поэтому мы всегда округляем до ближайшего бита. В этом случае нам нужно 3 бита для хранения числа от 1 до 6, но на самом деле мы можем хранить и от 0 и до 7:

000 - 0
001 - 1
010 - 2
011 - 3
100 - 4
101 - 5
110 - 6
111 - 7


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

По сути, переменная с n-ным количеством битов может иметь 2^n (2 в степени n) возможных значений. Поскольку байт состоит из 8 битов, то он может иметь 2^8 (256) возможных значений.

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

Компьютеры имеют ограниченное количество свободной памяти. Каждый раз, когда мы объявляем переменную, небольшая часть этой свободной памяти выделяется до тех пор, пока переменная существует. Поскольку современные компьютеры имеют много памяти, то в большинстве случаев – это не проблема, особенно когда в программе всего лишь несколько переменных. Тем не менее, для программ, которые требуют большого количества переменных (например, 100 000), разница между использованием 1-байтовых или 8-байтовых переменных может быть значительной.


Так видеоигра The Legend of Zelda, выпущенная в 1987 году была 8-битной и имела ограничение для значений переменных равное 255.

Я хотел бы, чтобы энтропия для подбора моего пароля была по крайне мере 128 бит. По большинству исследований, взлом 128-битного шифрования практически невозможен с использованием методов грубой силы менее чем за несколько миллиардов лет. Используя уравнение 2^n, мы можем хранить одно из 3.4*10³⁸ различных значений, используя 128 бит. Если бы вы могли протестировать 100 миллиардов возможных значений в секунду, все равно потребовались бы десятки триллионов лет, чтобы угадать правильный пароль. Я считаю это достаточно хорошо. 128-битный пароль почти наверняка не будет слабым звеном в цепочке вашей онлайн-безопасности.

Если каждый из наших кубиков вырабатывает 2,58 бита энтропии за один бросок, то подбрасывание пяти даст нам 12,9 бита. Если мы используем 5 игральных костей 10 раз, то мы получим 129 бит информации, а для тех кто не знает результатов создадим неопределенность или энтропию равную 129 битам.

Но как превратить эти результаты в безопасный, но запоминающийся пароль?

Я использую Diceware, который является словарем слов, индексированных с помощью результатов подбрасывания пяти игральных костей. Каждый раз, когда вы бросаете 5 кубиков (или один 5 раз), числа, которые получаются, соответствуют слову в списке. Например, если на 5 кубиках выпало 1-4-2-6-3, нужно перейти на страницу со всеми словами 14xxx и обнаружить, что 14263 соответвтует «blab». Сделайте это десять раз, и вы получите строку из десяти слов. Эти десять слов — потенциальный пароль.

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



В PDF формате одна из версий словаря доступна по ссылке тут, а тут версия на русском языке.

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

Теперь вы знаете как получить пароль, который действительно и доказуемо случайный, который не контролировался или не генерировался для вас третьей стороной и который безопасно хранится в вашем уме. Вы можете использовать его в течение нескольких лет, и это единственный пароль, который вам нужно будет знать. Даже если кто-то знает, что вы использовали 10 слов, и знаете, какой словарь вы использовали, им все равно придется «пробиваться» через 129 изнурительных бит энтропии.

Снимите шапочку из фольги и продолжайте свою жизнь. Надевать её время от времени — это нормально.

Комментарий Cloud4Y


Ранее этот вопрос поднимался на Хабрахабре в постах "Ликбез по псевдослучайным генераторам" и "Практические рекомендации по выбору паролей по результатам взлома antichat.ru".

Основные выводы, полученные автором:
1. Не столь важно, каким образом программа генератор получает пароли, сколь — откуда берет начальные данные. Если не происходит никакого интерактива вообще, следует усомниться.
2. Человек едва ли может уследить за отсутствием статистически популярных комбинаций в пароле, что подтверждается подбором 31790 паролей из 41037 MD5 хешей за 8 часов.
В связи с этим метод описанный Charlie Hoey может быть полезным особенно при отсутствии двухфакторной аутентификации.

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

1 2 3 4 5 6
1 ~! # $% ^
2 & * ( ) — =
3 + [ ] \ { }
4:; " < >
5? / 0 1 2 3
6 4 5 6 7 8 9

Вставка буквы в случайном порядке добавит около 10 бит энтропии. Всё это, конечно, предполагает секретность кодовой фразы.

P.S.
Также рекомендую статью Charlie Hoey "A Eulogy for the Headphone Jack" (Хвала «джеку»), в которой он описывает то, как, не имея страховки, сэкономил 1000 долларов на проверке собственного здоровья, собрав аппарат ЭКГ, и почему нам важно сохранить разъем для наушников и не потерять доступ к почти универсальному и свободному от лицензий порту ввода-вывода.

Эта и переведенная выше его статьи схожи идеей о том, как важно и приятно понимать то, как работает всё в окружающем нас технологическом пространстве.
Cloud4Y 94,55
#1 Корпоративный облачный провайдер
Поделиться публикацией
Комментарии 19
  • +2
    Из статьи так и не понял что мешает пароль к менеджеру паролей генерировать менеджером паролей.
    • 0
      А также что мешает подбирать пароль по словарю diceware.
      • +2

        Ну, это как раз простой вопрос. Ничего не мешает — подбирайте, число комбинаций известно.


        Слова diceware — это просто другой алфавит для пароля. Из 7776 букв.

      • 0
        We need to go deeper?

        брутфорсом одинаково успешно подбирается любой пароль. хоть скольугодно случайный.
        вобще говоря достаточно добавить в словарный пароль в произвольное место символ(или в два или в три) и вполне себе надежный будет.
        • 0
          Одинаково, с точностью до показателя экспоненты. Энтропия в пароле 40 бит — 40 показатель, 256 бит — 256 показатель.
      • 0

        Я, конечно, не очень силен в криптографии, но что-то мне подсказывает, что момент перехода от 128 бит к 10 словам из словаря сильно срезает стойкость. Фактически, количество возможных вариантов становится m^n, где n — это количество использованных слов, m — размер словаря. Т.е. если в словаре 200 000 слов (достаточно большой словарь), а вы используете для пароля 10 из них, вы получите ничто иное как 2 млн комбинаций, что просто смехотворно. Ну и в словаре априори словарные слова.


        Или я упустил что-то? Может предлагается запомнить набор слов, по ним восстановить последовательность бросков кубика, ее перевести в двоичный вид, скормить преобразователю двоичного вида в ANSII и это и будет паролем? А словарь на 600 000 слов без коллизий существует (с учетом того, что эти слова еще и запомнить нужно, а то будете вспоминать baron или все же barony)? И что делать с всякими там 0х08, вместо символа в пароле просто пикнуть?

        • +2

          Упустили. Не 200000*10, а 200000^10 = 1024e50.


          Точнее, словарь там на 7776 слов, так что там 7776^10 = 8e38 — около 2^129.

          • 0

            Да, что это со мной, в степень разучился возводить.

          • +1

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


            Если вскроется что вы используете этот алгоритм — его стойкость резко упадет до перебора словаря.


            И удачи запомнить словарь слова

            65221 yow
            65222 yp
            65223 yq
            65224 yr
            65225 ys
            65226 yt
            65231 yu
            65232 yucca
            65233 yuck
            65234 yuh
            65235 yuki
            65236 yukon


            А откидывание части слов как "незапоминаемые" так же уменьшает энтропию.

            • 0
              Думаю считать количество сочетаний из 7000 слов в словаре по 10 в пароле нужно по формуле image и это без повторов, которые могут быть, но как бы и так много
              • +1

                Порядок слов важен, так что если исключить повторы — не C_n^m, а A_n^m = n!/(n-m)!.

                • +2
                  Верно, ошибся, Вы выше правильно писали размещения с повторениями image
            • +1

              Насчёт интерактива в генераторе паролей — вообще-то на *nix система ваш интерактив уже заботливо собрала и положила в /dev/random, так что какой-то интерактив при генерации пароля — это просто для спокойствия пользователя.

                • 0
                  То же самое, только вставленное как картинка:
                  Собственно, сама картинка
                  image
                • +3
                  image
                  Обязательная картинка.
                  • 0
                    Удивлён что её не указали первым комментарием.
                    • 0
                      Ну мой комент застрял на модерации))
                  • 0
                    /шапочка из фольги режим он/
                    И весь этот старательно придуманный и запомненный пароль улетает кейлогом или скриншотом вместе с «телеметрией»
                    /шапочка из фольги режим он/

                    Такой подход мне кажется излишним по ряду причин:
                    1. ситуация с локальным хранилищем исключает квалифицированный брутфорс, это просто защита от любопытных.
                    2. если все же допускает атаку специалиста, то и шансы кейлога (или чего поинтереснее) далеко не нулевой и тут только электронный брелок для авторизаций или иная такая хардварь.
                    3. при «нелокальном» применении часто встречаю при регистрациях ограничения 4-16, 6-20 или 8-25 символов, что исключает «словарный» пароль.
                    4. велика ли вероятность, что проведя атаку по словарю + брут до 8-9 символа, кто-то оставит подбор дальше?
                    Да? Там такая важная информация — см п2.

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

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