密码学 从入门到放弃

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

编码

编码是为了传输方便以及协议中的格式统一。

HEX

  • 实际存储内容的16进制表示。
  • 冗余:1:21byte会变成2bytes进行存储。
  • 识别:只存在0-9A-Fa-f
  • 一般用处:可作为各类编码转换的过渡,最常见的是strint的转换。

Base家族

  • Base64/32/16:用64/32/16bytes表示所有的bytes
  • 越多的可见字符数来表现其他所有的字符越节省空间。
  • Base16==hex【使用特定的16个字符表达所有的字符,2^4→2^8
  • Base64base32同理,使用特定的64个字符表达所有的字符, 2^6→2^8
  • 单个字符取前六个bits根据编码表转码,后两位bits归入下一个字符。

例题

Base64的表被替换,该如何编码解码。

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
# /usr/bin/python
# encoding: utf-8
base64_table = ['=', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'+', '/'][::-1]


def encode_b64(s):
l = len(s)
i = 0
result = ''
while i < l:
# 将字符转换为二进制编码,然后对齐
s1 = s[i]
b1 = bin(ord(s1))[2:]
cb1 = b1.rjust(8, '0')
i += 1
if i >= l:
cb2 = '00000000'
else:
s2 = s[i]
b2 = bin(ord(s2))[2:]
cb2 = b2.rjust(8, '0')
i += 1
if i >= l:
cb3 = '00000000'
else:
s3 = s[i]
b3 = bin(ord(s3))[2:]
cb3 = b3.rjust(8, '0')
# 将三字节转换为四字节
cb = cb1 + cb2 + cb3
rb1 = cb[:6]
rb2 = cb[6:12]
rb3 = cb[12:18]
rb4 = cb[18:]
# 转换后的编码转为十进制备用
ri1 = int(rb1, 2)
ri2 = int(rb2, 2)
ri3 = int(rb3, 2)
ri4 = int(rb4, 2)
# 处理末尾为0的情况,以'='填充
if i - 1 >= l and ri3 == 0:
ri3 = -1
if i >= l and ri4 == 0:
ri4 = -1
result += base64_table[ri1] + base64_table[ri2] + base64_table[ri3] + base64_table[ri4]
i += 1
return result


print encode_b64(open("flag", "r").read())
# output: mZOemISXmpOTkKCHkp6Rgv==

两种思路,一是自己实现一个base64的解密算法来解,二是替换原表中的字符来恢复正常的编码,这儿列出第二种解题脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
base64_table = ['=', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z',
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u',
'v', 'w', 'x', 'y', 'z',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'+', '/'][::-1]

old_base64_table = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
'T',
'U', 'V', 'W', 'X', 'Y', 'Z',
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
'u',
'v', 'w', 'x', 'y', 'z',
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
'+', '/', '=', ]

res = ""
for i in "mZOemISXmpOTkKCHkp6Rgv==":
res += old_base64_table[base64_table.index(i)]

print res

其他

还有URLencodemorsecodejsfuckuuencodeXxencodeUnicode编码、Escape/Unescape编码、HTML实体编码等诸多编码,挖坑待补充。

密码

古典密码

古典密码学通常可以拿到加密算法【否则要么脑洞要么就是特征明显的题,且大部分是唯密文攻击。

移位密码

仅对密文的排列顺序进行变化。

简单移位

将密文以数字k的长度4进行分组,后按k的排列顺序排列密文,而攻击方法为肉眼识别、爆破秘钥、根据flag字符串逆推。

曲路密码

一般是将明文填入一个表中,并按照一定的曲路遍历,攻击方法只需逆向遍历。

云影密码

仅包含01248,以0分割,其他数字取和后按照26字母表转化。

栅栏密码

秘钥只有一个k,表示栅栏长度。把密文按每组k个分组,循环k次,取每组第k个字符拼接。

替代密码

会变更密文。

单表替换

