php 伪随机数的爆破

1 简介

接上篇，这一部分实现用GPU暴力猜解MT19937的种子。上一部分已经说过，php7.1.0之后的实现是标准的MT19937算法，这里就是针对标准MT19937算法进行爆破种子。

主要是因为php中mt_rand函数的种子空间是32位的(即seed最大取值232-1)，长度不是很长，参考php里的随机数这篇文章，用cpu来跑，需要比较长的时间，实验下用gpu跑的速度。

2 具体实现

同上篇一样，由于要用clojure的gpu相关的库，要添加依赖到deps.edn:

{:deps{uncomplicate/neanderthal{:mvn/version"0.22.0"}}}

然后是gpu执行的设备代码, php7_mt.cu:

//参考地址// https://5alt.me/2017/06/php%E9%87%8C%E7%9A%84%E9%9A%8F%E6%9C%BA%E6%95%B0/ // c的多线程MT19937爆破代码，基于此代码修改// 版权声明/*  The following functions are based on a C++ class MTRand by  Richard J. Wagner. For more information see the web page at  http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/MersenneTwister.h  Mersenne Twister random number generator -- a C++ class MTRand  Based on code by Makoto Matsumoto, Takuji Nishimura, and Shawn Cokus  Richard J. Wagner  v1.0  15 May 2003  rjwagner@writeme.com  The Mersenne Twister is an algorithm for generating random numbers.  It  was designed with consideration of the flaws in various other generators.  The period, 2^19937-1, and the order of equidistribution, 623 dimensions,  are far greater.  The generator is also fast; it avoids multiplication and  division, and it benefits from caches and pipelines.  For more information  see the inventors' web page at http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html  Reference  M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally  Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions on  Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.  Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,  Copyright (C) 2000 - 2003, Richard J. Wagner  All rights reserved.  Redistribution and use in source and binary forms, with or without  modification, are permitted provided that the following conditions  are met:  1. Redistributions of source code must retain the above copyright    notice, this list of conditions and the following disclaimer.  2. Redistributions in binary form must reproduce the above copyright    notice, this list of conditions and the following disclaimer in the    documentation and/or other materials provided with the distribution.  3. The names of its contributors may not be used to endorse or promote    products derived from this software without specific prior written    permission.  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*/#defineMAX_SEED0xffffffff// Mersenne Twister macros and parameters#definehiBit(u)((u)&0x80000000U)/* mask all but highest  bit of u */#defineloBit(u)((u)&0x00000001U)/* mask all but lowest    bit of u */#defineloBits(u)((u)&0x7FFFFFFFU)/* mask    the highest  bit of u */#definemixBits(u,v)(hiBit(u)|loBits(v))/* move hi bit of u to hi bit of v */#defineN(624)/* length of state vector */#defineM(397)/* a period parameter */#defineRAND_RANGE(__n,__min,__max,__tmax)\(__n)=(__min)+(long)((double)((double)(__max)-(__min)+1.0)*((__n)/((__tmax)+1.0)))#definePHP_MT_RAND_MAX((long)(0x7FFFFFFF))/* (1<<31) - 1 */typedefunsignedintuint32_t;typedefstruct{uint32_tstate[N];uint32_tleft;uint32_t*next;}MTState;__device__staticinlineuint32_tphp_twist(uint32_tm,uint32_tu,uint32_tv){return(m ^(mixBits(u,v)>>1)^((uint32_t)(-(uint32_t)(loBit(u)))&0x9908b0dfU));}__device__staticinlineuint32_tmt_twist(uint32_tm,uint32_tu,uint32_tv){return(m ^(mixBits(u,v)>>1)^((uint32_t)(-(uint32_t)(loBit(v)))&0x9908b0dfU));}__device__voidmtInitialize(uint32_tseed,MTState*mtInfo){/* 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. */registeruint32_t*s= mtInfo->state;registeruint32_t*r= mtInfo->state;registerinti=1;  *s++ = seed &0xffffffffU;for(; i < N; ++i){*s++ =(1812433253U*(*r ^(*r >>30))+ i)&0xffffffffU;    r++;}}__device__voidmtReload(MTState*mtInfo){/* Generate N new values in state    Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */registeruint32_t*p= mtInfo->state;registerinti;registeruint32_t(*twist)(uint32_t,uint32_t,uint32_t)= mt_twist;for(i = N - M; i--; ++p)*p = twist(p[M], p[0], p[1]);for(i = M; --i; ++p)*p = twist(p[M-N], p[0], p[1]);  *p = twist(p[M-N], p[0], mtInfo->state[0]);  mtInfo->left = N;  mtInfo->next = mtInfo->state;}__device__voidmt_srand(uint32_tseed,MTState*mtInfo){mtInitialize(seed, mtInfo);  mtInfo->left =0;}__device__uint32_tmt_rand(MTState*mtInfo){/* Pull a 32-bit integer from the generator state    Every other access function simply transforms the numbers extracted here */registeruint32_ts1;if(mtInfo->left ==0)mtReload(mtInfo);  --(mtInfo->left);  s1 = *mtInfo->next ++;  s1 ^=(s1 >>11);  s1 ^=(s1 <<7)&0x9d2c5680U;  s1 ^=(s1 <<15)&0xefc60000U;  s1 ^=(s1 >>18);returns1;}__device__uint32_tphp_mt_rand(MTState*mtInfo){returnmt_rand(mtInfo);}__device__uint32_tphp_mt_rand_range(MTState*mtInfo,uint32_tmin,uint32_tmax){uint32_tnum= php_mt_rand(mtInfo);returnnum%(max-min+1)+min;}__device__intcompare(MTState*mtInfo,uint32_tvalue,uint32_tmin,uint32_tmax){if(php_mt_rand_range(mtInfo, min, max)== value)return1;elsereturn0;}// 以上代码来自 https://5alt.me/downloads/mt_rand.c// 以下函数基本和mt_rand_me.cu相同,不再注释extern"C"__global__voidmt_rand_find(uint32_tsseed,uint32_t*value,uint32_tlength,uint32_tmin,uint32_tmax,bool*found,unsignedint*sols){unsignedintgid= blockDim.x * blockIdx.x + threadIdx.x;uint32_tseed= sseed + gid;  sols[gid]=0;MTStateinfo;  mt_srand(seed, &info);for(inti=0; i < length; i++){if(!compare(&info, value[i], min, max))return;}*found =true;  sols[gid]= seed;}//只用一个线程，用于测试randextern"C"__global__voidmt_rand(unsignedintseed,intstep,intmin,intmax,unsignedint*ret){MTStateinfo;unsignedintx=0;  mt_srand(seed, &info);for(inti=0; i <= step; i++){x = php_mt_rand_range(&info, min, max);}*ret = x;}

