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 是針對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
      • Image Not Showing Possible Reasons
        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported
        Learn More →
        CRL會過長,難以搜尋
      • Image Not Showing Possible Reasons
        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported
        Learn More →
        撤銷具有週期性
      • Image Not Showing Possible Reasons
        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported
        Learn More →
        query哪個certificate不會被CA知道
    • OCSP
      • Image Not Showing Possible Reasons
        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported
        Learn More →
        可隨時撤銷
      • Image Not Showing Possible Reasons
        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported
        Learn More →
        CA會知道哪個certificate被查詢
      • Image Not Showing Possible Reasons
        • The image file may be corrupted
        • The server hosting the image is unavailable
        • The image path is incorrect
        • The image format is not supported
        Learn More →
        若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
Select a repo