* 12 *

Kryptering

Ukens faktum

Kvante-computere er et teoretisk påfunn som benytter materiets egenskaper på kvante (mikroskopisk) nivå til å bygge en slags `datamaskin'. Kvante-computere vil ikke fungere som vanlige datamaskiner, de vil bruke helt nye prinsipper. Ifølge teorien kunne en kvante-computer knekke en standard krypteringsalgoritme på en brødel av et sekund. Racet for å bygge slike maskiner er i gang.

Kapittel 12 Gollmann

For noen år tilbake trodde man at kryptering ikke hadde noe å tilføre datasystemer. I dag er det motsatte tilfellet: kryptering er det siste slagordet for å selge dataprodukter. Det framlegges som en løsning til ethvert problem. Som vanlig ligger sannheten et sted mellom disse ekstreme posisjonene.

For å avrunde diskusjonen om softwaresikkerhet vil vi bruke denne forelesningen til å se på noen av de mest sentrale begrepene innen kryptering. Siden kryptering er et såpass stort emne må vi sikte nokså lavt og nøye oss med å:

Kryptering kan brukes for å overføre data via en kommunikasjonslinje eller for å lagre data på privat form. En krypteringsmetode krever i praksis en hemmelig nøkkel. Krypteringens sikkerhet avhenger av nøkkelens sikkerhet. I denne forelesningen tar vi det for gitt at nøklene er sikre.

Koder

En kode er en metode for å transformere lesbar tekst til en uleselig form. Koder ble brukt allerede i Julius Ceasars tid, med å permutere bokstaver etter veldefinerte regler. I filmen 2001: en romoddyse, har det f.eks. ofte blitt spekulert om navnet HAL (datamaskinen i filmen) ikke var en triviell kode for IBM (forskyv alle bokstaver fram en bokstav i alfabetet).

Under krigen ble koder utviklet til en teknologi. Idag bruker vi generelle kodealgoritmer basert på hemmelige nøkler for å øke deres fleksibilitet. Hvorfor trenger vi en nøkkel? En nøkkel er en parameter til krypteringsalgoritmen. Den forvandler en krypteringsalgoritme til en familie av krypteringsalgoritmer. Dersom vi hadde bare en kodetransformasjon ville alle måttet ha sin egne privatalgoritmer for å sørge for privatkommunikasjon. En algoritme per par. I tillegg, når koden ble knekket, ville de måtte skaffe en helt ny algoritme for å reparere skaden. Dette ville kostet altfor mye!

Det generelle prinsippet bak koder er å forvandle tekst til en uleselig form, i følge en veldefinert algoritme. Algoritmen må designes slik at det er praktisk umulig å invertere prosedyren uten kjennskap til en hemmelighet (nøkkelen).

Dersom vi bare er nødt til å forandre en parameter blir krypteringsmetoden lettere å vedlikeholde. Da gjør algoritmen beskjeden uleselig, mens nøkkelen gjør den privat.

Som Gollmann sier:

Kyptering er sjeldent løsningen av et sikkerhetsproblem. Kryptering er en oversettelsesmekanisme som forvandler et kommunikasjonssikkerhetsproblem til et nøkkeladministrasjonsproblem. Det er et klassisk tilfelle av sikkerhet gjennom obskuritet.

Kryptering er en kompleks og svært matematisk disiplin. Den er altfor omfattende til at vi klarer å dekke den i dette faget. Hensikten med denne forelesningen er å gi en smakebit på hvordan de to mest kjente krypteringsmetoder fungerer.

DES

Standardkrypteringsmekanismen i den vestlige verdene de siste 20 årene heter DES eller Data Encryption Standard. Den er basert på en symmetrisk kode (symmetric cipher), dvs en hemmelig nøkkel som er felles for begge parter i en samtale (ikke en asymmetrisk kode som RSA). Algoritmen ble utviklet på 70-tallet av de amerikanske myndightene. Den er fortsatt i bruk idag i en utvidet form som heter 3DES. Vanlig DES bruker en 56-bits nøkkel (plus en paritetsbyte). 3DES bruker tre ganger 56-bits for å øke vanskelighetsgraden til koden. Den er en iterasjon av DES:
3DES_encrypt(k1,k2,k3,message) = DES_encrypt(k1,DES_decrypt(k2,DES_encrypt(k3,message)))
DES er basert på transformasjoner, permutasjoner og masker. DES tar 32 bits med input om gangen og bruker en ikke-lineær funksjon til å utvide dem til en 48 bits blokk. Den 56 bits lange nøkkelen brukes som en database for å ekstrahere et antall 48 bits mindre-nøkler som da brukes til å maskere ut bits ved hjelp av en reversibel XOR. Disse permuteres og konverteres til output.

Basisalgoritmen kan brukes på to måter:

DES kryptering må ha input/output buffere med en størrelse som er et multiplum av 8 bytes.

RSA

Asymmetrisk offentlig/privat nøkkelkryptering ble moden da RSA algoritmen kom på banen. RSA kryptering er basert på modulo-aritmetikk (klokke aritmetikk) samt vanskelighetsgraden av å faktorisere produkter av store primtall modulo p.

Modulo-aritmetikk deler heltall inn i ekvivalensklasser. Dersom

\begin{displaymath}a = b ~{\rm mod}~m \end{displaymath}

så følger det at

\begin{displaymath}b = \lambda m + a \end{displaymath}

for et hvilket som helst helttall/integer $\lambda$. Vi kan, med andre ord, gå en hel omdreining rundt klokka og komme tilbake til samme sted. Det er ikke vanskelig å overbevise seg selv at følgende gjelder modulo m:

\begin{displaymath}(a ~{\rm mod}~m) + (b ~{\rm mod}~m) = (a + b) ~{\rm mod}~m \end{displaymath}

Mindre opplagt kanskje er denne:

\begin{displaymath}(a ~{\rm mod}~m) \times (b ~{\rm mod}~m) = (a \times b) ~{\rm mod}~m
\end{displaymath}

Denne kan forstås dersom vi skriver formelen slik:

\begin{displaymath}(a - \lambda m) \times (b -\lambda' m) = (ab - \lambda'' m)
\end{displaymath}

Merk at dette betyr at:

\begin{displaymath}(a ~{\rm mod}~m)^n = a^n ~{\rm mod}~m
\end{displaymath}

En spesiell egenskap av modulo-aritmetikk er at divisjon og multiplikasjon er den samme type operasjon, modulo m, fordi vi kommer alltid tilbake til lavere tall ved å fortsette rundt klokka i samme retning. Vi trenger ikke å gå bakover. Dvs at, mens inversen a-1 til et tall a, i vanlig aritmetikk alltid er 1/a, så er ikke det tilfellet i modulo-aritmetikk (som alltid dreier seg om heltall). Dersom tallet m er et primtall p, så fins det teoremer om spesielle egenskaper. Det er faktisk tilfellet at, for et hvilket som helst heltall som ikke er et multiplum av p, så er det alltid mulig å finne a-1 slik at

\begin{displaymath}a.a^{-1} = 1 ~{\rm mod}~p.
\end{displaymath}

Fermat's lille teorem (ikke i slekt med dens storebror) sier at, for et hvilket som helst primtall p,

\begin{displaymath}a^{p-1} = 1 ~{\rm mod}~p,
\end{displaymath}

sålenge a ikke er et multiplum av p. Dersom vi generaliserer denne ved å opphøye til en potens, så har vi

\begin{displaymath}(a^{p-1})^\alpha = a^{\alpha(p-1)}= 1^\alpha ~{\rm mod}~p = 1 ~{\rm mod}~p.
\end{displaymath}

RSA algoritmen er basert på disse egenskapene. Den begynner ved å generere to store primtall p og q og deres produkt pq. Størrelsenen p-1 og q-1 har en spesiell betydning på grunn av Fermats teorem. Krypteringsnøkkelen er da et random tall som ikke har noen felles faktorer med (p-1)(q-1). Dekrypteringsnøkkelen kan da beregnes som

\begin{displaymath}d = e^{-1} ~{\rm mod}~(p-1)(q-1)
\end{displaymath}

Dersom vi nå ønsker å kryptere en beskjed M (som har lengde mindre enn pq) regner vi den krypterte teksten ved

\begin{displaymath}C(M) = M^e ~{\rm mod}~pq.
\end{displaymath}

Dekrypteringen er gitt ved
C-1(M') = $\displaystyle {M'}^d ~{\rm mod}~pq$  
  = $\displaystyle (M^e ~{\rm mod}~pq)^d ~{\rm mod}~pq$  
  = $\displaystyle M^{ed} ~{\rm mod}~pq$  
  = $\displaystyle M^{\lambda(p-1)(q-1)+1} ~{\rm mod}~pq$  
  = $\displaystyle M ~{\rm mod}~pq$ (1)

Sikkerheten i RSA algoritmen har blitt testet grundig og viser seg å være svært god, bare produktet pq er stort nok.

RSA algoritmen er kostbar å beregne, slik at den vanligvis bare brukes under åpning av en protokoll for å etablere legitimasjon. Deretter brukes det en billigere form for kryptering med sesjonsnøkler for å overføre data.

Randomtall

For å bruke kryptering i praksis må vi generere random tall. Randomtall brukes til sesjonsnøkler og for å generere langvarige nøkler. De fleste randomtallgeneratorer krever et `frø' for å bootstrappe algoritmen. Ekte randomtall generatorer er vanskelige å lage. Mange bruker klokkeslett som frøet, men dette er lett å gjette seg fram til eller finne ut. Et bedre frø kan finnes ved å se på maskinens tilstand (f.eks. prosesstabellen) og kjøre den gjennom MD5 algoritmen for å komme frem til et helt unikt tall. Dette er umulig å gjette: for eksempel
DESMD5Random(digest)

