Kryptografi: Kryptografi (litt om mye, men egentlig uten å gå idybden om noe) Bjørn Remseth Matematisk institutt, Universitetet i Oslo Thomas Gramstad Internettlærer & skribent


Ubåtkrigføring under annen verdenskrig: Ubåtkrigføring under annen verdenskrig


Enigma: Vant Turing krigen?: Enigma: Vant Turing krigen? “In iceland I had been interrogating the survivors of the many merchant ships sunk in the, at first, highly successful offensive against the Atlantic convoys launched by the U-boats in March 1941. I had spent many yours trying to analyse their strength and tactics. I could have spared my pains. For now I discovered that all this, and everything else about the U-boats, was known with precision by those privy to the Enigma decrypts” (Edward Thomas, in “Codebreakers”, min understrekning)


Innledning og oversikt: Innledning og oversikt Kort om hemmelige koder Terminologi, hva er ubrytelige koder, hvorfor man vanligvis ikke bruke slike. Hva betyr bitlengde for sikkerhet? Hva er moderne kryptosystemer Hva er RSA, IDEA, DES og PGP? Svakheter i realistiske kryptosystemer? Politikk Hvorfor er kryptografi så himla viktig ?


Kort om hemmelige koder: Kort om hemmelige koder


Terminologi:: Terminologi: Holde en melding hemmelig: Kryptere Bryte en kode: Kryptoanalysere Vise opprinnelse: Autentisere


Kryptoanalyse: Hvordan knekke koder: Kryptoanalyse: Hvordan knekke koder Innfallsvinkler Knekke en melding (bryte nøkkelen) Knekke en algoritme (bryte alle nøkler) Knekke kneskåler («rubber hose cryptography») Vanskelig og mangslungen disiplin!


Overordnet, for ideelle kryptosystemer gjelder:: Overordnet, for ideelle kryptosystemer gjelder: Så lenge nøklene holdes hemmelige, holdes meldingene hemmelige Systemene skal være: Enkle, raske, sikre Problem: Generelt får man bare velge to av egenskapene over. ... Og vi skal etterhvert forstå hvorfor :-)


Et perfekt kryptosystem: “Engangsnøkler”: Et perfekt kryptosystem: “Engangsnøkler” Metode Like mange tilfeldige biter, som det er biter i klarteksten Kodemelding er klartekst XOR nøkkel Nøkkel like lang som melding Sikker og rask, men ikke enkel! Nøkkeldistribusjons-systemet må være komplisert. Himla mye nøkkel skal distribueres!


Komponenter system for å holde en melding hemmelig: Komponenter system for å holde en melding hemmelig Hold en melding hemmelig: Original melding Kodenøkkel Krypter Original melding Dekodenøkkel Dekrypter Kryptert melding Nøkkelutvekslingskanal


Symmetriske og asymmetriske nøkler: Symmetriske og asymmetriske nøkler (Kodenøkkel = Dekodenøkkel) => Symmetrisk IDEA, DES, «One Time Pad», .... Ofte raske algoritmer (Kodenøkkel != Dekodenøkkel) => Asymmetrisk RSA, «offentlig nøkkel kryptering» Langsommere enn symmetriske algoritmer Største nyvinning innen kryptografi de siste par-tre tusen år?


En praktisk krypto-algoritme: DES: En praktisk krypto-algoritme: DES Overblikk over algoritmen Mer detaljert enn de fleste vil like :-) Angrep mot algoritmen Mulige forbedringer


DES (Data Encryption Standard): Overblikk: DES (Data Encryption Standard): Overblikk Amerikanske myndigheter ønsket på tidlig syttitall en standard kryptoalgoritme DES ble valgt. Designet av IBM, testet og godkjent av NSA Teknologi 16 runders blokk-algoritme, HW-optimalisert. NB: Første offentlig kjente algoritme NSA stemplet som “Sikker nok for det meste”!!!


