Upgrade to Pro — share decks privately, control downloads, hide ads and more …

[Crypto in CTF] Bleichenbacher RSA Signature Fo...

oalieno
October 31, 2020

[Crypto in CTF] Bleichenbacher RSA Signature Forgery

oalieno

October 31, 2020
Tweet

More Decks by oalieno

Other Decks in Technology

Transcript

  1. PKCS • PKCS ( Public Key Cryptography Standards ) 是公鑰密碼標準

    • 制定了了⼀一系列列從 PKCS#1 到 PKCS#15 的標準 • 其中 PKCS#1 是 RSA Cryptography Standard
  2. • ASN.1 是編碼數據的格式,這裡紀錄了了使⽤用的 hash 演算法 H(M) ASN.1 01 FF …

    00 FF D = 00 padding Step 2 : Data Encoding Sign PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
  3. Step 3 : RSA encryption D d % n =

    S Sign PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
  4. Step 1 : RSA decryption Verify S e % n

    = D PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
  5. Step 2 : Data Decoding Verify • 需要 parse 這個格式取出

    H(M) • 這個標準沒有說要怎麼 parse • 如果 e 太⼩小且沒有正確的 parse,就有機會偽造簽章 H(M) ASN.1 01 FF … 00 FF D = 00 PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
  6. Step 3 : Message digesting and comparison M' H(M)' H(M)

    Verify compare PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
  7. Bleichenbacher RSA Signature Forgery ( 2006 ) https://mailarchive.ietf.org/arch/msg/openpgp/5rnE9ZRN1AokBVj3VqblGlP63QE • 實作缺陷

    : 可以有多餘的字元在後⾯面 • parse 的時候直接取出後⾯面固定長度的 H(M) • 沒有檢查後⾯面還有沒有東⻄西 H(M) ASN.1 01 FF … 00 FF 00 Garbage
  8. • 在 e = 3 的情況下可以 forge signature • 嘗試構造

    ED 讓 ED 的三次⽅方不超過 n 且滿⾜足以下格式 S 3 % n = H(M) ASN.1 01 FF … 00 FF 00 Garbage Bleichenbacher RSA Signature Forgery ( 2006 ) https://mailarchive.ietf.org/arch/msg/openpgp/5rnE9ZRN1AokBVj3VqblGlP63QE
  9. H(M) ASN.1 01 FF … 00 FF Garbage 00 D

    ( length d ) G ( length g ) 2t−15 G + total length t (x + y)3 x3 3x2y + 2g ⋅ D + −2d+g 3xy2 y3 + + = Bleichenbacher RSA Signature Forgery ( 2006 ) https://mailarchive.ietf.org/arch/msg/openpgp/5rnE9ZRN1AokBVj3VqblGlP63QE
  10. x = 2t − 15 3 y = (D −

    2d) ⋅ 2g 3 ⋅ 22(t − 15) 3 Bleichenbacher RSA Signature Forgery ( 2006 ) https://mailarchive.ietf.org/arch/msg/openpgp/5rnE9ZRN1AokBVj3VqblGlP63QE
  11. x = 21019 y = (D − 2288) ⋅ 234

    3 • 假設 • Key 長度為 3072 bit • Garbage 長度為 2072 bit • 使⽤用 SHA-1 的話,D 的長度是 288 bit • 最後 ED = x + y 就是我們構造出的合法簽章 Bleichenbacher RSA Signature Forgery ( 2006 ) https://mailarchive.ietf.org/arch/msg/openpgp/5rnE9ZRN1AokBVj3VqblGlP63QE
  12. RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/ •

    實作缺陷 : padding bytes 可以是任意字元 直接取第⼆二個 0x00 沒有檢查中間的 padding bytes
  13. • 在 e = 3 的情況下可以 forge signature • 嘗試構造

    ED 讓 ED 的三次⽅方不超過 n 且滿⾜足以下格式 • ED3 的後綴是 ASN.1 + H(M) • ED3 的前綴是 \x00\x01 H(M) ASN.1 01 ?? … 00 ?? 00 S 3 % n = RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  14. 0 S S3 ⽬目標 0 0 1 0 0 0

    1 1 1 0 1 match RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  15. 0 S S3 ⽬目標 0 0 1 0 0 0

    1 1 1 0 1 match RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  16. 0 S S3 ⽬目標 0 0 1 0 0 0

    1 1 1 0 1 mismatch RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  17. 0 S S3 ⽬目標 1 0 1 1 1 0

    1 1 1 0 1 match RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  18. 0 S S3 ⽬目標 1 0 1 1 1 0

    1 1 1 0 1 match RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  19. 0 S S3 ⽬目標 1 0 1 1 1 0

    1 1 1 0 1 01013 = 1111101 RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  20. 01 … … 00 3 = 92 3f … 68

    04 bc 28 76 e4 50 … = 3 • 要讓 ED3 的前綴是 \x00\x01 只要把 \x00\x01... 開三次⽅方 • 最後再把開完三次⽅方的值的後綴換成前⾯面算出來來的後綴 • 就可以成功⾃自⼰己構造合法簽章了了 RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  21. H(M) ASN.1 01 ?? … 00 ?? 00 92 3f

    … bc 28 3 = RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/
  22. A Decade After Bleichenbacher '06, RSA Signature Forgery Still Works

    ( 2019 ) https://i.blackhat.com/USA-19/Wednesday/us-19-Chau-A-Decade-After-Bleichenbacher-06-RSA-Signature-Forgery-Still-Works.pdf • 整個格式固定是 n 這麼長 • ⽤用 Symbolic Execution 去找到可以任意亂塞的部分有多長
  23. A Decade After Bleichenbacher '06, RSA Signature Forgery Still Works

    ( 2019 ) https://i.blackhat.com/USA-19/Wednesday/us-19-Chau-A-Decade-After-Bleichenbacher-06-RSA-Signature-Forgery-Still-Works.pdf • 實作缺陷 : padding bytes 可以是任意字元 H(M) ASN.1 01 ?? … 00 ?? 00 CVE-2018-15836 Openswan 2.6.50
  24. CVE-2018-16152 strongSwan 5.6.3 A Decade After Bleichenbacher '06, RSA Signature

    Forgery Still Works ( 2019 ) https://i.blackhat.com/USA-19/Wednesday/us-19-Chau-A-Decade-After-Bleichenbacher-06-RSA-Signature-Forgery-Still-Works.pdf • 實作缺陷 : • Algorithm Parameter 可以是任意字元 • Algorithm OID 後⾯面可以有多餘的字元 H(M) 01 FF … 00 FF 00 ASN.1 00 03 20 03 0c Algorithm Parameter 04 10 Algorithm OID
  25. CVE-2018-16150 axTLS 2.1.3 A Decade After Bleichenbacher '06, RSA Signature

    Forgery Still Works ( 2019 ) https://i.blackhat.com/USA-19/Wednesday/us-19-Chau-A-Decade-After-Bleichenbacher-06-RSA-Signature-Forgery-Still-Works.pdf • 實作缺陷 : • 可以有多餘的字元在後⾯面 • Algorithm Identifier 可以是任意字元 H(M) 01 FF … 00 FF 00 ASN.1 00 03 20 03 0c Algorithm Identifier 04 10 Garbage
  26. How to defense? • ⽤用其他的簽章演算法,比如說 ECDSA • ⽤用更更⼤大的 e,比如 65537

    • parsing based → comparison based H(M) ASN.1 01 FF … 00 FF 00 H(M) ASN.1 01 FF … 00 FF 00 compare