VIA PadLock - Ďábelsky rychlé šifrování
Michal Ludvig <michal@logix.cz> (c) 2005
![[en]](http://www.logix.cz/michal/img/en.gif)
Firma VIA Technologies vyrábí cenově dostupná CPU s hardwarovou podporou kryptografických funkcí. Díky tomu můžete svá data šifrovat rychlostí o jaké se vám nesnilo a navíc si u toho ani neuvaříte procesor.
Asi každý, kdo někdy šifroval nějaká data brzy zjistil, že je to činnost dost náročná na výkon procesoru. Cenou za pocit bezpečí při používání šifrovaného filesystemu je na starších počítačích značné snížení rychlosti přístupu k souborům, na novějších systémech alespoň výrazné vytížení procesoru. Podobné je to se zabezpečením síťového provozu (např. IPsec) kde už i na 100Mbps síti může dojít k problémům.
Řešení se nabízí několik:
- Nešifrovat
- To je na první pohled nejlevnější varianta, ale může přijít pěkně draho.
- Smířit se se zpomalením
- Prozatím většinové řešení
- Použít přídavný šifrovací akcelerátor (např. na PCI)
- Ne vždy výrazně pomůže, protože data musí častěji cestovat po sběrnici tam a zpátky.
- Pořídit si CPU od firmy VIA s technologíí PadLock
- Cože? To neznám! :-))
VIA PadLock
Firma VIA přišla s jednoduchou, i když poněkud kontroverzní myšlenkou: vybereme pár šifrovacích algoritmů a "zadrátujeme" je přímo do procesoru. Výsledkem je procesor třídy i686 (podobně jako Pentia či Athlony), který rozumí několika novým instrukcím starajícím se o vlastní šifrování. Tím vznikla technologie PadLock. Tento procesor samozřejmě sedí v klasickém motherboardu, má připojené běžné periferie a jelikož jde o starou dobrou architekturu x86 můžete na takovém systému v pohodě nabootovat Linux nebo Windows a ani nemusíte tušit co se vám skrývá pod kapotou. Vás to ale pochopitelně zajímá...
Co to umí?
Jakými schopnostmi váš procesor oplývá závisí pochopitelně na jeho verzi. Ta je určena trojicí family-model-stepping (F/M/S), přičemž family má vždy hodnotu 6, což znamená že jde o procesor třídy i686. Pokud model=9 pak máte procesor zvaný Nehemiah, pokud model=10 jde o procesor Esther (ten však ještě není na trhu). Položka stepping udává verzi každého modelu.
F/M/S procesoru se zjišťuje pomocí instrukce cpuid
,
případně v Linuxu si tyto hodnoty můžete přečíst v /proc/cpuinfo
.
- Nehemiah, stepping 3 a vyšší
- Obsahuje RNG - Random Number Generator, tedy
generátor náhodných čísel. Ta jsou odvozena z teplotního šumu
procesoru a tudíž velice kvalitní. Instrukce pro přístup k
RNG se jmenuje
xstore
. - Nehemiah, stepping 8 a vyšší
- Obsahuje dva nezávislé RNG a navíc
ACE - Advanced Cryptography Engine, který umí velmi rychle šifrovat a dešifrovat data algoritmem AES se všemi standardními délkami klíče (128b, 192b a 256b) v módech ECB, CBC, CFB a OFB. Instrukce se jmenujíxcryptecb
,xcryptcbc
, atd. Pro jednoduchost budu občas používat souhrnný názevxcrypt
. - Esther od steppingu 0
- Od předchozího modelu zdědil dvě RNG jednotky.
ACE zde bylo rozšířeno o mód CTR a počítání Message Authentication Code (MAC).
Navíc se zde objevují dvě nové zkratky:
PHE - PadLock Hash Engine umí spočítat hash (digest) bloku dat algoritmem SHA1 nebo SHA256. Doporučené jméno instrukce jexsha
.
PMM - PadLock Montgomery Multiplier, který má na starosti jednu z výpočetně nejnáročnějších operací asymetrické kryptografie (např. RSA), tedy spočítáníAB mod M kde A, B i M jsou velmi velká čísla (typicky 1024 nebo 2048 bitů). Příslušná instrukce byla nazvánamontmul
.
Ačkoliv jsem právě vyjmenoval spoustu různých instrukcí, budu v
následujícím textu mluvit převážně o xcrypt
. Většina
principů se samozřejmě vztahuje i na ostatní, ale
xcrypt
je v mnohém názornější.
Jak se PadLock používá?
Na rozdíl od běžných hardwarových šifrovacích karet, které se strkají
do PCI slotů je engine PadLock, jak již bylo řečeno, přímo
součástí CPU. Díky tomu odpadají veškeré komplikace s přístupem ke
sběrnici, s přerušeními, s asynchronními operacemi a podobně.
Zašifrovat blok paměti instrukcí xcrypt
je stejně snadné
jako ho zkopírovat instrukcí movs
.
Díky tomuto přístupu se šifrování stává téměř atomickou operací: před vykonáním instrukce jsou data nezašifrovaná a o pár hodinových cyklů později, jakmile instrukce skončí, jsou zašifrovaná (a pochopitelně naopak - PadLock umí data překvapivě i dešifrovat :-). Pokud program požadoval zpracování jediného bloku, který má v případě algoritmu AES délku 16 bajtů, tak je tato operace zcela atomická - šifrování neskončí někde v půlce a procesor nezačne dělat něco jiného dokud nebude mít hotovo.
Ovšem co když je potřeba zpracovat třeba gigabajt dat? Určitě
by nebylo fér na tu dobu zarazit veškeré ostatní operace a čekat až
bude vše hotovo. Procesor tedy může po každém zašifrovaném bloku
instrukci přerušit, uložit aktuální stav a jít dělat něco jiného -
třeba obsloužit přerušení, přepnout procesy, atd. Jakmile se
šifrující proces opět dostane na řadu, instrukce se automaticky
restartuje v místě kde předtím byla přerušena. Z toho důvodu jsem
napsal téměř atomická operace - pro volající proces se tváří
atomicky, ale procesor ji může přerušit, přesněji řečeno pozastavit.
Aktuální stav rozpracovanosti se samozřejmě ukládá přímo do paměti a
registrů příslušného procesu, čímž je šifrování umožněno mnoha
konkurenčním procesům zároveň - prostě se budou vzájemně přerušovat a
zase restartovat, ale jejich data se nepomíchají. Opět jde o stejnou
situaci jako v případě kopírování paměti instrukcí movs
.
Jak rychle?
Samotná VIA udává rychlost šifrování až 12GB/s. Takové rychlosti se vám ovšem těžko podaří dosáhnout. Už proto, že jen přístup do RAM je o dost pomalejší, takže byste procesor nestačili dostatečně rychle krmit daty.
Reálně dosahovaná rychlost závisí zejména na dvou faktorech:
- šifrovací mód - ECB je pochopitelně nejrychlejší, nejčastěji používané CBC zhruba o polovinu pomalejší.
- zarovnání dat - PadLock vyžaduje vstupní data zarovnaná na 16B hranicích. Pokud jsou jinak, je potřeba je před zpracováním zkopírovat do správně zarovnaného bufferu, což samosebou zdržuje.
Takže konečně se dostáváme k nějakým číslům. Benchmark OpenSSL vykazuje pro VIA Nehemiah 1.2Ghz tyto výsledky:
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes aes-128-ecb 11274.53k 14327.79k 14608.64k 14672.55k 14693.72k (software) aes-128-ecb 66892.82k 346583.52k 910704.21k 1489932.59k 1832151.72k (PadLock) aes-128-cbc 8276.27k 12915.75k 13264.13k 13313.02k 13322.92k (software) aes-128-cbc 48542.30k 241898.79k 523706.28k 745157.61k 846402.90k (PadLock)
Vidíme že velké bloky dat (8kB) je v ECB módu možné šifrovat rychlostí až cca 1.7 GB/s, zatímco v CBC módu je to cca 800 MB/s. Čím menší blok, tím více se uplatní režie knihovny OpenSSL a tím pádem je dosažena nižší rychlost. V porovnání se softwarovým šifrováním na stejném procesoru je PadLock 120x (ECB), resp. 60x (CBC) rychlejší.
Díky této ďábelské rychlosti je například IPsec na 100Mbps síti stejně rychlý jako nešifrovaný přenos (něco kolem 11MB/s). Stejně tak přístup na šifrovaný filesystem je výrazně rychlejší s PadLockem než se SW šifrováním: 49961 kB/s (PadLock) vs. 10005 kB/s (software). Test byl proveden na Seagate Barracuda v UDMA100 režimu a původní (plaintext) rychlost byla naměřena 61543 kB/s. PadLock je tedy o pouhých cca 20% pomalejší, zatímco software o téměř 85% oproti nešifrovanému stavu.
Podrobnosti a další výsledky k těmto testům jsem zpracoval na této stránce.
Podpora v Linuxu
Do linuxu jsem zatím napsal podporu jen pro AES (tedy instrukce
xcrypt
), protože mám k dispozici jen desku s procesorem
Nehemiah. Jakmile dostanu CPU Esther dopíšu i podporu
pro SHA/SHA2 a RSA.
Kernel
Pokud kernel potřebuje AES, standardně nahraje modul
aes.ko. V případě že chcete využít PadLock, musíte nahrát modul
padlock.ko - buď ručně pomocí modprobe
, nebo do
/etc/modprobe.conf
napíšete
alias aes padlock
tím pádem pokaždé když bude vyžadován algoritmus AES dojde automaticky k nahrání modulu padlock.ko.
Patche pro kernel jsou dostupné od verze 2.6.5. Těsně po vydání 2.6.10 je Linus akceptoval do svého stromu, takže od 2.6.11 bude modul padlock.ko k dispozici i bez patchování.
OpenSSL
Pokud jste odvážní a používáte CVS verzi OpenSSL tak od 2. srpna 2004 je podpora k dispozici přímo tam. Pokud používáte OpenSSL 0.9.7 tak si buď stáhnete patch a knihovnu překompilujete, nebo použijete distribuci, která ho obsahuje (např. SuSE Linux 9.2, dále jen SL 9.2)
Zda vaše verze OpenSSL podporuje PadLock nebo ne můžete zjistit Abyste zjistili, jestli vaše veze OpenSSL podporuje PadLock, použijte jednoduchý příkaz:
$ openssl engine padlock (padlock) VIA PadLock (RNG, ACE)
Pokud místo (RNG, ACE)
uvidíte (no-RNG,
no-ACE)
, znamená to, že vaše OpenSSL sice PadLock zvládá, ale
procesor nikoliv. Poslední možnost je, že dostanete nějakou chybovou
hlášku na téma no such engine. V tom případě je na čase se
poohlédnout po novější verzi OpenSSL.
Aby program využívající OpenSSL mohl těžit z výhod PadLocku, je
potřeba aby pro šifrování využíval tzv. EVP_interface (viz
man 3 evp
pokud máte nainstalovanou dokumentaci k OpenSSL)
a aby při inicializaci nahrál podporu pro hardwarové akcelerátory:
#include <openssl/engine.h> int main () { [...] ENGINE_load_builtin_engines(); ENGINE_register_all_complete(); [...] }
V SL 9.2 je takto upraveno například OpenSSH, takže šifrované přenosy po síti vám už nebudou zabírat tolik času.
Binutils
Pokud budete psát programy využívající výše uvedené instrukce, tak
máte dvě možnosti: buď použijete přímo jmého instrukce (např.
xcryptcbc
), nebo její opcode, neboli její
hexadecimální vyjádření (např.
.byte 0xf3,0x0f,0xa7,0xd0
)
Z důvodu zpětné kompatibility se staršími nástroji je prozatím lepší používat zápis pomocí opcode, nicméně Binutils 2.15 a novější již rozumí i přehlednějším symbolickým jménům. Jen pro úplnost dodávám, že balík binutils obsahuje např. programy gas (GNU assembler) či objdump a jeho knihovnu BFD, zodpovědnou m.j. za práci na úrovni instrukcí, využívá i debugger gdb. Výpis instrukcí v gdb tedy nyní může vypadat třeba takto:
(gdb) x/3i $pc 0x8048392: lea 0x80495f0,%edx 0x8048398 : repz xcryptecb 0x804839c : push %eax
Důvtipné čtenáře asi nepřekvapí, že SuSE Linux 9.2 má ve všech relevantních balíčcích patřičné patche. Pokud máte tu smůlu že používáte jinou distribuci, tak jí buď změnte, nebo přesvědčte jejího dodavatele aby do ní tyto patche zařadil. A nebo patchujte a kompilujte vlastními silami!
Programujeme PadLock
V následujících kapitolách ukážu několik principů programování PadLocku. Pro plné porozumění bude vhodná alespoň základní znalost architektury x86, assembleru a symetrického šifrování. Samozřejmě jsou zváni i čtenáři bez těchto znalostí, zas tak těžké to nebude :-)
Jak už víte, pro přístup k enginu PadLock vymyslela VIA
několik nových instrukcí. Podrobně se seznámíme s instrukcí
xcryptcbc
, pomocí níž nakonec zašifrujeme blok dat
algoritmem AES s délkou klíče 128 bitů v módu
CBC. Ostatní instrukce rodiny xcrypt
se používají
úplně stejně a i pro použití ostatních funkcí PadLocku (SHA, RSA, RNG)
platí podobné principy.
xcryptcbc
Tato instrukce nemá žádné explicitní operandy, naopak je pevně určeno, že co ve kterém registru před jejím vykonáním má být:
- ESI – Adresa zdrojových dat
EDI – Adresa cílových dat
EAX – Adresa inicializačního vektoru
EBX – Adresa šifrovacího klíče
ECX – Počet bloků ke zpracování
EDX – Adresa řídících dat (Control word)
Pokud nebude uvedeno jinak, musí být všechny adresy zarovnané na hranici 16 bajtů!
ESI/EDI - Adresy zdrojových/cílových dat
Tady není moc co vysvětlovat - prostě ukazatele na vstupní a výstupní buffer. Takže jen pár poznámek:
- Obě adresy mohou být shodné. Proto je možné šifrovat tzv. in-place.
- Velikost obou bufferů musí být shodná a dělitelná velikostí bloku, což je pro algoritmus AES 16 bajtů.
- Až přijde na trh CPU Esther, bude za určitých okolností možné mít zdrojová a cílová data na nezarovnaných adresách. Šifrování pak ovšem bude pomalejší.
EAX - Adresa inicializačního vektoru
Inicializační vektor je jeden z parametů, na kterém závisí výsledek šifrování (další jsou třeba vstupní data, klíč, atd.). Jeho velikost je shodná s velikostí bloku, tedy 16 bajtů. Nebudu zde vysvětlovat k čemu je IV dobrý - zvídavý čtenář si podrobnosti jistě dohledá sám.
EBX - Adresa šifrovacího klíče
Kromě IV je dalším vstupním parametrem šifrovací klíč (key, cipher key), který může mít délku 128b, 192b nebo 256b. Algoritmus AES interně používá tzv. expanded key, který je odvozen od daného šifrovacího klíče. Expanded key pro 128b klíč umí vypočítat PadLock sám. Pro delší klíče mu ho budeme muset předpřipravit.
ECX - Počet bloků ke zpracování
Instrukce xcrypt
se vždy vyskytuje s prefixem
rep
, který opakovaně vykonává danou instrukci, dokud v
registru ECX není nula. Po každém opakování, tedy zašifrování jednoho
bloku, je ECX samozřejmě o jedničku sníženo.
EDX - Control word
Aby PadLock věděl co přesně po něm chceme, musíme před každou operací vyplnit strukturu zvanou Control word, která obsahuje:
- Algoritmus - ovšem můžete si vybrat jen AES.
- Key size - délka klíče: jedna ze tří výše uvedených.
- Enc/Dec - směr: šifrování/dešifrování
- Keygen - zda připravíme expanded key, nebo to necháme na PadLocku.
- Rounds - udává kolika průchody bude blok zašifrován. Není mi úplně jasné proč je třeba tento údaj explicitně vyplňovat, protože standard AESu pro každou délku klíče uvádí i příslušný počet průchodů.
Datová struktura pro cword
bude v jazyce C vypadat takto:
union cword { uint8_t cword[16]; struct { int rounds:4; int algo:3; int keygen:1; int interm:1; int encdec:1; int ksize:2; } b; };
Union byl zvolen proto, aby pro Control word bylo vyhrazeno předepsané množství paměti, tedy 16 bajtů.
Příklad 1
Takže teorii máme za sebou a můžeme se vrhnout na skutečný příklad. Nejprve něco málo čistokrevného assembleru:
.comm iv,16,16 .comm key,16,16 .comm data,16,16 .comm cword,16,16 .text cryptcbc: movl $data, %esi #; Zdrojová data movl %esi, %edi #; Cílová data movl $iv, %eax #; IV movl $key, %ebx #; Klíč movl $cword, %edx #; Control word movl $1, %ecx #; Počet bloků rep xcryptcbc ret
Tento kousek kódu zašifruje obsah pole data
klíčem
key
a inicializačním vektorem iv
podle
parametrů nastavených v řídícím slově cword
. Všimněme si,
že zdrojová a cílová adresa jsou stejné, takže pracujeme in-place.
Jelikož pole data
má celikost jen jednoho bloku, nastavíme
do ECX jedničku.
Příklad 2
Pokud chceme PadLock používat v jazyce C máme dvě možnosti:
- Obslužné rutiny si napíšeme v assembleru, přeložíme do
samostatného modulu a k výslednému programu přilinkujeme. To má ovšem
spoustu nevýhod - kupříkladu překladač nemůže vložit příslušné
instrukce přímo do místa kde jsou potřeba, ale vždy je bude volat jako
podprogram instrukcí
call
. To samozřejmě trochu zdržuje. - Lepší bude vydat se cestou tzv. inline assembleru, tedy patřičné instrukce vložit přímo do C-čkového kódu.
Teorii nechám pro tentokrát stranou - zájemci si jistě do svého oblíbeného vyhledavače dokáží slova gcc inline assembler zadat sami a patřičné tutoriály si nastudovat. Takže vás nebudu napínat a rovnou si ukážeme výsledek:
static inline void * padlock_xcryptcbc(uint8_t *input, uint8_t *output, void *key, void *iv, void *control_word, int count) { asm volatile ("xcryptcbc" : "+S"(input), "+D"(output), "+a"(iv) : "c"(count), "d"(control_word), "b"(key)); return iv; }
Tenhle magický zápis kompilátoru řekne, aby do příslušných registrů
naplnil hodnoty parametrů input
, count
, ...,
pak aby vygeneroval instrukci xcryptcbc
a nakonec adresu,
která se po zpracování instrukce bude nacházet v registru
EAX
vrátil jako ukazatel na nový inicializační vektor.
Aby náš pokus skončil úspěchem, budeme muset ještě správně vyplnit control word. Ze všeho nejdřív je dobré ho smazat, aby tam náhodou nebyly nějaké nesmyslné hodnoty třeba ze zásobníku:
memset(&cword, 0, sizeof(cword));
Nyní už můžeme pěkně po pořádku vyplnit všechny položky. První na řadě
je rounds
- tato položka říká, kolik průchodů šifrovacím
algoritmem se má provést. Autoři algoritmu určili pro AES128 10
průchodů, pro AES192 jich je 12 a pro AES256 je to 14
průchodů. Pokud v proměnné key_size
budeme mít délku
klíče v bajtech, zinicializujeme rounds
takto:
cword.b.rounds = 10 + (key_size - 16) / 4;
Další na řadě je položka algo
. Tou by mělo být možné
vybrat šifrovací algoritmus, ale protože současné verze PadLocku
podporují jen AES, není z čeho vybírat a ponecháme zde nulu.
Do položky keygen
dáme jedničku v případě, že PadLocku
připravíme expanded key sami. Pokud tuto práci necháme na něm,
což je však možné jen pro AES128, necháme v keygen
nulu.
cword.b.keygen = (key_size > 16);
Položka interm
umožňuje zaznamenat mezivýsledek po každém
průchodu algoritmem. Po tom nijak extra netoužíme, takže zde necháme
nulu.
Jestli máme v úmyslu data zašifrovat nebo rozšifrovat se PadLock dozví
z položky encdec
. Nula je šifrování, jednička
dešifrování. Ještě nám zbývá vyplnit délku klíče. Musíme se
vejít do dvou bitů:
cword.b.ksize = (key_size - 16) / 8;
Hotovo. S takto vyplněným řídícím slovem a všemi správně zarovnanými
adresami můžeme zavolat výše popsanou magickou funkci
padlock_xcryptcbc()
a pokud nám budou elektrony
nakloněny, dočkáme se zašifrování našich dat.
Závěr
Dokumentace k PadLocku je veřejně dostupná na stránkách společnosti VIA, takže další podrobnosti o záludnostech programování tohoto chipu si zájemci jistě najdou sami. Kompletní, funkční příklad zašifrování jednoho bloku dat, včetně ověření výsledku knihovnou OpenSSL můžete najít na mých stránkách. Šifrování zdar a PadLocku zvlášť :-)