Clever Geek Handbook

Python乱数セキュリティ

この記事は、疑似乱数ジェネレーター（PRNG）の脆弱性に関する一連の出版物の2番目です。



最近、PRNGの脆弱性について、基礎（[1]）からさまざまなプログラミング言語の脆弱性まで、またそれらに基づいてCMSやその他のソフトウェア（[2]、[3]、[4] ）



PRNGはWebアプリケーションセキュリティの多くの側面の基盤であるため、これらの出版物は人気があります。 擬似乱数/文字シーケンスは、以下のWebアプリケーションを保護するために使用されます。





George ArgyrosとAggelos Kiayias （[3]）の研究に基づく以前の記事では 、 PHPSESSIDに基づいてPHPの乱数を予測し、さまざまな方法で擬似乱数のエントロピーを減らすことを学びました。



Pythonで開発されたWebアプリケーションのPRNGを見てみましょう。



Python PRNG機能



Pythonには、ランダム/擬似乱数を生成するように設計された3つのモジュールがあります： random 、 urandomおよび_random ：





ランダム（）


最初はMTアルゴリズム（ _randomモジュール）を使用しますが、まず最初にurandomから取得したSEEDを使用して初期化を試み、PRNGをRNG（乱数ジェネレーター）に変換します。 urandomを呼び出せない場合（たとえば、 / dev / urandomが見つからない場合、またはadvapi32.dllライブラリから目的の関数を呼び出せない場合）、 int（time.time（）* 256）が SEEDとして使用されます（既にご存じのとおり、エントロピーが不十分）。



システムランダム（）


SystemRandom（）は、外部ソースを使用してランダムデータを生成するurandomモジュールを呼び出します。



MTアルゴリズムの実装の変更点は、PRNG 状態の現在の状態からの624の番号の1つに基づく1つの番号の代わりに、2つの番号が使用されることです。 



random_random() { unsigned long a=genrand_int32(self)>>5, b=genrand_int32(self)>>6; return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0)); }


また、PHPとは異なり、ジェネレーターは長い変数だけでなく、任意のバイトシーケンス（ init_by_array（）が呼び出されます）を使用して初期化できます。これは、エントロピーの外部ソースを使用してランダムモジュールをインポートするときに発生します（32バイトが取得されます） urandomから）、これが失敗した場合、 時間（）が使用されます： 



 if a is None: try: a = int.from_bytes(_urandom(32), 'big') except NotImplementedError: import time a = int(time.time() * 256)


保護



これらの変更は、PHPとは異なり、 random.random（）を呼び出した場合でも十分なジェネレーターエントロピーを提供するようです。 しかし、すべてが「悪い」わけではありません。



Pythonフレームワークの機能は、PHPとは異なり、PythonがWebサーバーで1回実行されることです。つまり、 import randomコマンドが実行されるか、 random.seed（）が強制されると、デフォルト状態の初期化が1回発生しますWebアプリケーションのまれなケース）、次のアルゴリズムを使用してMT状態への攻撃を許可します。





状態を決定する精度は、状態要素（ i ）のインデックスに依存します。imod 2 = 0の場合、エントロピーは2 ^ 6 、 i mod 2 = 1-2 ^ 5の場合です。



次に、クエリ1,2,199,200を使用して、状態state_1 [1] 、 state_1 [2] 、 state_1 [3] 、 state_1 [397] 、 state_1 [398]を決定し 、それに基づいて状態state_2 [1]およびstate_2 [2]を生成し、リクエスト番号313の乱数が取得されます。 ただし、この数のエントロピーは2 ^ 24（16M）です。 エントロピーは、クエリ511および625を使用して削減されます。 これらのクエリは、 state_2 [397] 、 state_3 [1]の計算に役立ちます。 これにより、状態オプションの数が2 ^ 8に減少します。 クエリNo. 313で使用される「乱数」の合計256のバリアントがあります。



攻撃の前提条件は、クエリプロセスに干渉しないことです。これにより、PRNGの状態に影響します（つまり、状態インデックスが正しく決定される）。 また、リクエストNo. 1はインデックスが224以下のPRNGの状態要素を使用する必要があります。そうでない場合、リクエストNo. 200はアルゴリズムの実行を許可しないジェネレータの異なる状態を使用します。 このイベントの確率は36％です。



したがって、リクエストNo. 625の追加タスクは、以前のすべてのリクエストが実際に必要な状態で行われ、リクエストプロセスに誰も参加していないことを判断することです。



さらに、6つのリクエストの乱数を受け取るスクリプトに注目します。 出力では、リクエスト番号313のすべての可能な乱数が生成されます。



実用化



いくつかのPythonフレームワークとWebアプリケーション（特にPloneとDjango）を分析しました。 残念ながら、（そしておそらく幸いなことに）それらの間で脆弱性を見つけることはできませんでした。



最も可能性の高い候補はPloneで、これは乱数出力（ SiteErrorLog.py ）を持っていますが、攻撃の問題は次のとおりです。 PloneはPython 2.7で動作します。*は 、 floatが str（）に出力されると、最後の5桁を切り捨て、反復オプションの数（ローカル列挙とサーバーへの外部要求の両方）を非常に大きな数に拡張します。



3番目のブランチのPythonは、 st（）r関数のフロートをカットしません。この関数は、そのアプリケーションを攻撃の主な候補にします。



入力で6つの乱数を受け取るスクリプト （テストスクリプトvuln.pyなどから必要なインデックスを使用して状態によって初期化されます）に注目し、出力で選択した乱数の可能なバリアントを生成します。 このシナリオの平均的なコンピューターでの実行時間は約1時間です。



注：このシナリオでは、（i mod 2 = 1）の状態要素を決定する際に発生する可能性のあるエラーは考慮されないため、効率は36％から18％に低下します。



おわりに



（Webサーバー側での）Pythonフレームワークコードの実行の特性により、攻撃者はPHP言語で実装することが不可能または非常に困難な攻撃を実行できます。 PRNGを保護するには、単純なルールに従う必要があります。





参照資料



[1] http://habrahabr.ru/post/151187/

[2] http://jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html

[3] http://crypto.di.uoa.gr/CRYPTO.SEC/Randomness_Attacks_files/paper.pdf

[4] http://www.slideshare.net/d0znpp/dcg7812-cryptographyinwebapps-14052863

[5] http://media.blackhat.com/bh-us-10/presentations/Kamkar/BlackHat-USA-2010-Kamkar-How-I-Met-Your-Girlfriend-slides.pdf

[6] http://en.wikipedia.org/wiki/Mersenne_twister

[7] http://jazzy.id.au/default/2010/09/22/cracking_random_number_generators_part_3.html



著者：ユヌソフ・ティムール。


More articles:


All Articles