Ох энтро́пии мне мало... ветер пью, туман глотаю

[vak]

Почему NetBSD часто тормозит на i486 процессоре? Выяснились две причины: шифрование свопа и нехватка энтропии.

Не знаю, кто придумал включить по умолчанию шифрование страниц, откачиваемых в своп. Без аппаратной поддержки шифрования это убивает производительность напрочь. Отключается легко: достаточно добавить строчку "vm.swap_encrypt=0" в файл /etc/sysctl.conf.

С энтропией ситуация сложнее. При загрузке ядро NetBSD выдает строчку, означающую, что дело плохо.

WARNING: system needs entropy for security; see entropy(7)

За последние 10 лет мы привыкли к защищённым протоколам типа HTTPS и SSH, и не интересуемся деталями. А им для работы нужен качественный источник случайности. Иначе протокол станет слишком предсказуемым, а значит хакеры могут взломать его, легко подобрав ключ.

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

В процессе передачи с каждым сообщением отправляется дополнительная случайная строка, чтобы гарантировать, что даже если вы отправите одну и ту же команду дважды (например, «Заплатить 10 долларов»), зашифрованные данные будут выглядеть совершенно по-разному каждый раз. Без высокой энтропии эти одноразовые числа могут повторяться или следовать определенному шаблону. Злоумышленник может записать старое зашифрованное сообщение и «воспроизвести» его позже, чтобы обмануть сервер.

Откуда протокол берёт эту энтропию? В ядре операционной системы имеется специальный буфер, где хранится некоторый запас, обычно несколько тысяч качественных случайных бит. Установление каждого нового HTTPS-соединения потребляет примерно от 256 до 512 бит (от 32 до 64 байт) из этого запаса, то есть порядка 10%. На каждый передаваемый пакет тоже нужно немного случайности, но там уже работает псевдослучайный генератор. В активных системах (особенно на серверах или небольших устройствах IoT) запас энтропии может опустеть, если нужно быстро сгенерировать слишком много ключей. Система может замереть и ждать, пока не будет собрано больше случайных данных. Источником служит или специальный аппаратный генератор шума (TRNG), встроенный в современный процессор, или драйверы некоторых периферийных устройств. Скажем, можно отслеживать микроизменения времени, необходимого жесткому диску для поиска данных.

Мы не замечаем проблемы энтропии, потому что на современных устройствах генераторы шума встроены в процессор. На древнем же компьютере ничего такого нет, и поэтому вход по SSH на мой Cx486 занимает 78 секунд. Время уходит на сбор энтропии и генерацию одноразового ключа для защищённого сеанса.

Энтропию в ядро можно легко добавлять, просто записывая случайные данные в /dev/urandom. Вопрос, откуда брать качественную случайность. Скажем, можно соорудить девайс на микроконтроллере RP2350 и подключить его на COM порт. В этом чипе есть блок TRNG, способный выдавать 7500 случайных бит в секунду. Это примерно 938 байт/сек. Хватит с запасом на все потребности.

Comments

[dimorlus]

Мне кажется, из какого-нибудь game port можно довольно просто и чисто аналоговыми методами получить случайные данные

[vak]

Из любого АЦП можно, но получается мало и плохого качества.

Народ что только не пристраивает в качестве источника энтропии. Стену из лавовых ламп, к примеру.

https://en.wikipedia.org/wiki/Lavarand

https://blog.cloudflare.com/lavarand-in-production-the-nitty-gritty-technical-details/

[dimorlus]

Есть же простые схемы, генерирующие хаотичные "полноразмерные", на весь диапазон АЦП сигналы, на паре ОУ делаются, или даже проще, подключенные к X-Y входам осциллоскопа они завораживающие картинки рисуют, не хуже тех лавовых ламп (но намного проще в реализации). Что интересно, они и в симуляторах также работают. Неужели оцифровка таких сигналов не дает достаточно случайной последовательности бит, особенно если их потом еще перемешать?

[vak]

Выходит слишком высокая корреляция оцифрованного сигнала с предыдущим значением.

[dimorlus]

А кто и как это проверяет?

[ichthuss]

Что значит "проверяет"? Єнтропия - мера непредсказуемости (случайности) сигнала. Если на вход АЦП идет сигнал, с виду хаотический, но по сути полностью детерминированньій начальньім состоянием генератора, то єнтропия єтого сигнала, независимо от его длительности, ограничена єнтропией начального состояния.

