# Timing Attack 從入門到發現沒時間了 - Allen Chou

{%hackmd @HITCON/r1cl60dRc %}

###### tags: `HITCON2022`,`HITCON`

> 簡報到前五分鐘才做完 QQ
> [name=Allen Chou]

[簡報連結](https://drive.google.com/file/d/1q1ElgmwTq6Ji7br0tacQoRiMzyfoouY8/view?usp=sharing)

## Timing attack

- 比對: 字串長度，字串長度錯了會直接退出，長度是對的會再執行久一點

    SECRET = 'secretkey'
    def check(s):
      if len(s) != len(SECRET):
        return False
      else:
        for a,b in zip(s, SECRET):
          if a != b:
            return False
      return True

> 舉例: 因為字串逐字比對所造成執行時間上的差異，此差異可能洩漏許多資訊
* 是一種 [side-channel attack](https://en.wikipedia.org/wiki/Side-channel_attack)
- 用電腦本身而非演算法來找出漏洞

#### 上述問題
* 不同輸入執行時間不同
* 長度不對時，執行時間一樣
* 長度對但內容不對時，執行時間與前幾個字相同有關

### 字串比對
* 幾乎所有 Database system 都使用 memcmp 比較字串，有timing attack問題，隨便寫個比較就可能有洞

> 真的發生過攻擊，不是我在唬爛
> [name=Allen Chou]

### Padding Oracle

<!-- 我是密碼學菜雞QQ -->

## Noise
> 你以為 timing attack 的時間差異很好判別，實際上都擠在一起

* noise 太大，很難找到有用的資訊
可能問題來自於:
- 網路延遲
- CPU 高負載
- I/O
- etc.
* naive approach
- 直接取平均比較
- 當執行時間變長分佈會變廣，難以比較
- p-value test
- 執行時間不是 normal distribution QQ

這是我的結果（執行 100000 次的時間加總）（長度 時間）

* Mann-Whitney U test
* 可以比較各種 distribution
* 慢: O(n^2)
* KS-test
* Box-test
* 不需要比較整個distribution，只看比較快的結果
* 取一個"box" $P(lb),P(ub)$ (P(x)為xth percentile)，若兩個distribution的box沒有重疊就當作不同的distribution
* lb,ub要自己調 QQ

### 基於 rank-sum 概念的 classifier
1. 每個可能的值都 request 一次，排名時間
2. 重複前一步 N 次，取排名的平均
3. 把你的排名平均拿去排名

## 如何解決 Timing Attack

1. 不同 input 會有不同的執行時間
- 使用 Constant time: 避免 Fast-failing
- [結果還是被 compiler 優化 code (重新加入 fast-failing)](#如何被-compiler-&-cpu-背刺)
2. input 是使用者可控的
- 在運算前先檢查input的integrity
- 結果又創造了另一個Timing Attack機會
3. 可以聽到有效的 timing leakage
- 加上 random noise ?
- 攻擊者多測幾次就好，同時會造成效能地獄
- 可能不小心做出別的side-channel

:::success
最好用別人寫好的程式(Library)
:::

### 如何被 compiler & cpu 背刺
* compiler 非常擅長 optimization，可能在過程中把你拿掉的side-channel放回去
* 高階語言中的一行code可能不是constant time
* e.g. short-circuit evaluation (e.g. python 的 and)
* CPU 的 speculative execution 可能重新製造 side-channel
* e.g. CPU branch prediction, CPU以為每次這個if都會true，但如果突然來一個false，就需要pipeline flush，導致執行時間變長 -> timing attack
* Virtual address 在隔壁的位址可能 physical address 差很遠

## 結論
::: success
> 超級重要的結論：不要自己實作密碼學演算法
>[name=Allen Chou]
:::

* 密碼學很難，交給懂得人去處理就好