以下为特例,一般是以乱序表来替换,经典的单表替代密码就是用一个替代表对每一个位置的字符进行查表替换,词频分析可解。

凯撒密码

通过把字母在字母表上移动一定位数来实现加密解密,秘钥空间小,可直接爆破。

例题
1
2
3
4
5
6
7
8
9
10
11
12
def caesar_encrypt(m, k):
r = ""
for i in m:
r += chr((ord(i) + k) % 128)
return r


from secret import m, k

print caesar_encrypt(m, k).encode("base64")

# output:bXNobgJyaHB6aHRwdGgE

解法为爆破。

1
2
3
4
5
6
7
8
9
10
11
# -*-coding:utf-8-*
def caesar_encrypt(m, k):
r = ""
for i in m:
r += chr((ord(i) + k) % 128)
return r


m = "bXNobgJyaHB6aHRwdGgE"
for i in range(1, 129):
print caesar_encrypt(m.decode("base64"), i)
埃特巴什码

通过将字母表的位置完全镜面对称后获得字母的替代表进行加密,攻击方法为将其替代回去。

培根密码

AB表达两种字体,五个一组。类似二进制。

猪圈密码

图形替代密码,不做赘述。

仿射密码

依据公式c=am+b mod n来生成仿射密码的替代表。

  • m为明文对应字母得到的数字。
  • n为字符数量。
  • c为密文。
  • a、b为秘钥。

解密方法为求a关于n的逆元,公式m = modinv(a)(c-b) mod n,攻击方法有爆破、词频统计和已知明文攻击【如果知道一对(m,c),那么知道ab是简单的。

多表替代

维吉尼亚密码

秘钥不是固定不变的,随位置产生而改变,若密文为LOVE,则四个为一组进行循环加密。

词频统计

依赖在英语语言中字母的使用频率进行分析。

单表替换:统计所有字母频率,替换频率最近的。

多表替换:抽取使用相同替换表的所有密文,然后使用单表替换。

TWCTF2016 vigenere

先进行base64编码后维吉尼亚加密。

卡西斯基实验

若连续三个相同字母如ABC在密文中重复出现会是什么原因。

不同明文,不同秘钥:碰巧

相同明文,相同秘钥:如the经常连续出现,出现的间距的秘钥长度的倍数

解密方式为寻找重复出现的密文,求间距最大公约数。

现代密码

分组密码

分组密码【Block Cipher的数学模型是将明文消息编码表示后的数字【简称明文数字,划分成长度为n的组,每组分别在密钥的控制下变换成等长的密文,常见的有DESAES这两大对称加密算法。

分组密码通常是按固定规模将明文分组,对每组均使用一个固定的加密变换来进行运算。

常见出题思路

普通题目:CBC模式攻击、Feistel结构的简单攻击方法。

困难题目:需计算差分、积分、代数、MITM等。

ECB模式

相同的明文分组会被转换为相同的密文分组,一组16个字节,当最后一个明文分组的内容小于分组长度时,需要用一些特定的数据进行填充。

我们可以将其理解为是一个巨大的明文分组→密文分组的对应表,因此ECB模式也称为电子密码本模式。

因此,如果明文中存在多个相同的明文分组,则这些明文分组最终都将被转换为相同的密文分组。这样一来,只要观察一下密文,就可以知道明文存在怎样的重复组合,并可以以此为线索来破译密码,因此ECB模式存在一定风险,且攻击者无需破译密码就能操纵明文【交换密文块来颠倒语意。

CBC模式

CBC模式的加密方式为分组后,第一组和作为偏移量的随机字符串异或后被另一个作为秘钥的随机字符串加密,得到的密文用作下一组明文加密前的异或字符串操作,因此其优于ECB模式的一点是不会被交换密文的方式颠倒语意。

CBC比特翻转攻击

已知明文攻击,可以通过修改密文,来使密文解密出来的特定位置的字符变成我们想要的字符,但会使得前序密文无意义。

