Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
[Crypto in CTF] Bleichenbacher RSA Signature Fo...
Search
oalieno
October 31, 2020
Technology
0
560
[Crypto in CTF] Bleichenbacher RSA Signature Forgery
https://github.com/oalieno/Crypto-Course/tree/master/RSA
oalieno
October 31, 2020
Tweet
Share
More Decks by oalieno
See All by oalieno
[Crypto in CTF] Classical Cipher
oalieno
0
400
[Crypto in CTF] Block Cipher Mode
oalieno
0
940
[Crypto in CTF] HASH
oalieno
0
250
[Crypto in CTF] LFSR
oalieno
0
460
[Crypto in CTF] RSA
oalieno
0
660
[Crypto in CTF] Blockchain Security
oalieno
0
390
滲透測試基本技巧與經驗分享
oalieno
2
1.1k
Other Decks in Technology
See All in Technology
Lakebaseを使ったAIエージェントを実装してみる
kameitomohiro
0
180
shake-upを科学する
rsakata
7
930
Reach American Airlines®️ Instantly: 19 Calling Methods for Fast Support in the USA
flyamerican
1
180
ABEMAの本番環境負荷試験への挑戦
mk2taiga
5
810
cdk initで生成されるあのファイル達は何なのか/cdk-init-generated-files
tomoki10
1
540
IPA&AWSダブル全冠が明かす、人生を変えた勉強法のすべて
iwamot
PRO
2
220
データ基盤からデータベースまで?広がるユースケースのDatabricksについて教えるよ!
akuwano
3
160
microCMSではじめるAIライティング
himaratsu
0
120
QuickSight SPICE の効果的な運用戦略~S3 + Athena 構成での実践ノウハウ~/quicksight-spice-s3-athena-best-practices
emiki
0
260
全部AI、全員Cursor、ドキュメント駆動開発 〜DevinやGeminiも添えて〜
rinchsan
2
2.2k
推し書籍📚 / Books and a QA Engineer
ak1210
0
120
United™️ Airlines®️ Customer®️ USA Contact Numbers: Complete 2025 Support Guide
flyunitedguide
0
780
Featured
See All Featured
For a Future-Friendly Web
brad_frost
179
9.8k
We Have a Design System, Now What?
morganepeng
53
7.7k
The World Runs on Bad Software
bkeepers
PRO
69
11k
KATA
mclloyd
30
14k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
31
1.3k
A Tale of Four Properties
chriscoyier
160
23k
Measuring & Analyzing Core Web Vitals
bluesmoon
7
510
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.6k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3.1k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
231
53k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
7
330
How STYLIGHT went responsive
nonsquared
100
5.6k
Transcript
Bleichenbacher RSA Signature Forgery ( 2006 ) oalieno
PKCS
PKCS • PKCS ( Public Key Cryptography Standards ) 是公鑰密碼標準
• 制定了了⼀一系列列從 PKCS#1 到 PKCS#15 的標準 • 其中 PKCS#1 是 RSA Cryptography Standard
ASN.1 • ASN.1 是⾼高階的抽象標準 • 具體的實作編碼規則有 : BER, CER, DER,
PER, XER
PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313 Step 1 : Message Digest M
H(M) HASH Sign
• 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
Step 3 : RSA encryption D d % n =
S Sign PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
Step 1 : RSA decryption Verify S e % n
= D PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
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
Step 3 : Message digesting and comparison M' H(M)' H(M)
Verify compare PKCS#1 1.5 Signature https://tools.ietf.org/html/rfc2313
Bleichenbacher RSA Signature Forgery ( 2006 )
Bleichenbacher RSA Signature Forgery ( 2006 ) https://mailarchive.ietf.org/arch/msg/openpgp/5rnE9ZRN1AokBVj3VqblGlP63QE • ⼜又稱作
BB06 • 針對 PKCS#1 1.5 ( RFC 2313 ) • RSA 簽章偽造 06
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
• 在 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
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
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
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
RSA Signature Forgery in python-rsa ( 2016 ) CVE-2016-1494
RSA Signature Forgery in python-rsa ( 2016 ) https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/ •
實作缺陷 : padding bytes 可以是任意字元 直接取第⼆二個 0x00 沒有檢查中間的 padding bytes
• 在 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/
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/
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/
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/
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/
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/
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/
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/
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/
A Decade After Bleichenbacher '06, RSA Signature Forgery Still Works
( 2019 )
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 去找到可以任意亂塞的部分有多長
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
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
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
Defense against RSA Signature Forgery
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