owned this note
owned this note
Published
Linked with GitHub
# IT Security 1 (Ch4~Ch6)
## Ch4 Asymmetric Cryptography
### RSA
- Asymmetric加密機制
- 變數長度通常小於key
- 但加密結果與key長度相同
- 較少用在長訊息的加密
- 運用:
- 加密對稱key
- 加密authentication challenges
- digital signature
- **public key:**
- 選擇兩個質數 <font color=red>$p,q$</font>
- 計算 <font color=green>$n$</font>$=$<font color=red>$pq$</font>
- 在 $\phi($<font color=green>$n$</font>$)$ 中選擇 <font color=green>$e$</font>
- public key: <font color=green>$(n,e)$</font>
- **private key:**
- 計算 <font color=red>$d$</font>,其中 <font color=green>$e$</font><font color=red>$d$</font>$=1\ mod$<font color=red>$\ \phi(n)$</font>
- private key: <font color=red>$d$</font>
### Euler's Theorem
- $\text{for any }a\in\mathbb{Z}_n^*$
<font color=red>$a^{\phi(n)}=1\ \text{mod}\ n$</font>
- idea: 循環群,$\phi(n)$是元素個數
- 一般化:
$\text{for any }a\in$<font color=red>$\mathbb{Z}_n$</font>$\text{ in case }n=pq$
<font color=red>$a^{\phi(n)+1}=a\ \text{mod}\ n$</font>
<font color=red>$a$ 不必與 $n$ 互值</font>
### RSA的安全性
- <font color=#4285f4>**分解 $n=pq\ \Leftrightarrow$ 計算 $\phi(n) \Leftrightarrow$ 計算 $d$**</font>
- 目前還不知道有沒有方法:如果不知道 $d$ 仍能破解RSA加解密
- 建議用2048 bit,即p,q為1024 bit
### PKCS(Public Key Cryptography Standard)
- 定義兩個RSA的encoding方法:
- RSAES-PKCS1-v1_5
- RSAES-OAEP
> OAEP = Optimal Asymmetric Encryption Padding
> RSAES = RSA Encryption Scheme
>
- 兩者定義如何**pad**訊息為更長的訊息
- <font color=#ff9614>**為什麼需要PKCS?**</font>
- 確認明文是合法的、可辨識的
- 避免被竄改密文
- <font color=#ff9614>**為什麼需要OAEP?**</font>
- 使得密文具有隨機性(有random seed)
### RSA後門
- 製造RSA的key
- **Naïve RSA backdoor**
- <font color=red>固定prime $p$</font>,選擇隨機 $q$,計算出公開 $n$
- <font color=#ff9614>此backdoor可以用 $p$ 找到 $d$,為什麼?</font>
- 計算 $q=p^{-1}n$
- 計算 $d$, $e$ 在 $\phi(n)$ 中的inverse
- <font color=#ff9614>被external攻擊</font>:
- <font color=red>取得兩個public key $(n,e),(n',e')$即可攻擊</font>
- 因為 $p$ 固定,則 $gcd(n,n')=p$
- 則可用上列的方式取得 $d,d'$
- **Better RSA backdoor**
- 製造商擁有key pair
public key: $(E,N)$
private key: $D$
- <font color=red>隨機選取 $p,q$</font>
- 計算 $e=p^E\text{ mod }N$
檢查是否可逆,某則重新選取 $p$
- <font color=#ff9614>被external攻擊</font>:
- 若知道 $(e,n)$
- 則計算 <font color=red>$e^D\text{ mod }N=p$</font>,用此計算 $d$
> 因為 $e=p^E\text{ mod }N$
> $e^D=p^{ED}\text{ mod }N=p^{\phi(N)+1}\text{ mod }N=p\text{ mod }N$
> <font color=red>需要製造商的private key才有辦法攻擊</font>
>
- **Naïve RSA signature**
- 跟Naïve RSA生成key方式相同
- 易受 <font color=#4285f4>existential forgery</font> 攻擊
- 攻擊者隨機選擇 <font color=red>$s$</font>$\in\mathbb{Z}_n$,宣稱是Alice對 <font color=blue>$m$</font> 生成的signature:<font color=blue>$m$</font>$:=$<font color=red>$s$</font>$^e\text{ mod }n$
- 因為 <font color=blue>$m$</font>$^d=$<font color=red>$s$</font>$^{ed}\text{ mod }n=$<font color=red>$s$</font>$\text{ mod }n$
- 很容易生成pair $(m,s)$ 使得 $s$ 是 $m$ 的合法簽章
- 但是很難對有意義的 $m$ 生成 $s$
> [existential forgery](https://en.wikipedia.org/wiki/Digital_signature_forgery) 是針對digital signature或MAC攻擊的詞
>
- RSA是 <font color=#4285f4>multiplicative homomorphic(乘法同態)</font>
> 加密後再相乘等於相乘後再加密
- $s:=s_1s_2=m_1^dm_2^d=(m_1m_2)^d\text{ mod }n$
- $s$ 仍是 $m_1m_2$ 的合法簽章
- **安全的RSA signature**
- <font color=red>簽章前先用已知的hash function</font>
- $s=h(m)^d\text{ mod }n$
- 解決
- <font color=#4285f4>existential forgery</font>
因為**pre-image resistant**,難找到 $s^e=h(m)$
- <font color=#4285f4>multiplicative homomorphic</font>
因為**pre-image resistant**,難找到$h(m)=h(m_1)h(m_2)$
- 對DSS, ECDSA簽章機制仍適用
- 簽章的訊息若過長,hash之後能縮短
- PKCS
- RSA的兩個encoding scheme
- RSASSA-PSS
- RSASSA-PKCS1-v1_5
- 用digital signature的好處:
- MAC無法為 <font color=red>public</font> 提供authenticity
- <font color=red>Non-repudiation</font> 簽章人無法否認自己傳送過這個訊息
- RSA攻擊的結果:
- Total break: 取得私鑰
- Universal forgery: 偽造所有訊息簽章
- Selective forgery: 偽造選擇的訊息簽章
- Existential forgery: 偽造沒有意義的訊息的簽章
### DSS (Digital Signature Standard)
- 用DSA(Digital Sianature Algorithm)
- 建立在離散對數問題(discrete logarithm problem)的困難度
- 給定 $Y,p,g: Y=g^x\text{ mod }p$,難以找到 $x$
- <font color=#ff9614>Key generation</font>
- <font color=01b9ff>$p$</font>: 1024 bit
<font color=ff0199>$q$</font>: 160 bit
<font color=ff0199>$q$</font>$|($<font color=01b9ff>$p$</font>$-1)$
- 隨機選擇 <font color=ff7601>$x$</font>$\in\mathbb{Z}_p^*$ 使得<font color=ff7601>$x$</font>$^{\frac{p-1}{q}}\text{ mod }p\neq 1$
設 <font color=0bad01>$g$</font>$:=$<font color=ff7601>$x$</font>$^{\frac{p-1}{q}}\text{ mod }p$
- 隨機選擇 <font color=8601ff>$a$</font> $\in\{1...,$ <font color=ff0199>$q$</font> $-1\}$
計算 <font color=0109ff>$A$</font>$=$<font color=0bad01>$g$</font><font color=8601ff>$^a$</font>$\text{ mod }$<font color=01b9ff>$p$</font>
- public key:
$($<font color=01b9ff>$p$</font>$,$ <font color=ff0199>$q$</font>$,$ <font color=0bad01>$g$</font>$,$ <font color=0109ff>$A$</font>$)$
- private key:
<font color=8601ff>$a$</font>
> 支援的bitlength:
1024/160
2048/224
2048/256
3072/256
- <font color=#ff9614>Signature generation</font>
- 隨機選擇 <font color=3a7b82>$k$</font> $\in\{1...,$ <font color=ff0199>$q$</font> $-1\}$
計算
<font color=3a824d>$r$</font> $=($<font color=0bad01>$g$</font><font color=3a7b82>$^k$</font>$\text{ mod }$<font color=01b9ff>$p$</font>$)\text{ mod }$<font color=ff0199>$q$</font>
<font color=3a4a82>$s$</font> $=($<font color=3a7b82>$k$</font>$^{-1}(h(m)+$<font color=8601ff>$a$</font><font color=3a824d>$r$</font>$))\text{ where }$<font color=3a7b82>$k^{-1}$</font>$\text{ is the inverse of }$<font color=3a7b82>$k$</font>$\text{ mod }$<font color=ff0199>$q$</font>
- signature on $m$ is the pair $($<font color=3a824d>$r$</font>$,$ <font color=3a4a82>$s$</font>$)$
> 指數160 bit較有效率
> <font color=3a7b82>$k$</font> 對每個訊息需不同
- <font color=#ff9614>**為何需要不同的 $k$**</font>
- $s_1=(k^{-1}(h(m_1)+ar))\text{ mod }q$
$s_2=(k^{-1}(h(m_2)+ar))\text{ mod }q$
- <font color=red>$s_1-s_2$</font>$=k^{-1}(h(m_1)-h(m_2))\text{ mod }q$
可得 $k$
- 則private key <font color=8601ff>$a$</font> 可被算出來
- <font color=#ff9614>Signature verification</font>
- 當收到 $m,s,r$
- 檢查 $s, r\in{1,...,q-1}$
- 計算
$u_1=h(m)s^{-1}\text{ mod }q$
$u_2=rs^{-1}\text{ mod }$
- 計算 $v=(g^{u_1}A^{u_2}\text{ mod }p)\text{ mod }q$
- 若 $r=v$ 則接受此signature
### Diffie-Hellman Key Exchange
- 用在雙方需使用同一把<font color=red>對稱</font>私鑰時
- 建立在離散對數問題的困難度
- 方法:
- 雙方得到質數 $p$ 及generator $g\in\mathbb{Z}_p^*$
- Alice計算 $h_A=g^a\text{ mod }p$,Bob計算 $h_B=g^b\text{ mod }p$
- Alice傳 $h_A$ 給Bob,Bob傳 $h_B$ 給Alice
- Alice計算 $h_B^a$,Bob計算 $h_A^b$
- <font color=#ff9614>**Man-in-the-Middle Attack**</font>
- 攻擊者在中間替換 $h_A,h_B$
## Ch5. Certificates and Public Key Infrastructures
- **Trusted Third Parties**
- 假設Alice和Bob有trusted thrid party的public key
- trusted third party對發行的key做簽章(包含可以擁有key的人的名字)
- Bob可以驗證是不是由trusted third party發行的key
- 稱為<font color=red>**Certification Authority**</font>
- certificate至少包含:
- public key
- owner的名字
- 發行者的名字
- 對剩下的內容的hash的簽章
### Public Key Infrastructures
- CA發行certificate
- 檢索certificate的資料庫(repository)
- 撤銷certificate的方法
- 衡量certificate的"<font color=red>chain</font>"的方法
- <font color=red>RA</font>(registration authority)與CA並用
- 同意certificate的請求
### Certificate Revocation List (CRL)
- 被CA簽署過的list,其中的certificate都未到期(expired)
### Online Certificate Status Protocol(OCSP)
- OCSP允許certificate未過期的query
- OCSP回傳list中的certificate的狀態
- <font color=#ff9614>**CRL和OCSP的比較**</font>
- **CRL**
- :negative_squared_cross_mark: CRL會過長,難以搜尋
- :negative_squared_cross_mark: 撤銷具有週期性
- :white_check_mark: query哪個certificate不會被CA知道
- **OCSP**
- :white_check_mark: 可隨時撤銷
- :negative_squared_cross_mark: CA會知道哪個certificate被查詢
- :negative_squared_cross_mark: 若query太多會是CA的流量負擔
- <font color=red>雞蛋問題:</font>如果網路連線前要網站的secure access(要去OCSP retrieval)
- 可以用<font color=red>OCSP stapling</font>解決:用最近的OCSP的結果,也解決流量問題
### Using Certificates to Protect Diffie-Hellman
1. First try
- 流程:
1. Alice送 <font color=4285f4>$h_A,sig_A,cert_A$</font>
2. Bob用$pub_A$驗算$sig_A$,用$pub_{CA}$驗算$cert_A$
- <font color=#ff9614>**Problem:**</font>
- Signature沒有跟此protocal結合
- 攻擊者可以記錄Alice的訊息並且再重傳給Bob(replay)
2. Second try
- 流程:
1. Alice送 <font color=4285f4>$h_A$</font>
2. Bob用 $h_A$跟 <font color=4285f4>$h_B$</font>做簽章 $sig_B:=gensig(priv_B,h_B||$<font color=4285f4>$h_A$</font>$)$
3. Bob傳送 <font color=4285f4>$h_B,sig_B,cert_B$</font>
4. <font color=red>Alice驗證 $sig_B$ 是否包含 $h_A$</font>,則可以知道Bob收到的 $h_A$ 有沒有被竄改過
5. Alice也用上列的方法簽章 $sig_A:=gensig(priv_A,h_A||$<font color=4285f4>$h_B$</font>$)$
6. Alice傳送 <font color=4285f4>$sig_A,cert_A$</font>
7. Bob驗證
- <font color=#ff9614>**Problem:**</font>
- 攻擊者仍竄改Bob的public key,傳送自己的signature
3. **Secure Authentic Diffie-Hellman**
- 流程:
1. Alice傳送 $h_A$
2. Bob傳送 $h_B$
3. <font color=red>Alice用$h_B^a$作為對稱式key $k$</font>
用 $k$ <font color=red>加密</font> <font color=4285f4>$c_A:=enc(k,sig_A||cert_A)$</font> ($sig_A$如上定義)
4. Alice傳送 <font color=4285f4>$c_A$</font>
5. Bob也計算<font color=red>對稱式key $k=h_A^b$</font>
用 $k$ <font color=red>解密</font> <font color=4285f4>$sig_A||cert_A:=dec(k,c_A)$</font>
6. Bob也傳算 <font color=4285f4>$c_B$</font>
## Ch6. Authentication and Key Agreement
- <font color=#ff9614>**Authentication protocol的目標**</font>
- **正確性(Correctness):** A可以向B成功認證他的身份
- **不可轉移性(Resistance against transferability):** B不能重複使用A的身份向C證明自己
- **不可偽造(Resistance against impersonation):** C執行protocol後向B證明自己是A的機率很小
- **Password-Based Authentication**
- 用hash儲存使用者的password
使用者輸入password後找hash值
hash需要有pre-image resistant
- <font color=4285f4>Dictionary Attack</font>
- **Offline attack**
- 先預計算字典裡所有的字的hash
- 若拿到password file則比對所有的hash得到preimage
- **Online attack**
- 無法取得password file
- 攻擊者要一個一個測字典裡的字
> 攻擊有可能都存在,針對個人或所有用戶
- **<font color=#ff9614>Dictionary Attack的解法</font>**
- 使用<font color=red>salt</font>( $h(\text{salt,pwd})$ ),並在password file中儲存salt
- 使用相同密碼的使用者會有不同的hash值
- offline attack需要更多空間或無法precompute
- Default password attack
- **<font color=#ff9614>Mirai(日文「未來」) Botnet</font>**
- 對使用預設帳號密碼的物聯網裝置植入病毒,植入之後繼續搜尋其他IP位址
- **Challenge-response authentication**
- 流程:
1. Bob向Alice傳送一 <font color=4285f4>Challenge value</font> (a random value)
2. Alice回傳 $\text{Response=}f($ <font color=red>$\text{key}$</font>$\text{, challenge)}$
- Alice向Bob證明自己有secret key,而不用直接傳送secret key
- Example: **<font color=#ff9614> Lamport’s One-Time Passwords</font>**
- $h$ 是hash function
- Alice選擇一個隨機seed $S$,並計算
$h(S)=S_1,\\h(S_1)=h^2(S)=S_2,...,\\h(S_{n-1})=h^n(S)=S_n$
- Alice提供 <font color=red>$P_0=S_n$</font> 給Bob
> 則接下來的使用順序是 $P_1=S_{n-1},P_2=S_{n-2}$
- 若Bob傳送 <font color=4285f4>Challenge $k$</font>
則Alice回傳 <font color=red>$P_k$</font>
- Bob驗證是否 $h(P_k)=P_{k-1}$
- **<font color=#ff9614> Small $k$ attack:</font>**
- <font color=red>因為Bob傳送的 $k$ 沒有被授權(authenticated)</font>
- 攻擊者偽造一個 <font color=4285f4>$m$</font>$, m>k$,傳給Alice
- Alice回傳 <font color=4285f4>$P_m$</font>
攻擊者再回傳 <font color=red>$P_k$</font>
- 因為 <font color=red>$h^{m-k}(P_m)=P_k$</font>
- **<font color=#ff9614> Building Blocks for Unilateral(單方面) Authentication</font>**
1. $E_k(\text{timestamp,ID}_A)$
2. $E_k(\text{RAND})$ ($\text{RAND}$是Alice給的)
3. $MAC_k(\text{timestamp,ID}_A),\text{timestamp}$
4. $MAC_k(\text{RAND})$ ($\text{RAND}$是Alice給的)
- Bob的資訊包含在訊息中(key)
- Bob指定收件人(用Alice的對稱式或非對稱式key)
- **<font color=#ff9614> Building Blocks for Mutual(雙方) Authentication</font>**
- <font color=4285f4>$R_B$</font> 是另一個random number
1. Alice傳送$R_A$給Bob
Bob傳回 $E_K(R_A,R_B)$給Alice
Alice傳回 $E_K(R_B,R_A)$給Bob
2. Alice傳送$R_A$給Bob
Bob傳回 $MAC_K(R_A,R_B),$ <font color=4285f4>$R_B$</font>給Alice
Alice傳回 $MAC_K(R_B,R_A)$給Bob
- 將 $R_A,R_B$ 一起加密/計算$MAC$ 以避免<font color=red>chosen plain text</font>攻擊
- **<font color=#ff9614>Using Public Key Encryption</font>**
- 單方面authenticate
- Alice傳送 <font color=4285f4>$h(R)$</font>$,ID_B,E_B(h(R),ID_B)$
<font color=red>假設Bob知道<font color=4285f4>$h(R)$</font>且不會破解此$h(R)$</font>
- Bob回傳 $R$
- 互相authenticate
- (假設雙方還不知道彼此public key)
- Bob傳送 $R_B$ 給Alice
- Alice回傳 $Cert_A,R_A,B,Sign_A(R_A,R_B,B)$
- Bob回傳 $Cert_B,A,Sign_B(R_B,R_A,A)$
> $B,A$是Alice跟Bob的public key(!?)
### Key Establishment
- 如果沒有<font color=red>session key</font>,則上述的building block都無效
- 可以保障兩個授權的雙方仍在communicating
- **<font color=#ff9614>Key Establishment Protocols</font>**
- 先建立一個shared secret key
- 可分為
- <font color=4285f4>Key transport protocols</font>
- 被建立的key可以被安全的傳送
- <font color=4285f4>Key agreement protocols</font>
- example: **Diffie-Hellman**
- **<font color=#ff9614>Motivation</font>**
- 給定一定key,如果不被攻擊的話密文有限
- 減少暴露時間及資訊量
- 避免長期儲存大量secret key
- 建立使用者的獨立通道
- **Key Establishment該有的特質**
- key freshness
- Key control
- Efficiency
- Third party requirements
- **<font color=#ff9614>perfect forward secrecy</font>**
如果long-term signature keys被破解不會影響到以前的session key
- **<font color=#ff9614>vulnerable to a known-key attack</font>**
若過去的session key被破解,會影響到未來的session key或有辦法假冒他人
- **Key Establishment Protocols的性質**
- <font color=4285f4>Implicit key authentication</font>
一方知道除了被授權的另一方之外可以取得特定secret key
- <font color=4285f4>Key confirmation</font>
一方知道有另一個人(不一定被授權)可以擁有特定secret key
- <font color=4285f4>Explicit key authentication</font>
implicit key authentication+key confirmation
- <font color=4285f4>Authenticated key establishment</font>
一protocol提供implicit key authentication
- **<font color=#ff9614>Key Transport</font>**
- A和B用對稱式加密,加密session key $SK$
- 若需要key freshness,可以用Nonce
- B傳遞Nonce $N_B$ 給A
- A回傳$E_K(SK,N_A,N_B)$
### Key transport
1. **<font color=#ff9614>First attempt</font>**
- server $S$ 有跟 $A,B$ 的key $k_{SA},k_{SB}$
- <font color=4285f4>若 $A$ 想要建立與 $B$ 的溝通通道</font> (即取得$k_{AB}$)
- 步驟:
1. $A$ 對 $S$ 請求 $A,B$ 的key
2. $S$ 給 $A$ <font color=#4285f4>$E_{K_{AS}}(K_{AB})$</font> 及 <font color=#4285f4>$E_{K_{BS}}(K_{AB})$</font>
3. $A$ 再把 $(E_{K_{BS}}(K_{AB}),A)$ 傳給 $B$
4. $B$ 用自己的 $K_{BS}$ 解密得到 $K_{AB}$
- <font color=#ff9614>**Probelm:**</font>
- 攻擊者對調 $(E_{K_{BS}}(K_{AB}),A)$ with $(E_{K_{BS}}(K_{AB}),$<font color=red> $T$ </font>$)$
- $B$ 原本想給 <font color=red> $T$ </font> 訊息但是會給到 $A$
- 攻擊者可以從 $A$ 方獲得訊息而非從 <font color=red> $T$ </font> 方
> 可能從 $A$ 方更能取得訊息
- 假設攻擊者 <font color=red>$E$</font> 和 $S$ 也有key $k_{SE}$
- 則攻擊者可以攔截步驟1,再把 <font color=red>$E_{K_{AS}}(K_{AE})$</font> 及 <font color=red>$E_{K_{ES}}(K_{AE})$</font> 傳給 $A$
- $A$ 變成跟 <font color=red>$E$</font> 溝通
2. **<font color=#ff9614>Second attempt</font>**
- 步驟:
2. $S$ 給 $A$ <font color=#4285f4>$E_{K_{AS}}(K_{AB},B)$</font> 及 <font color=#4285f4>$E_{K_{BS}}(K_{AB},A)$</font> (加入 $A,B$ 的identity)
- <font color=#ff9614>**Probelm:**</font>
- 攻擊者如果獲得以前的session key $k_{AB}'$
- 並且記錄以前的訊息
- 攻擊者可以使 $A,B$ 再用同一把broken session key
- <font color=red>此protocol易受replay攻擊</font>
3. **<font color=#ff9614>Third attempt(Needham-Schroeder Protocol)</font>**
- 用 <font color=red>Nonce</font> 對抗replay攻擊
- 步驟:
1. $A$ 對 $S$ 請求 $A,B$ 的key,並給一個 <font color=red>Nonce $N_A$</font>
2. $S$ 回傳 <font color=red>$E_{k_{AS}}(k_{AB},B,N_A,$</font><font color=4285f4>$E_{k_{BS}}(k_{AB},A)$</font><font color=red>$)$</font>
3. $A$ 將 <font color=4285f4>$E_{k_{BS}}(k_{AB},A)$</font> 傳給 $B$
4. $B$ 傳 <font color=red>$E_{AB}(N_B)$</font> 給 $A$
5. $A$ 回傳 <font color=red>$E_{AB}(N_B-1)$</font>
- <font color=#ff9614>**Probelm:**</font>
- 若攻擊者知道old session key
- 可以破解步驟3,並且用 <font color=red>$k_{AB}'$</font> 與$B$溝通
4. **<font color=#ff9614>Fourth attempt</font>**
- 步驟:
3. $B$ 傳 <font color=red>Nonce $N_B$</font> 給 $A$
4. $A$ 回傳 <font color=4285f4>$E_{k_{BS}}(k_{AB},A,$<font color=red>$N_B$</font>$)$</font>
### Key Agreement
- **Based on public key cryptography**
- <font color=4285f4>Diffie-Hellman Key Agreement</font>
- 可用對稱式鑰匙或公鑰對公開變數授權
- **Based on symmetric keys**
- 對Nonce授權
- 用Nonce或long term shared secret進行Hash產生session key