Občas se lidé ptají na nějaký tutorial k eliptickým křivkám. Pokud vím, tak žádný rozumný neexistuje. Nejspíš z toho důvodu, že na rozdíl od RSA, které je celkem jednoduše vysvětlitelné, jsou eliptické křivky jen „prachsprostá“ algebra. Naposledy se o tutorial pokusil D. Bernstein přednáškou na 31C3, ale ve výsledku to ještě víc zamotal. My zkusíme jiný přístup – „cheatsheet“ – popíšeme, na co je která křivka dobrá, které jsou ty „špatné“, ale „bez důkazů“.
Eliptické křivky jsou kryptografické primitivum, nad kterým lze postavit Diffie-Hellman výměna klíčů (ECDHE), digitální podepisování (ECDSA) nebo asymetrické šifrování (ECIES).
Prvně: proč je v těch křivkách takový guláš? Protože jich je hodně. Do obecné Weierstrassovy rovnice dosadíte nějaké parametry a hle – máte novou křivku. Navíc křivky dost často mají „užívatelsky nepřívetivá“ jména, někdy má jedna křivka vícero jmen.
Křivky ze „Standards for Efficient Cryptography“ (SEC)
Asi nejvíce používané křivky pocházejí z dokumentů SEC-1 a SEC-2:
- secp192k1, secp224k1, secp256k1
- secp192r1 (NIST P-192), secp224r1 (NIST P-224), secp256r1 (NIST P-256), secp384r1 (NIST P-384), secp512r1 (NIST P-521)
- sect163k1, sect163r1, sect163r2, sect233k1, sect233r1, sect239k1, sect283k1, sect283r1, sect409k1, sect409r1, sect571k1, sect571r1
Číslo za „secp“ nebo „sect“ říká velikost klíče v bitech a velikost tělesa – čím větší, tím je pochopitelně křivka silnější.
Začneme od posledního třetího řádku, křivek jejichž jména začínají na „sect“ – tyto je možné najít třeba v TLS. Jsou definovány nad konečnými tělesy s charakteristikou 2, což s dnešním poznáním znamená, že na jejich lámání existují lepší algoritmy než na ostatní křivky.
V druhém řádku jsou „ty špatné“ NIST křivky, v závorce je ke každé secp křivce alternativní NIST název. Za „špatné“ se považují proto, že některé jejich koeficienty jsou hausnumera. Ta hausnumera by měla být náhodná, z toho důvodu je v názvu křivky „r“ od „random“. Ale jak náhodně byly vygenerované, si téměř nikdo není jist. Proto se spekuluje, zda nejsou parametry vybrány nějak speciálně, což by útočníkovi s určitou znalostí umožňovalo louskat je rychleji. Podobně, jak byly vybrané speciální koeficienty k Dual-EC-DRBG. Proto se v novějších softwarech doporučuje vybrat radši jiné křivky. Tyto „náhodné“ křivky lze nalézt v TLS, OpenSSH, OpenVPN, DNSSEC – prakticky všude, kde se ECC doporučovalo, protože byly standardizovány NIST-em a historicky preferovány.
V prvním řádku jsou Koblitzovy křivky, z nichž je asi nejzajímavější secp256k1, neboli „Bitcoinová křivka“. Používá se i v jiných „coinech“ a nepřekvapí její přítomnost v TLS. Její popularita způsobila, že se implementuje i do jiných softwarů, nedávno například OpenVPN.
Zatím probírané křivky mají jednu nepříjemnou vlastnost a tou je mnoho výjimek a složitá implementace operací. Kvůli této složitosti je velmi těžké vytvořit implementaci, která by neměla postranní kanály. Ty umožňují útoky jako FLUSH+RELOAD, kdy útočníkovi postačí k odhalení tajného klíče manipulování s cache. Nicméně implementace se už časem dost zlepšily.
Křivky speciálních tvarů
Právě náročnost správné implementace předchozích „obecních křivek“ vedla k nápadu vybrat tvar křivky tak, aby se rovnou některým útokům vyhla, a aby implementace byla snažší. To byla část důvodů stojící za vznikem křivky Curve25519 (Mongtomeryho křivka). Ta se používá pro Diffie-Hellman dohodu na klíči. Z ní je odvozen systém digitálního podpisu Ed25519.
Křivka Curve41417 je Edwardsova křivka, která má díky svému obrovitému klíči chránit data na velmi dlouhou dobu. Více o speciálních křivkách se můžete dočíst ve starším článku na Root.cz.
Především Curve25519 začíná být stále populárnější a dostává se do dalších softwarů (př. OpenSSH) nebo protokolů – brzy bude v TLS. Už se o tom CFRG hádá asi tak rok, tak už snad fakt brzy :-).
Podpora eliptických křivek na hardwarových tokenech
U podpory RSA v HW tokenech byla jedinou otázkou jen maximální podporovaná velikost modulu. RSA je na rozdíl od eliptických křivek jen jedna a nemuselo se rozhodovat, které křivky implementovat.
Podle očekávání je to s podporou celkem slabé – když už je, tak jenom specifický výrobce a ještě závisí, jak moc „exotická“ křivka je. Na druhé straně je problém i ze strany aplikací – dokud je jeden RSA token možné použít jak se OpenSSH, OpenVPN nebo Firefoxem, tak by jeden token musel podporovat vícero eliptických křivek, aby šel použít s vícero aplikacemi.