REDUNDANS I SIKKER OG PÅLITELIG KOMMUNIKASJON

Utfordringen i professorstafetten fra professor Helge Dahle var: Hva kan kode/krypto gruppen gjøre for å hindre min PC for å bli utsatt for hacking? Dette er omfattende og viktig problem uten noen enkel og direkte løsning. I dag er det overlatt til den enkelte PC bruker eller systemansvarlige ved de enkelte institutter å sørge for hjelp med å ta i bruk nødvendige brannmurer og implementere passordrutiner og gi gode råd om hva en bør og ikke bør gjøre. Ved Institutt for Informatikk har kode/kryptogruppen et videregående kurs i datasikkerhet som belyser noen av de problemstillinger som må vurderes for å forhindre ”hacking” i våre dagers datasystemer.

Da en kort artikkel ikke er nok for å beskrive løsningen til omfattende ”hacking” problemer, vil jeg legge mer vekt på å beskrive noen av de problemstillinger som kode/kryptogruppen ved Institutt for Informatikk arbeider med og har gitt vesentlige internasjonale bidrag til. Gruppen er i ferd med å opprette et senter: Ernst Selmer Senteret for forskning innen pålitelig og sikker digital kommunikasjon. Forskningsområdene i gruppen omfatter kodeteori, som brukes for å hindre feil ved overføring av data over et upålitelig transmisjonsmedium, samt kryptografi, som gir både sikker kommunikasjon over en overvåket kanal slik at kun rette vedkommende kan lese dataene og i tillegg sikrer at data som mottas kommer uendret fra den personen som utgir seg for å ha sendt disse.

Sikker og pålitelig kommunikasjon

I alle moderne kommunikasjonsystemer er det store krav til sikkerhet og pålitelighet. Pålitelig dataoverføring oppnås ved å benytte feilkorrigerende koder, mens sikkerhet mot innsyn og forfalskning av data oppnås ved å benytte metoder fra kryptografi. Kode/kryptogruppen ved Institutt for Informatikk har forsket innen de to beslektete fagfeltene kodeteori og kryptografi, og har bidratt med mange forskningsresultater som også er valgt til internasjonale standarder innen disse fagfeltene. Vi vil først beskrive disse områdene og angi noen vanlige anvendelser som blant annet inkluderer metoder som implementeres for å hindre ”hacking” på din PC.

Kodeteori

Dette omhandler metoder for å korrigere feil som oppstår når data sendes over en kanal som er utsatt for støy. Typiske kanaler er telefonlinjer, satellitt forbindelser eller lagringsmedia. Data som sendes i moderne kommunikasjonssystemer representeres av 0’ere og 1’re. Noen ganger blir en 0’er som er sendt mottatt som en 1’er eller omvendt. De underliggende fysiske lover gjør at dette er umulig å unngå, men virkningene av slike feil kan dramatisk reduseres ved å bruke kodeteori. De første viktige anvendelsene av kodeteori var ved kommunikasjon til et bemannet eller ubemannet romfartøy. De store avstandene krevde at eventuelle feil som oppsto underveis under kommunikasjonen med jorden ble korrigert automatisk når de ble mottatt i romfartøyet. Dette krevde anvendelse av feilkorrigerende koder.

Kodeteori som fagområde ble startet av Shannon i 1948 som med sitt banebrytende arbeid ”A Mathematical Theory of Communication” viste at enhver kanal som var utsatt for støy hadde en kapasitet, som i prinsippet kunne beregnes. Det er mulig å overføre informasjon feilfritt inntil kapasiteten til kanalen ved å bruke feilkorrigerende koder.

Hovedideen for å korrigere feil som oppstår ved overføring av data som sendes over en kanal utsatt for støy, er å sende i tillegg til informasjonen litt ekstra redundante data som er konstruert med det formål kun å korrigere feil som kan oppstå. Vi vil gi noen enkle eksempler som illustrerer metodene for å oppnå feilkontroll av data som overføres.

