Rangkuman kripto Membangun Kode Otentikasi Pesan Aman

4.4 Membangun Kode Otentikasi Pesan Aman

Alat alami yang digunakan untuk membuat kode otentikasi pesan adalah a fungsi pseudorandom. Secara intuitif, jika tag MAC t diperoleh dengan menerapkan fungsi pseudorandom ke pesan m, kemudian menempa MAC melibatkan menebak perilaku input / output fungsi pseudorandom. Lebih untuk- mally, kita tahu bahwa probabilitas menebak nilai fungsi acak pada titik yang tidak teramati adalah 2 − n ketika panjang output adalah n. Oleh karena itu mengikuti terendah kemungkinan menebak nilai seperti itu untuk fungsi pseudorandom (yang setara dengan menebak tag MAC) hanya bisa sangat berbeda. Teknis yang muncul di sini adalah definisi kami tentang fungsi pseudorandom tions.

THEOREM 4.4

Asumsikan bahwa fungsi F yang digunakan dalam Konstruksi 4.3 adalah fungsi pseudorandom. Kemudian, Konstruksi 4.3 adalah panjang tetap mes- kode otentikasi bijak dengan parameter panjang l (n) = n yang ada secara eksistensial tidak dapat dikalahkan di bawah serangan pesan yang dipilih.

KONSTRUKSI 4.3 MAC dengan panjang tetap.

Biarkan F: {0, 1} ∗ × {0, 1} ∗ → {0, 1} ∗ menjadi fungsi sedemikian rupa sehingga untuk setiap k, F k (·) memetakan string n-bit ke string n-bit. Tetapkan MAC dengan panjang tetap sebagai berikut:

• Gen (1 n ): pada input 1 n , pilih k ← {0, 1} n

• Mac k (m): saat tombol input k ∈ {0, 1} n dan pesan m ∈ {0, 1} n , hitung t = Fk (m). (Jika | m | = | k | maka keluaran ⊥.)

• Vrfy k (m, t): saat tombol input k ∈ {0, 1} n , pesan m ∈ {0, 1} n dan tag t ∈ {0, 1} n , output 1 jika dan hanya jika t = F k (m). (Jika panjangnya salah, maka output 0.)

BUKTI

Intuisi di balik bukti teorema ini dijelaskan atas. Karena itu, kami mempelajari rinciannya secara langsung. Seperti dalam penggunaan sebelumnya fungsi pseudorandom, bukti ini mengikuti paradigma pertama menganalisis keamanan skema menggunakan fungsi yang benar-benar acak, dan kemudian mempertimbangkan hasil penggantian fungsi yang benar-benar acak dengan yang pseudorandom. Misalkan A menjadi musuh waktu-polinomial probabilistik dan misalkan ε (·) menjadi fungsi yang seperti itu Pr [Mac-forge A, Π (n) = 1] = ε (n) (4.1). Kami menunjukkan bahwa ini menyiratkan adanya algoritma waktu polinomial itu dapat membedakan fungsi pseudorandom dari fungsi acak dengan keuntungan ε (n). Ini kemudian akan menyiratkan bahwa ε harus diabaikan, seperti yang dipersyaratkan. Pertimbangkan kode otentikasi pesan ˜Π = (˜ Gen, ˜ Enc, ˜ Desember) yang merupakan sama dengan Π = (Gen, Mac, Vrfy) dalam Konstruksi 4.3 kecuali yang benar-benar acak function fn digunakan sebagai ganti fungsi pseudorandom F. (Tentu saja, ini bukan "MAC legal" karena tidak efisien.

 Namun demikian, ini digunakan untuk demi bukti saja.) Sangat mudah untuk melihat itu Pr [Mac-forge A, ˜Π (n) = 1] ≤ 1 2 n (4.2) karena untuk setiap pesan m / ∈ Q, nilai t = f n (m) terdistribusi secara seragam di {0, 1} n dari sudut pandang musuh A. Kami sekarang membuat D-polinomial-time distinguisher yang diberi oracle (yang merupakan salah satu fungsi pseudorandom atau fungsi yang benar-benar acak) dan bekerja sebagai berikut. Setelah input 1 n , algoritma D memanggil A pada input 1 n . Kemudian, ketika A menanyakan oracle-nya dengan pesan m, D menanyakan oracle-nya dengan m dan set t untuk menjadi oracle reply. D menyerahkan t ke A dan melanjutkan. Pada akhirnya, ketika A menampilkan pasangan (m, t), D yang berbeda memeriksa bahwa m tidak diminta selama eksekusi (yaitu, m / ∈ Q) dan t itu adalah MAC yang “valid”. D melakukan ini dengan menanyakan m ke oracle-nya dan memeriksa apakah responsnya sama dengan t. Jika keduanya dari lulus pemeriksaan di atas (dan A "berhasil" dalam percobaan), lalu D output 1. Kalau tidak output 0. Kode Autentikasi Pesan dan Fungsi Hash yang Tahan Terhadap Tabrakan 115 Dari konstruksi D, dan keberhasilan A seperti yang ditunjukkan dalam Equa-tions (4.1) dan (4.2), karena itu: Pr [D F k (·) (1 n ) = 1] = Pr [Mac-menempa A, Π (n) = 1] = ε (n) dan Pr [D f n (·) (1 n ) = 1] = Pr [Mac-forge A, ˜Π (n) = 1] ≤ 1 2 n Karena itu, ∣Pr [D F k (·) (1 n ) = 1] - Pr [D f n (·) (1 n ) = 1] ∣∣∣ ≥ ε (n) – 1 2 n Dengan asumsi bahwa F adalah fungsi pseudorandom, maka ε (n) - 2 −n harus dapat diabaikan, dan jadi ε (·) harus merupakan fungsi yang dapat diabaikan. Ini mengatakan bahwa A berhasil di Mac-forge dengan probabilitas paling kecil, dan sebagainya Konstruksi 4.3 pada dasarnya tidak bisa dikalahkan di bawah serangan pesan yang dipilih. Kode otentikasi pesan panjang variabel. 

