替換排列網路之線性攻擊策略

Abstract

線性攻擊法是針對區塊加密系統的最重要的法法之一。在這篇論文裡，我們著重在使用線性攻擊法來攻擊替換排列網路，並且實際的攻擊一個區塊大小為 16 ，金鑰長度為 32 的一個 4 層的替換排列網路。我們將會討論一些在替換排列網路上的線性攻擊法的策略，並給出詳細的演算法。首先我們先了解 s-box 的定義，接著利用 Piling-up Lemma 來計算一條路徑的線性機率的大小。然後我們會說明如何去尋找一條最佳路徑並去攻擊它來求得金鑰的部份內容。我們也會研究一些能夠增加攻擊的成功率的技巧。

之後我們會提出尋找路徑的演算法，攻擊的策略，以及 backtracking 的策略。對於找出來的條路徑，我們會計算我們需要多少組的明文/密文對來做攻擊。最後我們會真正的去攻擊一個替換排列網路，並秀出我們使用這些策略之後的呈現出來的效能。

Linear cryptanalysis is one of the most important attacks of block cipher systems such as Feistel netowrks and substitution-permutation networks. In this thesis , we will focus on linear cryptanalysis on SPNs, and give a complete linear attacks on a 4-round SPN with 16-bit block size and 32-bit key length. We will discuss the strategies of linear cryptanalysis on SPNs and give the detial algorithms. We first define the linear probability of an s-box, and use Piling-up Lemma to compute the linear probability of a trail. Then we describe how to find the best trail and then attack the subkey bits. We also study some techniques to improve the success rate of the attack.

Next we give the algorithms of finding the trails, attack strategies, and the backtracking strategy. We will discuss how many plaintext/ciphertext pairs do we need for the given trail. Then we attack a simple SPN structure to show the performance of these strategies.