只需将上一组对应位置的字符与已知对应位置的明文和目标解密明文分别异或一次即可。

例题
1
2
3
4
5
6
7
8
9
10
11
# coding=utf-8
from Crypto.Cipher import AES

m = "hahahahahahahaha=1;admin=0;uid=1"
key = "1234567890abcdef"
iv = "fedcba0987654321"
cipher = AES.new(key, AES.MODE_CBC, iv)
c = cipher.encrypt(m)
print c.encode("hex")

# 49a98685a527bdfa4077c400963a4e3c9effb4148566f10bce9e07ccbb731896

那么根据公式。

1
2
3
4
5
6
7

Decrypt(Cipher[2][i]) = Cipher[1][i] ^ Plain[2][i]
Plain[2][i] == 0
Plain[2][i] → x

Plain[2][i] ^ x = 0 ^ x = x
Decrypt(Cipher[2][i]) = Cipher[1][i] ^ Plain[2][i] ^ x

因此根据上述公式构造Payload来进行CBC翻转攻击使得admin=1

1
2
3
4
5
6
7
8
# coding=utf-8

cipher = "49a98685a527bdfa4077c400963a4e3c9effb4148566f10bce9e07ccbb731896".decode('hex')
fake_cipher = (cipher[:9] + chr(ord(cipher[9]) ^ 0 ^ 1) + cipher[10:])

print cipher.decrypt(fake_cipher)

# |�nq��1�C?A��=1;admin=1;uid=1

可见admin已经成功更改为1,但前序明文无意义了。

例题

Jarvis OJ的一题xbitf

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
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/xbitf/flag","r").read()

from Crypto.Cipher import AES
import os

def aes_cbc(key,iv,m):
handler=AES.new(key,AES.MODE_CBC,iv)
return handler.encrypt(m).encode("hex")
def aes_cbc_dec(key,iv,c):
handler=AES.new(key,AES.MODE_CBC,iv)
return handler.decrypt(c.decode("hex"))

key=os.urandom(16)
iv=os.urandom(16)
session=os.urandom(8)
token="session="+session.encode("hex")+";admin=0"
checksum=aes_cbc(key,iv,token)
print token+";checksum="+checksum
for i in range(10):
token_rcv=raw_input("token:")
if token_rcv.split("admin=")[1][0]=='1' and token_rcv.split("session=")[1][0:16].decode("hex")==session:
c_rcv=token_rcv.split("checksum=")[1].strip()
m_rcv=aes_cbc_dec(key,iv,c_rcv)
print m_rcv
if m_rcv.split("admin=")[1][0]=='1':
print flag

# session=762fda4eacfb8321;admin=0;checksum=77df89f8da92cbde1baa5d34a9e9e791c763cf14ef63dc3c32ce1e757603de30

那么依题意。

1
2
3
4
5
6
7
8
# coding=utf-8
token = "session=762fda4eacfb8321;admin=0;checksum=77df89f8da92cbde1baa5d34a9e9e791c763cf14ef63dc3c32ce1e757603de30"

cipher = token.split("checksum=")[1].strip().decode('hex')
fake_cipher = (cipher[:15] + chr(ord(cipher[15]) ^ 0 ^ 1) + cipher[16:])
print "session=762fda4eacfb8321;admin=1;checksum=" + fake_cipher.encode('hex')

# session=762fda4eacfb8321;admin=1;checksum=77df89f8da92cbde1baa5d34a9e9e790c763cf14ef63dc3c32ce1e757603de30

就好了。

1
2
3
4
session=762fda4eacfb8321;admin=0;checksum=77df89f8da92cbde1baa5d34a9e9e791c763cf14ef63dc3c32ce1e757603de30
token:session=762fda4eacfb8321;admin=1;checksum=77df89f8da92cbde1baa5d34a9e9e790c763cf14ef63dc3c32ce1e757603de30
�l!_��zv�%��acfb8321;admin=1
flag{xman_bit_flip_112233}
CBC选择密文攻击

