Geri Dön

Usage of mixed integer linear programming in cryptanalysis of block ciphers

Blok şifreleme algoritmalarının kripto analizinde ktplyaklaşımının kullanılması

PDF İndir

  1. Tez No: 985676
  2. Yazar: HALİL İBRAHİM KAPLAN
  3. Danışmanlar: PROF. DR. ENVER ÖZDEMİR
  4. Tez Türü: Yüksek Lisans
  5. Konular: Matematik, Bilim ve Teknoloji, Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Mathematics, Science and Technology, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2025
  8. Dil: İngilizce
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Bilişim Uygulamaları Ana Bilim Dalı
  12. Bilim Dalı: Bilgi Güvenliği Mühendisliği ve Kriptografi Bilim Dalı
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Blok şifrelerin kriptoanalizi, simetrik kriptografi alanında hâlen en kritik araştırma konularından biri olarak önemini korumaktadır. Özellikle son yıllarda gelişen gömülü sistem teknolojileri, Nesnelerin İnterneti (IoT) uygulamaları ve RFID sistemleri gibi kaynak kısıtlamalarının baskın olduğu alanlarda kriptografik algoritmaların etkinliği ve verimliliği daha da ön plana çıkmıştır. Bu tür ortamlarda kullanılan cihazlar, genellikle sınırlı işlem gücüne, düşük enerji kapasitesine ve kısıtlı bellek kaynaklarına sahiptir. Bu nedenle, standart şifreleme algoritmaları — örneğin AES — bu sistemlerde kullanılmak istendiğinde performans sorunları veya aşırı kaynak tüketimiyle karşılaşılmaktadır. Bu gerçeklik, hafif blok şifreleme algoritmalarının geliştirilmesini ve değerlendirilmesini zorunlu kılmaktadır. Hafif şifreleme alanında öne çıkan alternatif algoritmalardan biri ITUbee blok şifre algoritmasıdır. ITUbee, hem yapısal sadeliği hem de düşük kaynak tüketimi ile özellikle kaynak kısıtlı ortamlarda kullanılmak üzere tasarlanmıştır. Ancak yeni bir şifreleme algoritmasının geliştirilmesi kadar, onun güvenliğinin sistematik ve derinlemesine incelenmesi de büyük önem arz etmektedir. Kriptografi literatüründe kabul gören standartlara göre, bir algoritmanın etkinliği yalnızca performans ölçütleriyle değil, aynı zamanda güçlü kriptanalitik dayanıklılık ile de değerlendirilmektedir. Bu noktada, literatürde en yaygın ve etkili kriptoanaliz yöntemleri olan diferansiyel kriptoanaliz ve doğrusal kriptoanaliz öne çıkmaktadır. Bu saldırı teknikleri, blok şifrelerin yapısal zayıflıklarını tespit ederek, algoritmanın rastgeleliğe ne ölçüde yaklaştığını analiz etmeyi amaçlar. Diferansiyel kriptoanaliz, belirli giriş farklarının çıkışlara nasıl yansıdığını inceleyerek, yüksek olasılıklı fark yolları (differential trails) üzerinden anahtar bilgisi elde etmeye çalışırken; doğrusal kriptoanaliz, giriş ve çıkış bitleri arasında doğrusal bağıntılar kurarak benzer bir bilgi sızdırma tekniği uygular. Her iki yöntemin de başarılı olabilmesi için, şifreleme algoritmasında belirli yapısal düzenliliklerin veya zayıflıkların mevcut olması gerekir. Bu iki yönteme ek olarak, ilişkili anahtar diferansiyel saldırılar (related-key differential attacks) da etkin kriptoanaliz yöntemleri arasındadır. Bu saldırı türü, saldırganın belirli farklara sahip birden fazla anahtar üzerinden işlem yapabilmesine olanak tanıyan genişletilmiş bir modeldir. Özellikle basit veya yapılandırılabilir anahtar genişletme mekanizmalarına sahip algoritmalar, bu tür saldırılara karşı savunmasız kalabilmektedir. Ancak, modern blok şifre algoritmalarının karmaşık yapıları göz önünde bulundurulduğunda, manuel (el ile) analiz yöntemlerinin uygulanabilirliği büyük ölçüde azalmaktadır. S-box yapısında veya doğrusal dönüşüm katmanlarında yapılan küçük bir değişiklik bile tüm analiz sürecinin baştan tasarlanmasını gerektirir. Bu durum, kriptoanaliz süreçlerinin otomatikleştirilmesini ve daha verimli bir biçimde yürütülmesini gerekli kılmaktadır. Bu bağlamda, Karma Tamsayılı Doğrusal Programlama (KTPL) temelli kriptanaliz yaklaşımların önemi artmıştır. KTPL, doğrusal programlamanın klasik yapısını tamsayı değişkenlerle birleştirerek daha karmaşık karar problemlerini çözebilen güçlü bir optimizasyon tekniğidir. Kriptoanaliz bağlamında KTPL, bir şifreleme algoritmasının bileşenlerini (S-box, XOR, doğrusal dönüşüm, taşıyıcı matrisler vb.) doğrusal eşitsizlikler aracılığıyla matematiksel olarak modelleme imkânı sunar. Bu sayede, kriptoanalitik saldırılar bir optimizasyon problemi haline getirilir ve mevcut yazılımlar aracılığıyla etkili biçimde çözüm aranabilir. Özellikle hafif blok şifrelerde, KTPL modelleri düşük tur sayıları için tüm olası fark yollarını tarayabilecek kapasitededir. Bu da KTPL'yi, klasik arama yöntemlerine (örneğin brute-force, ağaç arama, rastgele örnekleme) kıyasla daha etkili ve sistematik bir araç haline getirmektedir. Tez kapsamında, öncelikle simetrik şifreleme algoritmalarının temel yapı taşları açıklanmıştır. Substitution-Permutation Network (SPN) yapıları, Feistel ağları, ARX tabanlı şifreler ve sünger yapılar (sponge constructions) gibi yaygın kullanılan mimariler ele alınmış; bu yapıların güvenlik ve performans üzerindeki etkileri ayrıntılı bir biçimde incelenmiştir. Ardından, doğrusal, diferansiyel ve ilişkili anahtar diferansiyel kriptoanaliz teknikleri teorik temelleriyle birlikte değerlendirilmiştir. Bu bağlamda, kriptografik saldırıların temel varsayımları, başarı kriterleri ve uygulama koşulları detaylandırılmıştır. Devamında, doğrusal programlama (LP) ve KTPL hakkında genel bilgiler sunulmuş; ardından KTPL'nin kriptoanaliz bağlamındaki kullanımı üzerinde durulmuştur. Özellikle“dallanma sayısı”(branch number) ve“H-temsili”(H-representation) gibi kavramlar tanıtılmış, bu yapıların doğrusal eşitsizliklerle nasıl modellenebileceği örnekler ile açıklanmıştır. Branş sayısı, doğrusal dönüşüm matrislerinin difüzyon kapasitesini ölçen kritik bir metrik olup, güvenlik değerlendirmelerinde sıklıkla kullanılmaktadır. H-temsili ise doğrusal olmayan bileşenlerin (örneğin S-box'ların) doğrusal kısıtlarla ifade edilmesine olanak tanıyan geometrik bir modelleme yaklaşımıdır. Tezde ayrıca, KTPL modellerinde kullanılacak eşitsizlik sayısını azaltmaya yönelik olarak geliştirilen iki algoritma — ''Greedy'' ve ''New-Reduction'' — tanıtılmıştır. Bu algoritmalar, KTPL modellemelerinde performansı artırmak ve çözüm sürelerini düşürmek için kritik öneme sahiptir. Her bir algoritma, farklı hedef fonksiyonlara göre çalışmakta olup, çözüm uzayında daha verimli arama yapmayı mümkün kılmaktadır. Tüm bu teorik temeller ve araçlar kullanılarak, tezde ITUbee blok şifre algoritması detaylı bir biçimde modellenmiş ve analiz edilmiştir. ITUbee, Feistel yapısına dayalı, 64 bit blok boyutuna sahip ve 128 bit anahtar kullanan bir algoritmadır. Tasarımı itibarıyla hafif cihazlar için optimize edilmiştir. Tezde, ITUbee'nin her bir bileşeni — S-box, doğrusal katman, anahtar genişletme mekanizması, Feistel yapısı vb. — KTPL modelleri ile ifade edilmiş ve bu modeller üzerinden saldırı karakteristikleri elde edilmiştir. Elde edilen sonuçlara göre, ITUbee algoritması üç çevrimden sonra diferansiyel ve doğrusal saldırılara karşı güvenlidir. Bu, algoritmanın yazarlarının teorik olarak sunduğu güvenlik varsayımlarını desteklemektedir. Ancak ilişkili anahtar diferansiyel saldırıları açısından yapılan analizler, ITUbee algoritmasının yazarlarının teorik olarak gösterdiği 10 çevrimden daha güvenli olduğu, 8 çevrim ve sonrası için bu saldırı yönteminin uygulanamayacağı göstermiştir. Elde edilen karakteristikler, tezde tablo ve grafiklerle detaylı bir biçimde sunulmuş; kullanılan KTPL modelleri ise ekler kısmında verilmiştir. Bu çalışma, yalnızca ITUbee algoritmasının güvenliğini değerlendirmekle kalmayıp, aynı zamanda KTPL temelli modelleme yöntemlerinin pratikte nasıl uygulanabileceğini gösteren sistematik bir rehber sunmaktadır. Ayrıca, KTPL'nin hafif blok şifrelerin analizi için güçlü ve ölçeklenebilir bir araç olduğunu ortaya koymakta, gelecekteki kriptografik analiz çalışmaları için önemli bir zemin hazırlamaktadır.

Özet (Çeviri)

Cryptanalysis of block ciphers remains a fundamental area of research in symmetric cryptography, especially as lightweight cryptographic algorithms continue to be deployed in resource-constrained sytems like IoT devices and RFID systems, and embedded applications. These environments often impose strict limitations on hardware resources, energy consumption, and memory footprint, rendering standard algorithms like AES inefficient or impractical. As a result, alternative lightweight ciphers—such as the ITUbee block cipher—have been proposed to meet these requirements. However, the adoption of new algorithms necessitates rigorous and comprehensive security evaluations. Among the most influential cryptanalytic methods are differential cryptanalysis and linear cryptanalysis, which target structural properties of the cipher to exploit non-random behavior. Additionally, related-key differential attacks provide an extended model that considers adversaries with control over key differences, making them particularly relevant in analyzing ciphers with simple or predictable key schedules. For any cipher, resistance against these attacks is essential. Manual analysis of differential, linear and related-key differential characteristics becomes increasingly infeasible as cipher complexity grows. Changes to components such as the S-box, Feistel structure, or matrix-based linear layer often require re-analysis from scratch. This has motivated the development of automated cryptanalysis techniques, where MILP become a leading approach. MILP enables the systematic formulation of cryptanalytic problems using linear constraints, allowing modeling of S-box, XOR operations, MDS matrices and propagation probabilities. In recent years, MILP modeling of cryptographic attacks applied to many different block ciphers to prove the security of the cipher against cryptographic attacks. In traditional cryptanalysis methods (pattern search methods, brute force method, tree-search method etc. )searching all possible patterns is impossible for most cipher because of the computational costs. Unlike the traditional methods, MILP is very efficient tool for searching possible patterns for most of the ciphers(Especially for used for lightweight ciphers because of small structures like s-box). In this thesis, we begin by presenting an overview of symmetric encryption algorithms, including Substitution-Permutation Networks, Feistel structures, ARX ciphers, and sponge constructions. We then provide a comprehensive discussion of cryptanalytic techniques, with particular emphasis on linear, differential, and related-key differential cryptanalysis. Subsequently, we introduce the fundamentals of Linear Programming and Mixed-Integer Linear Programming , and formally define key concepts such as the branch number and the H-representation of block cipher components. We describe two algorithms—Greedy and New-Reduction—developed for minimizing the number of constraints required to represent cryptographic components within MILP models. Following this, we detail the MILP-based modeling of essential cipher operations, including XOR, linear transformations, S-boxes, and three-forked branches. The ITUbee block cipher is then examined in detail, and the previously introduced methods are applied to this cipher. We construct MILP models to assess the security of the ITUbee algorithm against differential, linear, and related-key differential attacks. These models are used to derive corresponding cryptanalytic characteristics. While the original designers of ITUbee claimed theoretical resistance to linear and differential attacks, our MILP-based analysis confirms that such attacks are ineffective beyond three rounds. Furthermore, While the designers suggested security after 10 rounds, our models shows that there is no practical related-key differential characteristics after 8 rounds. The obtained characteristics are presented within the thesis, and all MILP models are provided in the appendix for reference.

Benzer Tezler

  1. Tez No

    599124

    Demand side management – load scheduling optimisation in smart home by using mixed integer linear programming

    Karmaşık tamsayı doğrusal programlama ile akıllı ev uygulamalarında talep tarafı yönetimi ve yük zamanlama optimizasyonu

    SARIA ALHAMAD

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Ev EkonomisiKocaeli Üniversitesi

    Enerji Sistemleri Mühendisliği Ana Bilim Dalı

    PROF. DR. ENGİN ÖZDEMİR

  2. Tez No

    997631

    İlaç endüstrisinde blister ambalaj tasarımının ve üç boyutlu ambalaj düzenleme kararlarının entegre optimizasyonu

    Integrated optimization of blister packaging design and three-dimensional package arrangement decisions in pharmaceutical industry

    SERAY ÇAKIRGİL

    Doktora

    Türkçe

    Türkçe

    2025

    Endüstri ve Endüstri MühendisliğiTobb Ekonomi ve Teknoloji Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EDA YÜCEL

  3. Tez No

    376156

    Elektrik üretim planlamasında çok amaçlı optimizasyon yaklaşımı: Türkiye örneği

    multiobjectıve optımızation approach for electrıcıty generatıon planning: Case of Turkey

    EVREN CAN ÖZCAN

    Doktora

    Türkçe

    Türkçe

    2013

    Endüstri ve Endüstri MühendisliğiGazi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. SERPİL EROL

  4. Tez No

    496431

    Ana sisteme bağlı bir mikro şebeke için gün içi elektrik piyasasına dayalı çizelgeleme

    Energy scheduling for a microgrid connected to the main grid based on real time electricity market

    EMRAH ERDEM UFLUOĞLU

    Doktora

    Türkçe

    Türkçe

    2018

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. GÜLGÜN KAYAKUTLU

  5. Tez No

    439519

    Genişletilmiş bir malzeme gereksinim plânlaması modeli ve uygulaması: Türkiye kuyumculuk sektörü

    An extended MRP approach and application: Turkish jewelry industry

    ERHAN YAZICI

    Doktora

    Türkçe

    Türkçe

    2016

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MURAT BASKAK

    PROF. DR. GÜLÇİN BÜYÜKÖZKAN FEYZİOĞLU

Geri Dön