AES

AES çevrimindeki dört adımdan biri olan BaytDeğiştir işlemi

AES (Advanced Encryption Standard; Gelişmiş Şifreleme Standardı), elektronik verinin şifrelenmesi için sunulan bir standarttır. Amerikan hükûmeti tarafından kabul edilen AES, uluslararası alanda da defacto şifreleme (kripto) standardı olarak kullanılmaktadır. DES'in (Data Encryption Standard - Veri Şifreleme Standardı) yerini almıştır. AES ile tanımlanan şifreleme algoritması, hem şifreleme hem de şifreli metni çözmede kullanılan anahtarların birbiriyle ilişkili olduğu, simetrik-anahtarlı bir algoritmadır. AES için şifreleme ve şifre çözme anahtarları aynıdır.

AES, ABD Ulusal Standart ve Teknoloji Enstitüsü (NIST) tarafından 26 Kasım 2001 tarihinde US FIPS PUB 197 kodlu dokümanla duyurulmuştur. Standartlaştırma 5 yıl süren bir zaman zarfında tamamlanmıştır. Bu süreçte AES adayı olarak 15 tasarım sunulmuş, tasarımlar güvenlik ve performans açısından değerlendirildikten sonra en uygun tasarım standart şifreleme algoritması olarak seçilmiştir. Federal hükûmetin Ticaret Müsteşarı'nın onayının ardından 26 Mayıs 2002 tarihinde resmî olarak etkin hâle gelmiştir. Hâlihazırda birçok şifreleme paketinde yer alan algoritma Amerikan Ulusal Güvenlik Teşkilatı (NSA - National Security Agency) tarafından çok gizli bilginin şifrelenmesinde kullanımı onaylanan kamuya açık ilk şifreleme algoritmasıdır.

AES ile standartlaştırılan algoritma, esas olarak Vincent Rijmen ve Joan Daemen tarafından geliştirilen Rijndael algoritmasında bazı değişiklikler yapılarak oluşturulmuştur. Rijndael, geliştiricilerin isimleri kullanılarak elde edilen bir isimdir: RIJmen aNd DAEmen.

AES hakkında önemli bir nokta AES'in şifreleme standardının ismi olmasıdır. Ancak pratik kullanımda AES, standartta belirtilen şifreleme algoritmasının yerine geçecek şekilde kullanılmaktadır. Kolaylık ve literatürle uyumlu olması açısından bu dokümanda da standartta belirtilen algoritma AES olarak anılacaktır.

Algoritmanın Genel Yapısı

AES, Değiştirme-Karıştırma (Substitution-Permutation) olarak bilinen tasarım temeline dayanır. Öncülü DES ise Feistel yapıda tasarlanmış bir algoritmadır.

AES'in hem yazılım hem de donanım performansı yüksektir. 128-bit girdi bloğu, 128, 192 ve 256 bit anahtar uzunluğuna sahiptir. AES'in temel alındığı Rijndael ise 128-256 bit arasında 32'nin katı olan girdi blok uzunluklarını ve 128 bitten uzun anahtar uzunluklarını desteklemektedir. Dolayısıyla, standartlaşma sürecinde anahtar ve girdi blok uzunluklarında kısıtlamaya gidilmiştir.

AES, durum (state) denilen 4x4 sütun-öncelikli bayt matrisi üzerinde çalışır. Matristeki işlemler de özel bir sonlu cisim (finite field) üzerinde yapılmaktadır.

Algoritma belirli sayıda tekrar eden girdi açık metni, çıktı şifreli metne dönüştüren özdeş dönüşüm çevrimlerinden (round) oluşmaktadır. Her çevrim, son çevrim hariç, dört adımdan oluşmaktadır. Şifreli metni çözmek için bu çevrimler ters sıra ile uygulanır. Çevrimlerin tekrar sayıları 128-bit, 192-bit ve 256-bit anahtar uzunlukları için sırası ile 10, 12 ve 14'tür.

Algoritmanın Tanımı

• AnahtarOluştur (Key Expansion) - Esas anahtar kullanılarak algoritmanın çevrimlerinde kullanılacak çevrim anahtarları oluşturulur
• İlk çevrim

1. AnahtarEkle (AddRoundKey) - Durum, ilk çevrim anahtarı ile XOR'lanır.