攻击目的是恢复出偏移量IV,当输入密文可控且有解密后明文返回时可解。

明文每次加密前都会和IV异或,IV每次会更新为上一组的密文。

则满足上述条件时,使得cipher[0]==cipher[1]IV可解,公式如下。

1
2
3
4
5
6

Decrypt(Cipher[0]) ^ IV = Plain[0]
Decrypt(Cipher[1]) ^ Cipher[0] = Plain[1]
Cipher[0] == Cipher[1]

IV = Plain[0] ^ Plain[1] ^ Cipher[0]
例题

Jarvis OJ的一题xcc

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
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/xcc/flag","r").read()

from Crypto.Cipher import AES
import os

def aes_cbc(key,iv,m):
handler=AES.new(key,AES.MODE_CBC,iv)
return handler.encrypt(m).encode("hex")
def aes_cbc_dec(key,iv,c):
handler=AES.new(key,AES.MODE_CBC,iv)
return handler.decrypt(c.decode("hex"))

key=os.urandom(16)
iv=flag

for i in range(10):
c=raw_input("c:")
print aes_cbc_dec(key,iv,c).encode("hex")

此时,输入密文可控,且有解密后的明文返回。

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

def cbc_chosen_cipher_recover_iv(cc,mm):
assert cc[0:16]==cc[16:32]
def _xorstr(a, b):
s = ""
for i in range(16):
s += chr(ord(a[i]) ^ ord(b[i]))
return s
p0=mm[0:16]
p1=mm[16:32]
return _xorstr(_xorstr(p0, p1), cc[0:16])

target=("47.97.215.88",10001)
io=zio(target)
io.read_until("c:")
io.writeline(("1"*32).encode("hex"))
mm=io.readline().strip().decode("hex")
iv=cbc_chosen_cipher_recover_iv("1"*32,mm)
print iv
io.interact()
Padding Oracle Attack

满足的攻击条件:

  • 加密时采用了PKCS5的填充【填充的数值是填充的字符个数。
  • 攻击者可以和服务器进行交互,可以提交密文,服务器会以某种返回信息 告知客户端的Padding是否正常。

可在不清楚KeyIV的时候解密任意密文。

例如对Cipher[1]解密,Plain[1] = Decrypt(Cipher[1]) ^ Cipher[0]

Cipher[1]前拼接一个伪造的Cipher[0],用于当做Cipher[1]的初始向量,发送Cipher解密。

爆破Cipher[1]解密后Plain[0]的最后一位流程如下:

构造Cipher[0]最后一位为X ^ 1,发送并观察Padding的结果是否正确,错误返回1

Feistel 密码结构

Feistel密码结构是用于分组密码中的一种对称结构。

一组明文分成二组,LR

L使用K[i]作为秘钥经过F()加密,再和R异或后作为下一轮的RR不变作为下一轮的L

每一轮都是可推理的,且每个的内容均为L ^ R ^ K

L R
R R^L^K1
R^L^K1 L^K1^K2
L^K1^K2 R^K2^K3
R^K2^K3 R^L^K1^K3^K4
R^L^K1^K3^K4 L^K1^K2^K4^K5
L^K1^K2^K4^K5 R^K2^K3^K5^K6
R^K2^K3^K5^K6 R^L^K1^K3^K4^K6^K7
R^KY L^R^KX

如果F()方法是线性的,即可进行已知明文攻击。

只要知道一组明密文对,就可以解密所有密文。

例题

Jarvis OJ的一题xfz

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
import os
def xor(a,b):
assert len(a)==len(b)
c=""
for i in range(len(a)):
c+=chr(ord(a[i])^ord(b[i]))
return c
def round(M,K):
L=M[0:27]
R=M[27:54]
new_l=R
new_r=xor(xor(R,L),K)
return new_l+new_r
def fez(m,K):
for i in K:
m=round(m,i)
return m

