关于微信公众号

​ 周末的TQLCTF，出题人确实TQL，这篇主要是想详细分析一下密码学赛题中的OTP一题，末尾也会简单过一下另外两道题，一道是非预期，另一道分析起来还是值得再开一篇，但是解起来还是比较方便（因为有现成的板子）。

import os
import random
import secrets
import string

#from secret import flag, secret_1, secret_2, flag_token
flag='TQLCTF{eee67011-f2a0-4f5f-ae48-1de28c76939x}'


# ========================================================================


class InvalidChar(Exception):
    pass


class DangerousToken(Exception):
    pass


valid_char = [ord(x) for x in string.digits +
              string.ascii_letters + string.punctuation]


def check_valid(s: bytes):
    r = list(map(lambda x: x in valid_char, s))
    if False in r:
        raise InvalidChar(r.index(False))


def getrandbits(token: bytes, k: int) -> int:
    random.seed(token)
    return random.getrandbits(k)


def bytes_xor_int(s: bytes, r: int, length: int) -> bytes:
    s = int.from_bytes(s, 'little')
    return (s ^ r).to_bytes(length, 'little')


def __byte_shuffle(s: int) -> int:
    bits = list(bin(s)[2:].zfill(8))
    random.shuffle(bits)
    return int(''.join(bits), 2)


def __byte_shuffle_re(s: int) -> int:
    s = bin(s)[2:].zfill(8)
    idx = list(range(8))
    random.shuffle(idx)
    s = ''.join([s[idx.index(i)] for i in range(8)])
    return int(s, 2)


def bits_shuffle(s: bytes) -> bytes:
    s = bytearray(s)
    for i in range(len(s)):
        s[i] = __byte_shuffle(s[i])
    return bytes(s)


def bits_shuffle_re(s: bytes) -> bytes:
    s = bytearray(s)
    for i in range(len(s)):
        s[i] = __byte_shuffle_re(s[i])
    return bytes(s)


def bytes_shuffle(token: bytes, s: bytes) -> bytes:
    random.seed(token)
    s = bytearray(s)
    random.shuffle(s)
    return bytes(s)


def bytes_shuffle_re(token: bytes, s: bytes) -> bytes:
    random.seed(token)
    idx = list(range(len(s)))
    random.shuffle(idx)
    r = bytearray(len(s))
    for i in range(len(s)):
        r[idx[i]] = s[i]
    return bytes(r)


def encrypt(s: str, token=(None, None)):
    if token[0] is None or token[1] is None:
        token = (secrets.randbits(32).to_bytes(4, 'little'),
                 secrets.randbits(32).to_bytes(4, 'little'))
    s: bytes = s.encode()

    check_valid(s)

    r = getrandbits(token[0]+secret_1, 8*len(s))
    s = bytes_xor_int(s, r, len(s))
    s = bits_shuffle(s)
    s += token[0]

    s = bytes_shuffle(token[1]+secret_2, s)
    s += token[1]
    s = s.hex()

    return s


def decrypt(s: str):
    s: bytes = bytes.fromhex(s)

    s, token_1 = s[:-4], s[-4:]
    s = bytes_shuffle_re(token_1+secret_2, s)

    s, token_0 = s[:-4], s[-4:]
    r = getrandbits(token_0+secret_1, 8*len(s))
    s = bits_shuffle_re(s)
    s = bytes_xor_int(s, r, len(s))

    check_valid(s)

    s = s.decode()
    if (len(s) == len(flag)) + (token_0 == flag_token[0]) + (token_1 == flag_token[1]) >= 2:
        raise DangerousToken
    return s


def encrypt_flag():
    flag_enc = encrypt(flag, flag_token)
    print(f'flag: {flag_enc}')


def rebuild():
    global secret_1, secret_2, flag_token
    secret_1 = os.urandom(64)
    secret_2 = os.urandom(64)
    flag_token = (os.urandom(4), os.urandom(4))


def choose_mode():
    print('Choose function:')
    print('0: encrypt')
    print('1: decrypt')
    print('2: rebuild')
    mode = int(input('> '))
    assert 0 <= mode <= 2
    return mode


