Krackningsmetoder för krypteringsalgoritmer

Kryptering är en av de viktigaste (och förmodligen de mest effektiva) metoderna för att skydda datakonfidentialitet, dvs. skydd av data från obehörig åtkomst. Kryptering är omvandlingen av öppna data till slutna data (enligt en viss krypteringsalgoritm med ett unikt element - krypteringsnyckel ), som kallas \ kryptering \ ; omvänd transformation - få öppen data från krypterad - kallas \ dekryptering \ , en nyckel är också involverad i denna operation.

Kryptering är en av de viktigaste (och förmodligen de mest effektiva) metoderna för att skydda datakonfidentialitet, dvs. skydd av data från obehörig åtkomst. Kryptering är omvandlingen av öppna data till slutna data (enligt en viss krypteringsalgoritm med ett unikt element - krypteringsnyckel ), som kallas \ kryptering \ ; omvänd transformation - få öppen data från krypterad - kallas \ dekryptering \(dekryptering) , en nyckel är också involverad i denna operation.

Krypteringsnyckeln är associerad med en specifik relation med dekrypteringsnyckeln; i det följande kommer vi bara att överväga de krypteringsalgoritmer där dekrypteringsnyckeln och krypteringsnyckeln sammanfaller ( symmetrisk kryptering ).

Krypteringsnyckeln \personaliserar\ krypteringsalgoritmen - utan att veta vilken krypteringsnyckel som krävs är det ganska svårt att dekryptera data. Svårighetsgraden att få öppen data från krypterade (och få en krypteringsnyckel i närvaro av en viss uppsättning data - mer om det nedan) är en av de viktigaste egenskaperna för krypteringsalgoritmer och kallas dess kryptografisk styrka .

Vetenskapen om att motverka kryptografiska skyddsmetoder (som inkluderar kryptering) kallas kryptanalys ... Faktum är att kryptanalys är en samling matematiska tekniker för att knäcka krypteringsalgoritmer. Samma evolutionsmotstånd spåras här tydligt som i fallet med rustning och en projektil: mer och mer ihållande (utan förlust av andra viktiga egenskaper - till exempel i hastighet) krypteringsalgoritmer visas, som svar på vilka mer och mer avancerade metoder för bryta dem uppfinns


Låt oss överväga moderna kryptanalytiska metoder, för vilka vi börjar med att klassificera attacker på krypteringsalgoritmer.

Attacker på krypteringsalgoritmer

När du utför en attack kan en kryptoanalytiker sikta på att lösa följande problem:

1. Hämta klartext från den krypterade.

2. Beräkna krypteringsnyckeln.

I allmänhet är den andra av de listade uppgifterna betydligt mer komplicerad än den första. Men med en krypteringsnyckel kan en kryptoanalytiker därefter dekryptera all data krypterad med den hittade nyckeln. En sådan attack (om den lyckas) kallas fullständig information krypteringsalgoritm.

Attacker på krypteringsalgoritmer klassificeras vanligtvis beroende på vilken uppsättning information som angriparen har innan han utför sin attack. Först och främst kan kryptanalytiska attacker delas in i två kategorier:

Kategori 1. En kryptanalytiker har endast förmågan att passivt lyssna på en viss kanal genom vilken krypterad data skickas (se fig. 1). Som ett resultat har angriparen bara en uppsättning chiffertexter krypterade med en specifik nyckel. Detta kallas en attack. känd ciffertext ... Det är det svåraste, men den här typen av attacker är den vanligaste, eftersom den är den mest \vitala\ - i den överväldigande majoriteten av verkliga fall kan kryptoanalytikern inte få mer data.

Figur: 1. Passiv avlyssning av krypterad data.

Kategori 2. Antar att kryptanalysatorn har någon form av krypteringsenhet med krypteringsnyckeln inbäddad, vilket är målet för attacken. En sådan anordning kan till exempel vara ett kryptografiskt smartkort. En kryptoanalytiker kan utföra vissa åtgärder med krypteraren (tillåten av krypteraren och dess tekniska miljö, liksom av de taktiska förutsättningarna för att utföra en attack) för att få den information han behöver, till exempel \köra\ all klartext genom krypterare för att erhålla motsvarande ciffertexter (se fig. 2).

Figur: 2. Aktivt inflytande på kodaren.

Beroende på de data som kryptoanalytikern kan \extrahera\ från krypteraren finns följande typer av attacker:

1. Känd attack med klartext ... Antar att kryptoanalysatorn har ett antal textpar, var och en är en klartext och dess motsvarande ciffertext.

2. Vald attack i klartext ... Cryptanalyst har förmågan att välja vanliga texter för att erhålla motsvarande ciphertexts (hur detta kan vara användbart för cryptanalyst kommer att diskuteras nedan).

3 ... Anpassningsbar attack för klartextval ... En kryptanalytiker kan inte bara välja öppna texter för kryptering utan också göra det upprepade gånger med hänsyn till resultaten från analysen av tidigare erhållna data.

