密码学 从入门到放弃 序列密码

发表于 分类于 阅读次数：

XMan Day2，整理一下bibi师傅的笔记。

序列密码部分。

序列密码又称流密码，是使用一个随时间变化的加密变换，一次加密一个明文的独立符号单位。

随机数

不存在真正的随机数。

伪随机数发生器特性

相同的种子产生的随机数相同，其种子多是来源于时间和噪音。

Brute Seed

例题

Jarvis OJ的一题babyrpd。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Unbuffered(object):
    def __init__(self, stream):
        self.stream = stream

    def write(self, data):
        self.stream.write(data)
        self.stream.flush()

    def __getattr__(self, attr):
        return getattr(self.stream, attr)


import sys

sys.stdout = Unbuffered(sys.stdout)
import signal

signal.alarm(600)

import random
import time

flag = open("/root/level0/flag", "r").read()

random.seed(int(time.time()))
           

def check():
    recv = int(raw_input())
    if recv == random.randint(0, 2 ** 64):
        print flag
        return True
    else:
        print "atum tql"
        return False


while 1:
    if check():
        break

根据上述条件，种子相同的随机数生成器生成的随机数一样的，因此只需要爆破时间就好了。

要注意的是此处在对比recv()和random.randint()函数的值的时候，每比较一次，需多生成一次随机数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from zio import *
import time
import random

target = ("47.97.215.88", 20000)

io = zio(target)
io.interact()


def getstream(times):
    for i in range(times - 1):
        random.randint(0, 2 ** 64)
    return random.randint(0, 2 ** 64)


times = 0
now = int(time.time()) + 10
while 1:
    now -= 1
    times += 1
    seed = random.seed(now)
    io.writeline(str(getstream(times)))
    if "atum" not in io.readline():
        break

Linear Congruential PRNG

Java中的java.util.Random，C中的rand()，PHP中的rand()都有着相似的特性，使用一个48位的种子，被同一个线性同余公式生成，若使用的初始种子一样，则生成返回的随机序列一样，公式和初始值如下。

1
2
3
4
next_state = (state * multiplier + addend) mod (2 ^ precision) 
multiplier = 25214903917
addend = 11 
Precision = 48

从中摘抄了部分java.util.Random的实现代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Random implements java.io.Serializable {
    static final long serialVersionUID = 3905348978240129619L;
    
    private final AtomicLong seed;

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

    private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53)
    
    private static final AtomicLong seedUniquifier = new AtomicLong(8682522807148012L);
    
    public Random(long seed) {
        if (getClass() == Random.class)
            this.seed = new AtomicLong(initialScramble(seed));
        else {
            // subclass might have overriden setSeed
            this.seed = new AtomicLong();
            setSeed(seed);
        }
    }

    private static long initialScramble(long seed) {
        return (seed ^ multiplier) & mask;
    }
    
    public int nextInt() {
        return next(32);
    }
    
    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));
    }
}

此处截取的是有参的Random(long seed)构造函数，可以看到的是当seed一致的时候，返回生成的序列值也都一样。

例题

Jarvis OJ的一题mediumrpd。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Unbuffered(object):
   def __init__(self, stream):
       self.stream = stream
   def write(self, data):
       self.stream.write(data)
       self.stream.flush()
   def __getattr__(self, attr):
       return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
import signal
signal.alarm(600)
import os
os.chdir("/root/level1")

flag=open("flag","r").read()

import subprocess
o = subprocess.check_output(["java", "Main"])
tmp=[]
for i in o.split("\n")[0:3]:
    tmp.append(int(i.strip()))


v1=tmp[0] % 0xffffffff
v2=tmp[1] % 0xffffffff
v3=tmp[2] % 0xffffffff
print v1
print v2
v3_get=int(raw_input())
if v3_get==v3:
    print flag

还有一个被调用的Java代码。

