Utfyllnad (kryptografi)
I kryptografi är utfyllnad någon av ett antal distinkta metoder som alla inkluderar att lägga till data i början , mitten eller slutet av ett meddelande före kryptering. I klassisk kryptografi kan utfyllnad innefatta att lägga till nonsensfraser i ett meddelande för att dölja det faktum att många meddelanden slutar på förutsägbara sätt, t.ex.
Klassisk kryptografi
Officiella meddelanden börjar och slutar ofta på förutsägbara sätt: Min kära ambassadör, Väderrapport, Med vänlig hälsning, etc. Den primära användningen av utfyllnad med klassiska chiffer är att förhindra kryptoanalytikern från att använda den förutsägbarheten för att hitta känd klartext som hjälper till att bryta krypteringen. Utfyllnad med slumpmässig längd hindrar också en angripare från att veta den exakta längden på klartextmeddelandet.
Ett berömt exempel på klassisk utfyllnad som orsakade ett stort missförstånd är incidenten " världens underverk ", som nästan orsakade en allierad förlust i slaget vid andra världskriget utanför Samar , en del av det större slaget vid Leyte-bukten . I det exemplet amiral Chester Nimitz , överbefälhavaren , USA:s Stillahavsflotta under andra världskriget, följande meddelande till amiral Bull Halsey , befälhavare för Task Force Thirty Four (den allierade huvudflottan) i slaget vid Leyte-bukten, den 25 oktober 1944:
Var är, upprepa, var är Task Force Thirty Four?
Med utfyllnad (fetstilt) och metadata tillagd blev meddelandet:
TURKIET TRAV TILL VATTEN GG FRÅN CINCPAC ACTION COM TREDJE FLOTTA INFO COMINCH CTF SJUTTIOSJU X VAR ÄR RPT VAR ÄR TASK FORCE TREDJEFYRA RR VÄRLDEN UNDERAR
Halseys radiooperatör misstog en del av utfyllnaden för meddelandet, så amiral Halsey slutade med att läsa följande meddelande:
Var är, upprepa, var är Task Force Thirty Four? Världen undrar
Amiral Halsey tolkade utfyllnadsfrasen "världens underverk" som en sarkastisk tillrättavisning, vilket fick honom att få ett känslomässigt utbrott och sedan låsa in sig i sin bro och sura i en timme innan han flyttade sina styrkor för att hjälpa till i slaget utanför Samar. Halseys radiooperatör ska ha blivit tipsad av bokstäverna RR om att "världen undrar" var utfyllnad; alla andra radiooperatörer som tagit emot amiral Nimitz meddelande korrekt tog bort båda utfyllnadsfraserna.
Många klassiska chiffer ordnar klartexten i särskilda mönster (t.ex. kvadrater, rektanglar, etc.) och om klartexten inte passar exakt är det ofta nödvändigt att ange ytterligare bokstäver för att fylla i mönstret. Att använda nonsensbokstäver för detta ändamål har en sidofördel att göra vissa typer av kryptoanalys svårare.
Symmetrisk kryptografi
Hash-funktioner
De flesta moderna kryptografiska hashfunktioner behandlar meddelanden i block med fast längd; alla utom de tidigaste hashfunktionerna inkluderar något slags utfyllnadsschema. Det är avgörande för kryptografiska hashfunktioner att använda avslutningsscheman som förhindrar en hash från att vara sårbar för attacker med längdförlängning .
Många utfyllnadsscheman är baserade på att lägga till förutsägbara data till det sista blocket. Till exempel kan blocket härledas från meddelandets totala längd. Denna typ av utfyllnadsschema används vanligtvis för hashalgoritmer som använder Merkle–Damgård-konstruktionen som MD-5 , SHA-1 och SHA-2-familjen som SHA-224, SHA-256, SHA-384, SHA-512 , SHA512/224 och SHA-512/256
Blockera chiffer funktion
Chiffer-block chaining- läge (CBC) är ett exempel på blockchiffer-funktionsläge . Vissa blockchifferlägen (i huvudsak CBC och PCBC) för krypteringsalgoritmer med symmetriska nyckel kräver vanlig textinmatning som är en multipel av blockstorleken, så meddelanden kan behöva utfyllas för att få dem till denna längd.
Det finns för närvarande [ när? ] ett skifte till att använda strömningsläge i stället för blockdrift. [ citat behövs ] Ett exempel på strömningslägeskryptering är räknarens funktionsläge . Strömmande driftlägen kan kryptera och dekryptera meddelanden av alla storlekar och kräver därför ingen utfyllnad. Mer komplicerade sätt att avsluta ett meddelande, som t.ex. chiffertextstjälning eller återstående blockavslutning, undviker behovet av utfyllnad.
En nackdel med utfyllnad är att den gör den vanliga texten i meddelandet mottaglig för utfyllnad av orakelattacker . Utfyllnad av orakelattacker gör att angriparen kan få kunskap om ren text utan att attackera själva blockchifferets primitiva. Utfyllnad av orakelattacker kan undvikas genom att se till att en angripare inte kan få kunskap om borttagningen av utfyllnadsbyte. Detta kan åstadkommas genom att verifiera en meddelandeautentiseringskod (MAC) eller digital signatur innan utfyllnadsbyte tas bort, eller genom att växla till ett strömningsläge.
Bitstoppning
Bitstoppning kan appliceras på meddelanden av alla storlekar.
En enkel uppsättning ('1') bit läggs till meddelandet och sedan läggs så många återställningsbitar ('0') som krävs (möjligen ingen) till. Antalet återställda ('0') bitar som läggs till kommer att bero på blockgränsen till vilken meddelandet behöver utökas. I bittermer är detta "1000 ... 0000".
Denna metod kan användas för att fylla ut meddelanden som är hur många bitar som helst, inte nödvändigtvis ett helt antal byte långa. Till exempel, ett meddelande på 23 bitar som är utfyllt med 9 bitar för att fylla ett 32-bitars block:
... | 1011 1001 1101 0100 0010 011 1 0000 0000 |
Denna utfyllnad är det första steget i ett tvåstegs utfyllnadsschema som används i många hashfunktioner inklusive MD5 och SHA . I detta sammanhang specificeras det av RFC1321 steg 3.1.
Detta utfyllnadsschema definieras av ISO/IEC 9797-1 som utfyllnadsmetod 2.
Byte utfyllnad
Byte-utfyllnad kan tillämpas på meddelanden som kan kodas som ett helt antal byte .
ANSI X9.23
I ANSI X9.23 läggs alltid mellan 1 och 8 byte till som utfyllnad. Blocket är utfyllt med slumpmässiga bytes (även om många implementeringar använder 00) och den sista byten i blocket ställs in på antalet adderade byte.
Exempel: I följande exempel är blockstorleken 8 byte, och utfyllnad krävs för 4 byte (i hexadecimalt format)
... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 04 |
ISO 10126
ISO 10126 (återkallad, 2007) specificerar att utfyllningen ska göras i slutet av det sista blocket med slumpmässiga byte, och utfyllnadsgränsen ska specificeras av den sista byten.
Exempel: I följande exempel är blockstorleken 8 byte och utfyllnad krävs för 4 byte
... | DD DD DD DD DD DD DD DD | DD DD DD DD 81 A6 23 04 |
PKCS#5 och PKCS#7
Utfyllnad är i hela bytes. Värdet för varje adderad byte är antalet byte som läggs till, dvs N byte, var och en av värdet N läggs till. Antalet byte som läggs till beror på blockgränsen till vilken meddelandet behöver utökas.
Vadderingen kommer att vara en av:
01 02 02 03 03 03 04 04 04 04 05 05 05 05 05 06 06 06 06 06 06 osv.
Denna utfyllnadsmetod (liksom de två föregående) är väldefinierad om och endast om N är mindre än 256.
Exempel: I följande exempel är blockstorleken 8 byte och utfyllnad krävs för 4 byte
... | DD DD DD DD DD DD DD DD | DD DD DD DD 04 04 04 04 |
Om längden på originaldata är en heltalsmultipel av blockstorleken B , så läggs ett extra block av byte med värdet B till. Detta är nödvändigt så att dechiffreringsalgoritmen med säkerhet kan avgöra om den sista byten i det sista blocket är en padbyte som indikerar antalet utfyllnadsbyte som lagts till eller en del av klartextmeddelandet. Betrakta ett meddelande i klartext som är en heltalsmultipel av B byte där den sista byten av klartext är 01 . Utan ytterligare information kommer dechiffreringsalgoritmen inte att kunna avgöra om den sista byten är en klartextbyte eller en padbyte. Genom att lägga till B byte var och en av värdet B efter 01 klartextbyten, kan dechiffreringsalgoritmen alltid behandla den sista byten som en padbyte och ta bort det lämpliga antalet padbyte från slutet av chiffertexten; nämnda antal byte som ska strippas baserat på värdet av den sista byten.
PKCS#5-utfyllnad är identisk med PKCS#7-utfyllnad, förutom att den bara har definierats för blockchiffer som använder en 64-bitars (8-byte) blockstorlek. I praktiken kan de två användas omväxlande.
Den maximala blockstorleken är 255, eftersom det är det största antalet en byte kan innehålla
ISO/IEC 7816-4
ISO/IEC 7816 -4:2005 är identisk med bitutfyllnadsschemat, tillämpat på en vanlig text med N byte. Detta betyder i praktiken att den första byten är en obligatorisk byte värd '80' (hexadecimal) följt, om det behövs, av 0 till N − 1 byte satt till '00', tills slutet av blocket nås. ISO/IEC 7816-4 i sig är en kommunikationsstandard för smartkort som innehåller ett filsystem och innehåller i sig inga kryptografiska specifikationer.
Exempel: I följande exempel är blockstorleken 8 byte och utfyllnad krävs för 4 byte
... | DD DD DD DD DD DD DD DD | DD DD DD DD 80 00 00 00 |
Nästa exempel visar en utfyllnad på bara en byte
... | DD DD DD DD DD DD DD DD | DD DD DD DD DD DD DD 80 |
Noll stoppning
Alla bytes som krävs för att vara utfyllda är utfyllda med noll. Nollutfyllnadsschemat har inte standardiserats för kryptering, [ citat behövs ] även om det specificeras för hash och MAC som utfyllnadsmetod 1 i ISO/IEC 10118-1 och ISO/IEC 9797-1 .
Exempel: I följande exempel är blockstorleken 8 byte och utfyllnad krävs för 4 byte
... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 00 |
Nollutfyllnad kanske inte är reversibel om originalfilen slutar med en eller flera nollbyte, vilket gör det omöjligt att skilja mellan klartextdatabyte och utfyllnadsbyte. Det kan användas när längden på meddelandet kan härledas utanför bandet . Det tillämpas ofta på binärt kodade [ förtydligande behövs ] -strängar ( nullterminerad sträng ) eftersom nolltecknet vanligtvis kan tas bort som blanksteg .
Nollutfyllnad kallas ibland också för "nollutfyllnad" eller "nollbyteutfyllnad". Vissa implementeringar kan lägga till ytterligare ett block med noll byte om klartexten redan är delbar med blockstorleken. [ citat behövs ]
Offentlig nyckelkryptering
I kryptografi med offentlig nyckel är utfyllnad processen att förbereda ett meddelande för kryptering eller signering med hjälp av en specifikation eller ett schema som PKCS#1 v2.2, OAEP , PSS , PSSR, IEEE P1363 EMSA2 och EMSA5. En modern form av utfyllnad för asymmetriska primitiver är OAEP som tillämpas på RSA-algoritmen , när den används för att kryptera ett begränsat antal byte.
Operationen hänvisas till som "utfyllnad" eftersom slumpmässigt material från början helt enkelt lades till meddelandet för att göra det tillräckligt långt för det primitiva. Denna form av stoppning är inte säker och används därför inte längre. Ett modernt utfyllnadsschema syftar till att säkerställa att angriparen inte kan manipulera klartexten för att utnyttja den matematiska strukturen hos det primitiva och kommer vanligtvis att åtföljas av ett bevis, ofta i den slumpmässiga orakelmodellen , att det är lika svårt att bryta utfyllnadsschemat som att lösa det svåra. problem som ligger bakom det primitiva.
Trafikanalys och skydd via stoppning
Även om perfekta kryptografiska rutiner används kan angriparen få kunskap om mängden trafik som genererades. Angriparen kanske inte visste vad Alice och Bob pratade om, men kan veta att de pratade och hur mycket de pratade. Under vissa omständigheter kan detta läckage vara mycket kompromitterande. Tänk till exempel när en militär organiserar en hemlig attack mot en annan nation: det kan räcka med att varna den andra nationen för att de bara ska veta att det pågår en hel del hemlig aktivitet.
Som ett annat exempel, vid kryptering av Voice Over IP- strömmar som använder kodning med variabel bithastighet, döljs inte antalet bitar per tidsenhet, och detta kan utnyttjas för att gissa talade fraser. På liknande sätt är de skurmönster som vanliga videokodare producerar ofta tillräckliga för att identifiera den strömmande videon som en användare tittar på unikt. Även den totala storleken på enbart ett objekt, såsom en webbplats, fil, nedladdning av programpaket eller onlinevideo, kan unikt identifiera ett objekt, om angriparen känner till eller kan gissa en känd uppsättning objektet kommer ifrån. Sidokanalen med krypterad innehållslängd användes för att extrahera lösenord från HTTPS- kommunikation i de välkända CRIME- och BREACH - attackerna.
Att fylla på ett krypterat meddelande kan göra trafikanalys svårare genom att dölja den verkliga längden på dess nyttolast. Valet av längd att fylla ett meddelande till kan göras antingen deterministiskt eller slumpmässigt; varje tillvägagångssätt har styrkor och svagheter som gäller i olika sammanhang.
Randomiserad stoppning
Ett slumpmässigt antal ytterligare utfyllnadsbitar eller bytes kan läggas till i slutet av ett meddelande, tillsammans med en indikation i slutet hur mycket utfyllnad som lagts till. Om mängden utfyllnad väljs som ett enhetligt slumptal mellan 0 och något maximalt M, till exempel, kommer en avlyssnare inte att kunna bestämma meddelandets längd exakt inom det intervallet. Om den maximala utfyllnaden M är liten jämfört med meddelandets totala storlek, kommer denna utfyllnad inte att lägga till mycket overhead , men utfyllningen kommer att skymma endast de minst signifikanta bitarna av objektets totala längd, vilket gör att den ungefärliga längden av stora föremål lätt kan observeras och därför fortfarande potentiellt unikt identifierbara genom sin längd. Om den maximala utfyllnaden M är jämförbar med storleken på nyttolasten, däremot, är en avlyssnares osäkerhet om meddelandets verkliga nyttolaststorlek mycket större, till bekostnad av att utfyllnad kan lägga till upp till 100 % overhead (2× sprängning ) till budskapet.
Dessutom, i vanliga scenarier där en avlyssnare har möjlighet att se många på varandra följande meddelanden från samma avsändare, och dessa meddelanden är lika på ett sätt som angriparen känner till eller kan gissa, då kan avlyssnaren använda statistiska tekniker för att minska och så småningom till och med eliminera fördelen med randomiserad stoppning. Anta till exempel att en användares applikation regelbundet skickar meddelanden av samma längd, och avlyssnaren känner till eller kan gissa fakta baserat på till exempel fingeravtryck av användarens applikation. Alternativt kan en aktiv angripare kunna få en slutpunkt att skicka meddelanden regelbundet, till exempel om offret är en offentlig server. I sådana fall kan avlyssnaren helt enkelt beräkna medelvärdet över många observationer för att bestämma längden på det vanliga meddelandets nyttolast.
Deterministisk stoppning
Ett deterministiskt utfyllnadsschema fyller alltid en meddelandenyttolast av en given längd för att bilda ett krypterat meddelande med en speciell motsvarande utmatningslängd. När många nyttolastlängder mappas till samma vadderade utgångslängd, kan en avlyssnare inte urskilja eller lära sig någon information om nyttolastens verkliga längd inom en av dessa längdskopor, även efter många observationer av meddelanden av samma längd som sänds. I detta avseende har deterministiska utfyllnadsscheman fördelen att inte läcka någon ytterligare information med varje på varandra följande meddelande av samma nyttolaststorlek.
Å andra sidan, anta att en avlyssnare kan dra nytta av att lära sig om små variationer i nyttolaststorlek, som plus eller minus bara en byte i en lösenordsgissningsattack till exempel. Om meddelandeavsändaren har otur att skicka många meddelanden vars nyttolastlängder varierar med endast en byte, och den längden ligger exakt på gränsen mellan två av de deterministiska utfyllnadsklasserna, kommer dessa plus-eller-minus en nyttolastlängder konsekvent att ge olika vadderade längder också (plus-eller-minus ett block till exempel), läcker exakt den finkorniga information angriparen önskar. Mot sådana risker kan randomiserad utfyllnad erbjuda mer skydd genom att självständigt dölja de minst signifikanta bitarna av meddelandelängder.
Vanliga deterministiska utfyllnadsmetoder inkluderar utfyllnad till en konstant blockstorlek och utfyllnad till nästa större potens av två. Liksom randomiserad utfyllnad med en liten maximal mängd M , skymmer emellertid utfyllnad deterministiskt till en blockstorlek som är mycket mindre än meddelandenyttolasten endast de minst signifikanta bitarna av meddelandets sanna längd, vilket lämnar meddelandenas verkliga ungefärliga längd i stort sett oskyddad. Utfyllnad av meddelanden till en potens av två (eller någon annan fast bas) minskar den maximala mängd information som meddelandet kan läcka via sin längd från O (log M ) till O (log log M ) . Utfyllnad till en potens av två ökar dock meddelandestorleken med upp till 100 %, och utfyllnad till potenser av större heltalsbaser ökar den maximala overhead ytterligare.
PADMÉ-schemat, som föreslagits för vadderade likformiga slumpmässiga blobs eller PURBs , fyller deterministiskt meddelanden till längder som kan representeras som ett flyttal vars mantiss inte längre är (dvs innehåller inte mer signifikanta bitar) än dess exponent. Denna längdbegränsning säkerställer att ett meddelande läcker högst O (logg log M ) informationsbitar via sin längd, som utfyllnad till en potens av två, men medför mycket mindre overhead på högst 12 % för små meddelanden och minskar gradvis med meddelandestorleken .
Se även
- Skavning och vinkling , blanda in stora mängder nonsens innan du skickar
- Chiffertextstöld , ett annat sätt att hantera meddelanden som inte är en multipel av blocklängden
- Initialiseringsvektor , salt (kryptografi) , som ibland förväxlas med utfyllnad
- Nyckelinkapsling , ett alternativ till utfyllnad för system med offentliga nyckel som används för att utbyta symmetriska nycklar
- PURB eller vadderad enhetlig slumpmässig blob , en krypteringsdisciplin som minimerar läckage från antingen metadata eller längd
- Rysk parning , en annan teknik för att förhindra spjälsängar
