Valgt chiffertekstangreb

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. december 2018; verifikation kræver 1 redigering .

Valgt - chiffertekstangreb er et kryptografisk angreb , hvor en kryptoanalytiker indsamler information om en chiffer ved at gætte chifferteksten og dekryptere den med en ukendt nøgle. Typisk kan en kryptoanalytiker bruge dekryptering en eller flere gange for at få den dekrypterede chiffertekst. Ved hjælp af de modtagne data kan han forsøge at gendanne den hemmelige nøgle til dekryptering. Der er cifre, for hvilke denne type angreb kan lykkes. Disse omfatter: ElGamal Scheme ; RSA , brugt i SSL-protokollen ; NTRU . Til beskyttelse anvendes RSA-OAEP- og Cramer-Showe- cifre .

Et chiffertekstangreb kan være adaptivt eller ikke-adaptivt.

Angreb baseret på utilpasset chiffertekst

I et ikke-adaptivt angreb bruger kryptanalytikeren ikke resultaterne af tidligere dekrypteringer, det vil sige, at chiffertekster er valgt på forhånd. Sådanne angreb kaldes frokostangreb ( frokosttid eller CCA1 ).

Angreb baseret på en adaptivt valgt chiffertekst

Ellers vælger kryptoanalytikeren adaptivt en chiffertekst, der afhænger af resultaterne af tidligere dekrypteringer ( CCA2 ).

Angreb på protokoller baseret på RSA PKCS#1-krypteringsstandarden

En kort beskrivelse af RSA PKCS#1-standarden

En af repræsentanterne for offentlige nøglekryptosystemer ( Public Key Cryptography Standards ), baseret på RSA-algoritmen. Lad k være byte-længden af RSA-modulet, n. Der er mange variationer af PKCS#1-standarden. I dette eksempel betragtes RSAES-PKCS1-v1_5-versionen uden brug af en digital signatur, den anden byte i meddelelsesblokken er 00 eller 01. Standarden kan fungere med meddelelser med en maksimal længde svarende til k-11. PKCS#1 standardblokken, EB, består af k bytes. Dens form er EB = 00||02||PS||00||D. De første to bytes er konstante og lig med henholdsvis 00 og 02. PS er en polstringsstreng, et genereret pseudo-tilfældigt tal, der består af ikke-nul bytes. For at øge sikkerhedsniveauet anbefales det at generere en ny PS-blok for hver enkelt kryptering. Dens længde er henholdsvis lig k-3-|D|, hvor D er datablokken, |D| er dens byte længde. Længden af PS-blokken skal være mindst 8 bytes. PS- og D-blokkene skal adskilles af en nulbyte. For nemheds skyld vil vi i fremtiden ikke specificere RSAES-PKCS1-v1_5-standarden, vi vil udpege den som PKCS#1. Lad n, e være den offentlige nøgle og p, q, d være den hemmelige nøgle. Ifølge R.S.A. EB-blokken konverteres til et heltal x og krypteres med RSA-algoritmen, . Modtageren kontrollerer længden af chifferteksten, dekrypterer den , blokerer den og kontrollerer for de korrekte første to bytes, der adskiller null-byten og længden af PS-blokken. Hvis kontrollen mislykkes, opstår der en fejl. $n=pq,d=e^{-1}\operatørnavn {mod} (\phi (n))$ $c=x^{e}\operatørnavn {mod} (n)$ $c\leqslant n$ $m=c^{d}\operatørnavn {mod} (n)$

Beskrivelse af angrebet

Dette eksempel illustrerer muligheden for et vellykket angreb baseret på en adaptivt valgt chiffertekst. Lad kryptanalytikeren få adgang til en enhed, der for enhver valgt krypteringstekst angiver, om den tilsvarende almindelig tekst er i PKCS#1 standardformatet, og står over for opgaven med at dekryptere krypteringstekst C. På denne måde kan analytikeren vælge forskellige krypteringstekster og send dem til enheden. Efter at have modtaget svaret, komponerer den den næste chiffertekst baseret på resultaterne af de foregående. Baseret på de modtagne svar fra enheden og kendskab til det standard-kompatible åbne meddelelsesformat, kan kryptanalytikeren således beregne . Den afgørende faktor i angrebet er de første to bytes af den åbne besked, som er konstanter. I dette eksempel betragtes en algoritme, der minimerer antallet af chiffertekster, der kræves for at modtage en åben besked. Angrebet kan opdeles i 3 faser: $m=c^{d}\operatørnavn {mod} (n)$

