IT Security 1 (Ch4~Ch6)

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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.