A5 (krypteringsalgoritm)

A5  är en strömmande krypteringsalgoritm som används för att säkerställa konfidentialitet för data som överförs mellan telefonen och basstationen i det europeiska systemet för mobil digital kommunikation GSM ( Groupe Spécial Mobile ).

Chifferet är baserat på bitvis addition modulo två (boolesk XOR-operation) av den genererade pseudo-slumpmässiga sekvensen och informationen som ska krypteras. I A5 implementeras en pseudo-slumpmässig sekvens baserad på tre linjära återkopplingsskiftregister . Registren är 19, 22 respektive 23 bitar långa. Skiften styrs av en speciell krets som organiserar förskjutningen av minst två register vid varje steg, vilket leder till deras ojämna rörelse. Sekvensen bildas av XOR-operationen på registrens utgångsbitar.

Skapandes och utvecklingens historia

Inledningsvis utvecklades ett strömchiffer av franska militära kryptografer för att uteslutande användas för militära ändamål. I slutet av 80-talet krävde GSM-standarden skapandet av ett nytt, modernt säkerhetssystem. Den baserades på tre hemliga algoritmer: autentisering - A3 , strömkryptering - A5, generering av sessionsnyckel - A8 . En fransk utveckling användes som A5-algoritmen. Detta chiffer gav en ganska bra säkerhetsström och därför konfidentialiteten i konversationen. Till en början förväntades inte exporten av standarden från Europa, men snart uppstod behovet. Det var därför A5 döptes om till A5 / 1 och började distribueras både i Europa och i USA. För andra länder (inklusive Ryssland) modifierades algoritmen, vilket avsevärt sänkte chifferets kryptografiska styrka. A5/2 designades specifikt som ett exportalternativ för länder utanför EU. Den kryptografiska styrkan hos A5/2 reducerades genom att lägga till ytterligare ett register (17 bitar) som styr skiftningarna av resten. I A5/0 finns ingen kryptering alls. Algoritmen A5/3, baserad på Kasumi- algoritmen, har också utvecklats och godkänts för användning i 3G-nätverk. Dessa modifieringar kallas A5/x.

Utseende i det offentliga området

Officiellt publicerades inte detta kryptoschema och dess struktur offentliggjordes inte. Detta berodde på att utvecklarna förlitade sig på säkerhet på bekostnad av oklarhet , vilket innebär att algoritmer är svårare att knäcka om deras beskrivningar inte är offentligt tillgängliga. Data lämnades till GSM-operatörer endast vid behov. Men 1994 var detaljerna i A5-algoritmen kända: det brittiska telefonbolaget British Telecom lämnade in all dokumentation angående standarden till University of Bradford för analys utan att ingå ett sekretessavtal . Dessutom dök material om standarden upp på en av konferenserna i Kina. Som ett resultat läckte hans plan gradvis ut i vida kretsar. Samma år publicerade Cambridge-forskarna Ross Anderson (Ross Anderson) och Michael Roe (Michael Roe) ett kryptoschema som återställts från dessa data och bedömde dess kryptografiska styrka [1] . Den slutliga algoritmen presenterades i Jovan Golics arbete vid Eurocrypt'97-konferensen.

A5-struktur

Algoritmen A5 är för närvarande en hel familj av chiffer. För beskrivning, låt oss ta A5/1 som stamfader till denna familj. Förändringar i derivatalgoritmer kommer att beskrivas separat.

Strömkryptering

I denna algoritm motsvarar varje vanlig texttecken ett chiffertexttecken. Text är inte uppdelad i block (som i blockchiffer ) och ändras inte i storlek. För att förenkla hårdvaruimplementeringen och därför öka prestanda, används endast de enklaste operationerna: modulo 2 addition (XOR) och registerskift.

Utdatasekvensen bildas genom att lägga till källtextströmmen till den genererade sekvensen (gamma). Det speciella med XOR-operationen är att den tillämpas ett jämnt antal gånger leder till det initiala värdet. Följaktligen avkodas meddelandet genom att lägga till chiffertexten till en känd sekvens.

Systemets säkerhet beror alltså helt på sekvensens egenskaper. Helst är varje bit av gamma en oberoende slumpmässig variabel, och själva sekvensen är slumpmässig. Ett sådant system uppfanns av Vernam 1917 och uppkallades efter honom. Som Claude Shannon bevisade 1949 ger detta absolut säkerhet. Men användningen av en slumpmässig sekvens innebär överföring över en säker kanal av ett meddelande som är lika i volym som vanlig text, vilket avsevärt komplicerar uppgiften och praktiskt taget inte används någonstans.

