Vald chiffertextattack

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 december 2018; verifiering kräver 1 redigering .

Vald - chiffertextattack är en kryptografisk attack där en kryptoanalytiker samlar in information om ett chiffer genom att gissa chiffertexten och dekryptera den med en okänd nyckel. Vanligtvis kan en kryptoanalytiker använda dekrypteringsverktyget en eller flera gånger för att erhålla den dekrypterade chiffertexten. Med hjälp av mottagna data kan han försöka återställa den hemliga nyckeln för dekryptering. Det finns chiffer för vilka den här typen av attacker kan vara framgångsrika. Dessa inkluderar: ElGamal Scheme ; RSA , används i SSL-protokollet ; NTRU . För skydd används RSA-OAEP och Cramer-Showe chiffer .

En chiffertextattack kan vara adaptiv eller icke-adaptiv.

Attack baserad på felaktig chiffertext

I en icke-adaptiv attack använder kryptoanalytikern inte resultaten från tidigare dekrypteringar, det vill säga chiffertexter väljs ut i förväg. Sådana attacker kallas lunchattacker ( lunchtid eller CCA1 ).

Attack baserat på en adaptivt vald chiffertext

Annars väljer kryptoanalytikern adaptivt en chiffertext som beror på resultaten av tidigare dekrypteringar ( CCA2 ).

Attack mot protokoll baserade på RSA PKCS#1-krypteringsstandarden

En kort beskrivning av RSA PKCS#1-standarden

En av representanterna för kryptosystem med publik nyckel ( Public Key Cryptography Standards ), baserad på RSA-algoritmen. Låt k vara bytelängden för RSA-modulen, n. Det finns många varianter av PKCS#1-standarden. I detta exempel betraktas RSAES-PKCS1-v1_5-versionen utan att använda en digital signatur, den andra byten i meddelandeblocket är 00 eller 01. Standarden kan fungera med meddelanden med en maximal längd lika med k-11. Standardblocket PKCS#1, EB, består av k byte. Dess form är EB = 00||02||PS||00||D. De två första byten är konstanta och lika med 00 respektive 02. PS är en utfyllnadssträng, ett genererat pseudoslumptal som består av byte som inte är noll. För att öka säkerhetsnivån rekommenderas det att generera ett nytt PS-block för varje enskild kryptering. Dess längd är lika med k-3-|D|, där D är datablocket, |D| är dess bytelängd. Längden på PS-blocket måste vara minst 8 byte. PS- och D-blocken måste separeras med en nollbyte. För enkelhetens skull kommer vi i framtiden inte att specificera RSAES-PKCS1-v1_5-standarden, vi kommer att beteckna den som PKCS#1. Låt n, e vara den publika nyckeln och p, q, d vara den hemliga nyckeln. Enligt R.S.A. EB-blocket konverteras till ett heltal x och krypteras med RSA-algoritmen, . Mottagaren kontrollerar längden på chiffertexten, dekrypterar den , blockerar den och kontrollerar de första två byten som separerar nollbyten och längden på PS-blocket. Om kontrollen misslyckas skapas ett fel. $n=pq,d=e^{-1}\operatörsnamn {mod} (\phi (n))$ $c=x^{e}\operatörsnamn {mod} (n)$ $c\leqslant n$ $m=c^{d}\operatörsnamn {mod} (n)$

Beskrivning av attacken

Detta exempel illustrerar möjligheten till en framgångsrik attack baserat på en adaptivt vald chiffertext. Låt kryptoanalytikern ha tillgång till en enhet som för valfri vald chiffertext indikerar om motsvarande klartext är i standardformatet PKCS#1 och står inför uppgiften att dekryptera chiffertext C. På så sätt kan analytikern välja olika chiffertexter och skicka dem till enheten. Efter att ha fått svaret komponerar den nästa chiffertext, baserat på resultaten från de föregående. Baserat på svaren som mottagits från enheten och kunskap om det standardkompatibla öppna meddelandeformatet kan kryptoanalytikern beräkna . Den avgörande faktorn i attacken är de två första byten i det öppna meddelandet, som är konstanter. I detta exempel betraktas en algoritm som minimerar antalet chiffertexter som krävs för att ta emot ett öppet meddelande. Attacken kan delas in i tre steg: $m=c^{d}\operatörsnamn {mod} (n)$

Hämta chiffertexten som matchar meddelandet $c_{0}$ $m_{0}$
Att hitta små nummer för vilka chiffertexter i formen uppfyller PKCS-standarden. För varje framgångsrikt hittad , med hjälp av tidigare kunskaper om , beräknar analytikern en serie intervall som bör innehålla . $si}$ $c_{0}\cdot (s_{i})^{e}\operatörsnamn {mod} (n)$ $si}$ $m_{0}$ $m_{0}$
Hitta en serie som bara består av ett intervall. I det här fallet har analytikern tillräckligt med information om , för att välja önskad , för vilken den uppfyller PKCS-standarden. Värdet ökar gradvis tills intervallet reduceras till ett möjligt antal. $m_{0}$ $si}$ $c_{0}\cdot (s_{i})^{e}\operatörsnamn {mod} (n)$ $si}$

