RSA Algoritması Hata Analizi

Bu yazı, 1997-2016 yılları arasında RSA algoritmasına yapılan hata enjekte etme ataklarının bir derlemesidir. 

GİRİŞ

Hata analizi, bir sisteme çeşitli şekillerle hata yaptırılması sonucunda oluşan çıktıların yorumlanması ile gizli bilgi çıkarımında bulunma işlemidir. Hata analizi güç veya toprak ucundan yapılabilir. Hata enjekte edilmiş sistemlerin hatalı sonuçlarının incelenmesi de hata analizinin bir yöntemidir. RSA algoritması gibi gizli anahtarların kritik olduğu sistemlerde, hatalı sonuçların doğru sonuçlarla karşılaştırılması anahtar hakkında bilgi vermektedir. Bu nedenle sistemler hata ataklarını anlayacak ve bir hata olduğunda dışarıya çıktı vermeyecek şekilde tasarlanmaktadır.

HATA ANALİZİ

Hata analizi çeşitli şekillerde yapılabilmektedir. Aşağıda literatürde yer alan hata analiz yöntemleri anlatılmıştır:

Voltaj Atağı

Sistemlerin normal çalışma aralıklarına müdahalede bulunulur. Sistemler normal çalışma aralığının altında veya üstünde çalıştırılır. Ortaya çıkan bu kararsız durumda cihaz anormal davranışlar göstererek eksik tur sayısı (AES gibi algoritmalar için), eksik imzalama işlemleri (RSA, ECC) gibi anormal sonuçlar ortaya çıkarabilir. Sistemlerde bu atakların önüne geçilmek için voltaj sensörleriyle önlemler alınmaktadır. Maliyeti düşük bir atak olması sebebiyle kolaylıkla gerçekleştirilebilmektedir.

Saat Aksatma Atakları

Bir sistem dışarıdan saat üretimine gerek duyuyor olabilir. Sistemde bu saat girişine müdahalede bulunularak sistemde hatalar yaptırılmaktadır. Meydana getirilen bu hatalar sistemlerde kararsızlıklara yol açmaktadır. Bu hata sonucunda kritik veriler yazılmaması gereken bellek bölgelerine yazılabilmektedir. Bu durum ciddi güvenlik açıklıklarına sebep vermekte ve sistem koruması gereken gizli bilgileri güvensiz ortamlara sızdırmış olmaktadır. Voltaj atağı gibi bu atağın da maliyeti düşüktür ve bu atak da kolaylıkla gerçekleştirilebilmektedir. Sistemlerde bu tür atakların önüne geçilebilmek için, saat bilgisi devre içerisinde üretilmekte ve mümkün olduğunca dışarıdan saat bilgisi alınmamaya çalışılmaktadır. Ayrıca saat bilgisi kontrol mekanizmalarıyla özellikle kritik işlemlerden önce kontrol edilmektedir. Herhangi bir hata durumunda sistem kendisini korumaya almaktadır.

Isı Atakları

Bu atakta, sistem normal çalışma ısısının dışında çalıştırılır. Atak, belleklerde depolanan verilerin değiştirilmesi için uygulanır. Ancak verilerin belirli kısımlarına odaklanmak zor olduğu için uygulanabilirliği düşük bir ataktır. Sistemlerde bu atakların önüne geçilmek için ısı sensörleri kullanılmaktadır.

Optik Ataklar

Sistemlere yoğun ışık uygulanarak gerçekleştirilen ataklardır. Atağın temeli iletkenlerin ve yarı iletkenlerin lazer izolasyonuna duyarlı olmasına dayanmaktadır. Bir ışık palsına maruz kalan transistörlerde değişimler meydana gelmektedir. Odaklanmış bir iyon demeti kullanılarak, belleklerde bir bit, set ya da reset edilebilir. Pahalı bir yöntemdir. Uygulanabilirliği yüksektir. Sistemlerde bu atağın önüne geçmek için aktif kalkan yapısı kullanılmaktadır. Ancak FIB(Focused Ion Beam) gibi gelişmiş cihazlarla aktif kalkan by-pass edilerek bu atak uygulanabilir hale getirilebilmektedir.

