Yazan: Bağış Can Rona

Stream Cipher, rastgele alınmış kısa bir karakter dizisini daha uzun bir dizi haline getiren şifreleme algoritmasıdır. Giriş karakter dizisi “anahtar” olarak adlandırılırken, uzun çıkış karakter dizisi ise şifrenin “akışı” olarak adlandırılır. Stream Cipher paylaşılan anahtar şifreleme yöntemlerinde kullanılır. Scream Cipher’ın amacı ise yazılımlara çok hızlı uygulanabilen Stream Cipher’ı dizayn etmektir.

Scream Cipher’ın dizayn edilmesi

Scream Cipher’ı anlayabilmek için öncelikle Scream-0’ı anlamak gerekir. SEAL gibi bu şifreleme yöntemi de güvenliği arttırmak adına “yuvarlama fonksiyonu” etrafında dizayn edildi. Öncelikle tasarımda AES’in temelini oluşturan Rijndael’in yuvarlama fonksiyonu denendi ancak, Scream Cipher’ın dizaynına uygun olmadığı düşünüldü.

Scream Cipher’da kullanılan yuvarlama fonksiyonu Rijndael’in yuvarlama fonksiyonun küçültülmüş bir halidir ve 64 Bit Bloklar üzerinde çalışır. Giriş bloğu 2 x 4 matris olarak görünür. Öncelikle her bayt S-Box (S-kutusu) içerisinden S[x] e gönderilir, yer değiştirme işlemi, daha sonra ikinci satırdaki baytlar teker teker sağa dairesel olarak kaydırılır, en son olarak ise bütün sütunlar 2 x 2 lik geri dönüşebilen matris olan M ile çarpılır. Bu fonksiyona “yarı yuvarlama fonksiyonu” denir ve G_S,M(x) olarak ifade edilir. Aşağıda bu fonksiyon görülebilir.

Scream-0’ın tasarımında kullanılan yuvarlama fonksiyonu, F(x), yarı yuvarlama fonksiyonunun 2 tane örneğini kullanır. (G_{S1, M1} , G_S2M2). Burada S1 ve S2 ler farklı S-Box ları ve M1 ve M2 matrisleri de farklı matrislerdir. S1 ve S2 “box”ları Rijndael’in S-Box’undan türetilmiştir. S[] Rijndael’in S-Box’u iken ,bu S-Boxların ayarları şöyledir:

S1[x] = S[x], S2[x] = S[x xor 00010101].

“00010101” sabitinin seçilmesinin sebebi , 21 sayısı sayesinde S2’nin bir sabit noktası ve ters sabit noktası olmayacak olmasıdır. (s[x] = x’ gibi) M1 ve M2 matrisleri ise tersi alınabilir matrisler olduğu için seçilmiştir ve bu matrisler ve M2^-1M1 hiçbir zaman 0 içermez.

Matrisleri bu yöntemde kullanılır ve, bu matrislerdeki 1,x,x+1 değerleri, Z₂[x]=(x⁸+x⁷+x⁶+x+1) ile ifade edilen, GF(2⁸) fonksiyonunun elemanlarıdır.

F fonksiyonu, Fiestel Merdiveni ve SP(Substitute,Permutation) ağının bir karışımıdır. F fonksiyonunun PseudoCode’ u aşağıdaki gibidir.

1. X, 2 X 4 lük iki matrise ayrılır.

A :=

x0 x4 x8 x12

x1 x5 x9 x13

B :=

x2 x6 x10 x14

x3 x7 x11 x15

2. B := B xor GS2;M2(A) // A, A ve B’yi modifiye için kullanılır.

3. A := GS1;M1(A)

4. B :=

B0,2 B0,3 B0,0 B0,1

B1,2 B1,3 B1,0 B1,1

// B, 2 sütun ile döndürülür.

5. Swap A – B

6. B := B xor GS2;M2(A) // A A,B’yi modifiye için kullanılır.

7. A := GS1;M1(A)

8. A,B deki 16 bayt X içinde toplanır.

x0 := (A0,0 A1,0 B0,0 B1,0 A0,1 A1,1 B0,1 B1,1 A0,2 A1,2 B0,2 B1,2 A0,3 A1,3 B0,3 B1,3)

F döndürme fonksiyonu Şekil 2’de gösterilmiştir.

ŞEKİL 2 F fonksiyonu

Scream-0 ‘ın ana döngüsü

SEAL gibi, Scream-0’da “değişen durum” olarak X, yuvarlama anahtarları olarak Y,Z ve maske tablosu olarak W bulunur. X,Y,Z 16 bayt uzunluğundaki bloklardır, W ise her biri 16 bayt uzunluğundaki 16 bloğu temsil eder. Scream-0’ın her i. adımında ayarıyla modifiye edilir ve bu işlem sonunda çıktı olarak elde edilir.

