ANALISIS KINERJA SOLVER DALAM MENYELESAIKAN EKSPRESI BOOLEAN CIPHER S-DES PADA CIPHERTEXT-ONLY-ATTACK
DOI:
https://doi.org/10.52362/jmijayakarta.v6i3.2678Keywords:
boolean expression, brute force, binary decision diagram, sat solver, grobner basisAbstract
Ekspresi Boolean dapat digunakan untuk merepresentasikan hubungan logika antara plaintext, kunci, dan ciphertext pada algoritma kriptografi. Penelitian ini bertujuan mengekstrak ekspresi Boolean dari algoritma Simplified Data Encryption Standard (S-DES) dan mengevaluasi kinerja beberapa metode solving dalam menyelesaikan ekspresi tersebut pada skenario Ciphertext-Only Attack (COA). Ekspresi Boolean diekstrak dari proses enkripsi S-DES untuk merepresentasikan hubungan antara bit plaintext, bit kunci, dan setiap bit ciphertext, kemudian direpresentasikan dalam dua bentuk, yaitu Conjunctive Normal Form (CNF) dan Algebraic Normal Form (ANF). Ekspresi dalam bentuk CNF digunakan sebagai masukan untuk metode Binary Decision Diagram (BDD) dan Boolean Satisfiability (SAT) menggunakan modern SAT solver, sedangkan ekspresi dalam bentuk ANF digunakan untuk metode Brute Force dan Gröbner Basis. Pada skenario COA, ciphertext diketahui dan setiap metode digunakan untuk mencari kombinasi plaintext dan kunci yang memenuhi ekspresi Boolean hasil ekstraksi. Kinerja masing-masing metode dievaluasi berdasarkan waktu komputasi dan keberhasilannya dalam menemukan solusi. Hasil penelitian diharapkan dapat memberikan perbandingan kinerja berbagai metode solving terhadap representasi CNF dan ANF yang diekstrak dari algoritma S-DES.
References
C. Bright, J. Gerhard, I. Kotsireas, and V. Ganesh, “Effective Problem Solving Using SAT Solvers,” Commun. Comput. Inf. Sci., vol. 1125 CCIS, pp. 205–219, 2020, doi: 10.1007/978-3-030-41258-6_15.
H. K. Sahu, I. Gupta, N. R. Pillai, and R. K. Sharma, “BDD-based cryptanalysis of stream cipher: A practical approach,” IET Inf. Secur., vol. 11, no. 3, pp. 159–167, 2017, doi: 10.1049/iet-ifs.2016.0076.
A. D. Dwivedi, M. Klouček, P. Morawiecki, I. Nikolić, J. Pieprzyk, and S. Wójtowicz, “SAT-based cryptanalysis of authenticated ciphers from the CAESAR competition,” ICETE 2017 - Proc. 14th Int. Jt. Conf. E-bus. Telecommun., vol. 4, no. Icete, pp. 237–246, 2017, doi: 10.5220/0006387302370246.
M. Dubois and É. Filiol, “Hacking of the AES with boolean functions,” ICISSP 2017 - Proc. 3rd Int. Conf. Inf. Syst. Secur. Priv., vol. 2017-Janua, no. Icissp, pp. 599–609, 2017, doi: 10.5220/0006091305990609.
A. Soboń, M. Kurkowski, and S. Stachowiak, “Complete SAT based Cryptanalysis of RC5 Cipher,” J. Inf. Organ. Sci., vol. 44, no. 2, pp. 365–382, 2020, doi: 10.31341/jios.44.2.10.
Y. Makwana, A. Panigrahi, and S. K. Pal, “Improved BDD-based Cryptanalysis of Keystream Generators with application to Trivium,” Sadhana - Acad. Proc. Eng. Sci., vol. 51, no. 2, pp. 1–23, 2026, doi: 10.1007/s12046-026-03094-9.
I. Mironov and L. Zhang, “Applications of SAT Solvers to Cryptanalysis of Hash Functions,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 4121 LNCS, pp. 102–115, 2006, doi: 10.1007/11814948_13.
E. Maro, “Modeling of algebraic analysis of PRESENT cipher by SAT solvers,” IOP Conf. Ser. Mater. Sci. Eng., vol. 734, no. 1, 2020, doi: 10.1088/1757-899X/734/1/012101.
S. Stachowiak, M. Kurkowski, and A. Soboń, “SAT-Based Cryptanalysis of Salsa20 Cipher,” in Progress in Image Processing, Pattern Recognition and Communication Systems, 2022, pp. 252–266. doi: 10.1007/978-3-030-81523-3_25.
A. Soboń and S. Stachowiak, “ChaCha20 Cipher Cryptanalysis through SAT Problem Solving,” 2024 IEEE 17th Int. Sci. Conf. Informatics, pp. 355–361, 2024, doi: 10.1109/Informatics62280.2024.10900867.
S. Simmons, “Algebraic Cryptanalysis of Simplified AES,” Cryptologia, vol. 33, no. 4, pp. 305–314, 2009, doi: 10.1080/01611190903185328.
O. Grumberg, S. Livne, and S. Markovitch, “Learning to order BDD variables in verification,” J. Artif. Intell. Res., vol. 18, pp. 83–116, 2003, doi: 10.1613/jair.1096.
L. Xu, F. Hutter, H. H. Hoos, and K. Leyton-Brown, “SATzilla: Portfolio-based Algorithm Selection for SAT,” J. Artif. Intell. Res., vol. 32, pp. 565–606, 2008, doi: 10.1613/jair.2490.
F. Paradise and S. Indarjani, “ALGEBRAIC ATTACK PADA SIMPLIFIED DATA ENCRYPTION STANDARD (S-DES),” in Seminar Nasional Matematika UI, 2017, pp. 726–735.
N. M. Matanggwan and S. S. Carita, “Serangan Aljabar pada Algoritme S-IDEA dan Miniatur S-IDEA,” J. Info Kripto, vol. 15, no. 1, pp. 19–26, 2021, doi: 10.56706/ik.v15i1.16.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Fritz Gamaliel, P. Yudi Dwi Arliyanto
This work is licensed under a Creative Commons Attribution 4.0 International License.
_uk200_pxl.jpg)
_Barcode3.png)
