C ile Hafif AES-128 Gerçekleştirimi

Bir AES gerçekleniminde en kolay hata, S-box tablosunu yanlış yazmak değildir. Asıl risk, 16 baytlık durum matrisini bellekte yanlış yorumlamak, tur anahtarlarını farklı bir sırayla uygulamak veya son turdaki MixColumns istisnasını gözden kaçırmaktır. Kod görünüşte düzenli çalışır, şifreleme ile şifre çözme birbirini geri alabilir, ancak standart AES ile uyumlu olmayan ayrı bir dönüşüm üretilebilir.

Paylaştığım C kodunu geliştirirken hedefim AES-128 çekirdeğini harici kriptografi kütüphanesi kullanmadan, sabit bellekle ve gömülü sistemlerde çalışabilecek kadar yalın biçimde gerçeklemekti. Kod, tek bir 128 bitlik bloğu yerinde şifreler veya çözer. Dinamik bellek ayırmaz. S-box, ters S-box ve sonlu alan çarpımlarını önceden hesaplanmış tablolar üzerinden yürütür.

Bu çalışma, hazır bir API kullanma deneyiminden farklıydı. AES'in her adımını bayt düzeyinde kurmak, standardın cebirsel yapısını programlama kararlarına dönüştürmeyi gerektiriyordu. Daha sonra cebirsel kriptanaliz çalışmalarında edindiğim deneyim, aynı S-box yapısına başka bir yönden bakmamı sağladı. Uygulama tarafında S-box hızlı bir tablo erişimidir. Kriptanaliz tarafında ise bütün şifrenin doğrusal olmayanlığını taşıyan sonlu alan dönüşümüdür.

Durum matrisinin kurulması

Kaynak kod yalnızca AES-128'i hedefler. Sabitler bu sınırı doğrudan gösterir:

Blok boyutu       = 16 bayt
Anahtar boyutu    = 16 bayt
Sütun sayısı      = 4
Tur sayısı        = 10
Genişletilmiş anahtar = 176 bayt

AES standardı 128 bitlik bloklar üzerinde çalışır. AES-128, AES-192 ve AES-256 sırasıyla 128, 192 ve 256 bitlik anahtar kullanır. Paylaşılan gerçeklenim, 10 turluk AES-128 çeşidine göre sabitlenmiştir.

AES durumu matematiksel olarak 4x4 baytlık bir matristir. Giriş baytları sütun öncelikli yerleştirilir:

state[row, column] = input[row + 4 * column]

Kodda ayrı bir 16 baytlık durum dizisi oluşturmak yerine giriş tamponunun dört bölümüne işaret eden dört gösterici kullanılmıştır. İlk indis sütunu, ikinci indis satırı temsil eder:

state[column][row]

Bu seçim ilk bakışta standarttaki gösterimin tersi gibi görünür. Bellek yerleşimi incelendiğinde aynı yapıyı ifade ettiği anlaşılır. Her gösterici, tampon içindeki dört baytlık bir AES sütununa karşılık gelir.

Bu tasarımın iki sonucu vardır. İlki, şifreleme yerinde yapılır. Girdi ile çıktı için ayrı tampon gerekmez. İkincisi, ShiftRows işlemi satırları ardışık bir dizide kaydırmak yerine dört sütun arasındaki baytları taşır. Kodun satır kaydırma bölümündeki doğrudan atamalar bu veri yerleşiminin doğal sonucudur.

Kaynak kodu FIPS 197'deki bilinen AES-128 vektörüyle yeniden doğruladım. 000102030405060708090a0b0c0d0e0f anahtarı ve 00112233445566778899aabbccddeeff açık metni, beklenen 69c4e0d86a7b0430d8cdb78070b4c55a çıktısını üretti. Ters işlem de özgün açık metni geri verdi. Bu test, şifreleme ve şifre çözmenin yalnız birbirinin tersi olduğunu değil, gerçeklenimin standart AES-128 ile uyumlu olduğunu gösterir.

Anahtar genişletme

AES-128 anahtar takvimi, 16 baytlık anahtardan 11 ayrı tur anahtarı üretir. Başlangıç anahtarı da bu sayıya dahildir. Her tur anahtarı 16 bayt olduğundan toplam alan şöyledir:

11 x 16 = 176 bayt

Kaynak kod ilk 16 baytı doğrudan genişletilmiş anahtar alanına kopyalar. Kalan 160 bayt dört baytlık kelimeler halinde üretilir. Her yeni kelime, dört kelime önceki değer ile bir önceki kelimeden türetilen geçici değerin XOR işleminden oluşur.

Her dördüncü kelimede üç ek dönüşüm uygulanır:

1. RotWord, dört baytı bir konum sola döndürür.

