Ett blockchiffer är ett slags symmetriskt chiffer [1] som arbetar med grupper av bitar med en fast längd - block vars karakteristiska storlek varierar inom 64‒256 bitar. Om originaltexten (eller dess återstod) är mindre än blockstorleken, utfylls den före kryptering . Faktum är att ett blockchiffer är en substitution på alfabetet av block, som som en konsekvens kan vara mono- eller polyalfabetisk. [2] Blockchifferet är en viktig komponent i många kryptografiska protokoll och används ofta för att skydda data som överförs över ett nätverk.
Till skillnad från ett chifferblock , där längden på nyckeln är lika med längden på meddelandet, kan ett blockchiffer kryptera ett eller flera meddelanden med en enda nyckel med en total längd som är större än nyckelns längd. Att överföra en nyckel som är liten jämfört med meddelandet över en krypterad kanal är en mycket enklare och snabbare uppgift än att överföra själva meddelandet eller en nyckel av samma längd, vilket gör det möjligt att använda det varje dag. Men i det här fallet upphör chifferet att vara okrossbart. Blockchiffer skiljer sig från strömchiffer genom att de bearbetar bitar i grupper snarare än i en ström. Samtidigt är blockchiffer långsammare än strömchiffer. [3] Symmetriska system har en fördel framför asymmetriska när det gäller krypteringshastighet, vilket gör att de kan förbli relevanta, trots den svagare nyckelöverföringsmekanismen (mottagaren måste känna till den hemliga nyckeln som måste sändas över en redan etablerad krypterad kanal. Samtidigt tid, i asymmetriska chiffer kan den publika nyckel som behövs för kryptering vara känd för alla, och det finns inget behov av att dela krypteringsnyckeln).
Fördelarna med blockchiffer inkluderar likheten mellan kryptering och dekrypteringsprocedurer , som i regel endast skiljer sig åt i ordningsföljden för åtgärder. Detta förenklar skapandet av krypteringsenheter, eftersom det tillåter användning av samma block i krypterings- och dekrypteringskedjorna. Flexibiliteten hos blockchiffer gör att de kan användas för att konstruera andra kryptografiska primitiver: en pseudo-slumpmässig sekvensgenerator , ett strömchiffer, infogningsimitationer och kryptografiska hash . [fyra]
Den moderna blockchiffermodellen är baserad på idén om iterativa blockchiffer som föreslås i Claude Shannons 1949-publikation " Communication Theory in Secret Systems ". Detta koncept låter dig uppnå en viss säkerhetsnivå genom att kombinera lätta att utföra substitution och permutationsoperationer [ 5 ] .
Fram till 1970-talet var kryptografi militärens och underrättelseofficerarnas lott, det fanns praktiskt taget inga publikationer i den öppna pressen [6] . Pionjären var chiffret " Lucifer ", utvecklat 1970 av IBM och baserat på SP-net . Idén med chifferet var att använda kombinationer av enkla och därför snabbt beräknade operationer både i hårdvara och mjukvara. Schemat visade sig dock vara misslyckat: det var för besvärligt, vilket ledde till en låg krypteringshastighet i mjukvaruimplementering (cirka 8 kb/s) och i hårdvara (97 kb/s).
Oron för stabiliteten hos denna algoritm började dyka upp. Principerna som utvecklades under konstruktionen av Lucifer (SP-nätverket och Feistel-nätverket , uppkallat efter en av utvecklarna) låg dock till grund för konstruktionen av blockchiffer.
1973 utlyste National Institute of Standards and Technology ( NIST ) en tävling för att utveckla en datakrypteringsstandard, vars vinnare 1974 var DES (Data Encryption Standard)-chifferet, som i själva verket är en förbättrad version av Lucifer . Publiceringen av chifferet 1977 var grundläggande för allmänhetens förståelse av den moderna blockchiffermodellen. Samtidigt gav det upphov till utvecklingen av kryptoanalytiska attacker .
Efter att ha godkänts av American National Standards Institute 1981, användes algoritmen i den civila sektorn under lång tid och gick till och med utanför USA . Chifferet hade dock en betydande nackdel - en liten nyckellängd, vilket gav upphov till många attacker förknippade med parallell uppräkning och den annalkande möjligheten att implementera den. Bristen på adekvat skydd mot DES-chifferattacker har gett upphov till många algoritmer som både är en mer komplex version av DES ( 3DES ) och helt andra scheman ( NewDES , FEAL , IDEA ).
1997 var starten för AES -programmet (Advanced Encryption Standard). Tävlingen bestod av tre etapper, varav den slutliga vinnaren var RIJNDAEL- algoritmen utvecklad av belgierna J. Daemen och V. Rijmen. AES är, liksom sina föregångare, också byggt med hjälp av SP-nätverket.
Idag finns det många attacker som blockchifferet måste motstå, med början med brute-force attacken som den mest triviala. [7]
Ett blockchiffer består av två parade algoritmer: kryptering och dekryptering . [8] Båda algoritmerna kan representeras som funktioner. Krypteringsfunktionen E ( eng. kryptering - kryptering) tar emot ett datablock M ( eng. meddelande - meddelande) med en storlek på n bitar och en nyckel K ( eng. nyckel - nyckel) med en storlek på k bitar som inmatning och ger ett block av chiffertext C ( eng. chiffer ) vid utgången - chiffer) med en storlek på n bitar:
För vilken nyckel som helst K är EK en bijektiv funktion ( permutation ) på uppsättningen av n -bitars block. Dekrypteringsfunktionen D ( eng. decryption - decryption ) tar emot chiffertexten C, nyckeln K som inmatning, och ger M vid utgången:
är samtidigt inversen av krypteringsfunktionen:
ochObservera att nyckeln som krävs för kryptering och dekryptering är densamma, en följd av blockchiffrets symmetri.
”Att designa ett blockchiffer är inte svårt. Svårigheten ligger i att designa ett blockchiffer som inte bara är säkert, utan också lätt att beskriva och enkelt att implementera.”
Bruce Schneier , kryptograf och datasäkerhetsspecialist .
Pionjärer i utvecklingen av blockchiffer var anställda av IBM när de arbetade med chifferen " Lucifer ". [9] De designade de första fundamenten som användes i utvecklingen av efterföljande kretsar. Samtidigt bör man ta hänsyn till att det nya chiffret inte bara ska vara motståndskraftigt mot alla kända typer av attacker, utan också ganska enkelt att implementera.
De flesta blockchiffer är iterativa. Detta innebär att det givna chifferet omvandlar klartextblock med konstant längd till chiffertextblock av samma längd med hjälp av cykliska reversibla funktioner som kallas runda funktioner. [10] Detta beror på enkelheten och hastigheten för exekvering av både mjukvaru- och hårdvaruimplementationer. Vanligtvis använder runda funktioner olika nycklar härledda från den ursprungliga nyckeln:
,där C i är värdet på blocket efter den i:e omgången, C 0 = M är klartexten, K i är nyckeln som används i den i:te omgången och erhålls från den ursprungliga nyckeln K.
Blockstorleken n är en fast blockchifferparameter, vanligtvis 64 eller 128 bitar, även om vissa chiffer tillåter flera olika värden. En längd på 64 bitar var acceptabel fram till mitten av 1990-talet, då 128 bitar användes, vilket ungefär motsvarar storleken på ett maskinord och möjliggör effektiv implementering på de flesta vanliga datorplattformar. Olika krypteringsscheman låter dig kryptera vanlig text av godtycklig längd. Var och en har vissa egenskaper: sannolikhet för fel, lättillgänglighet, sårbarhet för attacker. Från och med 2006 kunde en 80-bitars nyckel förhindra en brute-force attack .
SP-nätverk ( engelsk substitution-permutation network, SPN ) är en av de viktigaste typerna av iterativa blockchiffer. Ett chiffer baserat på SP-nätet får ett block och en nyckel som input och utför flera alternerande omgångar, bestående av alternerande substitutionssteg och permutationssteg [ 11 ] . En S-box räcker för att uppnå säkerhet, men ett sådant block kommer att kräva en stor mängd minne. Därför används små S-boxar blandade med P-boxar [6] . Det icke-linjära substitutionssteget blandar nyckelbitarna med klartextbitarna, vilket skapar Shannons förlägenhet Det linjära permutationssteget fördelar redundansen genom datastrukturen, vilket ger upphov till diffusion [12] [13] .
S - boxen ersätter ett litet block av ingångsbitar med ett annat block av utgångsbitar. Denna substitution måste vara en-till-en för att garantera reversibilitet. Syftet med S-boxen är för en icke-linjär transformation, vilket förhindrar att linjär kryptoanalys utförs . En av egenskaperna hos S-boxen är lavineffekten , det vill säga en förändring av en bit vid ingången leder till en förändring av alla bitar vid utgången [14] .
P-block - permutation av alla bitar: blocket tar emot utdata från S-boxen som indata, byter alla bitar och matar resultatet till S-boxen i nästa omgång. En viktig egenskap hos en P-box är möjligheten att fördela uteffekten från en S-box till ingångarna på så stora S-boxar som möjligt.
För varje runda används en annan nyckel , erhållen från den ursprungliga . En sådan nyckel kallas en rund nyckel. Den kan erhållas genom att dela upp originalnyckeln i lika delar, eller genom någon form av transformation av hela nyckeln.
Ett Feistel-nätverk är en allmän metod för att omvandla en godtycklig funktion F till en permutation på en uppsättning block. [15] Den består av cykliskt repeterande celler - rundor. Inom varje omgång är klartextblocket uppdelat i två lika delar. Rund funktion
tar en halva (till vänster i figuren), omvandlar den med tangenten Ki och kombinerar resultatet med den andra halvan med den exklusiva ELLER (XOR) operationen. Denna nyckel ges av den initiala nyckeln K och är olika för varje varv. Sedan byts halvorna (annars kommer bara ena halvan av blocket att konverteras) och matas till nästa omgång. Feistel-nätverkets transformation är en reversibel operation.
Det finns vissa krav för F- funktionen :
Om det första kravet inte uppfylls kommer nätverket att utsättas för differentiella attacker (liknande meddelanden kommer att ha liknande chiffer). I det andra fallet är chiffrets handlingar linjära, och att lösa ett system av linjära ekvationer är tillräckligt för att bryta [3] .
Denna design har en påtaglig fördel: krypterings-/dekrypteringsprocedurerna är desamma, endast derivatorna av originalnycklarna används i omvänd ordning. Detta innebär att samma block kan användas för både kryptering och dekryptering, vilket säkerligen förenklar implementeringen av chifferet. Nackdelen med schemat är att endast hälften av blocket bearbetas i varje omgång, vilket leder till behovet av att öka antalet omgångar. [2]
När man konstruerar algoritmen beaktas bildandet av en grupp , där elementen är uppsättningen av chiffertextblock med alla nycklar, och gruppoperationen är sammansättningen av krypteringsrundor. Om ett givet chiffer bildar en nästan komplett grupp är det ingen mening att använda multipelkryptering [6] .
I sig själv låter ett blockchiffer dig endast kryptera enstaka datablock av en förutbestämd längd. Om meddelandelängden är mindre än blocklängden ( eng. blocklength ), så utfylls det till önskad längd. Men om meddelandelängden är längre blir det nödvändigt att dela upp det i block. Samtidigt finns det flera sätt att kryptera sådana meddelanden, så kallade blockchifferfunktioner.
Det enklaste arbetssättet för ett blockchiffer är det elektroniska kodboksläget eller det enkla substitutionsläget ( Eng. Electronic CodeBook, ECB ), där alla klartextblock är krypterade oberoende av varandra. Men när du använder detta läge bevaras de statistiska egenskaperna för öppna data delvis, eftersom varje identiskt datablock unikt motsvarar ett krypterat datablock. Med en stor mängd data (till exempel video eller ljud) kan detta leda till läckage av information om deras innehåll och ge mer utrymme för kryptoanalys .
Att ta bort statistiska beroenden i klartext är möjligt med hjälp av preliminär arkivering, men det löser inte problemet helt, eftersom arkiverarens tjänstinformation finns kvar i filen , vilket inte alltid är acceptabelt.
För att övervinna dessa problem har andra driftsätt [16] [17] utvecklats , etablerade av den internationella standarden ISO/IEC 10116 [18] och definierade av nationella riktlinjer, såsom NIST 800-38A [19] och BSI TR- 02102 [20]
Den allmänna idén är att använda ett slumptal, ofta kallat en initialiseringsvektor (IV). I det populära läget Cipher Block Chaining ( CBC ) måste IV vara slumpmässig eller pseudo-slumpmässig för säkerhets skull. När den väl har definierats, XORed den med det första blocket av klartext. Nästa steg är att kryptera resultatet och få det första chifferblocket, som vi använder som IV för det andra blocket, och så vidare. I chifferåterkopplingsläget ( CFB ) krypteras IV direkt, varefter den läggs till modulo två (XOR, exklusiv OR) med det första blocket. Det mottagna chifferblocket används som IV för ytterligare kryptering. Läget har inga speciella fördelar jämfört med de andra. Till skillnad från de tidigare lägena, krypterar OFB - läget ( Output Feedback ) IV:n cykliskt och bildar en ström av nycklar som läggs till meddelandeblocken. Fördelen med läget är det fullständiga sammanträffandet av krypterings- och dekrypteringsoperationerna. Räknarläget ( English Counter, CTR ) liknar OFB, men tillåter parallell beräkning av chiffer: IV kombineras med blocknumret utan ett och resultatet krypteras. Det resulterande blocket läggs till det motsvarande meddelandeblocket.
Tänk på att initieringsvektorn måste vara olika i olika sessioner. Annars kommer vi fram till problemet med ECB-läge. Det går att använda ett slumptal, men detta kräver en någorlunda bra slumptalsgenerator. Därför sätts vanligtvis ett visst nummer - en etikett som är känd för båda parter (till exempel sessionsnumret) och kallas en nonce ( Number Used Once ) . Sekretess för detta nummer krävs vanligtvis inte. Ytterligare IV är resultatet av nonce-kryptering. I fallet med räknarläge används nonce för att bilda den runda nyckeln K i [3] :
där i är det runda talet.Som nämnts ovan, om längden på själva meddelandet, eller det sista blocket, är mindre än längden på blocket, måste det fyllas med . Att bara fylla med nollbitar löser inte problemet, eftersom mottagaren inte kommer att kunna hitta slutet på nyttolasten. Dessutom leder det här alternativet till attacker av tilläggets Oracle [21] .
Därför är i praktiken lösningen som standardiserats som "Komplementmetod 2" ( Bit Completion ) i ISO/IEC 9797-1 tillämpbar, lägger till en 1 bit i slutet av meddelandet och fyller det återstående utrymmet med nollor [22] . I detta fall har motstånd mot sådana attacker bevisats [23] .
Liksom alla chiffer vars algoritmer är kända, är blockchiffer föremål för kryptografiska attacker. Målet med attacken är att utveckla en sprickningsalgoritm som är mer effektiv än en uttömmande sökning av alla möjliga nycklar. Om en sådan lösning hittas anses attacken vara framgångsrik. Samtidigt bryts chiffret om det finns en attack som tillåter brytning under den tid som informationen förblir relevant, och att utföra en sådan attack är fördelaktigt för angriparen.
engelsk True force attack . På grund av egenskapen hos ett blockchiffer som funktionsreversibilitet, blir dess utdata särskiljbar från en sann slumpmässig sekvens på grund av födelsedagsparadoxen . Denna funktion leder till en minskning av chifferns säkerhet och behovet av att ta hänsyn till blockstorleken. Det finns alltså en avvägning mellan stora block som minskar chifferns prestanda och opålitliga små block [24] .
Storleken på nyckeln spelar en lika viktig roll. Det tidiga DES -chifferet kännetecknades av en nyckelstorlek på 56 bitar, vilket, som praxis har visat, uppenbarligen inte är tillräckligt för tillförlitlig dataöverföring. Det var en brute-force attack som först bröt DES. Modernare algoritmer som AES och GOST 28147-89 har en nyckelstorlek på 128 bitar respektive 256 bitar, vilket gör sådana attacker meningslösa [25] .
engelsk Differentiell kryptoanalys . År 1990 definierade Eli Biham och Adi Shamir idén om differentiell kryptoanalys. Med denna metod var det möjligt att knäcka DES- chifferet . Konstanta S-box-chiffer och kodade e-boksläges- chiffer är känsliga för en liknande attack . Denna metod fungerar med par av chiffertexter för vilka skillnaden mellan motsvarande klartexter är känd, och tar hänsyn till utvecklingen av dessa skillnader. Tillsammans med den linjära är den vanligast vid attacker mot ett blockchiffer [6] .
engelsk Linjär kryptoanalys . Linjär kryptoanalys är en chifferbrytningsmetod baserad på sökningen efter affina approximationer för att algoritmen ska fungera. Utvecklad av den japanske matematikern Mitsuru Matsui , som var den första att använda denna teknik för att attackera DES och FEAL . Metoden är baserad på att tillämpa operationen "Exclusive OR" (XOR) på blocken av klartext, chiffertext och deras resultat, vilket gör det möjligt att erhålla resultatet av XORing av nyckelbitarna. S-blockets struktur har ett starkt inflytande på motståndet mot linjeattacker. När metoden utvecklades visade det sig att DES hade en svaghet för den, eftersom ingen hade förväntat sig sådana attacker när den utvecklades [6] .
engelsk Intergal kryptoanalys . Integral kryptoanalys är en typ av attack som är speciellt tillämplig på blockchiffer byggda på SP-nätet. Till skillnad från differentiell kryptoanalys, som använder ett par utvalda klartexter med en fast skillnad beräknad med XOR-operationen, använder integrerad kryptoanalys uppsättningar av klartexter där vissa delar hålls konstanta medan andra varierar mellan möjliga värden. En sådan uppsättning har nödvändigtvis en modulo 2 (XOR) summa på 0, medan motsvarande chiffertextsumma innehåller information om chifferets operationer.
Utöver de som beskrivs ovan finns det andra typer av attacker:
Varje ny chiffer måste visa motstånd mot alla kända typer av attacker.
I praktiken utvärderas ett blockchiffer enligt en mängd olika kriterier [26] [27] :
Luciferchifferet betraktas allmänt som det första blockchifferet. Algoritmen utvecklades av IBM på 1970-talet för dess egna behov och är baserad på Horst Feistels arbete . Den slutgiltiga versionen antogs som den amerikanska regeringens federala informationsbehandlingsstandard : FIPS PUB 46 Data Encryption Standard (DES) - datakrypteringsstandard.
DES har en blockstorlek på 64 bitar och en nyckel på 56 bitar. Därefter blev 64-bitars block allmänt accepterade i konstruktionen av chifferet. Nyckellängden berodde på flera faktorer, inklusive regeringsrestriktioner, och blev som ett resultat en uppenbar nackdel med algoritmen - den räckte inte för att motstå brute-force-attacker. 1993 designade Michael Wiener en maskin på 1 miljon dollar som kunde knäcka DES på 3,5 timmar med brute force , och 1998 byggdes en maskin som knäcka. Dessutom, för nycklarna till algoritmen, finns det ett antal värden som anses vara svaga [6] .
Det finns en förbättrad version av algoritmen som kallas Triple DES eller 3DES. Algoritmens hastighet minskade tre gånger, men systemet visade sig vara mycket mer motståndskraftigt mot uttömmande sökning på grund av den tredubblade nyckellängden (168 bitar och 112 hemliga bitar). Alternativt kan du välja en dubbelnyckel (112 bitar och 80 hemliga bitar). Från och med 2011 behåller trenyckelsystemet sin säkerhet, men tvånyckelversionen med 80-bitars säkerhet uppfyller inte längre moderna krav [28] .
GOST 28147-89, en rysk krypteringsstandard som introducerades 1990, är också en CIS-standard. Chifferet är baserat på ett 32-runda Feistel-nätverk med en 256-bitars nyckel. I maj 2011 försökte kryptanalytiker Nicolas Courtois en attack som minskade sprickningstiden med en faktor på 28 (256) men krävde 264 klartext/ chiffertext- par, vilket inte kan anses vara en framgångsrik attack, eftersom det inte finns något behov av denna mängd klartext. för kunskap om chiffertexten. [29] [30]
På grund av närvaron av ett stort antal omgångar är attacker baserade på differentiell och linjär kryptoanalys inte genomförbara, eftersom de senare är känsliga för antalet omgångar. En fullständig sökning med en sådan nyckellängd är helt meningslös. För att uppnå lavineffekten kräver GOST 8 omgångar, vilket kan vara en svaghet i algoritmen, men vid 32 omgångar spelar det inte så stor roll. Frågan om säkerheten för GOST är fortfarande öppen [6] .
Antogs av NIST 2001 efter 5 år av offentlig konkurrens, AES ersatte DES som USA:s federala standard. Chifferet utvecklades av två belgiska kryptografer , Daimen Yoan och Raymen Vincent . Blockstorleken är 128 bitar och nyckelstorlekarna är 128, 192 och 256 bitar, även om blockstorleken kan specificeras med valfritt antal bitars multipel av 32, med ett minimivärde på 128 bitar. Den maximala blockstorleken är 256 bitar, medan nyckelstorleken inte har någon teoretisk gräns. Stöd för detta chiffer introducerades av Intel i x86 -processorfamiljen .
Blockchifferet kan användas för att konstruera andra kryptografiska primitiver :
Ordböcker och uppslagsverk |
---|
Symmetriska kryptosystem | |
---|---|
Streama chiffer | |
Feistel nätverk | |
SP nätverk | |
Övrig |