Расчёт стоимости перебора одного пароля

Ранее я указывал примерное количество символов для паролей разных стойкостей. Давайте попробуем рассчитать, какая же необходима реальная длина пароля. Сначала забудем про квантовые компьютеры. Потом, после расчётов, подумаем и насчёт них.

Расчёт по стоимости Расчёт, разумеется, крайне приблизительный. Допустим, 1 видеокарта стоит 3020 рублей при курсе доллара (на декабрь 2020 - 73 рубля), то есть 41 доллар. Число универсальных процессоров 192. То есть 41/192=0,213542 доллара за процессор (упростим до 0,2 доллара). Частота процессора 1 ГГц. Чтобы не заморачиваться, считаем, что за 32 такта процессор перебирает ровно 1 пароль (хотя, в реальности, требуется гораздо больше тактов). 1e9/32=31250000=31e6 паролей (31 миллион паролей в секунду; 1e6 означает что это 1 с 6-тью нулями; 3e7 - это 3 с 7-мью нулями, то есть 30 миллионов, 3e7=30e6 - это научная нотация чисел). Считаем, что один процессор будет работать 10 лет - это его срок службы, за который он должен себя окупить. Всего за 10 лет будет 10*365,25*24*3600=315576000 секунд, упрощая, это 320e6, то есть 320 миллионов секунд. 31e6*320e6=9,92e+15. То есть, приблизительно, 1e16 (1 и 16-ть нулей) паролей за всё его время жизни. Извлекая двоичный логарифм (можно извлечь логарифм по формуле ln(1e16)/ln(2)) получаем 2 в степени 53. То есть 53 бита пароля будет перебрано. Таким образом, за 0,2 доллара можно перебрать 53 бита ключа или пароля (это не значит, что они реально будут перебраны за 10 лет - могут и за день, нужно лишь купить больше процессоров). На самом деле перебрать можно 54-ре бита ключа. Т.к. для угадывания пароля не нужно перебирать полностью все варианты: угадывание вероятностный процесс. В среднем, угадывание происходит при переборе половины всех вариантов пароля. То есть в два раза эффективнее, чем полный перебор, а это значит, что нам нужно добавить 1 бит (как раз два раза). Однако, наши расчёты довольно неточны и эти биты мы добавлять сейчас не будем. Но вы можете добавить. Если наша информация стоит N долларов, то нам нужно обеспечить стойкость в N/0,2 раз больше. В битах это будет log2(N/0,2)=ln(N/0,2)/ln(2). Либо упрощённо, каждые 1000 раз стойкости это плюс 10 битов. Например, для миллиарда долларов будет ln(1e9/0,2)/ln(2)=32,22. То есть ещё 33 бита по формуле с логарифмами. По упрощённой формуле примерно 32 бита. Добавим 33 бита к базовой стойкости 53+33=86. Получим 86 битов. Для информации, которая стоит 1 миллион долларов, это будет 76 битов (на 10 битов меньше, по упрощённой формуле). 76/6=12,7. То есть 13 символов в пароле. Почему мы делим биты на 6-ть? Если пароль случайно сгенерированный цифролатинский (содержащий латиницу обоих регистров и цифры), то всего у нас примерно 27 букв верхнего регистра, 27 нижнего регистра и 10 цифр. Всего 27+27+10=64 вариантов символа. Это 2 в степени 6. То есть один символ даёт 6 битов информации (2^6 вариантов). 6 битов стойкости. В словарных паролях на одно слово может приходится 6-9 битов в худшем случае, 10-12 битов в лучшем случае (не очень частые слова с разными окончаниями не из одного текста). Таким образом, если нам нужно обеспечить 76 битов, то это 76/6 символов (на каждый символ по 6 битов). Это на миллион долларов. Рекомендуется брать запас в 7-10 битов (на квантовые компьютеры запас берётся перед удвоением длины). Стоимость человеческой жизни в технике обычно примерно равна 1 миллиону долларов (примерный доход человека за всю его жизнь или стоимость выращивания нового ребёнка). Давайте попробуем рассчитать стойкость пароля, который нужен, чтобы защитить ваши самые сокровенные, но не имеющие стоимости, тайны (если вы, конечно, не олигарх). Мы уже рассчитали, что на миллион долларов нужно 76 битов (13-ть символов, 26 для квантовых компьютеров). Возьмём запас 10 битов, то есть 76+10=86. 86/6=14,33... . То есть получаем 15 символов (29 если у противника есть квантовый компьютер). Эта методика даёт результат для злоумышленника, который будет приобретать вычислительные ресурсы, то есть у него их нет "забесплатно". Разумеется, расчёт очень приблизительный, но, в целом, даёт верную картину.

