Published on 2005-04-05 at LinuxJournal

VIA PadLock - Ďábelsky rychlé šifrování

Michal Ludvig <michal@logix.cz> (c) 2005

[en] English version

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ázev xcrypt.
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 je xsha.
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ána montmul.

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:

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:

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:

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:

  1. 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.
  2. 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ášť :-)