Daniel J. Bernstein je celkem známá osoba mezi programátory i matematiky. Mezi jeho programátorské počiny patří třeba qmail. Z matematických prací publikoval několik kryptosystémů založených na eliptických křivkách (dále jen ECC). Velmi často mezi jeho spolupracovníky patří Tanja Lange a pár dalších zvučných jmen.
Na co je která křivka dobrá
Křivka Curve25519 je jedna z Bernsteinových starších prací z 2005. Je určena pro Diffie-Hellman dohodu na sdíleném klíči. Tento systém se časem dost osvědčil, je už součástí software jako SSH, Tor a míří do dalších protokolů – dost se o něm například mluví v souvislosti s TLS 1.3.
Kryptosystém Ed25519 je založen na křivce příbuzné Curve25519 a slouží ke generování digitálních podpisů. Podpisy jsou deterministické a nehrozí tedy v průběhu používání prozrazení tajného klíče špatným náhodným generátorem (viz též RFC 6979).
Křivka Curve41417 je nová velká křivka určená opět k Diffie-Hellman dohodě na klíči. Díky obrovskému konečnému tělesu, nad kterým je postavena, má být určena k designování systémů, které budou například více než 10 let sloužit v embedded zařízeních.
Velmi důležitým znakem každé zmíněné křivky je rychlost a vysoká odolnost proti postranním kanálům.
Občas zmíníme porovnání s NIST křivkami, těmi jsou myšleny křivky, jejichž názvy začínají s „NIST P“ nebo „sec“, např. NIST P-224, secp256r1 nebo sect409k1. NIST křivky se používají jak na Diffie-Hellmana, tak pro podepisování.
Klíče na eliptické křivce
Pro osvěžení si připomeneme, jak se reprezentují klíče u eliptických křivek. Privátní klíč je typicky velké celé číslo k. Veřejný klíč k privátnímu dostaneme násobením privátního klíče s generátorem G, což je specifický, veřejně známý bod na eliptické křivce. Obtížnost získání privátního klíče z veřejného klíče k•G se označuje jako problém diskrétního logaritmu pro eliptické křivky.
Curve25519
Křivka Curve25519 je pojmenována podle prvočísla 2255 – 19, které označuje konečné těleso, nad kterým je kryptosystém Curve25519 vybudován.
Nejdůležitější vlastnost křivky Curve25519 je její jednoduchá použitelnost pro programátora, která odstraňuje pasti jako speciální případy v ECC aritmetice a postranní kanály. Některé vlastnosti plynou z algebraických vlastností, jiné jsou dány implementací.
Návod, jak použít Curve25519 ve vlastním software, je k dispozici na stránkách D. Bernsteina. Implementaci optimalizovanou pro současné x86 procesory a generickou portabilní verzi lze najít pod názvem curve25519-donna.
Výhody křivky Curve25519
První vlastností je rigidnost výběru parametrů křivky – neobsahuje žádná „neodůvodněná hausnumera“ jako různé NIST křivky. Parametry jsou zvoleny, aby byly buďto nejmenší nebo nejbližší číslo splňující určitou algebraickou vlastnost.
Křivka je imunní proti časovým, hyperthreading a cachovacím postranním kanálům, protože se implementace vyhýbá větvení závislém na vstupu, nepoužívá indexy pole závislé na vstupu ani jiné instrukce s časováním závislým na vstupu.
Privátní klíče mají 32 bajtů, běžných u ECDH funkcí se stejnou úrovní bezpečnosti. Veřejné klíče mají také 32 bajtů, což je polovina proti 64 bajtům u typických ECDH funkcí. Trik spočívá v tom, že se používá „komprimovaná“ forma bodu, obsahující jenom x souřadnici.
Koordinátu y lze z komprimovaného bodu dopočítat, ale algoritmy jsou stavěny tak, že to není potřeba (tzv. laddering algoritmy). U NIST křivek také existuje komprimovaná forma bodu, ale body se při počítání musí dekomprimovat. Zároveň nelze použít laddering algoritmy.
Možnost počítání s komprimovaným bodem má ale jeden zásadní vedlejší efekt – není potřeba vstupní body kontrolovat, zda leží na křivce. Tím odpadá jeden podstatný útok, tzv. fault útok, kde útočník může získat bity našeho privátního klíče tím, že nás nechá počítat s bodem mimo křivku a my si to nezkontrolujeme. Takto máme „validaci bodu zdarma“.
Generování privátních klíčů je podobně jednoduché – vygenerujeme libovolné náhodné číslo dlouhé 256 bitů, bity 255, 2, 1 a 0 se vynulují, bit 254 se nastaví. Nulování nejnižších třech bitů způsobí, že privátní klíč bude násobkem 8. To je další designový prvek odstraňující twist útok.
Jak si představit Diffie-Hellman protokol s křivkou Curve25519
Curve25519 Diffie-Hellman
Alice má svůj tajný klíč – velké celé číslo a, Bob má svůj tajný klíč – velké celé číslo b. Řetězec 9 je použit jako generátor (přesněji se tím určuje bod na křivce, který ma Xovou souřadnici 9).
Funkci Curve25519 si můžeme představit jako násobení. Alice si s Bobem vymění bod vzniklý po násobení tajného klíče s generátorem, po drátě tedy putují veřejné klíče Curve25519(a, 9) a Curve25519(b, 9). Po přijetí tohoto čísla ze sítě si každý z nich spočte:
- Alice si spočte: Curve25519(a, Curve25519(b, 9))
- Bob si spočte: Curve25519(b, Curve25519(a, 9))
Můžeme si to ilustrovat opět násobením – jako by se posílalo a•9 a b•9, obě strany pak přijaté číslo vynásobí svým privátním klíčem a skončí tak s a•b•9 == b•a•9 (operace je komutativní). Na konci se toto sdílené tajemství ještě zahashuje.
Implementační specifika Curve25519
První implementace pro Pentium a Athlon
Koordináty křivky Curve25519 a privátní klíče pocházejí z konečného pole Fp, kde p = 2255 – 19. Pro reprezentaci prvků konečného pole se používají FPU registry a neceločíselný radix 225.5.
Oproti „naivní“ implementaci, kde by se prvek „rozsekal“ na 32bitová slova, to má tu výhodu, že je možné zdržovat normalizaci a mít koeficienty dočasně větší než radix. Analogie k dvojkové soustavě by vypadala asi tak, že bychom používali občas číslice 2 a 3 v mezivýpočtech, protože to zlepšuje algoritmus.
Praxe s pozdržováním normalizace koeficientů je zdá se celkem běžná u implementace ECC aritmetiky. Urychlují se tím operace na křivce. U Curve25519 se normalizace pozdrží až do doby, než se musí vrátit výsledek.
Implementace s ARM NEON instrukční sadou
NEON je instrukční sada pro vektorové operace na mnoha ARM procesorech, které se běžně používají v modernějších telefonech a tabletech. Důvod výběru této platformy pro implementaci je tudíž zřejmý.
Trochu zvláštní je, že kód byl napsán v meta-assembleru qhasm, který by se dal označit jako „platformně nezávislá“ mezivrstva mezi C a CPU-specifickým assemblerem.
Asi nebude překvapením, že i na této platformě byly cíle rychlost a odolnost proti postranním kanálům.
Curve41417
Křivka Curve41417 je celkem novinka, byla publikována teprve v červenci 2014. Název následuje podobnou konvenci jako Curve25519, je nazvána po prvočísle 2414 – 17, podle prvočíselného tělesa, nad kterým je křivka definována.
Proč potřebujeme tak obrovskou křivku?
Úroveň bezpečnosti mezi 280 a 2128 operací je ta, na kterou většina dnešních aplikací míří. Spodní hranice 80 bitů je spíš už pokládána za překonanou – dokážou ji upočítat třeba dnešní botnety.
Nicméně někteří autoři pořád argumentují, že pro klíče s krátkým trváním to postačuje. Například u DNSSEC se pořád používají 1024-bitové RSA zone signing keys, které jsou asi na úrovni „80bitové bezpečnosti“.
CAB Forum vyžaduje pro nově vydávané HTTPS certifikáty 2048-bitový modulus v případě RSA klíče, což zhruba odpovídá 112bitové bezpečnosti. RSA klíče velikosti 1024 bit už označuje za slabé i známý Qualys SSL/TLS server test.
Snad nikdo momentálně nezpochybňuje, že 128bitová bezpečnost postačuje pro většinu současných aplikací (sem spadají i eliptické křivky s 256 bitů velikými konečnými tělesy).
Úroveň bezpečnosti křivky Curve41417 odpovídá asi 212 bitům. Je úroveň nad 200 bitů k něčemu?
Křivce Curve25519 trvalo téměř 10 let, než byla dostatečně prověřena a začala se víc používat. Je celkem očekávatelné, že stejně dlouho bude trvat křivce Curve41417, než se začne používat v systémech, kde se dělá obtížně upgrade – právě v embedded systémech.
V embedded systémech pravděpodobně minimálně dalších 10 let vydrží a pro vygenerovaný klíčový materiál může být požadováno dalších několik let, aby zůstal neprolomitelný. Požadovat tedy odolnost na 30, 40 nebo i více let dává v těchto případech smysl.
Kromě samotného zvyšování dostupného výpočetního výkonu časem se musí ještě myslet na algoritmické průlomy. Ty nenastávají často, ale můžou být o to výraznější.
Například relativně nedávno se prolomila bezpečnost jedné speciální instance diskrétního logaritmu pro speciální křivky nad tělesy s malou charakteristikou. Z očekávaných 2128 operací zůstalo pouhých 259 operací.
Eliptické křivky nad tělesy s velkou prvočíselnou charakteristikou – kam patří i všechny Bernsteinovy křivky zde zmiňované – jsou něčím diametrálně odlišným, nežli křivky nad tělesy s malou charakteristikou. Ale stejně nelze zaručit, že k nějakému matematickému průlomu nedojde.
Budoucnost se těžko odhaduje, ale pravděpodobně se velikost křivky Curve41417 bude ještě hodit. Většinou je důvod nenasazení kryptografických primitiv s obrovskými parametry pomalost – problém, který tato křivka řeší výborně.
ČLÁNKY DO MAILU