Если злоумышленник захочет прослушивать всех людей на земле, то стойкость пароля можно уменьшить на количество людей, которые шифруют переписку. Например, если в стране шифруют переписку 20 миллионов человек, то log2(20e6)=24,25 битов стойкости. То есть ключ шифрования для бытового шифрования (шифрование неважной информации) может снизиться до 86-24,25=61,75, то есть 62-х битов. В данном случае я считаю, что фирма выделила миллиард долларов на расшифровку всей переписки. Так как грядут квантовые компьютеры, домножим это на 2, получим 62*2=124 бита. То есть для бытового шифрования (неважной информации) достаточно 128-ми битов ключа шифрования для защиты от массового прослушивания переписки даже с квантовыми компьютерами. Достаточно до 4*2=8 лет, то есть 2020+8=2028 год. Как мы понимаем, АНБ такую переписку прочитает как только появится квантовый компьютер.

Расчёт по эвристике Считаем, что в 80-ом году для серьёзных применений было допустимо применять 80 битный ключ (или пароль). Для менее серьёзных - 70. Для несерьёзных - 60. Для бытовой обфускации против массового отслеживания даже 40-50 битов. Каждые 2 года стойкости должна расти на 1 бит. По худшей эвристике, стойкость должна расти на 1 бит за год. Давайте возьмём средние по серьёзности применения - 70 битов. Если пароль должен быть стоек до 2030 года, то считаем 2030-1980=50 лет. За 2 года 1 бит: 50/2=25 битов. Получаем 70+25=95 битов. 95/6=15,83... . Примерно 16 символов. Как видим, пароль по этой эвристике требуется чуть более стойкий (примерно на 1,5 символа). Если же брать 1 год - 1 бит, то будет совсем плохо. 70+50=120 битов. То есть 20 символов. С квантовыми компьютерами умножаем, опять, на 2 (40 символов, о боже!).

Расчёт по общему количеству процессоров в мире К сожалению, рассчитать общее количество процессорных ядер в мире затруднительно. Иногда считают производительность распределённых сетей типа bitcoin и т.п. Давайте прикинем количество ядер в мире. Будем считать, что у каждого человека есть видеокарта на 512 универсальных процессоров, ещё 8 процессорных ядер в центральном процессорном устройстве, ещё 8 ядер в мобильных устройствах. "Умные" холодильники, лампочки и т.п. пока считать не будем. 512 ядер по 1 ГГц, ещё 8 ядер по 3 ГГц, и ещё 8 ядер по 1 ГГц. Приведём всех к общему знаменателю на 3 ГГц: (512+8)/3 + 8 = 181 процессорное ядро на 3 ГГц. 7 миллиардов людей. Пусть у всех будет именно такая комбинация. Тогда 7e9*181=1,267e12 процессорных ядер всего в мире. Пусть, хакеры АНБ взломали все компьютеры и держат их под контролем, используя вообще все их ресурсы. Опять же, 32 такта на один пароль, всего 1,267e12/32=4e10 паролей на все процессоры в мире на один такт. Допустим, тактовая частота 3e9, то есть 4e10*3e9=1,2e+20 паролей за секунду. Приблизительно 32e6 секунд в году. 1,2e+20*32e6=3,84e+27 вариантов паролей за год. Примерно 91,633 бита за год. То есть пароль должен быть со стойкостью 92 бита, если его будут перебирать 1 год (16 символов). За два года добавится ещё один бит. За 10 лет - 5 битов. Более 10-ти лет придётся уже выбирать пароль в 17-ть символов. Так как 97/6=16,16... , а округляем мы всегда в большую сторону, чтобы соблюсти минимальную стойкость. Значит, 16,1666 после округления это - 17 символов. То есть по данной методике, пароль, который будет стоек 1 год в 2020-ом году - это 16 символов. Который будет стоек до 2030-ого года - 17 символов. 17*2=34 символа с квантовыми компьютерами.