1
2
3
4
5
6
7
8
9
import java.util.Random;
public class Main {
	public static void main(String[] args) {
		Random random = new Random();
		System.out.println(random.nextInt());
		System.out.println(random.nextInt());
		System.out.println(random.nextInt());
	}
}

根据上面截取的部分Random()函数的实现代码，48位的nextseed最后进行了一个>>>的无符号右移16位，因此我们最后已知的只有32位，但可以通过爆破被销毁的16位即math.pow(2,16)来求解。

1
2
3
4
5
6
7
8
9
10
Random random = new Random();
long v1 = random.nextInt();
long v2 = random.nextInt();
for (int i = 0; i < 65536; i++) {
    long state = v1 * 65536 + i;
    if (((state * multiplier + addend) & mask) >>> 16) ==v2){
        System.out.println("Seed found: " + state);
        break;
        }
    }

故Exp如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from zio import *
import time
import random
target=("47.97.215.88",20001)

io=zio(target)

v1=int(io.readline().strip())
v2=int(io.readline().strip())
def liner(seed):
    return ((seed*25214903917+11) & 0xffffffffffff)

for i in range(0xffff+1):
    seed=v1*65536+i
    if  liner(seed)>>16 == v2:
        print seed
        print liner(liner(seed))>>16
        io.writeline(str(liner(liner(seed))>>16))
        print io.readline()

Mersenne Twister

Ruby的rand()，Python的random，PHP的mt_rand()也有着相似的特性。

1
2
3
4
5
s1 = *BG(next)++;
s1 ^= (s1 >> 11);
s1 ^= (s1 <<  7) & 0x9d2c5680U;
s1 ^= (s1 << 15) & 0xefc60000U;
return ( s1 ^ (s1 >> 18) );

截取了通过上一位随机数生成下一位随机数的算法。

首先，在/ext/standard/basic_functions.h中定义如下。

1
2
3
4
5
6
7
8
9
#define MT_N (624)

#ifdef ZTS
#define BG(v) ZEND_TSRMG(basic_globals_id, php_basic_globals *, v)
PHPAPI extern int basic_globals_id;
#else
#define BG(v) (basic_globals.v)
PHPAPI extern php_basic_globals basic_globals;
#endif

以及在/Zend/zend.h中定义如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifdef ZEND_ENABLE_STATIC_TSRMLS_CACHE
#define ZEND_TSRMG TSRMG_STATIC
#define ZEND_TSRMLS_CACHE_EXTERN() TSRMLS_CACHE_EXTERN()
#define ZEND_TSRMLS_CACHE_DEFINE() TSRMLS_CACHE_DEFINE()
#define ZEND_TSRMLS_CACHE_UPDATE() TSRMLS_CACHE_UPDATE()
#define ZEND_TSRMLS_CACHE TSRMLS_CACHE
#else
#define ZEND_TSRMG TSRMG
#define ZEND_TSRMLS_CACHE_EXTERN()
#define ZEND_TSRMLS_CACHE_DEFINE()
#define ZEND_TSRMLS_CACHE_UPDATE()
#define ZEND_TSRMLS_CACHE
#endif

还有在/TSRM/TSRM.h中有如下定义。

1
2
3
4
5
6
7
#define TSRM_UNSHUFFLE_RSRC_ID(rsrc_id)		((rsrc_id)-1)

#define TSRMG(id, type, element)	(TSRMG_BULK(id, type)->element)
#define TSRMG_BULK(id, type)	((type) (*((void ***) tsrm_get_ls_cache()))[TSRM_UNSHUFFLE_RSRC_ID(id)])

#define TSRMG_STATIC(id, type, element)	(TSRMG_BULK_STATIC(id, type)->element)
#define TSRMG_BULK_STATIC(id, type)	((type) (*((void ***) TSRMLS_CACHE))[TSRM_UNSHUFFLE_RSRC_ID(id)])

后在/ext/standard/mt_rand.c中定义如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#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) ^ ((uint32_t)(-(int32_t)(loBit(v))) & 0x9908b0dfU))

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++;
	}
}
/* }}} */

