IF Notes

RC4 dan A5

5 min read

Back to IF4020 Kriptografi

RC4 dan A5

Questions/Cues

  • Bagaimana RC4 membangkitkan keystream (KSA dan PRGA)?
  • Mengapa RC4 kini dianggap tidak aman dan dilarang di TLS?
  • Apa itu A5/1, dan bagaimana tiga LFSR dengan kaidah mayoritas bekerja?
  • Bagaimana A5/1 diinisialisasi dari kunci sesi dan nomor frame?
  • Bagaimana A5/1 dipecahkan?
  • Mengapa A5 tidak aktif di Indonesia?

Reference Points

  • IF4020 Kriptografi — Kriptografi Modern dan Stream Cipher (Slides 40-73)

RC4

Stream cipher paling populer, dibuat Ronald Rivest (1987) di RSA Laboratories (Ron’s Code / Rivest Cipher), namun kini tidak aman. Dipakai di SSL/TLS, WEP (IEEE 802.11), dan WPA.

  • Kunci rahasia panjang maks 256 byte; bila lebih pendek, karakter kunci diulang periodik.
  • Keluaran: keystream berpanjang tak terbatas, dibangkitkan byte demi byte lalu di-XOR dengan byte plainteks.
  • Status internal: larik (permutasi 0-255 yang bergantung kunci) dan dua pencacah indeks , .
  • Dua sub-proses: KSA dan PRGA.

KSA (Key-Scheduling Algorithm):

for i = 0 to 255: S[i] = i
j = 0
for i = 0 to 255:
    j = (j + S[i] + K[i mod Length(K)]) mod 256
    swap(S[i], S[j])

PRGA (Pseudo-Random Generation Algorithm):

i = 0; j = 0
for idx = 0 to Length(P) - 1:
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap(S[i], S[j])
    t = (S[i] + S[j]) mod 256
    u = S[t]              // keystream byte
    c = u XOR P[idx]

Verifikasi: kunci Key dan plainteks Plaintext menghasilkan cipherteks BBF316E8D940AF0AD3 (vektor uji standar).

flowchart TD
    K["Kunci rahasia K"] --> KSA["KSA<br/>acak larik S[0..255]"]
    KSA --> PRGA["PRGA<br/>swap S[i],S[j]; u = S[(S[i]+S[j]) mod 256]"]
    PRGA --> U["Keystream byte u"]
    P["Plainteks byte"] --> X(("XOR"))
    U --> X
    X --> C["Cipherteks byte"]

Keamanan RC4: byte awal keystream berkorelasi tinggi dengan byte awal kunci (karena itu disarankan membuang 256-512 byte pertama); sebagai stream cipher ia tidak tahan flip-bit attack; dipecahkan dalam jam atau hari; sejak Februari 2015 dilarang di TLS (RFC 7465). Varian perbaikan: Spritz, RC4A, VMPC, RC4+.

A5

A5 adalah stream cipher untuk mengenkripsi sinyal percakapan GSM. Frame GSM 228 bit dikirim tiap 4,6 ms; A5 menghasilkan keystream 228 bit yang di-XOR dengan frame. Kunci sesi 64 bit. Dikembangkan Prancis. Dua versi: A5/1 (kuat, Eropa) dan A5/2 (lemah, versi ekspor). A5/1 semula rahasia tetapi terbongkar lewat reverse engineering pada 1994.

Struktur A5/1: tiga LFSR berpanjang 19, 22, 23 bit (total 64). Bit dengan indeks 0 = LSB (paling kanan). Keluaran = XOR ketiga LFSR. Tiap register punya bit kendali detak dan bit umpan balik:

RegisterPanjangBit kendali detakBit umpan balik (taps)
R119bit 813, 16, 17, 18
R222bit 1020, 21
R323bit 107, 20, 21, 22

Kaidah mayoritas (stop/go): tiap putaran, bit kendali ketiga register diperiksa, dicari bit mayoritas; register yang bit kendalinya sama dengan mayoritas didetak. Biasanya 2 atau 3 register didetak; peluang sebuah register didetak = . Saat didetak, bit-bit taps di-XOR dan hasilnya masuk ke LSB (geser ke kiri); bit MSB yang terlempar di-XOR bersama menjadi keluaran.

Pembangkitan keystream:

  1. Semua register di-nol-kan. Selama 64 putaran, tiap bit kunci sesi di-XOR ke LSB tiap register, lalu semua didetak.
  2. Selama 22 putaran, bit nomor frame dicampurkan dengan cara sama.
  3. 100 putaran stop/go (kaidah mayoritas), keluaran dibuang.
  4. 228 putaran stop/go menghasilkan 228 bit keystream untuk mengenkripsi satu frame.

A5/1 ditanam di chip SIM card. Di negara yang melarang operator mengenkripsi percakapan, termasuk Indonesia, A5 dinonaktifkan dan sinyal terkirim sebagai plainteks.

Keamanan A5/1

Tujuan kriptanalisis: menemukan kunci sesi, dengan asumsi penyerang mengetahui keluaran A5/1 pada awal komunikasi (known-plaintext) sehingga sisa percakapan dapat didekripsi. Serangan pertama oleh Ross Anderson (1994): menebak 42 bit isi R1 dan R2 lalu menurunkan 23 bit R3; butuh lebih dari sebulan di PC. Kemudian kunci ditemukan dalam hitungan menit. A5/1 sudah berhasil dikriptanalisis.

Summary

RC4 (Rivest, 1987) membangkitkan keystream byte demi byte dari larik permutasi lewat KSA (mengacak dengan kunci) dan PRGA (swap dan , lalu ). Dulu dipakai di TLS, WEP, WPA, tetapi byte awalnya berkorelasi dengan kunci, rentan flip-bit, dipecahkan dalam jam/hari, dan dilarang di TLS (RFC 7465, 2015). A5/1 mengenkripsi frame GSM 228 bit dengan tiga LFSR (19+22+23 = 64 bit) yang didetak stop/go berkaidah mayoritas; diinisialisasi dari kunci sesi 64 bit dan nomor frame 22 bit, dengan 100 putaran pemanasan. Rahasianya terbongkar 1994 dan diserang known-plaintext (Anderson 1994; kini hitungan menit). Di Indonesia A5 dinonaktifkan sehingga sinyal GSM plainteks. Contoh stream cipher modern yang menggantikannya: Trivium, Salsa20, dan ChaCha20.

Graph View

Backlinks