1. SubWord, her baytı S-box üzerinden geçirir.

1. İlk bayta ilgili tur sabiti uygulanır.

Diğer kelimelerde bir önceki kelime doğrudan kullanılır. Bu yapı yalnız AES-128 için yeterlidir. AES-256 anahtar takvimindeki ek SubWord koşulu kaynak kodda bulunmaz. BLOCK_LENGTH sabiti hem blok sütunu sayısı hem de 128 bitlik anahtarın kelime sayısı yerine kullanılmıştır. Bu iki değer AES-128'de eşittir, ancak genel Rijndael modelinde ayrı kavramlardır.

RCon dizisinin ilk elemanı olan 0x8d algoritmada kullanılmaz. Gerçek tur sabitleri dizinin 1 ile 10 arasındaki elemanlarıdır. Bu yerleşim, RCon[i / 4] ifadesini doğrudan kullanmayı sağlar. Aynı düzen birçok küçük AES gerçekleniminde de görülür. Ancak sabit tabloların aynı olması tek başına kod kökeni hakkında kanıt oluşturmaz. S-box, ters S-box ve tur sabitleri AES standardının tanımladığı ortak verilerdir.

Anahtar genişletme her Encrypt ve Decrypt çağrısında yeniden yapılır. Bu tercih API'yi durumsuz tutar. Çağıran tarafın bir bağlam nesnesi veya genişletilmiş anahtar saklaması gerekmez. Tek blokluk seyrek işlemlerde sade bir kullanım sağlar.

Aynı anahtarla çok sayıda blok işlendiğinde bu yaklaşım gereksiz hesaplama üretir. Anahtar bir kez genişletilip sonraki bloklarda tekrar kullanılabilir. Bu durumda 176 baytlık anahtar takviminin yaşam döngüsü ayrıca yönetilmelidir. Bellekte daha uzun süre kalan genişletilmiş anahtar, işlem sonunda güvenli biçimde temizlenmelidir. Mevcut kod yerel RoundKey dizisini açıkça silmez.

Tur işlemlerinin kurulması

Şifreleme başlangıçta açık metni ilk tur anahtarıyla XOR işlemine sokar. Ardından dokuz normal tur yürütülür:

SubBytes ShiftRows MixColumns AddRoundKey

Onuncu turda MixColumns uygulanmaz:

SubBytes ShiftRows AddRoundKey

Kod bu istisna için ayrı bir son tur fonksiyonu kullanmaz. Döngü SubBytes ve ShiftRows işlemlerini tamamladıktan sonra tur numarasını kontrol eder. Onuncu turda döngüden çıkar ve son AddRoundKey işlemini dışarıda uygular. Böylece dokuz normal tur ile son tur arasındaki ortak işlemler tekrarlanmaz.

SubBytes, 16 durum baytının tamamını 256 elemanlı S-box tablosundan geçirir. Girdi baytı doğrudan tablo indisi olarak kullanılır. Bu işlem sabit sayıda 16 tablo erişiminden oluşur.

ShiftRows ayrı bir tampon kullanmadan uygulanmıştır. Birinci satır bir konum, ikinci satır iki konum, üçüncü satır üç konum döndürülür. İki konumluk kaydırma için iki ikili takas yeterlidir. Diğer satırlarda yalnız bir geçici bayt kullanılır.

MixColumns, her sütunu GF(2^8) üzerinde sabit bir matrisle çarpar. İlk çıktı baytı şu ilişkiye karşılık gelir:

s'0 = 02.s0 + 03.s1 + s2 + s3

Toplama işlemi XOR'dur. Kod, 02 ve 03 ile sonlu alan çarpımını çalışma anında hesaplamak yerine iki ayrı 256 baytlık tablodan okur:

s'0 = Mul2[s0] XOR Mul3[s1] XOR s2 XOR s3

Diğer üç çıktı aynı matrisin döndürülmüş katsayılarını kullanır. Sütun önce dört geçici bayta alınır. Yeni değerler hesaplanırken önceki değerlerin ezilmesi böylece önlenir.

Şifre çözme aynı yapının tersidir. Başlangıçta son tur anahtarı uygulanır. Turlar geriye doğru yürütülür:

InvShiftRows InvSubBytes AddRoundKey InvMixColumns

Sıfırıncı tur anahtarı uygulandıktan sonra fonksiyon döner. Böylece son ters turda InvMixColumns çalıştırılmaz. Döngü sayacı uint8_t olmasına rağmen sıfıra ulaştığında fonksiyon döndüğü için taşma oluşmaz.

Ters sütun karıştırma işlemi 09, 0B, 0D ve 0E katsayılarını kullanır. Bunların her biri için ayrı tablo tutulmuştur. Şifre çözme bu nedenle şifrelemeden daha fazla tablo erişimi yapar.