• Çevrimler

1. BaytDeğiştir (SubBytes) - Durum matrisindeki her bayt bir tabloya göre ve doğrusal olmayan bir dönüşümle güncellenir.
2. SatırKaydır (ShiftRows) - Her satır belirli bir sayıda çembersel olarak kaydırılır.
3. SütunKarıştır (MixColumn) - Her bir sütundaki dört bayt, birbiriyle karıştırılır.
4. AnahtarEkle

• Son Çevrim

1. BaytDeğiştir
2. SatırKaydır
3. AnahtarEkle

BaytDeğiştir (SubBytes) Adımı

BaytDeğiştir adımında, matristeki her baytın değeri, 8 bitlik bir değişim kutusu (substitution box) kullanılarak güncellenir. Bu adım algoritmanın doğrusallığını bozar ve doğrusal-olmayan (non-linear) bir dönüşüm hâline gelmesini sağlar. Kullanılan değişim kutusu yüksek doğrusal-olmayanlık (nonlinearity) özelliğine sahip olduğu bilinen, sonlu cisim GF (2⁸) üzerinde ters alma işleminden elde edilmiştir. Cebirsel özellikler kullanan saldırılara karşı dayanıklı olası için sonlu cisim üzerinde ters alma işlemine tersi olan doğrusal bir dönüşüm daha eklenmiştir. Ayrıca değişim kutusu herhangi bir sabit nokta veya ters sabit nokta olmayacak şekilde seçilmiştir.

SatırKaydır (ShiftRows) Adımı

Matrisin satırları üzerinde çalışan bu işlem her satırdaki bayt değerlerini belirli sayıda kaydırır. AES'de ilk satır sabit kalırken 2., 3. ve 4. satırlar sırası ile 1, 2 ve 3 bayt sola kaydırılır. Rijndael algoritmasında ise 256-bit için bu değerler, ilk satır sabit kalacak şekilde 1, 3 ve 4 bayttır.

SütunKarıştır (MixColumn) Adımı

Bu adımda her sütundaki dört bayt değeri tersi olan doğrusal bir dönüşüm kullanılarak birbirleriyle karıştırılır. SütunKarıştır fonksiyonu 4 bayt girdi alıp 4 bayt çıktı verir ve girdideki her baytın çıktıdaki her bayt değerini etkilemesini sağlar. SütunKarıştır işlemi, her sütunun sabit bir matrisle çarpılması işleminden oluşur. Bu sabit matris aşağıda verilmiştir:

${\displaystyle {\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}}.}$

Matris çarpması işlemi sonlu cisim GF (2⁸) üzerinde yapılmaktadır. Her bayt bu sonlu cisim üzerinde bir polinom tanımlayacak şekilde, mod x⁴+1'de c(x) = 0x03 · x³ + x² + x + 0x02 polinomu ile çarpılır. SütunKarıştır adımındaki sabit matris bir MDS matristir ve SatırKaydır adımı ile birlikte şifrede karmaşıklık (diffusion) sağlar.

AnahtarEkle (AddRoundKey) Adımı

Bu adımda çevrim anahtarı durum matrisi ile kaynaştırılır. Çevrim anahtarı baytlara bölündükten sonra sıra ile matrisin elemanları ile XOR'lanır.

Algoritmanın İyileştirilmesi

32 ya da daha büyük kelime uzunluğuna sahip sistemlerde BaytDeğiştir ve SatırKaydır adımlarını SütunKarıştır adımı ile birleştirip bir tablo oluşturarak hızlanma sağlamak mümkündür. Bu işlem toplam 4 kilobayt (4069 bayt) hafızayı kullanan 32-bitlik 256 girdili dört tablo gerektirir. Bu iyileştirme sayesinde her çevrim 16 tablo okuması ve 12 32-bit XOR işlemini takip eden AhahtarEkle, 4 32-bit XOR, adımı ile gerçekleştirilebilir.

Hedef platformun 4 kilobaytlık tabloların gömülmesine izin vermediği durumlarda ise tek bir tablo kullanılabilir. Bu durumda 32-bitlik 256 girdisi olan bir tablo (1 kilobayt) oluşturulur ve tablodaki değerler çembersel kaydırma yardımıyla çevrimlerde kullanılabilir.

Ayrıca, bayt-tabanlı bir yaklaşımla da BaytDeğiştir, SatırKaydır ve SütunKarıştır adımları tek bir adımda birleştirilebilir.

Algoritmanın Güvenliği

Kriptografların bakış açısından bir algoritmanın kriptografik olarak kırılması, anahtarın ya da anahtarın bazı parçalarının olası tüm anahtarların denendiği kaba kuvvet saldırısından daha hızlı bir şekilde elde edilmesi anlamına gelir. Bu açıdan, 256-bit anahtar uzunluğuna sahip AES algoritması için 2²⁰⁰ işlem gerektiren bir saldırı algoritmanın kırılması olarak kabul edilirken 2²⁰⁰ mertebesindeki bir işlem, şu an için, evrenin yaşından daha uzun bir süre gerektirmektedir.

2011 yılına kadar AES'in tam çevrimine yapılan başarılı saldırılar belirli donanım gerçeklemeleri üzerinde çalışan yan kanal saldırılarıdır. Bu tarihte Andrey Bogdanov, Dmitry Khovratovich ve Christian Rechberger tarafından kaba kuvvet saldırısından yaklaşık 4 kat daha hızlı olan bir saldırı yayımlanmıştır.

NSA, AES yarışması finalistlerini güvenlik açısından değerlendirdikten sonra bütün finalistlerin Amerikan hükûmetinin gizlilik derecesine sahip olmayan verilerinin kullanımına uygun olduğunu belirtmiştir. 2003 yılı Haziran ayında ise, AES'in gizlilik derecesine sahip bilginin şifrelenmesinde de kullanılabileceğini duyurmuştur:

AES algoritmasının bütün anahtar boylarının (128, 192 ve 256 bit) tasarımı ve dayanıklılığı "GİZLİ" mertebesine kadar bütün verilerin korunması için uygundur. "ÇOK GİZLİ" veriler 192 ya da 256-bit anahtar kullanımını gerektirmektedir. Ulusal güvenlik sistemlerinin ya da bilgilerinin korunması amacını taşıyan ürünlerdeki AES uygulamaları, bu ürünlerin alımı ve kullanımından önce NSA tarafından incelenip sertifikalandırılmalıdır.

Bilinen Saldırılar

2002 yılında AES'in sade ve basit cebirsel yapısını değerlendiren Nicolas Courtois ve Josef Pieprzyk "XSL Attack" isimli bir teorik saldırı duyurmuşlardır. Ancak daha sonra, duyurulan hâliyle atağın çalışmadığını gösteren bilimsel yayınlar yapılmıştır. Blok şifrelere XSL saldırısı.

AES süreci sırasında diğer tasarımcılar Rijndael'in kritik uygulamalarda kullanımına ilişkin endişelerini dile getirdilerse de yarışmadan sonra Twofish algoritmasının tasarımcılarından güvenlik uzmanı Bruce Schneier Rijndael'e başarılı teorik saldırılar yapılabileceğini ancak bu saldırıların pratik hâle gelebileceğine inanmadığını belirtmiştir.

1 Temmuz 2009 tarihinde Bruce Schneier blogunda 192-bit ve 256-bit AES versiyonlarına Alex Biryukov ve Dmitry Khovratovich tarafından 2¹¹⁹ işlem karmaşıklığı ile uygulanabilen ve AES'in basit anahtar oluşturma algoritmasından faydalanan bir ilişkili-anahtar (related-key) saldırısını duyurmuştur. Aralık 2009'da bu saldırının işlem karmaşıklığı 2^99.5e düşürülmüştür. Ardından Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich ve Adi Shamir 9 çevrim AES-256'ya sadece iki ilişkili-anahtar kullanarak 2³⁹ zamanda anahtarın tamamının elde edildiği saldırıyı yayımlamışlardır. Bu saldırı 2⁴⁵ zaman karmaşıklığı ile 10 çevrime, 2⁷⁷ zaman karmaşıklığı ile 11 çevrime genişletilmiştir ancak tam çevrim AES bu ataktan etkilenmemiştir.

Kasım 2009'da 8 çevrimlik AES-128'e bilinen anahtarlı ayırt etme (distinguishing) saldırısı yayımlanmıştır. Bu saldırı AES-benzeri permütasyonlara uygulanan rebound (ya da ortadan-başla) saldırılarının geliştirilmiş bir hâlidir. Bu saldırının zaman karmaşıklığı 2⁴⁸, hafıza karmaşıklığı ise 2³²dir.

