Skip to content

Instantly share code, notes, and snippets.

@hashedhyphen

hashedhyphen/ronen_2018.md

Created January 5, 2019 17:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hashedhyphen/2db38f3f66b070a928f7e1868eb89e3d to your computer and use it in GitHub Desktop.
Save hashedhyphen/2db38f3f66b070a928f7e1868eb89e3d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ronen_2018.md

The 9 Lives of Bleichenbacher’s CAT: New Cache ATtacks on TLS Implementations

https://eprint.iacr.org/2018/1173.pdf

  • Eyal Ronen (Weizmann Institute)
  • Robert Gillham (University of Adelaide)
  • Daniel Genkin (University of Michigan)
  • Adi Shamir (Weizmann Institute)
  • David Wong (NCC Group)
  • Yuval Yarom (University of Adelaide, Data61)

どういうもの？

  • RSA PKCS #1 v1.5 に準拠した様々な TLS 実装群について、サイドチャネル攻撃が可能な新たな脆弱性をパディング処理部に複数発見
  • 既存手法よりもサイドチャネル攻撃の確度を向上させ、パディングオラクル攻撃に利用した際の必要クエリ数の削減に成功
  • さらに、パディングオラクル攻撃自体を並列化し、2048-bit RSA の TLS に対する active MitM を現実のタイムアウト内で実現

先行研究と比べてどこがすごい？

  • OpenSSL API に対するサイドチャネル攻撃について、既存手法は処理時間や performance counter を使用

  • Flush+Reload という別の既存手法を採用することで確度を向上

  • Klima et al. 2003 で Bleichenbacher attack の並列化可能性が示唆された（部分的に複数クエリを並列に投げる）

  • Bock et al. 2018 (ROBOT) で複数サーバの利用による並列化可能性が示唆された

  • Nguyen 2009 で Bleichenbacher attack のより直感的な形式として格子手法が提案された

  • 今回の研究では、鍵が共通な複数サーバと格子手法を利用した具体的・高速な並列化手法を提示

  • Jager et al. 2015 の padding oracle MitM attack は 1024-bit RSA で 1097s

  • 今回の並列化手法により、2048-bit RSA でもタイムアウト 30s 以内に平文への復号に成功

技術や手法のキモは？

サイドチャネル攻撃

前提条件:

  • 攻撃対象の実装と同じマシン (CPU のキャッシュ機構) でコードを実行できること (パブリッククラウドで実現可能なことは先行研究が実証済み)
  • 復号したいデータを取得できるようにネットワーク上の中間者であること (passive MitM)
  • 攻撃対象の実装に選択暗号文を復号させられること

TLS における PKCS #1 v1.5 の実装は以下の 3 段階に分けられるが、このすべてで脆弱性が見つかった

1) 暗号文を復号して byte array に変換する処理

  • RSA 自体は平文と暗号文をリトルエンディアンで定義

  • PKCS #1 v1.5 はビッグエンディアンで定義

  • この差異によりフォーマットの変換処理が必ず行われる

  • この変換処理において、復号結果が小さい値であった場合、0x00 で先頭を埋める処理が必要

  • 内部に分岐を持った memset などを使用している TLS 実装が存在

  • その分岐を使って branch prediction attack が成立し、Manger oracle を構成することが可能

  • Manger oracle: 平文の先頭バイトが 0x00 かどうかの oracle

  • Bleichenbacher oracle: 平文の先頭 2 バイトが 0x00 0x02 かどうかの oracle

2) byte array が PKCS #1 v1.5 標準に準拠しているか検査する処理

  • とある OpenSSL API は、この検査処理内部に分岐が存在（片方のみ memset がある、エラー時のみロギングがある）
  • これを使って Bleichenbacher attack が可能なことが既に指摘されている（ただし OpenSSL 自体はこの API を使用していない）
  • しかし、Amazon s2n はこの API を利用しているため脆弱

3) PKCS #1 v1.5 非準拠時に平文を乱数で入れ替える処理

  • パディングのフォーマット検証に失敗した場合、その復号された平文を乱数で入れ替える必要がある（パディングオラクル攻撃対策）
  • Apple CoreTLS では乱数を入れ替える処理が if 文の中に含まれているため、エラー時のみ乱数生成処理が走る
  • 乱数生成は比較的重い処理なので oracle として使用可能
  • 他にもエラーロギング処理などで複数の if 文があるため branch prediction attack で Bleichenbacher-type oracle を構成可能

高速化

基本方針

  • Bleichenbacher oracle や Manger oracle を使ってパディングオラクル攻撃を完遂するには膨大な oracle queries が必要
  • 所要時間を制限したとき、攻撃が成功する確率はかなり小さい。ただし無視できないほど小さいわけではない。
  • oracle queries は確率試行（ベルヌーイ試行）なので、成功確率を 0.1% に設定すれば必要クエリ数は減らせる
  • その攻撃を BEAST 攻撃のように何回も試行して、最終的な成功確率を上げる

