TIMING ATTACK PADA RSA

Dewi Setianingrum – NPM 0807100761

Teknik III Teknik Kripto, Sekolah Tinggi Sandi Negara

Abstraksi

Timing attack merupakan sistem yang digunakan untuk mendapatkan informasi kunci

rahasia pada algoritma enkripsi dengan memanfaatkan waktu yang digunakan untuk

algoritma dalam melakukan operasi kriptografi. RSA merupakan salah satu algoritma

yang dapat diserang dengan menggunakan timing attack. Masalah pemfaktoran bilangan

besar pada RSA bukan menjadi fokus dalam timing attack. Timing attack juga dapat

menyerang protokol seperti OpenSSL. Implementasi RSA dalam OpenSSL dapat

diserang dengan menggunakan timing attack.

Kata Kunci: OpenSSL, RSA, Timing attack

1. Pendahuluan

Saat ini keamanan informasi merupakan hal yang penting dalam komunikasi antar

pihak. Terdapat pembagian kategori informasi, yaitu sangat rahasia, rahasia, dan tidak

rahasia. Untuk mengamankan informasi tersebut dengan kriptografi. Dalam

Handbook of Crytography, kriptografi adalah teknik matematika yang bergantung

pada aspek keamanan informasi seperti kerahasiaan, keaslian data, otentikasi pihak

dan data.

Algoritma kriptografi banyak dikembangkan, salah satunya adalah RSA. RSA

merupakan algoritma enkripsi yang dibentuk berdasarkan masalah pemfaktoran

bilangan besar. Banyak algoritma yang dirancang untuk memecahkan masalah

pemfaktoran bilangan besar. Namun, masih memiliki batasan dalam perhitungan

pemfaktoran bilangan besar.

Attack yang digunakan untuk menyerang algoritma RSA bukan hanya melalui

pemfaktoran bilangan besar. Saat ini, terdapat attack yang berorientasi pada

pemfaktoran bilangan besar melainkan memanfaatkan lingkungan kriptografi. Timing

attack merupakan algoritma dapat dirancang untuk mendapatkan informasi private

key dengan memanfaatkan waktu yang digunakan RSA dalam menghitung pangkat

private key.

2. RSA

RSA merupakan algoritma enkripsi public key yang dibuat pada tahun 1977.

Nama RSA berasal dari inisial nama pembuat RSA, yaitu Ronald Rivest, Adi Shamir,

dan Leonard Adlemand. Dasar pembentukan RSA adalah operasi dasar aljabar pada

intejer besar dan kesulitan pada pemfaktoran bilangan intejer besar.

Saat ini banyak dikembangkan algoritma yang dibuat untuk menyelesaikan

masalah pemfaktoran bilangan besar. Namun, dari algoritma pemfaktoran tersebut

masih terdapat batasan dalam bilangan besar. Salah satu algoritma pemfaktoran

bilangan besar adalah GNFS. GNFS dapat menyelesaikan masalah pemfaktoran

bilangan besar berukuran 150 digit.

Algoritma RSA dapat digunakan untuk proses enkripsi, digital signature, dan key

establishment. Selain itu, RSA juga digunakan pada protokol, misal SSL/TLS, SET,

SSH, S/MIME, PGP, dan DNSSEC. RSA menyediakan confidentiality, integrity, dan

authentication.

Algoritma pembangkitan kunci RSA

Setiap pihak membuat public key RSA dan private key yang berkorespondensi. Pihak

A melakukan :

Bangkitkan dua bilangan acak prima berbeda p dan q, memiliki ukuran yang

sama.

Hitung n = pq dan (n) = (p – 1)(q – 1).

Pilih bilangan acak e, 1 < e < , sedemikian sehingga gcd (e, ) = 1.

Gunakan algoritma Extended Euclidean untuk menghitung intejer unik d, 1 < d <

, sedemikian sehingga ed 1 mod (n).

Public key A adalah (e, n), private key A adalah d.

Algoritma enkripsi dan dekripsi public key RSA

Misal B mengenkripsi pesan m pada A, A mendekripsi pesan m.

Enkripsi. Pihak B melakukan :

Peroleh public key otentikasi A (e, n).

Representasikan pesan intejer m dalam interval [0, n – 1].

Hitung c = me mod n.

Kirim ciphertext c ke A.

Dekripsi. Untuk memperoleh plaintext m dari c, A melakukan :

Gunakan private key d untuk mendapatkan m = cd mod n.

Penggunaan RSA untuk enkripsi dan digital signature menyebabkan perbedaan

private key dan public key. Untuk private key pada enkripsi digunakan sebagai public

key pada digital seignature begitu juga sebaliknya. Oleh karena itu, setiap kunci

hanya boleh digunakan untuk satu aplikasi saja.

3. Timing Attack

Timing attack pertama kali diperkenalkan oleh Paul Kocher, konsultan

independent kriptografi, pada tahun 1996. Digunakan untuk menyerang kelemahan

dari peralatan komputasi seperti smartcard. Tujuan timing attack adalah untuk