2010 yılının Temmuz ayında ise tasarımcılardan Vincent Rijmen, AES'e yapılan ve kriptografi camiasında da taşıdığı anlam tartışmalı olan ilişkili-anahtar saldırıları ile ilgili olarak bu saldırıları tiye alan bir makale yayımlamış, bu tür ilişkilerin her algoritmada bulunduğunu savunmuştur.

Tam çevrim AES'e yapılan ilk başarılı anahtar elde etme saldırısı Andrey Bogdanov, Dmitry Khovratovich ve Christian Rechberger tarafından yapılmıştır. Atak, biclique adı verilen yapılar kullanarak 128-bit anahtarı 2^126.1, 192-bit anahtarı 2^189.7 ve 256-bit anahtarı 2^254.4 işlem karmaşıklığı ile elde etmektedir.

Yan Kanal Saldırıları

Yan kanal saldırıları, kullanılan şifreleme algoritmalarının güvenlikleri ya da açıklarıyla ilgilenmek yerine, algoritmaların gerçeklendiği donanımlara saldırarak buradan veri sızdırmaya çalışır. Bazı AES gerçeklemelerine yapılan başarılı yan kanal saldırıları ile anahtarın elde edilmesi mümkün olmuştur.

2005 yılında D.J. Bernstein OpenSSL'in AES uygulamasını kullanan bir sunucuya ön bellek-zamanlama (cache-timing) saldırısı yapmıştır. 200 milyon civarında seçilmiş açıkmetin kullanılarak yapılan saldırıda, sunucu şifreli metinle birlikte şifrele işleminin kaç işlemci saati sürdüğünü de alıcıya göndermekteydi. Bernstein, bu saldırının başarılı olması için, şifreleme süresinin sunucudan gelen kadar kesin olmasına gerek olmadığını göstermiştir.

Aynı yıl Dag Arne Osvik, Adi Shamir ve Eran Tromer, yine ön bellek-zamanlama saldırıları ile AES anahtarını 65 milisaniyede elde eden bir yöntem geliştirmiştir. Bu yöntemin başarılı olması için saldırganın, saldırdığı platformda AES ile şifreleme yapabilme imkânının olması gerekiyordu.

2009 yılında ise FPGA kullanan bir platformda, 2³² zorlukla anahtar elde edilmiştir.

Endre Bangerter, David Gullasch ve Stephan Krenn, 2010 yılında açık metin ya da şifreli metin kullanmadan OpenSSL gibi sıkıştırma tabloları kullanan uygulamalardan AES-128 gizli anahtarını elde etmeye yarayan bir saldırı yayımlamışlardır. Bu saldırı da saldırganın, saldırılan sistemde kod çalıştırabilmesini gerektirmektedir.

Test Değerleri

Test değerleri, algoritmanın gerçeklemesinin doğruluğunu kontrol etmek amacıyla oluşturulan, verilen açıkmetin ve anahtar çiftlerine karşılık gelen şifreli metinlerdir. Test değerleri (KAT-Known Answer Test) buradan indirilebilir.

Performans

AES seçim sürecinde NIST'in performans kriterleri yüksek hız ve düşük RAM gereksinimi olarak belirlenmişti. Bu kriterler göz önünde bulundurularak tasarlanan AES, 8-bit akıllı kartlardan yüksek performanslı bilgisayarlara kadar birçok değişik donanım üzerinde yüksek performansla çalışır.

Pentium Pro işlemci üzerinde bir AES şifrelemesi bayt başına 18 saat çevrimi gerektirir. Bu da 200 MHz saat frekansına sahip bir işlemci için yaklaşık olarak saniyede 11 MiB veri büyüklüğüne denk gelir. AES'in kullandığı işlemlerin işlemcilerin komut setine dâhil edilmesi ile şifreleme işleminin gerektirdiği saat çevrimi bayt başına 3,5'e^[1], yüksek ara bellekli (buffer) sistemlerde ise 1,3'e^[2] kadar düşmüştür.

Kaynakça

1. http://en.wikipedia.org/wiki/AES_instruction_set
2. software.intel.com/file/27067