Python3.6でのdictのキー順維持と、hash randomizeによるDoS回避の関係について

Question

訂正 DDoS ではなく、 DoS でした。ベストアンサーを決定済みなので本文はそのままにしてタイトルだけ修正します。以降すべてDDoS -> DoS で読み替えお願いします。

###前提

Pythonは以前からdictのキーの順番は不定、とされてきました。
しかし、見た目上は何らかの固定の順番でdictのキーを取り出せていました。（不定だけど一定） --(A)

Python3.3では、 hash randomizeが導入されました。
導入された目的は、object.__hash__のドキュメントに書いてあったので以下に引用します。

この目的は、慎重に選ばれた入力で辞書挿入の最悪性能 O(n^2) 計算量を悪用することで引き起こされるサービス妨害 (denial-of-service, DoS) に対する保護です。 詳細は http://www.ocert.org/advisories/ocert-2011-003.html を参照してください。

この導入によって、dictのキーの順番がインタプリタ起動毎に不定になりました。 --(B)

そしてPython3.6でdictの実装が変わり、dictが省メモリになり、キーの順番が維持されるようになりました。 ref: Python 3.6 の（個人的に）注目の変更点 - methaneのブログ --(C)

検証したこと

Python2.7.13で文字列のhash値を取得(**(B)**の確認)

$ python2.7 -c "print(hex(hash('abc')))"
0x142a6050a093d0a3
$ python2.7 -c "print(hex(hash('abc')))"
0x142a6050a093d0a3
$ python2.7 -c "print(hex(hash('abc')))"
0x142a6050a093d0a3

Python3.5.2で文字列のhash値を取得(**(B)**の確認)

$ python3.5 -c "print(hex(hash('abc')))"
0x53a97f418e279642
$ python3.5 -c "print(hex(hash('abc')))"
-0x745a06d34cd5d4ed
$ python3.5 -c "print(hex(hash('abc')))"
0x29736bbb038652f5

Python3.6.0で文字列のhash値を取得(**(B)**の確認)

$ python3.6 -c "print(hex(hash('abc')))"
0x11108253ed4a023b
$ python3.6 -c "print(hex(hash('abc')))"
-0x5dc778080cb917cd
$ python3.6 -c "print(hex(hash('abc')))"
-0x687164debf8ee240

Python2.7.13で辞書のキー順を取得(**(A)**の確認)

$ python2.7 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['a', 'c', 'b', 'e', 'd', 'g', 'f']
$ python2.7 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['a', 'c', 'b', 'e', 'd', 'g', 'f']
$ python2.7 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['a', 'c', 'b', 'e', 'd', 'g', 'f']

Python3.5.2で辞書のキー順を取得(**(B)**の確認)

$ python3.5 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['e', 'd', 'f', 'a', 'b', 'c', 'g']
$ python3.5 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['e', 'f', 'g', 'b', 'a', 'c', 'd']
$ python3.5 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['d', 'e', 'a', 'g', 'b', 'f', 'c']

Python3.6.0で辞書のキー順を取得(**(C)**の確認)

$ python3.6 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['a', 'b', 'c', 'd', 'e', 'f', 'g']
$ python3.6 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['a', 'b', 'c', 'd', 'e', 'f', 'g']
$ python3.6 -c "print(list(dict.fromkeys(list('abcdefg'))))"
['a', 'b', 'c', 'd', 'e', 'f', 'g']

質問

Python3.6では、セキュリティ上安全で、これまでOrderedDictを使っていたプログラムをdictで一部置き換え可能と考えてよいでしょうか？
複数の要素が絡み合っていそうなので、質問を以下の3つに分けます。

1. **(B)**で、DDoS回避のためにdictキー順をランダム化したかった訳ではなく、object.__hash__がランダム化された副作用でdictキー順が起動毎にランダムになった、という理解であってますか？

2. Python3.6未満でも、PYTHONHASHSEED環境変数を指定すれば、起動毎には変化しない以前の挙動を復活させる方法がありますが、これをやるとDDoS回避の実装を無効化することになるという理解であってますか？

