Cara DES Dipecahkan

DES memiliki 2^56 kemungkinan kunci, yang setara dengan sekitar 72 kuadriliun (72,057,594,037,927,936) kunci. Meskipun jumlah ini terdengar sangat besar, ruang tersebut terbatas dan dapat dicari secara sistematis dengan daya komputasi yang memadai.

Penghabisan kunci (pencarian menyeluruh) rata-rata memerlukan pengujian terhadap separuh ruang kunci sebelum kunci yang benar ditemukan. Untuk DES, ini berarti sekitar 2^55 dekripsi percobaan, yang masing-masing memerlukan beberapa operasi pada perangkat keras modern.

Pada 1997, RSA Data Security menawarkan hadiah $10,000 bagi pihak yang berhasil memecahkan pesan yang dienkripsi dengan DES. Rocke Verser mengoordinasikan upaya komputasi terdistribusi melalui puluhan ribu komputer yang terhubung ke internet.

Setelah pencarian selama 96 hari, kuncinya ditemukan. Teks terangnya adalah "Kriptografi yang kuat membuat dunia menjadi tempat yang lebih aman." Upaya ini menunjukkan bahwa DES dapat dipecahkan, meskipun memerlukan waktu berbulan-bulan dan koordinasi dalam skala besar.

Electronic Frontier Foundation membangun Deep Crack dengan biaya $250,000 pada 1998. Perangkat ini memiliki 1.856 ASIC khusus, yang masing-masing mampu menguji 2,5 juta kunci DES per detik, sehingga Deep Crack mencapai laju gabungan lebih dari 90 miliar kunci per detik.

Deep Crack dapat menghabiskan seluruh ruang kunci DES rata-rata dalam waktu sekitar 9 hari. Hal ini membuktikan bahwa lawan yang gigih dengan investasi $250,000 dapat memecahkan DES dalam waktu kurang dari dua minggu.

Dalam DES Challenges II-1 (Februari 1998), Deep Crack yang digabungkan dengan jaringan komputasi sukarela distributed.net memecahkan DES hanya dalam 39 hari. Challenges II-2 (Juli 1998) berhasil dipecahkan dalam 56 jam.

Perbaikan pesat dari 96 hari menjadi 56 jam hanya dalam satu tahun menunjukkan betapa cepatnya peningkatan perangkat keras dan koordinasi yang lebih baik dapat mempercepat serangan pencarian menyeluruh.

Pada Januari 1999, Deep Crack milik EFF yang digabungkan dengan distributed.net memecahkan DES Challenge III hanya dalam 22 jam 15 menit dan memenangkan hadiah $10,000 dari RSA Security.

Demonstrasi definitif bahwa DES dapat dipecahkan dalam waktu kurang dari 24 jam ini secara efektif mengakhiri segala argumen mengenai keamanan DES. Tidak lama kemudian, NIST memulai proses pemilihan pengganti DES, yang akhirnya menjadi AES.

Distributed.net mengorganisasi upaya komputasi sukarela, dengan pengguna internet biasa menyumbangkan siklus CPU mereka untuk tantangan DES. Pada puncaknya, ratusan ribu komputer berpartisipasi.

Setiap komputer menguji bagian ruang kunci yang berbeda, dengan koordinasi dari server pusat. Model komputasi terdistribusi untuk kriptanalisis ini dirintis melalui upaya tersebut dan masih digunakan hingga saat ini untuk tantangan seperti memecahkan sandi lama.

Penghabisan kunci dapat dilakukan karena setiap dekripsi DES berlangsung cepat (dalam hitungan mikrodetik pada perangkat keras) dan bersifat independen. Tidak ada ketergantungan antara pengujian kunci N dan kunci N+1, sehingga pencarian dapat diparalelkan secara sempurna ke sejumlah mesin.

Sifat tugas yang sangat mudah diparalelkan ini berarti bahwa menggandakan perangkat keras akan tepat membagi dua waktu yang diperlukan. Penambahan mesin memberikan percepatan linear, sehingga biayanya menguntungkan bagi penyerang.

Eli Biham dan Adi Shamir menerbitkan kriptanalisis diferensial pada 1990, yaitu teknik yang memanfaatkan cara perbedaan pada pasangan masukan merambat melalui putaran-putaran sandi. Untuk DES, teknik ini secara teori memerlukan 2^47 teks terang pilihan.

Kemudian diketahui bahwa kotak substitusi DES dirancang dengan mempertimbangkan ketahanan terhadap kriptanalisis diferensial, yang menunjukkan bahwa NSA telah mengetahui teknik ini pada 1970-an. Serangan ini mengesankan secara teori, tetapi dalam praktiknya kalah efektif dibandingkan pencarian menyeluruh dengan perangkat keras.

Mitsuru Matsui menerbitkan kriptanalisis linear pada 1993, yang memerlukan 2^43 teks terang yang diketahui untuk menyerang DES. Ia menerapkan serangan tersebut dan berhasil memecahkan DES secara eksperimental pada 1994, sehingga mengonfirmasi analisis teoretisnya.

Kriptanalisis linear menemukan pendekatan linear terhadap perilaku kotak substitusi dan menggunakannya untuk memulihkan bit-bit kunci dengan memanfaatkan bias statistik. Secara teori, teknik ini memerlukan data yang jauh lebih sedikit daripada pencarian menyeluruh, tetapi tidak praktis sebelum adanya serangan berbasis perangkat keras.

Kriptanalisis diferensial diterbitkan pada 1990, tetapi memerlukan teks terang pilihan, yang tidak praktis dalam sebagian besar situasi nyata. Kriptanalisis linear diterbitkan pada 1993 dan dapat bekerja dengan teks terang yang diketahui, tetapi memerlukan 2^43 teks terang tersebut.

Pencarian menyeluruh dengan perangkat keras (Deep Crack) memecahkan DES dalam 22 jam pada 1999. Dalam praktiknya, serangan perangkat keras lebih menghancurkan daripada kemajuan kriptanalisis teoretis karena sama sekali tidak memerlukan pasangan teks terang-teks tersandi khusus.

Pembobolan DES secara terbuka dan terdokumentasi memiliki implikasi kebijakan yang langsung. NIST memulai proses kompetisi AES pada 1997, tahun yang sama ketika DES Challenge I berhasil diselesaikan. Kompetisi tersebut secara khusus dirancang untuk menghindari kelemahan dalam proses standardisasi DES.

Bank dan lembaga pemerintah mulai beralih ke 3DES sebagai tindakan sementara selama AES dikembangkan. Linimasa pembobolan DES secara langsung menentukan urgensi dan jadwal upaya adopsi AES.

Ujilah pemahaman Anda tentang sejarah pembobolan DES.

DES dipecahkan dengan semakin cepat: dalam 96 hari pada 1997, 56 jam pada 1998, dan 22 jam pada 1999. Deep Crack milik EFF seharga $250,000 menggunakan ASIC khusus untuk menguji 90 miliar kunci per detik.

Kriptanalisis diferensial (2^47 teks terang pilihan) dan kriptanalisis linear (2^43 teks terang yang diketahui) juga secara teori dapat memecahkan DES, tetapi pencarian menyeluruh dengan perangkat keras merupakan serangan yang paling efektif dalam praktik. Pembobolan dalam 22 jam mengakhiri kelayakan DES sebagai sandi.