if __name__ == '__main__':
    print('Welcome to Nano OTP Box!')
    rebuild()
    encrypt_flag()

    while True:
        try:
            mode = choose_mode()
            if mode == 0:
                print('Please input original message.')
                msg = input('> ')
                print('encrypted message:', encrypt(msg))
            elif mode == 1:
                print('Please input encrypted message.')
                msg = input('> ')
                print('original message:', decrypt(msg))
            elif mode == 2:
                rebuild()
                encrypt_flag()
        except InvalidChar as e:
            print('The original message contains invalid characters: pos', e)
        except DangerousToken:
            print('The encrypted message contains dangerous token')

题目流程

加密：需要一共四个参数，分别是secret1，secre2，token0，token1，其中secret为64bytes，token为4bytes

1. 首先以secre1与token0的拼接作为随机数种子初始化一个随机数生成器
2. 利用上述随机数生成器 getrandbits 生成随机数r，与明文异或，小端序
3. 然后对每一个字节进行一个bit级别的乱序（还是用的上面的随机数生成器）
4. 将输出拼接上token0
5. 然后以secre2与token1的拼接作为随机数种子初始化一个随机数生成器
6. 利用上述随机数生成器对整个字符串进行一个bytes级别的乱序
7. 最后拼接上token1，输出密文

解密：

1. 将输入密文的后四个字节取出作为token1
2. 以secre2与token1的拼接作为随机数种子初始化一个随机数生成器
3. 利用上述随机数生成器对整个字符串进行一个bytes级别的乱序恢复
4. 将输出的后四个字节取出作为token2
5. 以secre1与token0的拼接作为随机数种子初始化一个随机数生成器
6. 然后对每一个字节进行一个bit级别的乱序恢复
7. 继续利用上述随机数生成器 getrandbits 生成随机数r，与step6的输出异或，小端序
8. 对上述输出进行检查，如果有一个非法字符（定义了可见字符集为合法字符），则会报错，并输出该字符在字符串中的位置
9. 如果明文的长度与flag的长度相等，token0与flag_token0相等，token1与flag_token1相等，三者满足二，则会报错，并返回dangerous token
10. 通过检查，则返回解密后的明文字符串。

题目分析

题目每次加密都对明文进行一次的异或，然后对每个字节进行一个bit级别的乱序，很像DES里的S盒，盒的数量就是字节数，最后进行一个byte级别的乱序，类似DES里的P盒。OTP体现在token0和token1决定了随机方式，只要token不同，那么每次的随机方式则不同。题目也做了限制，用于flag加密的token0和token1也不允许同时用于一条密文的解密。

解题思路

对于题目限制的三个条件，明文长度，token0，token1，其中token1我们是知道的（就在密文后面），但token1只对应一种字节级别的乱序方式，如果我们能够获取乱序方式，token1是可以被代替的。而token0与随机数生成有关，几乎是不可替代的，想要解密flag，这个地方不能碰。那么我们字符串的长度，我们就需要取舍了，少一位，或者多一位。

step1 获取token1对应乱序规则

​ 那么如何替换token1呢，也就是找到token1所对用的乱序方式。我们注意到题目提供的一个check，如果有非法字符，他会报错，并给出错误字节的位置，那么切入点就在这里了。只有token1与字节位置相关，试想一下，如果我们把flag的密文传回去，那肯定不会报错，但如果我们改了flag密文的一个字节呢？比如我们改了第一个字节的第二个bit，那么在解密的时候，打个比方在byte乱序恢复的时候第一个字节到了第八个字节，然后再进行bit乱序恢复的时候第二个bit到了第一个bit，然后进行一个随机数r的异或，显然，如果一切正常，第八个字节的第一个bit肯定是0，但是由于我们对它进行了一次修改，此时他肯定是1，那么就会报错，报明文的第八个字符是非法的，此时我们即获得了一条映射关系：第八个字节会被调到第一个字节。如下图所示

可以明确的是，对每个字节的每个bit进行修改，八次修改里面，至少会爆一次错，因为如果改到了最高位，字符必然是非法的。如果有多次报错，那么报错的位置也必然是同一处。但我们手里的密文，除了最后四个字节是token1，在前面的48（一共有52个字符）字节中，还有四个是属于token0的，如果我们改到了token0的字节，八次修改，极大概率应该是都会报错，而且八次报错中大概率会出现不一样的错误位置，因为token0是与异或随机数r相关的，动了token0，那么随机数r会整个被改动，会影响到所有字节。