Henter den chiffertekst , der matcher beskeden $c_{0}$ $m_{0}$
Finde små tal, for hvilke chiffertekster af formen opfylder PKCS-standarden. For hver succesfuld fundet , ved hjælp af tidligere viden om , beregner analytikeren en række intervaller, der skal indeholde . $s_{i}$ $c_{0}\cdot (s_{i})^{e}\operatørnavn {mod} (n)$ $s_{i}$ $m_{0}$ $m_{0}$
At finde en serie, der kun består af ét interval. I dette tilfælde har analytikeren nok information om , til at vælge den ønskede , som den opfylder PKCS-standarden for. Værdien øges gradvist, indtil intervallet reduceres til et muligt tal. $m_{0}$ $s_{i}$ $c_{0}\cdot (s_{i})^{e}\operatørnavn {mod} (n)$ $s_{i}$

Matematisk beskrivelse af angrebet

Antag, at kryptoanalytikerens mål er at finde ud af det . Da k er bytelængden af n, så . Analytikeren vælger tallet s, beregner det og sender det til enheden. Hvis enheden modtager en besked, ved vi med sikkerhed, at de første to bytes er 00 og 02. Lad os for nemheds skyld angive . Antag, at s er passende, så er estimatet sandt . Ved at indsamle denne type information kan vi finde m. Som regel vil chiffertekster være nok, men dette tal kan svinge meget. Lad os skrive angrebet trin for trin. $m=c^{d}\operatørnavn {mod} (n)$ ${\displaystyle 2^{8(k-1)}\leqslant n<2^{8k))$ $c'=c\cdot s^{e}\operatørnavn {mod} (n)$ $c'$ ${\displaystyle B=2^{8(k-2)))$ $2B\leqslant m\cdot s\operatørnavn {mod} (n)<3B$ $2^{20}$

Finde $s_{0}$ . Givet et heltal c, vælger vi forskellige tilfældige heltal , så kontrollerer vi med enheden, om udtrykket opfylder PKCS-standarden. For det første tal, der er fundet på denne måde, finder vi , , . $s_{0}$ $c\cdot s_{0}^{e}\operatørnavn {mod} (n)$ $s_{0}$ $c_{0}=c\cdot (s_{0})^{e}\operatørnavn {mod} (n)$ $M_{0}={[2B,3B-1]}$ $i=1$
At finde de rigtige beskeder
1. Søgning starter. Hvis i=1, så leder vi efter det mindste positive tal , for hvilket chifferteksten opfylder PKCS-standarden. $s_{1}\geqslant {\frac {n}{3B))$ $c_{0}\cdot (s_{1})^{e}\operatørnavn {mod} (n)$
2. Ellers, hvis og antallet af intervaller er mindst 2, så leder vi efter det mindste heltal , for hvilket chifferteksten opfylder PKCS-standarden. $i>1$ $M_{{i-1}}$ $s_{i}>s_{i-1}$ $c_{0}\cdot (s_{i})^{e}\operatørnavn {mod} (n)$
3. Ellers, hvis det indeholder præcis ét interval (dvs. ), så vælg heltal , der opfylder udtrykkene og indtil chifferteksten opfylder PKCS-standarden. $M_{{i-1}}$ $M_{i-1}={[a,b]}$ ${\displaystyle s_{i}r_{i))$ $r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n))$ ${\frac {2B+r_{i}n}{b}}\leqslant s_{i}\leqslant {\frac {3B+r_{i}n}{a}}$ $c_{0}\cdot (s_{i})^{e}\operatørnavn {mod} (n)$
Indsnævring af sæt af løsninger . Når først fundet, beregnes en række intervaller for både alle og . $s_{i}$ $M_{i}$ $M_{i}=\bigcup _{(a,b,r)}[\operatørnavn {max} (a,[{\frac {2B+rn}{s_{i}}}]),\operatørnavn {min} (b,[{\frac {3B-1+rn}{s_{i))}])]$ $[a,b]\in M_{i-1}$ ${\frac {as_{i}-3B+1}{n}}\leqslant r\leqslant {\frac {bs_{i}-2B}{n}}$
Beregning af en løsning . Hvis kun indeholder ét interval af formen , så sæt og returner m som løsningen . Ellers går vi til trin 2. $M_{i}$ $M_{i}={[a,a]}$ $m=a(s_{0})^{-1}\operatørnavn {mod} (n)$ $m=c^{d}\operatørnavn {mod} (n)$ $i=i+1$

Det første trin kan springes over, hvis C er en krypteret meddelelse, der er i overensstemmelse med PKCS-standarden. I det andet trin starter kampen med , da beskeden for mindre værdier ikke vil være i overensstemmelse med PKCS-standarden. Tallet bruges til at dividere intervallet ved hver iteration med cirka halvdelen. $s_{1}$ ${\frac {n}{3B))$ ${\displaystyle m_{0}s_{1))$ $r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n))$

Angrebsanalyse

Estimering af sandsynligheden for, at en meddelelse er i overensstemmelse med PKCS-standarden