Scream-0 ‘da maske tablo ve yuvarlama anahtarları hesaplama boyunca modifiye edilir. Spesifik olarak, W’nin her geçişinde ( örneğin her 16 adımda), Y,Z ve W tablosunda bir değer F fonksiyonundan geçirilerek değiştirilir.

W tablosundaki değerlerin değiştirilmesi şu sırayla olur: Tablodan j. geçişten sonra tablo üzerinde W[j mod 16]değeri değiştirilir. Bunun yanında, X ve Y’yi korumak yerine, y her kullanımdan sonra birkaç bayt döndürülür. Döndürülme değeri 32 bit ve 64 bit lik makinelerde “neredeyse özgür” olacak şekilde belirlenir. Bu basit ölçüm “alçak difüzyon saldırısı” ve doğrusal analize karşı güvenlik sağlar.

Scream-0’ın PseudoCode’u ŞEKİL 3’teki gibidir:

ŞEKİL 3 Scream ve Scream-0’ın ana gövdesi

Anahtar ve Sözcük oluşturulması

Anahtar ve sözcüklerin oluşturulması için; lazım olan kadar sayı üretmek için F fonksiyonu kullanılır. Anahtar oluşturulması rutini W tablosunu başlangıç değerleri ile doldurur. Bu değerler daha sonra sözcük (nonce) oluşturulması sırasında modifiye edilir.

Bu iki prosedür ŞEKİL 4 ve ŞEKİL 5’te gösterilmiştir.

ŞEKİL 4 Anahtar Oluşturma Fonksiyonu

ŞEKİL 5 Kelime türetme Fonksiyonu

Scream Cipher

Scream Cipher, Scream-0’a oldukça benzer. Aradaki tek fark, S-Boxları Rijndael S-Box’undan anahtar bağımlı olarak almamızdır. Yukarıdaki Key Formülündeki 4.satır şöyle değiştirilir:

S1[x] := S[…S[S[x + seed0] + seed1] … + seed15]

Yazılımsal hız olarak karşılaştıracak olursak, Scream-S, Scream-0’dan daha hızlıdır.

Uygulama ve Performans

F fonksiyonunun yazılımsal uygulaması : F fonksiyonunun hızlı biçimde uygulanması aşağıdaki gibidir:

İki “yarım yuvarlama fonksiyonu” olan G_S1, _M1 ve G_S2,M2 , sadece 256 tane 4 baytlık kelimeden oluşan iki tabloda 8 tane arama yapılarak, beraber gerçeklenir. GS1M1 ve GS2M2 ‘nin 8 baytlık girdi (x0,x1,x4,x5,x8,x9,x12,x13) olarak gösterilirken, çıkışlar sırasıyla (u1,u4,u5,u8,u9,u12,u13) ve (u2,u3,u6,u7,u10,u11,u14,u15) olarak gösterilir. Ve şu eşitlikler yazılabilir:

Aynı zamanda, i ve j giriş matrisinin satır ve sütunlarını göstermek üzere, benzer eşitlikler diğer u baytları için de yazılabilir. Bu durumda tablolarımız olan T1 ve T2’yi şöyle ifade edersek,

hesaplamalarını yapabiliriz. İyileştirilmiş F fonksiyonu 32 bit makinede aşağıdaki gibi çalışacaktır:

Kelime kurma rutini : Kelime kurma rutini ilk çıktı bloğunun mümkün olan en kısa sürede hesaplanması amacıyla dizayn edilir. Her ne kadar, W tablosundaki bütün girişler kelime kurma işlemi sırasında modifiye edilmek zorundaysa da, uygulama, hepsini kullanmaz ve sadece ihtiyacı olan kadarını modifiye eder. Bu yüzden, sadece birkaç girdi için çıktıyı hesaplayan uygulama , bütün kelime kurma işlemini tamamlamak zorunda değildir.

Yazılımdaki Performans : İki ayrı sistemde yapılan deneme sonuçları aşağıdaki gibidir:

*Tabloda “throughput” (paketlerin zamana oranı) değeri hesaplanırken, prosedürün 256MB çıktı üretme süresi hesaplanmıştır.

Gerçekleme işlemi, Rijndael fonksiyonunda olduğu gibi, bir çok sistemde yapılabilir. Ancak, Scream çok küçük hafızalı sistemler için uygun değildir, bunun yanında 400 bayt memorylik sistemlerde çok yavaş olsa da uygulanabilir.

Güvenlik Analizi

Scream Cipher’a uygulanacak saldırıları incelediğimizde 2 farkı saldırı tipiyle karşılaşıyoruz. Bunlardan birincisi F fonksiyonuna lineer yaklaşım ile yapılan lineer saldırı, ikincisi ise bir F fonksiyonunun sağladığı “alçak difüzyon”( Low Diffusion) u sömüren saldırıdır. Bu iki saldırının da amacı, tamamen rastgele üretilmiş bir akıştan şifrenin çıktısını açığa çıkarmaktır.

Lineer Saldırı

Şifrelemede kullanılan F fonksiyonu 8*8 S-Box ların 3 tanesine yaklaşan bir yaklaşıma sahiptir. Scream-0’ın S-Box ları Rijndael’in S-Box larına dayandığı için, onların en iyi yaklaşımı 2^-3 eğilimine sahiptir, ve bu yüzden F fonksiyonunun yaklaşımını 2^-9 eğilimle elde edebiliriz.

Prx[L(x,F(x)) = 0] = (1+-2^-9)/2 şeklinde bir L fonksiyonumuz olsun. Bu yaklaşımı uygulamak için; öncelikle y,z,W[i] lerle tanımlanmış, lineer maskelemeyi elememiz lazım. Burada şu gerçeği kullanacağız : Bu maskelerden her biri modifiye edilmeden önce 16 defa kullanılmıştır. Şifrelemenin her adımında, saldırgan “x”in rastgele olduğu ,bir çift görecektir.

Lineer yaklaşım L’yi, bu çifte uygularsak;

şeklinde biti elde ederiz. Bu biti a ile gösteriyoruz.

Basitleştirmek için, her adımdan sonraki y nin rotasyonunu yok sayıyoruz. Aynı y ve z bloklarını kullanan iki tane a’yı eklersek ;

şeklinde bir “r” elde edeceğiz. Bundan sonra son bit y ve z’den bağımsız olacaktır. Aynı maskeleri kullanan r’leri toplama işlemine sokarsak bunun sonucunda;

şeklinde m bitine ulaşabiliriz.

L(x,F(x))’in 2^-9 eğilimi olduğundan, m biti 2^-36 eğilimine sahiptir, bu yüzden biz de 2⁷² bit gördükten sonra, rastgele değerden şifreyi açığa çıkarabiliriz.

Her maske kullanılmadan önce 16 defa modifiye edildiğinden ötürü, sayıda eklenecek a çifti seçeneği ve sayıda eklenecek r çiftine sahibiz. Şifrelemenin 256 adımı bize M biti verecektir.

256. 2⁵⁸ = 2⁶⁶ şifreleme adımını gördükten sonra ( örneğin 70 baytlık çıktı için), ihtiyacımız olan 2⁷² tane m biti ile şifrelemeyi açığa çıkarabiliriz.

y’nin rotasyonu:

y’nin rotasyonu saldırıları planlamayı zorlaştırır. Hem y hem z bloklarını iptal edebilmek için, aynı çıktı örüntüsüyle iki farklı yaklaşım uygulayan, ama girdi örüntüsü sırayla dönen birine sahip olmamız gerekir.

Gizli S-Boxlar

S-Boxlar anahtar-bağımlı olduklarından ötürü, saldırgan “en iyi yaklaşımı” bulamaz, ama bir yandan da S-Boxlar, Rijndael Boxlarından daha iyi yaklaşıma sahiptirler. Bundan ötürü, saldırgan en iyi yaklaşıma kadar iyi olan rastgele yaklaşımı kullanabilir.

Kelime Kurma prosedürü

Saldırı modelimizde, saldırgan şifreyi çok sayıda kelime ile besleyebilir. Bunun neden daha verimli saldırı olduğunu anlamak için, eğer kelime kurma prosedüründen maske modifiye işlemini elediğimizi düşünelim. Saldırgan bu sayede, her kelime için sadece ilk birkaç çıktı bloğunu gözleyerek, şifreyi bir den fazla kelime ile besleyebilecektir. Bu işlemde maskeler artık ayarlanmıştır ve bir daha iptal edilmelerine gerek yoktur. Burada tek iptal edilmesi gereken y ve z bloklarıdır ve saldırgan her kelimeye iki adımda yaklaşarak bunu çok rahat yapabilir. Bu, bu yaklaşımın 2^-18 yaklaşımı olduğunu gösterir ve bu durumda da saldırgan rastgele kelimelerden şifreyi açığa çıkarmak için sadece 2³⁶ farklı kelimeye ihtiyaç duyacaktır.

En kolay ayarlama, bütün maskeleri kelime kurma işlemi sırasında modifiye etmektir. Ancak bunu yapmak pahalı bir işlemdir. Bu yüzden bunu sağlamak için , farklı girişleri farklı değer ile toplayarak, aynı girişleri ise aynı değer ile toplayarak modifiye ettik. Bunun yardım sağladığı nokta, her adımın yaklaşımının bir aynı ve bir farklı maskeye içermesidir. Böylece hala daha farklı maskeleri iptal etmek için en az 4 yaklaşıma ihtiyaç duyulur.

Farklı adımlarda maskelerden kaçınmanın tek yolu, düşük bir eğilime sahip olan, 2 F fonksiyonuna ardı ardına yaklaşım, işlemini kullanmaktır. Ayrıca, aynı maskelere eklenen değerleri de y ve z bloklarını da iptal edebiliriz, ve bunu 2 adımda yapabilmek için;

1. Fonksiyonun girdilerinde ve çıktılarında aynı bitlerin örüntüsünün kullanılması
   
2. Bitlerin örüntüsünün periyodik olması
   

özelliklerine sahip en az bir F fonksiyonunun yaklaşımının kullanılması gerekir.

Bütün S-Box’ların kullanmasından daha az S-Box kullanan bir yaklaşım bulunmamaktadır.

Düşük Difüzyon Saldırısı

Düşük difüzyon saldırısı, x’in her baytı için etkilenmeyen F(x) baytını sömürür.

Bu saldırıda da Lineer saldırıdaki gibi, önce y,z, w[i] ile tanıtılmış lineer maskelemeyi yok etmeye çalışıyoruz. Gene y bloğunun rotasyonunu yok sayıyoruz. Saldırgan, şifrelemenin her adımında 4 baytlık fonksiyonunu görüyor. Aynı y ve z bloklarını kullanan bir değeri, y ve z ye ekleyerek ikisi arasındaki bağımlılığı yok ediyoruz. Bu da bize 4 baytlık bir değer olan veriyor.

Y ve Z bloklarına olan bağımlılığı ortadan kaldırmak için, aynı y ve z bloğunu kullanan değerleri ekliyoruz. Ve bu da bize 4 baytlık değerini veriyor.

Bunların iki tanesine aynı i ve j yi eklersek, 4 baytlık elde ediyoruz.

Bu son değeri, s,t,u,v ‘nin 3 bayt uzunluğunda ve her g(x)’in 1 bayt uzunluğunda olduğu bir durumda, g fonksiyonuna göre,
çifti olarak yazabiliriz.

Bu denklemleri istatistiksel olarak analiz ettiğimizde, şifreyi açığa çıkarmamız için gerekli olan örnek sayısını bulabiliyoruz.

y’nin rotasyonu : y’nin rotasyonu saldırıyı yukarıda da söylendiği gibi zorlaştıran bir etmendir. Biz, şifreyi çözmek için gerekli çıktı uzunluğunun 2⁴³ bayt olmasını tahmin ediyoruz. Bunun yanında, açığa çıkarma işlemi oldukça pahalı bir işlemdir. Bunun yanında, 2⁴³ baytı kullanmak için 2⁵⁰ alan ve 2⁸⁰ zamana ihtiyacımız var.

Gizli S-Boxlar : Şu anda gizli S-Boxlar ile ilgili, düşük difüzyon saldırısını ne kadar genişletmemiz gerektiğini bilemiyoruz Ancak inandığımız bir şey var ki; bazı değişkenler, bizim saldırgana görmesi için verdiğimiz 2⁶⁴ bayttan daha fazla metin gerektirmektedir.

Scream-F Şifrelemesi

Scream’de, düşük difüzyon saldırısından korunmak için gizli S-Box lar kullanılır. Bu gizli S-Boxlar anahtar bağımlıdır. Bunun yerine yapılabilecek bir çözüm daha vardır. O da S-Boxları sabit tutarak, anahtar bağımlılık işlemini, her bloğun çıkışından önce, şifrelemenin ana gövdesine koymaktır. Scream-F anahtar bağımlı tabloyu kullanarak bu yaklaşımı alır. Ama, elimizdeki tek anahtar bağımlı tablomuz W tablosudur, ve biz W tablosunu aynı zaman S-Box olarak da tanımlıyoruz.

Spesifik olarak da, aşağıdaki kodu Figür 3’teki 3.satırın altına yazıyoruz.

Xi ^00111110 operasyonu 0 ile 62 arasında aynı numara döndürmektedir. Biz de W’nin aynı girişlerini x0..3 ve x8..11 i modifiye etmek için, farklı girişlerini ise x4…7 ve x12..15 i modifiye etmek için kullanıyoruz. Bunun sebebi x0..3 ve x8..11 i W’nin aynı değerleriyle maskelemek, x4..7 ve x12..15 i de W’nin farklı değerleriyle maskelemektir. Bu aynı/farklı indekslemenin sağladığı şey ise, Feistel operasyonundaki girişler kullanılarak maskelerin iptal edilmesi ihtimalini ortadan kaldırmaktır.

Sonuç

Scream, SEAL ile aynı şekilde dizayn edilmiştir. Ancak, Scream SEAL’den daha hızlı ve daha güvenli olarak düşünülmektedir. Gerçeklenme esnekliği olarak Scream SEAL’e göre daha avantajlıdır. Scream 128 bit kelime kullanırken, SEAL 32 bit kelime kullanmaktadır.