PEMBUATAN COUNTEREXAMPLE PADA ALGORITMA PENGUJIAN KEAMANAN PROTOKOL PING-PONG

ERWIN EKO WAHYUDI, Dr.-Ing. Mhd. Reza M. I. Pulungan, M.Sc.

2016 | Skripsi | S1 ILMU KOMPUTER

Penggunaan protokol pengiriman pesan yang "kurang benar" akan rentan terhadap serangan aktif terhadap jaringan. Suatu protokol pengiriman pesan dikatakan aman jika seorang penyabot Z tidak bisa memperoleh pesan asli M yang dikirim. Pada tugas akhir ini, dilakukan implementasi algoritma pengujian protokol pengiriman pesan yang diajukan oleh Dolev dkk. (1982), yaitu mengecek apakah terdapat string gamma sehingga overline(gamma) = lambda. Pembuatan algoritma pencarian counterexample untuk protokol yang telah teruji tidak aman juga dilakukan. Algoritma yang diajukan sedikit modifikasi dari Algoritma BFS (Breadth-First Search). Jika k adalah panjang string gamma yang memenuhi overline(gamma) = lambda dan l adalah banyak perulangan dari protokol, algoritma yang diajukan memiliki kompleksitas waktu O((kn^(k+1)-(k+1)n^k+1)/((n-1)^2)) dan kompleksitas memori O(kn^(k-1)) dengan n = 10 + 6l.

An improperly designed protocol for sending a message could be vulnerable to an active saboteur. A protocol for sending a message is called secure if for any saboteur Z, one cannot obtain plaintext M. In this research, the implementation of an algorithm for checking protocol security which is proposed by Dolev et. al. (1982), stated that whether string gamma exists so that overline(gamma) = lambda, has been done. The design of an algorithm for searching counterexample in insecure protocol is proposed. The algorithm is slightly modified from BFS (Breadth-First Search) Algorithm. Let k be the length of string gamma satisfies overline(gamma) = lambda and l be the number of looping in a protocol, the proposed algorithm runs in O((kn^(k+1)-(k+1)n^k+1)/((n-1)^2)) time-complexity and O(kn^(k-1)) memory-complexity, where n = 10 + 6l.

Kata Kunci : keamanan protokol, protokol ping-pong, kriptografi, finite state automata (FSA)