具体的な方法

  • 鍵を共有する複数のサーバに対して、それぞれ異なる初期値で padding oracle attack を並列に実行する
  • ただし、各サーバへの攻撃は最後まで行わず、ある程度のステップで打ち切る
  • 各攻撃から得られた情報を集めて（確率的に）復号を試行する。これは Hidden Number Problem (Hidden Subgroup Problem?) に帰着でき、格子基底縮小などを用いて解けることが知られている

パディングオラクル攻撃と active MitM を用いた Online Downgrade Attack

  • PKCS #1 v1.5 は RSA なので、RSA が drop された TLS 1.3 だとサイドチャネル攻撃の前提となる passive MitM ができない
  • ただし、RSA に強制させる active MitM 手法を Jager et al. 2015 が発見
  • サーバ: 署名と鍵交換で同じ RSA 証明書を使用 && TLS 1.2（または TLS 1.2 と 1.3 を並行）で運用している場合
  • クライアント: TLS 1.3 でも可
  • パディングオラクル攻撃を利用した active MitM により RSA 鍵交換への online downgrade attack が可能なことを示唆
  • ただし、実験の結果としては実際のブラウザのタイムアウトに間に合わない

実際、Amazon AWS のサーバは署名と鍵交換に同じ RSA 証明書を使用している

上記の高速化手法により、実際のブラウザのタイムアウト 30s 以内に攻撃できるように

どうやって有効だと検証した？

良く知られた TLS 実装以下 9 つでテストし、先頭 7 つが現実的な PoC で攻撃成功

  • OpenSSL
  • Amazon s2n
  • MbedTLS
  • Apple CoreTLS
  • Mozilla NSS
  • WolfSSL
  • GnuTLS
  • BearSSL
  • Google BoringSSL

OpenSSL API に対する攻撃

  • 4 core Intel Core i7-7500
  • 4MiB cache & 16GiB memory
  • Ubuntu 18.04.1
  • FLUSH+RELOAD 攻撃を Mastik toolkit で実装

既存手法と比べてエラーレートを 4.3% -> 1.1% に改善したため oracle queries を 1/6 に削減

OpenSSL のデータ変換に対する攻撃

  • Intel NUC computer

  • Intel Core i7-6770HQ CPU

  • 32 GiB memory

  • CentOS 7.4.1708

  • shadow branches の生成という既存手法を採用

  • ただし shadow branches の生成する方法を工夫することで確度を 98% に向上させた（既存手法の確度は？）

  • 対象となる複数の分岐点を並列に監視することはできず、Manger attack については 1 クエリを複数回送信することになっている

Online Active MitM

  • Manger Oracle を用いて 2048 bits RSA の TLS に MitM できることをシミュレーションした（実際に OpenSSL とかで実験したかどうかは明確に書かれていない気がする）
  • TLS コネクションのタイムアウトは 30s と仮定
  • 各 TLS handshakes は 0.05s と仮定 (Core i7-7500U CPU @ 2.70GHz での実測値とのこと)
  • 並列攻撃するサーバは 5 つ
  • Manger attack の適応的なクエリは、各サーバに対し 560 クエリに制限
  • 最後の 2s は格子基底縮小と handshake の finalize に使用
  • 格子基底縮小の LLL アルゴリズムには Sage を使用（Intel Core i7-4790 CPU @ 3.6GHz で 0.01s 未満、所要時間は十分短い）

以上の条件で PoC を実装し、平文の復号に成功

0.1% の確率で各並列攻撃から 438 bits 以上の情報を得られ、合わせて 2190 bits 以上。これは復号するのに十分な情報量

議論はある？

Recommendation for Mitigation

  • RSA 鍵交換を捨てろ
  • 署名と鍵交換で証明書を別にしろ
  • サーバごとにも証明書を分けろ
  • BoringSSL や BearSSL のように定数時間で処理するコードや API を使え
  • 鍵長 N を大きくすれば MitM 攻撃を非現実的にできるかもしれない (log N なので)
  • クライアントのタイムアウトは短く
  • RSA ほとんど使われてないから RSA の処理速度を落とすか
  • 復号処理は他の処理と共有されるハードウェアではなく専用のハードウェアで動かせ

Future Work

  • 今回用いた並列化手法は、RSA 実装に対する他のサイドチャネル攻撃にも応用できるかもしれない
  • 他のクライアント (curl や git など) についてもタイムアウトについて要調査
  • Keyless TLS (LURK extension など) も要調査