Lad sandsynligheden for, at en tilfældigt valgt chiffertekst har et passende almindeligt tekstformat være , og vær sandsynligheden for, at for ethvert tilfældigt valgt heltal er de første 2 bytes 00 og 02. Siden , følger det, at . RSA-modulet er normalt valgt som et multiplum af 8. Så normalt tæt på . Sandsynligheden for, at en PS-blok indeholder mindst 8 ikke-nul-bytes, der slutter med en nul-byte, er . Hvis vi antager, at n er mindst 512 bit (k > 64), har vi . Så . $\Pr(P\cap A)$ $\Pr(A)={\frac {B}{n))$ $2^{8}B<n<2^{16}B$ ${\displaystyle 2^{-16}<\Pr(A)<2^{-8))$ $\Pr(A)$ $2^{-16}$ $\Pr(P|A)=({\frac {255}{256)))^{8}\cdot (1-({\frac {255}{256)))^{k-10} )$ $0,18<\Pr(P|A)<0,97$ $0.18\cdot 2^{-16}<\Pr(P\cap A)<0.97\cdot 2^{-8}$

Estimering af intervaller

M_{i}

Lad os bevise det . Da den overholder PKCS-standarden, følger det, at . Lad os antage det . Så der er et interval med . Da den overholder PKCS-standarden, er der en sådan r , som derfor, , , altså er indeholdt i et af intervallerne. ${\displaystyle m_{0}\in M_{i))$ $m_{0}$ $2B\leqslant m_{0}\leqslant 3B-1$ $m_{0}\in M_{0}$ $m_{0}\in M_{i-1}$ $[a,b]\in M_{i-1}$ $a\leqslant m_{0}\leqslant b$ $m_{0}s_{i}$ $2B\leqslant m_{0}s_{i}-rn\leqslant 3B-1$ $as_{i}-(3B-1)\leqslant rn\leqslant bs_{i}-2B$ ${\frac {2B+rn}{s_{i}}}\leqslant m_{0}\leqslant {\frac {3B-1+rn}{s_{i}}}$ $m_{0}$

Estimering af kompleksiteten af et angreb

