Crypto 101 – [2] Block Cipher Encryption ve DES Analizi

Merhaba

Crypto 101 isimli yazı serimizin ikinci bölümünde Block Cipher algoritmalarına girişi ve DES şifreleme algoritmasının derinlemesine analizi ele alıyor olacağız. Bir önce ki  yazıya https://www.mehmetince.net/crypto-101-1-merhaba-exclusive-or-xor/ adresinden ulaşabilirsiniz. 

Block Ciphers

Block cipher’lar sabit uzunlukta ki blokları şifrelememizi sağlayan algoritmalara verilen genel isimdir. Bu işlem aşağıdaki matematiksel denklem ile ifade edilmektedir.

C = E(k, P)

E isimli fonksiyon block cipher algoritmasını, k algoritma tarafından kullanılacak key değerini ve P ise Plaintext değeri ifade etmektedir.
block cipher encrypt

Block Cipher, symmetric-key encryption ailesine ait bir yöntemdir. Simetrik Anahtar Şifreleme olarak Türkçe’ye çevirebileceğimiz symmetric-key encryption bir plain-text verinin Alice ve Bob arasında gidip gelmesi süresince aynı anahtarın kullanılıyor olması anlamına gelir. Bir diğer söyleyiş ile, şifreleme için kullanılan anahtar aynı zaman da deşifreleme işleminde de kullanılmaktadır. Tüm süreç bu anahtarın Alice ve Bob harici kimse tarafından bilinmiyor olmasıyla ayakta kalmaktadır. Özetle; algoritmanın karmaşıklığına bakılmaksızın, anahtarınız ne kadar gizli ve ne kadar zor tahmin edilebilir ise, symmetric-key encryption kullanarak sakladığınız veriniz de o kadar güvenli olacaktır.

Tüm yazı serisi boyunca bolca kullanıyor olacağımız “Ne/neden ?” soru kalıbına tekrar gelmiş bulunuyoruz. One-time pad’e göre Block Cipher’ların farkı nedir ? Block Cipher’ların özellikleri nelerdir ? Bu sorulara aşağıda ki şekilde cevap verebiliriz.

  • Symmetric-encryption ailesine aittirler.
  • Fixed-lenght dediğimiz yaklaşım ile, plain-text ve key sabit uzunlukta gruplara bölünerek şifreleme işlemi gerçekleştirilmektedir.
  • Anahtar ile cipher-text yani şifreli metin arasında herhangi bir ilişki kurulamıyor olmalıdır.
  • Aynı şekilde cipher-text yani şifreli metine bakarak anahtar hakkında herhangi bir tahminde bulunulamıyor olmalıdır.
  • Şifreli metin üzerinde yapılacak 1 bit’lik değişiklik bile plain-text’in en az %50’sinin değişmesine neden olmalıdır.

Son maddeyi göz önünde tutarak bir önceki bölümde ele alınan OTP (one-time pads) yaklaşımını düşünelim. Hatırlarsanız aynı key ile encrypt edilmiş tamamiyle 2 farklı resmin cipher-text hallerini birbiri ile XOR işlemine soktuğumuzda kesişen “Mehmet” ve “InceBlog” kelimelerini vermekteydi. İkinci resimde ki “InceBlog” yerine “InceBlag” yazısı olsaydı ( o yerine a harfi geldi ) sonucun sadece “o” ve “a” harflerinin geldiği bölge anlamsız hale gelecekti. Kalan resmi hala daha aynı şekilde net ve okunabilir halde elde ediyor olacaktık.

One-time-pads ile Block Cipher arasında ki farkin anlaşılabilir olması için bilinen en eski Block Cipher algoritmalarından birisi olan ve ilerleyen bölümlerde detaylıca ele alacağımız DES ile ilgili ufak bir python testi gerçekleştirebiliriz.

from Crypto.Cipher import DES

key = "g1zl1KEY"
plain_text = "Mehmet-Ince-Blog"

des = DES.new(key, DES.MODE_ECB)
cipher_text = des.encrypt(plain_text)