DES detaljer: Feistel-nettverk: DES detaljer: Feistel-nettverk L i-1 R i-1 K i-1 L i R i 32 bit “Runde”- funksjon


DES: Nøkkel-permutasjoner: DES: Nøkkel-permutasjoner K i-1 K i Kompresjon Rotasjon 56 bit 56 bit 48 bit


DES: Runde-funksjonen: DES: Runde-funksjonen Ekspansjon Permutasjon Substitusjon 32 bit 48 bit 48 bit 32 bit


DES: S-boksene: DES: S-boksene 4 bit 2 bit 0 3 15 4 bit S-boksen


DES: Helheten (Total DESorientering :-): DES: Helheten (Total DESorientering :-) L i-1 R i-1 K i-1 K i L i R i Ekspansjon Permutasjon Substitusjon Kompresjon Rotasjon 32 bit 32 bit 56 bit 32 bit 32 bit 32 bit 48 bit 48 bit 32 bit


DES: Angrep: DES: Angrep Dårlige nøkler (lite antall, ikke noe problem) Rå makt, et problem i dag! 1 milllion dollar, knekk nøkkelen på ca 3.5 timer (i snitt). Differensial kryptoanalyse Biham & Shamir 1990. DES optimalisert før 1975! Lineær kryptoanalyse Anta lineær approksimasjon, virker dersom minst en S-bokse har lineær bias, og det har de. Andre metoder ???


DES forbedringer: DES forbedringer Kjør odde antall DES etter hverandre Med forskjellige nøkler! Bruk andre S-bokser F.eks. Nøkkel-avhengige bokser


IDEA: IDEA Moderne design Seks runder, symmetrisk algoritme, 128 bit nøkkel, 64 bit blokker Optimalisert mot lineær og differensial kryptoanalyse Sikkerhet Har motstått alle kjente angrep, men er forholdsvis ny. Husk: DES ble tatt i bruk på midten av syttitallet, femten år før differensial kryptoanalyse ble kjent!


RSA offentlig nøkkel kryptering: RSA offentlig nøkkel kryptering Oppfunnet av Rivest, Shamir og Adelman i 1976 Asymmetriske nøkler Største nyvinning de siste to tusen år, sånn ca. Ganske langsom Utrolig praktisk for nøkkelutveksling Kryptering av korte «session»-nøkler Diffie-Hellman nøkkelutveksling med samtidig autentisering


RSA algoritmen: RSA algoritmen Basis p og q er primtall. “e” tilfeldig 1

Asymmetriske nøkler i RSA: Asymmetriske nøkler i RSA Offentlig nøkkel: (e,n) Privat nøkkel: (e,n,d) Asymmetri ON dekrypterer meldinger kryptert med PN PN dekrypterer meldinger kryptert med ON Sikkert fordi: «n» er et stort tall, og det er fryktelig vanskelig å faktorisere store tall «stort» er her typisk 512 bit eller mer (mere enn hundre siffer i titalls-systemet)


Kort digresjon om alle disse detaljene:: Kort digresjon om alle disse detaljene: Ikke for at dere skal huske dem :-) For å vise at både DES og RSA ikke er så veldig komplisert Essensen kan vises frem på en side En dyktig programmerer vil kunne lage kode ut fra slike beskrivelser Eksportforbud er derfor bortimot umulig, mer om dette senere.


Noen bruksområder for RSA: Noen bruksområder for RSA Utveksle hemmelig meldinger Signere en melding Regne ut en enveis hash-verdi, og kryptere denne med privat nøkkel Andre kan selv regne ut hash-verdi, og de kan dekryptere signaturen, og se at hash-verdiene stemmer. Dermed er det originale dokumentet autentisk.


PGP: PGP