Квантовые компьютеры и длина паролей

Квантовые компьютеры обещают принципиальное увеличение производительности задач по перебору вариантов, поэтому длина паролей в эру квантовых компьютеров возрастёт в два раза. Так как они могут находить коллизии (парадокс дня рождения и т.п.) то стойкость паролей и ключей шифрования может упасть вдвое. То есть пароль, стойкостью 100 битов будет иметь стойкость всего лишь 100/2=50 битов. Это совсем не радует, т.к. влечёт за собой существенное повышение длин паролей, если информация о возможностях квантовых компьютеров верна. Самое злобное то, что удваивать придётся, прежде всего, стойкость именно криптографических паролей, которые, обычно, люди помнят наизусть. Какое здесь можно предложить решение? Дело в том, что используемый в квантовых компьютерах алгоритм Гровера, видимо, не способен совмещать словарный перебор с перебором вариантов пароля. Впрочем, и здесь могут быть сюрпризы. Однако, для затруднения можно пытаться в большей степени использовать удлинители паролей. Так как их перебор будет словарным, а перебор случайно сгенерированной части - квантовым, то потребуется более сложная и дорогостоящая система. В таком случае, половина пароля может состоять из удлинителя, даже не очень стойкого, а ещё половина - случайно сгенерированные символы. То есть, например, 25 символов случайных, и ещё 25 символов удлинителя. В таком случае, существуют следующие варианты: 1. Квантовый компьютер будет перебирать весь пароль целиком. Для 50-ти символов это будет стойкость, эквивалентная 25-ти символам. Даже если удлинитель не стойкий. 2. Специалисты найдут способ алгоритмизировать перебор паролей в квантовом компьютере с учётом словарного перебора. Тогда паролям придётся несладко. Однако, вероятность этого не такая высокая. 3. Обычный компьютер будет перебирать удлинитель, а квантовый компьютер - случайную часть пароля. В таком случае, стойкость удлинителя для словарного перебора сложится со стойкостью случайной части пароля. Например, если удлинитель длиной 25 символов состоит из 5 слов, по 10 битов на каждое слово, плюс 25 символов случайно сгенерированных (по 6 битов на каждый символ), то получим 5*10+25*6/2=125 битов. То есть эквивалент примерно 125/6=20,83 символов стойкости без квантовых компьютеров. Пояснение: в расчёте 25*6 делим на два в связи с тем, что квантовые компьютеры снижают стойкость пароля в 2 раза по его длине. То есть 25 символов для квантового компьютера всего лишь 12,5. 4. Квантовый компьютер будет перебирать хеш пароля. Тогда стойкость будет зависеть не от длины пароля, а от длины хеша и размера его внутреннего состояния. В таком случае, пароль можно будет не удлинять. Как видим, удлинители тоже не сильно помогают решению, но, всё же, осложняют перебор, а запомнить их чуть проще. В первом же варианте даже простой удлинитель сильно повысит стойкость пароля. Так что, если ваши пароли должны быть стойкими к квантовым вычислениям, стоит в любой криптографический пароль добавлять удлинитель. Основная опасность здесь именно для паролей к криптографии, а также для иных паролей, которые возможно подбирать оффлайн (например, украденные хеши паролей после взлома некоторого сайта).

Так ли грядут гадкие кванты?

