Skip to content
Kembali ke hasil pencarian

Kriptanalisis Linear

Diperkenalkan oleh
Mitsuru Matsui
Tahun
1993
Jenis
linear approximation attack
Keluarga
Cryptanalytic technique

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Kriptanalisis linear adalah serangan plaintext yang diketahui yang mengeksploitasi aproksimasi linear dari transformasi non-linear sebuah sandi untuk memulihkan bit kunci rahasia.

Diperkenalkan oleh Mitsuru Matsui pada tahun 1993, kriptanalisis linear memberikan serangan praktis pada sandi seperti DES dengan kompleksitas komputasi yang lebih rendah daripada brute force. Teknik ini menganalisis bias statistik dalam bagaimana kombinasi linear bit plaintext dan ciphertext berhubungan dengan bit kunci, memungkinkan pemulihan kunci dengan persyaratan data yang berkurang.

Intuisi di balik metode

Kriptanalisis linear menemukan persamaan linear yang menghubungkan bit plaintext, bit ciphertext, dan bit kunci. Karena pencampuran yang tidak sempurna dalam putaran sandi, persamaan linear ini berlaku dengan probabilitas sedikit lebih baik daripada acak. Dengan mengumpulkan banyak pasangan plaintext-ciphertext dan mengamati nilai kunci mana yang membuat persamaan ini berlaku lebih sering, penyerang dapat mempersempit kunci yang benar.

Sejarah

Kriptanalisis linear diperkenalkan oleh Matsui pada tahun 1993 sebagai serangan plaintext yang diketahui pada DES. Pada tahun 1994, Matsui mendemonstrasikan kriptanalisis eksperimental pertama dari standar DES menggunakan kriptanalisis linear, memulihkan kunci dengan 2^43 plaintext yang diketahui. Terobosan ini menunjukkan serangan praktis terhadap standar yang diterapkan dan memengaruhi pengembangan AES dengan batas ketahanan yang terbukti.

Kapan digunakan

Kriptanalisis linear digunakan dalam penelitian kriptanalisis dan evaluasi desain sandi. Ini memandu perancang sandi dalam memilih S-box dan transformasi yang tahan terhadap aproksimasi linear. Sandi modern dirancang dengan batas terbukti pada kekuatan aproksimasi linear.

Batasan dan pertimbangan

  • Sandi modern (AES) dirancang dengan hati-hati untuk menahan kriptanalisis linear dengan batas yang dapat dibuktikan
  • Membutuhkan pasangan plaintext-ciphertext yang diketahui, yang mungkin tidak tersedia dalam semua skenario
  • Persyaratan komputasi dan data dapat melebihi kelayakan praktis untuk sandi yang dirancang dengan baik
  • Menemukan aproksimasi linear yang kuat untuk sandi modern sangat sulit

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Serangan praktis pada DES membutuhkan 2^43 pasangan plaintext-ciphertext dan 2^39 operasi
  • Kerangka kerja matematis yang terformalkan dengan baik (lemma piling-up) untuk menganalisis bias aproksimasi
  • Melengkapi kriptanalisis diferensial, menemukan kelemahan yang mungkin terlewatkan oleh analisis diferensial
  • Membentuk persyaratan desain sandi untuk pemilihan S-box dan transformasi putaran

Penerapan

  • Kriptanalisis sandi blok mengevaluasi sifat keamanan dalam penelitian dan standardisasi
  • Desain sandi dan pemilihan S-box untuk memastikan batas aproksimasi linear yang memadai
  • Validasi standar kriptografi (NIST, ETSI) yang memerlukan analisis ketahanan linear
  • Penilaian sandi lama untuk keputusan pensiun dan penggantian

Cara kerjanya

Cara kerjanya

1

Temukan aproksimasi linear: hubungan linear antara bit plaintext, bit ciphertext, dan bit kunci yang berlaku dengan probabilitas yang secara signifikan berbeda dari 0,5.

2

Perkirakan bias (penyimpangan dari 0,5) dari setiap aproksimasi linear menggunakan analisis statistik transformasi putaran.

3

Untuk nilai kunci kandidat, hitung seberapa sering aproksimasi linear berlaku dalam pasangan plaintext-ciphertext yang diketahui. Kunci yang benar membuat aproksimasi berlaku paling sering.

4

Verifikasi bit kunci yang dipulihkan dengan mendekripsi ciphertext dan memeriksa kebenarannya.

Kesalahan umum

  • Mengasumsikan semua aproksimasi linear dapat dieksploitasi; aproksimasi lemah memberikan keuntungan minimal
  • Meremehkan kesulitan serangan praktis ketika persyaratan data teoretis tampak masuk akal
  • Mengabaikan interaksi antara sifat linear dan diferensial dalam analisis sandi

Pertanyaan yang sering diajukan

Apa itu lemma piling-up?

Lemma piling-up menyediakan metode untuk menghitung bias aproksimasi linear di berbagai putaran dengan menggabungkan bias aproksimasi putaran individu. Ini adalah dasar untuk kriptanalisis linear.

Bagaimana AES menahan kriptanalisis linear?

AES menggunakan S-box yang dipilih untuk meminimalkan probabilitas aproksimasi linear maksimum dan lapisan difusi yang memastikan difusi bias linear yang cepat di seluruh putaran. Batas yang terbukti menjamin tidak ada aproksimasi linear praktis.

Apa perbedaan antara kriptanalisis linear dan diferensial?

Analisis diferensial mempelajari perbedaan input-output, sedangkan analisis linear mempelajari aproksimasi linear (XOR bit plaintext dan ciphertext). Keduanya mengeksploitasi kelemahan struktural dalam sandi.

Bisakah kriptanalisis linear memecahkan sandi modern?

Tidak secara praktis. Sandi modern seperti AES memiliki batas yang dapat dibuktikan pada aproksimasi linear yang membuat serangan secara komputasi tidak mungkin dilakukan.

Bagaimana cara mengevaluasi ketahanan linear dalam desain sandi saya?

Analisis tabel aproksimasi linear S-box dan hitung bias maksimum melalui putaran menggunakan lemma piling-up. Pastikan bias maksimum dapat diabaikan di semua aproksimasi linear yang memungkinkan.

Metode terkait

Sumber

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    Buka referensi DOI
    Disalin.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    Buka referensi DOI
    Disalin.