Odaklanmış Bir Lazer Işını Etkisi

Elektromanyetik Ataklar

Bir çipe dış manyetik alan kullanılarak hata eklenebilir veya herhangi bir bellek bölgesindeki veriler değiştirilebilir. Çip yüzeyi yoğun bir manyetik girdaba maruz bırakılır. Çipin fiziksel kısmı manipüle edilerek transistörler arası anormal geçişler elde edilebilir.

RSA Algoritması Ve RSA-CRT

RSA, güvenliği tam sayıları çarpanlarına ayırmanın zorluğuna dayanan açık anahtarlı bir şifreleme yöntemidir. 1978’de Ron Rivest, Adi Shamir ve Leonard Adleman tarafından geliştirilmiştir. Günümüzde 2048 bit ve üzeri güvenli kabul edilmektedir.

Aşağıda RSA algoritması matematiksel olarak ifade edilmiştir:

p ve q asal olmak üzere,

N = p*q

Φ (n) = (p-1)*(q-1)

e, 1 < e < Φ (n)

d, d*e ≡ 1 mod(Φ (n))

Şifreleme:

c = m^e (mod n)

Şifre Çözme:

m = c^d  (mod n)

RSA algoritması yavaş çalışan bir algoritmadır. Bu durum performans açısından RSA’i olumsuz etkilemektedir. Güvenlik gerekçesiyle anahtar bit boyutları artırıldıkça, bu sorun daha da aşılamaz hale gelmektedir. Bu nedenle RSA algoritmasının hız açısından iyileştirilmesi için çalışmalar yapılmaktadır. RSA-CRT de bu yönde ortaya atılmış bir çözümdür. RSA algoritmasının hızlandırılmış olarak implemente edilmiş halidir. Çinli Kalan Teoremi’nin RSA algoritmasının hesaplanmasında kullanılmasıdır.

Aşağıda RSA-CRT algoritması matematiksel olarak ifade edilmiştir:

d mod (p-1) = e^-1 mod (p-1)

d mod (q-1) = e^-1 mod (q-1)

d_p = d mod (p-1)

d_q = d mod (q-1)

Q_inv = q^-1 mod p

S_p = M^dp mod p

S_q = M^dq mod q

S = (((Sp – Sq)*Qinv) mod p)*q + Sq

RSA algoritması bir sistemde gerçeklenirken(özellikle akıllı kartlarda), RSA performansının artırılması için RSA-CRT olarak implemente edilir. Bu nedenle literatür incelendiğinde RSA-CRT implementasyonuna yapılan atakların daha fazla olduğu görülmektedir. 

RSA Algoritması’na Hata Ekleme Noktaları

RSA algoritmasına hata üç farklı yerde enjekte edilebilir:

1. Giriş parametrelerine hata yaptırılabilir. Özel giriş değerleri ile sistemden, gizli anahtar değerleriyle ilgili bilgi vermesi beklenir.
2. İşlem esnasında hata yaptırılabilir. RSA işlemi gerçekleştirilirken sisteme müdahale edilir. Bu müdahale ile sistemin işlemleri eksik yapması sağlanır.
3. Program akışına hata yaptırılabilir. Sistemde hata sonucunda ortaya çıkan kararsız yapıyla, sistemin işlem sırasını karıştırması sağlanabilir.

Literatürde RSA Hata Analizi

Bu bölümde literatürde yer alan RSA algoritmasına yapılan hata atakları anlatılacaktır. 

Hatalı Üs Atağı

1997 yılında, önlemsiz RSA algoritmasına, El Gamal ve Schnorr imzalama şemasına yapılan bir ataktır. Üs alma işleminde herhangi bir yere rastgele hata yaptırılır. Sonuç yorumlanır hata yaptırılan bitin gerçek değeri öğrenilir.

Aşağıda matematiksel olarak atak açıklanmıştır:

Hatasız mesaj:

m = c^d mod n

Hatalı mesaj:

m’ = c^d’ mod n

Hata yaptırılan bit d_j olsun

Bellcore Atağı

Atak, 1997 yılında Bellcore Laboratuvarları çalışanları tarafından gerçekleştirilmiştir. Teorik bir model olarak sunulmuştur. RSA-CRT algoritmasının önlemsiz haline yapılan bir ataktır. Algoritmanın çalışması esnasında S_p ya da S_q bileşenlerinden birinin herhangi bir kısmına rastgele hata yaptırılır. Hatasız sonuçla hatalı sonucun birlikte analiz edilmesiyle p ve q değerlerine ulaşılır.

Aşağıda Bellcore atağı matematiksel olarak anlatılmıştır:

Hatasız RSA-CRT sonucu:

S = (((Sp – Sq)*Qinv) mod p)*q + Sq

Hatalı RSA-CRT sonucu:

S’ = (((Sp’ – Sq)*Qinv) mod p)*q + Sq (Burada S_p bileşenine hata yaptırılmıştır)

İki işlemin fark değeri hesaplanır:

S-S’ = (((S_p – S_q)*Qinv) mod p)*q - (((S’_p – S_q) * Qinv) mod p)*q

Sonuç:

Eğer S-S’ işleminin sonucu p değerine bölünmüyorsa;

gcd(S-S’, N) = q değerini vermektedir.

p = n/q eşitliğinden p değeri de hesaplanır. Böylece gizli olan p ve q değerleri elde edilmiş olur.

Bellcore atağından sonra RSA-CRT algoritması için önlemler geliştirilmiş ve doğrudan p ve q değerlerine erişimin önüne geçilme çalışmaları yapılmıştır.

RSA-CRT Optik ve EM Atağı

2007 yılında Jörn-Marc Schmidt ve Michael Hutter tarafından geliştirilmiş bir ataktır. Atakta fiber optik ışıkları kullanılmıştır. Ayrıca makalede yüksek frekanslı kıvılcım boşlukları kullanılarak yeni bir non-invasive elektromanyetik hata saldırısı anlatılmaktadır. Tüm saldırıların low-cost olduğu iddia edilmiştir.

Atakta yapılan işlemin matematiksel ifadesi aşağıdaki gibidir:

p ve q 1024 bit iki asal,

z = CRT(x,y)

z ϵ Z_n

CRT (x, y) = xc_p + yc_q mod n

c_p = q (q^-1 mod p)        (Gauss Algoritması)

c_q = p (p^-1 mod q)

S = m^d mod n, m mesaj

Hatasız RSA-CRT işlemi

S = CRT ((m^d mod p), (m^d mod q)) mod n:

Hatalı RSA-CRT işlemi

S’ = CRT ((m mod p)^d, (m mod q)^d + ∆) mod n

     = m^d + ∆ p (p^-1 mod q) mod n,   ∆ → hata

Sonuç:

p = gcd( S’ – S, n) ya da

p = gcd( S’^e – m, n)

Perturbating RSA Public Keys

Atak, imza şemasında üs hesaplanması sırasında public olan modülüsün değiştirilmesine dayanmaktadır. Bilgisayarlarda kullanılan GMP kütüphanesine aktif olarak yapılmış bir ataktır.

R₈, 0’dan farklı rastgele byte değeri

Yapılan hata geçicidir ve üs sonuna kadar bu modifiye edilen üs kullanılır. Örneğin hatanın, sağdan-sola üs alma algoritmasında uygulandığı varsayılırsa, hata kare alma ya da çarpma işlemi sırasında enjekte edilebilir.

Brier Atağı

2006 yılında CHES’de sunulmuş bir ataktır. Public parametrelerin (modülüs) değeri bozularak public şifreleme üzerinde hata analizi anlatılmaktadır. Public anahtarların güvenliği çok önemsenmediği için motivasyonu yüksek bir atak olarak kabul edilmiştir. Atak standart RSA algoritmasına yapılmıştır, ancak RSA-CRT ve diğer RSA implementasyonları için de geçerli olduğu iddia edilmiştir. Pratik olarak gerçeklenmemiştir, ancak güçlü simülasyonlar aracılığıyla doğrulanmıştır.

Atakta, saldırgan bilinen farklı girişler için birçok hatalı imza elde edebilmelidir. Saldırgan hatalı hesaplanan birçok modulüs elde eder.

Seifert Atağı