mendapatakan informasi private key seperti RSA, dengan menghitung waktu yang

dibutuhkan untuk melakukan operasi private key atau dekripsi. Timing attack

termasuk dalam kategori side-channel attack.

Pada dasarnya, konsep timing attack sudah ada pada tahun 1995. Namun, hanya

dapat memperoleh sebagian informasi kunci dan membutuhkan informasi waktu

setiap langkah tanpa operasi kriptografi. Timing attack mulai dikembangkan oleh P.

Kocher sehingga dapat memperoleh seluruh informasi kunci hanya dengan

mengetahui banyaknya waktu yang dibutuhkan untuk operasi tersebut.

Dengan memanfaatkan algoritma key-dependent yang memiliki korelasi antara

input dengan waktu running, timing attack dapat dilakukan misal pada RSA, DSA,

Diffie-Helman, dan RC5. Namun, untuk algoritma yang tidak memiliki korelasi

antara input dan waktu running seperti DES, DESX, Triple-DES, RC2, RC4, dan

variasi message digest, timing attack sulit diterapkan.

Untuk penerapan timing attack sukses digunakan pada protokol SSL seperti

smartcard. Adanya timing attack dapat menjadi noise bagi pengiriman data. Oleh

karena itu, timing attack tidak bisa diterapkan pada operasi yang tidak menggunakan

kondisi eksternal seperti digital signature dan enkripsi secara off-line.

4. Timing Attack pada RSA

Penerapan efektif timing attack pada RSA tepat dilakukan ketika algoritma RSA

diimplementasikan dalam BSAFE dan RSAREF. Timing attack pada RSA

memanfaatkan korelasi antara private key dan runtime operasi kriptografi, yaitu

ekponensial modulus dengan d sebagai bilangan eksponensial.

Untuk menghitung eksponensial modulus menggunakan algoritma repeated

squaring. Jika panjang private key k bit, banyaknya loop running pada d adalah 2k

perkalian modulus. Setiap data dipangkatkan dua dengan perkalian modulus jika bit

yang dipangkatkan tersebut adalah 1. Attacker dapat dengan mudah mendapatkan bit

d diawali dengan LSB terlebih dahulu dengan menghitung runtime operasi private

key pada bilangan acak pesan. Sehingga atacker memperoleh sebagian informasi awal

tentang kunci. Jika pangkat public key yang digunakan kecil, attacker dapat

menemukan kunci bit pertama k/4 dengan metode ini dan sisa bit selanjutnya dapat

didapatkan dengan metode sebelumnya.

Timing attack dapat diatasi dengan mengurangi korelasi antara runtime dengan

pangkat private key. Salah satunya solusi adalah dengan menambahkan delay pada

perhitungan perpengkatan sehingga setiap operasi modulus memiliki waktu yang

sama dan sulit untuk ditemukan perbedaan. Sistem ini dapat bekerja apabila

dilakukan pada smartcard. Solusi yang lain yaitu blinding. Dengan mengubah data

sebelum dipangkatkan dengan private key menggunakan nilai acak yang dibangkitkan

oleh modul kriptografi. Data yang acak tersebut akan menyulitkan attacker untuk

memperoleh informasi mengenai kunci yang digunakan.

Dalam paper yang dibuat oleh Boneh dan Brumley, timing attack dapat dilakukan

dengan jarak jauh pada OpenSSL dengan mengetahui modul kriptografi. Selain itu,

cari ini juga efektif dalam memperoleh private key RSA apabila diimplementasikan

pada modul OpenSSL. Untuk mencegah keberhasilan attacker mendapatkan private

key RSA dapat menggunakan blinding yang diimplementasikan pada OpenSSL tapi

kemungkinan untuk berhasil sekitar 2% - 10%.

Timing attack tidak hanya menyerang RSA namun juga protokol SSL dengan

memanfaatkan perbedaan waktu pada OpenSSL dalam mendeteksi perbedaan error.

Dengan memilih pesan secara teliti ketika menggunakan kunci simetri block cipher

pada mode CBC.

5. Kesimpulan

Timing attack salah satu metode untuk menyerang RSA dengan memanfaatkan

korealsi antara input dengan private key. Mendapatkan informasi private key dengan

menghitung waktu yang diperlukan dalam perhitungan dengan private key atau proses

dekripsi. Algoritma yang menggunakan protokol OpenSSL mudah diserang dengan

timing attack seperti impelementasi RSA dalam OpenSSL.

6. Daftar Pustaka

[1] Alfred J. Menezes, Paul C. van Oorschot, dan Scott A. Vanstone. “Handbook of

Applied Cryptography”. CRC Press. Oktober 1996.

[2] Burt Kaliski. “Timing Attack on Cryptosystems”. RSA Laboratories Bulletin. 23

Januari 1996.

[3] David Brumley dan Dan Boneh. “Remote Timing Attacks are Practical”. 2003.

[4] Reading Room SANS. “Cryptanalysis of RSA: A Survey”. Sans Institute. 2003.

[5] Zhanxiang. “Timing Attacks to RSA”.