Bernsteinovy eliptické křivky

Ondrej Mikle 25. 7. 2014

Křivka Curve25519 se v současnosti zabydluje ve více a více protokolech. Pojďme se podívat, co je na ní tak zvláštního. Snažil jsem se vybrat přednosti této křivky a křivek jí příbuzných a zajímavé implementační finty bez toho, aby se zabíhalo příliš do algebry. Řeč přijde i na úplnou novinku – Curve41417.

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ě.

Našli jste v článku chybu?
Lupa.cz: V Praze se otevřel první podnik s virtuální realitou

V Praze se otevřel první podnik s virtuální realitou

Měšec.cz: Se stavebkem k soudu už (většinou) nemusíte

Se stavebkem k soudu už (většinou) nemusíte

120na80.cz: Jaké plavecké pomůcky vaše dítě ochrání?

Jaké plavecké pomůcky vaše dítě ochrání?

Měšec.cz: Banky umí platby na kartu, jen to neříkají

Banky umí platby na kartu, jen to neříkají

120na80.cz: SOS aneb spálená pokožka

SOS aneb spálená pokožka

Podnikatel.cz: Profese budoucnosti? Úředník nepřežije

Profese budoucnosti? Úředník nepřežije

Podnikatel.cz: Selhala pokladna k EET. Kdo zaplatí pokutu?

Selhala pokladna k EET. Kdo zaplatí pokutu?

Měšec.cz: Investice do drahých kovů - znáte základní chyby?

Investice do drahých kovů - znáte základní chyby?

Měšec.cz: Kurzy platebních karet: vyplatí se platit? (TEST)

Kurzy platebních karet: vyplatí se platit? (TEST)

Lupa.cz: Seznam.cz sleduje stisky kláves, aby odhalil roboty

Seznam.cz sleduje stisky kláves, aby odhalil roboty

DigiZone.cz: Ve Varech představeni i noví "Četníci"

Ve Varech představeni i noví "Četníci"

120na80.cz: I tuto vodu můžete pít

I tuto vodu můžete pít

Podnikatel.cz: Prodej na Alibabě? Malí hráči utřou nos

Prodej na Alibabě? Malí hráči utřou nos

Podnikatel.cz: Polská vejce na českém pultu Albertu

Polská vejce na českém pultu Albertu

Vitalia.cz: Zmrzlinu? Ani snad ne

Zmrzlinu? Ani snad ne

Podnikatel.cz: Akční plán podpoří byznys padesátníků

Akční plán podpoří byznys padesátníků

DigiZone.cz: Skylink: do pátku může docházet k výpadkům

Skylink: do pátku může docházet k výpadkům

Měšec.cz: Do ostravské MHD bez jízdenky. Stačí vaše karta

Do ostravské MHD bez jízdenky. Stačí vaše karta

Root.cz: Bitcoin začal vyplácet jen půlku odměn

Bitcoin začal vyplácet jen půlku odměn

Podnikatel.cz: Tahle praktika stála šmejdy přes milion

Tahle praktika stála šmejdy přes milion