Blok şifreleme algoritmalarına uygulanan İntegral analizinin geliştirilmesi
Enhancement of Integral Cryptanalysis for some block ciphers
Yazar: FATİH DEMİRBAŞ
Danışman: DOÇ. DR. ORHUN KARA
Marmara Üniversitesi / Fen Bilimleri Enstitüsü / Siber Güvenlik Ana Bilim Dalı / Bilgi Güvenliği Mühendisliği ve Kriptografi Bilim Dalı
Derece: Yüksek Lisans, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
İntegral kriptanaliz, integral özelliklerin bir blok şifreleme algoritmasının çevrimleri boyunca yayılımını inceleyen simetrik anahtarlı yapı taşları için uygulanan bir kriptanalitik yöntemdir. Bir integral karakteristik oluşturmak ve bu karakteristiği kullanarak anahtar elde etmek, integral atağın iki ayrı aşaması olarak düşünülebilir. En önemli aşama, integral karakteristiğin nasıl oluşturulacağıdır. Bu tez çalışmasında, yeni integral özellikler tanımlayarak bazı blok şifreleme algoritmaları için yeni bir integral karakteristik oluşturma yöntemi sunulmaktadır. Bu integral özelliklerin, bir blok şifreleme algoritmasının çevrimleri boyunca yayılımasını sağlamak için algoritmanın ikili yayılım katmanı ve anahtar şeması algoritmasından faydalanılmaktadır. Bu integral özellikleri ve yöntemimizi kullanarak, bir blok şifreleme algoritması için bilinen ilk yinelemeli integral karakteristik oluşturulmaktadır. Yöntemimizin ne kadar etkili olduğunu göstermek adına, Bayt Tabanlı SPN Blok Şifreleme (M,n)(BSPN) algoritması için oluşturulan bu yinelemeli integral karakteristik R=2^(n⋅ (M-2))+2 çevrime kadar uzatılabilmektedir. En fazla ((M-1)¦2)+1 seçili açık metin kullanılarak, herhangi bir R-çevrim (R≤ 2^(n⋅ (M-2))+3) BSPN algoritması için ilk defa kaba kuvvet saldırısından daha hızlı bir anahtar elde etme saldırısı yapılmış, saldırının zaman maliyeti anahtarın özelliğine göre 2^(2⋅ n)'ya kadar düşmüştür. Genel olarak, saldırıların maliyetleri çevrim sayısı arttıkça artmaktadır. Fakat bu tez çalışmasında buna karşı bir örnek verilmektedir: Bir j değeri için R= 2^(n⋅ j)+3-çevrim BSPN'e yapılan saldırının zaman karmaşıklığı, çevrim sayısı yaklaşık olarak 2^(n⋅ j -p) azaltıldığında yaklaşık olarak 2^p katına çıkmaktadır. Anahtar elde etme saldırısının zaman maliyeti, diğer çevrim sayılarından neredeyse bağımsızdır. Ek olarak; geliştirilen yeni karakteristik oluşturma yöntemi Midori64 blok şifreleme algoritması için bilinen en etkili integral karakteristiğin oluşturulması için kullanılmıştır. Bu tez çalışmasının sonuçları, bazı blok şifreleme algoritmalarının anahtar şeması tasarımı için yeni bir güvenlik kriteri ortaya koymaktadır.

Abstract:
In this study, we provide a new method to construct integ\-ral characteristics for some block ciphers by introducing new integral properties. We exploit the binary diffusion layer and key schedule algorithm of a block cipher to propagate these integral properties through rounds. We construct the first iterative integral characteristic for a block cipher to the best of our knowledge by using the integral properties defined and our method. We extend this iterative characteristic for the Byte-oriented Substitution-Permutation Network (M,n)-(BSPN) block cipher where each blok of BSPN contains M number of n× n S-Boxes, the block and key sizes are given as M⋅ n.  Using at most ((M-1)¦2)+1 chosen plaintexts, we mount key recovery attacks for the first time on the BSPN and recover the key with a time complexity as low as 2^(2⋅ n) for R -round BSPN for any R≤ 2^(n⋅ (M-2))+3 depending on the characteristic of the key. In general, the complexity of attacks get higher as the number of rounds increases. In this work, we provide a counter example: the time complexity of our attack on  R= 2^(n⋅ j)+3 rounds increases by a factor of roughly 2^p when we decrease the number of rounds by a factor roughly 2^(n⋅ j -p). The time complexity of the key recovery is almost independent of the number of rounds for any other rounds. We also use our method to construct the most efficient integral characteristics found so far for Midori64. Our results impose a new security criteria for the design of the key schedule algorithm for some block ciphers.