char digest[16];

   /* Make a decent random number by crunching some system states through
      MD5. We can use this as a seed for pseudo random generator */

{ MD5_CTX context;
  int len;
  unsigned char buffer[bufsize],buff[bufsize];
  FILE *pp;
  char pscomm[bufsize];

printf("Looking for a good random number seed...\n");
cfMD5Init (&context);
sprintf(buffer,"%d%d",APPSTARTTIME,digest);
cfMD5Update (&context, buffer,bufsize);

/* Have to use /bin/ps -ef or /usr/ucb/ps aux for Solaris */
 
if ((pp = cfpopen("/bin/ps aux","r")) == NULL)
   {
   printf("Couldn't open the process list with command %s\n",pscomm);
   perror("cfpopen");
   return;
   }

while (!feof(pp))
   {
   ReadLine(buffer,bufsize,pp);
   cfMD5Update (&context,buffer,bufsize);
   }

cfpclose(pp);
 
cfMD5Final (digest, &context);
}

Denne kan brukes for å generere tre randomtall som kan brukes til 3DES nøkler:
 char digest[16];
 char seed[8],key[8];

 DESMD5Random(digest);
 bcopy(digest,seed,8);
 des_random_seed(seed);
 des_random_key(key);
 printf("%8.8s",key);
 des_random_key(key);
 printf("%8.8s",key);
 des_random_key(key);
 printf("%8.8s",key);