step2 用token1’ 替换token1

由此我们进行48*8次交互就能够确定token1所对应的乱序规则，并且能确定token0所在的位置，但是我们不知道他们之间的相对顺序。但好在只有4字节，只需要$A_4^4 = 24$ 次尝试即可。有了映射规则后，我们就能够自己把flag的顺序调回去。然后我们给它一个新的token1’，并给他以token1’的规则进行乱序。这样服务器那边收到密文后，再以token1’的规则恢复乱序，也就还是正常的flag的顺序了。至于token1’的获取和token1’规则的获取，我们只需要进行一次正常加解密，再利用上述方式走一遍就可以了。

step3 枚举token2进行解密获取flag

但是token0不能动，我们得动一下字符的长度，这里我选择加一位。即我们再恢复了flag的顺序后，再在末尾加一个字符，再加上token0（24种中的一种）。然后去向服务申请45字节（flag是44个字节）消息的加密，获取相应的token1’，求出相应的token1’ 的乱序规则，然后将其应用到我们恢复好顺序的flag上。只要我们token0顺序对了，然后拿去给服务器解密，应该就是能成功，的叭？

ps:

这里还有一个问题，就是随机数r的选取，他利用的getrandbit，这个随机数生成的方式是4个字节一组，先生成的数放小端，最后不满四字节的部分取大端，所以这里如果少取1字节，那么解密的时候，就算给了flag用的token0和token1，那么最后随机数异或的时候也会导致最后三字节因为错位异或而导致解密处别的字符，

如上图所示，flag加密的时候是44个字节，这里异或的时候用的是小端序，所以最后四个字节 ” } z y x “，会和 “ a b c d “进行异或，但如果解密的时候，你少传了一个字符，把最后一个 ‘}’ 给丢掉了，那么他在异或的时候，会是” z y x” 和 “a b c” 异或，就这么错位了。所以解密的时候就会寄，如果运气好可见的话，你还能看到flag的前面40个字节，运气不好就会报字符非法了（算每一个字符合法概率为1/2，都合法只有1/8的概率）。（虽然后续会有补救的方法，但确实太过于麻烦）所以我们这里选5字节，多出的一字节要是解密失败——报位置44处非法字符，那说明我们的token0顺序对了，我们换一个字节继续试就好了。

解题流程与脚本编写

由于复现的时候场景已经关闭，这里直接利用源代码进行本地测试。

设置的flag为 ‘TQLCTF{eee67011-f2a0-4f5f-ae48-1de28c76939a}’

secret_1, secret_2, flag_token参数都没有设置，直接开局调用一个rebuild

from Crypto.Util.number import *
from TQLOPT import *

flag_enc = encrypt(flag, flag_token)
c = long_to_bytes(int(flag_enc,16))
table_from_to={}
token1to=[]
c = list(c)
# 异或flag_enc的各个bit以得到token1所对应的乱序规则
for index in range(len(c)-4):	# 最后四个字节是token1
    times = 0	#记录invalid次数
    for i in range(8):
        tempc = c.copy()
        tempc[index] ^= 1 << i
        tempstr = ''.join(chr(i) for i in tempc)
        tempbytes = tempstr.encode('latin1')
        templong = bytes_to_long(tempbytes)
        temphex = hex(templong)[2:].rjust(104,'0')	# 这里只是想把异或c的一个bit然转成hex而已，绕了一圈属于是
        try:
            decrypt(temphex)
        except InvalidChar as e:	# 由于是本地调试，我直接捕获异常了，如果是远程交互，可能还需要写一个正则匹配一下返回值
            fr0m = str(e)
            times += 1
        except DangerousToken:
            pass
    if times == 8:	# 如果八次全错，说明我们改到token0了，记录下位置
        token1to.append(index)
    else:
        table_from_to[fr0m] = index
# 至此，我们获取到了密文中token0的位置，已经相应的token1所对应的映射关系 table_from_to
# 故技重施，加密一个45字节的msg，获取token1' 已经其对应的映射关系 table11_to_from，这里反正记是方便后面的调用

msg = 'a'*45
msg_enc = encrypt(msg)
token11 = msg_enc[-8:]
table11_to_from={}
token11to=[]

