Advanced Encryption Standard
===

###### tags: `nsysu` `information security` `AES`

## 目錄
[TOC]

*[AES]: Advanced Encryption Standard
*[DES]: Data Encrption Standard
*[NIST]: National Institute of Standards and Technology

# AES 的背景

AES 是用來取代 DES 的，他是一種加密的標準
由美國國家標準與技術研究局 (NIST) 所向大眾徵選而來的。

屬於對稱式 block encryption 加密演算法的一種。

## DES
- DES 是一種典型的 Block Cipher Encritption (塊加密) 演算法
- 將固定長度的明文，透過一系列的操作，加密成同樣長度的密文
- 對稱性加密
- key 長度 56 bit (運算時還是拿 64 bit，但實際上只拿 56 bit，剩下的拿來做奇偶校正)

### 運算流程

1. 將明文對半切
2. 輸入進置換函數 IP，僅是置換，沒有加密上的意義，是以前用來簡化輸入輸出的 legacy 而已
3. 將半塊的明文（右）送進 F 函數加密
4. 將原本的半塊（左）和 F(右半塊) 互相做 XOR
5. 調換輸入
- 將 XOR 的輸出，當作下一個 F 函數的輸入
- 將原本的右半塊當作下一輪 XOR 的輸入
6. 重複 step 3-5，共 16 次
7. 最後再送進 FP 置換 (FP = inverse of IP)

#### F 函數 (Feistel function)

1. **Expension**: 將原本 32 位元的半塊擴展成 48 位元（即圖中的 E）
2. **XOR with Subkey**: 將擴展完的 48 bit 和 Subkey(48 bit) 做 XOR
- Subkey 是從原本的金鑰(56 bit) 經由切半以及 shift 而來的，總共有 16 個 Subkey，因為要做 16 輪

3. **S Box**: 將 48 bit 切成 8 塊，每塊有 6 bit，送進 S box 進行 Substitution，而 S Box 也同樣有 8 個
- 
- S Box 其實就是 lookup table
- 要注意是針對頭兩位以及**中間兩位**進行置換的判斷
- Ex: 011011 -> S Box -> 1001
- S Box 是 DES 加密中最重要的流程，因為該轉換是**非線性的**
- 在 DES 中，S Box 是一個固定的表，而不是動態隨機生成的

4. **P 置換**: 將上一步的輸出 32 bit (8*4 = 32) 進行置換，這個步驟的目的是為了將下一輪進行 S Box 時，能夠使用不同的 S Box 進行處理

### 爭議
1. IBM 在評估階段時，key 的長度從 128 bits 被縮短成 56 bits，太短
2. IBM 對 S Box 做了一些改動，而且對 S Box 的設計基本理念並無解釋
3. 有些人甚至懷疑 DES 的設計暗藏了一些後門

### 小平反
後來有人研發出差分密碼攻擊法，該攻擊是一種對 Block Cipher 的通用方法，但是 DES 的 S Box 設計使得其對這種類型的攻擊有很強的抵抗力，遠大於使用隨機的 S Box 演算法，有人推測這其實 imply 了 IBM 老早就知道這個攻擊，只是沒有公佈出來，並將預防的方法放入 DES 裡了。

## DES 被取代的原因
1. 56 bits 的 key 太短了，現今的電腦可以較為輕易地破解
2. DES 主要都在硬體上實作，需要有軟體面上的實作，來保障軟體的安全
- 因爲 DES 每次運算都是只有 4 或 6 個 bits，而且又一堆 shuffle 及 shift，這些在當時的電腦上用軟體來實現是很慢的一件事，但在硬體上實現就快多了。
- 後來有人提出了 TDES，DES 做三次，每次都用不同的 key 來 encrypt，但相對的要花的時間也是三倍，而且其仍然在硬體面而已，軟體依然很慢，且安全性僅為 DES 的兩倍（2^112^），而非三倍 。[[1]](https://cs.jhu.edu/~sdoshi/crypto/papers/p465-merkle.pdf)

3. 需要一個公開透明的流程徵選
- 因為當初 DES 的設計是由某一個公司設計的，過程不公開，儘管發表了算法，某些東西的設計理念並沒有說明清楚（例：S Box），容易讓人懷疑有特意為其留下後門。
- 所以為了避嫌，有必要透過公開的方式徵選一個強力有效的演算法。

# AES 的徵選

## 徵選條件
NIST 公佈了以下 AES 的徵選必須要有的條件

1. 公開的
2. 有 128, 192, 256 bits 的 key size 可以選
3. 128 bit block size
4. 免費、免版稅

其中比較重要的是 block size 的限制(128 bit，DES 是 64 bit)，block size 越長，就越減少了 hash collision 的機會，
2^n/2^ 是一個著名的 hash collision 的界線（請參考：[collision](https://en.wikipedia.org/wiki/Collision_resistance) ），攻擊者只要嘗試到這個次數，就可以找個兩個明文， hash 後完全相同，進而發動 collision 類的攻擊
所以提升 block size bit 數有助於安全性的提升

## 徵選結果
- 總共有五組入選最後階段，分別是
1. MARS
2. RC6
3. Rijndael
4. Serpent
5. Twofish

- NIST 選擇的冠軍需具有以下的特點：
1. General security(themostimportantconsideration)
2. Performance
3. Algorithm characteristics, including intellectual property

以下是這幾點的說明：

### Security

一個對稱式加密的演算法都有一個基本的目標，那就是針對此演算法，最有效的攻擊是 key exhaustion (暴力攻擊 key)。也就是說他要在其他地方上沒有什麼弱點，最好的方法就是一個一個去試。

這樣的話 key 的長度就很重要了。在現今的電腦上，56 bit key size 的 DES 已經不安全了，容易被猜出來，所以 NIST 才會要求說 key 的長度至少都會有 128 bit。

若以 Moore's Law 去推估未來電腦的效能，128 bit 的 AES 至少能撐到 2066 年，前提是不把量子電腦考慮進去。

但以上這些都有個前題假設，我們怎麼知道對一個加密演算法而言，brutal attack 就是最有效的 attack，沒有其他更有效的 attack?

#### 我們無法確保且證明 key exhaustion 就是最有效的攻擊方式
我們無法去證明這件事，而且我們也不清楚未來的攻擊手法，只能儘量去防止 shortcut attack 成功運用在演算法上。
- shortcut attack: For n bits key size of symmetirc algorithm, the method which use less then 2^n-1^ operations to find the key.

- 在密碼學上，若有一個攻擊法比窮舉法更有效率，那這個演算法就算是 break 了，雖然實際上可能不實際（電腦的運算速度還沒跟上）。

#### 在選拔階段，NIST 其實無法區分出哪個 Algorithm security 較好
因為這些參選的演算法在當時，都可以預防已知的攻擊，但未來的攻擊就不確定了，
且對於那些參選得演算法，NIST 其實並不會管他是設計的**簡單**或**複雜**。

因為對設計相對簡單的演算法來說，好處是易於分析，我們能夠知道他有多強大；但壞處就是在未來他可能就是第一個被破解的，因為結構相對簡單。

而對設計相對複雜的演算法，好處是不易完整破解，因為結構複雜，當你破解了 a，可能還有 b, c, ... 等著你；壞處就是結構越複雜，就表示某些地方出錯的機率就越高，但我們分析不出來，因為太複雜，太難分析了。

### Performance
需要在軟體上也有不錯的 performance，不僅僅是在 hardware 好而已。而且 NIST 也有測試在各個平台上的 performance。大部分的演算法運行在 32 bit Pentium 上效率都還可以，但其他的平台就不一定了。

### Intellectual property
被 NIST 選出來的 AES algorithm，他要是免費的、向大眾公開的。
而且還有一個問題，NIST 要只選一個演算法放進 AES 嗎？還是要選擇多個演算法呢？

最後 NIST 決定只選了一個演算法放進 AES 裡，因為：
1. 多個演算法之間的交換協作會很混亂
2. 硬體供應商怕成本增加，因為要 apply 多個 algorithm 在他們的商品上
3. 多個演算法，專利問題就越有可能發生

### 最後贏家
最後 NIST 選擇了 Rijndael，因為其不論在 software or hardware 都有不錯的 performance
詳細的徵選流程及更細節的資訊可以參考 [這個](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4863838/)

# The AES
- 一種加密標準
- 使用 Rijndeal 發表的演算法，見前文
- 屬於對稱式加密
- 屬於區段加密 (Block cipher)

## 區段加密法的工作模式

NIST 在發表 DES 後，發表了 FIPS 81, DES Modes of Operation，define 了四種 DES 的加密模式。
這四種 mode 被廣泛使用，儘管在 FIPS 81 的文件裡這些模式是被定義 64 bit block 和 56 bit key 的 DES，但其實這些 size 都是可以擴展的。

*[ECB]: the electronic codebook
*[CBC]: the cipher block chaining
*[CFB]: the cipher feedback
*[OFB]: the output feedback

1. The electronic codebook (ECB), block cipher
2. The cipher block chaining (CBC), block cipher
3. The output feedback (OFB), stream cipher
4. The cipher feedback (CFB), stream cipher

### 區段加密法 Block Cipher
- ECB, CBC 都屬於 Block Cipher
- 所謂的區段加密法，就是在運作時會直接把整個 block 拿去做加解密。
- 如果明文長度不是 block 的整數倍，則需要 padding

### ECB mode

- 最簡單的版本
- 很直覺，資料分段，分別送入加密，在分段解密，每個區塊的運算都是獨立的。
- 缺點：相同的明文，加密後的密文會一模一樣。而且不能很好的隱藏資料，見下圖：
[image source](https://zh.wikipedia.org/wiki/分组密码工作模式#电子密码本（ECB）)

### CBC mode


- IBM invented
- 加密時，每一段明文，都會和前一個階段的密文進行 XOR，而初始階段則是與 IV 值（初始向量）進行 XOR，解密時亦同，也是和前一階段的密文進行 XOR。
- 缺點：
1. 加密是 serial，無法平行化處理；但解密可以平行化，解密第 n 段密文只需要第 n-1 block and n block
2. 加密時，只要中間有一個 bit 壞掉（沒收到，或者收到錯誤的），就整組爛掉；但解密不會，只會影響該 block 及其下一個 block，不會影響到其他的。

### 串流加密法 Stream Cipher

在 FIPS 81 中，也定義了兩種 stream cipher mode（及後面會講的 CFB, OFB），串流加密是生成一種偽隨機加密資料流（pseudo-random stream)，叫做 keystream ，通常由 key, IV, 或者甚至是明文本身來決定。

透過與 keystream 進行 XOR，來做到加解密的動作。
另外，串流加密不像是區塊加密，需要加上 padding

而 IV 值的主要目的是要讓相同的明文，即使透過同樣的加密演算法，也能產生不同的密文（即希望能避免掉 ECB 的缺點）。

IV 值通常不需要保密，但需要是 **nonce**，即在同一個加密 session 下，或是在更換 key 之前，IV 值不可重複，使用過的 IV 值不能再被使用。

IEEE 802.11 WEP 就是一個很好的例子，他的一個著名的缺點就是 IV key 長度只有 24 bits，無法保證在繁忙的網路下不會用到同樣的 IV 值。

### OFB mode


- 初始狀態，IV 值 encrypt，生成 keystream，和 plaintext XOR，生成密文。
- 之後將 keystream 當作下一個階段的 input，encrypt，再 XOR
- 由於 XOR 的特性，所以加解密的過程都一樣，都要先生成 keystream 再拿去做 XOR，來加解密。
- 密文在傳輸時，如果 bit 出錯（EX: 0 --> 1），只會影響該相對應的明文 block，實際上也可以透過錯誤糾正碼來防止，但是如果是 bit 直接 lost 或是被 insert 的話，還是會整組壞掉。
- keystream 的生成是不能平行化的，他是 serial 的；但是加解密可以。我們可以預先將所有的 keystream 算出來，在平行化處理加解密。

### CFB mode


- 基本上和 OFB 一樣，但他的下一輪的輸入不是 keystream，而是密文（keystream 和 plaintext XOR 後的結果）。
- 若每次 feedback 的密文只有 1 bit，再加上一個移位的暫存器，則可以達到 self-synchronizing (自同步，可以處理任意位情況錯誤的串流加密法)。請參考：[這裡](https://zh.wikipedia.org/wiki/分组密码工作模式)
- CFB 其實和 CBC 很像，CFB 的解密過程幾乎就是顛倒的 CBC 的加密過程
- 所以也擁有 CBC 的一些特性，密文如果壞掉一小部分，就只有那個 block 受影響，其他仍然正常。

## 新的 mode

上述的都是在 DES 時期提出的 mode，大部分都有一個明顯的缺點，就是用了一堆 feedback，在這些算法上實現平行化是很困難的一件事，而唯一沒用 feedback 的 ECB 又有前述的一些問題。

所以 NIST 決定推出一個新的 mode - CTR (counter mode)

*[CTR]: conunter mode

### CTR mode


- 類似 CFB, OFB mode, 但沒有 feedback
- CTR1, CTR2, ... 是一個計數器，和 IV 值的屬性相同，不能重複，有些實作上是將 nounce 值和計數器 append (Ex: F45212 + 000001 = F45212000001)
- 由於沒有 feedback 了，可以在上面進行平行化處理，增進 performance 了。
- 和 OFB 的屬性類似，密文的傳遞錯誤只影響一個 block

## Reference
1. [Selecting the Advanced Encryption Standard](https://ieeexplore.ieee.org/document/1193210)