3. **(C)**で、dictのキー順が維持されるようになりましたが、これはキー順がobject.__hash__の結果に依存しなくなった、という理解で合っていますか？ DSAS開発者の部屋:Python に現在実装中の Compact dict の紹介 からそのように読み解きました。

Comments

[jun68ykt]

詳細に突っ込んだご質問ありがとうございます。以下の質問 https://teratail.com/questions/146865 への回答の追記1にてこちらの質問を参照させて頂きました。

[shimizukawa]

はい。ありがとうございます

Answer 1

外部QAサイト(StackOverflow)引用ですが "Why is the order in dictionaries and sets arbitrary?" に詳細回答がついています。

前掲サイトの回答原文(英語)を参照頂いた方が正確ですが、私の見解を簡単にまとめます。断定的な表現でない部分は、あまり確信がありません。解釈誤りあれば訂正下さい。

---

(B)で、DDoS回避のためにdictキー順をランダム化したかった訳ではなく、object.__hash__がランダム化された副作用でdictキー順が起動毎にランダムになった、という理解であってますか？

はい。

意図的なハッシュ値の衝突、および同事象により引き起こされるDDoS攻撃を回避するため、ハッシュ関数の出力結果がランダム化されました。同回避策の副作用として、ハッシュテーブル実装（≒ハッシュ値に依存）を採用するdictキー順序もランダム化されました。

---

Python3.6未満でも、PYTHONHASHSEED環境変数を指定すれば、起動毎には変化しない以前の挙動を復活させる方法がありますが、これをやるとDDoS回避の実装を無効化することになるという理解であってますか？

部分的に、はい。

少なくともCPython 3.3～CPython 3.5実装では、DDoS回避策が無効化されるため、再びDDoS攻撃の脅威にさらされます。CPython 3.6の新しいdict実装に対しては、ハッシュ関数のランダム／非ランダムとDDoS回避効果の相関は読み取れませんでした（私には）。

---

(C)で、dictのキー順が維持されるようになりましたが、これはキー順がobject.__hash__の結果に依存しなくなった、という理解で合っていますか？

恐らく、いいえ。

参照先回答を読む限り、CPython 3.6であってもdict内部実装で「ハッシュ関数は依然として利用する」ように読めます。このような内部実装とはまた別に、同実装上の振る舞いとしてdictキー順が維持され（当然、順序維持のための仕組みが別途あり）ます。

---

Python3.6では、セキュリティ上安全で、これまでOrderedDictを使っていたプログラムをdictで一部置き換え可能と考えてよいでしょうか？

CPython 3.6でdictキー順が保持されるのは、あくまでも実装仕様としてです。Python言語の仕様としてはPython 3.5以前と同様に、「dictキー順序は任意」となっていますので、この点だけ注意してデータ型を選択ください。

Comments

[shimizukawa]

回答ありがとうございます。
リンクを教えていただいたStackOverflowの情報はとても参考になりそうです。じっくり読んでみます。

(3)については、私もobject.__hash__は使っていると思っています。あくまでキー順がobject.__hash__の結果に依存しなくなったのだと理解していますので、回答いただいた内容で認識が合ってそうだと思いました。

Dictのキー順序意義があくまで実装依存、というのはそのとおりですね。
https://twitter.com/raymondh/status/773978885092323328 こんなtweetをみたので、言語仕様としては順番を保障しないことを忘れそうになりました。指摘ありがとうございます。

[shimizukawa]

リンク先を読みました。

> CPython 3.6の新しいdict実装に対しては、ハッシュ関数のランダム／非ランダムとDDoS回避効果の相関は読み取れませんでした（私には）。

上記については、リンク先では特に触れていませんでした。しかし、dictがキーの挿入順を持っていること、密なhashテーブルを持っていること、3.3以降のhashはrandomizeされていること、から類推して、hash collision を引き起こす攻撃があっても3.6の新しいdict実装が3.5よりも悪い影響を受けることは無いと言えそうです。

大変参考になりました。ありがとうございました。

[shimizukawa]

頂いた回答をまとめて、簡単に検証したものをblogにまとめました
また、 @methane さんからTwitterでツッコミをもらったのでそれについても書いてあります。
http://www.freia.jp/taka/blog/python3-hash-randomie/index.html