Nahodnost a entropie

Náhodnost a entropie

Skoro každý reálný kryptografický průšvih poslední čtvrtstoletí měl stejnou příčinu. Nebyla to prolomená šifra. Byl to špatný generátor náhodných čísel.

Je to slabé místo, na které se nemyslí, protože se nedá vidět. Klíč vygenerovaný z vadné náhody vypadá naprosto stejně jako správný. Nic nehlásí chybu, nic není pomalejší, testy projdou. Jen ho někdo umí uhodnout.

Navazuje na stavební kameny a je nutným doplňkem asymetrické kryptografie.

Proč na tom všechno stojí

Zamysli se, kde všude potřebuješ nepředvídatelné číslo:

• Soukromý klíč — SSH, TLS, WireGuard, GPG. Uhodnutelný klíč = žádný klíč.
• Dočasné klíče pro Diffie-Hellmana — a a b. Predikovatelné a = celé spojení dešifrované.
• Nonce u AEAD šifry — opakování prolomí integritu.
• k u podpisu ECDSA — opakování prozradí přímo soukromý klíč.
• Sůl u hesel, session cookies, CSRF tokeny, resetovací odkazy.
• Session ID — uhodnutelné ID znamená převzetí cizí relace bez znalosti hesla.

Ve všech případech platí totéž: bezpečnost systému je nejvýš tak velká jako nepředvídatelnost čísla, ze kterého vznikl. AES-256 s klíčem odvozeným z časového razítka má sílu toho časového razítka, ne 256 bitů.

Entropie: kolik nepředvídatelnosti tam doopravdy je

Entropie měří, kolik toho útočník neví. Udává se v bitech a hodnota n bitů znamená, že nejlepší útok potřebuje řádově 2ⁿ pokusů.

Zdroj	Skutečná entropie
Aktuální čas v sekundách, odhad na den	~17 bitů
Aktuální čas v mikrosekundách, odhad na hodinu	~32 bitů
PID procesu	~15 bitů
MAC adresa	~24 bitů (výrobce je známý)
Heslo Heslo123!	~4 bity — je ve všech slovnících
Čtyři náhodná slova ze slovníku 8000 slov	~52 bitů
16 bajtů z /dev/urandom	128 bitů

Poznámka k tomu předposlednímu řádku: entropie je vlastnost postupu, kterým hodnotu vybíráš, ne té hodnoty. 4839 má stejnou entropii jako 0000, pokud jsi obojí losoval stejně. Vypadá to nenáhodně, ale to je psychologie, ne matematika.

Praktický důsledek pro hesla: délka a náhodnost výběru rozhodují, ne exotické znaky. mrkev-tramvaj-pisek-hlina je výrazně silnější heslo než P@ssw0rd!.

Skutečná náhoda versus generátor

Počítač je deterministický stroj. Náhodu si musí odněkud vzít.

Zdroje entropie — fyzikální jevy, které se nedají předpovědět: přesné časování přerušení z klávesnice, myši a disku, šum síťové karty, hardwarový generátor v procesoru (RDRAND u Intelu/AMD, RNDR u ARM), TPM čip, virtio-rng u virtuálních strojů.

CSPRNG — kryptograficky bezpečný generátor. Ze semínka (typicky 256 bitů skutečné entropie) vyrábí nekonečný proud, ze kterého nejde předpovědět další bajt ani při znalosti všech předchozích.

To je celý model: entropie se sbírá jednou na začátku, pak už jen běží generátor. Nemusíš mít gigabajt skutečné náhody, aby ses dostal ke gigabajtu klíčů. Stačí, aby to semínko bylo dobré.

Obyčejný PRNG je něco jiného. rand() v C, Math.random() v JavaScriptu, random v Pythonu (bez secrets), $RANDOM v bashi, Mersenne Twister. Jsou rychlé, statisticky vypadají náhodně a z pár výstupů se dá dopočítat vnitřní stav a předpovědět všechno další. Na simulace ano, na klíče nikdy.

/dev/urandom versus /dev/random

Nejrozšířenější mýtus v celém Linuxu.

Kolem roku 2010 se všude psalo, že /dev/urandom je „slabší", protože nečeká na doplnění entropie, a že se na klíče musí použít /dev/random. Dnes je to nesprávné.

