Bevist sikkerhet

Leverbar sikkerhet er et begrep i moderne kryptologi . I kryptografihistorien er det mange eksempler på systemer som ble antatt å være sikre av oppfinnerne, men som likevel kunne brytes. Det er derfor ønskelig å overbevise deg selv om sikkerheten til et system ved hjelp av et formelt bevis . For dette må både det kryptografiske systemet og sikkerheten som skal oppnås formaliseres.

Perfekt sikkerhet

Claude Shannon definerte perfekt sikre krypteringsmetoder i 1949 og viste forholdene de eksisterer under. En perfekt sikker krypteringsprosess er preget av det faktum at en krypteringstekst som genereres med den, ikke tillater å trekke noen konklusjoner om den tilsvarende klarteksten. Med en slik metode er det matematisk bevist at en angriper som kjenner krypteringsteksten ikke kan få ytterligere informasjon om den bortsett fra lengden på ren tekst. Han kan ikke dekryptere krypteringsteksten eller til og med bryte hele prosedyren. Shannon var i stand til å bevise at engangsputen er helt trygg.

Asymptotisk sikkerhet

Et informasjonsteoretisk bevis garanterer sikkerhet mot angripere som ikke er begrenset i datakraft. En slik angriper kan imidlertid bare prøve alle mulige nøkler med en metode som AES . Med ekte datamaskiner vil det imidlertid ta for lang tid. For å gjøre begrepet sikkerhet mer realistisk, er angriperen derfor begrenset i sin datakraft, avhengig av nøkkellengden som brukes (eller en sikkerhetsparameter). Deretter vises det at systemet er sikkert mot en slik angriper. Det viser bare at innsatsen for en angriper vokser mye raskere enn innsatsen for brukeren. Ved å velge riktig nøklelengde kan angrep praktisk talt ekskluderes. Nøkkellengden må imidlertid tilpasses den tilgjengelige datakraften, noe som er en av grunnene til at nøkkelengden på 768 bits som tidligere ble brukt for RSA nå anses som usikker. Fordi bare den asymptotiske atferden blir undersøkt her , kalles sikkerheten også asymptotisk eller kompleksitetsteoretisk .

For de fleste kryptografiske metoder kan ikke systemets sikkerhet bevises uten ytterligere forutsetninger. En av de tidligste forutsetningene som er brukt er at factoring-problemet er alvorlig. Beviset for sikkerhet er da en reduksjon mellom å bryte systemet og løse problemet. For eksempel kan det bevises at enhver angriper som kan beregne den hemmelige fra den offentlige nøkkelen til RSA-kryptosystemet, også kan løse faktoriseringsproblemet (mer presist, en effektiv løser kan konstrueres fra en vellykket angriper). Siden det ifølge antagelsen ikke kan være en slik løser, kan det heller ikke være en vellykket angriper. Sikkerhet betyr ikke lenger at det er helt umulig for angriperen å bryte systemet, men at dette er praktisk talt umulig. Sannsynligheten for suksess er med andre ord ubetydelig liten.

Konkret sikkerhet

Med asymptotiske sikkerhetsbevis vises det bare at et system er sikkert over en viss verdi av sikkerhetsparameteren (nøkkellengden). Hvis du vil starte et slikt system, må du velge en bestemt parameter. For dette formålet må beviset være mer presist og det må spesifiseres en smal øvre grense for angriperens sannsynlighet for å lykkes avhengig av ressursene som brukes (kjøretid, antall oracle-henvendelser). Hvis en slik avhengighet kan spesifiseres, snakker man om konkret sikkerhet.

eksempel

Simulatoren S genererer IND-CPA “grensesnittet” for angriperen A fra problemet P.

Den ElGamal kryptering er IND-CPA -safe forutsatt at for å fatte beslutninger Diffie-Hellman problemet er vanskelig. Beviset består av en reduksjon der en løsning for DDH-problemet konstrueres fra enhver vellykket angriper mot sikkerheten til systemet. Fordi DDH ble akseptert som alvorlig, er det klart at en slik angriper ikke kan eksistere.