Anahtar genişletme dahil edildiğinde tek blokluk şifreleme yaklaşık olarak şu tablo okumalarını içerir:

Anahtar genişletme S-box erişimi 40 SubBytes erişimi 160 MixColumns erişimi 288 Toplam 488

Şifre çözmede sayı yükselir:

Anahtar genişletme S-box erişimi 40 InvSubBytes erişimi 160 InvMixColumns erişimi 576 Toplam 776

Bu sayılar işlemci ardışık düzeni, önbellek ve derleyici optimizasyonundan bağımsız algoritmik erişim sayılarıdır. Ters karıştırma matrisinde her çıktı dört sonlu alan çarpımı gerektirdiği için şifre çözme yolunun tablo yükü daha fazladır.

Bellek ve karmaşıklık

Gerçeklenimde sekiz adet 256 baytlık tablo bulunur:

S-box

Ters S-box

02, 03, 09, 0B, 0D ve 0E çarpım tabloları

Tur sabitleri de eklendiğinde salt okunur tablo verisi toplam 2059 bayttır:

8 x 256 + 11 = 2059 bayt

Bu tasarım hesaplamayı bellekle değiştirir. Sonlu alan çarpımları kaydırma, koşullu indirgeme ve XOR adımlarıyla çalışma anında hesaplanabilirdi. Önceden hazırlanmış tablolar bu işlemleri tek indisli okumaya indirger. İşlem sayısı azalır, fakat yaklaşık 2 KB sabit veri gerekir.

2 KB masaüstü sistemlerde önemsizdir. Küçük mikrodenetleyicilerde program belleği ve RAM yerleşimi birlikte değerlendirilmelidir. Standart C'deki static const tanımı, her mimaride tablonun otomatik olarak istenen salt okunur belleğe yerleşeceğini garanti etmez. Gerçek konum derleyiciye, bağlayıcı betiğine ve mikrodenetleyicinin bellek modeline bağlıdır.

Çalışma anında ana bellek maliyeti 176 baytlık genişletilmiş anahtardır. Buna dört göstericilik durum dizisi ve birkaç geçici bayt eklenir. Heap kullanımı yoktur. Girdi tamponu ayrıca kopyalanmaz.

AES-128 parametreleri sabit olduğu için tek blok işleminin asimptotik karmaşıklığı teknik olarak O(1) değerindedir. Tur ve blok boyutunu değişken kabul eden daha açıklayıcı model şöyledir:

Zaman = O(Nr x B)
Alan  = O(Nr x B) + O(T)

Nr tur sayısını, B bloktaki bayt sayısını, T ise tabloların toplam boyutunu gösterir. AES-128 için Nr=10, B=16 ve T=2059 bayttır.

Kaynak dosyanın başındaki yorumlarda karşılaştırmalı benchmark başarısından söz edilir. Ancak paylaşılan sürümde zaman ölçümü yapan kod bulunmaz. mean, elapsed ve iteration değişkenleri tanımlanmış fakat kullanılmamıştır. Ayrıca her döngüde yapılan printf çağrıları şifreleme maliyetini bütünüyle gölgeler. Bu nedenle kodun optimizasyon tercihleri analiz edilebilir, fakat geçmiş benchmark sonuçları bu dosyadan yeniden üretilemez.

Test kodunun sınırı

Dosyanın sonundaki main fonksiyonu sürekli olarak rastgele açık metin ve anahtar üretir. Veriyi şifreler, ardından çözer. Bu bölüm bir geliştirme deneyi olarak değerlidir, ancak otomatik doğrulama yapmaz. Özgün veri ile çözülmüş veri karşılaştırılmaz ve hata durumunda program durmaz.

rand() burada yalnız test verisi üretmek için kullanılabilir. Kriptografik anahtar veya nonce üretmek için uygun değildir. Fonksiyonun ayrıca <stdlib.h> başlığına ihtiyacı vardır. Paylaşılan dosya bu başlığı içermediği için katı C derlemelerinde örtük fonksiyon bildirimi hatası veya uyarısı oluşur.

Kütüphane çekirdeği ile test programının aynı dosyada bulunması erken geliştirme aşamasında kullanışlıdır. Üretim sürümünde üç parçaya ayrılması daha doğru olur:

1. Sabitleri ve veri tiplerini tanımlayan iç başlık

1. AES çekirdeğini içeren C dosyası

1. Bilinen cevap vektörlerini çalıştıran test programı

