如果使用安全种子，如何利用C rand（）？

#1 楼

C标准的ISO / IEC 9899：1990版本包含：


示例下列函数定义了rand和srand的可移植实现。

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

该发生器的状态完全由变量next的31个低位组成。如果像问题中那样“使用LavaRnd生成一个随机数来播种srand()，然后使用rand()生成一些大密钥”，那么“大密钥”最多只能有$ 2 ^ {31} = 2147483648 $结果，完全由输入seed的31个低位决定。

然后允许攻击尝试所有这些键。如果测试密钥需要以$ 2 ^ {31} $ Hz运行的$ 2 ^ 3 $核心CPU的$ 2 ^ {20} $个时钟周期（大约一百万个），则预计攻击将持续$ 2 ^ {31 + 20- 3-31-1} = 2 ^ {16} = 65536 $秒，不到一天。

根据“大钥匙”的处理方式，攻击可能会更快。例如，如果rand()也用于生成初始化向量（通常在加密消息的开头），情况就是这样。一个简单的攻击就可以从三个连续的next值中找到rand()的值。实际上，这不需要眨眼，而且可以轻松查找rand()的所有过去和将来的输出，而不会被srand()中断。

另一方面，也许在$ 2 ^ {20} $以上的周期估计值太低（RSA密钥可能就是这种情况）。但是无论如何，31位密钥空间太低了。目前，实际安全性的门槛大约为80位，即20或20。在2030年之前128被认为是可以的，除非人们相信仙子或量子计算机很快将可用于密码分析。

#2 楼

我曾经玩过这个在线游戏，那是一个古老的MUD。您登录，聊天，杀死一些妖精。

它有一个赌场。您进入赌场并下注X黄金，则有40％的机会赢得双倍下注。显然，从长远来看，赌场将永远赢，对吧？

事情就是这样。我知道游戏是用C ++编写的，并且我知道rand（）算法。

所以这就是我要做的。我走进赌场，并尽可能快地连续下注1金大约10次。如果输了，我记录为0，如果赢了，我记录为1。

然后我将数据输入我编写的程序中。它从种子0开始遍历rand（）序列中的所有随机数。如果它生成的数字小于0.4，则为0。如果它是0.4到1.0，则为1。链中的顺序与我在赌场中记录的顺序相同。如果所有10位都匹配，则宾果游戏。我找到了游戏正在使用的当前种子。

当然，这需要一分钟左右的时间来计算，因此当人们为杀死小妖精而苦思冥想时，游戏继续进行了几百个种子。它产生了更多的数字。所以我再次进行了测试，再进行了10次快速下注，再输了10金。输入我的第二个序列到程序中，这一次它会在几微秒内找到当前种子（因为我们是从上次找到的种子开始），这一次它将打印出接下来的30个左右的下注，重新成为赢家或输家。

所以我要做的是，如果下一个数字丢失，我下注1。然后，如果要赢，我下注一半钱。布拉莫，立即增加了150％的资金。重复，重复，重复，我突然有了一个成倍增长的银行帐户。

现在，此方法存在一些问题。第一，如果游戏在您最初的10个下注的“问题”之间生成了一个随机数，则找不到顺序。没什么大不了的，只需再做一次。最终您会找到一个。

第二个问题；如果您不快，则游戏会在其他地方生成一个新的随机数，并在您下注真实时放弃您的顺序。在某些情况下，我损失了很多钱。因此，这正是我的telnet客户端中的宏真正起作用的地方。

第三个问题...该游戏使用32位整数存储货币。大约100次下注后，您最终溢出了计数器。我超过了20亿金币，却发现自己负有20亿金币。而且游戏没有编程处理负金的问题。但是数字解析系统可以。

所以我四处走走，开始给人们提供负量的黄金。嘿Zethryr，这里是负数100万！繁荣，他一生的积蓄立即消失wipe尽。

这很有趣，但是它突出了为什么伪随机数可能很危险。如果有某种方式可以让随机数定期出现在用户面前（即bet命令），那么它们将能够轻松地找出您的程序当前在rand（）种子链中的哪个位置是。一旦这样做，他们就可以通过猜测下一个随机数是什么来在您的系统中获得优势。

有时，Web开发人员将基于随机数生成器生成记录ID，盐字符串和临时密码。如果他们使用伪RNG，则攻击者可以连续创建几个帐户或记录并检查其ID号（可能已编码为URL）。然后他们可以猜测其他人的帐户或记录的ID，甚至是他们的密码。这可能非常危险。

#3 楼

请检查rand（）如何实现为LCG。 int值有效地暴露了内部状态中的大多数位。

具有两个后续值（以及一些蛮力）将完全恢复原始种子并允许预测将来的值。

这个论坛上已经有一个关于它的问题（使用Java），这让我感到惊讶，而且它是如此容易。

#4 楼

我在此地址发布了随机数预测方法，该方法可减少rand（）生成序列的攻击键空间；也有可能以类似的方法猜测种子。