Dalam semua berikut ini (dan dalam konstruksi aman kami di bawah), idenya adalah untuk istirahat pesan ke dalam blok dan menerapkan fungsi pseudorandom ke blok di entah bagaimana :

1. Terapkan fungsi pseudorandom ke blok pertama: Ini jelas bukan mengamankan MAC karena tidak ada yang mencegah musuh mengubah semua blok lainnya terpisah dari yang pertama. 1 Kami mencatat bahwa jika kami memiliki fungsi pseudorandom yang berfungsi untuk input panjang variabel, maka bukti Teorema 4.4 akan melalui MAC yang tidak berubah dan jadi variabel-panjang akan diturunkan.Fungsi pseudorandom praktis adalah untuk panjang input tetap, kami menggunakan yang berbeda metode untuk mendapatkan MAC panjang variabel.

2. Eksklusif-ATAU semua blok dan menerapkan fungsi pseudorandom ke hasil: Dalam hal ini, yang perlu dilakukan musuh adalah mengubah pesan ehingga XOR dari blok tidak berubah (dengan demikian menyiratkan bahwa Tag MAC tetap sama). Ini dapat dilakukan dengan mengubah dua dari blok sehingga XOR mereka tetap sama. 

3. Terapkan fungsi pseudorandom untuk setiap blok secara terpisah dan output hasil: Ini mirip dengan mode ECB di Bagian 3.6.4. Pada kasus ini, tidak ada blok yang dapat dengan mudah dimodifikasi. Kami sekarang membuktikan bahwa Konstruksi 4.5 merupakan pesan aman auten- kode ticate:

THEOREM 4.6

Asumsikan bahwa fungsi F yang digunakan dalam Konstruksi 4.5 adalah a fungsi pseudorandom. Kemudian, Konstruksi 4.5 adalah otentikasi pesan kode yang secara eksistensial tidak dapat dikalahkan di bawah serangan pesan yang dipilih.

BUKTI

Intuisi di balik buktinya adalah bahwa jika pengidentifikasi acak r adalah berbeda di setiap tanda tangan yang diterima musuh dari oracle, lalu pemalsuan harus mengandung pengidentifikasi baru atau entah bagaimana harus memanipulasi blok pesan yang ditandatangani. Dalam kedua kasus, musuh harus menebak output dari fungsi pseudorandom pada "titik baru". Misalkan A menjadi musuh waktu-polinomial probabilistik dan misalkan ε (·) menjadi fungsi yang seperti itu Pr [Mac-forge A, Π (n) = 1] = ε (n) 

KONSTRUKSI 4.5 MAC panjang variabel. 

Biarkan F: {0, 1} ∗ × {0, 1} ∗ → {0, 1} ∗ menjadi fungsi sedemikian rupa sehingga untuk setiap k ∈ {0, 1} n , F k (·) memetakan string n-bit ke string n-bit. Tentukan variabel- panjang MAC sebagai berikut:

• Gen (1 n ): pada input 1 n , pilih k ← {0, 1} n

• Mac k (m): setelah memasukkan kunci k ∈ {0, 1} n dan pesan m ∈ {0, 1} ∗ panjang maksimal 2 n 4 −1 , parse m pertama ke d blok m 1 , ···, m d , masing-masing panjang n / 4. (Untuk memastikan pengodean yang unik, yang terakhir blok diisi dengan 10 ∗ .) Selanjutnya, pilih pengidentifikasi acak r ← {0, 1} n / 4 . Kemudian, untuk i = 1, ..., d, hitung t i = F k (rdim i ), di mana i dan d secara unik dikodekan menjadi string dengan panjang n / 4 dan "" menunjukkan rangkaian. Sebuah

Akhirnya, keluarkan tag t = (r, t 1 , ..., t d ).

