Nahodnost-a-entropie.md

# 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](Sifrovani-zaklady) a je nutným doplňkem [asymetrické kryptografie](Verejny-a-soukromy-klic). ## 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](Diffie-Hellman)** — `a` a `b`. Predikovatelné `a` = celé spojení dešifrované.- **Nonce u [AEAD šifry](Sifrovani-zaklady#nonce-se-nesmí-opakovat-nikdy)** — 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. ```bash# správněhead -c 32 /dev/urandom | base64openssl rand -base64 32openssl rand -hex 16 # heslotr -dc 'A-Za-z0-9' < /dev/urandom | head -c 24; echo # špatněecho $RANDOM$RANDOMdate +%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é](Verejny-a-soukromy-klic#ecdsa-a-smrtelná-past-s-nonce): 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](Proxmox-site) 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ří: ```bash# před vytvořením šablonyrm -f /etc/ssh/ssh_host_*rm -f /var/lib/systemd/random-seedtruncate -s 0 /etc/machine-idrm -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: ```bash# na každém stroji — otisky se musí lišitfor f in /etc/ssh/ssh_host_*_key.pub; do ssh-keygen -lf "$f"; donecat /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: ```bashapt 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 ```bash# 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_availablecat /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íč](Verejny-a-soukromy-klic)** — co se z té náhody vyrábí- **[Hashe, HMAC a podpisy](Hashe-a-podpisy)** — sůl, pepř a ECDSA- **[Diffie-Hellman](Diffie-Hellman)** — dočasné klíče, které musí být nepředvídatelné- **[Zabezpečení serveru](Zabezpeceni-serveru)** — praktická opatření- **[Proxmox a sítě](Proxmox-site)** — kde se dělají šablony