Gröbner Tabanları ile AES'e Saldırı

Kriptografiyle uğraşanlar bilir; genelde iki ana yol vardır. Ya diferansiyel analiz gibi istatistiksel yöntemlerle şifreli metinde “iğneyle kuyu kazarsınız” ki bu yöntemler genelde büyük veri yığınları ve karmaşık olasılık hesapları gerektirir– ya da işi tamamen matematiğe döküp “mutlak çözümün” peşine düşersiniz. Birinde “Büyük olasılıkla anahtar bu” dersiniz, diğerinde ise “Anahtar kesinlikle budur” diyerek denklemi çözersiniz.

Benim (ve muhtemelen sizin de) ilgimi çeken kısım bu ikincisi: Cebirsel Kriptanaliz.

Olayımız aslında çok net: Gröbner tabanlarını kullanarak AES’i matematiksel olarak köşeye sıkıştırmaya çalışıyoruz. Kulağa basit geliyor değil mi? “Altı üstü birkaç denklem çözeceğiz” diyebilirsiniz. Ama işin içine girince, polinomların derecelerinin patladığı, belleklerin yetmediği ve NP-zor problemlerin o kaotik dünyasında kaybolmak işten bile değil. Bu, bir şifreyi kırmaktan çok, onu matematiksel olarak çözümlemeye ve zayıf karnını idealler teorisiyle bulmaya benzer.

Bugün, modern şifrelemeyi kırmak için elimizdeki en güçlü ve belki de en “niş” silahlardan birine, Gröbner Tabanlarına ve bu alandaki en yırtıcı algoritmalardan biri olan M5GB’ye yakından bakacağız. Kahvenizi alın, biraz polinom çiğneyeceğiz.

Şifre mi, Denklem mi?

Bir yazılımcıya AES nedir deseniz, size baytların yer değiştirdiği (ShiftRows), karıştığı (MixColumns) ve bir tablodan geçtiği (SubBytes) bir algoritma çizer. Ama bir cebirci olarak ben AES’e baktığımda, $GF(2^8)$ üzerinde tanımlı devasa bir polinom denklem sistemi görüyorum.

Temelde yapmaya çalıştığımız şey, şifreleme algoritmasının $E_k(x) = y$ fonksiyonunu, bilinmeyen $k$ anahtarına bağlı bir denklem seti olarak yazmaktır:

Buradaki $x$’ler bildiğimiz açık ve şifreli metin blokları, $k$’lar ise o çok değerli gizli anahtar bitleridir. Eğer bu sistemi çözebilirsek, anahtarı elimizle koymuş gibi buluyoruz. Ancak buradaki zorluk, sistemin $GF(2^8)$ (Galois Field) üzerinde çalışmasıdır. Yani sayılarla değil, katsayıları 0 veya 1 olan polinomlarla işlem yapıyoruz ve her işlem modüler aritmetikte gerçekleşiyor.

S-Box Baş Belasıdır (İyi Anlamda)

Sizin optimize ettiğiniz S-box yapılarını düşünün. Bir S-box’ın güvenli olması için matematiksel olarak karmaşık olması, yani lineer olmaması gerekir. AES’in S-Box’ı aslında $GF(2^8)$ cisminde bir “ters alma” ($x^{-1}$) işlemidir. Zhao ve arkadaşlarının çalışmasında [1] detaylandırıldığı üzere, S-box’ın cebirsel ifadesi Lagrange interpolasyonu ile şöyle korkunç bir hale gelir:

Derecesi 254! Gröbner tabanları yüksek dereceleri hiç sevmez. Hatta nefret eder. Derece ne kadar yüksekse, hesaplama karmaşıklığı o kadar hızlı (çift üstel) artar. Bu yüzden Zhao ve ekibi [1], AES-256 üzerine yaptıkları çalışmada bu dereceyi düşürmek için sisteme $w = x^d$ gibi yeni değişkenler ekleyerek dereceyi 2’ye (Quadratic) düşürme yoluna gitmişlerdir. Buna MQ (Multivariate Quadratic) modelleme denir.

Makalede [1] özellikle vurgulanan bir diğer nokta ise Sıfır Boyutlu İdeal (Zero-Dimensional Ideal) inşasıdır. Bir denklem sisteminin idealinin sıfır boyutlu olması, o sistemin sonlu sayıda çözümü olduğu (yani sonsuz çözüm veya çözümsüzlük içermediği) anlamına gelir. Zhao, doğru değişken sıralaması ve terim sıralaması (Term Order) seçildiğinde, AES-256 sisteminin sıfır boyutlu bir ideale dönüştüğünü kanıtlamıştır. Bu, saldırının matematiksel olarak “tamamlanabilir” olduğunun garantisidir.