最后是clojure的host代码:

(require '[uncomplicate.clojurecuda.core:refer:all])(require '[uncomplicate.commons.core:refer:all])(init)(device-count)(defmy-gpu(device0))(defctx(context my-gpu))(current-context! ctx)(defphp-rand(slurp"php7_mt.cu"))(defrand-program(compile!(program php-rand)))(defrand-module(module rand-program))(defmt-rand-find(function rand-module"mt_rand_find"))(defmt-rand-one(function rand-module"mt_rand"));; 注意，php7.1.0以上mt_rand()和mt_rand(min,max)返回结果不同;; mt_rand()返回的数字右移了一位;; 参考php7 mt_rand.c中的注释，为了和以前兼容,mt_rand()返回的最大值位2^31;; /*;; * Melo: it could be 2^^32 but we only use 2^^31 to maintain;; * compatibility with the previous php_rand;; */;; RETURN_LONG(PHP_MT_RAND_MAX); /* 2^^31 */;;;; 这里只是示例，全部采用mt_rand(min,max)进行测试(defthreads2000000);; GPU线程数量(defsizethreads);; 保存GPU计算结果的数组大小，等同于GPU线程数量(defbool-size1)(defuint-size4)(defmax-rand(int(dec(Math/pow231))))(defnfind-rand-range-one-block[n values &[opts]](let[found(mem-alloc bool-size)_(memcpy-host!(byte-array[0])found)values-len(count values)values-match(mem-alloc(* uint-size values-len))_(memcpy-host!(int-array values)values-match)min(get opts:min0)max(get opts:maxmax-rand)sols-len(* size uint-size)sols(mem-alloc sols-len)_(launch! mt-rand-find(grid-1d size)(parameters n                              values-match                              values-len                              min                              max                              found                              sols))ret-found(->(memcpy-host! found(byte-array1))first)ret-sols(memcpy-host! sols(int-array size))](release sols)(release values-match)(release found)(when-not(zero? ret-found)(println"block:"n"ret found:"ret-found)(filter(comp not zero?)ret-sols))))(defmax-blocks(/0xffffffff(+ size1)))(defnfind-all-seed[vals &[opts]](doseq[n(range(int(Math/ceil max-blocks)))](let[rs(find-rand-range-one-block(* size n)vals opts)](whenrs(doseq[r rs](println"found:"(Integer/toUnsignedString r)))))));; 跟第二部分不同，随机序列的长度对速度影响不大了;; 因为算法的实现，取624个值后才进行reload,现在计算同一个seed的下一个随机数时mt_rand的计算量较小。;; 这里仅为了测试，指定了一个比较大的max,这样就算随机序列短一点,seed也不会那么多;; php7.3执行，获取两个元素的随机数序列;; php -r 'mt_srand(88663332); echo mt_rand(0,12345689)."---".mt_rand(0,12345689). "\n";';; 5079804---2835549(time(find-all-seed[50798042835549]{:max12345689}));; block: 88000000 ret found: 1;; found: 88663332;; "Elapsed time: 465653.628795 msecs";; 跑完整个32位地址空间，不到8分钟，可以看到比cpu还是快很多的。(defnrand-range-one[seed &[opts]](let[step(get opts:step0)ret(mem-alloc50)min(get opts:min0)max(get opts:maxmax-rand)_(launch! mt-rand-one(grid-1d1)(parameters seed step min max ret))ret-sols(memcpy-host! ret(int-array1))](release ret)(first ret-sols)))(comment;; 应该和php结果相同(rand-range-one1234{:max62:step0});; => 6(rand-range-one1234{:max62:step1});; => 39;; php7.3 执行结果如下;; $ php -r 'mt_srand(1234); echo mt_rand(0,62)."---".mt_rand(0,62). "\n";';; 6---39;;; php中不指定min max，需要把结果右移一位(rand-range-one1234);; => 822569775(bit-shift-right*11);; => 411284887 (->(rand-range-one1234{:step1})(bit-shift-right1));; => 1068724585;; php7.3 执行结果如下;;  $ php -r 'mt_srand(1234); echo mt_rand()."---".mt_rand(). "\n";';;  411284887---1068724585);; clean env(release rand-module)(release rand-program)(release ctx)

