Page 117 - bilgem-teknoloji-dergisi-4

Esen AKKEMİK PEDERSEN, Orhun KARA Düzensiz Şifreleme Algoritmasının Gerçek Zamanlı Kriptoanalizi

1
bakılır. Bu değerler eşitse k = kabul edilir ve C t+ 11 … C t+ 18 edilmiş ancak sonraki bir adımda tekrar doğru anahtar Önerme 2: Herhangi bir açık metin karakteri, karşılık gelen t = + 1 ;
t
i
bitleri bir sonraki açık metnin şifrelenmiş hali olarak kabul değerlerine ulaşılmış demektir. şifreli metin karakteri ve BV ’nin bitleri arasında k = k + k ;
edilir. Saldırı bu şekilde sürdürülür. C ile simgelenen şifreli (2) bağıntısı ve Tablo 1’deki değerlerle elde edilen şifreli top top t
metin, eldeki bütün şifreli metinlerin her birini ifade eder. metin sayısı arttıkça saldırıyla tahmin edilen anahtar P ⊕ i C ⊕ i BV = i k 0 , i = 1, …,8 (3) }
Anahtar değeri belirleme işlemi yapılırken şifreli metin dizisinin doğru olma olasılığının arttığı sonucuna varılır. eşitliği vardır. Bu saldırının başarısı, şifre çözme boyunca anahtar için
bitlerinin karşılaştırılmasında eşit olmama durumunun en az Tablo 1’den de görüldüğü gibi yaklaşık 20 şifreli metin, doğru tahminin yapılmasına bağlıdır. Elde S tane açık-şifreli
bir şifreli metinde, eşit olma durumunun da bütün şifreli anahtarın neredeyse % 100 olasılıkla ele geçirilmesi için Kanıt: BV değeri açık metin karakterinin i ’inci bitinin metin çifti olsun. Bu durumda, her bir anahtar adayının (3)
i k
0
metinlerde sağlanması gereklidir. değiştirilip değiştirilmeyeceğini belirler. BV = iken, açık denklemi ile verilen denetim mekanizmasından geçme
yeterli olmaktadır. i k
Bu saldırı algoritma olarak şu şekilde verilir: metin bitleri (değiştirilmeyecekleri için) karşılık gelen şifreli olasılığı 2 − 8S olmaktadır. Dolayısıyla, belirli bir açık metin
Tablo 1. Sadece Şifreli Metin Saldırısında metin bitlerine eşit olacaktır. BV = 1 iken ise açık metin karakterini şifreleyen anahtar değeri dışında en az bir tane
i k
d dizisi açık metin karakterinin olası şifreli halini ve Şifreli Metin Sayısına (S) Karşılık yanlış anahtar gelme olasılığı
BV ’nin en anlamlı bit değerini taşıyan 9 elemanlı diziyi, m Saldırının Yanlış Alarm Olasılığı (P ) karakterindeki i ’inci bit 1 ile ayrıcalıklı veyası alınacaktır. BV
1
değeri de [1,8] aralığında herhangi bir değeri göstersin. m f değeri de 1 olduğundan, (3) eşitliği bu durumda da sağlanır. P =− (1 2− − 8S ) 7 (4)
f
değeri 8’i aştığı zaman algoritma sonlandırılmalıdır. t ’nin S P †
ilk değeri 0 alınarak saldırıya başlanır. f Dikkat edilecek olursa, Önerme 2 Önerme 1’in ifadesi ile verilir.
5 0,2 genelleştirilmiş halidir. Buna karşın, Önerme 1, Sadece
k i− 1 = m ; j = 0 ; 6 0,1 Şifreli Metin çözümlemesinde kullanıldığı için ayrıca Tablo 3. Bilinen Açık Metin Saldırısında
d = { t+ C 1 ,C t + 2 , …,C t + 8 ,C t + 9 } ; 7 0,05 vurgulanmıştır. Açık Metin-Şifreli Metin Çifti Sayısına (S) Karşılık
0,027
Saldırının Yanlış Alarm Olasılığı (P )
8
eğer ( [ ] 1d ≠ d [ ] 9 ) ise { 9 0,014 Bilinen Açık Metin saldırısında da, tıpkı Sadece Şifreli f
( [ ] 1d ≠ d [ ] 9 ) iken { 10 0,0068 Metin saldırısında olduğu gibi her bir karakter için elde S P
f
–6
j
k i − 1 = k i − 1 + 1; j =+ 1; 20 6,6× 10 bulunan verilerden aday anahtar değerleri belirlenir. Bu 5 6,4 × 10 –12
–9
d = { C 1 j ,…,C t+ 8 j ,C t+ 9 j } t++ ; } 30 6,5 × 10 durumda ayırt edici özellik olarak Önerme 1 yerine 6 2,5 × 10 –14
+
+
Önerme 2 kullanılır. Önerme 2’de verilen eşitlik şartını
} 7 9,7 × 10 –17
3.2 Bilinen Açık Metin Çözümlemesi bütün veriler için sağlayan anahtar değerleri aday olarak
eğer ( [ ] 1d = d [ ] 9 ) ise { belirlenir. Diğer taraftan, sadece birkaç tane açık-şifreli 8 3,8 × 10 –19
k = 1; Bu bölümde DŞA’ya bir Bilinen Açık Metin saldırısı metin çifti bile aday olarak sadece gerçek anahtarın 9 1,5 × 10 –21
i
d = { C 10 j ,…,C t + 17 j ,C t + 18 j } t+ ; uygulaması anlatılmaktadır. Bu saldırıda çok daha az veri ile kalmasına yeterli olmaktadır.
+
+
+
} anahtarı bulmak mümkün olabilmektedir. Tablo 3’teki örneklerden de görüleceği gibi saldırının
Algoritma kodu aşağıda verilmiştir. P ile açık metin, d ile yanlış alarm olasılığı son derece düşüktür. Öyle ki, birkaç
Bu saldırının başarısı, şifre çözme boyunca anahtar için Saldırıda açık metin bitlerinin değiştirilip olası şifreli metin, BV ile şifrelemede kullanılacak olası BV, tane açık metin-şifreli metin çifti neredeyse 1 olasılıkla
doğru tahminin yapılmasına bağlıdır. Saldırıda bit değiştirilmeyeceğine karar veren BV bitleri kullanılmaktadır. m ile açık metin karakter sayısı simgelenmektedir. k top , anahtarı tespit etmek için yeterli olmaktadır.
karşılaştırma işleminde her şifreli metin için herhangi bir Saldırının sömürdüğü ayırt edici özellik Önerme 2’de bulunulan adımdan önceki bütün anahtar değerlerinin
adımda Önerme 1 sağlanıyorsa 0, sağlanmıyorsa 1 olacak verilmektedir. Tablo 2’de herhangi bir açık metin toplamını gösterir. Bir dizinin sonuna yeni eleman ekleme Bu saldırıda da, bir önceki saldırıdaki duruma benzer bir
biçimde bir vektör oluşturulsun. Bir karakter şifre çözme karakterinin i ’inci biti şifrelenirken, anahtar değerine bağlı “|” ile gösterilmiştir. durum söz konusu olabilir, yani, yanlış anahtar değeri,
işleminde 8 farklı anahtar değeri için 8 vektör elde edilir. olarak BV ’nin kaçıncı bitinin kullanıldığı gösterilmektedir. ileride tespit edilebilecek bir hataya neden olabileceği gibi,
1
Doğru anahtar için bu vektör 0 vektörü olacaktır. Ancak, Örneğin, anahtar değeri 1 iken her bir i değeri için k = k top = 0 ; t = 0, …,m − 1 { sonradan kendini toparlayan bir duruma da yol açabilir.
i
yanlış anahtar değeri için de sıfır olabilir. Bu durumu olmaktadır. d = { C ,…,C
sağlayan anahtar değerleri saldırıda yanlış alarma, yani + top 1 8tk + + top 8 } 8tk + 4 SONUÇ
+
+
anahtar değeri yanlış iken doğru kabul etmeye neden olur. Tablo 2. Anahtar Değerine Göre P = P 81 , … ,P 8 8 ; Bu çalışmada DŞA’ya biri Sadece Şifreli Metin, diğeri
t
t
Açık Metnin Şifrelenmesinde
Bu durumda, elde olan S tane şifreli metin için herhangi bir BV ’nin Kullanılacak Bitlerinin (k ) Gösterimi k t+ 1 = 1 ; Bilinen Açık Metin olmak üzere iki saldırı anlatılmıştır. Bu
+
adımdaki yanlış alarm olasılığı i ind = 8t + 8 k top + 1 ; saldırılar algoritmaya uygulanan ilk saldırılardır ve
P =− (f − − S )1 2 7 (2) K k k k k k k k k BV = C ind ; karmaşıklıkları son derece düşüktür. Sonuç olarak, DŞA’nın
1
8
3
4
1
2
6
7
5
son derece zayıf bir algoritma olduğu anlaşılmaktadır.
1 1 1 1 1 1 1 1 1 i = 1, …,8 {
olarak hesaplanır. 2 1 1 1 1 2 2 2 2 d ⊕ i P ⊕ i BV ≠ i k 0 ise { EK 1 SALDIRI ÖRNEKLERİ
Bir karakter için birden fazla 0 vektör olması, birden 3 1 1 1 2 2 2 3 3 k t + 1 = k t + 1 + 1 ; Bu bölümde Sadece Şifreli Metin ve Bilinen Açık Metin
fazla anahtarın şifre çözme işleminde kullanılabileceğinin 4 1 1 2 2 3 3 4 4 ind = ind 1 ; saldırılarına birer örnek verilecektir.
+
göstergesidir. Ancak, bu durum sonraki karakterlerin şifre 5 1 1 2 2 3 3 4 5 BV = BV|C ;
çözümünde uyumsuzluk yaratıp hatayı tespit etme olanağı 6 1 1 2 2 3 4 5 6 ind EK 1.1 Sadece Şifreli Metin Saldırısı
i k
oluşturabileceği gibi, yapılan bir hata başka hatalarla birleşip 7 1 1 2 3 4 5 6 7 d ⊕ i P ⊕ i BV ’yi hesapla;
doğru karakter-BV çiftine tekrar ulaşabilir. Böyle bir 8 1 2 3 4 5 6 7 8 } Elde aynı anahtar dizisi ile şifrelenmiş 3 tane şifreli metin
durumda, bir adımdan sonra bir grup anahtar yanlış tahmin } olsun. Açık metnin ilk bitinin 0 olduğu da bilinsin
(alfanümerik karakterler durumu). Bu durumda
114 Sayı 03 Mayıs-Ağustos 2010 http://www.uekae.tubitak.gov.tr/ 115
·