Repetisjonskoden

Repetisjonskoden gjentar dataene, som sendes flere ganger. La oss illustrere bruk av denne enkle koden når data skal overføres over en kanal der 1 av 1000 bit i gjennomsnitt er feil. Dette kan være typisk for en dårlig kanal. Uten feilkontroll vil antall feil dette medfører være for omfattende når typiske hastigheter kan være flere millioner bit i sekundet. Dette vil medføre flere tusen feil i sekundet noe som vil være uakseptabelt i de fleste anvendelser som krever pålitelig overføring.

For å øke påliteligheten av dataene er en mulig metode å gjenta hver bit som sendes 5 ganger. Dette gir en ”kode” med to ”kodeord” 00000 og 11111. Det første kodeordet representerer 0 og det andre kodeordet representerer 1. Ulempen med dette er at en sender fem ganger mer informasjon enn strengt tatt nødvendig, men til gjengjeld blir overføringen atskillig mer pålitelig, noe vi vil diskutere nedenfor.

Når kodeordet 00000 eller 11111 sendes, kan de sendte fem biter mottas feil på grunn av at vi antar at kanalen utsettes for støy. Da det er mer sannsynlig at en bit er feilfri enn at den er feil vil beste strategi være å ”dekode” de fem mottatte biter til majoriteten av de fem bitene. For eksempel: hvis 01111 mottas, vil denne bli dekodet til 1 og 10100 vil bli dekodet til 0. For å dekode en bit feil måtte minst 3 av fem biter være feil og dette er mye mindre sannsynlig enn at en enkel bit er feil. For eksempel: hvis kanalen som bitene ble sendt over typisk gjorde feil ved 1 av 1000 bit, så ville sannsynligheten for at tre av fem biter var feil være en av 100 millioner. Altså er sannsynligheten for at en bit er feil etter denne majoritetsdekodingen være redusert fra 1 av 1000 til 1 av 100 millioner. Redundansen har medført en mye større pålitelighet på bekostning av at vi har sendt hver bit fem ganger.

I virkeligheten benyttes atskillig mer sofistikerte og mer effektive koder enn repetisjonskoden. Valg av koden avhenger av hvor mye feil og hvilke typer av feil det er på den aktuelle kanalen, og av hvor viktig det er at dataene er feilfrie. Dette krever også avanserte teknikker for å konstruere gode koder som i tillegg til å redusere feilsannsynligheten er raske å dekode.

Hammingkoden

Et lite eksempel er vist nedenfor på hvorledes en kan korrigere enkle feil med en litt mer sofistikert metode enn repetisjonskoden. Dette er et eksempel på Hammingkoden som ble funnet i 1950 av Richard Hamming, og som er en av de første kodene som ble tatt i bruk i praksis.

Hammingkoden (i dette eksemplet) sender fire biter med informasjon, og benytter tre redundante biter til feilkontroll. En beskrivelse av hvorledes de tre feilkontrollbitene er valgt er illustrert av de tre sirklene nedenfor. De tre sirklene i Figur 1 skjærer hverandre i 7 områder, som vi nummererer fra P1 til P7. De fire områdene felles for minst to sirkler nummereres P1 til P4. De fire informasjonsbitene plasseres med en bit i hver av disse områdene. I hver av de tre sirklene er det et ekstra område. En feilkontroll bit plasseres i hvert av disse områdene slik at hver sirkel får et jevnt antall 1’ere.

Figur 1.

Et enkelt eksempel er vist i Figur 1. Anta vi vil sende informasjonen 1011 over en kanal som er utsatt for støy. Siden informasjonsbitene i posisjon 1, 3 og 4 alle er 1’ere plasserer vi 1’ere i de tre områdene P1, P3 og P4. Siden informasjonsbiten i posisjon 2 er 0 plasserer vi en 0’er i område P2. Vi lager de tre feilkontrollbiter ved å velge bitene i de tre øvrige områdene slik at hver sirkel har et jevnt antall 1’ere. Vi ser at dette krever 0 i områdene P5 og P6 samt 1 i området P7. Dette betyr at vi sender 1011001 over kanalen.