[dimorlus]

То и значит, как это проверить-то? Особенно учитывая, что в аналоговых цепях ничего полностью детерминированного не бывает. Кто/что и как решает достаточно или нет энтропии у той или иной реализации ГСЧ?

[ichthuss]

Так єнтропия - єто теоретическое понятие, оно не "проверяется", а "вьіводится". Рассмотрим такую простую модель: есть псевдохаотическая аналоговая схема, ее поведение полностью определяется начальньім состоянием и шумами, возникающими в процессе работьі (сюда же отнесем и квантовьіе єффектьі). Если следующее состояние такой схемьі сильно детерминированно предьідущим, то влияние шумов минимально.

Допустим, мьі использовали нашу схему, чтобьі она поработала и сгенерировала нам 128 псевдослучайньіх бит. Из-за вьісокой детерминистичности может оказаться, например, что при любом заданном исходном состоянии шумьі приводят к тому, что результат будет одним из 8 разньіх битовіх строк (разніх для каждого начального состояния). Єто означает, что работа нашей системьі добавила только максимум 3 бита єнтропии к начальному состоянию. Т.е. можно бьіло вообще не париться псевдохаотической схемой, а оцифровать ее исходное состояние и наскрести дополнительньіе 3 бита из теплового шума.

[dimorlus]

Тут выше по ссылке на ответ LLM куда более осмысленная информация, псевдо или не псевдо хаотична аналоговая схема вы как предлагаете "выводить"? А "начальный момент" как? Экспериментально проверить, набрав данные и попытавшись найти там корреляции - это путь, хотя бы. Погуглите "генератор хаоса" - там есть несколько широко известных схем, и куча их модификаций. Есть и механические конструкции с подобными свойствами вроде маятника на маятнике. Другое дело, что может быть сложно простыми средствами обеспечить требуемый поток данных. Надо чтобы и АЦП успевал что-то осмысленное выдать, и частоты генераторов хаоса были достаточными, чтобы АЦП просто близкие соседние точки потоком не гнал, это, кстати и построенных на основе шума схем касается. А вот как на этом сказывается программное перемешивание бит какой-нибудь хеш функцией, да хоть простейшим и довольно шустрым CRC я не знаю, но по-моему, это добавляет хаоса.

[ichthuss]

В информационно-теоретическом смысле никакие детерминистические преобразования энтропии не добавляют.

[dimorlus]

А в практическом - да.

[ichthuss]

"Єнтропия" - информационно-теоретическое понятие. Хотите обсуждать что-то, что "растет" при детерминистических преобразованиях - вьіберите другое слово.

[tiresome_cat]

Интересно.

[kondybas]

"..Если ваша система обладает высокой энтропией, хакеру придется перебрать почти все из них.."

В середньому тільки половину.

[vak]

Половина від 2¹²⁸ все ж таки 2¹²⁷. Немало. 😀

[x86128]

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

[netch80]

Рассматриваю SSH: RFC4253: для генерации ключей шифрования используются общий секрет и две cookie. В общем секрете энтропия зависит от длины участвующих чисел. При ECDH она невысока, в пределах ну например 256 бит каждый. И куки по 128 каждая. До сеансового ключа симметричного шифра это всё урезается. Если формально включить IV/nonce в ключ, может, чуть меньше урезается, но всё равно обычно меньше. Расширять ключ не на чем. Протоколов, где поверх такого соединения делается ещё один KEX, чтобы не заменить, а расширить ключ, я не слышал -- наверно, это вредно с точки зрения науки.
В случае TLS ещё сильнее ужимание - там обе куки по 256 бит.
Так что "более длинным ключом" обычно некорректно.

На прикладном уровне поверх TLS обычно своё уже не наворачивают, потому что неизвестно, как они проинтерферируют. В принципе можно, но теория не рекомендует.

[itsi]

Интернет для этого использовать.

[fenikso]

О! Ходить в Интернет за случайньіми числами! :)

[vak]

Вы будете смеяться.

https://www.random.org/

[brumka]

Отличный ликбез, спасибо. Я вот не знал, что генераторы случайных чисел встраиваются в современные процессоры. То есть очень логично, но я думал, что всякие rand() выполняются исключительно программно. Надо-бы, при случае, полюбопытствовать как это реализовано, например, в HSM модулях