/* {{{ php_mt_reload
 */
static inline void php_mt_reload(void)
{
	/* Generate N new values in state
	   Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */

	register uint32_t *state = BG(state);
	register uint32_t *p = state;
	register int i;

	if (BG(mt_rand_mode) == MT_RAND_MT19937) {
		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]);
	}
	else {
		for (i = N - M; i--; ++p)
			*p = twist_php(p[M], p[0], p[1]);
		for (i = M; --i; ++p)
			*p = twist_php(p[M-N], p[0], p[1]);
		*p = twist_php(p[M-N], p[0], state[0]);
	}
	BG(left) = N;
	BG(next) = state;
}
/* }}} */

/* {{{ php_mt_srand
 */
PHPAPI void php_mt_srand(uint32_t seed)
{
	/* Seed the generator with a simple uint32 */
	php_mt_initialize(seed, BG(state));
	php_mt_reload();

	/* Seed only once */
	BG(mt_rand_is_seeded) = 1;
}
/* }}} */

/* {{{ php_mt_rand
 */
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)++;
	s1 ^= (s1 >> 11);
	s1 ^= (s1 <<  7) & 0x9d2c5680U;
	s1 ^= (s1 << 15) & 0xefc60000U;
	return ( s1 ^ (s1 >> 18) );
}
/* }}} */

/* {{{ proto void mt_srand([int seed])
   Seeds Mersenne Twister random number generator */
PHP_FUNCTION(mt_srand)
{
	zend_long seed = 0;
	zend_long mode = MT_RAND_MT19937;

	ZEND_PARSE_PARAMETERS_START(0, 2)
		Z_PARAM_OPTIONAL
		Z_PARAM_LONG(seed)
		Z_PARAM_LONG(mode)
	ZEND_PARSE_PARAMETERS_END();

	if (ZEND_NUM_ARGS() == 0)
		seed = GENERATE_SEED();

	switch (mode) {
		case MT_RAND_PHP:
			BG(mt_rand_mode) = MT_RAND_PHP;
			break;
		default:
			BG(mt_rand_mode) = MT_RAND_MT19937;
	}

	php_mt_srand(seed);
}
/* }}} */

在PHP中使用mt_srand()给随机数发生器播种时，一般是使用MT_RAND_MT19937模式生成随机数，先调用php_mt_srand(uint32_t seed)函数，利用seed先在栈上初始化生成624组state，后调用php_mt_reload()函数重新生成624组state，接着执行BG(left) = N表示剩余未用于计算随机数的state组数，然后执行BG(mt_rand_is_seeded) = 1表示已经使用过种子播种。

最后每次调用mt_rand()函数的时候，都会先检查是否已经使用种子生成过序列值，若无则使用GENERATE_SEED()函数生成，否则就根据已有的state直接生成新的随机数，同时减少BG(left)，当其为0时再次调用php_mt_reload()函数生成新一组state。

例题

Jarvis OJ的一题hardrpd。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Unbuffered(object):
   def __init__(self, stream):
       self.stream = stream
   def write(self, data):
       self.stream.write(data)
       self.stream.flush()
   def __getattr__(self, attr):
       return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
import os
os.chdir("/root/level2")

from random import *


while 1:
    a=raw_input("#")
    target=getrandbits(32)
    if a!=str(target):
        print target
    else:
        print open("flag","rb").read()

那么根据以上的分析，只需收集好624组随机数，逆推出用作计算的state，再得出下一组新的state，计算新的第625个随机数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from zio import *
target=("47.97.215.88",20002)

io=zio(target)


getlist=[]
for i in range(624):
    print i
    io.read_until("#")
    io.writeline("1")
    getlist.append(int(io.readline().strip()))

import libprngcrack
r=libprngcrack.crack_prng(getlist)
io.read_until("#")
io.writeline(str(r.getrandbits(32)))
io.interact()