Galina Iaroshenko

iOS-developer, ИТ-переводчица, пишу статьи и гайды. Этот рассказ о пересечении теплофизики, космологии и некоторых компьютерных наук поможет ответить на, казалось бы, безобидный вопрос: «Насколько сильным должен быть пароль, чтобы его физически было невозможно подобрать методом брутфорса?»

Данная статья является переводом. Автор: Rohan Kumar. Ссылка на оригинал.

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

Я реализовал идеи из этого поста в блоге (и не только) в программе/библиотеке MOAC.

Введение

Я понимаю, что рекомендации по надежности пароля могут устареть. По мере того как суперкомпьютеры становятся все более мощными, необходимо обновлять рекомендации по надежности паролей, чтобы противостоять более сильным атакам грубой силы. Надежные сегодня пароли могут оказаться слабыми в будущем. Какой длины должен быть пароль, чтобы его было физически невозможно взломать?

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

Задаем правильный вопрос

Давайте ограничим рамки этой статьи паролями, используемыми при шифровании/дешифровании. Злоумышленник пытается угадать пароль, чтобы что-то расшифровать.

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

Суперкомпьютер, вероятно, быстрее вашего телефона. Однако при наличии достаточного времени оба могут выполнять одни и те же вычисления. Время не является узким местом, в отличие от потребления энергии. Более эффективные компьютеры могут передавать больше битов, используя конечное количество энергии.

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

Назовем эту абсолютную единицу энергоэффективного компьютера MOAC (Mother of All Computers). Для всех классических компьютеров, состоящих из материи, выполняющих вычисления и связанных принципом сохранения энергии, MOAC представляет собой конечный, но недостижимый предел вычислительной мощности. И да, он может играть в пасьянс с потрясающей частотой кадров.

Насколько надежным должен быть ваш пароль, чтобы он был защищен от атаки грубой силы со стороны MOAC?

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программис Интересно, перейти к каналу

Количественная оценка надежности пароля

Предыдущая версия этого раздела не была ясной и точной. С тех пор я удалил проблемные биты и добавил разъяснение о солении/хэшировании (salting/hashing) в раздел «Предостережения и оценки».

Хорошей мерой надежности пароля являются биты энтропии. Биты энтропии в пароле представляют собой логарифм по основанию 2 числа догадок, необходимых для его перебора (James Massey (1994). Guessing and entropy (PDF). Proceedings of 1994 IEEE International Symposium on Information Theory. IEEE. p. 204.)

Атака грубой силы, которая выполняет 2n догадок, наверняка взломает пароль с n битами энтропии и имеет шанс один к двум взломать пароль с n+1 битами энтропии.

Для масштабирования шифрование AES-256 в настоящее время является отраслевым стандартом для надежного симметричного шифрования и использует ключи длиной 256 бит. Метод поиска ключа по 256-битному ключевому пространству противоречил бы его 2256 возможным перестановкам. При использовании шифрования AES-256 с ключом, полученным из пароля с более чем 256 битами энтропии, узким местом является энтропия ключа AES; злоумышленнику будет лучше выполнить исчерпывающий поиск ключа AES, чем атаку методом грубой силы для подбора пароля.

Для расчета энтропии пароля я рекомендую использовать такие инструменты, как zxcvbn или KeePassXC.

Проблема

Определите функцию P. P определяет вероятность того, что MOAC правильно угадает пароль с n битами энтропии после использования e энергии:

         P(n, e)     

Если P(n, e ) ≥ 1, MOAC обязательно угадает ваш пароль до того, как закончится энергия. Чем меньше P(n , e), тем меньше вероятность того, что MOAC угадает ваш пароль.

Предостережения и оценки

У меня нет сильного физического образования.

Атака грубой силы будет просто угадывать один пароль, пока не будет найден правильный. Атака грубой силы не «расшифровывает» сохраненные пароли, потому что они не должны храниться в зашифрованном виде; их обычно «солят» и «хэшируют».

При оценивании мы предпочитаем более высокие оценки, которые увеличивают вероятность подбора пароля; в конце концов, цель этого упражнения — установить верхний предел надежности пароля. Мы также упростим еще кое-что: например, MOAC не будет тратить тепло, и единственный способ, которым он может подобрать пароль, — это перебор. Сосредоточение внимания на слишком большом количестве деталей лишило бы смысла этого мысленного эксперимента.

Квантовые компьютеры могут использовать алгоритм Гровера для экспоненциального ускорения; для квантовых компьютеров с использованием алгоритма Гровера вместо этого рассчитайте P(n/2, e).

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

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