同第二部分一样，测试随机字符串序列，如下php代码：

<?phpfunctionrandStr($l=4){$ret="";$chars="qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM";for($i=0;$i<$l;$i++)$ret.=$chars[mt_rand(0,strlen($chars))];return$ret;}// 注意mt_srand的参数与第二部分的不同mt_srand(6688991);echorandStr(5);?>

randStr结果是:P3ThR 现在根据randStr的结果猜解出seed:

;; 首先要获得随机后的转换表，才能把字符串转换回随机数序列。;; 这里假定已经有了这个表(defchars"qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM")(defnrand-strs->rand-seq"把随机结果字符串转换回随机数字序列"[strs](mapv #(->>(str%1)(.indexOf chars))strs));; randStr结果(defresult"P3ThR")(defrand-seq(rand-strs->rand-seq result))rand-seq;; => [45 28 40 15 39](defmax-r(count chars))max-r;; => 62(time(find-all-seed rand-seq{:maxmax-r}));; block: 6000000 ret found: 1;; found: 6688991;; block: 32000000 ret found: 1;; found: 32333633;; block: 322000000 ret found: 1;; found: 322799803;; block: 828000000 ret found: 1;; found: 829594924;; block: 1930000000 ret found: 1;; found: 1930582992;; block: 2016000000 ret found: 1;; found: 2016439798;; block: 2310000000 ret found: 1;; found: 2311825734;; block: 3632000000 ret found: 1;; found: 3633831162;; block: 3776000000 ret found: 1;; found: 3776934990;; "Elapsed time: 466266.530259 msecs"

可以看到，对于比较小的随机范围和随机序列，找到的seed比较多。

3 总结

GPU计算确实快，对于爆破，值得拥有。如果为了加快速度，可以多块显卡并行计算,并不难实现。 可以说分分钟就能预测出原始seed。难度在于得到mt_rand生成随机序列之后的变换过程，只有知道这个过程才能获得原始的随机序列，进行seed爆破。比如上面示例的php代码中的chars字符串。

当然种子空间增加的话，难度也会直线上升，以现在的硬件水平，64位的mt19937应该没那么容易爆破了。

作者: ntestoc