Matematisk beskrivning av attacken

Anta att kryptoanalytikerns mål är att ta reda på det . Eftersom k är bytelängden på n, då . Analytikern väljer antalet s, beräknar det och skickar det till enheten. Om enheten tar emot ett meddelande vet vi säkert att de två första byten är 00 och 02. För enkelhetens skull, låt oss beteckna . Antag att s är lämpligt, då är uppskattningen sann . Genom att samla in den här typen av information kan vi hitta m. Som regel kommer chiffertexter att räcka, men det här antalet kan fluktuera kraftigt. Låt oss skriva attacken steg för steg. $m=c^{d}\operatörsnamn {mod} (n)$ ${\displaystyle 2^{8(k-1)}\leqslant n<2^{8k))$ $c'=c\cdot s^{e}\operatörsnamn {mod} (n)$ $c'$ ${\displaystyle B=2^{8(k-2)))$ $2B\leqslant m\cdot s\operatörsnamn {mod} (n)<3B$ $2^{20}$

Hitta ${\displaystyle s_{0))$ . Givet ett heltal c väljer vi olika slumpmässiga heltal , sedan kontrollerar vi med enheten om uttrycket uppfyller PKCS-standarden. För det första numret som lyckades hittas på detta sätt, hittar vi , , . ${\displaystyle s_{0))$ $c\cdot s_{0}^{e}\operatörsnamn {mod} (n)$ ${\displaystyle s_{0))$ $c_{0}=c\cdot (s_{0})^{e}\operatörsnamn {mod} (n)$ $M_{0}={[2B,3B-1]}$ $i=1$
Att hitta rätt meddelanden
1. Sök start. Om i=1, så letar vi efter det minsta positiva talet , för vilket chiffertexten uppfyller PKCS-standarden. $s_{1}\geqslant {\frac {n}{3B))$ $c_{0}\cdot (s_{1})^{e}\operatörsnamn {mod} (n)$
2. Annars, om och antalet intervall är minst 2, så letar vi efter det minsta heltal för vilket chiffertexten uppfyller PKCS-standarden. $i>1$ $M_{{i-1}}$ $s_{i}>s_{i-1}$ $c_{0}\cdot (s_{i})^{e}\operatörsnamn {mod} (n)$
3. Annars, om den innehåller exakt ett intervall (dvs. ), välj sedan heltal som uppfyller uttrycken och , tills chiffertexten uppfyller 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örsnamn {mod} (n)$
Begränsa mängden lösningar . När den väl hittats beräknas en serie intervall för både alla och . $si}$ $Mi}$ $M_{i}=\bigcup _{(a,b,r)}[\operatörsnamn {max} (a,[{\frac {2B+rn}{s_{i}}}]),\operatörsnamn {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}}$
Beräkna en lösning . Om innehåller bara ett intervall av formuläret , ställ in och returnera m som lösningen . Annars går vi till steg 2. $Mi}$ $M_{i}={[a,a]}$ $m=a(s_{0})^{-1}\operatörsnamn {mod} (n)$ $m=c^{d}\operatörsnamn {mod} (n)$ $i=i+1$

Det första steget kan hoppas över om C är ett krypterat meddelande som överensstämmer med PKCS-standarden. I det andra steget börjar matchningen med , eftersom meddelandet för mindre värden inte överensstämmer med PKCS-standarden. Siffran används för att dividera intervallet vid varje iteration med ungefär hälften. $s_{1}$ ${\frac {n}{3B))$ ${\displaystyle m_{0}s_{1))$ $r_{i}\geqslant 2{\frac {bs_{i-1}-2B}{n))$

Attackanalys

Uppskattning av sannolikheten för att ett meddelande överensstämmer med PKCS-standarden

Låt sannolikheten att en slumpmässigt vald chiffertext har ett lämpligt klartextformat vara , och vara sannolikheten att för ett slumpmässigt valt heltal de första 2 byten är 00 och 02. Eftersom , det följer att . RSA-modulen väljs vanligtvis som en multipel av 8. Så, vanligtvis nära . Sannolikheten att ett PS-block innehåller minst 8 byte som inte är noll som slutar med en nollbyte är . Om vi antar att n är minst 512 bitar (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}$

Beräkna intervaller

Mi}

Låt oss bevisa det . Eftersom den överensstämmer med PKCS-standarden, följer det att . Låt oss anta det . Så det finns ett intervall med . Eftersom den överensstämmer med PKCS-standarden finns det ett sådant r som därför, , , det vill säga finns i ett av intervallen. ${\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}$