print "Original CipherText   = {0}".format(repr(cipher_text))
# Cipher text is = '\x9b\xca\x92\xe0\x82\xb0\xf9\xb5\xfa5\x0e\xe0\xbb\x84@`'
# Change one byte= '\x9b\xcb\x92\xe0\x82\xb0\xf9\xb5\xfa5\x0e\xe0\xbb\x84@`'
print "Change only one thing = {0}".format(repr('\x9b\xcb\x92\xe0\x82\xb0\xf9\xb5\xfa5\x0e\xe0\xbb\x84@`'))

print "Original CipherText decryption  = {0}".format(des.decrypt(cipher_text))
manipulated_cipher = '\x9b\xcb\x92\xe0\x82\xb0\xf9\xb5\xfa5\x0e\xe0\xbb\x84@`'
print "One thing changed CipherText    = {0}".format(des.decrypt(manipulated_cipher))

Bu basic uygulamanın çıktısı ise aşağıdaki gibidir.

Original CipherText   = '\x9b\xca\x92\xe0\x82\xb0\xf9\xb5\xfa5\x0e\xe0\xbb\x84@`'
Change only one thing = '\x9b\xcb\x92\xe0\x82\xb0\xf9\xb5\xfa5\x0e\xe0\xbb\x84@`'
Original CipherText decryption  = Mehmet-Ince-Blog
One thing changed CipherText    = *p,9p^�nce-Blog

Görüldüğü üzere sadece ve sadece 1 karakterin değiştirilmesi ( \xca yerine \xcb geldi ) plain-text’in %50’sinin değişmesine neden oldu.

Block cipher’lar ile ilgili bu uzun girizgahtan sonra artık elleri gerçekten çamura bulaştırmanın vakti geldi. Yazı serisinin bu anına kadar bir çok örnekleme ve küçük kriptoloji modelleri kurarak ilerlemiştik. Artık sıra gerçekten bir şifreleme algoritmasını ele almak ve tüm iç yapısını anlamaya geldi. Kendinizi toparlayın, olabildiğinde odaklanın, anlamadığınız yerlerde durup 2-3 paragraf geriye gidip tekrar okuyun, yapacağımız işlemleri kağıt-kalem ile tekrar edin (ben böyle çalışarak anlamıştım).

DES ( Data Encryption Standart )

Amerika Birleşik Devletleri bundan yıllar önce “Bizim bir kriptoloji algoritması standartına ihtiyacımız var. Bunu kim yapabilir ?” sorusuyla çıka geldi. IBM bu çağrıya cevap vererek “Biz bunu gerçekleştireceğiz” dedi ve Horst Fiestel tarafından geliştirilmiş olan bir yöntemi temel alarak DES algoritmasını 1974 yılında ortaya koydu. Bu algoritma ise doğrudan NSA tarafından 1974 yılında kullanılmaya başlandı. İlginçtir ki; 1974 yılına kadar daha önce ne USA ne de başka herhangi bir ülke tarafından böyle bir ihtiyaç ortaya çıkmamıştı… (Caesar, Enigmalar bir kenara, standart hazırlamak tamamiyle ayrı bir disiplindir. )

1977 ve 1998 yılları arasında DES şifreleme algoritması USA tarafından standart olarak kabul görmüştür. Bugünlerde ise DES’in kullandığı anahtarın yani key’in kısa olmasından kaynaklanan ciddi problemler nedeniyle güvensiz bir şifreleme algoritması olarak kullanımına hemen hemen tamamiyle son verilmiştir.

DES Internals

DES’in önce genel hatları ile daha sonra ise iç mekanizmalarının nasıl çalıştığını analiz edeceğiz. Block cipher konusuna girişte verdiğimize çok benzer şema ile başlayabiliriz.

DES abstract

