Идея на тему генерации и запоминания надёжных паролей

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

Требования к паролю

Во-первых надо понять, каким требованиям должен отвечать хороший пароль:

1. Должен быть трудноподбираемым. Он должен быть достаточно длинным и содержать символы разных типов (большие/маленькие буквы, цифры, спецсимволы), чтобы нельзя было подобрать полным перебором. Должен быть неподбираемым по словарю, словарю с комбинациями и мутациями.
2. Должен быть уникальным для каждого аккаунта, так что компрометация пароля от одного аккаунта, не приведёт к несанкционированному доступу к другим аккаунтам.
3. Должен периодически меняться.

Сначала я подумал, что можно делать так: запомнить одну случайную последовательность символов и для каждого сайта пристыковывать к ней строку, специфическую именно для данного сайта. Например брать каждый третий символ адреса сайта. Пароль на хабр (вводится на id.tmtm.ru) будет выглядеть таким образом: «Q9y:y>1W.tr», где «Q9y:y>1W» — строка, используемая на всех сайтах, а ".tr" — добавка, специфичная именно для id.tmtm.ru. Фактически здесь две секретные составляющие: сам алгоритм генерации и случайная строка. Для получения пароля надо знать обе. Пароль вполне себе стойкий к перебору, можно периодически менять случайную стоку — требования (1) и (3) выполняются. Проблема в том, что об обеих составляющих можно относительно легко догадаться, зная пароли от пары сайтов.

Общий алгоритм

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

• Мастер-пароль — секретная строка долговременного использования, должен быть достаточно сложным для противостояния перебору на любом кластере ;-)
• Сайт — адрес сайта/имя компьютера — куда логинимся
• Номер версии пароля для этого сайта — нужен в том случае, если потребуется сменить пароль для этого конкретного сайта.
• Логин — может пригодиться если есть несколько аккаунтов на одном сайте/компьютере (так что пароли от разных учёток совпадать не будут). Так же логин работает как соль для защиты от перебора по радужным таблицам.

Про таблицы

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

Эти данные подаём на вход хэш-функции, выход рассматриваем как длинное целое число, кодируем его в 95ричной системе счисления, получаем псевдослучайную строку длиной 25 символов для 160 битной хэш-функции. Старший символ лучше откинуть, т.к. он может принимать далеко не все значения (точнее — только 5 значений). Получаем 24 псевдослучайных симовола.

Точнее про распределение символов

На самом деле распределение вероятностей по возможным значениям символов там будет не совсем равномерным за счёт того, что 2^160 не является степенью 95. Получится, что часть символов будет появляться с бОльшей вероятностью, чем другие. Но эта неравномерность будет очень быстро (экспоненциально) убывать от старших разрядов к младшим. Так (в предположении что хэш-функция идеальная и все значения её выхода равновероятны) на 24ой (старшей) позиции символы будут появляться с вероятностями 1.158011% и 1.051510%. На 23-ей позиции — с вероятностями 1.053724%, 1.051753% и 1.051510%. На 22-ой позиции — с вероятностями 1.052652%, 1.052639% и 1.052629%. Дальше разница будет ещё меньше. Для паролей такие отклонения от равномерного распределения значения практически не имеют.

Конкретная реализация

Тут лежит простенькая консольная программа на Python3, которая таким образом генерирует пароли.
Можно указать один из параметров:
-m — сгенерировать много паролей из одного мастер-пароля (чтобы не вводить мастер пароль несколько раз);
-r — сгенерировать случайный пароль (источник случайности — системные генераторы случайных последовательностей и строка, вводимая с клавиатуры);
без параметров — сгенерировать один пароль и выйти.
Сразу после ввода мастер-пароля программа выводит 2х байтный хэш от мастер-пароля. Это нужно для контроля правильности ввода. Если хэш кажется незнакомым, значит мастер-пароль введён неправильно.
В этой программе используются 2 разные хэш-функции (ripemd160 и sha512) и несколько более замороченный порядок скармливания им исходных данных, чем просто конкатенация строк. Использование двух функций — ход для параноиков — позволяет (насколько я вижу) сохранить криптостойкость алгоритма даже при обнаружении очень серьёзной уязвимости в одной из них (понятно, что это практически невероятно, но накладные расходы на такую «параною» тоже минимальны).

Точный алгоритм

SitePwd = ripemd160(ver2str(version) + sha512_hex(ver2str(version) + master_password + site + login) + site)
Все текстовые строки кодируются UTF-8; ' + ' означает конкатенацию строк.
Функция ver2str(n) возвращает строку, состоящую из записанных подряд n+1 последовательных чисел от n до 0, например:
ver2str(0) = '0'
ver2str(4) = '43210'
ver2str(12) = '1211109876543210'
SitePwd дальше преобразуется в длинное целое число, которое записывается в 95-ричной системе счисления. В качестве 95-ричных цифр используются символы из массива chars (всего 95 символов):

chars = "`1234567890-=\~!@#$%^&*()_+|qwertyuiop[]QWERTYUIOP{}asdfghjkl;'ASDFGHJKL:"zxcvbnm,./ZXCVBNM<>? "

(Без внешних кавычек, последний символ — пробел)
24 младших разряда полученной записи, выведенные в порядке слева на право от младших к старшим, и являются сгенерированным паролем.

Практически проблемы при использовании таких паролей

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

Сравнение с «запоминалками» паролей

Плюсы такого алгоритма по сравнению с «запоминалками» паролей:

• Не нужно иметь под рукой базу паролей. Понадобилось на другом компьютере получить пароль — просто скачал с гитхаба программу, вбил свой мастер-пароль — и вся база паролей с собой.
• Отсутствует файл, который злоумышленник может украсть и попытаться расшифровать. Правда в хорошей запоминалке с хорошим мастер-паролем дешифрование базы паролей так же практически невероятно.
• Даже в случае получения полного доступа к вашему компьютеру (с чтением всех файлов и установкой кейлогеров) злоумышленнику ещё придётся отгадывать данные ваших аккаунтов (особенно тех, в которые с этого компьютера не заходят)
• Гарантирует использование разных и случайных паролей. И придумывать пароль каждый раз не надо.

Плюсы «запоминалок»:

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

Что дальше

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

Аналогичные программы

В комментариях подсказали что есть ещё:
MasterPassword — поделка хабравчанина FanKiLL
pwdhash.com — то же на JavaScript от коллектива из Стэнфордского университета. Есть плагины для браузеров. После хэширования пароль дополняется так, что бы проходить стандартный тест на сложность.