Serangan Aljabar pada Algoritme S-IDEA dan Miniatur S-IDEA

Authors

  • Nadya Marta Matanggwan BSSN
  • Sa'aadah Sajjana Carita BSSN

DOI:

https://doi.org/10.56706/ik.v15i1.16

Keywords:

serangan aljabar, miniatur S-IDEA, S-IDEA, XL Algorithm

Abstract

Serangan aljabar dapat dilakukan dalam dua tahapan yaitu mendapatkan sistem persamaan polinomial dan menentukan solusi dari sistem persamaan polinomial tersebut. Pada penelitian ini dilakukan serangan aljabar pada S-IDEA. Proses enkripsi satu round S-IDEA terdiri dari 14 langkah sedangkan sampai dengan Langkah ke-7 sudah diperoleh persamaan polinomial yang besar yaitu terdiri dari 4.721 monomial. Oleh karena keterbatasan sumber daya, dibuat miniatur S-IDEA agar serangan aljabar dapat dilakukan pada setiap langkah secara utuh. Algoritme miniatur S-IDEA terdiri dari 2,5 round yang setiap round-nya terdiri dari 14 langkah seperti halnya S-IDEA. Proses serangan aljabar pada miniatur S-IDEA menghasilkan 8 persamaan polinomial dengan monomial maksimal yang diperoleh yaitu sebanyak 1.109 monomial. Penentuan solusi dari persamaan polinomial yang diperoleh dilakukan dengan metode XL algorithm dan basis Gröbner. Metode XL algorithm dilakukan sampai tahap 4 dari 5 tahap, yaitu tahap linierisasi. Tahap linierisasi menghasilkan 136 persamaan yang didalamnya terdapat 1512 monomial. Konstanta dari persamaan linier tersebut dapat direpresentasikan ke dalam bentuk matriks berukuran 1512×136. Besarnya sistem persamaan hasil linierisasi yang diperoleh menyebabkan nilai kunci belum bisa didapatkan secara langsung melainkan harus dilakukan analisis lebih lanjut mengenai persamaan mana saja yang perlu digunakan untuk tahap selanjutnya pada XL algorithm. Sementara itu penentuan solusi dengan basis Gröbner menghasilkan 34 persamaan baru yang cukup panjang, sehingga nilai kunci belum dapat diperoleh secara langsung.

References

M. Voros, Algebraic Attack on Stream Ciphers, Comenius University, Faculty of Mathematics, Physics and Informatics, 2007.

S. Simmons, “Algebraic Cryptanalysis of Simplified AES,” Cryptologia, pp. 305-314, 2009.

B. Preneel, J. Vandewalle dan J. Nakahara, Cryptanalysis and Design of Block cipher, Leuven: Katholieke Universiteit Leuven, 2003.

G. V. Bard dan N. T. Courtois, “Algebraic Cryptanalysis of the Data Encryption Algorithm,” IMA International Conference on Cryptography and Coding, pp. 152-169, 2007.

F. Paradise, Serangan Aljabar pada Simplified Data Encryption Standar (S-DES) dengan metode XL algorithm, Bogor: Sekolah Tinggi Sandi Negara, 2018.

T. Sundari, Serangan Aljabar pada Algoritme Mini-AES, Bogor: Sekolah Tinggi Sandi Negara, 2015.

N. Hoffman, “A Simplified IDEA Algorithm,” Crytplogia, pp. 143-151, 2007.

H. K. Sahu, V. Jadhav, S. Sonavane dan R. K. Sharma, “Cryptanalytic Attacks on International Data Encryption Algorithm Block cipher,” Defence Science Journal, vol. 66, pp. 582-589, 2016.

A. Kipnis dan A. Shamir, “Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization,” Annual International Cryptology Conference, pp. 19-30, 1999.

N. Courtois, A. Klimov, J. Patarin dan A. Shamir, “Efficient Algorithm for Solving Overdefined Systems of Multivariate Polynomial Equations,” EUROCRYPT 2000, pp. 392-407, 2000.

G. V. Bard, Algebraic Cryptanalysis, Springer Science & Bussiness Media, 2009.

B. Buchberger, “Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal,” Symbolic Computation, vol. 41, pp. 475 - 551, 2006.

I. Ajwa, Z. Liu dan P. Wang, Gröbner Bases Algorithm, Ohio: Kent State University, 2003.

Downloads

Submitted

06-04-2021

Accepted

17-05-2021

Published

07-06-2021

Issue

Section

Articles