K=[]
for i in range(7):
K.append(os.urandom(27))
m=open("flag","rb").read()
assert len(m)<54
m+=os.urandom(54-len(m))

test=os.urandom(54)
print test.encode("hex")
print fez(test,K).encode("hex")
print fez(m,K).encode("hex")

print xor(test[:27],m[:27]).encode("hex")

# 5ca045c3402219b13eee964e650fefb438d6bcaf1081cf86b50ebcade518e4c5c4b5c8567492405e26f1bcd47015ba86947600f4fb3a
# e8cb1fadcb6c4be6fe4a9a67e1507833c0db402e6b1eb91d3377f16fd805f15b1116443bb359245fab6251db8dc382edef95a89b3207
# 7c586f783cc0cd40de53759c7ac1d22d719a654f16ff96b76afa8fc187518097f9ec2051214cced65046900d2c6c7adfbe45e21dd8a1

根据如上加密过程,推得公式如下。

1
2
3
4
5
6
7
test_K[:27] = test[-27:] ^ K2 ^ K3 ^ K5 ^ K6
m_K[:27] = m[-27:] ^ K2 ^ K3 ^ K5 ^ K6
m[-27:] = test[-27:] ^ test_k[:27] ^ m_K[:27]

test_K[-27:] = test[:27] ^ test[-27:] ^ K1 ^ K3 ^ K4 ^ K6 ^ K7
m_K[-27:] = m[:27] ^ m[-27:] ^ K1 ^ K3 ^ K4 ^ K6 ^ K7
m[:27] = test_K[-27:] ^ test[:27] ^ test[-27:] ^ m_K[-27:] ^ m[-27:]

根据公式写出脚本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
test = "d8dc053d372d0690194553d7ffbed36750703f417bcb989f98b181a07203ec4807e239df7f4dd9f983cc8d5081b8f7673e7b9ea32b51".decode("hex")
test_K = "f55847d90055888b420b5e3921f3697a63fe88e6c6541a8e53e58cd89e1702c45498b45b57516feb01925de8fa9e359ce226ed1aa5be".decode("hex")
m_K = "6c5c2c047a3a59dceb196ebad9dd9e98055e3f0325f0891e783010ff2a1885f2702a009f655e649bf4d7b3811c20a75bbc1d84c3a8c7".decode("hex")


def xor(a, b):
assert len(a) == len(b)
c = ""
for i in range(len(a)):
c += chr(ord(a[i]) ^ ord(b[i]))
return c


m_back = xor(xor(test_K[:27], m_K[:27]), test[-27:])

m_front = xor(xor(xor(test_K[-27:], test[:27]), xor(test[-27:], m_K[-27:])), m_back)

print m_front + m_back
# flag{festel_weak_666_10fjid9vh12h3nvm}Z�;o6!������

更多高级的攻击方式

  • 差分攻击
  • 积分攻击
  • MITM
  • 代数攻击

序列密码

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

随机数

不存在真正的随机数。

伪随机数发生器特性

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

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.RandomC中的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

Rubyrand()PythonrandomPHPmt_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先在栈上初始化生成624state,后调用php_mt_reload()方法重新生成624state,接着执行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()

公钥密码

公钥密码【Public-key cryptography,也称非对称密码学,是密码学的一种算法,它需要两个密钥,一个是公开密钥,另一个是私有密钥;一个用作加密,另一个则用作解密。使用其中一个密钥把明文加密后所得的密文,只能用相对应的另一个密钥才能解密得到原本的明文;甚至连最初用来加密的密钥也不能用作解密。由于加密和解密需要两个不同的密钥,故被称为非对称加密;不同于加密和解密都使用同一个密钥的对称加密。虽然两个密钥在数学上相关,但如果知道了其中一个,并不能凭此计算出另外一个来源请求;因此其中一个可以公开,称为公钥,任意向外发布;不公开的密钥为私钥,必须由用户自行严格秘密保管,绝不透过任何途径向任何人提供,也不会透露给被信任的要通信的另一方。