Od jádra 5.6 (rok 2020) platí:

• /dev/urandom — po inicializaci nikdy neblokuje a poskytuje kryptograficky kvalitní data. Toto je správná volba.
• /dev/random — chová se prakticky stejně, blokuje jen dokud není generátor vůbec poprvé inicializovaný.
• getrandom() — systémové volání, které je nejsprávnější. Počká na první inicializaci a pak už nikdy.

Ta stará představa „entropie se používáním spotřebovává" vychází z teoretického modelu, ne z toho, jak CSPRNG fungují. Kdo dnes v produkci čte z /dev/random a pak si stěžuje, že generování klíčů na čerstvém VPS trvá deset minut, řeší neexistující problém.

# správně
head -c 32 /dev/urandom | base64
openssl rand -base64 32
openssl rand -hex 16

# heslo
tr -dc 'A-Za-z0-9' < /dev/urandom | head -c 24; echo

# špatně
echo $RANDOM$RANDOM
date +%s | sha256sum

entropy_avail v /proc/sys/kernel/random/ je dnes v podstatě informační údaj. Podle něj neřiď nic.

Skutečné katastrofy

Tohle nejsou hypotézy. Každá z nich stála někoho hodně.

Debian, OpenSSL, 2008

Vývojář Debianu odstranil z OpenSSL řádek, na který si stěžoval nástroj na hledání chyb v paměti. Ten řádek přiváděl do generátoru entropii. Zbylo z ní PID procesu — a tedy zhruba 32 768 možností.

Dva roky se na Debianu a Ubuntu generovaly SSH klíče, TLS certifikáty a klíče OpenVPN, kterých existovalo dohromady 32 768 kusů na typ a délku. Někdo si je všechny předpočítal a zveřejnil. Nešlo je „opravit", každý klíč z toho období se musel vyhodit.

Poučení: nikdo si toho dva roky nevšiml, protože klíč z vadné náhody vypadá naprosto normálně.

Sony PlayStation 3, 2010

Sony podepisovalo software pomocí ECDSA. Podpisové schéma vyžaduje ke každému podpisu nové náhodné číslo k. Sony použilo pořád stejné.

Ze dvou podpisů s totožným k se soukromý klíč dopočítá pár řádky středoškolské algebry. Klíč byl zveřejněn na konferenci, konzole šla podepisovat čímkoliv a opravit to nešlo, protože veřejný klíč byl v hardwaru.

Tohle je hlavní důvod, proč je Ed25519 deterministické: svoje k si odvozuje z klíče a zprávy, takže tuhle chybu nelze udělat.

Android, 2013

Vada v SecureRandom na Androidu vedla k opakovaným hodnotám k u podpisů. Z bitcoinových peněženek zmizely reálné peníze — každý, kdo dvakrát podepsal se stejným k, dal svůj klíč veřejně k dispozici v blockchainu.

Mining your Ps and Qs, 2012

Výzkumníci proskenovali celý internet a stáhli miliony TLS a SSH veřejných klíčů. Zjistili, že statisíce zařízení sdílí prvočíslo s jiným zařízením — routery, firewally, tiskárny a kamery generovaly klíče hned po prvním zapnutí, kdy ještě žádnou entropii neměly.

A dvě RSA čísla se společným dělitelem jdou rozložit okamžitě, protože Euklidův algoritmus je z 18. století. Zhruba 0,5 % TLS klíčů na internetu se dalo takhle rozbít bez jakéhokoliv útoku na RSA samotné.

Tohle se týká i tebe: routery, IP kamery a NAS krabice generují své klíče při prvním startu, kdy je entropie nejméně.

ROCA, 2017

Knihovna Infineonu generovala RSA klíče podle vzorce, který snížil počet možností natolik, že 2048bitový klíč šel rozložit za desítky hodin výpočtu. Týkalo se to čipových občanek (mimo jiné estonských), TPM modulů a části YubiKeyů. Zase: klíče vypadaly úplně normálně.

Kde se to týká tvého homelabu

Klonované virtuální stroje a šablony

Tohle je nejpravděpodobnější způsob, jak si problém způsobíš sám.