3DES kryptering

Programmering

Krypteringsfunskjonene krever litt oppsett. La oss anta at vi skal sende en hel fil (mange buffere etter hverandre) ved hjelp av kjedekryptering:
sprintf(in,"Message");

cfencrypt(in,out,DES1,DES2,DES3,strlen(in));

if ((send(sd,out,bufsize,0)) == -1)
   {
   return false;
   }

...(transfer)

if ((n_read = recv(sd,inbuffer,bufsize,0)) == -1)
   {
   return false;
   }

cfdecrypt(inbuffer,outbuffer,DES1,DES2,DES3,bufsize);

printf("%s",outbuffer);
Funskjonene defineres som følger, ved hjelp av biblioteksfunksjonene i OpenSSL:
cfencrypt(in,out,key1,key2,key3,len)

char *in,*out;
char key1[8],key2[8];
int len;

{ char workvec[bufsize];
  des_key_schedule ks1,ks2,ks3;

des_set_key((C_Block *)key1,ks1);
des_set_key((C_Block *)key2,ks2);
des_set_key((C_Block *)key3,ks3);

memset(workvec,0,bufsize);

des_ede3_cbc_encrypt(in,out,(long)len,ks1,ks2,ks3,(C_Block *)workvec,DES_ENCRYPT);
}

