ランダムおよび擬似乱数ジェネレーターの詳細

はじめに

• セッションジェネレーター（PHPSESSID）
• キャプチャテキストの生成
• 暗号化
• パスワードを保存するための不可逆的なソルト生成
• パスワードジェネレーター
• オンラインカジノでカードを配布する手順

数字のランダムなシーケンスを非ランダムなものと区別する方法は？

もう少し複雑な例またはPi

擬似乱数ジェネレーター（PRNG）と乱数ジェネレーター（RNG）の違い

PRSPの脆弱性

• 数字間の予測可能な関係。
• ジェネレーターの予測可能な初期値。
• 乱数の生成されたシーケンスの短い期間の長さ。その後、ジェネレーターはサイクルになります。

線形合同PRNG（LCPRNG）

線形合同法の結果の予測

 public static int a = 45; public static int c = 21; public static int m = 67; public static int seed = 2; public static int getRand() { seed = (a * seed + c) % m; return seed; } public static void main(String[] args) { for(int i=0; i<30; i++) System.out.println(getRand()); } 

Javaの組み込み乱数ジェネレーターのハッキング

 private static final long multiplier = 0x5DEECE66DL; // 25214903917 private static final long addend = 0xBL; // 11 private static final long mask = (1L << 48) - 1; // 281474976710655 = 2^48 – 1 

 protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) & mask; } while (!seed.compareAndSet(oldseed, nextseed)); return (int)(nextseed >>> (48 - bits)); } 

 ((x1*multiplier + addend) & mask) << 16 

 import java.lang.reflect.Field; import java.util.Random; import java.util.concurrent.atomic.AtomicLong; public class PasswordCracking { public static final long multiplier = 0x5DEECE66DL; public static final long addend = 0xBL; public static final long mask = (1L << 48) - 1; public static void main(String[] args) { Random random = new Random(); long v1 = random.nextInt(); long v2 = random.nextInt(); long v3 = random.nextInt(); long v4 = random.nextInt(); System.out.println("v1=" + v1 + "\nv2=" + v2 + "\nv3=" + v3 + "\nv4=" + v4); // brute-force seed for (int i = 0; i < 65536; i++) { long seed = (((long) v1) << 16) + i; int nextInt = (int)(((seed * multiplier + addend) & mask) >>> 16); if (nextInt == v2) { System.out.println("Seed found: " + seed); Random crackingRandom = new Random(); try { /* set the seed for Random to be convinced that we have found the right seed because constructor Random (long seed) uses the private static long initialScramble (long seed) { return (seed ^ multiplier) & mask; } for simplicity will use Reflection */ Field privateSeedField = Random.class.getDeclaredField("seed"); privateSeedField.setAccessible(true); AtomicLong crackingSeed = (AtomicLong)privateSeedField.get(crackingRandom); crackingSeed.set(seed); }catch(Exception e) { System.out.println(e.toString()); System.exit(1); } long cv1 = crackingRandom.nextInt(); long cv2 = crackingRandom.nextInt(); long cv3 = crackingRandom.nextInt(); long cv4 = crackingRandom.nextInt(); System.out.println("Set fiend seed and generate random numbers"); System.out.println("cv1=" + cv1 + "\ncv2=" + cv2 + "\ncv3=" + cv3 + "\ncv4=" + cv4); break; } } } } 

 v1 = -1184958941 v2 = 274285127 v3 = -1566774765 v4 = 30466408 Seed found: -77657469128792 Set fiend seed and generate random numbers cv1 = 274285127 cv2 = -1566774765 cv3 = 30466408 cv4 = -803980434 

 public static long getPreviousSeed(long prevSeed) { long seed = prevSeed; // reverse the addend from the seed seed -= addend; // reverse the addend long result = 0; // iterate through the seeds bits for (int i = 0; i < 48; i++) { long mask = 1L << i; // find the next bit long bit = seed & mask; // add it to the result result |= bit; if (bit == mask) { // if the bit was 1, subtract its effects from the seed seed -= multiplier << i; } } System.out.println("Previous seed: " + result); return result; } 

PHPでPRNG Mersenneツイスターをハッキングする

 #define MT_N (624) /* rand.c */ php_uint32 state[MT_N+1]; /* state vector + 1 extra to not violate ANSI C */ php_uint32 *next; /* next random value is computed from here */ int left; /* can *next++ this many times before reloading */ unsigned int rand_seed; /* Seed for rand(), in ts version */ zend_bool rand_is_seeded; /* Whether rand() has been seeded */ zend_bool mt_rand_is_seeded; /* Whether mt_rand() has been seeded */ 

 #define N MT_N /* length of state vector */ #define M (397) /* a period parameter */ #define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */ #define loBit(u) ((u) & 0x00000001U) /* mask all but lowest bit of u */ #define loBits(u) ((u) & 0x7FFFFFFFU) /* mask the highest bit of u */ #define mixBits(u, v) (hiBit(u)|loBits(v)) /* move hi bit of u to hi bit of v */ #define twist(m,u,v) (m ^ (mixBits(u,v)>>1) ^ ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU)) /* {{{ php_mt_reload */ static inline void php_mt_reload(TSRMLS_D) { /* Generate N new values in state Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */ register php_uint32 *state = BG(state); register php_uint32 *p = state; register int i; for (i = N - M; i--; ++p) *p = twist(p[M], p[0], p[1]); for (i = M; --i; ++p) *p = twist(p[MN], p[0], p[1]); *p = twist(p[MN], p[0], state[0]); BG(left) = N; BG(next) = state; } /* }}} */ /* {{{ php_mt_initialize */ static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state) { /* Initialize generator state with seed See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier. In previous versions, most significant bits (MSBs) of the seed affect only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */ register php_uint32 *s = state; register php_uint32 *r = state; register int i = 1; *s++ = seed & 0xffffffffU; for( ; i < N; ++i ) { *s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU; r++; } } /* }}} */ /* {{{ php_mt_srand */ PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC) { /* Seed the generator with a simple uint32 */ php_mt_initialize(seed, BG(state)); php_mt_reload(TSRMLS_C); /* Seed only once */ BG(mt_rand_is_seeded) = 1; } /* }}} */ /* {{{ php_mt_rand */ PHPAPI php_uint32 php_mt_rand(TSRMLS_D) { /* Pull a 32-bit integer from the generator state Every other access function simply transforms the numbers extracted here */ register php_uint32 s1; if (BG(left) == 0) { php_mt_reload(TSRMLS_C); } --BG(left); s1 = *BG(next)++; s1 ^= (s1 >> 11); s1 ^= (s1 << 7) & 0x9d2c5680U; s1 ^= (s1 << 15) & 0xefc60000U; return ( s1 ^ (s1 >> 18) ); } 

 public static long unBitshiftRightXor(long value, long shift) { // we part of the value we are up to (with a width of shift bits) long i = 0; // we accumulate the result here long result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part long partMask = (-1 << (32 - shift)) >>> (shift * i); // obtain the part long part = value & partMask; // unapply the xor from the next part of the integer value ^= part >>> shift; // add the part to the result result |= part; i++; } return result; } public static long unBitshiftLeftXor(long value, long shift, long mask) { // we part of the value we are up to (with a width of shift bits) long i = 0; // we accumulate the result here long result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part long partMask = (-1 >>> (32 - shift)) << (shift * i); // obtain the part long part = value & partMask; // unapply the xor from the next part of the integer value ^= (part << shift) & mask; // add the part to the result result |= part; i++; } return result; } 

 long value = output; value = unBitshiftRightXor(value, 18); value = unBitshiftLeftXor(value, 15, 0xefc60000); value = unBitshiftLeftXor(value, 7, 0x9d2c5680); value = unBitshiftRightXor(value, 11); 

ハッキングエリア

擬似乱数ジェネレーターの分布の設定

三角分布

 double triangular(double a, double b, double c) { double U = rand() / (double) RAND_MAX; double F = (c - a) / (b - a); if (U <= F) return a + sqrt(U * (b - a) * (c - a)); else return b - sqrt((1 - U) * (b - a) * (b - c)); } 

指数分布

PRNGテスト

既知の乱数ジェネレーターのハッキング

• エントロピーの低い初期のNetscape SSL暗号化プロトコル[11]
• PHP セッションの脆弱性habrahabr.ru/company/pt/blog/149746
• マイクロソフトCryptGenRandom [12]
• 多くのオンラインカジノは、PRNGの脆弱性を通じて複数回標的にされています。

参照資料

オリジナル