Vi kan alltid korrigere enhver enkel feil som oppstår ved overføringen. La oss demonstrere dette ved å anta at det oppstår en feil i posisjon 2 slik at 1111001 mottas. Hvorledes kan vi enkelt finne feilen? Den enkle fremgangsmåten er å plasseres de sju bitene i de sju tilsvarende områdene. Vi ser av Figur 2 at de to øverste sirklene har et odde antall enere og at den nederste har et jevnt antall 1’ere. Altså: om det er en enkel feil må den være i alle sirkler med odde antall 1’ere og ikke i sirkler med jevnt antall 1’ere. I vårt tilfelle må feilen derfor være i område P2, dvs i posisjon 2. Det som er sendt er derfor 1011001 og den enkle feilen er derfor korrigert. På denne måten kan vi forbedre påliteligheten ved dataoverføringen.

Figur 2.

I slutten av 50’årene og 60’årene ble mer avanserte koder konstruert. Blant disse var Reed-Solomon kodene. På denne tiden var teknikken ikke moden for å ta disse i bruk, men i dag er disse implementert i alle CD spillere. Enhver CD spiller benytter seg faktisk av to Reed-Solomon koder, så nesten alle hjem eier i dag flere feilkorrigerende koder. Videre brukes koding for feilkontroll i DVD spillere, harddisker, modemer, mobiltelefoner, kollisjonsputer og i mange andre anvendelser. En kuriositet er at kodeteori også har anvendelser i tippesystemer i fotball. Faktisk er en av de første og mest berømte kodene funnet av Golay i 1949 presentert i et finsk tippeblad i 1947. Denne koden har også vært til salgs i norske tippeblader.

I tredje generasjons systemer for mobilkommunikasjon er ofte hver bruker/apparat utstyrt med en signatursekvens som består av 0’ere og 1’ere. Når mange brukere kommuniserer samtidig, stiller dette strenge krav til utvelgelsen av signatursekvensene til brukerne for å forbedre kvaliteten på kommunikasjonen. Metodene for å velge ut de beste sekvensene er basert på ideer fra kodeteori. Kode/kryptogruppen har sammen med tre amerikanske forskere konstruert en familie sekvenser som er valgt som standard for tredje generasjons mobilkommunikasjon.

Feilkontroll i personnummer

Det norske personnummer systemet består som kjent av 11 sifre, hvorav de seks første er fødselsnummeret, og de tre neste er et nummer tildelt for å skille personer født samme dag. De to siste sifrene er konstruert utelukkende til feilkontroll. Disse to sifrene er laget ved å benytte spesielle matematisk sjekksummer som medfører at feil i ett siffer, ombytting av måned og dato, og noen andre vanlig forekommende feiltyper blir oppdaget (men ikke korrigert). Feilkontroll av personnummer systemet er konstruert av professor Ernst Selmer, som var en av pionerene i feilkorrigerende koder og kryptografi i Norge.

Tilsvarende feilkontroller er i våre dager tatt i bruk i strekkodesystemet som brukes i varehandel, og ISBN-kodesystemet som er det internasjonale systemet som brukes til å merke bøker.

Kryptografi

Til alle tider har det vært viktig å beskytte kommunikasjon av sensitive data fra sender til mottaker. Tradisjonelt har metoden vært å kryptere dataene ved at sender og mottaker har hatt en felles hemmelig nøkkel som brukes ved krypteringen. Det betyr at alt som sender krypterer med en hemmelig nøkkel, kan leses av mottaker dersom han har samme nøkkel.

