IF Notes

SHA-3 Keccak dan Konstruksi Spons

6 min read

Back to IF4020 Kriptografi

SHA-3 Keccak dan Konstruksi Spons

Questions/Cues

  • Mengapa NIST mengadakan kompetisi SHA-3 dan siapa pemenangnya?
  • Apa yang membedakan Keccak dari finalis lain (konstruksi spons)?
  • Apa arti (bitrate), (capacity), dan ?
  • Bagaimana fase absorbing dan squeezing bekerja?
  • Langkah apa saja pada fungsi permutasi Keccak-f?

Reference Points

  • IF4020 Kriptografi — Beberapa Fungsi Hash (Slides 40-61)

Latar Belakang dan Kompetisi

Seperti sejarah AES, NIST menyelenggarakan kompetisi terbuka untuk fungsi hash baru bernama SHA-3, sebagai pelengkap SHA-1 dan SHA-2. Kompetisi diumumkan pada 2007 dan berakhir Oktober 2012.

TahapJumlah
Submission64 rancangan
Putaran pertama (penyisihan)51
Putaran kedua (semi final)14
Final5 finalis

Lima finalis:

  • BLAKE (digest 224/256/384/512; 14 atau 16 putaran),
  • Grøstl (256/512),
  • JH (224/256/384/512; Hongjun Wu),
  • Keccak (digest sembarang; Bertoni, Daemen, Peeters, Van Assche) dan
  • Skein (digest sembarang; Schneier dkk.; 72 atau 80 putaran).

Pemenang: Keccak, terpilih sebagai SHA-3. Nama “Keccak” berasal dari Kecak, tari dari Bali.

Konstruksi Spons (Sponge)

Berbeda dari finalis lain yang bertumpu pada fungsi kompresi (Merkle-Damgård, SHA-1 dan Konstruksi Merkle-Damgard), Keccak memakai konstruksi spons dengan fungsi permutasi (bukan kompresi) yang “menyerap” masukan lalu “memeras” digest. NIST menilai pendekatan yang berbeda justru lebih baik.

Parameter:

  • = panjang digest yang diinginkan (bit); = bitrate, ukuran blok masukan/keluaran per iterasi.
  • = capacity, bagian state yang tidak dipakai langsung untuk absorb/squeeze dan menentukan keamanan (makin besar makin tinggi ketahanan).
  • = ukuran total state .

SHA3-256: bit (136 byte), bit (64 byte), bit.

Praproses: pesan di-padding menjadi yang panjangnya kelipatan ; dipecah menjadi blok berukuran bit; state (sebesar bit) diisi nol.

Fase penyerapan (absorbing): untuk tiap blok , XOR-kan dengan bit pertama , lalu seluruh ( bit) dimasukkan ke permutasi menghasilkan baru. Setelah semua blok diproses, beralih ke fase pemerasan.

Fase pemerasan (squeezing): diinisialisasi kosong. Selama : sambungkan bit pertama ke ; bila masih , jalankan .

Catatan keamanan: bit terakhir state tidak pernah dipengaruhi langsung oleh blok masukan dan tidak pernah keluar saat pemerasan, sehingga mencegah kolisi.

flowchart TD
    subgraph ABS["Absorbing"]
        direction LR
        S0["S = 0<br/>(r+c bit)"] --> X1["XOR P1<br/>(ke r bit)"] --> F1["f"]
        F1 --> X2["XOR P2"] --> F2["f"]
    end
    subgraph SQZ["Squeezing"]
        direction LR
        Z1["ambil r bit<br/>→ Z"] --> G1["f"] --> Z2["ambil r bit<br/>→ Z"]
    end
    F2 --> Z1

Fungsi Permutasi Keccak-f

Keccak-f menjalankan sejumlah putaran Round, masing-masing lima langkah pada state (matriks dari word):

LangkahOperasi
; ;
rotasi tiap word dengan offset berbeda, lalu permutasi posisi:
(satu-satunya langkah non-linear)
(konstanta putaran)

Pseudocode Keccak (slide 58-59):

Keccak[r,c](Mbytes || Mbits) {
  # Padding
  d = 2^|Mbits| + sum for i=0..|Mbits|-1 of 2^i * Mbits[i]
  P = Mbytes || d || 0x00 || ... || 0x00
  P = P xor (0x00 || ... || 0x00 || 0x80)

  # Initialization
  S[x,y] = 0, for (x,y) in (0..4, 0..4)

  # Absorbing phase
  for each block Pi in P
    S[x,y] = S[x,y] xor Pi[x+5*y], for (x,y) such that x+5*y < r/w
    S = Keccak-f[r+c](S)

  # Squeezing phase
  Z = empty string
  while output is requested
    Z = Z || S[x,y], for (x,y) such that x+5*y < r/w
    S = Keccak-f[r+c](S)
  return Z
}

Keccak-f[b](A) {
  for i in 0..n-1: A = Round[b](A, RC[i])
  return A
}

Round[b](A, RC) {
  # theta
  C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4]
  D[x] = C[x-1] xor rot(C[x+1], 1)
  A[x,y] = A[x,y] xor D[x]
  # rho and pi
  B[y, 2*x+3*y] = rot(A[x,y], r[x,y])
  # chi
  A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y])
  # iota
  A[0,0] = A[0,0] xor RC
  return A
}

Keterangan: adalah ukuran satu lane (word) state; state bit disusun sebagai matriks lane (untuk , ). Padding menambahkan bit penanda d, nol, lalu mengatur bit tertinggi blok terakhir menjadi 0x80; sumber: keccak.team/keccak_specs_summary.html.

Pada demo daring (emn178.github.io/online-tools/keccak_256.html) tersedia pula SHA3-224/256/384/512, Keccak-224/256/384/512, SHA-512/224, dan SHA-512/256.

Contoh digest Keccak-256: keccak256("halo") = 51e5ddea...16d836; keccak256("halu") = beccbf92...59d144 (satu huruf berbeda, digest sama sekali berbeda).

Summary

SHA-3 dipilih NIST lewat kompetisi terbuka (2007-Oktober 2012; 64 submission 51 14 5 finalis BLAKE, Grøstl, JH, Keccak, Skein) dan dimenangkan oleh Keccak (Bertoni, Daemen, Peeters, Van Assche; nama dari tari Kecak). Keccak memakai konstruksi spons: state bit (bitrate , capacity ; SHA3-256: , , ). Pada fase absorbing, tiap blok di-XOR ke bit pertama state lalu di-permutasi dengan ; pada fase squeezing, bit pertama state diambil ke digest dan state dipermutasi lagi sampai panjang terpenuhi. bit tidak pernah menyentuh masukan/keluaran, sehingga menjaga keamanan. Permutasi Keccak-f memakai langkah .

Graph View

Backlinks