Jurnal Matematika Vol. 6 No. 2, Desember 2016. ISSN: 1693-1394

Distribusi Difference dari S-Box Berbasis Fungsi Balikan Pada GF(28)

Andriani Adi Lestari Lembaga Sandi Negara e-mail: aaltari@gmail.com

Nunik Yulianingsih Lembaga Sandi Negara e-mail: nunik.yulianingsih@lemsaneg.go.id

Abstract: Substitution-box (s-box) is a basic component of block cipher which performs a substitution. Two powerful cryptanalysis techniques applied to block ciphers are linear cryptanalysis and differential cryptanalysis. The resistance against differential cryptanalysis can be achieved by eliminating high-probability differential trails. We should choose an s-box where the maximum difference propagation probability is as small as possible to eliminating high-probability differential trails. Nyberg proposed a method to construct the n×s s-box by using the inverse mapping on a finite field GF(2n~) then implements affine transformations on FF(2~) . In this study, we generate 47.104 8 ×8 s-box according to Nyberg. The experimental results showed that s-boxes have the maximum difference propagation probability — — 2~ 6 with the same frequency.

Keywords: block cipher, difference distribution table, finite field, substitution-box keyword.

  • 1.    Pendahuluan

Block cipher adalah skema enkripsi atau dekripsi yang memproses blok plaintext menjadi blok ciphertext dengan ukuran yang sama [1]. Pada umumnya block cipher mengkombinasikan fungsi sederhana seperti substitusi dan permutasi. Substitution-box (s-box) merupakan salah satu komponen dasar pada block cipher yang digunakan untuk melakukan substitusi dan berfungsi untuk menyembunyikan hubungan antara kunci dengan ciphertext.

Suatu algoritma dikatakan aman jika tidak dapat diserang dengan serangan yang sudah diketahui [2]. Serangan yang umumnya dapat diterapkan pada block cipher yaitu linear cryptanalysis, differential cryptanalysis, dan related-key attack. Differential cryptanalysis adalah sebuah metode yang menganalisis pengaruh dari suatu nilai difference dalam pasangan-pasangan plaintext terhadap nilai difference pasangan-pasangan ciphertext yang dihasilkan [3]. Differential cryptanalysis dilakukan dengan mencari differential trail dengan peluang yang tinggi untuk melakukan ekstraksi kunci. Salah satu mekanisme untuk mengeliminasi differential trail dengan peluang yang

tinggi adalah memilih s-box yang memiliki peluang maksimum difference sekecil mungkin. Mekanisme tersebut memberikan kriteria yang jelas dalam memilih s-box.