4. Välj ciphertext attack ... En kryptoanalytiker kan välja ciphertexts och genom att köra dem genom en krypterare få genom dekryptering motsvarande klartext.

5. Adaptiv ciphertext-valattack. I analogi med de attacker som beskrivits tidigare är det uppenbart att en kryptanalytiker kan välja ciphertexts upprepade gånger för att dekryptera dem med hänsyn till tidigare resultat.

I teorin kanske en kryptanalysator inte kan begränsas till de som anges ovan; mer allvarliga alternativ för en kryptanalysers inflytande på en scrambler kommer att diskuteras i en senare del av den här artikeln.

Kvantifiera krypteringsalgoritmernas styrka

Kryptomotstånd är en kvantitativ egenskap hos krypteringsalgoritmer - ett visst antal resurser krävs för att öppna en specifik krypteringsalgoritm under vissa förhållanden (inklusive en viss kryptanalytisk metod). Resurserna i detta fall är följande värden:

1. Mängden information som krävs för att utföra en attack - säg hur många par kända eller valda texter som behövs.

2. Den tid det tar att utföra attacken. Det mäts vanligtvis i antalet testkrypteringsoperationer av den attackerade algoritmen, vars exekvering, om andra nödvändiga villkor är uppfyllda, till exempel kommer att beräkna krypteringsnyckeln.

3. Minne krävs för att lagra information som används under en attack. Det är också en viktig egenskap, eftersom många attacker kan ha mycket stora minneskrav.

Kombinationen av dessa tre värden kännetecknar en specifik attack mot en specifik krypteringsalgoritm. Och det bästa (som kräver ett minimum av resurser) av de möjliga attackerna mot en algoritm kännetecknar dess kryptografiska styrka.

Härefter antas det att angriparen känner till krypteringsalgoritmen - endast nyckeln är okänd. Den överväldigande majoriteten av kryptanalytiska metoder (som kommer att diskuteras i de efterföljande delarna av artikeln) bygger på en grundlig kunskap om kryptanalysatorens attackerade algoritm. Det finns också en viktigare egenskap hos krypteringsalgoritmen - hur mycket ciphertexts som erhålls med hjälp skiljer sig från en slumpmässig sekvens. Dessutom kan denna egenskap uttryckas kvantitativt i samma tre typer av resurser som beskrivs ovan, men detta är redan ett ämne för en separat artikel.

Kryptanalys av modifierade algoritmer

Det finns många krypteringsalgoritmer som är kryptografiskt starka. I ett välkänt arbete definieras begreppet en stark algoritm enligt följande:

1. En algoritm är kryptografiskt säker om det inte finns några metoder för att bryta den från brute force-metoden, vilket kommer att diskuteras i nästa del av artikeln.

2. Dessutom är algoritmens nyckelstorlek tillräckligt stor för att göra brute-force-metoden omöjlig vid den nuvarande datorteknologin.

Det kan dock till exempel vara nödvändigt att jämföra två eller flera kryptografiskt starka krypteringsalgoritmer med varandra (som till exempel i en öppen tävling om en ny amerikansk krypteringsstandard AES). I detta fall används en annan egenskap (snarare kvalitativ än kvantitativ) - säkerhetsmarginalen.

Det är känt att den överväldigande majoriteten av moderna krypteringsalgoritmer består av ett visst antal omgångar, i var och en av samma (eller liknande) transformationer upprepas över den krypterade datan. För att bestämma marginalen för kryptografisk styrka, analysera algoritmen med trunkerad rundor - d.v.s. modifiering av algoritmen som studeras, där antalet rundor minskas jämfört med det specifika antalet rundor som tillhandahålls i algoritmen. Den kryptografiska styrkan kan definieras som förhållandet mellan det initiala antalet omgångar av den studerade algoritmen och det maximala antalet omgångar av dess modifieringar som inte är kryptografiskt starka.

Ett annat alternativ för att bestämma den kryptografiska styrkan är analysen av modifieringar av den undersökta algoritmen med mindre förändringar i den runda strukturen. Ett av de mest slående exemplen är att knäcka Skipjack-3XOR-algoritmen med endast 29 valda släta texter och deras motsvarande ciffertexter genom att endast utföra cirka en miljon testkrypteringsoperationer. Tack vare denna attack kan Skipjack-3XOR enligt moderna standarder betraktas som en mycket svag algoritm, men den skiljer sig från den välkända och ganska utbredda krypteringsalgoritmen Skipjack genom att endast 3 specifika XOR-operationer tas bort från den senare strukturen ( bitvis logisk operation \exklusiv eller\) för sådana operationer som tillhandahålls av Skipjack-algoritmen (!). Följaktligen fanns (dock obevisade) antaganden om den otillräckliga kryptografiska styrkan hos Skipjack-algoritmen. I fallet med analys av algoritmer med liknande modifieringar kan dock kryptografisk styrka marginal endast betraktas som en kvalitativ egenskap som har ett ganska indirekt förhållande till den krypteringsalgoritm som studeras.

1