Det er en angriper A, som ingenting er kjent med, bortsett fra at han vinner IND-CPA-eksperimentet mot ElGamal. Så når den mottar en offentlig nøkkel, utsteder den to meldinger . Hvis du da gir ham kryptering av en av de to under den offentlige nøkkelen, kan han sannsynligvis fortelle hvilken melding som ble kryptert. ${\ displaystyle m_ {0}, m_ {1}}$${\ displaystyle 1/2 + \ epsilon}$

Fra denne angriperen A konstruerer man nå en løser S for DDH som følger. Dette får en beskrivelse av en gruppe med produsent og en trippel som innspill. S simulerer nå nøkkelgenerering og gir A som den offentlige nøkkelen. S kjenner ikke den tilsvarende hemmelige nøkkelen, men A kan ikke vite det. A sender ut to meldinger etter hvert . S må nå simulere krypteringen. Han velger en tilfeldig bit og setter krypteringen . Angriperen A kommer så tilbake litt . I så fall kan ikke krypteringen skilles fra en normalt generert. Hvis det er et tilfeldig gruppeelement, kan angriperen bare gjette og vinne med sannsynlighet 1/2. Strategien til S er derfor som følger: Hvis A var vellykket og returnerer riktig bit, mistenker S det . Hvis A har feil, mistenker S at det var et tilfeldig element. Sannsynligheten for suksess for S er da . ${\ displaystyle g}$${\ displaystyle (g ^ {x}, g ^ {y}, g ^ {z})}$${\ displaystyle g ^ {x}}$${\ displaystyle m_ {0}, m_ {1}}$${\ displaystyle b}$${\ displaystyle g ^ {y}, g ^ {z} m_ {b}}$${\ displaystyle b '}$${\ displaystyle g ^ {z} = g ^ {xy}}$${\ displaystyle g ^ {z}}$${\ displaystyle g ^ {z} = g ^ {xy}}$${\ displaystyle g ^ {z}}$${\ displaystyle 1/2 + \ epsilon / 2}$

diskusjon

Paradokset med påviselig sikkerhet er at et system som er bevist å være sikkert ikke nødvendigvis egentlig er sikkert. Dette er fordi flere forutsetninger og formaliseringer er nødvendige for å bevise et bevis. Systemet, angriperen og sikkerhetsmålet må beskrives formelt (for eksempel IND-CPA- sikkerhet for kryptering), og bevisene er bare en reduksjon av et problem hvis alvorlighetsgrad ble antatt. En angriper som er sterkere enn den som antas i beviset, kan potensielt bryte systemet. Det kan også hende at sikkerhetsmålet ikke er formulert tilstrekkelig, dvs. en mindre suksess er tilstrekkelig for angriperen. Hvis sikkerhetsmålet for eksempel er "Ingen angriper skal kunne utlede ren tekst fra en krypteringstekst", gir bevisene ikke en uttalelse om en angriper som bare vil lære de tre første bokstavene i ren tekst. Et annet problem er at det virkelige kryptosystemet ikke akkurat kartlegger det formelle, fordi det ble gjort feil enten i implementeringen av det formelle eller i formaliseringen av et allerede eksisterende system. En ganske usannsynlig måte å bryte systemet uansett er å løse matteproblemet som ligger til grunn for sikkerhet. Til slutt, selvfølgelig, kan beviset rett og slett være feil. Til tross for disse mange problemene er bevis på sikkerhet et verdifullt verktøy i moderne kryptologi.

Individuelle bevis

1. ^ Claude Shannon: Kommunikasjonsteori om hemmeligholdssystem . I: Bell System Technical Journal . teip 28 , nr. 4 , 1949, s. 656-715 ( netlab.cs.ucla.edu [PDF; 549 kB ]).