RC5: Rivests variable blokchiffer med dataafhængige rotationer

Læs om RC5: Rivests fleksible blokchiffer med variable blokstørrelser, nøgler og dataafhængige rotationer — enkel design, stor betydning for kryptoanalyse.

Kryptografi-algoritmen RC5 en er et simpelt, men fleksibelt blokchiffer med symmetrisk nøgle, udviklet af Ronald Rivest i 1994 og er en parameteriseret algoritme. RC5 tillader variabel blokstørrelse, variable nøglestørrelser og et varierende antal runder, hvilket gør det muligt at afbalancere sikkerhed og ydeevne til forskellige anvendelser. "RC" står for "Rivest Cipher" (eller populært "Rons kode").

Parametre og notationskonvention

RC5 beskrives ofte med notationen RC5-w/r/b, hvor:

• w er ordstørrelsen i bit (typisk 16, 32 eller 64). Blokkens størrelse er 2w (dvs. to ord).
• r er antallet af runder (0–255).
• b er nøglens længde i bytes (0–255 bytes svarende til op til 2040 bit).

Eksempel: RC5-32/12/16 betyder ordstørrelse 32 bit, 12 runder og en 16-byte (128 bit) nøgle. I det oprindelige forslag var standardparametrene blokstørrelse 64 bit (dvs. w = 32), en 128-bit nøgle og 12 runder.

Grundlæggende operationer

De primære operationer i RC5 er:

• modulær addition (ord-størrelse, dvs. addition modulo 2^w),
• eXclusive OR (Xor), og
rotationer — rotation med et antal bit bestemt af data (en anden ordværdi mod w).

Disse få primitive operationer gør implementeringen både kompakt og hurtig på processorer med rotationsinstruktioner.

Kryptering og dekryptering (skitse)

RC5 er struktureret som et Feistel-lignende netværk med to w-bit ord A og B i hver blok. En forenklet skitse af krypteringsflowet (for r runder) ser således ud:

• Start: A = A + S[0], B = B + S[1]
• For i = 1 til r:
  • A = ((A xor B) <<< (B mod w)) + S[2*i]
  • B = ((B xor A) <<< (A mod w)) + S[2*i + 1]

Dekryptering udføres ved at invertere disse trin i omvendt rækkefølge (subtraktion i stedet for addition og højrerotation i stedet for venstrerotation), og rutinerne kan implementeres meget kompakt i kode.

Nøgleskemaet

Nøgleskemaet udvider den originale nøgle til en intern tabel S med t = 2(r + 1) w-bit ord. Udvidelsen starter med to "nothing up my sleeve numbers" (konstanter Pw og Qw), som er baseret på de binære udvidelser af både tallet e og det gyldne snit. Herefter blandes nøglematerialet og S-tabellen i en række iterationer (typisk 3·max(t, c) trin, hvor c er antallet af ord i den originale nøgle), hvilket sikrer at S afhænger af hele nøglen.

På grund af denne nøgleudvidelse er nøgleskemaet mere komplekst end selve krypteringskernen, men det giver også god diffusion af nøglebits gennem de interne rundeparametre.

Sikkerhed og kryptanalyse

Et af de centrale designmål med RC5 var at undersøge effekten af de dataafhængige rotationer på sikkerheden. Fordi rotationerne afhænger af data, er RC5 modstandsdygtig over for nogle klassiske angrebsteknikker, men den har også tiltrukket sig betydelig interesse fra kryptoanalytikere.

Der findes adskillige kryptanalytiske resultater mod reducerede varianter af RC5. Især er differential- og lineære analyser samt relaterede-nøgle-angreb blevet brugt til at bryde eller svække versioner med færre runder end de anbefalede. Nogle angreb reducerer effektiv sikkerhed for kraftigt nedsatte rundeantal eller under visse nøgle-relaterede modeller, men konventionelle fuldrunde-parametre (fx RC5-32/12/16) anses generelt for at være robuste i mange anvendelsesscenarier. Som altid bør man vælge parametre efter den aktuelle trusselmodel og krav til modstandsdygtighed over for avancerede angreb.

Implementering, ydeevne og anvendelser

RC5 er let at implementere: krypterings- og dekrypteringsrutiner kan ofte skrives i få kodelinjer, og chifferet kører hurtigt på platforme med effektiv understøttelse af rotationer og 32- eller 64-bit ord. Den variable natur af parametrene gør RC5 anvendelig både i ressourcerestrikterede indlejrede systemer (med små ordstørrelser og få runder) og i høj-sikkerhedsopsætninger (større w og flere runder).

RC5 har også historisk betydning: arbejdet med RC5 bidrog til videreudviklingen af designideer i blokchifre, og Rivest brugte nogle af erfaringerne fra RC5 i udviklingen af RC6, som var en kandidat i AES-konkurrencen.

Begrænsninger og overvejelser

Selvom RC5 er fleksibelt, bør man være opmærksom på:

• at visse nøglestørrelser og lave antal runder kan gøre chifferet sårbart for kryptanalytiske angreb,
• at nøgleskemaets styrke er vigtig—dårligt designede nøgler eller brug af relaterede-nøgler kan udnyttes af angribere, og
• at nyere designs og standardiserede algoritmer (fx AES) ofte foretrækkes til nye systemer pga. bred standardisering og aktuel evaluering.

Samlet set er RC5 et pædagogisk og praktisk interessant blokchiffer: det kombinerer enkelhed i kerneoperationerne med forskning i dataafhængige rotationer og tilbyder stor fleksibilitet gennem sine parametre. For kritiske anvendelser bør man følge den aktuelle forskning og overveje veletablerede standarder og anbefalede parametre.

Spørgsmål og svar

Spørgsmål: Hvad er RC5?

Sp: Hvad står "RC" for?

Sp: Hvad er parametrene for RC5?

Spørgsmål: Hvad er algoritmens generelle struktur?

Spørgsmål: Hvor kompleks er nøgleplanen?

Spørgsmål: Hvorfor har RC5 været attraktiv for kryptoanalytikere?

Søg efter bogstav