Creative Commons License
本Blog采用 知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议 进行许可。 —— Fox <游戏人生>

游戏人生

游戏人生 != ( 人生 == 游戏 )
站点迁移至:http://www.yulefox.com。请订阅本博的朋友将RSS修改为http://feeds.feedburner.com/yulefox
posts - 62, comments - 508, trackbacks - 0, articles - 7

网络游戏安全思考——伪随机数篇

Posted on 2008-04-03 02:35 Fox 阅读(6673) 评论(15)  编辑 收藏 引用 所属分类: G游戏编程

Author: Fox

一、随机数

软件实现的随机数生成器(random number generator, RNG)生成的随机数列大多是惟定数列,因此一般被称作伪随机数(pseudorandom number, PRN),而基于热噪声(thermal noise)光电效应(photoelectric effect)放射性衰变(radioactive disintegration)等不可预知的物理现象实现的硬件随机数生成器(hardware random number generator)生成的随机数才被认为是真随机数(truly random number)。PRN在计算机领域主要用于仿真(simulation)和密码学(cryptography)。

本文仅讨论伪随机数软件实现算法,并且仅讨论满足均匀分布(uniform distribution, UD)的伪随机数发生器(pseudorandom number generator, PRNG)。非均匀分布(non-uniform distribution, NUD)的PRNG可通过满足均匀分布的PRNG与非线性函数生成。

本文讨论的PRNG应满足以下三点:

a. 在取值空间内满足UD,即等概率取得取值空间内任意值。

b. 充分随机,即该随机数列周期(period)应尽量长。此点由所谓的熵(entropy)度量。

c. 唯一输入或称种子(seed)对应唯一输出PRN。这一点ms是计算机的强项,也是PRN惟定的根源,也是算法被破解的根源。

由于PRN sequence(PRNS)惟定,所以算法的安全性主要取决于熵的选择和算法的复杂性

二、可预测PRNG与不可预测PRNG

所谓可预测(determined)PRNG,也被称为统计意义上的PRNG(statistic PRNG),一般只有一个seed,而对于同一个seed,生成的PRNS是惟定的。

不可预测(indetermined)PRNG,从理论上讲,不可预测的PRNG是不存在的,这儿指密码学安全的PRNG(cryptographically secure PRNG, CSPRNG)。

三、常用PRNGs

1、线性同余发生器(linear congruential generators, LCG)