I verkliga system skapas en nyckel av en given storlek, som enkelt överförs över en privat kanal. Sekvensen genereras baserat på den och är pseudo-slumpmässig. En stor klass av strömchiffer (inklusive A5) är chiffer vars pseudo-slumpmässiga sekvensgenerator är baserad på linjära återkopplingsskiftregister.

RSLOS

Ett linjärt återkopplingsskiftregister består av själva registret (en sekvens av bitar av en given längd) och återkoppling. På varje cykel inträffar följande åtgärder: biten längst till vänster (högsta biten) extraheras, sekvensen skiftas till vänster och värdet på återkopplingsfunktionen skrivs till den tomma högra cellen (minst signifikant bit). Denna funktion är modulo två-summan av vissa bitar i registret och skrivs som ett polynom, där exponenten anger bitnumret. De extraherade bitarna bildar utmatningssekvensen.

För LFSR är huvudindikatorn perioden för den pseudo-slumpmässiga sekvensen. Den blir maximal (och lika med 2 n − 1) om återkopplingspolynomet är primitivt modulo 2 . Utgångssekvensen i detta fall kallas en M-sekvens.

LFSR-system i A5

LFSR i sig lämpar sig lätt för kryptoanalys och är inte tillräckligt stark för att användas i kryptering. Praktiska tillämpningar är system med variabla klockregister med olika längder och återkopplingsfunktioner.

Strukturen för A5-algoritmen är som följer:

  • Tre register (R1, R2, R3) har längder på 19, 22 och 23 bitar,
  • Återkopplingspolynom:
    • X 19 + X 18 + X 17 + X 14 + 1 för R1,
    • X 22 + X 21 + 1 för R2 och
    • X 23 + X 22 + X 21 + X 8 + 1 för R3,
  • Klockning styrs av en speciell mekanism:
    • varje register har synkbitar: 8 (R1), 10 (R2), 10 (R3),
    • funktionen F = x&y|x&z|y&z beräknas, där & är boolesk AND, | - booleskt ELLER, och x, y och z är synkroniseringsbitarna R1, R2 respektive R3,
    • endast de register som har synkbiten lika med F skiftas,
    • i själva verket skiftas registren vars synkbit tillhör majoriteten,
  • Systemets utgångsbit är resultatet av XOR-operationen på registrens utgångsbitar.

A5-algoritmens funktion

Låt oss överväga funktionerna i algoritmens funktion baserat på det kända schemat. Dataöverföringen utförs i en strukturerad form - uppdelad i ramar (114 bitar). Före initiering återställs registren, sessionsnyckeln (K - 64 bitar) bildad av A8 och ramnumret (Fn - 22 bitar) matas in i algoritmen . Därefter utförs följande steg sekventiellt:

  • Initiering:
    • 64 cykler, där nästa bit av nyckeln XORed med den minst signifikanta biten i varje register, medan registren skiftas på varje cykel,
    • liknande 22 cykler, endast XOR-operationen utförs med ramnumret,
    • 100 cykler med registerskiftkontroll, men ingen sekvensgenerering,
  • 228 (114 + 114) cykler fungerar, den överförda ramen är krypterad (de första 114 bitarna) och den mottagna ramen dekrypteras (de sista 114 bitarna),
  • ytterligare initiering utförs på nytt, ett nytt ramnummer används.

Skillnader i härledda algoritmer A5/x

Ytterligare ett 17-bitarsregister (R4) har lagts till i A5/2-algoritmen , som styr restens rörelse. Strukturförändringarna är som följer:

  • lagt till register R4 med en längd på 17 bitar,
  • återkopplingspolynom för R4: ,
  • klockning styrs av R4:
    • R4 har synkbitar 3, 7, 10,
    • majoritetsfunktionen beräknas F = x&y|x&z|y&z (lika majoriteten), där & är boolesk OCH, | - booleskt OR, och x, y och z är synkroniseringsbitarna R4(3), R4(7) respektive R4(10),
    • R1 skiftas om R4(10) = F,
    • R2 skiftas om R4(3) = F,
    • R3 skiftas om R4(7) = F,
  • systemets utgångsbit är resultatet av XOR-operationen på de höga bitarna i registren och majoritetsfunktioner från vissa bitar i registren:
    • R1 - 12, 14, 15,
    • R2 - 9, 13, 16,
    • R3 - 13, 16, 18.

Förändringar i funktion är inte så betydande och gäller endast initiering:

  • 64+22 cykler är fyllda med sessionsnyckel och ramnummer även R4,
  • 1 cykel R4(3), R4(7) och R4(10) är fyllda med 1,
  • 99 cykler med registerskiftstyrning, men ingen sekvensgenerering.

