- 暗号コードで重要な 定数時間（constant-time） 性質は、コンパイラ最適化だけでも壊れる可能性があり、LLVM 内部に警告パッチを入れて危険なパターンを見つける実験が進められている
- コンパイラの「最適化」はベンチマークの一部を高速化できるが、実際の中核パスは intrinsics とアセンブリ に依存することが多く、最適化で生じたバグのコストも別途積み上がる
- 2024年6月、Antoon Purnal は Kyber 参照コードが Clang 15 以降の一部最適化オプションで 秘密値に基づく条件分岐 に変わり、タイミング攻撃を許す可能性があることを確認した
- TIMECOP 2 は SUPERCOP 内で定数時間だと宣言されたコンパイル結果を検査するが、Valgrind 対応命令や実際のテスト実行で現れたデータフローに限界がある
- 実務上の対応としては、
crypto_{int,uint}{8,16,32,64}.h のような関数でコンパイラが 1 ビット結果を bool と見なせないようにするか、検証済みアセンブリ・セキュリティ指向言語・専用コンパイラへ移行する方向になる
コンパイラ「最適化」が生む責任の空白
- 最新の LLVM と GCC の変更履歴には、「最適化」、最適化テスト、テスト修正、「最適化」バグ修正が繰り返し登場する
- コンパイル前には正しく動いていたコードがコンパイラ変更後に変わっても、多くの場合その責任は「undefined behavior」を踏んだプログラマに帰される
- こうした「language standards」はコンパイラ作者たちが作っており、結果として小さなコンパイラ作者集団の変更よりも、何百万ものプログラマのコードのほうが大きな責任を負わされる構造になっている
- 暗号コードの例では、複数の CPU ベンチマークで
kyber768 の avx2 実装は「最適化」コンパイラでコンパイルした移植性コードより約 4 倍高速
最適化性能測定の限界
- 2000年、Todd A. Proebsting は Proebsting's Law で「コンパイラの進歩は18年ごとに計算能力を2倍にする」と表現し、コンパイラ最適化の寄与は周辺的だと結論づけた
- Arseny Kapoulkine は 2022 年の ベンチマーク で、LLVM 11 は LLVM 2.7 より最適化コンパイルに 2 倍長くかかり、実行コードは概ね 10〜20% 高速だとまとめた
- どちらの議論も、実際の利用者が体感する性能測定を捉えきれていない
- 性能が集中する ホットスポット には intrinsics とアセンブリが多く入る
- FFmpeg には
.asm と .S ファイルで 160,000 行のアセンブリがある
- コンピュータとネットワークがより多くのデータを処理するほど、実際の CPU 時間はこうしたホットスポットにさらに載る
- セキュリティコストも最適化議論とは別に増大している
- Deloitte は 2023 年の IT セキュリティ予算が企業売上の 0.5% だと報告した
- 2022 年の世界全体の企業総売上が 48 兆ドル超だったという数字と合わせると、総額は数千億ドル規模になりうる
- ただし Deloitte の 0.5% は企業ごとの単純平均かもしれず、すべての企業が調査に回答したわけではないという留保がある
タイミング漏洩と Kyber の事例
- 「最適化」コンパイラが生むセキュリティ問題には、伝統的なバグだけでなく、秘密情報が実行時間に漏れる タイミング漏洩 も含まれる
- Laurent Simon、David Chisnall、Ross Anderson の EuroS&P 2018 論文 は、コンパイラ更新が以前は安全だったコードに予告なくタイミングチャネルを開く可能性があると警告した
- 2018 年論文で強調された例は、
bool で 2 つの値のどちらかを選ぶコードで、bool がコンパイラの条件ジャンプ生成を誘発するというものだった
- 暗号実装ではこれを避けるため、重要なコードから
bool を排除し、定数時間比較関数を別に用意する慣行がある
- OpenSSL はそのために 37 個の関数を宣言していると引用されている
- 2015 年の
curve25519-donna と MSVC 2015 の事例は、本文では誤解だったと整理されている
- 実際には 32 ビット x86 向けにコンパイルした際、
int64 演算が Microsoft の 32 ビット int64 ライブラリ llmul.asm 呼び出しに変換されていた
- タイミング漏洩は
llmul.asm のデータ依存分岐で生じており、このライブラリも合理的なソースコード概念に含めるべきだとされる
- 2024 年 6 月、Antoon Purnal は Kyber 参照コードが Clang 15 以降の一部最適化オプションでタイミング攻撃を許しうることを確認した
- 問題の形は
(-((x>>j)&1))&y で、これは x の j 番目のビットが立っていれば y、そうでなければ 0 を作る計算である
- Clang はビットテスト命令で対象ビットを
bool に変換し、その bool に基づく 条件分岐 を生成する
- LLVM 内部では
lib/CodeGen/SelectionDAG/DAGCombiner.cpp の combineShiftAnd1ToBitTest がこの「最適化」を処理する
- この関数は Sanjay Patel が 2019 年 9 月に 追加 し、その後複数人が修正している
- GCC にも似た境界侵犯の事例がある
- ARM の 2021 年 11 月の GCC パッチ は
(-x)>>31 を -(x>0) に変換する
- 2024 年 4 月にはこれに対する警告が出た
TIMECOP と定数時間検査
- TIMECOP 2 は SUPERCOP 暗号テストフレームワークに組み込まれており、定数時間だと宣言されたコンパイルコードに対して 秘密値由来の条件分岐 を自動検査する
- 検査対象は条件分岐だけでなく、秘密値から導かれた配列インデックスも含む
- TIMECOP 1 は Moritz Neikes が SUPERCOP を改造して作ったツールで、Adam Langley の ctgrind アプローチを自動化したものだった
- TIMECOP 2 は既存方式をいくつか拡張している
- RNG 出力を自動的に 秘密値 とマークする
- “declassification” をサポートする
- “public inputs” 指定をサポートする
- 複数コアで実行される
- TIMECOP には明確な制限がある
- Valgrind が対応する命令しか扱えず、AMD XOP 命令などでは停止する
- 実際のテスト実行で観測されたデータフローしか検査しない
- 定数時間動作の検査ツール開発は継続しており、関連ツール一覧は ct-tools にある
- TIMECOP 相当の検査は libmceliece のテストスイートにも入り、他ライブラリへ広がる可能性がある
定数時間への書き換え手法
- 可変時間コード片を見つけた後は、バグを入れずに定数時間へ書き換える方法が必要になる
- 2024 年 7 月の発表では、libmceliece と SUPERCOP が提供する定数時間関数の一部が紹介された
- ファイル名は
crypto_{int,uint}{8,16,32,64}.h
- これらのファイルは他プロジェクトへコピーして使える
- 例の関数
crypto_uint32_bitmod_mask(x,j) は -((x>>(j&31))&1) と同じ効果を持つが、コンパイラが 1 ビット結果 を見えないようにする
- より複雑な例として
crypto_uint32_max(x,y) もある
- 2018 年論文は、Clang/LLVM に定数時間関数
__builtin_ct_choose(bool cond, x, y) を追加する tweak を扱っている
- この論文は、この関数 1 つで十分だと誤って提案していた
- この関数が将来コンパイラに入る可能性はあるが、プロジェクトが依存できるようになるまでには長い時間がかかるかもしれない
- 実装方式は
crypto_{int,uint}{8,16,32,64}.h より脆弱に見えると評価されている
問題を事前に避ける方法
- コンパイル済みライブラリの配布前テストが、コンパイラ導入のタイミング漏洩を検出できれば、コードを書き換えている間は以前のコンパイラ版を使って配布できる
- この方法は、利用者を継続して安全に保つための暫定対応である
- 1 つの解決策は、ライブラリを アセンブリ で配布すること
- ただし、この水準に達していない暗号ソフトウェアでは、アセンブリ監査の難しさという問題が依然として残る
- C、C++ などで書かれたコードに、タイミング漏洩防止の「ワクチン」を迅速に入れる方法も模索されている
clang-vs-clang パッチ実験
x&1 と x>>31 の共通点は、結果の候補が 2 つしかないこと
x&1 は 0 または 1uint32 の x>>31 は 0 または 1int32 の x>>31 は 0 または -1
- この種の形は、コンパイラ「最適化」作者が 1 ビット結果を
bool に入れやすい
- 常に
-fwrapv でコンパイルし、GCC と Clang に 2 の補数算術 を仮定させるべきだという勧告がある
- 単純にソース中の
&1、1&、>>31 などをスキャンしても多くの例が見つかるが、LLVM “optimizer” に直接パッチを入れて別の方法でスキャンした
- パッチ は LLVM commit
68df06a0b2998765cb0a41353fcf0919bbf57ddb を起点に &1 と >>31 を探し、次の警告を出す
please take this away before clang does something bad
- 例のコンパイルコマンドは
clang -Rpass-analysis=clang-vs-clang -O -c x.c
- テスト関数は次のとおり
int sra31(int x)
{
x >>= 31;
return x;
}
- 同じ警告が繰り返されるのは不思議ではない
- コンパイラは「最適化」がこれ以上進まなくなるまで、適用を繰り返し試みるからだ
clang-vs-clang の出力は shift で signed と unsigned を区別する
- この違いは
crypto_{int,uint}{8,16,32,64}.h ベースの手動または自動書き換えに重要である
- ソース変換自動化の方法の 1 つとして
clang-tidy が挙げられている
#ifdef で外されたコードや、この「最適化」段階より前に除去されたコードは clang-vs-clang 警告を出さない
SUPERCOP 実行結果と発見事例
- SUPERCOP 20240716 を dual EPYC 7742 上で
./data-do-biglittle により実行した
- オーバークロックは無効化した
- SUPERCOP のコンパイラ一覧は
okcompilers/{c,cpp} の clang 行に -Rpass-analysis=clang-vs-clang を追加し、clang-vs-clang を使うよう調整した
- 結果は 3 時間後に準備できた
- 出力には、public data に基づくソース分岐が Clang 内部で
&1 を作って生じるノイズが多い
- 明らかに事前変更すべき例は次のとおり
a0 += (a0>>15)&106;
- 単純なソーススキャンで見つけるには C の構文解析が必要な例は次のとおり
- マクロ
ONE8 は ((uint8_t)1) と定義される
*pk2^=(((* pk_cp)>>ir)&ONE8)<<jr;
- さらに見つけにくい例は AVX2 intrinsic ベースのマクロから出る
signmask_x16(x) は _mm256_srai_epi16((x),15) と定義される- これは 256 ビットベクトル内の各 signed 16 ビット片を 15 ビット右シフトする
mask = signmask_x16(sub_x16(x,const_x16((q+1)/2)));
- この AVX2 の事例は当面優先度が高くない
- ベクトル演算が条件分岐に変わるには AVX-512 でコンパイルし、さらにコンパイラがベクトル化された
bool を直列の bool 条件分岐へ変換するという奇妙な判断をする必要がある
- TIMECOP は Valgrind を使い、Valgrind は AVX-512 をサポートしていない
- 現時点では AVX-512 コンパイルは推奨されない
int128 とより広い対応方針
- 最も興味深い発見は、
int128 の 64 ビット右シフトが >> 警告を引き起こした事例である
int128 実装は内部的に、上位 64 ビットワードの符号を調べるために 63 ビット右シフトを使う可能性がある- Clang が GCC のように 63 ビット右シフトを
bool、さらに条件分岐へ変換するサポートを加えると、多くの int128 コードが突然 可変時間 になりうる
- この場合は 2015 年論文タイトルが主張した状況に近いが、今回は実際のソースに
bool がなくても起こる
- ソースレベルで最も簡単な防御策は、コンパイラ既存の
int128 実装を避けて crypto_int128 関数を使うこと
crypto_int128 は GCC と Clang の int128 と違い、小さな 32 ビットプラットフォームでも動作できる
- GCC と Clang に秘密データ型を追加する案は魅力的に見えるが、両コンパイラの構造上、それを堅牢に実現する方法はあまり見えていない
- 最初からセキュリティのために設計されたコンパイラには、より大きな期待が寄せられている
- 新しい入力言語を要求するセキュリティ中心コンパイラとして FaCT と、活発に開発中の Jasmin がある
- コード書き換えの時間に対する懸念はあるが、現在のコンパイラが既存コードを扱う方式を見る限り、何らかの対処は必要だ
1件のコメント
Hacker Newsのコメント
未定義動作をするコードが期待どおりに動かないからといって、コンパイラのバグと呼ぶのは適切ではない
間違った引数で
ddを実行してデータを消してしまい、それでddがバグだと言うのと似ているソースコードやコンパイラがバグだというより、C標準が筆者の基準ではあまりに仕様が薄く、一部の対象でセキュリティバグを生むと見るほうが妥当だ
結局のところ、C標準の策定者はハードウェアの動作までは定義できず、言語意味論しか定義できないので、暗号分野はハードウェア起因のバグに悩まされるしかない
Rustの利点の1つは、潜在的な未定義動作を
unsafeブロック内に制限していることだ。それでも、Cでは未定義動作になる多くの事柄をRustが定義していても、unsafeコードに入ると微妙な未定義動作をうっかり踏むのは非常に簡単だ静かに失敗して予測不能なコードを生成する3つ目のモデルは、コンパイラ作者にしか役立たない。仕様の陰に隠れても、実際の利用者には利益がない
その最適化が、以前は正しく動いていたコードを壊してしまう。コンパイラ作者は下位互換性を優先することもできるが、そうしていない
しかも、こうした最適化が実際のコード性能を有意に改善しているわけでもないのだから、コードを壊すというトレードオフに価値があるという主張こそ反証されるべきだ
Bernsteinは好きだが、ときどき方向を誤って過激になることがあり、この記事はその好例だ。本人も最後で半ば認めている
記事の大部分は、最適化の利益がどれほど大きいかという副次的な論点で、たとえデータがあってもユースケース次第の判断になる
核心となる不満は、Cコンパイラが言語で表現できない意味論を考慮しないことだが、驚くような話ではない
最後に「必要な意味論を表現できる言語を使え」と言っているが、記事全体はその一文で置き換えられたはずだ
そのかなりの部分は根拠が疑わしく、正しいプログラムを書くことをより難しくしている
CとC++ は、定数時間保証を持つアルゴリズムを書くのに不向きだ
標準にはリアルタイムの概念がほとんどなく、コンパイラも拡張機能として追加の保証を提供していない
しかし、これをコンパイラ開発者のせいにするのは筋違いだ
Intel CPUでは、
clangであれ何であれ、ユーザーモードで正しいコードを生成することはできない。そもそも正しいコードが存在しないからだhttps://www.intel.com/content/www/us/en/developer/articles/t...
文書の
DOITMを見ると、ユーザー空間の暗号ライブラリが必要なビットを設定するのは単純に不可能だ一度有効になればユーザー空間でも問題なく動作するので、たとえば
prctlシステムコールで有効化されるプロセス単位のフラグにして、スケジューラのコンテキストスイッチ時にMSRを調整する、といったことは可能だ「可能な限り、コンパイラ作者は自分たちが作ったバグの責任を取りたがらない」という一文を見ただけでも、ブログ記事の専門性がここまで早く崩れる例は珍しい。
リンク先までたどってみると、未定義動作が「任意の値」を生み出すという意味ではない、というごく基本的なCの話でしかない。
未定義動作があっても、ソースコードはバグがあっても生成されたプログラムは依然として正しい、ということはよくある。後になってコンパイラ作者が新しい最適化を入れ、その未定義動作を根拠にバグのあるプログラムを生成すると、責任の押し付け合いが始まる。
認めたがらない点は、ユーザーに対する責任があらゆる側に分散していることだ。CRUDアプリが
NULLの逆参照をしたせいでバッテリーが発火したとしても、まともな人ならアプリ作者がNULLチェックを忘れたことだけを責めはしないだろう。コンパイラ、OS、ハードウェアの各ベンダーも、無責任に設計した製品について責任を負うべきであり、ISO標準で「未定義動作」と書かれているだけで話は終わらない。サプライチェーンのすべての構成員は、製品がどう誤用されうるかを予測し、合理的に対処する責任を分かち合っている。
未定義動作は価値を与えるために存在する。そうしたものがなくても言語は作れるのに、あえて存在するのは移植性とコンパイラ作者に与える柔軟性のためだ。
記事の要点は、その柔軟性が未定義動作なしにプログラムを書く難しさと比べて、本当に価値があるのかという点にある。
筆者は、バグで失う金額のほうが高速なバイトコードで節約できる金額より大きく見え、また言語標準に何を入れるかを決める際にコンパイラ作者の影響力が大きいため、これを改めようとする意志は弱いと見ている。
参考までに、
clangには関数ごとにすべての最適化を無効にするclang::optnone属性があり、GCC には名前で最適化を追加・削除したり、コンパイラフラグに関係なく最適化レベルを設定できる優れたgnu::optimize属性がある。gnu::optimize(0)はそのclangフラグに近い。clangには特にmemcpyとmemsetの最適化を無効にするclang::no_builtinsもある。optimize属性は デバッグ目的 にのみ使用すべきであり、プロダクションコードには適していない」https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
暗号分野の人たちが求める目標、たとえば 定数時間評価 や秘密値の隠蔽にはある程度共感する。
しかし汎用コンパイラはたいていの場合そうしたことを考えていないので、せいぜい大体は動くハック以上のものにはなりにくそうだ。
本気でやるなら専用の特殊コンパイラが必要か、引き続きアセンブリに行くしかないだろう。
いつか今を悪しき昔として振り返り、未定義動作がはるかに少ない言語へCから移行している気がする
Cでは、コンパイルは通るが、コンパイラには意図を到底理解できない表現をあまりにも簡単に書けてしまう
たとえばPythonでは
result = [something(value) for value in set_object]のようなコードが書ける。setオブジェクトには順序がないため、要素の処理順や結果の順序が重要でないことが明確であり、これはコンパイラが作者の意図を推測しなくても、言語レベルで多くの最適化を可能にする不変データを持つ他の言語の類似コードでは、さらに一歩進んで、
something(value1)がsomething(value2)に影響し得ないため、スレッドでもプロセスでも並列実行できるCコンパイラ最適化のかなりの部分は、コードパターンを見て、作者が意図したであろう処理をより高速に行う方法を見つけることだ。Cは現代的な言語に比べて意図を表現する能力が乏しいので推測の自由度はあるが、まともな性能を出すにはそうした推論を行わなければならない
それでも、ハッブル望遠鏡に眼鏡が必要だった件のように、偽装された恩恵かもしれない。限界を克服しようとして優れた技法が生まれ、問題を修正した後には、それらの技法が当初の想定をはるかに上回る性能を出した。Cコンパイラ最適化をC以外の言語に適用すれば、超能力のように働くかもしれない
基本的には未定義動作に似ているが、直ちに安全性の問題になるのではなく、誤った結果として現れることがある。もちろん、その誤った結果が後になって安全性の問題につながることはあり得る
未定義動作と違って、あり得るすべての
setの順序でコードが動作するか確認する「サニタイザ」を作るのは事実上不可能だgccとclangには、他の言語ではあまり見られない低レベルのヒントが多い。__builtin_expect/__builtin_unpredictable、__builtin_unreachable/__builtin_assume、#pragma clang loop vectorize(assume_safety)/#pragma GCC ivdep、ループ展開やベクトル化を無効にしたり、特定の値を選んだりする pragma などがある最も大きく欠けているのは、値の出所を根拠にコンパイラが推論できないよう、明示的に防ぐ最適化バリアだと思う。
__asm__である程度は可能だが、望ましくない副作用があり、プラットフォームごとのレジスタ種別名も必要になる高レベルな意図ベース最適化の潜在力も確かにある。ループで
n回pushする前に配列リストの領域を予約したり、同じキーに対するcontains→get→putのハッシュマップ参照をまとめたり、グローバルな割り当て動作を局所的に推論してオブジェクトや割り当て自体を消したり、といったものが思い浮かぶCは実際のハードウェアに十分近く、プログラマは単に何をするかをそのまま述べられるので、コンパイラがプログラマの意図を推測する必要がない
そうしたメモリ最適化を実装する言語はたいていJava系で、そもそも攻撃的な先行的悲観化があるため、そうした最適化を行う動機が生まれる。だが、その最適化でも損失は埋め合わせられない
要するに、Cも大したものではないが、他はさらに悪いということだ
Cのセマンティクスが気に入らないなら、コンパイラエンジニアに腹を立てるのではなく、別のプログラミング言語を使えばいい
qhasm以外をどこまで許容できるのかは分からない。Zigですらそうだ。今回の評も、彼からすればそれほど意外ではないあまり耳にしない観点を伝える新鮮な記事だ。あわせて読む価値がある: https://gavinhoward.com/2023/08/the-scourge-of-00ub/