Cara DES Dipecahkan

DES mempunyai 2^56 kunci yang mungkin, bersamaan kira-kira 72 kuadrilion (72,057,594,037,927,936) kunci. Walaupun jumlah ini kedengaran sangat besar, ruang tersebut adalah terhingga dan boleh dicari secara sistematik dengan kuasa pengkomputeran yang mencukupi.

Penghabisan kunci (serangan cuba habis-habisan) secara purata memerlukan pengujian separuh daripada ruang kunci sebelum kunci yang betul ditemui. Bagi DES, ini bermakna kira-kira 2^55 penyahsulitan percubaan, yang setiap satunya hanya memerlukan beberapa operasi pada perkakasan moden.

Pada tahun 1997, RSA Data Security menawarkan hadiah $10,000 untuk memecahkan mesej yang disulitkan dengan DES. Rocke Verser menyelaraskan usaha pengkomputeran teragih merentasi puluhan ribu komputer yang disambungkan ke Internet.

Selepas 96 hari pencarian, kunci tersebut ditemui. Teks biasanya ialah "Kriptografi yang kukuh menjadikan dunia tempat yang lebih selamat." Usaha ini menunjukkan bahawa DES boleh dipecahkan, walaupun ia memerlukan masa berbulan-bulan dan penyelarasan besar-besaran.

Electronic Frontier Foundation membina Deep Crack dengan kos $250,000 pada tahun 1998. Ia mengandungi 1,856 ASIC tersuai, yang setiap satunya mampu menguji 2.5 juta kunci DES sesaat, memberikan Deep Crack kadar gabungan melebihi 90 bilion kunci sesaat.

Deep Crack boleh menghabiskan seluruh ruang kunci DES dalam purata kira-kira 9 hari. Ini membuktikan bahawa penyerang yang bertekad dan membuat pelaburan $250,000 boleh memecahkan DES dalam masa kurang daripada dua minggu.

Dalam Cabaran DES II-1 (Februari 1998), Deep Crack yang digabungkan dengan rangkaian pengkomputeran sukarelawan distributed.net memecahkan DES dalam masa hanya 39 hari. Cabaran II-2 (Julai 1998) berjaya dipecahkan dalam masa 56 jam.

Peningkatan pantas daripada 96 hari kepada 56 jam dalam masa hanya setahun menunjukkan betapa cepatnya peningkatan perkakasan dan penyelarasan yang lebih baik dapat mempercepatkan serangan cuba habis-habisan.

Pada Januari 1999, Deep Crack milik EFF yang digabungkan dengan distributed.net memecahkan Cabaran DES III dalam masa hanya 22 jam 15 minit, lalu memenangi hadiah $10,000 daripada RSA Security.

Demonstrasi muktamad bahawa DES boleh dipecahkan dalam masa kurang daripada 24 jam ini secara berkesan menamatkan sebarang hujah tentang keselamatan DES. Tidak lama selepas itu, NIST memulakan proses memilih pengganti DES, yang akhirnya menjadi AES.

Distributed.net menganjurkan usaha pengkomputeran sukarelawan yang membolehkan pengguna Internet biasa menyumbangkan kitaran CPU mereka kepada cabaran DES. Pada kemuncaknya, ratusan ribu komputer mengambil bahagian.

Setiap komputer menguji bahagian ruang kunci yang berbeza, dengan penyelarasan daripada pelayan pusat. Usaha ini mempelopori model pengkomputeran teragih untuk kriptanalisis yang masih digunakan pada hari ini bagi cabaran seperti memecahkan sifir lama.

Penghabisan kunci berkesan kerana setiap penyahsulitan DES adalah pantas (mikrosaat pada perkakasan) dan tidak bergantung pada penyahsulitan lain. Tiada kebergantungan antara pengujian kunci N dengan kunci N+1, jadi pencarian boleh diparalelkan dengan sempurna merentasi sebarang bilangan mesin.

Sifat yang sangat mudah diparalelkan ini bermakna penggandaan perkakasan akan membahagikan masa tepat kepada separuh. Penambahan lebih banyak mesin memberikan peningkatan kelajuan linear, lalu menjadikan kosnya berbaloi bagi penyerang.

Eli Biham dan Adi Shamir menerbitkan kriptanalisis pembezaan pada tahun 1990, iaitu teknik yang mengeksploitasi cara perbezaan dalam pasangan masukan merambat melalui pusingan sifir. Bagi DES, teknik ini secara teori memerlukan 2^47 teks biasa terpilih.

Kemudiannya didedahkan bahawa kotak-S DES direka dengan mengambil kira ketahanan terhadap kriptanalisis pembezaan, yang menunjukkan bahawa NSA mungkin telah mengetahui teknik ini pada tahun 1970-an. Serangan ini mengagumkan dari segi teori, tetapi secara praktikalnya ditandingi oleh serangan cuba habis-habisan menggunakan perkakasan.

Mitsuru Matsui menerbitkan kriptanalisis linear pada tahun 1993, yang memerlukan 2^43 teks biasa diketahui untuk menyerang DES. Beliau melaksanakan serangan tersebut dan memecahkan DES secara eksperimen pada tahun 1994, sekali gus mengesahkan analisis teori.

Kriptanalisis linear mencari penghampiran linear terhadap tingkah laku kotak-S dan menggunakannya untuk mendapatkan semula bit kunci dengan kecenderungan statistik. Secara teori, teknik ini memerlukan data yang jauh lebih sedikit berbanding kaedah cuba habis-habisan, tetapi tidak praktikal sebelum wujudnya serangan menggunakan perkakasan.

Kriptanalisis pembezaan diterbitkan pada tahun 1990 tetapi memerlukan teks biasa terpilih, yang tidak praktikal dalam kebanyakan senario sebenar. Kriptanalisis linear diterbitkan pada tahun 1993 dan berfungsi dengan teks biasa diketahui, tetapi memerlukan 2^43 teks biasa sedemikian.

Serangan cuba habis-habisan menggunakan perkakasan (Deep Crack) memecahkan DES dalam masa 22 jam pada tahun 1999. Secara praktikal, serangan perkakasan itu lebih dahsyat berbanding kemajuan kriptanalisis secara teori kerana ia langsung tidak memerlukan pasangan teks biasa-teks sifir yang khusus.

Pemecahan DES secara terbuka dan didokumentasikan memberikan implikasi dasar yang serta-merta. NIST memulakan proses pertandingan AES pada tahun 1997, iaitu tahun yang sama Cabaran DES I berjaya diselesaikan. Pertandingan tersebut direka khusus untuk mengelakkan kelemahan dalam proses penyeragaman DES.

Bank dan agensi kerajaan mula beralih kepada 3DES sebagai langkah sementara sementara AES dibangunkan. Garis masa pemecahan DES secara langsung menentukan tahap kesegeraan dan jadual usaha penerimaan AES.

DES dipecahkan dengan semakin pantas: 96 hari pada tahun 1997, 56 jam pada tahun 1998 dan 22 jam pada tahun 1999. Deep Crack milik EFF yang berharga $250,000 menggunakan ASIC tersuai untuk menguji 90 bilion kunci sesaat.

Kriptanalisis pembezaan (2^47 teks biasa terpilih) dan kriptanalisis linear (2^43 teks biasa diketahui) juga secara teori boleh memecahkan DES, tetapi serangan cuba habis-habisan menggunakan perkakasan merupakan kaedah yang benar-benar berkesan. Pemecahan dalam masa 22 jam menamatkan hayat DES sebagai sifir yang boleh dipercayai.