Det kan ses att initiering tar samma tid (100 cykler utan generering är uppdelade i två delar).

Algoritmen A5/3 utvecklades 2001 och ska ersätta A5/1 i tredje generationens mobilsystem. Den kallas också för Kasumi- algoritmen . När det skapades togs Mitsubishi Corporations MISTY- chiffer som grund. A5/3 anses för närvarande ge erforderligt motstånd.

Algoritmen A5/0 innehåller ingen kryptering.

Säkerhet

Utvecklingen av GSM-standarden innebar en kraftfull krypteringsmaskin som inte kunde hackas (särskilt i realtid). Utvecklingen som användes, med korrekt implementering, gav högkvalitativ kryptering av överförda data. Detta är den typ av information som kan erhållas från företag som distribuerar denna standard. Men det är värt att notera en viktig nyans: att lyssna på konversationer är ett integrerat attribut som används av specialtjänster. De var intresserade av möjligheten att avlyssna för sina egna ändamål. Således gjordes ändringar i algoritmen, vilket gjorde det möjligt att knäcka på en acceptabel tid. Dessutom modifierades A5 för export till A5/2. MoU (Memorandum of Understand Group Special Mobile standard) erkänner att syftet med att utveckla A5/2 var att minska krypteringens kryptografiska styrka, men de officiella testresultaten säger att det inte finns några kända brister i algoritmen [2] .


Kända sårbarheter

Med tillkomsten av data om A5-standarden började försök att knäcka algoritmen, samt att söka efter sårbarheter. En stor roll spelades av funktionerna i standarden, som kraftigt försvagar skyddet, nämligen:

  • 10 bitar av nyckeln tvingas till noll,
  • brist på tvärlänkar mellan register (förutom skiftkontroll),
  • kryptering av tjänstinformation känd för kryptoanalytikern,
  • mer än 40 % av nycklarna leder till den minsta längden på perioden för den genererade sekvensen, nämligen [3]
  • i början av sessionen utbyts null-meddelanden (en bildruta i taget),
  • samma stoppning för alla paket,
  • i A5/2 utförs rörelsen av ett separat register 17 bitar långt.

Baserat på dessa "hål" i algoritmen byggs hackningsscheman.

Anmärkningsvärda attacker

Nyckeln är en 64-bitars sessionsnyckel, ramnumret antas vara känt. Således är komplexiteten för en brute-force attack 2 64 .

De första recensionerna av chiffret (Ross Andersons arbete) avslöjade omedelbart algoritmens sårbarhet - på grund av en minskning av den effektiva nyckellängden (nollning av 10 bitar) sjönk komplexiteten till 2 45 (med 6 storleksordningar på en gång ). Andersons attack är baserad på antagandet om den initiala fyllningen av korta register och på resultatet för att erhålla fyllningen av den tredje.

1997 publicerade Jovan Golic resultaten av A5-analysen. Han föreslog ett sätt att bestämma den initiala fyllningen av register från ett känt segment av gamma, endast 64 bitar långt. Detta segment erhålls från nollmeddelanden. Attacken har en genomsnittlig svårighetsgrad på 2 40 .

1999 visade Wagner och Goldberg lätt att det, för att öppna systemet, räcker att bestämma den initiala fyllningen R4 genom uppräkning. Kontroll utförs på bekostnad av noll ramar. Komplexiteten i denna attack är 2 17 , så det tar några sekunder att bryta chifferet på en modern dator.

I december 1999 publicerade en grupp israeliska forskare ( Adi Shamir , Alex Biryukov , och senare amerikanen Wagner mycket icke-trivial, men teoretiskt mycket effektiv metod för att öppna A5/1:

Detta är en mycket komplex idé, en som vi attackerar på många fronter för att samla några små fördelar, men tillsammans gör de stor skillnad.Adi Shamir

Anteckningar

  1. ↑ Anderson, Ross A5 - GSM Encryption Algorithm  (eng.) (txt)  (länk ej tillgänglig) . sci.crypt (7 juni 1994). Hämtad 24 november 2009. Arkiverad från originalet 21 september 2011.
  2. ↑ Quirke, Jeremy Säkerhet i GSM-systemet (länk ej tillgänglig) . AusMobile (1 maj 2004). Arkiverad från originalet den 12 juli 2004. 
  3. ↑ Preneel, Bart Snabb mjukvarukryptering  ( google book) (december 1994). — (sidan 26). Hämtad: 24 november 2009.

Länkar


 Symmetriska kryptosystem
Streama chiffer
Feistel nätverk
SP nätverk
Övrig