Salah satu metode untuk mengkonstruksi s-box berukuran n× n adalah metode yang diajukan oleh Nyberg [4], yaitu membangkitkan s-box dengan menggunakan pemetaan f(x) = x ~ 1 pada finite field ( G F(2nff Pada makalah ini akan dibangkitkan s-box berukuran 8 × 8 pada finite field GF(28) menggunakan metode Nyberg. Penelitian ini bertujuan untuk mengetahui apakah s-box yang dibangkitkan menggunakan metode Nyberg memiliki peluang maksimum difference sekecil mungkin berdasarkan distribusi difference-nya.

  • 2.    Data dan Metode

Pada bagian ini dijelaskan mengenai metode pembangkitan s-box, difference distribution table dan tahapan penelitian. Tahapan penelitian meliputi teknik pengambilan sampel, banyaknya sampel yang digunakan, analisis data.

  • 1)    Metode Pembangkitan S-box

Sebuah s-box berukuran × adalah sebuah fungsi pemetaan yang dinotasikan dengan S:{0,1}n →{0,1}m . S-box S akan mentransformasi input berukuran n bit menjadi output berukuran m bit dengan m tidak harus sama dengan n b Block cipher umumnya menggunakan s-box yang tetap, seperti pada Data Encryption Standard (DES) [5] dan Advanced Encryption Standard (AES) [6]. Namun terdapat block cipher yang menggunakan s-box yang dibangkitkan secara dinamis berdasarkan kunci, seperti pada Twofish [7].

Banyak metode yang dapat diterapkan untuk membangkitkan sebuah s-box tetap. Salah satu metode untuk mengkonstruksi s-box tetap berukuran × dengan peluang maksimum difference = = 22 ~n adalah metode yang diajukan oleh Nyberg [4], yaitu membangkitkan s-box dengan menggunakan pemetaan [(x) = X ~ 1 pada finite field ( GF(2nff Pemetaan tersebut masih menghasilkan nilai input dan output yang tetap pada s-box (fixed point) yaitu pada input 0 dan 1. Untuk mengatasi hal tersebut maka perlu diimplementasikan transformasi affine pada GF(2f yaitu

y = A∙ x + b (1)

p, 1

Γ a00

aOl

a02

⎡yι ⎤

⎡a10

all

a12

⎢ y2

a20

a21

a22

⎢ y, ⎥

=

⎢ α30

a31

a32

⎢ y4 ⎥

⎢ ““

a41

a42

⎢ y5

⎢ α⅛o

a51

a52

⎢ y6 ⎥

⎢ α60

⅝1

a62

⎣   ⎦

⎣a70

α71

a72


aO3

<⅞4

aO5

α06

⅝7 1

rXo 1

⎡ ⅛1

a13

a14

a15

a16

¾7

X1

⎢ bi

a23

a24

a25

a26

a27

⎥

⎢ χ2

⎥ ⎥

^2

a33

a34

a35

a36

α37

⎢ X3

⎥+

⎢ b3 ⎥

a43

Q44

a45

a46

≈47

⎥

⎢ Xt

⎢ b4 ⎥

a53

a54

a55

a56

a57

⎥

X5

⎥

⎢ b5 ⎥

a63

a64

α65

a66

a67

⎥

⎢ X6

⎥

⎢ ⅛ ⎥

a73

a74

a75

a76

a77⎦

⎣ X7 ⎦

⎣   ⎦

Tabel 1. S-box pada Algoritma AES


S-box pada algoritma AES (Tabel 1) merupakan s-box 8×8 dibangkitkan berdasarkan metode Nyberg, yaitu :

• Hitung invers perkalian pada GF (2 8)=GF(2)[x]/(x8 + X4 + X3 +X+1) dengan elemen {00} dipetakan ke dirinya sendiri.

• Kemudian lakukan transformasi affine (pada GF (2))


P,"l ⎡ yι ⎤

y2

⎢ y3

⎢ yt ⎥

⎢ ^5 ⎥ ⎢ y6 ⎥

⎣ ⎦


10 ⎢⎡11 11 ⎢1 1 ⎢1 1 ⎢0 1 ⎢0 0 ⎣0 0


00

00

10

11

11

11

11

01


11

01

00

00

10

11

11

11


1

1

1 0

0

0

1

1


1πχoι


1

1

1 0

0

0


Xi

X2 x3 x4 x5 x6


+


1⎦⎣  ⎦


⎡1⎤

⎢0⎥

⎢0⎥

⎢0⎥

⎢⎢11⎥⎥

⎣0⎦


Parameter dalam mengkonstruksi s-box 8×8 dengan metode Nyberg adalah polinomial irredusibel m(x) berderajat 8 yang digunakan untuk mendefinisikan GF (2 8), matriks biner Aberdimensi 8×8 dan vektor binerbberdimensi 8×1 untuk membentuk fungsi affine. Banyaknya polinomial irredusibel m(x) berderajat 8 adalah 30 polinomial, yaitu 11b, 11d, 12b, 12d, 139, 13f, 14d, 15f 163, 165, 169, 171, 177, 17b, 187, 18b, 18d, 19f, 1a3, 1a9, 1b1, 1bd, 1c3, 1cf, 1d7, 1dd, 1e7, 1f3, 1f5, 1f9 (polinomial disajikan dalam representasi hexadesimal, misal 11b merupakan representasi hexadesimal dari X8 + X4 + X3 + X1+1 ). Banyaknya matriks biner A berdimensi 8×8 yang memiliki invers adalah ((28 - 1)(28 - 2)(28 -22)…(28-27))=262 . 21 dan banyaknya kemungkinan dari vektor biner b adalah 2 8 . Oleh karena itu, banyaknya kemungkinan s-box yang dapat dibentuk berdasarkan metode ini adalah 30∙262 . 21∙28 =275 . 12 .

  • 2)    Difference Distribution Table

S-box sebagai komponen yang melakukan substitusi pada block cipher merupakan fungsi non linear. Oleh karena itu, jika XOR dari pasangan input (input difference) diketahui maka tidak dapat diketahui dengan pasti XOR dari pasangan output (output difference). Untuk suatu nilai input difference memungkinkan beberapa nilai output difference namun tidak semua nilai output difference muncul. Tabel yang menunjukkan distribusi dari input difference dan output difference untuk semua pasangan yang mungkin dari s-box disebut tabel XOR atau Difference Distribution Table (DDT) [3]. Misal X adalah input dari s-box S berukuran n×n dan Δx adalah input difference dengan x ,∆x∈ ^2 .S(x) adalah output dari s-box S dengan input x,S(x⨁∆X) adalah output dari s-box S dengan input x⨁∆X, dan ∆ y adalah output difference. DDT untuk input difference ∆X dan output difference ∆ y adalah

DDT[∆x,∆y]=#{x|s(x⨁∆X)⨁S(X)=∆y}.           (2)

Peluang maksimum difference dinotasikan dengan δ yaitu rasio antara nilai DDT maksimum dengan 2 n , atau

δ = maxΔ X,∆y{DDT [∆x,∆y]}∙2 n .                  (3)

Untuk n genap maka peluang maksimum difference terkecil adalah 2 2-n [8]. Sampai saat ini, s-box dengan peluang maksimum difference adalah 2 1-n untuk n genap masih menjadi permasalahan terbuka.

  • 3)    Tahapan Penelitian

Data pada makalah ini adalah s-box 8×8. S-box tersebut dibangkitkan sesuai dengan metode Nyberg. Karena keterbatasan waktu dan sumber daya maka penelitian dilakukan dengan mengambil sampel s-box 8×8 dan tidak dilakukan pada populasi s-box 8×8 yang dapat dikonstruksi menggunakan metode Nyberg. Parameter yang digunakan adalah 8 polinomial irredusibel m(x) berderajat 8, 23 matriks biner A , dan 256 vektor biner b (semua kemungkinan vektor biner b ). Banyaknya sampel s-box 8×8 pada penelitian ini adalah 8×23×256=47.104 s-box. Setiap s-box tersebut dihitung DDT-nya sesuai dengan (2) dan diamati nilai δ beserta frekuensi terjadinya nilai δ. Simulasi pembangkitan s-box dan perhitungan DDT dilakukan menggunakan bahasa pemrograman C, sedangkan pembangkitan matriks biner A yang memiliki balikan dilakukan menggunakan Maple.

  • 3.    Hasil dan Pembahasan

Berdasarkan hasil eksperimen diperoleh bahwa nilai-nilai yang muncul pada tabel DDT dari 47.104 s-box 8×8 adalah 0, 2, dan 4. Setiap nilai DDT muncul dengan frekuensi yang sama pada semua s-box. Tabel 2 menunjukkan frekuensi nilai DDT dari setiap s-box.

Tabel 2. Frekuensi Nilai DDT

Nilai DDT

Frekuensi

0

32640

2

32130

4

255

Sumber: data primer (2016)

Berdasarkan tabel tersebut dapat diketahui bahwa nilai DDT maksimum dari setiap s-box adalah 4. Karena nilai maksimum DDT dari setiap s-box adalah 4, maka peluang maksimum difference-nya adalah δ=4∙2 8 =2 6 . Peluang maksimum difference terkecil yang diketahui untuk n=8 adalah 22-n=22-8 =26 . Oleh karena itu, s-box yang dibangkitkan berdasarkan metode Nyberg memiliki peluang maksimum difference terkecil.

Pada setiap s-box terdapat 255 pasangan (∆X,∆y ) yang memiliki 4 solusi untuk S(X⨁∆X)⨁S(X)=∆y (dengan kata lain terdapat 4 nilai X∈ %2 yang memenuhi S(X⨁∆X)⨁S(X)=∆y ) . Hasil eksperimen tersebut sesuai dengan proposisi yang diajukan oleh Nyberg [4], yaitu pada pemetaan balikan #{X|S(X⨁∆X)⨁S(X)=∆y}≤ 4 dengan penjelasan sebagai berikut :

Jika S(%) = x 1 pada GF(28 ) dan operasi © merupakan operasi + pada GF(28 ) maka S(xθ∆x)θS(%) = ∆y dapat dituliskan sebagai

(x + ∆%)^ 1+x- 1 = ∆y(4)

Untuk % ≠ 0 dan x ≠ ∆x , maka Pers. (4) akan ekivalen dengan

∆y ∙ X2 + ∆x ∙ ∆y ∙ x + ∆x = 0(5)

yang memiliki paling banyak dua solusi pada GF(28). Jika antara x = 0 atau x = ∆x adalah solusi untuk (4), maka keduanya adalah solusi dan ∆y = ∆x “1. Dalam kasus tersebut (5) ekivalen dengan

x2 + ∆x ∙ x + (∆x)2 = 0(6)

yang memberikan dua solusi tambahan untuk (3).

Penyelesaian (6) pada GF(28)  dilakukan dengan mengkuadratkan (6) dan

mensubtitusikan x2 = ∆x ∙ x + (∆x)2 sehingga diperoleh

x (x 3 + (∆x)3 ) = 0

yang akan memberikan 4 solusi pada GF(28), yaitu x = 0, x = ∆x, x = (∆x)d+1, n 8_

x = (∆x)2 d+1 dengan d = —.

Penggunaan transformasi affine hanya digunakan untuk menghindari adanya pemetaan dengan nilai yang tetap. Transformasi tersebut mengubah nilai ∆y dari fungsi invers dengan peluang satu. Jika adalah input dari transformasi affine yang merupakan invers pada GF(2n), maka output difference ∆y dari transformasi affine untuk input difference ∆ adalah

∆y = (4 ∙ x + b) φ (4 ∙ (x φ ∆x) + b )               (7)

= 4∙xφbφ4∙(xφ∆x)φb

= 4∙xφ4∙(xφ∆x)φbφb

= 4 ∙ x φ 4 ∙ (x φ ∆x)

= 4 ∙ (x φ x φ ∆x)

= 4 ∙ (∆x)

Berdasarkan (7) dapat dilihat bahwa output difference dari transformasi affine adalah hasil perkalian antara matriks 4 dengan input difference. Hal tersebut sesuai dengan hasil eksperimen, yaitu penggunaan transformasi affine yang berbeda tidak mengubah sebaran dari nilai DDT, dengan kata lain transformasi affine tidak mengubah karakteristik differential dari s-box

  • 4.    Simpulan dan Saran

Berdasarkan hasil eksperimen diperoleh bahwa 47.104 s-box 8 × 8 yang dibangkitkan menggunakan metode Nyberg memiliki nilai peluang maksimum deference δ = 2-6 dengan frekuensi 255, sehingga dapat disimpulkan bahwa s-box yang dibangkitkan menggunakan metode Nyberg memiliki peluang maksimum difference terkecil yang mungkin untuk n genap. Penggunaan transformasi affine yang berbeda tidak mengubah sebaran dari nilai DDT.

Daftar Pustaka

  • [1]    W. Stallings, Cryptography and Network Security: Principles and Practices. 2005.

  • [2]    L. R. Knudsen, “Block Ciphers,” in Encyclopedia of Cryptography and Security, H. C. A. van Tilborg and S. Jajodia, Eds. Boston, MA: Springer US, 2011, pp. 152–157.

  • [3]    E. Biham and A. Shamir, “Differential Cryptanalysis of DES-like Cryptosystems,” 1990.

  • [4]   K. Nyberg, “Differentially uniform mappings for cryptography,” Advances in

Cryptology — EUROCRYPT ’93. pp. 55–64, 1994.

  • [5]    H. Feistel, “Data Encryption Standard (DES),” Fips Pub 46-3, vol. 3, 1999.

  • [6]    N. Fips, “197: Announcing the advanced encryption standard (AES),” … Technol. Lab. Natl. Inst. Stand. …, vol. 2009, pp. 8–12, 2001.

  • [7]    B. Schneier, J. Kelsey, D. Whiting, D. Wagner, and C. Hall, “Twofish : A 128-Bit Block Cipher,” NIST AES Propos., vol. 15, no. 1, pp. 1–27, 1998.

  • [8]    T. P. Berger, A. Canteaut, P. Charpin, and Y. Laigle-chapuy, “On Almost Perfect Nonlinear Functions Over Fn,” vol. 52, no. 9, pp. 4160–4170, 2006.

99