Наконец, всегда существует ненулевая вероятность того, что атака грубой силы угадает пароль с заданной энтропией. Буквальный «иммунитет» невозможен. Снижение этой вероятности до статистической незначительности делает наш пароль практически невосприимчивым к атакам грубой силы.

Вычисление

Сколько энергии MOAC использует на одно предположение во время атаки грубой силы? В контексте этого мысленного эксперимента это число должно быть нереально низким. Я остановился на kT. k представляет собой постоянную Больцмана (около 1,381×10-23 Дж/К), а T представляет собой температуру системы. Их произведение соответствует количеству тепла, необходимого для увеличения энтропии системы на 1 нат.

Для более сложного подхода к выбору хорошего значения можно использовать соотношение Планка-Эйнштейна.

Также, вероятно, лучше сделать это значение оценкой для одного бита, также нужно оценить среднее количество инвертированных битов (bit-flips), необходимых для подбора одного пароля. Если вас это беспокоит, выберите число b, которое, по вашему мнению, является хорошей оценкой для подсчета инвертированных битов, и вычислите P(n+b , e) вместо P(n, e ).

Что насчет температуры системы? Следующая информация поможет нам узнать:

1. MOAC находится где-то в обозримой части Вселенной.
2. MOAC поглотит всю наблюдаемую Вселенную.
3. Вселенная в основном пуста.

Хорошим значением T была бы средняя температура всей наблюдаемой Вселенной. Вселенная в основном пуста; T примерно равна температуре космического фонового излучения в космосе. Самая низкая разумная оценка этой температуры составляет 2,7 градуса Кельвина (Assis, A. K. T.; Neves, M. C. D. (3 July 1995). History of the 2.7 K Temperature Prior to Penzias and Wilson). Более низкая температура означает меньшее потребление энергии, меньшее потребление энергии позволяет выполнять больше вычислений, а большее количество вычислений повышает верхний предел надежности пароля.

На каждое предположение MOAC расходует kT энергии. Пусть E = общее количество энергии, которое может использовать MOAC; пусть B = максимальное количество догадок, которые MOAC может выполнить, прежде чем закончится энергия.

         B = E/(kT)     

Теперь, учитывая максимальное количество паролей, которые MOAC может угадать B, и биты энтропии в нашем пароле n, мы получаем уравнение вероятности того, что MOAC угадает наш пароль:

         P(n,B) = B/2ⁿ     

Подставьте наше выражение для B:

         P(n,E) = E/(2ⁿkT)     

Вычисление массы-энергии наблюдаемой Вселенной

MOAC может использовать всю массу-энергию наблюдаемой Вселенной (Примечание: предполагалось, что MOAC 2 сможет потреблять другие источники энергии, такие как темная материя и темная энергия. К сожалению, у Intergalactic Business Machines закончились средства, поскольку все их предыдущие средства, состоящие из материи, были поглощены исходным MOAC). Просто поместите наблюдаемую вселенную в присоединенную печь со 100% КПД, включите горелку и выработайте энергию для компьютера. Возможно, вам придется попросить друга о помощи.

Только сколько это энергии? Формула эквивалентности массы и энергии довольно проста:

         E = mc²     

Мы пытаемся найти Е и знаем, что с, скорость света, равна 299 792 458 м/с. Остается m. Какова масса наблюдаемой Вселенной?

Расчет критической плотности наблюдаемой Вселенной

Критическая плотность — это наименьшая средняя плотность вещества, необходимая для того, чтобы почти полностью остановить расширение Вселенной. Еще немного плотнее, и расширение прекратится; меньше, и расширение никогда не остановится.

Пусть D = критическая плотность наблюдаемой Вселенной и V = объем наблюдаемой Вселенной. Масса есть произведение плотности на объем:

         m = DV     

Мы можем получить значение D, решив его в уравнениях Фридмана:

         D = 3Hₒ²/(8πG)     

Где G — гравитационная постоянная, а Hₒ — постоянная Хаббла. Hₒd — скорость расширения на соответствующем расстоянии d.

Давайте предположим, что наблюдаемая Вселенная — это сфера, расширяющаяся со скоростью света с момента Большого взрыва. (Примечание: Это огромное упрощение; нет однозначного ответа на вопрос «Каков объем наблюдаемой Вселенной?» Использование этого подхода, основанного на скорости света, является одной из множества действительных точек зрения. Абсолютный размер наблюдаемой Вселенной намного больше из-за того, как работает расширение, но чтобы запихнуть его в топку MOAC, потребуется движущаяся масса со скоростью, превышающей скорость света.). Объем V нашей сферической Вселенной при заданном ее радиусе r равен:

         V = (4/3)πr³     