Neden Herkes Bunu Yapmıyor? (Niş Olmasının Sebebi)

Dürüst olalım, bu alan gerçekten zor. Bir “script kiddie”nin yapabileceği türden bir iş değil.

Çoğu güvenlikçi istatistiksel analiz yapar çünkü modelleri kurmak nispeten daha “standarttır”. Ama cebirsel kriptanaliz? Hem kriptografiyi hem de Hesaplamalı Cebiri (Computational Algebra) çok iyi bilmeniz gerekiyor. Bir yanda diferansiyel olasılıklar, diğer yanda idealler, varyeteler ve halka teorisi…

Bu yüzden bu alanda çalışan araştırmacı sayısı bir elin parmaklarını çok geçmez. Ama bence işin “süper ilginç” kısmı da burada. Herkesin baktığı yere değil, problemin kalbine, matematiksel yapısına saldırıyorsunuz. Sadece “bu şifre zayıf” demiyorsunuz, “bu şifrenin cebirsel yapısı şurada kırılıyor” diyerek matematiksel bir kanıt sunuyorsunuz.

Matematiğin İsviçre Çakısı: Gröbner Tabanları

“Gröbner Tabanı nedir?” diye sorarsanız, size en basit haliyle şunu söylerim: Gauss Yok Etme yönteminin steroid almış halidir.

Elinizde karman çorman, çözülemez görünen, lineer olmayan bir denklem sistemi var. Gröbner tabanı algoritmasını çalıştırıyorsunuz ve size “üçgensel” forma girmiş, çözülebilir yeni bir denklem seti veriyor.

Gelin basit bir “Toy Cipher” üzerinde ne demek istediğimi göstereyim. $GF(2)$ (yani bitler dünyası, $1+1=0$) üzerinde şöyle bir sistemimiz olsun:

• $f_1: x^2 + y + z + 1 = 0$
• $f_2: xy + z = 0$
• $f_3: y + 1 = 0$ (Bu, örneğin bir “bilinen açık metin” saldırısından elde ettiğimiz bilgi olsun, $y=1$ demek).

Normalde bunu kağıt kalemle çözersiniz ama bilgisayar bunu nasıl yapıyor? Buchberger algoritması devreye giriyor. Temel mantık, polinomların “baş terimlerini” (leading terms) birbirini yok edecek şekilde çarpmaktır (buna S-Polinomu denir):

1. S-Polinomu Hesapla: $f_1$ ve $f_2$’yi çarpıştır.
2. İndirgeme (Reduction): Çıkan sonucu eldeki diğer denklemlerle sadeleştir (bölme algoritması gibi).
3. Kalanı Ekle: Eğer kalan sıfır değilse, bu “yeni bir bilgi” demektir, sisteme ekle.

Bu süreç sonunda bize şunu verir:

• $g_1: x$
• $g_2: y + 1$
• $g_3: z$

Bum! Sonuç: $x=0, y=1, z=0$. Şifre çözüldü. Artık elimizde anahtar var.

M5GB: İşin “Know-How” Kısmı

Yukarıdaki örnekte 3 değişken vardı. AES-128’de ise yaklaşık 3200 değişken ve 5000’den fazla denklem var. Klasik Buchberger algoritmasını buna uygularsanız, algoritma milyonlarca gereksiz S-polinomu üretir ve bilgisayarınız muhtemelen erir.

İşte tam burada, Hauke, Lamster, Lüftenegger ve Rechberger tarafından geliştirilen M5GB devreye giriyor [2]. 2022 tarihli çalışmalarında sundukları bu algoritma, bence tam bir mühendislik harikası çünkü iki farklı dünyanın en iyi özelliklerini birleştiriyor:

• Gereksiz İş Yapma (F5 Mantığı): Klasik algoritmada hesaplanan polinomların %90’ı, uzun işlemler sonucunda “0=0” çıkar (buna syzygy denir). M5GB, F5 algoritmasından miras aldığı “imza” (signature) konseptini kullanır. Her polinoma bir imza atayarak onun soyağacını takip eder. Eğer iki polinomun imzası aynı kökten geliyorsa, “bunlar birbirini zaten götürecek, hesaplamaya gerek yok” diyerek o çifti çöpe atar [2].

• Hafızayı Kullan (M4GB Mantığı): İndirgeme yaparken $(f - g)$ işlemi yaparız. Genellikle $g$’nin sadece baş terimiyle ilgileniriz ama $g$’nin geri kalanı (kuyruğu) da işlem görür. M4GB mantığını entegre eden M5GB, bu “kuyrukları” (tail-reduction) tamamen sadeleştirilmiş halde bir önbellekte (cache) tutar. Hauke ve ekibi [2], bu süreçte “Signature Flags” (İmza Bayrakları) adını verdikleri yeni bir mekanizma geliştirmişlerdir. Bu bayraklar, önbellekteki indirgenmiş elemanların, değişen imza kriterlerine göre hala geçerli olup olmadığını kontrol eder. Bu sayede algoritma, eski hesaplamaları güvenle yeniden kullanabilir.