RSA

原理
1
2
3
4
Alice: 随机选择两个不同大质数p和q,计算n=p×q,根据欧拉函数,可以求出r=φ(N)=φ(p)φ(q)=(p-1)(q-1),然后选择一个小于r的正整数e,使得e与r互质,后求得e关于r的模反元素d。这时,(N,e)是公钥,(N,d)是私钥,接着把公钥发送给Bob。
Bob: 使用公钥(N,e)对明文m进行加密【太长则分组后得到c发送给alice,c=pow(m,e,n)。
Alice: 使用私钥(N,d)对c进行解密,m=(c^d)mod(n),e*d=(1)mod(f(n)),modinv(e,(p-1)*(q-1)),m=pow(c,d,n)。
cat: 在这个过程中,第三方窃听者只能获取到c,e,n,无法解出明文m。
直接模数分解

直接模数分解首当其冲的一个便是数学难题:分解大素数N

暴力分解

N的长度较小可直接分解【长度小于512bit

例题

Jarvis OJ的一题Medium RSA,给了一个公钥和一个密文。

1
2
3
4
5
6
7
8
openssl rsa -in pubkey.pem -pubin -noout -text -modulus
Public-Key: (256 bit)
Modulus:
00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD

N很小,可以直接分解,使用CTF-RSA-Tool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
python solve.py --verbose --private -N 87924348264132406875276140514499937145050893665602592992418171647042491658461 -e 65537
DEBUG: factor N: try past ctf primes
DEBUG: factor N: try Gimmicky Primes method
DEBUG: factor N: try Wiener's attack
DEBUG: Starting new HTTP connection (1): www.factordb.com:80
DEBUG: http://www.factordb.com:80 "GET /index.php?query=87924348264132406875276140514499937145050893665602592992418171647042491658461 HTTP/1.1" 200 1021
DEBUG: http://www.factordb.com:80 "GET /index.php?id=1100000000836631227 HTTP/1.1" 200 899
DEBUG: http://www.factordb.com:80 "GET /index.php?id=1100000000836631226 HTTP/1.1" 200 898
DEBUG: d = 0x1806799bd44ce649122b78b43060c786f8b77fb1593e0842da063ba0d8728bf1L
INFO:
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
d=10866948760844599168252082612378495977388271279679231539839049698621994994673

INFO: private key:
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEAwmNq5cPY5D/7l6sJAo8arGwL9s09cOvKKBv/6X++MN0CAwEAAQIg
GAZ5m9RM5kkSK3i0MGDHhvi3f7FZPghC2gY7oNhyi/ECEQDO+7LPfhipjr7cNuPn
w7ArAhEA8Gwo6RyJIrnCNuI1YMCXFwIRAJulRkclqWIHx5pNZIAp9VUCEGjeJLIZ
ek+lSut5m+LJ3p0CEDRBEd7C622/wt1+58xOIfE=
-----END RSA PRIVATE KEY-----

然后解出flag

1
2
3
4
5
6
7
8
9
10
import libnum
from Crypto.Util.number import long_to_bytes

n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
d = 10866948760844599168252082612378495977388271279679231539839049698621994994673
c = open('flag.enc').read().encode('hex')
c = int(c, 16)
m = pow(c, d, n)
print long_to_bytes(m)
# ���&[�PCTF{256b_i5_m3dium}
PQ选择不当

NPQ选择存在的问题【过于接近/差距过大/光滑。

  • |p-q|很大:当p-q很大时,一定存在某一个参数较小,这里我们假设为p,那么我们可以通过穷举的方法对模数进行试除,从而分解模数,得到保密参数与明文信息。基本来说,不怎么可行。

  • 费马分解和Pollard_rho分解

  • Yafu分解

  • -1光滑

  • P+1光滑【2017 SECCON very smooth

  • 一些特定的N【在factordb上测试一下

背包

椭圆曲线

杂凑函数