Cryptography : Advanced Encryption Standard (AES)
Halo, pada post sebelumnya saya telah menjelaskan mengenai Cryptogaphy DES. Pada post kali ini, saya akan menjelaskan mengenai algoritma symmetric lainnya, yaitu: Advanced Encryption Standard (AES). Selain DES, algoritma AES adalah algoritma yang saat ini masih banyak digunakan dalam berbagai bidang, selain prosesnya yang cepat tingkat keamaan AES sangatlah tinggi. Sampai saat ini algoritma ini masih belum berhasil dibobol dengan metode cryptoanalys. Oke langsung saja kita ke pembahasannya.
Advanced Encryption Standard (AES)
AES merupakan algoritma cryptography symmetric yang sampai saat ini masih digunakan diberbagai macam aplikasi. Algoritma ini telah disahkan sebagai algoritma untuk data encryption standard oleh National Institute of Standards and Technology (NIST) pada tahun 2001. Sebenarnya nama original dari AES adalah algoritma Rijndael, dimana algoritma ini pertama kali dikembangkan oleh Vincent Rijmen dan Joan Daemen.
Pada awalnya algoritma Rijandael merupakan hasil kompetisi yang diadakan oleh NIST setelah sebelumnya algoritma DES berhasil dibobol. Selain Rijndael terdapat dua kandidat terkuat lainnya yaitu Serpent dan juga Twofish. Namun Rijndael berhasil memenangi score dengan nilai pengujian 86 positif dan 10 negatif, sehingga algoritma Rijandael diresmikan sebagai standar enkripsi dengan nama AES.
Rijndael merupakan algoritma berjenis block cipher dengan jumlah key yang berbeda-beda. Namun untuk AES NIST memilih 3 sub bagian dari Rijndael, setiap blok terdiri dari 128 bit input data, dengan 3 jenis ukuran key yang berbeda yaitu: 128, 192 atau 256 (bit). Proses AES terdiri dari beberapa sub proses. Untuk lebih jelasnya lihatlah gambar berikut
Algoritma encryption ataupun decryption pada AES terdiri dari proses awal yaitu: Key Expansion dan AddRoundKey, proses utama yaitu: SubBytes — ShiftRows — MixColumns — AddRoundKey dan proses akhir yaitu: SubBytes — ShiftRows — AddRoundKey. Pada proses utama jumlah pengulangan atau round, dimana pengulangan yang terjadi bergantung dengan jumlah key yang digunakan
128 bit key -> 9 kali
192 bit key -> 11 kali
256 bit key -> 13 kaliUntuk lebih jelasnya mari kita langsung mengerjakan contoh
Data yang akan diencrypt: HELOBUDYSAYAKRES (dalam bentuk ASCII), kita ubah ke bentuk HEX menjadiPlaintext: 48 45 4c 4f 42 55 44 59 53 41 59 41 4b 52 45 53
Key: 00 11 22 33 44 55 66 77 88 99 AA BB CC DD EE FF
Key Expansion/Schedule
Sama seperti DES yang memiliki proses key schedule, AES juga memiliki proses yang disebut key expansion. Pada proses ini key utama akan diperbanyak menjadi 10/12/14 buah tergantung dari jumlah ukuran key yang digunakan. Pada kali ini kita akan menggunakan key dengan ukuran 16 byte (128 bit) sehingga kita akan memiliki 10 buah key berbeda untuk masing-masing roundnya. Berikut adalah gambaran proses key expansion pada AES
Pertama — Kita akan merubah 16 byte key utama kedalam bentuk matrix 4x4 seperti berikut
Kedua — Kita akan melakukan proses RotWord, dimana pada algoritma AES prosesnya adalah “one byte left circular shift”, atau menggeser posisi byte ke kiri secara circular. Pada proses pertama, kita akan mengambil kolom terakhir dari matrix key utama.
Ketiga — Kita akan melakukan proses SubWord. Pada proses ini kita akan petakan setiap byte key dengan menggunakan tabel S-Box AES.
Pada contoh sebelumnya 4 byte pada kolom terakhir adalah DD, EE, FF, dan CC maka padanan pada S-Box adalah
Sehingga kita mendapatkan nilai
Keempat — Kita akan melakukan proses Rcon, dimana 4 byte hasil S-Box akan di XOR-kan dengan matrix konstan Rcon
i merupakan nomor round saat proses dilakukan. Untuk AES 128 bit terdapat 10 jumlah round, sehingga nilai rci untuk masing-masing round adalah
Sehingga pada proses round 1 matrix rcon yang digunakan adalah [01 00 00 00] di XOR-kan dengan hasil S-Box sebelumnya
Kelima — Hasil dari proses Rcon akan di-XOR-kan dengan key utama pada kolom ke 0 yaitu [00 11 22 33]
Hasil dari XOR pada proses pertama akan dilakukan XOR lagi dengan key utama pada kolom ke 1 yaitu [44 55 66 77] sehingga mendapatkan hasil
Proses ini akan berulang hingga kita mendapatkan 4 kolom baru seperti yang telah ditunjukan pada diagram key xpansion AES. Sehingga kita akan mendapatkan 16 byte sub key untuk round 1
Kita akan mengulang kelima proses di atas sebanyak 10 kali hingga mendapat 10 sub key untuk 10 round pada AES. Hasilnya adalah sebagai berikut
Add Round Key
Pada proses ini kita akan melakukan XOR antara plaintext dengan key utama
Proses Encryption — Sub Bytes
Proses selanjutnya adalah Sub Bytes. Proses ini sama dengan proses sub bytes pada key expansions, dimana hasil dari add round key sebelumnya kita petakan ke dalam tabel S-Box AES. Contohnya pada kolom pertama [48 54 6E 7C
Sehingga untuk keseleruhan proses kita mendapatkan
Proses Encryption — Shift Row
Proses selanjutnya adalah Shift Row, dimana kita akan melakukan pergeseran baris pada matrix ke sebelah kiri sebanyak:
Baris Ke 2 << 1 kali
Baris Ke 3 << 2 kali
Baris Ke 4 << 3 kali
Proses Encryption — Mix Column
Setelah kita melakukan proses Shift Row, selanjutnya kita akan melakukan proses Mix Column pada matrix. Proses ini relatif lebih sulit dikarenakan kita akan melakukan perkalian pada Galois Field dengan orde GF(2⁸).
Pertama kita akan melakukan perkalian antara matrix dengan menggunakan Matrix Mix Column
Contohnya kita akan melakukan perkalian pada kolom pertama dari input sebelumnya terlebih dahulu
Untuk perkalian pertama yaitu:
Kita dapat melakukan proses perkalian pada Galois Field secara matematis langsung ataupun dengan menggunakan pendekatan algoritma. Pada kali ini saya akan membahas perhitungan secara matematis.
Pertama kita konversikan terlebih dahulu bilangan-bilangan Hexadesimal tersebut menjadi bentuk binernya, lalu kita transformasikan ke dalam bentuk Polynomialnya
Setelah itu kita akan melakukan proses perkalian polynomial seperti biasa
Selanjutnya kita transformasikan lagi ke dalam bentuk biner dan kita konversi kan kembali ke dalam bentuk Hexadesimal. Contoh selanjutnya adalah
Pada penjumlahan dalam Galois Field, jika terdapat penjumlahan 1+1 maka hasilnya adalah 0, dimana hal ini serupa dengan operasi XOR.
Sehingga untuk d0 kita mendapatkan hasil
Dalam Galois Field dengan orde 2⁸ jika kita mendapatkan hasil polynomial lebih dari x⁷ kita perlu melakukan pembagian modulus dengan menggunakan irreducible polynomial → x⁸ + x⁴ + x³ + x +1. Contohnya jika kita memiliki perkalian bilangan berikut
dimana pembagian modulusnya adalah sebagai berikut
Sehingga hasil akhirnya adalah
Setelah kita melakukan mix column untuk semua kolom pada matrix input, maka kita akan mendapatkan hasil
Proses Encryption — Add Key
Proses selanjutnya adalah melakukan XOR antara input hasil mix column dengan sub key yang telah didapat dari proses key expansion. Pada contoh ini adalah round 1, sehingga Sub Key yang digunakan adalah yang pertama
Hasil dari add key akan digunakan kembali sebagai input proses encryption (sub byte, shift row, mix column, add key) selanjutnya. Seluruh proses akan dilakukan kembali sampai dengan round 9 . Untuk round ke 10 prosesnya masih sama, namun pada round ini proses mix column tidak dilakukan.
Setelah melakukan seluruh proses sebanyak 10 round, maka hasil encryption adalah sebagai berikut
Sulit sekali bukan !!! prosesnya terlihat lebih simple dibandingkan DES. Namun ketangguhan AES sangatlah hebat dikarenakan sampai sekarang algoritma ini masih belum berhasil dibobol secara cryptoanalys. Dengan komputer paling canggihpun saat ini AES masih belum mampu dibobol. Namun mungkin dengan berkembangnya teknologi kuantum dan juga super komputer, mungkin kedepannya AES akan berhasil dibobol.
Untuk lebih jelasnya saya sudah membuat contoh pemograman AES dengan menggunakan pemograman python pada jupyter notebook yang bisa diakses di Example AES
Penutup
Sekian dulu penjelasan mengenai algoritma AES. Hingga saat ini AES masih belum mampu dibobol secara langsung. Namun terdapat metode lain yang disebut Side Channel Analysis/Attack (SCA) dimana kita dapat membobol AES dari leakage yang terjadi pada perangkat yang digunakan, misalnya dengan menggunakan Daya (Power Measurement) ataupun Elektro Magnetik. Pada post selanjutnya saya akan membahas mengenai metode Side Channel Attack untuk melakukan pembobolan pada AES dan juga algoritma lainnya.
Materi terkait lainnya:
