AES Kriptanalizinde Cebirsel Temsil

Bir blok şifrenin cebirsel olarak daha kısa bir ifadeyle gösterilmesi, şifrenin kırıldığı anlamına gelmez. Daha kompakt bir temsil, saldırı problemini farklı bir denklem uzayına taşır. Asıl güçlük, ortaya çıkan denklem sistemini anahtarın elde edilebileceği hesaplama maliyeti içinde çözmektir. AES üzerinde yapılan cebirsel kriptanaliz çalışmalarında bu ayrım belirleyicidir.

2020 ile 2022 yılları arasında, özellikle AES üzerine çalışan kriptanalist mühendis Bekir Ünlü ile birlikte çalışma imkanı buldum. Üniversite bünyesinde yürütülmeyen bir kriptanaliz projesinde onun koordinasyonunda görev aldım ve projeyle ilişkili yazılımın geliştirilmesine katıldım. Bu çalışma, kriptografik bir algoritmayı uygulamak ile aynı algoritmayı cebirsel yapısı üzerinden incelemek arasındaki farkı doğrudan görmemi sağladı.

Bekir Ünlü'nün 2019 yılında IET Information Security dergisinde yayımlanan çalışması, AES S-box yapısını girişin çarpımsal tersi, belirli bitler ve sonlu alan elemanları üzerinden birleşik bir ifadeyle göstermeyi önerir. Makale, bu gösterimin cebirsel kriptanaliz için yeni dönüşüm yolları sağlayabileceğini inceler. Çalışma 1 Mayıs 2019 tarihinde yayımlanmış ve "10.1049/iet-ifs.2018.5051" DOI numarasını almıştır.

AES'in cebirsel yapısı

AES, 128 bitlik durum üzerinde çalışan ve anahtar uzunluğuna göre 10, 12 veya 14 tur kullanan bir blok şifredir. AES-128 için her normal tur "SubBytes", "ShiftRows", "MixColumns" ve "AddRoundKey" dönüşümlerinden oluşur. Son turda "MixColumns" uygulanmaz.

Bu dönüşümlerin üçü cebirsel açıdan görece düzenlidir. "ShiftRows" bir permütasyondur. "MixColumns", "GF(2^8)" üzerinde sabit bir matris çarpımıdır. "AddRoundKey" ise bit düzeyinde XOR işlemine karşılık gelir. Cebirsel analizi zorlaştıran temel bileşen "SubBytes" içindeki doğrusal olmayan S-box dönüşümüdür.

AES içindeki her bayt, 256 elemanlı sonlu alanın bir elemanı olarak yorumlanır. Toplama XOR ile yapılır. Çarpma sonucunda oluşan polinom, AES standardında tanımlanan

m(x) = x^8 + x^4 + x^3 + x + 1

polinomuna göre indirgenir. Sıfırdan farklı her alan elemanının bu yapı içinde tek bir çarpımsal tersi vardır. AES S-box, giriş baytının "GF(2^8)" içindeki çarpımsal tersini aldıktan sonra bitler üzerinde afin dönüşüm uygular. Sıfır girdisi özel olarak sıfıra eşlenir ve ardından aynı afin dönüşümden geçirilir.

S-box doğrusal olmadığı için AES'in cebirsel derecesini ve denklem yapısını belirler. Şifrenin geri kalan bölümleri, ara durum baytları değişken kabul edildiğinde sonlu alan denklemleriyle doğrudan ifade edilebilir. Bu nedenle cebirsel kriptanalizde temel sorulardan biri şudur:

S-box, denklem sisteminin çözümünü kolaylaştıracak başka bir biçimde gösterilebilir mi?

Ünlü'nün çalışması bu soruyu AES'in yalnız bir turuna değil, şifreleme kısmı ile anahtar genişletme kısmının birlikte oluşturduğu sisteme yöneltir. Makale, üç turluk örnek üzerinden ara durum değişkenlerini tanımlar. Tam 10 turluk AES-128 için de şifreleme ve anahtar takvimi değişkenlerini kapsayan 336 denklemli bir "GF(2^8)" sistemi ortaya koyar. Bu sistemde 200 ayrı S-box kullanımı bulunur.

Bu sayıların eşit olması, yani denklem sayısı ile değişken sayısının aynı olması, sistemin pratik olarak çözülebilir olduğunu göstermez. Denklemlerin derecesi, bağımlılıkları, terim sayısı ve çözüm algoritmasının bellek ihtiyacı belirleyicidir. Cebirsel kriptanalizin güçlüğü çoğu zaman denklem üretmekten değil, üretilen sistemin yapısal olarak çözülebilir olup olmadığını belirlemekten doğar.

S-box'un birleşik gösterimi

Makaledeki temel katkı, S-box dönüşümünün yalnız yüksek dereceli bir polinom veya yalnız bit tabanlı ikinci derece denklemler olarak ele alınmamasıdır. Bunun yerine bayt, bit ve çarpımsal ters bilgisi aynı ifadede birleştirilir.

"X", S-box girdisi ve "Y = X^-1" bu girdinin "GF(2^8)" içindeki çarpımsal tersi olsun. "y_7", "y_6", "y_5" ve "y_4", "Y" elemanının üst dört bitini göstersin. Makalede önerilen birleşik gösterim şu biçimdedir:

S(X) = "1F" * X^-1

• "96" * y_7
• "46" * y_6
• "2E" * y_5
• "1A" * y_4
• "63"

Buradaki hexadecimal sabitler "GF(2^8)" elemanlarıdır. "y_i" değerleri ise "GF(2)" elemanlarıdır. Toplama ve çarpma işlemleri normal tamsayı aritmetiğiyle değil, ilgili sonlu alan kurallarıyla yürütülür.

İfadenin ilgi çekici tarafı, S-box'un doğrusal olmayan çekirdeğini doğrudan "X^-1" terimi üzerinden korurken afin dönüşümden kalan yapıyı yalnız dört bit ve sabit alan elemanlarıyla temsil etmesidir. Makaledeki "birleşik" sözcüğü de bu farklı gösterim düzeylerinin aynı denklemde bulunmasından gelir.

Klasik S-box gösteriminde her çıkış biti giriş bitlerinin cebirsel normal biçimiyle ifade edilebilir. Alternatif olarak giriş ile çıkış arasındaki ilişki, çok değişkenli ikinci derece denklemlerle modellenebilir. Birleşik gösterim bunların yerine geçmekten çok yeni denklem türetme yolları açar.

Makale, bu gösterimden olasılık 1 ile 81 terim içinde 23 bi-affine denklem veya 137 terim içinde 39 tam ikinci derece denklem elde edilebildiğini belirtir. Aynı bölümde, kullanılan cebirsel karmaşıklık ölçüsüne göre S-box gösterimindeki terim sayısının 9'dan 6'ya indiği ifade edilir.

Buradaki 9 ve 6 sayıları AES'in güvenlik bitlerini göstermez. Bunlar belirli cebirsel gösterimlerdeki terim sayısıyla ilgilidir. Daha az terimli bir S-box ifadesi, bütün AES denklem sisteminin aynı oranda kolay çözüleceğini kanıtlamaz. Sistem büyüdükçe ara değişkenler, denklem bağımlılıkları ve ters fonksiyonların etkileşimi ayrı bir karmaşıklık üretir.

Çalışma bu birleşik gösterimi yalnız yerel S-box analizi için kullanmaz. Denklemlerin tamamına dışarıdan sonlu alan işlemleri uygulanmasını önerir. İncelenen iki yöntem şunlardır:

• Her denklemin belirli bir "GF(2^8)" elemanıyla çarpılması
• Denklem sistemine alan izi işleminin uygulanması

İlk yöntemde denklemler hexadecimal "FD" alan elemanıyla çarpılır. Bu dönüşüm, dört artık biti yarım bayt biçimindeki bilinmeyenlere indirgemeyi amaçlar. Ancak yeni bilinmeyenlerin etkileşimini çözebilecek bir yöntemin bulunması gerekir. Makalenin kendisi de tam 10 turluk sistem için verilen karmaşıklık hesabının, dönüştürülmüş sistemin çözülebileceği varsayımına bağlı olduğunu belirtir.

Alan izi ile dönüşüm

Alan izi, "GF(2^8)" elemanını "GF(2)" elemanına taşıyan doğrusal bir fonksiyondur:

Tr(a) = a + a^2 + a^4 + a^8

• a^16 + a^32 + a^64 + a^128

Sonuç yalnızca 0 veya 1 olabilir. Alan izi toplama üzerinde doğrusaldır:

Tr(a + b) = Tr(a) + Tr(b)

Bu özellik, büyük bir sonlu alan denklemindeki terimlerin bit alanına taşınmasını sağlar. Makale önce temel S-box izini çıkarır. Ancak ilk dönüşümde "y_7" ve "y_5" bitlerinin kaldığını gösterir. Ardından S-box çıktısını uygun alan elemanlarıyla çarpıp iz alarak bu artık bitleri yok eden genişletilmiş bir dönüşüm önerir.

Örneğin "C8" alan elemanı kullanıldığında makalede şu ilişkiye ulaşılır:

Tr("C8" * S(X)) = Tr("60" * X^-1)

Bu eşitlikte S-box ifadesindeki dört artık bit ve sabit terim iz altında ortadan kalkar. Makale, aynı özelliği sağlayan başka alan elemanları da belirler.

Buradaki fikir, S-box'u doğrudan tersine çevirmek değildir. S-box içeren her AES denklemini, alan izi altında yalnız çarpımsal tersler ve sabitler içeren başka bir denkleme dönüştürmektir. Böylece saldırı problemi farklı bir cebirsel yapıya taşınır.

Bu dönüşüm bilgi kaybeder. "GF(2^8)" içindeki bir bayt, alan iziyle tek bite indirgenir. Tek bir iz denklemi özgün bayt değerini belirleyemez. Farklı çarpanlarla üretilen iz ilişkilerinin birlikte ne kadar bilgi taşıdığı ve bu bilginin anahtar değişkenlerine nasıl aktarılacağı ayrıca incelenmelidir. Makalenin açık bıraktığı ana problem de budur.

Azaltılmış tur saldırısının sınırı

Çalışmadaki somut saldırı iyileştirmesi, tam AES-128 yerine 6 turluk azaltılmış sürümü hedefler. Birleşik ters S-box gösterimi, Partial Sum Attack içindeki ara durum kontrolüne ek bilgi kazandırmak için kullanılır.

Makaledeki hesaplamaya göre klasik yöntemde bir delta kümesi yanlış anahtar tahminlerinin "255/256" oranını elerken yeni kontrolün beklenen eleme oranı "287/288" olur. Bu fark, beş anahtar baytını belirlemek için gereken seçilmiş açık metin veri karmaşıklığını

6 * 2^32

değerinden

5 * 2^32

değerine indirir. Zaman karmaşıklığı ise yaklaşık "2^44" olarak kalır.

Bu iyileştirme önemlidir, ancak kapsamı doğru okunmalıdır. Sonuç 6 turluk AES-128 içindir. Standart AES-128 10 tur kullanır. Azaltılmış tur saldırıları, şifrenin güvenlik payını ve yapısal özelliklerini anlamak için değerlidir. Tam sürüm üzerinde uygulanabilir bir anahtar kurtarma saldırısı oldukları anlamına gelmez.

Makale bu sınırı açıkça kabul eder. Sonuç bölümünde çalışmanın tam AES üzerinde bir saldırı tanımlamadığı, önerilen yöntemlerin büyük bir çarpımsal ters denklem sisteminin çözülebilirliğine bağlı olduğu ve küçük ölçekli AES türevleri üzerinde yeni deneylere ihtiyaç bulunduğu belirtilir. Alan iziyle elde edilen sistemin değişkenleri ile gerçek AES anahtar değişkenleri arasındaki ilişkinin de açık bir araştırma problemi olduğu ifade edilir.

Bu ayrım, kriptanaliz çalışmalarında kullanılan dil açısından önemlidir. Yeni bir temsil bulmak, saldırı yüzeyini genişletebilir. Yeni denklemler üretmek, çözüm algoritmasına daha fazla yapı sunabilir. Fakat tam saldırı, bu yapıdan anahtarın uygulanabilir zaman ve bellek maliyetiyle çıkarılmasını gerektirir.

Kriptanaliz yazılımı geliştirmek

Bu alanda yazılım geliştirmek, AES şifreleme kodu yazmaktan farklı bir düşünme biçimi gerektirir. Normal bir AES uygulamasında doğru anahtar, açık metin ve şifreli metin ilişkisi bilinir. Başarı, standart test vektörleriyle doğrulanabilir. Kriptanaliz yazılımında ise ara değişkenler bilinmeyendir. Amaç, bu bilinmeyenler arasındaki ilişkileri üretmek, sadeleştirmek ve çözüm araçlarının işleyebileceği biçime dönüştürmektir.

Sonlu alan aritmetiğinin bit düzeyinde doğru uygulanması ilk koşuldur. "GF(2^8)" toplaması XOR olsa da çarpma normal bayt çarpması değildir. Polinom indirgeme, ters alma, karesini alma ve alan izi işlemleri aynı alan tanımına bağlı kalmalıdır. Bir bit sırası veya hexadecimal gösterim hatası, bütün denklem sistemini geçersiz hale getirebilir.

Yazılımın her katmanı bağımsız doğrulanmalıdır:

1. Sonlu alan toplama ve çarpma işlemleri
2. Çarpımsal ters hesabı
3. S-box ve ters S-box üretimi
4. Afin dönüşüm
5. Birleşik gösterimin 256 giriş için doğrulanması
6. Denklem üretimi
7. Denklem bağımlılığı ve rank analizi
8. Azaltılmış tur modelleri
9. Saldırı karmaşıklığı ölçümü

Birleşik gösterimin doğrulanması yalnız birkaç örnek değerle yapılmamalıdır. S-box giriş uzayı 256 değer içerdiği için bütün değerler tüketilebilir. Standart S-box sonucu ile birleşik formülün sonucu her giriş için karşılaştırılabilir. Aynı yöntem ters S-box için de uygulanabilir.

Denklem üretiminde değişken adlandırma ve tur indeksleri deterministik olmalıdır. Aynı model her çalıştırmada aynı değişken sırasını ve aynı denklem kümesini üretmelidir. Aksi halde iki deneyin rank, terim sayısı veya çözüm süresi sonuçlarını güvenilir biçimde karşılaştırmak zorlaşır.

Bu çalışmalar sırasında programlama yalnız matematiksel formüllerin kodlanması anlamına gelmiyordu. Denklem sayısının büyümesi bellek yerleşimini, veri yapısını ve dosya biçimini doğrudan etkiliyordu. Seyrek polinomları yoğun matrislerle saklamak, henüz çözücüye ulaşmadan belleği tüketebilir. Monomların kanonik sırada tutulması, aynı terimlerin birleştirilmesi ve sıfır katsayıların erken elenmesi gerekir.

Kriptanaliz yazılımında yanlış bir iyileştirme sonucu, hiç sonuç alınamamasından daha tehlikelidir. Eksik denklem, hatalı alan işlemi veya yanlış bağımsızlık hesabı, gerçekte bulunmayan bir saldırı avantajı üretebilir. Bu nedenle deney kodu ile doğrulama kodunun aynı algoritmayı paylaşmaması tercih edilir. Bağımsız iki uygulamanın aynı sonucu üretmesi daha güçlü kanıt sağlar.

Bir temsil problemi olarak kriptanaliz

Bekir Ünlü ile yürüttüğüm çalışma, kriptanalizin yalnız yüksek hesaplama gücü kullanarak anahtar aramak olmadığını gösterdi. Bir algoritmayı hangi değişkenlerle ve hangi cebirsel uzayda ifade ettiğimiz, uygulanabilecek saldırı yöntemlerini değiştirir.

Aynı S-box bir tablo, yüksek dereceli polinom, bit düzeyinde cebirsel normal biçim, ikinci derece denklem sistemi veya çarpımsal ters içeren birleşik bir ifade olarak gösterilebilir. Bu gösterimlerin her biri aynı fonksiyonu tanımlar. Ancak denklem sayıları, dereceleri, seyrekliğe ilişkin özellikleri ve çözücülerle uyumları farklıdır.

Ünlü'nün çalışması, AES'in kırıldığını iddia etmez. Daha dar ve teknik bir katkı sunar. S-box için alternatif bir cebirsel temsil kurar, bu temsil üzerinden yeni denklemler türetir ve bütün AES sistemi üzerinde uygulanabilecek iki dönüşüm önerir. Ayrıca azaltılmış tur saldırısında ölçülebilir bir veri karmaşıklığı iyileştirmesi gösterir.

Benim açımdan bu çalışma döneminin kalıcı etkisi, kriptografik yazılım geliştirmeye bakışımı değiştirmesi oldu. Uygulama güvenliği için standarda doğru uymak gerekir. Kriptanaliz için ise standardın arkasındaki cebirsel yapıyı yeniden kurmak gerekir. Birinci problem deterministik bir gerçekleştirim ister. İkinci problem, aynı fonksiyonu daha açıklayıcı ve çözülebilir bir biçimde temsil etmeyi amaçlar.

Bu iki alanın kesiştiği yerde mühendislik disiplini belirleyici olur. Matematiksel eşitlikler bit düzeyinde doğrulanmalı, deneyler yeniden üretilebilmeli ve hesaplama sınırları açıkça raporlanmalıdır. Cebirsel bir sadeleşme ile uygulanabilir bir saldırı arasındaki mesafe ancak bu şekilde doğru ölçülebilir.

Kaynakça

Unlu, B. (2019). Base for algebraic cryptanalysis based on combined representation of S-box. IET Information Security, 13, 249-257. DOI: "10.1049/iet-ifs.2018.5051".

National Institute of Standards and Technology. (2023). Advanced Encryption Standard. FIPS 197-upd1.