Historien bak PGP: “Pretty Good Privacy”: Historien bak PGP: “Pretty Good Privacy” Skrevet av Philip Zimmermann Han ønsket at sterk kryptografi skulle være tilgjengelig for andre enn regjerninger. er er vegetarianer, og kjernevåpenmotstander og aktivist i diverse andre saker. PGP er fra hans side hovedsakelig et politisk verktøy Ganske Sikker! Bruker standard algoritmer, og er kritisk gjennomgått av de beste i verden, og kritikken er tatt til følge.


PGP: Hvilke algoritmer bruker den?: PGP: Hvilke algoritmer bruker den? Programvare for å kryptere meldinger i elektronisk post og lagrede filer. Bruker IDEA til å kryptere meldingene Derfor er PGP veldig rask Bruker RSA til å kode IDEA-nøklene. Koder IDEA nøkkelen med mottagerens offentlige nøkkel Nøkkel-distribusjon basert på “Tillitsnett”


Anatomien av en PGP-kodet melding: Anatomien av en PGP-kodet melding Original melding, signert med avsenders private nøkkel, komprimert med LZWH (e.l.) , kryptert med IDEA. IDEA nøkkel, kryptert med mottager nr. 1 sin offentlige RSA-nøkkel IDEA nøkkel, kryptert med mottager nr. n sin offentlige RSA-nøkkel


PGP- “tillitsnett”- for nøkkel-distribusjon: PGP- “tillitsnett”- for nøkkel-distribusjon A har signert B sin offentlige nøkkel: Indikerer at A har sett bevis for at B virkelig er den hun gir seg ut for. Hvis C stoler på A, stoler hun også på at hvis A har signert Bs nøkkel, så er Bs nøkkel autentisk. For å ugyldiggjøre en nøkkel. Signer den offentlige nøkkelen med den private nøkkelen, og si at nøkkelen er ugyldig.


Kryptoanalyse: Kryptoanalyse


Litt mer om praktisk kryptoanalyse: Litt mer om praktisk kryptoanalyse Klartekst-metoder Avlytt rommet meldingene kodes i Stjel logger Jernvare-metoder Saboter utstyr, så det lekker informasjon. Lag eget utstyr for å knekke koder raskt Matematiske metoder Differensial analyse Lineær analyse Dårlige nøkler ... (mye, mye mer) Politiske metoder Forby gode algoritmer Registrer alle nøkler Knekk menneskene Tortur, utpressing, overtalelse


Politikk: Politikk


Politikk, noen scenarier: Politikk, noen scenarier Internasjonal lovgivning Enklere kontakt med offentlige myndigheter Fryktelig vanskelig å avlytte telefonen Muliggjør elektronisk handel Sikre transaksjoner Anonyme transaksjoner


Internasjonal lovgivning: Internasjonal lovgivning USAs lover viktige! Verdens ledende programvare-leverandør Strenge regler for eksport: Inntil 56 bit, ved tvungen nøkkeldeponering NSA: Ubegrenset avlytting av ikke-amerikanere Europeisk lovgivning Frankrike, Portugal har forbud. Strid i Tyskland om streng lovgivning. EU har en «prosess» i lovgivende organer Amerikanerne presser på for “Harmonisering”, “krypto-finlandisering”


Kontakt med det offentlige enklere: Kontakt med det offentlige enklere Elektroniske brev i stedet for papir-korrespondanse Signaturer + sikker transport. Meldinger blir ikke «tapt». Mer transparent forvaltning Maskinlesbare postlister “Glasshus”-administrasjon Vil fremtvinge radikal endring i bedriftskultur


Elektronisk handel mulig: Elektronisk handel mulig Store og små transaksjoner kan gå over nettet Microsoft, Intuit og Checkfree kom nylig med standard, VISA og Mastercard med en annen, alle disse samarbeider. Produkter høsten 97. Småpengekort introduseres snart Personlig fremmøte og fysisk signatur ikke nødvendig Mulig at ECU blir en elektronisk valuta!