Seifert, public parametreler kullanarak atak yapan ilk kişidir. Modülüse yönelik bir ataktır. Seifert Atağı iki aşamadan aluşmaktadır. İlki off-line mod, diğeri de on-line moddur. İlk modda değiştirilmiş bir modülüs bulma ve imza üretme işlemleri yer alır. Ikinci modda ise üretilen bu hatalı imzanın doğrulanması işlemi vardır. Saldırgan burada iki aşamada da hata saldırısını gerçekleştirmelidir. Bu iki sonuç birbiriyle uyuşmalıdır.

Aumüller Atağı

Aumüller atağı Bellcore atağına benzemektedir. RSA-CRT hesaplanırken, S_p ya da S_q bileşenlerinden birisine hata yaptırılır. Analiz kısmında Aumüller, Bellcore’dan farklı bir yöntem denemektedir.

Aumüller atağının matematiksel ifadesi aşağıdaki gibidir:

S = (((Sp – Sq)*Qinv) mod p)*q + Sq

S’ = (((Sp’ – Sq)*Qinv) mod p)*q + Sq

S – S’ ≠ 0

S – S’ ≡ 0 mod q

gcd (( m – (S’)^e) mod n, n) = q

Wagner Atağı

Blömer, Otto ve Seifert tarafından yayınlanan Bellcore ataklarına dayanıklı RSA algoritmasına yapılan bir ataktır. Atak yayınlandıktan sonra yeni bir yayınlanan makaleyle [11] Blömer ve Otto tarafından konuya açıklık getirilmiş ve algoritmanın hala güçlü olduğu iddia edilmiştir.

Sonuç

Bu çalışmayla, son yıllarda RSA algoritmasına yapılan ataklar incelenmiştir. Ataklar aşağıdaki tabloyla gruplandırılmıştır. Bu tabloda ataklar, RSA algoritmasının hangi aşamasına atak yapıldığına göre sınıflandırılmıştır.

Son yıllardaki ataklar incelendiğinde, motivasyonun yüksek olmasından dolayı public verilere ataklarda bir artış görülmüştür. Makaleler incelendiğinde atakların düşük maliyetle gerçekleştirilebileceği sonucuna varılmıştır.

Ayrıca makaleler incelendiğinde, RSA algoritmasına hata yaptırılması sırasında, yeri doğru olmak şartıyla herhangi bir byte ya da bit değerine hata yaptırmanın atağı başarılı bir şekilde sonlandırmada yeterli olduğu görülmüştür. Bu durum da RSA algoritmasına yapılan ataklar da motivasyonu artıran diğer bir etken olarak yerini almaktadır.

Kaynakça

1. D.Karaklajic, Schmidt and I.Verbauwhede “Hardware Designer’s Guide to Fault Attacks”, Ekim 2013.
2. Jörn-Marc Schmidt, “Differential Fault Analysis”, Haziran 2008
3. Bao, F, Deng, R., Han, Y., Jeng, A., Narasimhalu, A.D., Ngair, T.-H., “Breaking Public Key Cryptosystems an Tamper Resistance Devices in the Presence of Transient Fault”, 1997
4. D.Boneh, R.ADeMillo and R.J.Lipton “On the Importance of Checking Cryptographic Protocols for Faults”, 1997
5. Jörn-Marc Schmidt and Michael Hutter, “Optical and EM Fault-Attacks on CRT-based RSA: Concrete Results”, 2007
6. Alexandre Berzati, Cecile Canovas and Louis Goubin, “Perturbating RSA Public Keys: An Improved Attack”, 2008
7. Brier, E., Chevallier-Mames, B., Ciet, M., Clavier, C., “Why one should also secure RSA public key elements”, 2006
8. Seifert, J.-P., “On Authenticated Computing and RSA-based Authentication”, 2005
9. C. Aumüller, P. Bier, W. Fischer, P. Hofreiter, and J.-P. Seifert, “Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures”, 2002
10. David Wagner, “Cryptanalysis of a provably secure CRT-RSA algorithm”, 2002
11. Johannes Blömer, and Martin Otto, “Wagner’s Attack on a Secure CRT-RSA Algorithm Reconsidered”, 2006