Public API tampon uzunluğunu açık biçimde belirtmelidir. Mevcut fonksiyonlar verilen göstergelerin en az 16 baytlık geçerli alanları gösterdiğini varsayar. Null gösterici, kısa tampon veya örtüşme denetimi yapmaz. Kapalı ve kontrollü gömülü kodda bu sözleşme kabul edilebilir. Genel amaçlı bir kütüphanede sınırlar API tarafından görünür hale getirilmelidir.

Güvenlik sınırı

Bu kod bir AES-128 blok şifre çekirdeğidir. Dosya, mesaj şifreleme biçimi tanımlamaz. IV, nonce, padding, kimlik doğrulama etiketi, anahtar türetme veya anahtar saklama mekanizması içermez.

Fonksiyon art arda her bloğa bağımsız uygulanırsa fiilen ECB davranışı oluşur. ECB aynı anahtar altında eşit açık metin bloklarını eşit şifreli bloklara dönüştürdüğü için veri örüntülerini gizlemez. NIST, blok şifreleri için CBC, CFB, OFB ve CTR gibi çalışma kiplerini tanımlar ve ECB kullanımının bu yapısal sızıntısını açıkça belirtir.

Gizlilik yanında bütünlük de gerekiyorsa yalnız şifreleme yeterli değildir. GCM gibi doğrulanmış şifreleme kipleri, şifreli veriye kimlik doğrulama etiketi ekler. GCM'nin güvenliği nonce değerlerinin doğru yönetilmesine bağlıdır. Mevcut çekirdek bu üst katmanı sağlamaz.

Tablo tabanlı tasarımın ikinci sınırı yan kanal güvenliğidir. Döngü sayısı ve dallanma yapısı anahtardan bağımsızdır, fakat S-box ve çarpım tablolarındaki indisler gizli duruma bağlıdır. Önbellekli işlemcilerde bu erişim örüntüsü zamanlama ve önbellek yan kanallarına dönüşebilir. AES üzerindeki tablo erişimli yazılım gerçeklenimlerine karşı pratik önbellek saldırıları akademik çalışmalarda gösterilmiştir.

Önbelleksiz küçük bir mikrodenetleyici bu saldırı sınıfını aynı biçimde taşımaz. Fiziksel erişimi olan saldırganlara karşı güç tüketimi, elektromanyetik yayılım ve hata enjeksiyonu ayrı tehditlerdir. Bu kod maskeleme, çift hesaplama veya hata algılama önlemi içermez.

Kritik bir sistemde canlı kullanım için şu ayrım yapılmalıdır. Algoritmanın standartla uyumlu olması gereklidir, fakat tek başına yeterli değildir. Çalışma kipi, anahtar yönetimi, nonce politikası, yan kanal modeli, hata davranışı ve test kapsamı birlikte doğrulanmalıdır. Düzenlemeye tabi bir ortamda özel bir AES gerçeklenimi, yalnız FIPS 197'yi doğru uyguladığı için doğrulanmış kriptografik modül sayılmaz. NIST de onaylı algoritmanın uygulanması ile FIPS 140 doğrulamasının aynı şey olmadığını açıkça belirtir.

Uygulama ile kriptanaliz arasındaki köprü

Bu kodda S-box, 256 baytlık sabit bir tablodur. İşlemci açısından gereken tek işlem, durum baytını indis olarak kullanıp karşılık gelen değeri okumaktır. S-box'un içindeki çarpımsal ters ve afin dönüşüm çalışma anında görünmez.

Cebirsel kriptanaliz ise aynı işlemi ters yönden açar. Bekir Ünlü'nün S-box birleşik gösterimi üzerine çalışması, tabloyla temsil edilen doğrusal olmayan dönüşümü girişin çarpımsal tersi, dört bit ve sonlu alan sabitleriyle yeniden ifade eder. Bu gösterim, AES denklemlerine farklı cebirsel işlemler uygulanabilmesini amaçlar.

Bir tarafta hızlı yürütme için cebirsel yapı tablolara sıkıştırılır. Diğer tarafta kriptanaliz için aynı yapı yeniden denklemlere açılır. C ile yazdığım bu gerçeklenim ile daha sonra katıldığım kriptanaliz çalışmaları arasındaki en ilgi çekici bağ budur.

Kodun mühendislik değeri yalnız AES'i çalıştırmasından gelmez. Durum yerleşimi, yerinde dönüşüm, tablo önhesaplama ve sabit bellek kullanımı aynı tasarım içinde birleştirilmiştir. Güvenlik sınırı da aynı ölçüde açıktır. Bu çekirdek, doğru kullanıldığında standart AES-128 dönüşümünü üretir. Güvenli bir kriptografik sistem ise bu çekirdeğin çevresinde kurulacak kip, kimlik doğrulama, anahtar yönetimi ve yan kanal önlemleriyle ortaya çıkar.