Meddelelsen i trin 1 er valgt tilfældigt, hvilket betyder, at du skal sende til enheden i nærheden af beskederne for at finde . Tilsvarende for trin 2.1 og 2.2 for . Lad være antallet af intervaller i . Så for . Længden af intervallet er afgrænset ovenfra af værdien . Ved at vide, at PKCS-formatet, får vi intervaller af formen . vil indeholde ca intervaller. Hvis , så er hvert af intervallerne, eller en del af det, inkluderet i, hvis det overlapper med et af intervallerne . Ingen af intervallerne kan overlappe med to intervaller . Hvis intervallerne er tilfældigt fordelt, så vil sandsynligheden for, at man skærer med , være afgrænset ovenfor af . Således opnås ligningen for under den antagelse, at et interval skal indeholde værdien . I vores tilfælde forventer vi at komme med om og have . Derfor vil det tage en enkelt værdi med stor sandsynlighed. Derfor forventes trin 2.2 kun at forekomme én gang. Lad os analysere trin 2.3. Der er derfor . Interval længde . Derfor er det muligt at finde et par , der opfylder ulighederne i trin 2.3 for hver tredje værdi af . Sandsynligheden for, at , er ca. Derfor kan vi finde , som tilfredsstiller standarden cirka ved hjælp af chiffertekster. Da resten af intervallet i halveres i hvert trin 2.3, forventer vi at finde ved hjælp af næsten chiffertekster. For og vil have brug for om chiffertekster for et vellykket angreb. Alle de ovenfor angivne sandsynligheder blev fundet under den antagelse, at alle er uafhængige. Lad og opfylde PKCS-standarden og have samme PS-bloklængde. Så for et eller andet heltal får vi og . Så opfylder de højst sandsynligt PKCS-standarden, da de også ofte opfylder standarden. Normalt vælges n som et multiplum af 8, da sandsynligheden er lille for det. Et modul med en bitlængde lig med , er praktisk for analytikeren, da der i dette tilfælde kræves ca. chiffertekster for et vellykket angreb. ${\frac {1}{\Pr(P\cap A)))$ $s_{0}$ $i\geqslant 1$ $w_{i}$ $M_{i}$ ${\displaystyle w_{i}\leqslant 1+2^{i-1}s_{i}({\frac {B}{n)))^{i))$ $i\geqslant 1$ $M_{i}$ ${\displaystyle {\frac {B}{s_{i))))$ $m_{0}s_{i}$ ${\frac {Bs_{i}}{n}}$ $I_{r}=[[{\frac {2B+rn}{s_{i}}}],[{\frac {3B-1+rn}{s_{i}}}]]$ $M_{1}$ ${\frac {Bs_{i}}{n}}$ $i>1$ $I_r$ $M_{i}$ $I_r$ $M_{{i-1}}$ $I_r$ $M_{{i-1}}$ $I_r$ $M_{{i-1}}$ $({\frac {1}{s_{i}}}+{\frac {1}{s_{i-1}}})w_{i-1}$ $w_{i}$ $m_{0}$ $s_{2}$ ${\frac {2}{\Pr(P\cap A)))$ $2{\frac {({\frac {B}{n)))^{2}}{\Pr(P\cap A)))={\frac {2B}{n\Pr(P| A)))<{\frac {2B}{0.18n}}<{\frac {1}{20}}$ ${\displaystyle w_{2))$ $M_{i-1}={[a,b]}$ $a\leqslant m_{0}\leqslant b$ ${\frac {2B+r_{i}n}{b}}\leqslant {\frac {2B+r_{i}n}{m_{0))}\leqslant s_{i}\leqslant {\ frac {3B-1+r_{i}n}{m_{0}}}\leqslant {\frac {3B-1+r_{i}n}{a}}$ ${\frac {3B-1+r_{i}n}{a}}-{\frac {2B+r_{i}n}{b}}\geqslant {\frac {3B-1+r_{ i}n}{m_{0))}-{\frac {2B+r_{i}n}{m_{0))}\geqslant {\frac {B-1}{m_{0))}\geqslant {\frac {B-1}{3B}}$ ${\displaystyle r_{i}s_{i))$ $r_{i}$ $s_{i}\in [{\frac {2B+r_{i}n}{m_{0}}},{\frac {3B-1+r_{i}n}{m_{0}} }]$ ${\frac {1}{2))$ $s_{i}$ ${\frac {2}{\Pr(P|A)))$ $M_{i}$ $m_{0}$ ${\frac {3}{\Pr(P\cap A)))+{\frac {16k}{\Pr(P|A)))$ $\Pr(P\cap A)=0,18\cdot 2^{-16}$ $k=128$ $2^{20}$ $s_{i}$ $m_{0}$ $m_{0}s_{i}$ $j$ $m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS+D$ $s_{i}m_{0}=2\cdot 2^{8(k-2)}+2^{8j}PS'+D'$ ${\displaystyle (2s_{i}-1)m_{0))$ $(2s_{i}-1)m_{0}=2\cdot 2^{8(k-2)}+2^{8j}(2PS'-PS)+2D'-D$ $\Pr(P\cap A)$ $8k-7$ $2^{13}$

Adgang til dekryptering

Overvej 3 situationer, hvor en analytiker kan få adgang til en enhed.

Almindelig kryptering . Alice genererer en besked, krypterer den ved hjælp af PKCS#1-standarden uden at anvende integritetstjek og sender den til Bob. Bob dekrypterer det, og hvis formatet af den dekrypterede besked ikke opfylder standarden, så kaster han en fejl, ellers handler han i henhold til protokollen. Således kan analytikeren fungere som Alice og kontrollere meddelelserne for overholdelse af standarden. Bemærk, at analytikerens angreb virker, selvom der bruges autentificering i næste trin, da analytikeren får de nødvendige oplysninger, før brugeren skal godkendes.
Detaljerede fejlmeddelelser . Integritetskontrol er en vigtig del af RSA-kryptering. En måde at gøre dette på er at signere beskeden med den private nøgle, før afsenderen krypterer den med den offentlige nøgle. Så vil angriberen ikke være i stand til at oprette den korrekte besked ved et uheld. Dog kan angrebet lykkes. I tilfælde af en mislykket validering sender modtageren en besked, der angiver, hvor valideringen mislykkedes. Det kompromitterer især sikkerheden ved at returnere forskellige fejlmeddelelser for en meddelelse, der ikke er i overensstemmelse med standarden, og for en meddelelse, der har en signaturbekræftelsesfejl.
Tidsangreb . Nogle muligheder for meddelelsesgenerering inkluderer både kryptering og signatur. Overvej rækkefølgen af handlinger.
1. Beskeden er dekrypteret.
2. Hvis det ikke opfylder standarden, sendes en fejlmeddelelse.
3. Ellers er signaturen verificeret.
4. Hvis signaturen er forkert, bliver der smidt en fejl, ellers adgang.

Ved at måle modtagerens responstid er det således muligt at afgøre, om der er en formatfejl eller ej.

Litteratur

Bleichenbacher D. Valgte chiffertekstangreb mod protokoller baseret på RSA-krypteringsstandarden PKCS #1 // Advances in Cryptology — CRYPTO '98 :18th Annual International Cryptology Conference Santa Barbara, Californien, USA 23.–27. august 1998 Proceedings / H. Krawczyk - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 1998. - S. 1-12. — 524 s. - ( Lecture Notes in Computer Science ; Vol. 1462) - ISBN 978-3-540-64892-5 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/BFB0055716