Resimden anlaşıldığı üzere DES encryption isimli kutu şifrelenecek metni 8 byte ( 64bit) ‘lık blocklara bölerek işleme alır ve çıktı olarak gene 64 bit’lik ciphertext üretmektedir. Son derece basit, yüzeysel ve anlaşılır şekilde DES algoritması bu şekilde ifade edilir. Eğer elimize büyüteci alıp “DES Encryption” isimli kutuya yaklaşırsak aşağıda ki resmi görüyor olacağız. ( Resmi büyütmek için üzerine tıklayınız.)

Des feistel network-draw.io-2

Bu diagram DES şifreleme algoritmasının iç yapısını kismen anlatmaktadır. Tüm adımları tek tek anlatmaya geçmeden önce sizi bir kez daha yukarıda ki grafiği kendi başınıza anlayamaya devam ediyorum. Bu sayede aşağıda anlatılan akış diagramını takip etmesi çok daha kolay olacaktır.

  1. Ciphertext hale getirilecek plaintext veri 8 byte’lık blocklara bölündü ve DES algoritmasına girmeye hazır halde.
  2. İlk 64 bitlik plaintext veri alındı.
  3. Initial Permutation adını verilen matematik fonksiyonuna girdi. ( Daha sonra değineceğiz. )
  4. Hala daha plaintext halde olan verimiz 32’şer bitlik 2 eşit alt bloğa ayrıldı. BU bloklar Left-0 ve Right-0 olmak üzere isimlendirildil.
  5. Bu sırada 56 bit’lik anahtarımız Subkey generation adı verilen başka bir fonksiyondan geçti ve her 32bit’lik alt bloklarımızda kullanılmak üzere 48 bitlik alt-anahtar’lar üretildi.
  6. Right-0 yani R0 isimli 32 bitlik alt blok K1 olarak adlandırılan alt anahtar ile birlikte F isimli fonksiyondan geçti. ( Bu fonksiyonu daha sonra mercek altına alacağız. )
  7. F fonksiyonunun çıktısı Left-0 yani L0 ile XOR işlemine girdi.
  8. XOR işleminin sonucu yeni durumumuzun R1 bloğu, bir önce durumun R0 bloğu ise yeni durumun L1 bloğu olarak atandı.
  9. Bu işlem tam olarak 16 kere tekrar edildi. Her tekrar’a round adı verildi.
  10. En son ise başlangıçta yapılan Initial Permutation işleminin tam tersi gerçekleştirilerek 64bit’lik ciphertext elde edildi.

Öncelikle bu karmaşayı birazcık daha netleştirelim. Öncelikle 1-2 terime açıklık getirmek gerek.

Initial Permutation isimli fonksiyon plaintext verimizin üzerindeki bitlerin yerlerini değiştirmektedir. Bu değişiklikler look-up table adı verilen bir tabloya göre yapılır. BU tablo sabittir ve 1970 yılından ( yani DES’in icadı ) beri herkes tarafından bilinmektedir. Bu durumda akıllara şu soru gelir;

“Madem bu işlem herkes tarafından geri döndürülebilir halde ise, bu işlem güvenli değildir. Peki o zaman niye gerçekleştirilmektedir ?”

Initial permutation işlemi elektrik&elektronik dünyası ile ilgilidir. Bu işlemin kriptoloji dünyası ile hiçbir ilgisi yoktur. Bu nedenle fonksiyonun içerisine girip “Neler oluyor burada ?” diye sormayacağız. Merak eden arkadaşlar  için “DES Initial Permutation table” keyword’u google için yeterli olacağını size garanti ediyorum.

İkinci bilinmeyen terim ise “Subkey generation function.” Bu fonksiyon 56 bit uzunluğunda ki anahtardan 48 bit’lik  alt-anahtarlar üretmektedir. Sadece 64 bitlik bir bloğun şifrelenmesinin ele alındığı bu grafikte 16 kere tekrar eden round loop bulunmaktadır. Her loop’ta farklı 48 bit’lik alt-anahtarlar kullanılmalıdır. Bu nedenle “Subkey generation” bizim için bir alt-anahtar üretici fabrika olarak düşünülebilir. Çalışma mekanizması ise 56bit’i ortadan ikiye böler. 28 bit’lik alt blokları birer veya ikişer bit kaydırır. Her 28bit’lik desteden 24bit seçilerek 48 bitlik alt-anahtar üretilmiş olur.

