A5 (krypteringsalgoritme)

A5  er en streaming krypteringsalgoritme , der bruges til at sikre fortroligheden af ​​de data, der transmitteres mellem telefonen og basestationen i det europæiske system for mobil digital kommunikation GSM ( Groupe Spécial Mobile ).

Chifferen er baseret på bitvis addition modulo to (boolesk XOR-operation) af den genererede pseudo-tilfældige sekvens og informationen, der skal krypteres. I A5 implementeres en pseudo-tilfældig sekvens baseret på tre lineære feedback-skiftregistre . Registrene er henholdsvis 19, 22 og 23 bit lange. Skift styres af et specielt kredsløb, der organiserer skiftet af mindst to registre ved hvert trin, hvilket fører til deres ujævne bevægelse. Sekvensen dannes af XOR-operationen på registrenes udgangsbit.

Historie om skabelse og udvikling

Oprindeligt blev en strømchiffer udviklet af franske militærkryptografer til udelukkende at blive brugt til militære formål. I slutningen af ​​80'erne krævede GSM-standarden skabelsen af ​​et nyt, moderne sikkerhedssystem. Det var baseret på tre hemmelige algoritmer: autentificering - A3 , stream-kryptering - A5, generering af sessionsnøgler - A8 . En fransk udvikling blev brugt som A5-algoritmen. Denne chiffer gav en ret god sikkerhedsstrøm og derfor fortroligheden af ​​samtalen. I første omgang forventedes eksporten af ​​standarden fra Europa ikke, men snart opstod behovet. Derfor blev A5 omdøbt til A5/1 og begyndte at blive distribueret både i Europa og i USA. For andre lande (inklusive Rusland) blev algoritmen ændret, hvilket væsentligt sænkede krypteringsstyrken. A5/2 er specielt designet som en eksportmulighed for lande uden for EU. Den kryptografiske styrke af A5/2 blev reduceret ved at tilføje et andet register (17 bit), der styrer skift af resten. I A5/0 er der ingen kryptering overhovedet. Algoritme A5/3, baseret på Kasumi- algoritmen, er også udviklet og godkendt til brug i 3G-netværk. Disse modifikationer kaldes A5/x.

Optræden i det offentlige domæne

Officielt blev denne kryptoordning ikke offentliggjort, og dens struktur blev ikke offentliggjort. Dette skyldtes, at udviklerne stolede på sikkerhed på bekostning af uklarhed , hvilket betyder, at algoritmer er sværere at knække, hvis deres beskrivelser ikke er offentligt tilgængelige. Data blev kun leveret til GSM-operatører, når det var nødvendigt. I 1994 var detaljerne i A5-algoritmen dog kendt: Det britiske telefonselskab British Telecom indsendte al dokumentation vedrørende standarden til University of Bradford til analyse uden at indgå en tavshedspligt . Derudover dukkede materialer om standarden op på en af ​​konferencerne i Kina. Som et resultat blev hans plan gradvist lækket ud i brede kredse. Samme år offentliggjorde videnskabsmændene fra Cambridge Ross Anderson (Ross Anderson) og Michael Roe (Michael Roe) et kryptoskema gendannet fra disse data og vurderede dets kryptografiske styrke [1] . Den endelige algoritme blev præsenteret i Jovan Golic's arbejde på Eurocrypt'97-konferencen.

A5-struktur

Algoritme A5 er i øjeblikket en hel familie af cifre. For beskrivelse, lad os tage A5/1 som stamfader til denne familie. Ændringer i afledte algoritmer vil blive beskrevet separat.

Strømkryptering

I denne algoritme svarer hvert almindeligt teksttegn til et chifferteksttegn. Tekst er ikke opdelt i blokke (som i blokchiffer ) og ændres ikke i størrelse. For at forenkle hardwareimplementeringen og derfor øge ydeevnen, bruges kun de enkleste operationer: modulo 2 addition (XOR) og registerskift.

Outputsekvensen dannes ved at tilføje kildetekststrømmen til den genererede sekvens (gamma). Det ejendommelige ved XOR-operationen er, at den anvendes et lige antal gange, fører til startværdien. Derfor afkodes meddelelsen ved at tilføje chifferteksten til en kendt sekvens.

Systemets sikkerhed afhænger således helt af sekvensens egenskaber. Ideelt set er hver bit af gamma en uafhængig tilfældig variabel, og selve sekvensen er tilfældig. En sådan ordning blev opfundet af Vernam i 1917 og opkaldt efter ham. Som Claude Shannon beviste i 1949, giver dette absolut sikkerhed. Men brugen af ​​en tilfældig sekvens betyder transmission over en sikker kanal af en meddelelse, der i volumen svarer til almindelig tekst, hvilket komplicerer opgaven meget og praktisk talt ikke bruges nogen steder.