I 1970’årene kom et gjennombrudd i kryptografien. Da ble offentlig nøkkel (public-key) kryptosystemet oppfunnet. I dette tilfellet hadde hver bruker to nøkler: en offentlig nøkkel samt en tilhørende privat nøkkel. Dette fungerte slik at for å sende en hemmelig melding til en person kunne en benytte hans offentlige nøkkel til å kryptere meldingen. For å dekryptere meldingen bruker mottageren sin tilhørende private nøkkel, og dermed er han den eneste som kan lese meldingen, forutsatt at han holder sin private nøkkel skjult for alle andre.

Det faktum at en bruker i et offentlig nøkkel system har en privat nøkkel som bare han kjenner gir også muligheter for å lage en ”digital signatur” av en melding. Dette skjer ved at han bruker den private nøkkelen til signering. Alle andre brukere kan, ved å bruke den tilhørende offentlige nøkkelen, verifisere at signaturen er gyldig. Uten offentlig nøkkel kryptografi er det ikke uten videre mulig å signere meldinger på samme måte, da sender og mottaker har samme nøkkel.

Meldingsintegritet

I mange situasjoner er meldingen som skal signeres så lang at en av effektivitetshensyn kun signerer en komprimert versjon (fingeravtrykk) av meldingen. Derfor er det utviklet metoder som komprimerer en digital melding til et fingeravtrykk (typisk 160 biter) på en rask og effektiv måte, slik at det er ekstremt vanskelig å konstruere en annen melding som gir samme fingeravtrykk. En kan da nøye seg med å signere fingeravtrykket istedenfor hele meldingen. Konstruksjon av kryptografisk sikre komprimeringsalgoritmer (hashingalgoritmer) er et meget vanskelig problem, da metoden som benyttes til å lage fingeravtrykket er offentlig og ingen hemmelig nøkkel benyttes. Det er viktig at alle bits i meldingen inngår på en komplisert måte i konstruksjonen av fingeravtrykket.

Meldingsautentisering

I mange anvendelser er det viktigere å være sikker på at en melding som overføres ikke er endret under overføringen, enn at den er hemmeligholdt. For eksempel er det viktig å sikre seg mot endring av beløp eller kontonumre ved finansielle transaksjoner. Dette oppnås ved å konstruere en ”meldingsautentiseringskode(MAC)” til hver melding.

Sender og mottager har da en felles nøkkel K som brukes til autentisering av meldinger. Når meldingen M sendes lages samtidig meldingsautentiseringskoden MAC_K(M) som sendes som et vedlegg til meldingen. Denne er konstruert slik at det er praktisk umulig uten kjennskap til K å lage MAC_K(M). Mottageren som kjenner K kan da verifisere at meldingen er autentisk ved å verifisere at meldingsautentiseringskoden som sendes som vedlegg stemmer overens.

Dersom noen prøver å endre meldingen M under transmisjonen vil han ikke kunne endre meldingsautentiseringskoden tilsvarende uten å kjenne nøkkelen. Kode/kryptogruppen har bidratt til internasjonale standarder som brukes i meldingsautentisering. Dette har også andre viktige anvendelser. For eksempel ved å utstyre filer med meldingsautentiseringskoder, kan en sjekke at ingen filer i systemet har blitt endret av uautoriserte prosesser som virus etc.

Moderne kryptografi og umulige problemer

I de siste 25 år har kryptografien løst problemer som tilsynelatende ser helt umulig ut. Et eksempel er at to parter som aldri har møtt hverandre før kan utveksle en felles nøkkel over en kommunikasjonslinje som overvåkes, slik at en som observerer kommunikasjonen ikke kan bestemme nøkkelen.

Det er også mulig ved hjelp av metoder i kryptografi å løse det tilsynelatende umulige problem å kaste mynt og krone over telefon på en rettferdig måte selv for to parter som ikke stoler på hverandre. Det er også utviklet metoder i kryptografi for å identifisere seg ovenfor en annen person på en slik måte at en som overhører informasjonen som utveksles i en identifikasjon prosess, ikke kan misbruke denne informasjonen til å utgi seg for å være en annen.