Mulig scenario: Skattevesenets sammenbrudd: Mulig scenario: Skattevesenets sammenbrudd En internasjonal økonomi basert på tjenester Skatt på tjenester gir stort incitament for å flytte inntekter utenlands Penger som er ute kan betale for tjenester utenlands og innenlands Plutselig blir pengestrømmene som skatten tapper, flyttet utenfor skattevesenets nasjonale jurisdiksjon. Indirekte beskatning vil derfor måtte øke


Telefonavlytting umulig: Telefonavlytting umulig Telefonkontroll mindre nyttig Alle, både kriminelle og lovlydige, kan samtale uten stor avlyttingsrisiko. PGP-phone finnes i dag. Rimelig sikker. Romavlytting o.l. mer nødvendig Vi vil se allverdens vikarierende argumenter for dette: «Motorsykkelgjenger», «Utenlandske voldsforbrytere» , narkotika, terrorisme etc.


Stri strøm av amerikanske lovforslag: Stri strøm av amerikanske lovforslag Digital Telephony Bill Computer Decency Act “Son of ITAR” Amerikanerne regner kryptografi som våpenteknologi Begrenser den sterkt De krever kontroll og bakdører! Vanskelig å eksportere krypto fra USA


Kryptering mot kriminalitet: Kryptering mot kriminalitet Signaturer kan brukes mot Datavirus Svindel og tukling med dokumenter og data Koding av meldinger og filer Beskyttelse av følsomme persondata Autentisering av sender og mottaker Gjør politiets registre og samband sikrere mot avlytting Kryptografi innebærer at datakriminalitet reduseres, ikke at den øker


Retten til god krypto = retten til å bruke lukket konvolutt: Retten til god krypto = retten til å bruke lukket konvolutt Konvolutten kan inneholde hva som helst du kan signere den og forsegle den slik at mottaker er sikker på at kun du kan ha forseglet den du kan adressere den på en slik måte at kun mottaker kan åpne den og lese innholdet


Anvendelser: Anvendelser Privatliv Bedriftshemmeligheter Autentisering Integritet Tilgjengelighet


Kryptering for Ola Nordmann/Olea Nordkvinne: Kryptering for Ola Nordmann/Olea Nordkvinne Uforfalskbare signaturer Private transaksjoner Sikker konto og kontoinformasjon Tyverisikring Datasikkerhet i nettverk, adgangskontroll


Nøkkeldeponering (“key escrow”): Nøkkeldeponering (“key escrow”) Ett eller flere deponier har kopi av alle nøklene Kan være nyttig Frivillig eller tvungen?


Avlyttbare krypteringsmetoder: Avlyttbare krypteringsmetoder “Utro tjenere” innen det offentlige Privatlivets fred Dårlig kontroll med avlyttingen


Umulig å hindre bruk av krypto: Umulig å hindre bruk av krypto Umulig å “nedfinne” alle kryptoprogrammene og kunnskapen som er i bruk Skjulte kanaler Uklarhet om hva som er en kode


Norsk virkelighet: Norsk virkelighet NSK, er den brukbar til noe? Ukjent algoritme Ingen offentlig debatt Aukrust-utvalgets todelte rapport


Bibliografi: Bibliografi “Applied Cryptography” (2nd ed.) av Bruce Schneier, John Wiley 1986. “PGP: Pretty good Privacy”. Av Simson Garfinkel, O’Reilly &Associates, 1995 “Enigma”. Alan Hodges sin Turing biografi. “Codebreakers”. Hindsley, F. H and Stripp, Alan (redaktører). Oxford Univ. Press 1993 “The Puzzle Palace” av James Bamford, PNGN. 1983


Web-bibliografi: Web-bibliografi www.eff.org (EFF) www.krypto.com (Encryption Policy Resource Page) www.privacy.org/ipc/ (Internet Privacy Coalition) home.sn.no/home/efn/ (EFN) www.cypher.net (Cypherpunks) www.pgp.org (PGP)