Dekrypteringen settes da opp slik:
cfdecrypt(in,out,key1,key2,key3,len)

char *in,*out;
char key1[8],key2[8],key3[8];
int len;

{ char workvec[bufsize];
  des_key_schedule ks1,ks2,ks3;

memset(workvec,0,bufsize);
des_set_key((C_Block *)key1,ks1);
des_set_key((C_Block *)key2,ks2);
des_set_key((C_Block *)key3,ks3);

des_ede3_cbc_encrypt(in,out,(long)len,ks1,ks2,ks3,(C_Block *)workvec,DES_DECRYPT);

out[len] = '\0';

Debug("Decrypted %d to [%d]\n",len,strlen(out)); 
}

Dersom vi ikke initialiserer workvectors og keys korrekt vil ikke dekrypteringen lykkes.

Sesjonsnøkler

Dersom vi ønsker å bruke en engangsnøkkel, dvs et forskjellig nøkkelsett for hver transaksjon, trenger vi allikevel en felles nøkkel for å komme igang.
  1. Etablere en forbindelse.
  2. Generer random sesjonsnøkkel.
  3. Krypter sesjonsnøkkelen med felles nøkkel (avtalt på forhånd).
  4. Send random sesjonsnøkkel til andre siden som en del av protokollen.
  5. Den andre maskinen dekrypterer sesjonsnøkkelen med felles nøkkel.
  6. Deretter krypteres all kommunikasjon ved hjelp av sesjonsnøkkelen.
Etter at maskinene har byttet sesjonsnøkkel kan de fortsette å kommunisere ved hjelp av sesjonsnøkklene. Det er kun under den initiale transasjonen at en fellesnøkkel trengs.

SSL

SSL er industriens standardprotokoll for WWW tjenesten. Den er utviklet av Netscape Communications. SSL er et sett med transparente `wrappers' som krypterer socket-basert kommunikasjon mellom maskiner, ved hjelp av RSA. Biblioteket OpenSSL innholder alt som trengs for å lage SSL applikasjoner gratis. Dette er skrevet i Australia og andre steder utenfor USA og kan dermed brukes fritt i Europa. Web browsere bruker SSL til å kommunisere privat med servere over en sikker linje (HTTPS).

OpenSSL pakken innholder eksempler på hvordan SSL applikasjoner virker. Vi skal ikke gjenta disse, men heller sammenligner en SSL klient med en vanlig socket klient. En vanlig klient socket forbindelse startes ved å kalle:

sd = socket(..);
connect(sd,address..);

  {
  write(sd..)  or send(sd ..)
  read(sd... ) or recv(sd ..)
  }

close(sd);

I SSL åpner klienten en vanlig socket og så startes det en SSL sesjon på socketen. Deretter bytter man bare ut de vanlige read/write (recv/send) systemkall med de tilsvarende SSL kommandoer:

sd = socket (..);

err = connect(sd ... );

  /* Now we have TCP conncetion. Start SSL negotiation. */

ssl = SSL_new (ctx);
SSL_set_fd (ssl, sd);

err = SSL_connect (ssl);

server_cert = SSL_get_peer_certificate (ssl);

printf ("Server certificate:\n");

str = X509_NAME_oneline (X509_get_subject_name (server_cert),0,0);

  {
  err = SSL_write (ssl, "Hello World!", strlen("Hello World!"));
  err = SSL_read (ssl, buf, sizeof(buf) - 1);                    
  }

SSL_shutdown (ssl);  /* send SSL/TLS close_notify */
close (sd);
SSL_free (ssl);
SSL_CTX_free (ctx);                                             
Bortsett fra nøkkelforhandlingene ved oppstart, og litt opprydding til slutt, er det svært lite arbeid for programmerere. SSL sertifikater må genereres på omtrent samme måte som vi brukte for å sette opp Secure Shell i en tidligere oppgave.

Ukens tanke

Noen system administrasjonspakker skryter av at de er sikre fordi de kommuniserer kun over krypterte linjer. Øker krypteringen din tillit til informasjon du mottar fra noen? Gjelder kryptering bare fortrolighet. Hva med autentisering?

Back