Чтобы найти радиус наблюдаемой вселенной r, мы можем использовать возраст вселенной t:

         r = ct     

Закон Хаббла оценивает возраст Вселенной примерно в 1/ Hₒ

Решение для Е

Подставим все полученные значения в исходное уравнение для массы наблюдаемой Вселенной m:

         m = DV     

Помните, в начале статьи я сказал, что ни одно из уравнений не будет длинным или сложным?

Я солгал.

         m = (3Hₒ²/(8πG))(4/3)π(ct)³ m = c³/(2GHₒ) E = mc² E = c⁵/(2GHₒ)     

Ура, мы нашли выражение для полной энергии, которую может потреблять МОАК!

Окончательное решение

         P(n,E) = E/(2ⁿkT) P(n, c⁵/(2GHₒ)) = c⁵/(2GHₒ*2ⁿkT)     

Давайте скопируем и вставим значения этих констант из Википедии и Wolfram Alpha:

         с = 299 792 458 м/с G ≈ 6,67408×10-11 м³/кг/с² Hₒ ≈ 2,2 × 10-18 Гц (неточно; посмотрите натяжение Хаббла) Т ≈ 2,7 К k ≈ 1,38065×10-23 Дж/К     

Подключаем их и упрощаем:

         P(n) ≈ 2,21×1092 / 2n     

Вот несколько примеров выходных данных:

P(256) ≈ 1,9×1015 (пароль определенно взломан после сжигания 1,9 квадриллионной массы-энергии наблюдаемой Вселенной).

P(306,76) ≈ 1 (пароль определенно взломан после сжигания массы-энергии наблюдаемой вселенной)

P(310) ≈ 0,11 (примерно один из десяти)

P(326,6) ≈ 1,1×10-6 (около одного на миллион)

Если ваша модель угрозы немного меньше, смоделируйте помещение объекта меньшего размера в топку MOAC. Например, Земля имеет массу 5,972×10²⁴ кг; это дает MOAC один шанс из десяти триллионов взломать пароль с 256 битами энтропии и 100% шанс взлома 213-битного пароля.

Примеры невзламываемых паролей

Согласно генератору паролей KeePassXC, каждый из следующих паролей имеет энтропию от 330 до 340 бит.

Использование расширенного набора символов ASCII:

         ¦=¦FVõ)Çb^ÄwΡ=,°m°B9®;>3[°r:t®Ú"$3CG¨/Bq-y;     

Использование символов стандартной раскладки US QWERTY:

         %nUzL2XR&Tz5hJfp2tiYBoBBX^vWo3`g6H#JSC#N6gWm#hVdD~ziD$YHW     

Использование только буквенно-цифровых символов:

         tp8D69CGWE5t5a9si5XNsw32CKyCafh8qGrKWLwE6KJHpGyUtcJDWpgRz5mFNx     

Отрывок из религиозного текста с пробелом в конце:

         I'd just like to interject for a moment. What you’re referring to as Linux, is in fact, GNU/Linux,     

Не используйте в качестве пароля настоящие отрывки из ранее существовавших произведений.

Заключение, TLDR

Вопрос: Какой должна быть энтропия у пароля, чтобы гарантировать, что он никогда не будет уязвим для атаки грубой силы? Может ли невероятно эффективный компьютер — MOAC — взломать ваш пароль?

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

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

Дополнительная литература: альтернативные подходы

Ознакомьтесь со статьей Скотта Ааронсона «Космология и сложность». Он использует альтернативный подход к нахождению максимальных битов, с которыми мы можем работать: он просто инвертирует космологическую постоянную.

Эта модель учитывает не только массу наблюдаемой Вселенной. Хотя ранее мы обнаружили, что MOAC может подобрать пароль с энтропией 306,76 бит, эта модель позволяет то же самое до 405,3 бит.

Подходы, учитывающие скорость вычислений

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

Одним из хорошо известных подходов к вычислению физических пределов вычислений является предел Бремермана, который рассчитывает скорость вычислений при заданном количестве массы. Подход этой статьи игнорирует время, сосредотачиваясь только на эквивалентности массы и энергии.

Предельные физические пределы вычислений Сета Ллойда дополнительно исследует пределы скорости вычислений на идеальном 1-килограммовом компьютере.

***

Материалы по теме

• 🕵 Как взломать Wi-Fi с помощью Kali Linux 2020.4 и Ubuntu 20.04
• 🏴‍☠️ История цифрового взлома: 10 самых известных хакеров всех времен