单博伟标准库rand()函数的缺陷以及Blitz++随机数生成的简介中给出了The C Programming Langurage 2nd的实现,我手头没有这本书,所以无从查证,FallHunter应该还有吧。

 1 unsigned  int  next  =   1 ;
 2
 3 /*  rand: return pseudo-random integer on 0..32767  */
 4 int  rand( void )
 5 {
 6  next  =  next  *   1103515245   +   12345 ;
 7   return  (unsigned  int )(next / 65536 %   32768 ;
 8 }

 9
10 /*  srand: set seed for rand()  */
11 void  srand(unsigned  int  seed)
12 {
13  next  =  seed;
14 }

VS2003中给的实现是:

 1 /* **
 2 *rand.c - random number generator
 3 *
 4 *       Copyright (c) Microsoft Corporation. All rights reserved.
 5 *
 6 *Purpose:
 7 *       defines rand(), srand() - random number generator
 8 *
 9 ****************************************************************************** */

10
11 #include  < cruntime.h >
12 #include  < mtdll.h >
13 #include  < stddef.h >
14 #include  < stdlib.h >
15
16 #ifndef _MT
17 static   long  holdrand  =   1L ;
18 #endif   /* _MT */
19
20 /* **
21 *void srand(seed) - seed the random number generator
22 *
23 *Purpose:
24 *       Seeds the random number generator with the int given.  Adapted from the
25 *       BASIC random number generator.
26 *
27 *Entry:
28 *       unsigned seed - seed to seed rand # generator with
29 *
30 *Exit:
31 *       None.
32 *
33 *Exceptions:
34 *
35 ****************************************************************************** */

36
37 void  __cdecl srand (
38         unsigned  int  seed
39         )
40 {
41 #ifdef _MT
42
43         _getptd() -> _holdrand  =  (unsigned  long )seed;
44
45 #else   /* _MT */
46         holdrand  =  ( long )seed;
47 #endif   /* _MT */
48 }

49
50
51 /* **
52 *int rand() - returns a random number
53 *
54 *Purpose:
55 *       returns a pseudo-random number 0 through 32767.
56 *
57 *Entry:
58 *       None.
59 *
60 *Exit:
61 *       Returns a pseudo-random number 0 through 32767.
62 *
63 *Exceptions:
64 *
65 ****************************************************************************** */

66
67 int  __cdecl rand (
68          void
69         )
70 {
71 #ifdef _MT
72
73         _ptiddata ptd  =  _getptd();
74
75          return ( ((ptd -> _holdrand  =  ptd -> _holdrand  *   214013L
76              +   2531011L >>   16 &   0x7fff  );
77
78 #else   /* _MT */
79          return (((holdrand  =  holdrand  *   214013L   +   2531011L >>   16 &   0x7fff );
80 #endif   /* _MT */
81 }


2、LFG, LFSR等

限于篇幅,有兴趣的TX可以参考后面的资料,主要是Wikipedia,上面给的算法还是非常详细的,CSPRNGs包括Blum Blum Shub、Fortuna等。

如果出于安全性的考虑,PRNG的输出不应直接作为种子。在《构建安全的软件》一书中,作者认为“一个好的PRNG具有这样的性质:给足够的熵,即使攻击者知道全部的算法细节,还是不能猜出生成的数据流”。

三、PRNG的安全测试

FIPS-140标准包含了对RNs的测试规范。这个标准我也没有去仔细看,所以没法给出更多的信息。被提到的测试包有DIEHARD、pLab

四、随机数在游戏中的应用

1、随机数为游戏带来更多的不确定性,不确定性产生可玩性

这个应该是所有游戏的根本了吧。游戏中玩家、怪物、NPC的很多属性都是一个范围,比如攻击就有最小攻击和最大攻击,每次的实际攻击伤害总在二者之间。

同样的,玩家乐此不疲的一次次“洗装备”、“碰运气”。其他类推吧。

2、游戏的AI更多的依赖于随机数

如果怪物、NPC的AI一切尽在玩家的掌握中,游戏的乐趣就大大降低了,这一点在单机游戏中有着很好的体现。War3中,人机对战,电脑的战术并不单一(但还是有规律可循,人类玩家尚且如此),这其中固然有多方面 的因素。但随机数的功劳也不容抹杀。

3、随机数减少数据存储,一个种子可以代替一批数据

游戏中含有大量数据,如果每一项都要存取,对时间和空间都是一个考验。对于场景中随机生成的怪物信息,如果给定一个相同的种子。呃,是不是要简单一些呢?

五、相关内容

至于为什么PRNGs大多使用素数,需要更多的数论知识,对密码学有了解的TX应该能够体会到安全和数论之间的紧密联系。因为手头没有数论的书,所以不多加妄测了。到时写论文的时候,再填充上吧。

六、参考文献

1. 构建安全的软件. [美]John Viega, Gary McGraw. 钟向群, 王鹏 译.  北京. 清华大学出版社, 2003.

2. Pseudorandom number generator及相关链接. http://en.wikipedia.org/wiki/Pseudorandom_number_generator

3. PRNG - Pseudo-Random Number Generator. http://statmath.wu-wien.ac.at/prng/

-------------------------------------------------------------------------

PS01:手上的几本书

从几位TX那儿拿的几本书,放在桌上大半年了,一直没有怎么翻过。想想周末还给他们算了,于是就拿过来翻翻,立此存照,如果以后用到的话,再来查。

a. 《用TCP/IP进行网际互联》Vol. III,主要是针对Linux/POSIX套接字的C/S架构实现。因为MMORPG的C/S架构多依赖于TCP,上面第8、10-16章的内容可以关注一下。

b. 《构建安全的软件》,上面关于开源、闭源的口水(Chap. 4),关于缓冲区溢出(Chap. 7),关于随机数(Chap. 10),关于数据库安全(Chap. 14),关于客户端安全(Chap. 15),都是值得一看的东西。

c. 《UNIX环境高级编程》,进程控制(Chap. 8)、线程控制(Chap. 12)、进程通信(Chap. 15, 17)、套接字(Chap. 16)、数据库(Chap. 20)。

d. 《UNIX网络编程》Vol.I,如果涉及到泛UNIX操作系统下网络编程,可以当作参考书翻。

e. 《计算机安全原理》,加密(Chap. 5)、认证(Chap. 6)、协议安全(Chap. 7)、入侵检测(Chap. 13)、恶意攻击(Chap. 15)、灾难恢复(Chap. 19)。

PS02:微软宣布不会抬高收购Yahoo价格

消息来自Wall Street Journal,不过当天可是April Fool

PS03:关于Wikipedia

不是说Wikipedia被禁的吗?很久没有访问过了,这么好的东西,被封了还是很遗憾的。

PS04:有问题

发现问题,找Google;解决问题,找Wikipedia

PS05:欢迎补充

-------------------------------------------------------------------------

Added on Apr.10th

今天从CodeProject上看到一篇文章Applied Crypto++: Pseudo Random Number Generators),作者Jeffrey Walton对密码学和安全比较有研究。

Jeffrey Walton对Knuth的The Art of Computer Programming Vol.2中关于随机数的部分作了概括。

这篇文章从一个工程师的角度给出了随机数的应用和实现,很具有参考性。

作者还从FIPS 140-2标准中引用了下面一段话:

Random Number Generators fall into one of two classes: deterministic and nondeterministic. A deterministic RNG consists of an algorithm that produces a sequence of bits from an initial value called a seed. A nondeterministic RNG produces output that is dependent on some unpredictable physical source that is outside human control.

这一段话很好的说明,依赖于算法的RNG所生成的随机数列只可能是伪随机数,真随机数依赖于不可预测的物理源

Feedback

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-03 08:44 by Kevin Lynx
说实话,被满世界的术语蒙住了。没看懂。
还以为你要讲rand中那几个数字为什么会被使用。

# re: 网络游戏安全思考——伪随机数篇[未登录]  回复  更多评论   

2008-04-03 08:49 by len
还有日本人加强的马氏回转法,周期长,性能效果蛮好的.还有些算法,可以参见boost中的random这部分

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-03 10:29 by 杜中伟
什么时候弄个真随机数的软件实现呢 ?

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-03 10:40 by Fox
@Kevin Lynx
Xn+1 = (a*Xn+b)mod c
a, b, c通常是素数(仅仅是通常),说白了,这样一个线性同余函数其实就是所谓的Hash函数,选值不是固定不变的,ms Knuth的编程艺术(Vol. 2?)中对a, b, c的选取原则有提供。

@len
马氏回转是比较快的了,只是不是密码学安全的算法。

@杜中伟
没有考虑过遗传算法、模糊理论、神经网络能否提供真正随机的实现。不过这个倒是可以考虑,个人感觉上面几种即使实现起来,效率是个问题。

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-03 18:30 by 亨德列克
呃,今天大开眼界,一个srand() / rand() 居然能有这么多名堂,受教了

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-03 20:03 by chaosjimmy
术语有点多,有点玄乎了。程序员们经常需要随机数的时候随便拿过来一个就用,这倒不是个好的习惯,因为有些环境里的随机数发生器是不敢恭维的。最好懂一点其所以然。

# re: 网络游戏安全思考——伪随机数篇[未登录]  回复  更多评论   

2008-04-04 16:01 by fox
之所以保留诸多术语,是为了以后加到论文里方便,但仔细看的话,还是可以看得懂的,如果懂点数论知识的话,更好。

# re: 网络游戏安全思考——伪随机数篇[未登录]  回复  更多评论   

2008-04-07 00:35 by noname
@fox
是准备做反外挂系统吗?
可以参考下SD的动态加解密,防脱机外挂很NB的说
饭兄对这个dynende很熟悉的,呵呵

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-07 20:32 by Kevin Lynx
gr说,灌水也可以得分。

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-07 20:32 by Kevin Lynx
gr说,灌水也可以得分 = =

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-07 20:33 by Kevin Lynx
gr说,灌水也可以得分。 = =#

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-04-07 20:38 by Kevin Lynx
= = 结果不可以得分

# re: 网络游戏安全思考——伪随机数篇[未登录]  回复  更多评论   

2008-04-07 21:13 by CppExplore
嘿嘿,可以得分滴。不过刷新分数有间隔的,并不是实时的。

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2008-05-22 19:06 by 游戏迷
随机数为游戏带来更多的不确定性,不确定性产生可玩性

这个应该是所有游戏的根本了吧。游戏中玩家、怪物、NPC的很多属性都是一个范围,比如攻击就有最小攻击和最大攻击,每次的实际攻击伤害总在二者之间。

同样的,玩家乐此不疲的一次次“洗装备”、“碰运气”。其他类推吧

如何能破解随机数,比如幻想当中的随机领悟技能,怎么能破解各个技能的代码而且掌握其总的规律?

# re: 网络游戏安全思考——伪随机数篇  回复  更多评论   

2009-03-05 01:12 by
太多术语,

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理