Стандартный набор символов паролей, которые можно набрать на клавиатуре, используя английские буквы и небуквенные символы, состоит из $D=94$ символов. При длине пароля $L$ символов и предположении равновероятного использования символов энтропия паролей равна
Клод Шеннон (англ. Claude Elwood Shannon), исследуя энтропию символов английского текста, изучал вероятность успешного предсказания людьми следующего символа по первым нескольким символам слов или текста. В результате Шеннон получил оценку энтропии первого символа $s_1$ текста порядка $H(s_1) \approx 4{,}6$–$4{,}7$ бит/символ и оценки энтропий последующих символов, постепенно уменьшающиеся до $H(s_9) \approx 1{,}5$ бит/символ для 9-го символа. Энтропия для длинных текстов художественных произведений получила оценку $H(s_\infty) \approx 0{,}4$ бит/символ.
Статистические исследования баз паролей показывают, что в англоязычных текстах наиболее часто используются буквы «a», «e», «o», «r» и цифра «1».
NIST (Национальный институт стандартов и технологий США, англ. National Institute of Standards and Technology) использует следующие рекомендации для оценки энтропии паролей, создаваемых людьми.
Для оценки энтропии пароля нужно сложить энтропии символов $H(s_i)$ и сделать дополнительные надбавки, если пароль удовлетворяет тестам на композицию и отсутствует в словаре.
| 4ex | ||||
| 4 | 10 | 14 | 16 | 26.3 |
| 6 | 14 | 20 | 23 | 39.5 |
| 8 | 18 | 24 | 30 | 52.7 |
| 10 | 21 | 26 | 32 | 65.9 |
| 12 | 24 | 28 | 34 | 79.0 |
| 16 | 30 | 32 | 38 | 105.4 |
| 20 | 36 | 36 | 42 | 131.7 |
| 24 | 40 | 40 | 46 | 158.0 |
| 30 | 46 | 46 | 52 | 197.2 |
| 40 | 56 | 56 | 62 | 263.4 |
В таблице [tab:password-entropy] приведена оценка NIST на величину энтропии пользовательских паролей в зависимости от их длины, и приведено сравнение с энтропией случайных паролей с равномерным распределением символов из набора в $D=94$ символов клавиатуры. Вероятное число попыток для подбора пароля составляет $O(2^H)$. Из таблицы видно, что по критериям NIST энтропия реальных паролей в 2--4 раза меньше энтропии случайных паролей с равномерным распределением символов.
Пример. Оценим общее количество существующих паролей. Население Земли – 7 млрд. Предположим, что всё население использует компьютеры и Интернет, и у каждого человека по 10 паролей. Общее количество существующих паролей – $7 \cdot 10^{10} \approx 2^{36}$.
Имея доступ к наиболее массовым интернет-сервисам с количеством пользователей десятки и сотни миллионов, в которых пароли часто хранятся в открытом виде из-за необходимости обновления ПО и, в частности, выполнения аутентификации, мы:
Даже если пароль хранится в защищённом виде, то при вводе, как правило, он в открытом для сервиса виде пересылается по Интернету, и все преобразования пароля для аутентификации осуществляет интернет-сервис, а не веб-браузер. Следовательно, интернет-сервис периодически имеет доступ к исходному паролю.
В 2002 г. был подобран ключ для 64-битного блочного шифра RC5 сетью персональных компьютеров distributed.net, выполнявших вычисления в фоновом режиме. Суммарное время вычислений всех компьютеров – 1757 дней, было проверено 83 пространства всех ключей. Это означает, что пароли с оценочной энтропией менее 64 бит, то есть все пароли до 40 символов по критериям NIST, могут быть подобраны в настоящее время. Конечно, с оговорками на то, что 1) нет ограничений на количество и частоту попыток аутентификаций, 2) алгоритм генерации вероятных паролей эффективен.
Строго говоря, использование даже 40-символьного пароля для аутентификации или в качестве ключа блочного шифрования является небезопасным.
Приведём различные оценки числа паролей, выбираемых людьми. Чаще всего такие пароли основаны на словах или закономерностях естественного языка. В английском языке всего около $1\ 000\ 000 \approx 2^{20}$ слов, включая термины.
Используемые слоги английского языка имеют вид V, CV, VC, CVV, VCC, CVC, CCV, CVCC, CVCCC, CCVCC, CCCVCC, где C – согласная (consonant), V – гласная (vowel). 70 слогов имеют структуру VC или CVC. Общее число слогов $S = 8000 \dots 12000$. Средняя длина слога – 3 буквы.
Предполагая равновероятное распределение слогов английского языка, для числа паролей из $r$ слогов получим верхнюю оценку
Средняя длина паролей составит:
Теперь предположим, что пароли могут состоять только из 2--3 буквенных слогов вида CV, VC, CVV, VCC, CVC, CCV с равновероятным распределением символов. Подсчитаем число паролей $N_2$, которые могут быть построены из $r$ таких слогов. В английском алфавите число гласных букв $n_v = 10$, согласных $n_c = 16$, $n = n_v + n_c = 26$. Верхняя оценка числа $r$-слоговых паролей:
Средняя длина паролей:
Как видно, в обоих предположениях получились одинаковые оценки для числа и длины паролей.
Подсчитаем верхние оценки числа паролей из $L$ символов, предполагая равномерное распределение символов из алфавита мощностью $D$ символов: a) $D_1 = 26$ строчных букв, б) все $D_2 = 94$ печатных символа клавиатуры (латиница и небуквенные символы):
| 3.5ex | |||
| 6 | $2^{26}$ | $2^{28}$ | $2^{39}$ |
| 9 | $2^{39}$ | $2^{42}$ | $2^{59}$ |
| 12 | $2^{52}$ | $2^{56}$ | $2^{79}$ |
| 15 | $2^{65}$ | $2^{71}$ | $2^{98}$ |
| 21 | $2^{91}$ | $2^{99}$ | $2^{137}$ |
| 39 | $2^{169}$ | $2^{183}$ | $2^{256}$ |
Из таблицы [tab:password-number] видно, что при доступном объёме вычислений в $2^{60}$ – $2^{70}$ операций, пароли вплоть до 15-ти символов, построенные на словах, слогах, изменениях слов, вставках цифр, небольшом изменении регистров и других простейших модификациях, в настоящее время могут быть найдены полным перебором как на вычислительном кластере, так и на персональном компьютере.
Для достижения криптостойкости паролей, сравнимой со 128- или 256-битовым секретным ключом, требуется выбирать пароль из 20 и 40 символов соответственно, что, как правило, не реализуется из-за сложности запоминания и возможных ошибок при вводе.
В схемах аутентификации по паролю иногда используется хеширование и хранение хеша пароля на сервере. В таких случаях применима словарная атака или атака с применением заранее вычисленных таблиц для ускорения поиска.
Для нахождения пароля, прообраза хеш-функции, или для нахождения ключа блочного шифрования по атаке с выбранным шифртекстом (для одного и того же известного открытого текста и соответствующего шифртекста) может быть применён метод перебора с балансом между памятью и временем вычислений. Самый быстрый метод радужных таблиц (англ. rainbow tables, 2003 г., [82]) заранее вычисляет следующие цепочки и хранит результат в памяти.
Для нахождения пароля, прообраза хеш-функции $H$, цепочка строится как
где $R_i(h)$ – функция редуцирования, преобразования хеша в пароль для следующего хеширования.
Для нахождения ключа блочного шифрования для одного и того же известного открытого текста $M$ таблица строится как
где $R_i(c)$ – функция редуцирования, преобразования шифртекста в новый ключ.
Функция редуцирования $R_i$ зависит от номера итерации, чтобы избежать дублирующихся подцепочек, которые возникают в случае коллизий между значениями в разных цепочках в разных итерациях, если $R$ постоянна. Радужная таблица размера $(m \times 2)$ состоит из строк $(M_{0,j}, M_{t+1,j})$ или $(K_{0,j}, K_{t+1,j})$, вычисленных для разных значений стартовых паролей $M_{0,j}$ или $K_{0,j}$ соответственно.
Опишем атаку на примере нахождения прообраза $\overline{M}$ хеша $\overline{h} = H(\overline{M})$. На первой итерации исходный хеш $\overline{h}$ редуцируется в сообщение $\overline{h} \xrightarrow{R_t(\overline{h})} \overline{M}_{t+1} $ и сравнивается со всеми значениями последнего столбца $M_{t+1,j}$ таблицы. Если нет совпадения, переходим ко второй итерации. Хеш $\overline{h}$ дважды редуцируется в сообщение $\overline{h} \xrightarrow{R_{t-1}(\overline{h})} \overline{M}_t \xrightarrow{H(\overline{M}_t)} \overline{h}_t \xrightarrow{R_t(\overline{h}_t)} \overline{M}_{t+1}$ и сравнивается со всеми значениями последнего столбца $M_{t+1,j}$ таблицы. Если не совпало, то переходим к третьей итерации и т. д. Если для $r$-кратного редуцирования сообщение $\overline{M}_{t+1}$ содержится в таблице во втором столбце, то из совпавшей строки берётся $M_{0,j}$, и вся цепочка пробегается заново для поиска искомого сообщения $\overline{M}: ~ \overline{h} = H(\overline{M})$.
Найдём вероятность нахождения пароля в таблице. Пусть мощность множества всех паролей равна $N$. Изначально в столбце $M_{0,j}$ содержится $m_0 = m$ различных паролей. Предполагая наличие случайного отображения с пересечениями паролей $M_{0,j} \rightarrow M_{1,j}$, в $M_{1,j}$ будет $m_1$ различных паролей. Согласно задаче о размещении,
Вероятность нахождения пароля:
Чем больше таблица из $m$ строк, тем больше шансов найти пароль или ключ, выполнив в наихудшем случае $O \left( m \frac{t(t+1)}{2} \right)$ операций.
Примеры применения атаки на хеш-функциях $\textrm{MD5}$, $\textrm{LM}$ (т. е. $\textrm{DES}_{\textrm{Password}} (\textrm{const})$) приведены в таблице [tab:rainbow-tables].
| 2ex | ||||||
| A–Z | $2^{33}$ | 610 MB | 6 с | |||
| $2 \times 56$ | 14 | A–Z, 0-9 | $2^{36}$ | 3 GB | 15 с | |
| все | $2^{43}$ | 64 GB | 7 мин | |||
| 8 | A-Z, 0-9 | $2^{41}$ | 36 GiB | - | 4 мин | |