[sassa_nf]

> rand()

It depends.

Intel has RDRAND, which ends up in /dev/random. But a lot of software uses /dev/urandom, as that is a PRNG, so is not blocking.

[brumka]

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

[vak]

RDRAND появился всего десять лет назад.

[sassa_nf]

Yes. Before that it was way harder to find a source of good entropy.

Eg on a hardware platform we were working on the network got so predictable latency that we could not use it as a source of entropy.

[netch80]

При наличии RDRAND оба /dev/random и /dev/urandom его используют. Разница в том, где они останавливаются при плотном потоке потребления: при чтении /dev/random оно не может сделать reseed, если нет аппаратной энтропии в достаточном количестве, чтобы подмешать в процесс.

По факту для 99.9+% даже криптографических применений /dev/urandom достаточно случаен, чтобы не сильно плакать по аппаратной энтропии.

[henry_flower]

але ж ув сучасних лайнаксах /dev/random також не блокується?

навіть на amd картоплі з 2021 (найстаріше шо я знайшов)

dd if=/dev/random of=/dev/null bs=1024 count=10000000 iflag=fullblock

різницю у часі з /dev/urandom не показує

вмикання/вимикання rngd демону дає 0 ефекту

[sassa_nf]

Ну, rdread має бути вже якийсь час, то напевно rngd is a noop now.

[mopexod]

Младшие шумящие биты температурного датчика процессора, в основном.
Пояснено, что очень часто опрашивать не получится: АЦП термометра не бесконечно быстрый.

[brumka]

Ага, я чуток почитал как добывают энтропию в TRNGs из физических датчиков - прикольно

[vak]

Народ постоянно изобретает более качественные методы, получше броуновского движения. Лавинный эффект, к примеру.

https://crypto.stackexchange.com/questions/108803/entropy-extraction-from-a-zener-diode-trng

[mopexod]

Вау, какая минималистическая схема!

[dimorlus]

Использовать шум стабилитрона - классика. На сколько компаратором может работать порог FET'а - вопрос. Как его свойства на качество генератора влияют - тоже. И тут опять возникает вопрос кто и как это проверяет.

[vak]

Есть классный веб сайт, где тема в подробностях раскрыта.

http://www.reallyreallyrandom.com/zener/breadboard/index.html

[dimorlus]

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

[vak]

https://chatgpt.com/share/694db453-cd94-8001-8245-f17d562baad7

[dimorlus]

Осталось собрать и проверить.

[prool]

Студент! Возьми ведро сходи в сад накопай энтропии

[vak]

Именно так! Источник хорошей энтропии находится снаружи компьютера. Обычно из всяких природных процессов.

[juan_gandhi]

О как нынче. Спасибо за информацию!

[vak]

Чего только не узнаешь, копаясь в древних железяках. 😀

[spamsink]

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

Интересно, что будет при cat /dev/zero > /dev/urandom.

[vak]

Наверное проигнорирует. “У вас случайность сломалась.”

[netch80]

Подмешает точно так же.
Современные хэши, начиная с SHA-256, достаточно надёжны, чтобы от этого не страдать.

Если один накопительный пул (вариант Linux), то просто будет регулярное выполнение операции:

K[n+1] = Hash(K[n] ‖ Hash(pool))

где K - ключ для генерации текущей порции данных каким-то потоковым (stream) шифром.

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

В варианте Fortuna (вроде бы все BSD) ещё и регулярно подключаются разные пулы из массива пулов, так что надо знать полное состояние генератора, чтобы хоть что-то хоть как-то предсказать, и то на короткое время. Такой себе самовосстанавливающийся самоусиливающийся хаос, годится для тёмной фэнтези. Ну а текущий ключ и значения пулов генератора даже руту сложно достать.

Последние лет 20 не было движений в сторону усложнения механизма или хотя бы расширения ширины ключа. Значит, хватает.

[flamedancerii]

В новых процессорах тоже не все гладко - вот недавняя ошибка в аппаратном блоке генератора случайных чисел AMD Zen 5 https://www.linuxjournal.com/content/amd-confirms-zen-5-rng-flaw-when-random-isnt-random-enough

Про медленный заход по ssh - странно, urandom не должен block. Там случайно дело не в reverse dns timeout?

[vak]

Там ещё и процессора недостаёт для мощного шифрования. Аппаратной поддержки ведь нету.