Když v Proxmoxu uděláš šablonu z běžícího systému a naklonuješ z ní deset strojů, všechny mají stejné SSH host keys, stejné semínko generátoru a stejný machine-id. Nikdo si toho nevšimne, protože všechno funguje.

Do šablony proto patří:

# před vytvořením šablony
rm -f /etc/ssh/ssh_host_*
rm -f /var/lib/systemd/random-seed
truncate -s 0 /etc/machine-id
rm -f /var/lib/dbus/machine-id

Při dalším startu si systemd i sshd všechno vyrobí znovu. Cloud-init to řeší sám, ale jen když ho skutečně používáš.

Ověření, že se ti to nestalo:

# na každém stroji — otisky se musí lišit
for f in /etc/ssh/ssh_host_*_key.pub; do ssh-keygen -lf "$f"; done
cat /etc/machine-id

Virtuální stroje a entropie po startu

VM nemá klávesnici, myš ani skutečný disk, takže klasické zdroje entropie odpadají. Řešením je prostředníka z hostitele:

Proxmox / KVM — přidej zařízení virtio-rng s hostitelským /dev/urandom jako zdrojem. Ve webovém rozhraní je to Hardware → Add → VirtIO RNG.

Kontejnery sdílí generátor jádra hostitele, takže tam problém není. Docker ani LXC vlastní entropii neřeší a nemusí.

Malá zařízení (Raspberry Pi, routery) — Pi má hardwarový generátor, rng-tools ho zapojí do jádra:

apt install rng-tools5

Kdy klíče generovat

Nikdy hned po prvním startu čerstvě nainstalovaného systému bez zdroje entropie. Pokud instaluješ přes síť na hardware bez hardwarového generátoru, chvíli počkej, něco na tom stroji dělej, a klíče vygeneruj až potom. Na moderním x86 s RDRAND a s virtio-rng ve VM je to bezpředmětné, na exotičtějším hardwaru ne.

Klíče generuj tam, kde budou použité. Když ti někdo pošle vygenerovaný klíč, netušíš, z čeho vznikl ani kolik existuje kopií.

Jak si to ověřit

# hardwarový generátor v procesoru?
grep -o 'rdrand\|rdseed' /proc/cpuinfo | sort -u

# jaké zdroje jádro používá
cat /sys/devices/virtual/misc/hw_random/rng_available
cat /sys/devices/virtual/misc/hw_random/rng_current

# je generátor inicializovaný? (na běžícím systému vždycky ano)
dmesg | grep -i "random: crng init done"

Testy náhodnosti ti neřeknou nic užitečného. dieharder, ent a spol. odhalí statistickou vadu, ale kryptograficky vadný generátor projde všemi. Výstup z AES v čítačovém režimu se semínkem 0 je statisticky dokonale náhodný a přitom naprosto předvídatelný. Nezaměňuj „vypadá náhodně" a „je nepředvídatelné".

Praktická pravidla

Používej systémový generátor. getrandom(), /dev/urandom, secrets v Pythonu, crypto.randomBytes v Node, crypto/rand v Go. Nikdy rand(), Math.random(), random.random(), $RANDOM.

Nemíchej si vlastní entropii. „Pro jistotu" přidané časové razítko nebo PID nic nepřidá a v horším případě uškodí.

Nikdy nepoužívej stejný nonce dvakrát. Když nemůžeš zaručit čítač, zvol šifru s dlouhým nonce.

Nepodepisuj ECDSA v prostředí, kde si nejsi generátorem jistý. Použij Ed25519 nebo deterministické ECDSA podle RFC 6979.

Šablony VM čisti. Viz výše. Je to dvouřádkový skript a ušetří ti nepříjemnou situaci.

Nedůvěřuj slepě RDRAND. Je to černá skříňka od výrobce procesoru. Linux ho proto míchá s ostatními zdroji místo aby ho použil samostatně, což je správné řešení — když je v pořádku, pomůže, a když ne, neuškodí.

Kam dál

• Veřejný a soukromý klíč — co se z té náhody vyrábí
• Hashe, HMAC a podpisy — sůl, pepř a ECDSA
• Diffie-Hellman — dočasné klíče, které musí být nepředvídatelné
• Zabezpečení serveru — praktická opatření
• Proxmox a sítě — kde se dělají šablony