Yapılan benchmark testlerinde, özellikle “overdefined” (denklem sayısı > değişken sayısı) ve yoğun (dense) kuadratik sistemlerde M5GB’nin, klasik imza tabanlı algoritmalara (SB) kıyasla çok daha hızlı çalıştığı ve daha az bellek tükettiği gösterilmiştir [2].

Peki, AES’i Kırdık mı?

Henüz değil :)

Teoride her şey harika ama pratikte hesaplamalı zorluk (computational complexity) en büyük duvarımız. Gröbner tabanlı saldırıların karmaşıklığı genelde üsteldir ($O(2^n)$ veya daha spesifik olarak $O(d^{O(n)})$). 80 bitlik bir sistemi evdeki güçlü bir PC ile çözebilirsiniz ama AES hala çok büyük lokma. Polinom dereceleri işlem sırasında “Intermediate Expression Swell” dediğimiz bir olayla patlayabilir.

Ama umutsuzluğa kapılmayın. Şöyle heyecan verici gelişmeler var:

• Hibrit Yaklaşımlar: Gröbner tabanlarını sadece sistemi “yumuşatmak” ve dereceyi düşürmek için kullanıp, öldürücü darbeyi SAT Solver’lara (Boolean Satisfiability) bırakmak şu an çok popüler.
• Post-Quantum Dünyası: Kuantum sonrası için tasarlanan MQ şifreleme sistemlerinin (örneğin Rainbow, GeMSS) güvenliği tamamen bu problemin zorluğuna dayanıyor. Yani bu araçlar gelecekte daha da kritik olacak.

Strateji: Nasıl Başlarım?

Eğer bu işe bulaşmak istiyorsanız (uyarayım, bağımlılık yapar), benim izlediğim yol haritası genelde şöyledir:

Modelleme (SageMath/Magma):

Önce SageMath açıp şifreyi BooleanPolynomialRing üzerinde tekrar yazıyorum. Burada Zhao’nun makalesindeki [1] gibi değişken sıralaması (Variable Ordering) çok kritiktir. Genellikle anahtar değişkenlerini en sona koyarız ki eliminasyon (yok etme) sırasında en son onlar kalsın.

# SageMath candır
# 128 bitlik bir halka tanımlıyoruz
R = BooleanPolynomialRing(128, 'x', order='degrevlex') 
# Denklemleri buraya döküyoruz...
# S-box denklemleri, MixColumns (lineer) denklemleri vb.

Saldırı (Gröbner Basis Hesaplama):

Sistemi çözmek için önce DegRevLex (Degree Reverse Lexicographic) sıralamasını kullanıyorum. Bu sıralama “Greedy” (açgözlü) davranır ve toplam dereceyi düşük tutar. Çözümü direkt vermez (üçgensel formda değildir) ama Gröbner tabanını çok daha hızlı hesaplar. Bu aşamada M5GB veya F4 algoritmaları kullanılır.

Dönüşüm (FGLM Algoritması):

Elinizdeki DegRevLex tabanını, asıl çözümü veren Lex (Lexicographic) tabana dönüştürmek için FGLM algoritmasını kullanın. Zhao [1], AES-256 analizinde sıfır boyutlu idealler için FGLM’in önemini vurgulamıştır; çünkü bu algoritma lineer cebir operasyonlarıyla taban değişimi yaparak sonuca hızla ulaşır.

Çözüm:

Lex tabanı size $x_n + a = 0$ gibi basit denklemler verir. Geriye doğru yerine koyarak anahtarı çekersiniz.

Sonuç

Cebirsel kriptanaliz, kaba kuvvetin (brute-force) hamallığına karşı, matematiğin zarafetidir. Belki yarın AES’i kıramayacağız ama Hauke ve ekibinin M5GB [2] gibi algoritmalarıyla duvarda her gün yeni bir gedik açıyoruz. Bu matematiksel satrançta bir sonraki hamleyi kimin yapacağını görmek için sabırsızlanıyorum.

Referanslar

[1] Zhao, K., Cui, J., & Xie, Z. (2017). “Algebraic Cryptanalysis Scheme of AES-256 Using Gröbner Basis”. Journal of Electrical and Computer Engineering.

[2] Hauke, M., Lamster, L., Lüftenegger, R., & Rechberger, C. (2022). “A Signature-Based Gröbner Basis Algorithm with Tail-Reduced Reductors (M5GB)”. arXiv preprint arXiv:2208.00844.