c = long_to_bytes(int(msg_enc,16))
c = list(c)
for index in range(len(c)-4):
    times = 0
    for i in range(8):
        tempc = c.copy()
        tempc[index] ^= 1 << i
        tempstr = ''.join(chr(i) for i in tempc)
        tempbytes = tempstr.encode('latin1')
        templong = bytes_to_long(tempbytes)
        temphex = hex(templong)[2:].rjust((45+8)*2,'0')
        try:
            decrypt(temphex)
        except InvalidChar as e:
            fr0m = str(e)
            times += 1
        except DangerousToken:
            pass
    if times == 8:
        token11to.append(index)
    else:
        table11_to_from[index] = fr0m
# 现在我们按照table_from_to，把flag的顺序调回来，

c = long_to_bytes(int(flag_enc,16)).decode('latin1')
rec = []
for i in range(52-8):
	rec += c[table_from_to[str(i)]]
token0 = ''.join(c[token1to[i]] for i in range(4))


from itertools import permutations
for each in list(permutations(token0,4)):
    token00 = list(each)
    rectmp = rec+['0'] + token00	#然后加上一个字节，加上24种token0，

    rec_s = ""
    token00index=0
    for i in range(53-4):
        if i in table11_to_from.keys():
            rec_s += rectmp[int(table11_to_from[i])]	# 按照table11_to_from乱序,剩下四个空用token0去补
        else:
            rec_s += token00[token00index]
            token00index += 1
        tempbytes = rec_s.encode('latin1')
        templong = bytes_to_long(tempbytes)
        temphex = hex(templong)[2:].rjust((45+4)*2,'0')	
        temphex += token11	#加上token1'，再拿去解密
    try:
        Token0=0
        if 'TQLCTF' in decrypt(temphex):
            print(decrypt(temphex))
            exit()	# 运气好一步到位
    except InvalidChar as e:
        if str(e) == '44':
       		Token0 = token00	#如果44出错说明token0对了，去换字节就好
        	break
            
if not Token0:	#实测下来发现就算token0对了，它解密后最开头的四个字节还是会异或出错，这就不是很清楚原因了，直接再来一遍好了。
    print("Try again")
    exit()
    
table = list(string.digits + string.ascii_letters + string.punctuation)

for each in table:
    rectmp = rec+[each] + Token0    #	故技重施2，换字节，直到最后一个异或完是可打印字符
    rec_s = ""
    token00index=0
    for i in range(53-4):
        if i in table11_to_from.keys():
            rec_s += rectmp[int(table11_to_from[i])]    # 按照table11_to_from乱序,剩下四个空用token0去补
        else:
            rec_s += Token0[token00index]
            token00index += 1
        tempbytes = rec_s.encode('latin1')
        templong = bytes_to_long(tempbytes)
        temphex = hex(templong)[2:].rjust((45+4)*2,'0') 
        temphex += token11  #加上token1'，再拿去解密
    try:
        if 'TQLCTF' in decrypt(temphex):
            print(decrypt(temphex))
            break
    except Exception as e:
        pass

本地跑跑还是快的。远程多试几次应该也还好。

Signature

看了半天，觉得熟悉，但是还是不知道是什么签名系统。后来才知道这似乎就是GGH的签名系统，以前只知道GGH的加密。。有非预期，直接对公钥pk进行规约就能当私钥用：

sk = pk.BKZ(block_size = 20)
v = hash_msg("")
e = signature(sk,v)

或者用BKZ求v的cvp

hardrsa

涉及二元copper，和MRCTF2021 的 strangeCRT有一点点区别，这里的dp比较大，但是用MRCTF2021 官方的wp 的脚本，稍微改改参数，还是能用。

beta = 0.233
delta = 0.226
amplification = 1024
alpha = 0.9987

modulus = e
mm = 5
ss = 0
tt = 5

Xp = int(2 * N ** (alpha + beta + delta  - 1))
Yp = int(N**beta)
Yq = int(2 * N ** (1 - beta) )

#下面求G basis的时候，取个三组，会快些
I = ideal(all_pol[:3])

就是改了一下bound和格子，参考 New_attacks_on_RSA_with_small_secret_CRT-exponents

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com