• Vrfy k (m, t): Setelah tombol input k, pesan m dan tag t, jalankan MAC- algoritma pembuatan tag Mac kecuali bahwa alih-alih memilih a pengidentifikasi acak, ambil pengidentifikasi r yang muncul di t. Keluaran 1 jika dan hanya jika tag yang diterima dengan menjalankan Mac dengan ini r identik dengan t. sebuah Perhatikan bahwa saya dan d dapat dikodekan dalam n / 4 bit karena panjang dari padded m paling banyak 2 n / 4 . Kami menunjukkan bahwa ini menyiratkan adanya algoritma waktu polinomial itu dapat membedakan fungsi pseudorandom dari fungsi acak dengan keuntungan setidaknya ε (n) - negl (n) untuk fungsi negl yang dapat diabaikan (·).. Kami sekarang menunjukkan bahwaPr [Mac-forgeA, ˜Π(n) = 1] ≤ negl (n) (4.4) untuk fungsi negl yang dapat diabaikan (·). Biarkan Q menjadi set kueri yang dibuat oleh A in Mac-forge dengan ˜Π dan biarkan (m, t) menjadi outputnya. Kami menganalisis probabilitas bahwa m / ∈ Q dan t adalah tag MAC yang valid untuk m. Ingat analisis kami di sini adalah dalam kasus bahwa fungsi yang benar-benar acak digunakan. Biarkan t = (r, t 1 , ..., t d ). Kami memiliki kasus-kasus berikut:

1. Identifier r yang muncul di tag t output oleh A berbeda dari semua pengidentifikasi yang diperoleh oleh A dari oracle MAC-nya selama percobaan: Ini menyiratkan bahwa fungsi f n tidak pernah diterapkan ke blokmform (r, ⋆, ⋆, ⋆) selama Mac-menempa dengan ˜Π. Karena fn benar-benar acak, maka f mengikuti bahwa probabilitas bahwa A berhasil menebak setiap t i adalah paling banyak 2 − n . (Ini sebenarnya perlu berhasil menebak semua t 1 , ..., t d nilai karena r pengidentifikasi baru harus muncul di semua blok. Namun demikian, itu cukup untuk mengikat keberhasilannya dengan 2 − n .)

2. Pengidentifikasi r muncul di tag t output oleh A muncul persis salah satu tag MAC yang diperoleh oleh A dari oracle MAC-nya selama Percobaan: Ditunjukkan oleh m pesan bahwa A menanyakan oracle-nya yang jawabannya t berisi pengidentifikasi r. Karena m / ∈ Q menyatakan itu m = m, di mana m adalah output pesan oleh A. Biarkan d dan d menjadi jumlah blok dalam parsing m dan m, masing-masing. Ada dua bagian di sini: 

(a) Kasus 1: d = d. Dalam hal ini, isi pesan dari salah satu blok harus berbeda (yaitu, untuk beberapa i itu harus menyatakan bahwa (m i , i) = (m i , i)); biarkan saya menunjukkan indeks dari blok yang berbeda. Seperti dalam kasus sebelumnya, ini berarti bahwa fungsi acak f n tidak pernah diterapkan pada blok dengan konten (r, d, i, m i ) selama Mac-forge with ~Π, dan A dapat berhasil dalam menebak t i dengan probabilitas paling 2 − n .

(b) Kasus 2: d = d. Dalam hal ini, setiap blok dalam pesan yang diuraikan m adalah dari bentuk (r, d, ⋆, ⋆). Namun, r hanya digunakan dalam menghasilkan MAC untuk m panjang d. Oleh karena itu, f n tidak pernah diterapkan pada a blok bentuk (r, d, ⋆, ⋆) selama percobaan. (Fungsinya f n hanya diterapkan untuk blok dengan r yang berbeda atau dalam bentuk (r, d, ⋆, ⋆) di mana d = d.) Dengan demikian, f n tidak pernah diterapkan pada blok muncul di pemalsuan MAC t. Seperti di atas, ini berarti bahwa A dapat berhasil dengan probabilitas paling banyak 2 − n .

3. Pengidentifikasi r muncul di tag t output oleh A muncul dalam dua atau lebih banyak dari tag MAC yang diperoleh oleh A dari oracle MAC-nya selama percobaan: Kami mengesampingkan kasus ini dengan menunjukkan bahwa dua tag MAC (gen- telah dihapus secara hukum) memiliki pengidentifikasi yang sama dengan kemungkinan yang paling kecil bility. Sekarang, panjang pengidentifikasi acak adalah n / 4. Karena itu, untuk N pesan, probabilitas bahwa setidaknya dua tag MAC memiliki yang sama pengidentifikasi adalah ( N 2 ) · 2 −n / 4 = O (N 2 ) 2 n / 4 (Perhitungan ini didasarkan pada fakta bahwa probabilitas bahwa satu pasangan memiliki pengidentifikasi yang sama adalah 2 − n / 4 dan ada ( N 2 ) kemungkinan pasangan). Karena N = poli (n), kita memiliki ini dapat diabaikan, seperti yang dipersyaratkan. Analisis di atas mencakup semua kasus yang mungkin, dan jadi kami memiliki bahwa A dapat berhasil ceed di Mac-forge dengan ˜Π dengan kemungkinan paling kecil, membuktikan Equa- tion (4.2).