В настоящее время квантовые компьютеры не так страшны, как кажутся. Например, для экспериментального квантового компьютера на 50 кубитов число аппаратно запутанных между собой кубитов достигло всего 6 (на 2020-ый год). Для того, чтобы запутать большее количество кубитов, необходимо делать уже логические квантовые операции. То есть тратить дополнительные кубиты. На одно такое запутывание может прийтись и пара десятков лишних кубитов. Для перебора криптографического пароля, длиной в N битов, нужно как минимум N запутанных кубитов. Поэтому, если вы слышите, что в квантовом компьютере 128 кубитов (3-его декабря 2020-ого года о таком объявила IBM; новости о квантовых компьютерах на английском) не спешите волноваться: возможно, запутать он может значительно меньше кубитов. А значит, пароли длиной 128-мь битов всё ещё неприкосновенны (и даже пароли значительно меньшей длины :) ). Проблемы квантовых вычислений таковы, что даже эти биты постоянно сбрасываются (из-за декогеренции). Так, рекорд на 2020-ый год составляет 148,5 мкс (микросекунд; источник). То есть весь перебор должен длиться порядка одной десятитысячной секунды. Если квантовый компьютер не успеет за это время - прости-прощай. Расчёт не удался. Так что даже если хватает запутанных кубитов, это ещё не значит, что они успеют перебрать пароль. Чтобы повысить время когерентности, опять же, нужны специальные алгоритмы коррекции ошибок. Пока что речь идёт о том, что для коррекции одного логического кубита нужны десятки тысяч физических кубитов. То есть квантовый компьютер, способный перебирать пароль, длиной в 76 битов, должен будет иметь не 76-ть кубитов, а 76*10000 = 760 000. Пока это очень далеко от обещанного. При этом, чем больше физических кубитов, тем быстрее наступает их декогеренция (из-за того, что каждый из них может провзаимодействовать с внешней средой даже в высоком вакууме). Тактовая частота квантовых компьютеров нигде не афишируется. Видимо, учёных этот вопрос пока совершенно не интересует. Однако, как известно, чем меньше размеры, тем ниже инерция, а значит, и тем выше частоты. Для неквантовых компьютеров, основанных на аналогичных размерах, тактовая частота может достигнуть 770 ГГц. То есть в пару сотен раз выше, чем сейчас у обычных компьютеров. Если это предположение верно, то это плохо. Есть и хорошая новость. Квантовые компьютеры, в любом случае, дороже, требуют криогенных устройств и так далее. Также само считывание результата квантовых вычислений может занять очень продолжительное время. Реально мы даже не видим, что учёные говорят о решении каких-либо практических задач на квантовых компьютерах. Хотя могли бы и сделать демонстрацию. Значит, с этим есть сложности. Давайте рассчитаем, что время когеренции квантового компьютера составляет 1 секунду. Пусть, за каждый такт он выполняет полный цикл алгоритма Гровера (что явная фантастика). Тогда, за эту секунду он выполнит 770e9 операций. Это примерно 40 битов сложности. То есть, такой компьютер переберёт пароль в 40*2 битов длиной, то есть пароль в 80-т битов длиной при наличии 80-ти кубитов минимум. Напомню, при современном времени декогеренции они могут подобрать примерно в 10 тысяч раз меньше. То есть, примерно на 13 битов меньше - 67 битов. Однако, если у квантового компьютера уже есть хеш пароля размером 512-ть битов, то обращать ему придётся порядка 1024-х битов или более. А значит, ему потребуется как минимум 1024 кубита даже на обращение односимвольного пароля. То есть вместо 80-ти кубитов ему потребуется минимум 1024 кубита. Как видим, сложность перебора пароля на квантовом компьютере зависит и от сложности доступного ему хеша пароля. В худшем случае, даже пароль в один символ ему придётся, всё равно, перебирать также, как и пароль в 64-ре символа. Хотя это не обязательно.

Вывод

Вывод по квантовым компьютерам следующий: либо пароли делайте в 2 раза длиннее, либо, хотя бы, удлиняйте пароли в два раза удлинителями, пусть даже и простыми. Плюс к этому, если есть возможность, используйте как дополнение к паролю ключевые файлы, если вы их можете защитить от попадания в руки злоумышленника (и не боитесь эти файлы потерять при форс-мажорных событиях типа обысков, пожаров, краж и так далее). Перебор пароля производится через обращение хеша или функции шифрования. А значит, сложность такого перебора будет зависеть не только от длины пароля, но и от длины хеша и размера его внутреннего состояния (битности функции сжатия или ёмкости губки). Значит, всегда стоит использовать криптографические алгоритмы с максимальной длиной ключа (хеша). Предпочитать алгоритмы, основанные на большой битности внутренних состояний, например, алгоритмы, основанные на концепции Sponge (губка) или Duplex. Так квантовому компьютеру потребуется большее число кубитов.

Шифрование данных.