Üçüncü bilinmeyen terim ise F fonksiyonudur ki birazdan detaylıca ele alacağız. Şimdilik sadece Right ve K verilerini parametre alan fonksiyon olarak düşünmeniz yeterlidir.

XOR işlemi ise bildiğimiz XOR işleminden hiç farklı değildir. Bir sonraki tura geçmeden önce tek yapılması gereken işlem yeni 32’şer bitlik yeni sağ-sol blokların hazırlanması. Round-1’i ele alırsak, R0 ve L0 olmak üzere elimizde iki adet blok bulunmakta ve ikiside şu anda plaintext halde. L0 ile F(R0,K) yani F fonksiyonu çıktısının XOR işlemine girdiği görülmektedir. Ardından yeni blocklar R1 ve L1 ataması gerçekleştirilecektir. Bu atama şu şekilde gerçekleştirilecektir; Round-1’in sağ bloğu yani R0 değeri doğrudan Round-2’nin L1 değeri,  XOR işleminin sonucu ise Round-2’nin R1 değeri olacaktır. Bu atama algoritması aşağıdaki şekilde denklem haline getirilebilir.

Li = Ri-1

Ri = Li-1 ⊕ F(Ri-1,Ki)

F-function

En başta elimize büyüteci alıp DES şifreleme algoritmasına baktığımızda yukarıda ki akış şemasını görmüştük. Bu şemasında F isimli bir fonksiyonumuz vardı. Şimdi ise bu fonksiyonu analiz edeceğiz.

DES F-function-draw.io

Hatırlarsanız F fonksiyonumuz 48 bit uzunluğunda Key ve 32 bit uzunluğunda Right-N bloğunu parametre olarak almaktaydı. 48bit’lik Key ile XOR işleminin olması için 32 bit uzunluğunda ki bloğumuz 48 bit’e Expansion isimli fonksiyon ile genişletilecektir. Bu noktada “En başta 56 bitlik anahtardan 48 bit’lik alt-anahtarlar oluşturduk. Neden doğrudan 32 bitlik alt-anahtarlar yapıp direk 32 bitlik bloklar ile rahatça XOR işlemi yapmıyoruz ?” sorusunu sorabilirsiniz. Bunun nedeni Shannon isimli bilim insanının Block cipher’lar için ortaya koyduğu iki temel prensipten ötürü geldiğini söyleyebilirim. Bu prensipler, Confusion ve Diffusion  isimli iki atomik ifadeden oluşmaktadır.

Confusion; Plaintext ile ciphertext arasında ki ilişkinin belirsiz olması.

Diffusion; Plaintext’in her bitinin, cipher text’in bütününe etki etmesi.

Bu Expansion fonksiyonu ise Diffusion gereksinimini karşılaşamaktadır. 32bit’lik veriye, yeni değer eklemeden 48 bit’e çıkartmak için belirli bitleri tekrar eder şekilde kullanmak gerekir. Böylece normalde sadece 1 bit ile XOR işlemine girecek değer, farklı bit’ler ilede XOR’lanır. Bu da Shannon prensibini karşılamış olacaktır.

Ortaya 48 bitlik XOR’lanmış bir veri çıktı. Bu veri 6 bit’lik daha da ufak bloklara bölünerek S-box adını verdiğimiz fonksiyonlara gitmektedir. S-box adını verdiğiniz bu fonksiyonlar 6 bit’lik alt veri kümemizi 4’bit ile ifade ederek toplamda 32 bit’e dönüştürürler. Bu sayede F-fonksiyonundan çıkıp Li ile XOR işlemine girmeye hazır bir output elde edilmiş olur.

Serinin devamı olan 3. yazı yayınlandı. https://www.mehmetince.net/crypto-101-3-dese-yonelik-saldirilar-3des-aes-metodlari/