I rigtige systemer skabes en nøgle af en given størrelse, som nemt transmitteres over en privat kanal. Sekvensen genereres baseret på den og er pseudo-tilfældig. En stor klasse af stream-cifre (inklusive A5) er chiffer, hvis pseudo-tilfældige sekvensgenerator er baseret på lineære feedback-skifteregistre.

RSLOS

Et lineært feedbackskifteregister består af selve registret (en sekvens af bits af en given længde) og feedback. På hver cyklus sker følgende handlinger: biten længst til venstre (højeste bit) udtrækkes, sekvensen flyttes til venstre, og værdien af ​​feedbackfunktionen skrives til den tomme højre celle (mindst signifikant bit). Denne funktion er modulo to-summen af ​​visse bit i registret og skrives som et polynomium, hvor eksponenten angiver bittallet. De udtrukne bits danner outputsekvensen.

For LFSR er hovedindikatoren perioden for den pseudo-tilfældige sekvens. Det vil være maksimum (og lig med 2 n − 1), hvis tilbagekoblingspolynomiet er primitivt modulo 2 . Udgangssekvensen kaldes i dette tilfælde en M-sekvens.

LFSR-system i A5

LFSR egner sig let til krypteringsanalyse og er ikke stærk nok til at blive brugt til kryptering. Praktiske anvendelser er systemer med variable urregistre med forskellige længder og feedbackfunktioner.

Strukturen af ​​A5-algoritmen er som følger:

  • Tre registre (R1, R2, R3) har længder på 19, 22 og 23 bit,
  • Feedback polynomier:
    • X 19 + X 18 + X 17 + X 14 + 1 for R1,
    • X 22 + X 21 + 1 for R2 og
    • X 23 + X 22 + X 21 + X 8 + 1 for R3,
  • Uret styres af en speciel mekanisme:
    • hvert register har synkroniseringsbits: 8 (R1), 10 (R2), 10 (R3),
    • funktionen F = x&y|x&z|y&z beregnes, hvor & er boolsk OG, | - boolesk OR, og x, y og z er henholdsvis synkroniseringsbit R1, R2 og R3,
    • kun de registre, der har synkroniseringsbitten lig med F, forskydes,
    • faktisk er de registre, hvis synkroniseringsbit tilhører majoriteten, forskudt,
  • Systemets outputbit er resultatet af XOR-operationen på registrenes outputbit.

A5-algoritmens funktion

Lad os overveje funktionerne i algoritmens funktion baseret på det kendte skema. Datatransmission udføres i en struktureret form - opdelt i rammer (114 bit). Før initialisering nulstilles registrene, sessionsnøglen (K - 64 bit) dannet af A8, og rammenummeret (Fn - 22 bit) indlæses til algoritmen . Dernæst udføres følgende trin sekventielt:

  • Initialisering:
    • 64 cyklusser, hvor den næste bit af nøglen XORed med den mindst signifikante bit af hvert register, mens registrene forskydes på hver cyklus,
    • svarende til 22 cyklusser, udføres kun XOR-operationen med rammenummeret,
    • 100 cyklusser med registerskiftkontrol, men ingen sekvensgenerering,
  • 228 (114 + 114) cyklusser arbejder, den transmitterede ramme er krypteret (de første 114 bit), og den modtagne ramme er dekrypteret (de sidste 114 bit),
  • yderligere initialisering udføres på ny, et nyt billednummer bruges.

Forskelle i afledte algoritmer A5/x

Et andet 17-bit register (R4) er blevet tilføjet til A5/2 algoritmen , som styrer restens bevægelse. Strukturændringerne er som følger:

  • tilføjet register R4 med en længde på 17 bit,
  • feedback polynomium for R4: ,
  • clocking styres af R4:
    • R4 har synkroniseringsbit 3, 7, 10,
    • majoritetsfunktionen beregnes F = x&y|x&z|y&z (lig med majoriteten), hvor & er boolsk OG, | - boolesk OR, og x, y og z er henholdsvis synkroniseringsbit R4(3), R4(7) og R4(10),
    • R1 forskydes hvis R4(10) = F,
    • R2 forskydes hvis R4(3) = F,
    • R3 forskydes hvis R4(7) = F,
  • systemets outputbit er resultatet af XOR-operationen på de høje bits af registrene og majoritetsfunktioner fra visse bits af registrene:
    • R1 - 12, 14, 15,
    • R2 - 9, 13, 16,
    • R3 - 13, 16, 18.

Ændringer i funktion er ikke så væsentlige og vedrører kun initialisering:

  • 64+22 cyklusser er fyldt med sessionsnøgle og rammenummer også R4,
  • 1 cyklus R4(3), R4(7) og R4(10) er fyldt med 1,
  • 99 cyklusser med registerskiftkontrol, men ingen sekvensgenerering.