次に読むべき論文は？

  • 1983 Interval oracle attack, 1 bit leakage から RSA を復号 (Ben-Or et al.) -> 先頭ビットが 1 の oracle

  • 1996 DH 鍵交換の秘密鍵における MSB の考察 (Boneh & Venkatesan) -> 格子基底縮小の応用

  • 1998 PKCS #1 v1.5 padding oracle attack (Bleichenbacher) -> 先頭が 0x00 0x02 の oracle

  • 1999 TLS 1.0 (RFC 2246)

  • 2001 PKCS #1 v2.0 (v1.5 も可) padding oracle attack (Manger) -> 先頭が 0x00 の oracle

  • 2003 Bleichenbacher 亜種 (Klima et al.)

  • 2005 AES の設計自体に対する cache-timing attacks (Bernstein)

  • 2006 TLS 1.1 (RFC 4346)

  • 2007 OpenSSL RSA に対する命令キャッシュの side channel attack (Aciicmez)

  • 2008 TLS 1.2 (RFC 5246)

  • 2009 Bleichenbacher attack を lattice techniques で置き換え (Nguyen)

  • 2012 Bleichenbacher の 2M queries を 3800 queries に削減 (Bardou et al)

  • 2012 Bleichenbacher 亜種 XML encryption (Jager et al.)

  • 2013 Lucky 13 (TLS CBC HMAC に対する padding oracle attack)

  • 2014 Bleichenbacher 亜種 (Meyer et al.)

  • 2014 Bleichenbacher 亜種 (Zhang et al.)

  • 2014 FLUSH+RELOAD (Yarom & Falkner)

  • 2015 TLS 1.3 での RSA key exchange downgrade (Jager et al.)

  • 2015 cache attacks による Lucky 13 対策の回避 (Irazoqui et al.)

  • 2018 cache attacks による Lucky 13 対策の回避 (Ronen et al.) -> 著者

  • 2018 ROBOT (Return of Bleichenbacher's oracle threat) (Bock et al.)

  • 2018 microarchitectural side channel attacks (Ge et al.)

  • M. Ben-Or, B. Chor, and A. Shamir, “On the crypto-graphic security of single RSA bits,” in STOC, 1983.

  • D. Boneh and R. Venkatesan, “Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes,” in CRYPTO, 1996.

  • J. Manger, “A chosen ciphertext attack on RSA optimalasymmetric encryption padding (OAEP) as standardized in PKCS #1 v2.0,” inCRYPTO, 2001

  • V. Kl ́ıma, O. Pokorn ́y, and T. Rosa, “Attacking RSA-based sessions in SSL/TLS,” inCHES, 2003

  • D. J. Bernstein, “Cache-timing attacks on AES,” 2005.

  • O. Acıic ̧mez, “Yet another microarchitectural attack: Exploiting I-Cache,” in CSAW, 2007.

  • P. Q. Nguyen,Public-Key Cryptanalysis, ser. Contempo-rary Mathematics. AMS–RSME, 2009, vol. 477.

  • R. Bardou, R. Focardi, Y. Kawamoto, L. Simionato,G. Steel, and J. Tsay, “Efficient padding oracle attackson cryptographic hardware,” in CRYPTO, 2012.

  • T. Jager, S. Schinzel, and J. Somorovsky, “Bleichen-bacher’s attack strikes again: Breaking PKCS#1 v1.5 inXML encryption,” in ESORICS, 2012

  • N. J. AlFardan and K. G. Paterson, “Lucky thirteen: Breaking the TLS and DTLS record protocols,” in IEEESP, 2013, pp. 526–540. https://www.ieee-security.org/TC/SP2013/papers/4977a526.pdf

  • C. Meyer, J. Somorovsky, E. Weiss, J. Schwenk,S. Schinzel, and E. Tews, “Revisiting SSL/TLS im-plementations: New Bleichenbacher side channels andattacks,” in USENIX Security, 2014.

  • Y. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart,“Cross-tenant side-channel attacks in PaaS clouds,” in CCS, 2014.

  • Y. Yarom and K. Falkner, “FLUSH+RELOAD: A highresolution, low noise, L3 cache side-channel attack,” in USENIX Security, 2014.

  • T. Jager, J. Schwenk, and J. Somorovsky, “On the secu-rity of TLS 1.3 and QUIC against weaknesses in PKCS#1 v1.5 encryption,” in CCS, 2015.

  • G. Irazoqui, M. S. Inci, T. Eisenbarth, and B. Sunar,“Lucky 13 strikes back,” in ASIA CCS, 2015.

  • E. Ronen, K. G. Paterson, and A. Shamir, “Pseudoconstant time implementations of TLS are only pseudosecure,” in CCS, 2018.

  • H. B ̈ock, J. Somorovsky, and C. Young, “Return of Bleichenbacher’s oracle threat (ROBOT),” in USENIXSecurity, 2018

  • Q. Ge, Y. Yarom, D. Cock, and G. Heiser, “A survey ofmicroarchitectural timing attacks and countermeasures on contemporary hardware,”J. Cryptographic Engineering,vol. 8, no. 1, 2018.

Bleinbacher は noisy oracle に耐性がある。Manger は耐性がない。

Bleichenbacher attack に対しては PKCS #1 v1.5 validation に失敗したら、その平文を別の適当な乱数値に入れ替える必要がある。ただし、この premaster secret の選択についてエラーケースなどで処理時間が変わってしまってはいけない。

microarchitectural side channel attacks: プロセッサレベルのキャッシュ機構について、別のプログラムとそれを共有していた際に、別プログラムの影響を受ける性質を利用

TLS 1.3 は RSA を drop した、TLS 1.2 も RSA より ECDH を推奨している。そのため、攻撃者は RSA へのダウングレード攻撃を仕掛ける必要がある

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment