Jakten på den fungerande kryptoimplementationen

Jag fick för en dryg vecka sedan skäl att börja arbeta med på en hårdvaruimplementation av blockkryptot CAST. Mer exakt CAST5 med stöd för 40, 80 och 128 bitars nyckel. Den referensdokumentation som finns för CAST är RFC 2144.

RFC:n innehåller tack och lov testvektorer. Men, vilket tyvärr är vädligt vanligt i kryptospecar brister det i entydighet. I fallet RFC 2144 är saker som bitordning på orden och nycklar mindre exakt specat. Det går att gissa, men hade underlättat om det var tydligare. Och det är nu en referensmodell är så värdefull.

Nu finns det ingen utpekad officiell referensmodell att hämta hem. Då är nästa steg att hitta en implementation, helst en som används och går att lita på fungerar. Tyvärr är kryptoimplementationer vanligen optimerade för prestanda med utrullade loopar, inline-assembler och andra trick som gör att dom strukturmässigt kan skilja rätt mycket mot specifikationen.

Sökning på nätet ger att Bruce Schneier har några stycken implementationer av CAST på den CD som följde med hans gamla bibel Applied Cryptography. Jag började titta på implementationen CAST-BAR (zipfil) och jösses.

Bibeln.
Bruce Schneiers stora röda. En bibel för kryptonörden. I dag ersatt av Cryptography Engineering.

Applied Cryptography är gammal, och CAST är ännu äldre (RFC 2144 är från 1997). Och koden i CAST-BAR har knappast åldrats med grace. Men det är faktiskt värre än så – den kan aldrig ha fungerat.

CAST är ett blockkrypto med en struktur som kallas SP-nät och är ett (balanserat) Feistel-krypto. Figuren nedan visar hur iterationen i CAST är uppbyggd:

Iterationen i CAST.

Notera speciellt de fyra lådorna märkta S-box1, …, S-box4. Dessa lådor innehåller de utbytestabeller (S-box) som ger olinjäriteten i CAST. Det finns fyra olika fixa S-boxar i CASTs iteration. Vidare finns det ytterligare fyra andra fixa (dvs med fixt innehåll, ej nyckel eller databeroende) S-boxar som del av kryptots nyckelexpansion. Totalt åtta tabeller om 256 stycken 32-bitars ord vilket kräver 8 kByte ROM-minne. Tabellerna finns listade i appendix A i RFC:n. Men i CAST-BAR finns inga tabeller.

Det som finns är en deklaration #include "cast_tab.h" som uppenbarligen pekar ut en fil där tabellerna skulle vara deklarerade. Men ingen sådan fil finns med i ZIP-filen. Nu var det inte jättesvårt att skapa sig en sådan fil med tabellerna och försöka bygga kryptot. Då kom nästa problem.

Jag kör som standard med den lysande kompilatorn clang (och llvm). Den hostade rejält på ett antal saker i koden. Inga speciellt allvarliga utifrån ett syntax-perspektiv. Men det det är uppenbart att C har blivit mycket striktare och (likt det jag efterfrågar från kryptospecar) mer entydigt. Koden i CAST-BAR är långt ifrån C99. Det gick dock bra att putsa till koden och få den att bygga (utan varningar). Dags att provköra:

js@snabbis>./cast
usage: cast [ n | -x | -y ]
n (integer) will encrypt n times (useful for timing tests)
-x will test the code by encrypting once (and print out the reference vector)
and then run the 1000000 iteration Full Maintenance Test (with reference output)
-y will test the code by encrypting once (and print out the reference vector)
and then run a shortened 1000 iteration Partial Maintenance Test (with reference output)
( which is more convenient for debugging than the Full test
This code is an implementation of CAST-128

js@snabbis>./cast -y
key is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a

Segmentation fault

Oops.
Test i debuggern visar att programmet hoppar rätt ut i skogen pekarmässigt. Lite koll på typer visar att det förutsätts implicit en massa storlekar som inte alls stämmer på en system med 64-bitars arkitektur. Jag testar att flytta koden till min utvecklingsmaskin sbox som kör 32-bit GNU/Linux. Och där fungerar det.

Dags att städa upp i typträsket. Jag gillar stdint.h. Den gör det entydigt vad man verkligen vill ha och kan vara (hyggligt) säker på att det man deklarerar stämmer på olika plattformar. En stunds arbete med att byta ut long int, unsigned char etc mot uint32_t, uint8_t etc och sedan är det dags för nytt försök på min 64-bitsmaskin:

js@snabbis>./cast -y
key is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a

Single Key-Plaintext-Ciphertext Test:
plaintext is: 01 23 45 67 89 ab cd ef
iter = 1
ciphertext is: 23 8b 4f e5 84 7e 44 b2
ref text is: 23 8b 4f e5 84 7e 44 b2
after decryption:
ciphertext is: 01 23 45 67 89 ab cd ef

Partial Maintenance Test (only 1000 iterations):
key is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a

a is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a
b is: 01 23 45 67 12 34 56 78 23 45 67 89 34 56 78 9a
a is: 23 f7 3b 14 b0 2a 2a d7 df b9 f2 c3 56 44 79 8d
ref a is: 23 f7 3b 14 b0 2a 2a d7 df b9 f2 c3 56 44 79 8d

b is: e5 bf 37 ef f1 4c 45 6a 40 b2 1c e3 69 37 0a 9f
ref b is: e5 bf 37 ef f1 4c 45 6a 40 b2 1c e3 69 37 0a 9f

Sådär. En fullt fungerande implementation av CAST. Synd bara att koden är skriven på ett i stort sett oläsbart och (försök till) prestandamaximerat sätt vilket gör den väsentligen oanvändbar som referensmodell.

Jag tycker att det inte är så konstigt om såpass gammal kod inte fungerar då de implicita förutsättningarna ändrats. I dag bör man i alla fall se till att koda på ett sätt som minimerar eller helst eliminerar implicita förutsättningar. Men att ingen sedan 1996 eller så testat CAST-BAR och sett att det saknas en fil är desto mer förvånande. Jag har haft kontakt med Bruce och levererat den uppdaterade, hela och fungerande versionen av CAST-BAR till honom. Den bör dyka upp på hans webbplats i närtid.

Så nu är det bara att jaga vidare efter en användbar referensmodell. Eller så får det bli som jag gjort mer än en gång – skriva en egen referensmodell i Python. Ett utmärkt språk för att skriva funktionella referensmodeller. All in a days work. Kul!

4 reaktioner på ”Jakten på den fungerande kryptoimplementationen

  1. Mycket trevlig blogg med bra matnyttig kryptoinfo.

    Dock måste jag påpeka att Applied Cryptography utgavs redan 1994 så den är alltså äldre än CAST. Den andra utgåvan (som du refererar till) utgavs något senare, 1995 enligt och 1996 enligt själv, men dock fortfarande innan . Köpte min kopia 1994 när jag lägligt var på besök över atlanten.

    Ja, jo, kollade utgivningsdatum i mitt nyaste ex. Så visst Scheniers stora röda är äldre än CAST. Tack för påpekandet och kul att du gillar bloggen.

    1. Blev lite tag-fel i inlägget… Följande skulle det stå:

      Mycket trevlig blogg med bra matnyttig kryptoinfo.

      Dock måste jag påpeka att Applied Cryptography utgavs redan 1994 så den är alltså äldre än CAST. Den andra utgåvan (som du refererar till) utgavs något senare, 1995 enligt Amazon och 1996 enligt Bruce Schneier själv, men dock fortfarande innan CAST RFC:n. Köpte min kopia 1994 när jag lägligt var på besök på andra sidan atlanten.

  2. Hmm, mitt svar blev uppenbarligen inlagt i din första kommentar. Det som borde varit en kommentar från mig var:

    Ja, jo, kollade utgivningsdatum i mitt nyaste ex. Så visst Scheniers stora röda är äldre än CAST. Tack för påpekandet och kul att du gillar bloggen.

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *

Följande HTML-taggar och attribut är tillåtna: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>