Det kan ses, at initialisering tager samme tid (100 cyklusser uden generering er opdelt i to dele).

Algoritme A5/3 blev udviklet i 2001 og skulle erstatte A5/1 i tredje generation af mobilsystemer. Det kaldes også Kasumi- algoritmen . Da det blev oprettet, blev Mitsubishi Corporations MISTY -chiffer taget som grundlag. A5/3 anses i øjeblikket for at give den nødvendige modstand.

Algoritme A5/0 indeholder ingen kryptering.

Sikkerhed

Udviklingen af ​​GSM-standarden betød en kraftig krypteringsmaskine, der ikke kunne hackes (især i realtid). Den anvendte udvikling, med korrekt implementering, gav højkvalitetskryptering af de transmitterede data. Det er den slags information, der kan fås fra virksomheder, der distribuerer denne standard. Men det er værd at bemærke en vigtig nuance: at lytte til samtaler er en integreret egenskab, der bruges af særlige tjenester. De var interesserede i muligheden for aflytning til deres egne formål. Der blev således foretaget ændringer i algoritmen, som gjorde det muligt at knække på en acceptabel tid. Derudover blev A5 modificeret til eksport til A5/2. MoU (Memorandum of Understand Group Special Mobile standard) anerkender, at formålet med at udvikle A5/2 var at reducere krypteringens kryptografiske styrke, men de officielle testresultater siger, at der ikke er nogen kendte mangler ved algoritmen [2] .


Kendte sårbarheder

Med fremkomsten af ​​data på A5-standarden begyndte forsøg på at knække algoritmen samt at søge efter sårbarheder. En stor rolle blev spillet af standardens funktioner, som kraftigt svækker beskyttelsen, nemlig:

  • 10 bits af nøglen tvinges til nul,
  • mangel på krydsforbindelser mellem registre (undtagen skiftkontrol),
  • kryptering af serviceinformation kendt af kryptoanalytikeren,
  • mere end 40 % af nøglerne fører til minimumslængden af ​​perioden for den genererede sekvens, nemlig [3]
  • i begyndelsen af ​​sessionen udveksles null-meddelelser (en ramme ad gangen),
  • samme polstring for alle pakker,
  • i A5/2 udføres bevægelsen af ​​et separat register på 17 bit.

Baseret på disse "huller" i algoritmen opbygges hacking-skemaer.

Bemærkelsesværdige angreb

Nøglen er en 64-bit sessionsnøgle, rammenummeret antages at være kendt. Således er kompleksiteten af ​​et brute-force angreb 2 64 .

De første anmeldelser af chifferen (værket af Ross Anderson) afslørede straks algoritmens sårbarhed - på grund af et fald i den effektive nøglelængde (nulstilling af 10 bits) faldt kompleksiteten til 2 45 (med 6 størrelsesordener på én gang ). Andersons angreb er baseret på antagelsen om den indledende udfyldning af korte registre og på outputtet for at opnå udfyldningen af ​​den tredje.

I 1997 offentliggjorde Jovan Golic resultaterne af A5-analysen. Han foreslog en måde at bestemme den indledende fyldning af registre fra et kendt segment af gamma, kun 64 bit langt. Dette segment er opnået fra nul-meddelelser. Angrebet har en gennemsnitlig sværhedsgrad på 2 40 .

I 1999 demonstrerede Wagner og Goldberg let, at for at åbne systemet er det tilstrækkeligt at bestemme den indledende fyldning R4 ved opregning. Kontrol udføres på bekostning af nul rammer. Kompleksiteten af ​​dette angreb er 2 17 , så det tager et par sekunder at bryde chifferen på en moderne computer.

I december 1999 udgav en gruppe israelske videnskabsmænd ( Adi Shamir , Alex Biryukov og senere amerikaneren Wagner meget ikke-triviel, men teoretisk meget effektiv metode til at åbne A5/1:

Dette er en meget kompleks idé, som vi angriber på mange fronter for at akkumulere et par små fordele, men tilsammen gør de en stor forskel.Adi Shamir

Noter

  1. ↑ Anderson, Ross A5 - The GSM Encryption Algorithm  (eng.) (txt)  (link ikke tilgængeligt) . sci.crypt (7. juni 1994). Hentet 24. november 2009. Arkiveret fra originalen 21. september 2011.
  2. ↑ Quirke, Jeremy Sikkerhed i GSM-systemet (link utilgængeligt) . AusMobile (1. maj 2004). Arkiveret fra originalen den 12. juli 2004. 
  3. ↑ Preneel, Bart Fast softwarekryptering  ( google bog) (december 1994). — (side 26). Hentet: 24. november 2009.

Links


 Symmetriske kryptosystemer
Stream-cifre
Feistel netværk
SP netværk
Andet