Uppskattning av komplexiteten i en attack

Meddelandet i steg 1 väljs slumpmässigt, vilket innebär att du måste skicka till enheten nära meddelandena för att hitta . På samma sätt för steg 2.1 och 2.2 för . Låt vara antalet intervaller i . Sedan för . Längden på intervallet begränsas uppifrån av värdet . Genom att veta att PKCS-formatet får vi intervaller av formuläret . kommer att innehålla ungefär intervaller. Om , så ingår vart och ett av intervallen, eller en del av det, i om det överlappar med ett av intervallen . Inget av intervallen kan överlappa med två intervall . Om intervallen är slumpmässigt fördelade, så kommer sannolikheten att man skär sig att begränsas ovan av . Således erhålls ekvationen för under antagandet att ett intervall måste innehålla värdet . I vårt fall förväntar vi oss att få med om och ha . Därför kommer det att ta ett enda värde med hög sannolikhet. Därför förväntas steg 2.2 inträffa endast en gång. Låt oss analysera steg 2.3. Det finns därför . Intervalllängd . Därför är det möjligt att hitta ett par som uppfyller olikheterna i steg 2.3 för vart tredje värde på . Sannolikheten för att , är ungefär . Därför kan vi hitta , som uppfyller standarden ungefär med hjälp av chiffertexter. Eftersom resten av intervallet halveras i varje steg 2.3, förväntar vi oss att använda nära chiffertexter. För och kommer att behöva ca chiffertexter för en lyckad attack. Alla sannolikheter som anges ovan hittades under antagandet att alla är oberoende. Låt och uppfylla PKCS-standarden och ha samma PS-blocklängd. Sedan för något heltal får vi och . Då är det mycket troligt att de uppfyller PKCS-standarden, eftersom de också ofta uppfyller standarden. Vanligtvis väljs n som en multipel av 8, eftersom sannolikheten är liten för det. En modul med en bitlängd lika med , är bekvämt för analytikern, eftersom det i det här fallet behövs cirka chiffertexter för en framgångsrik attack. ${\frac {1}{\Pr(P\cap A)))$ ${\displaystyle s_{0))$ $i\geqslant 1$ $w_{i}$ $Mi}$ ${\displaystyle w_{i}\leqslant 1+2^{i-1}s_{i}({\frac {B}{n)))^{i))$ $i\geqslant 1$ $Mi}$ ${\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$ $Mi}$ $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))$ $si}$ ${\frac {2}{\Pr(P|A)))$ $Mi}$ $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}$ $si}$ $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}$

Tillgång till dekryptatorn

Tänk på tre situationer där en analytiker kan få tillgång till en enhet.

Vanlig kryptering . Alice genererar ett meddelande, krypterar det med standarden PKCS#1 utan att tillämpa integritetskontroller och skickar det till Bob. Bob dekrypterar det och om formatet på det dekrypterade meddelandet inte uppfyller standarden, slänger han ett fel, annars agerar han enligt protokollet. Därmed kan analytikern agera som Alice och kontrollera meddelandena för överensstämmelse med standarden. Observera att analytikerns attack fungerar även om autentisering används i nästa steg, eftersom analytikern får den information som krävs innan användaren behöver autentiseras.
Detaljerade felmeddelanden . Integritetskontroll är en viktig del av RSA-kryptering. Ett sätt att göra detta är att signera meddelandet med den privata nyckeln innan avsändaren krypterar det med den offentliga nyckeln. Då kommer angriparen inte att kunna skapa rätt meddelande av misstag. Attacken kan dock bli framgångsrik. I händelse av en misslyckad validering skickar mottagaren ett meddelande som anger var valideringen misslyckades. I synnerhet äventyrar det säkerheten genom att returnera olika felmeddelanden för ett meddelande som inte överensstämmer med standarden och för ett meddelande som har ett signaturverifieringsfel.
Tidsattack . Vissa meddelandegenereringsalternativ inkluderar både kryptering och signatur. Tänk på sekvensen av åtgärder.
1. Meddelandet är dekrypterat.
2. Om den inte uppfyller standarden skickas ett felmeddelande.
3. Annars är signaturen verifierad.
4. Om signaturen är felaktig, så kastas ett fel, annars åtkomst.

Genom att mäta mottagarens svarstid är det således möjligt att avgöra om ett formatfel föreligger eller inte.

Litteratur

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

Länkar

RSA Data Security Inc. PKCS #1: RSA Encryption Standard. — Redwood City, CA, nov. 1993. Version 1.5 - ftp://ftp.rsa.com/pub/pkcs/ascii/pkcs-1.asc
Bleichenbacher's Attack // Authenticated Key Exchange (i TLS), Kenny Paterson, 2015, s. 32-41