Kode autentikasi

Nama : Nurul Badriya
Nim : 17.01.071.087
Kelas : Informatika B 2017

http://www.uts.ac.id

Kode Autentikasi Pesan dan Fungsi Hash yang Tahan Terhadap Tabrakan

4.3 Kode Otentikasi Pesan – Definisi

Tujuan dari kode otentikasi pesan adalah untuk mencegah musuh memodifikasi pesan yang dikirim oleh satu pihak ke pihak lain, tanpa pihak-pihak tersebut mengisyaratkan bahwa modifikasi telah dilakukan. Seperti dalam hal enkripsi, seperti sebuah tugas hanya mungkin jika pihak yang berkomunikasi memiliki rahasia itu musuh tidak tahu (kalau tidak, tidak ada yang bisa mencegah musuh dari menyamar sebagai pihak yang mengirim
pesan). Pengaturan yang kami lakukan Oleh karena itu, orang di sini menganggap bahwa para pihak memiliki kunci rahasia yang sama. Sejak para pihak berbagi kunci yang sama,gagasan kode otentikasi pesanmilik dunia kriptografi kunci pribadi. Secara longgar, kode otentikasi pesan adalah suatu algoritma diterapkan ke pesan. Output dari algoritma adalah
tag MAC (atau hanya tag) yang dikirim bersama pesan. Keamanan dirumuskan dengan mengharuskan itutidak ada musuh yang dapat menghasilkan tag MAC yang valid pada pesan apa pun yang tidak terkirimoleh pihak komunikasi yang sah.
Sintaks kode otentikasi pesan. Sebelum mendefinisikan keamanan, kode adalah.
Seperti halnya enkripsi, kode otentikasi pesan terdiri daritiga algoritma Gen, Mac dan Vrfy. Algoritma Gen menghasilkan rahasia kunci; seperti pada enkripsi kunci pribadi, kita akan mengasumsikan bahwa pada input 1 n , thealgoritma menghasilkan string berdistribusi merata n. Algoritma Mac menghasilkan tag MAC; yaitu, memetakan kunci k dan pesan m ke tag t. Kita tulis ini sebagai Mac k (m). Akhirnya, algoritma Vrfy menerima kunci k, sebuah pesan m, dan tag t, dan menghasilkan 1 (berarti valid) atau 0 (berarti tidak valid). Kami menulis ini sebagai Vrfy k (m, t). Kami memiliki definisi
formal berikut:

DEFINISI 4.1 (kode otentikasi pesan - sintaksis): Pesan kode otentikasi atau MAC
adalah tuple dari probabilitas polinomial-waktu rithms (Gen, Mac, Vrfy) memenuhi yang
berikut:
1. Setelah input 1 n , algoritma Gen mengeluarkan kunci yang terdistribusi secara
meratak dengan panjang n; k ← Gen (1 n ).
2. Algoritma Mac menerima input beberapa k ∈ {0, 1} n dan m ∈ {0, 1} ∗ , dan
menghasilkan beberapa t ∈ {0, 1} ∗ . Nilai t disebut tag MAC 3. Algoritma Vrfy menerima input beberapa k ∈ {0, 1} n , m ∈ {0, 1} ∗ dan t ∈ {0,
1} ∗, dan menghasilkan sedikit b ∈ {0, 1}.
4. Untuk setiap n, setiap k ∈ {0, 1} n dan setiap m ∈ {0, 1} ∗ menyatakan bahwa
Vrfy k (m, Mac k (m)) = 1.
Jika ada fungsi l (·) sehingga Mac k (·) didefinisikan hanya atas pesan panjang l (n) dan Vrfy k (m, t) menghasilkan 0 untuk setiap m yang tidak panjang l (n),maka kita
katakan bahwa (Gen, Mac, Vrfy) adalah MAC panjang tetap dengan parameter panjang
l.Kami berkomentar bahwa untuk enkripsi, persyaratan kedua dalam Definisi 4.1 bisa
santai jadi itu
Pr [Vrfy k (m, Mac k (m)) = 1]> 1 - negl (n)
di mana negl adalah fungsi yang dapat diabaikan, dan probabilitas diambil alih pilihan k
dan setiap lemparan koin internal untuk Mac dan Vrfy.
Keamanan kode otentikasi pesan.
Definisi 4.1 tidak mengatakan apa-apa apa pun tentang keamanan. Ide intuitif di balik definisi keamanan adalah bahwa tidak ada musuh waktu polinomial yang dapat menghasilkan MAC yang valid tag pada pesan "baru" apa pun (yaitu, pesan yang tidak dikirim oleh komunikator. Para Pihak). Seperti halnya definisi apa pun, kita harus mendefinisikan kekuatan musuh, serta apa yang dianggap sebagai "istirahat" dari skema. Mengenai kekuatan musuh, dalam pengaturan otentikasi pesan, musuh mungkin dapat melihat banyak pesan yang ditandai yang dikirim oleh masing-masing pihak. Selain itu, musuh bahkan mungkin dapat mempengaruhi konten ini pesan. Sebagai contoh, perhatikan kasus bahwa musuh adalah pribadi asisten salah
satu pihak. Dalam hal ini, musuh mungkin bertanggung jawab untuk kata-kata aktual dari banyak pesan yang dikirim (tentu saja, kami berasumsi bahwa asisten tidak memiliki akses ke kunci partai dan itu partai meninjau pesan apa pun sebelum menghitung MAC
di dalamnya). Jelas, kita perlu memastikan bahwa asisten ini tidak dapatmenghasilkan
MAC yang valid pada a pesan tidak ditinjau oleh pihak yang sah. Untuk memodelkan
kemungkinan bahwa musuh dapat secara efektif memilih pesan yang ditandai (atau
setidaknya memengaruhi mereka sampai batas tertentu), kami memberikan musuh
dengan aKotak MAC-generation, atau lebih teknis, dengan oracle MAC. Selama serangan musuh, musuh dapat meminta tag MAC pada pesan apa pun yang diinginkannya, di mana tag ini dihitung menggunakan pihak yang berkomunikasikunci
rahasia. Pada akhir serangan ini, musuh mencoba untuk memutus skema MAC. Kami membuat model jeda dengan mengatakan bahwa musuh berhasil jika menghasilkan yang barupesan dan tag MAC yang valid pada pesan itu. Dengan pesan baru, kami berarti yang tidak ditanyakan oleh musuh ke oracle tag MAC. Itu pertanyaan terakhir yang harus
dijawab di sini adalah bentuk apa yang harus "baru" pesan "miliki. Artinya, apakah itu teks bahasa Inggris yang valid, atau yang benar dokumen Word yang disandikan? Seperti yang mungkin sudah Anda duga, sebutkan spesifik format akan membuat keamanan skema MAC tergantung pada yang diberikan aplikasi. Karena skema kriptografi harus
aman untuk semua aplikasi, bahkan aplikasi-aplikasi di mana string acak ditandai, kami akan mempertimbangkan aSkema MAC rusak jika musuh membuat pesan baru Bersama dengan tag MAC yang valid. Tingkat keamanan ini disebut eksistensial unorgeability terhadap serangan pesan yang dipilih. The "unforgeability eksistensial" mengacu pada
fakta bahwa musuh seharusnya tidak dapat menghasilkan tag MAC yang valid pada pesan apa pun, dan "serangan pesan yang dipilih" mengacu pada fakta bahwa musuh dapat memperoleh tag MAC pada pesan apa pun yang diinginkan selama pesannyamenyerang. Definisi formal percobaan untuk otentikasi pesan kode Π = (Gen, Mac, Vrfy), dengan musuh A dan parameter keamanan n, adalah sebagai berikut:
Percobaan otentikasi pesan Mac-forgeA, Π (n).
1. Kunci acak k ← {0, 1} n dipilih.
2. Musuh A diberi akses oracle ke Mac k (·) dan output
sepasang (m, t). Secara formal, (m, t) ← A Mac k (·) (1 n ). Biarkan Q menyatakan
pertanyaan yang diminta oleh A selama eksekusi.
3. Output percobaan didefinisikan menjadi 1 jika dan hanya jika m / ∈ Q dan Vrfy
k (m, t) = 1.
Definisi tersebut menyatakan bahwa musuh yang efisien tidak akan berhasil di atas bereksperimen dengan probabilitas yang tidak dapat diabaikan.

DEFINISI 4.2 Kode otentikasi pesan Π = (Gen, Mac, Vrfy) adalah eksistensial tidak
dapat dikalahkan di bawah serangan pesan yang dipilih adaptif, atau hanya aman, jika
untuk semua musuh polinomial-waktu probabilitas A, ada yang dapat diabaikan
berfungsi negl sedemikian rupa sehingga:
Pr [Mac-forge A, Π (n) = 1] ≤ negl (n)
Kami berkomentar bahwa kode otentikasi pesan selalu dapat dipatahkanprobabilitas
yang dapat diabaikan (yaitu, tidak ada harapan untuk memastikan bahwa lawan memiliki
sukses dalam percobaan adalah nol). Untuk melihat ini, misalkan q (·) menjadi
polynomialmenunjukkan panjang tag MAC untuk skema (yaitu, untuk kunci Panjang n
dan pesan m, tag keluaran t panjangnya paling banyak q (| m | + n)). Lalu, a serangan naif
yang bekerja untuk skema apa pun adalah mengambil m (dengan panjang berapa pun)
dan cukup pilih string acak t dengan panjang q (| m | + n). Probabilitas itu string ini adalah
tag MAC yang valid setidaknya 2 −q (| m | + n) karena setidaknya satu stringmerupakan
tag MAC yang valid. Tentu saja, serangan semacam itu tidak banyak berpengaruh karena
kesuksesan mereka terlalu kecil. Namun demikian, ini memberi kita lebih rendah terikat
pada panjang tag yang diperlukan dalam skema MAC yang aman. Secara khusus, tag
harus super logaritmik; jika tidak q (| m | + n) = O (log n) dan sebagainya 2 −q (| m | + n)
= 2 −O (log n ) = 1 / poli (n). Dalam kasus seperti itu, tebakan acak dari Tag MAC benar
dengan probabilitas tidak dapat diabaikan, sehingga skema tidak bias amanlah.
Putar ulang serangan dan kode otentikasi pesan. Pertimbangkan skenario rendah:
seorang pengguna Alice mengirimkan pesanan kepada banknya untuk mentransfer $
1.000akunnya ke akun Bob. Alice adalah pengguna yang sah, dan dia juga menerapkan kode otentikasi pesan ke pesan sehingga bank tahu bahwa itu asli. Bob tidak dapat mencegat pesan dan mengubah pesan jumlah hingga $ 10.000 karena ini akan melibatkan penempaan skema MAC. Namun, tidak ada yang mencegah Bob mencegat pesan Alice
dan meneruskannya sepuluhberulang kali ke bank. Jika bank menerima semua pesan ini, maka $ 10.000 akan ditransfer ke akun Bob, dan bukan $ 1.000. Serangan seperti itu disebut serangan replay dan mekanisme MAC dalam dirinya sendiri tidak curhat itu.
Sebaliknya, aplikasi yang menggunakan MAC bertanggung jawab untuk mencegah
replay. Alasan untuk ini adalah bahwa legitimasi atau tidak sah replaytergantung pada aplikasinya. Selain itu, tidak dapat diselesaikan dengan mempertimbangkan satu pesan yang terisolasi; melainkan konteks dan sejarah harus dipertimbangkan Akun. Dengan
demikian diserahkan ke aplikasi tingkat yang lebih tinggi.Dua teknik yang mungkin untuk mencegah replay menggunakan nomor quence dalam transaksi dan menggunakan cap waktu. Saat menggunakan uniknomor urut, idenya
adalah untuk tidak mengizinkan dua transaksi untuk memiliki nomor yang sama (tentu saja, ini membutuhkan mengingat trans- nomor tindakan, tetapi ada solusi untuk ini juga). Saat menggunakan urutanangka, MAC diterapkan pada konten transaksi bersama dengan nomor quence. Catatan daripada setiap serangan balasan yang berhasil harus memalsukan
MAC untuk mengubah nomor urut (jika pesan yang sama persis diputar ulang, itu akan ditolak karena nomornya sudah digunakan). Cap waktu memiliki efek yang serupa: di sini, pesannya termasuk waktu saat ini, dan beberapa Mekanisme ini digunakan agar tidak ada dua transaksi dengan stempel waktu yang sama diterima. Kami menekankan lagi bahwa masalah serangan replay sangat nyata perhatian. Namun, ini harus diselesaikan di
tingkat aplikasi.