BLOG

我想成为二进制高手！

虽然不确定这个学了对二进制有没有用，但学校也有这个课，就开始看了。

第一章

编译器（complier）：将源语言翻译成目标语言，并可以报告错误的一个程序。

从源程序形成可执行文件，需要经过预处理器（preprocessor），再通过编译器产生汇编语言程序，由汇编器（assmbler）处理，生成可重定位的机器代码，连接器（linker）解决内存地址问题，再由加载器（loader）统一执行。

编译器结构和步骤：

两个部分：分析（analysis）和综合（synthesis），也分别称为编译器的前端（front end）和后端（back end）。

步骤：

• 词法分析（lexical analysis）或扫描（scanning），形成有意义词素（lexeme）。词法分析产生词法单元（token）作为输出：<token-name,attribute-value>。类似于一个 <属性 ，存储位置> （？瞎理解的）的东西。
• 语法分析（syntax analysis）或解析（parsing），常用语法树（syntax tree）。类似于表达式求值这种，当然肯定复杂很多。
• 语义分析（semantic analysis），检查源程序是否符合源语言的规定，一个重要部分是类型检查（type checking），支持一些自动类型转换（coercion）。
• 中间代码生成，三地址代码（three-address code），用类似于汇编的指令组成，形如 or ， 是某种运算。
• 代码优化和代码生成。
• 符号表管理。符号表记录源程序中的各种变量名和属性相关信息，支持编译器查询/修改/存储每个名字的记录。
• 最后统一为一个趟（pass）。

然后是一些杂项，包括历史，应用，体系架构啥的。

程序语言设计基础

静态（static）和动态（dynamic）：取决于一个问题是否可以在编译时刻（complie time）决定，还是在运行时刻（run time）决定。

作用域（scope）：一个 变量 的声明 的作用域 指程序的一个区域 使得 这个区域的对 的使用 都指向这个声明。如果可以仅通过阅读程序可以确定作用域，则称这个语言使用静态作用域（static scope），或词法作用域（lexical scope），否则为动态作用域（dynamic scope）。

环境（environment）与状态（state）：环境是一个从名字到存储位置（变量，C 语言中的 “左值”）的映射，状态是一个位置到值的映射（C 语言中，即把左值映射为右值）。

参数传递机制：

实在参数：调用过程中使用的参数。

形式参数：过程定义中使用的参数。

• 值调用（call-by-value）：对参数求值或拷贝变量。需要注意的是，很多指针是值调用，也可以更改变量的值，比如传递数组名。
• 引用调用（call-by-reference）：传递实在参数的地址。类似于传指针，会修改参数的值。但是如果是表达式，调用前会先求值并存储到一个新位置上，此时修改不会影响数据。
• 名调用，今天不再采取，忽略（

别名（alias）：就是两个形式参数指向同一个位置，修改一样的东西。

第二章

上下文无关文法（context-free grammar)：

• 终结符号（terminal），就是前面的词法单元。
• 非终结符号（nonterminal），“语法变量“，表示一个终结符号串的集合。
• 产生式（production），包括一个产生式头部或左部的非终结符号，箭头，一个产生式体或右部的由上面两个符号组成的序列，表示产生式头代表的一种构造的书写形式。形如 ，其中 是一个非终结符号， 是串，表示 可以由 中的某种方式构造。
• 开始符号（starts symbol），指定的一个非终结符号。

推导：从开始符号串出发，不断将某个非终结符号替换为其某个产生式的体。

语言（language）：一个文法可以推导出的所有终结符号串的集合。

语法分析（parsing）：接受一个终结符号串，找出推导方法。如果不能，报告语法错误。

语法分析树（parse tree）：将推导过程表示成树形结构。构造方式为，如果使用产生式 ，则将 按序作为 的子节点接上去。

二义性（ambiguous）：一个文法有多个语法分析树可以生成同一个终结符号串。

运算符的结合（associate）：左结合是运算分量两侧都有运算符时，属于左边的运算符，右结合则属于右边。简单理解就是 等价于 还是 ， 是某个运算。

运算符的优先级：很熟悉的东西，不多说了（

后面一些内容在之后的章节会有具体讲述，所以 gugugu

day -?

貌似混进了 Nu1L，非常地高兴，非常的激动，感谢 hash_hash！好像还有机会线下参加今年 defcon quals，赢麻了！

和北京的高中同学们说了一声，有机会参观 tp 了！

day 0

五月三日，乡下人进京了，首都机场线很舒服啊。下午 check in 了 n1 订的豪华酒店，休息了一下去清华玩了，在清华和 xql 打牌，被打爆了，怎么回事呢，我要和世上的 xql 爆了！

清华环境还是好的，有个湖，有个湖意味着什么呢，意味着我们可以绕湖走一圈走出一个环，而有环就可以无限走，就可以散步了！

晚饭时间第一次见到 n1 的队员，非常社恐，只认识 shino，只能吃吃吃。有道北京特色菜，芥末白菜，非常的好，希望大家有机会都尝试一下 (x。

和 hash_hash 住一间，晚上打了 miniL，把 crypto ak 了。跟 hash_hash 讨论了一下题，学到许多，果然 n1 学长是真的强。

day 1

五月四日，早上八点开题，这次赛制对我来说也是第一次见，有 hot challenge 部分，就是在一个题有一血之后才放开下一个题；还有一个 live ctf 部分，在固定时间放出一道题，分数按时间递减，从一血出现是开始计算。

虽然但是，上来我们密码手没事干啊，好像全是 re 和 pwn 题。躺了一上午，吃午饭（外卖真好吃）。

下午又枯坐 3 h，突然来了个消息，说晚上 9 点第一场 live 是 crpyto，好评！但我又发现在这之前真没事，就润去北大了。见到老同学还是很激动的，听他们聊天，发现都在理财，真的很厉害！

北大有好几个湖，也可以有环无限走，非常地羡慕。

tp 景色风格感觉很体现学校风格。清华都是些大路，或者说是比较方正的那种；北大很多幽静的小路，也有很多比较古老的建筑。

晚上回来打 live，呃，怎么说呢，这个密码有点，太，大家都一眼秒了。唉，10 min 不到就下班了。

day 2

真躺尸吧。中途有个题有密码部分，但好像也是一个碰撞就能解决的。感觉我根本没有用，来北京真旅游了。

day 3

早上起来一看，大爹们打到了 rk4，真强啊。深感自己的无力，回去要狠狠学习二进制！

然后就回成都了，感觉首都机场不如天府，安检挺慢的，饮水机也很稀有的样子。

做了两道 medium 的分组密码，感觉算是练习了一下不太熟悉的东西。

cry

• task

  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

  #!/usr/bin/env python3 from Crypto.Util.number import bytes_to_long, long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES from secrets import randbelow from string import printable from os import getenv def encrypt(data, keys): if isinstance(data, str): data = data.encode() data = pad(data, 16) data += b"<<valid_secret>>" for k in keys: data = AES.new(k, AES.MODE_ECB).encrypt(data) return data def decrypt(data, keys): if isinstance(data, str): data = data.encode() for k in keys[::-1]: data = AES.new(k, AES.MODE_ECB).decrypt(data) if data[-16:] != b"<<valid_secret>>": return (f"Could not decrypt; invalid data: {data[:-16]}") return f"Decrypted data: {unpad(data[:-16], 16)}" def add(vault, keys, key, data): vault[key] = encrypt(data, keys) def get(vault, keys, key): return decrypt(vault.get(key, b""), keys) def generate_keys(): return [long_to_bytes(randbelow(2**9)).ljust(16) for _ in range(6)] def main(): vault = {} print("Welcome to the future of secret vaults") print("Here you can store all your secrets") admin_keys = generate_keys() user_keys = generate_keys() add(vault, admin_keys, "example", "nobody will be able to read this") add(vault, admin_keys, "FLAG", getenv("FLAG", "flag{fakeflagfakeflag}")) EVALUATION_PERIOD = 5 while 1: print(f"Vault menu: {EVALUATION_PERIOD} TESTING QUERIES LEFT") print(" 1) add value to vault") print(" 2) get value from vault") print(" 3) list available keys in the vault") option = int(input("option > ")) match option: case 1: key = input("key > ") text = input("text > ") assert all(i in printable for i in text) add(vault, user_keys, key, text) print(f"Successfully added the value ({vault[key]})") case 2: key = input("key > ") value = get(vault, user_keys, key) print(value) case 3: keys = [*vault] print(f"Available keys: {keys}") EVALUATION_PERIOD -= 1 if EVALUATION_PERIOD <= 0: print("You used your entire allowance. Goodbye") exit(0) if __name__ == "__main__": main()

  首先大概了解一下 task 在干啥。

  交互库有 admin_key 和 user_key，并且在 vault 里存了经 admin_key 加密的 example 和 flag，example 的明文我们是知道的。

  然后我们交互时：

  1. 用 user_key 加密自己给的一段 plain_text，存到 vault 里，并得到 cipher_text。

  2. 查询 vault 里某一键值对应 cipher_text 经 user_key 解密后的数据。

  3. 查询 vault 里有哪些键值。

  交互次数限制在 5 次。

  发现 admin_key 和 user_key 都是 级别，那么如果 meet in the middle 就是 ，是 级别，爆破可以接受。

  流程就是先用 1 操作随便加密一段，然后用这个密文和自己的明文去求 user_key。

  然后用 2 操作查询 example 密文经 user_key 解密后的假明文，再本地加密得到 example 明文经 admin_key 加密后的密文，用这两个求出 admin_key。

  再用一次 2 操作查询 flag 的密文，操作跟上面同理，key 都知道了，解密出 flag。

  只需要 3 次交互。

  这里 exp 实现上有地方要注意，最后我的实现是这样的：

  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

  def get_key(start,end): cipher=[] for i in range(2**9): cipher.append(AES.new(long_to_bytes(i).ljust(16),AES.MODE_ECB)) rev=[] for k0 in range(2**9): s0=cipher[k0].decrypt(end) for k1 in range(2**9): s1=cipher[k1].decrypt(s0) for k2 in range(2**9): rev.append(cipher[k2].decrypt(s1)) print("11111") for up in range(2**3): dic={} for k0 in range(2**6): s0=cipher[k0+up*2**6].encrypt(start) for k1 in range(2**9): s1=cipher[k1].encrypt(s0) for k2 in range(2**9): dic[cipher[k2].encrypt(s1)]=((k0+up*2**6)<<18)+(k1<<9)+k2 print(up) for k in range(2**27): if(dic.get(rev[k])!=None): return [dic[rev[k]],k] print(up) del dic

  具体来说在 meet in the middle 的时候，开 大小的 dictionary 并不现实，这样时空开销都不可接受（至少对大部分电脑来说是这样的），我这边最后选择将 拆成 组，分组进行和另一半 check，虽然增加了对另一半的访问次数，但 list 的访问肯定比 dictionary 快得多。

  然后还有个实现细节是 del dic ，因为 clear 操作是不释放内存的，所以我们必须将 dictionary 对象 delete 掉才能保证效率。

  我这里还有个想法是去弄两个 list sort 完再比较，但没实现，不知道会不会更快。

  大概一次要跑 15 分钟到 30 分钟，两次求 key 30 多分钟，还好。

desperate-intern

• task

  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 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201

  import secrets from Crypto.Util.Padding import pad, unpad FLAG = "fake_flag" # Initial permutation table IP = [58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4, 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8, 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3, 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7] # Final permutation table FP = [40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31, 38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29, 36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27, 34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25] # Expansion table E = [32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1] # Permutation table P = [16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10, 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25] # Permutation choice 1 table PC1 = [57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18, 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36, 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22, 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4] # Permutation choice 2 table PC2 = [14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2, 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32] # Number of rotations for each key shift_table = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1] # S-boxes (Customizable) # Each S-box is a 4x16 matrix # S-boxes taken from FIPS 46-3 Appendix 1 S_BOXES = [ [0, 1, 2, 3, 4, 5, 6, 7], [1, 2, 3, 4, 5, 6, 7, 8], [2, 3, 4, 5, 6, 7, 8, 9], [3, 4, 5, 6, 7, 8, 9, 10], [4, 5, 6, 7, 8, 9, 10, 11], [5, 6, 7, 8, 9, 10, 11, 12], [6, 7, 8, 9, 10, 11, 12, 13], [7, 8, 9, 10, 11, 12, 13, 14] ] def int_to_64b_bitstring(number): b = bin(number)[2:] if len(b) != 64: b = '0'*(64-len(b)) + b return b def permute(block, table): res = '' for i in table: res = res + block[i - 1] return res def rotate_left(key, bits): return key[bits:] + key[:bits] def generate_round_keys_enc(key): round_keys = [] key = permute(key, PC1) left_half = key[:28] right_half = key[28:] for round_num, shift_bits in enumerate(shift_table): left_half = rotate_left(left_half, shift_bits) right_half = rotate_left(right_half, shift_bits) round_key = permute(left_half + right_half, PC2) round_keys.append(round_key) return round_keys def xor_strings(s1, s2): return ''.join(str(int(a) ^ int(b)) for a, b in zip(s1, s2)) def substitute(expanded_half): output = '' for i in range(0, len(expanded_half), 6): chunk = expanded_half[i:i + 6] row = int(chunk[:3], 2) col = int(chunk[3:], 2) val = S_BOXES[row][col] output += format(val, '04b') return output def feistel_network(right_half, round_key): states = [] expanded_half = permute(right_half, E) states.append(expanded_half) xored_half = xor_strings(expanded_half, round_key) substituted_half = substitute(xored_half) permuted_half = permute(substituted_half, P) states.append(permuted_half) return states def des_encrypt(plain_text, key): cipher_text = '' round_keys = generate_round_keys_enc(key) plain_text = permute(plain_text, IP) left_half = plain_text[:32] right_half = plain_text[32:] for round_key in round_keys[:-1]: feistel_output = feistel_network(right_half, round_key) new_right_half = xor_strings(left_half, feistel_output[-1]) left_half = right_half right_half = new_right_half feistel_output = feistel_network(right_half, round_keys[-1]) new_right_half = xor_strings(left_half, feistel_output[-1]) left_half = right_half right_half = new_right_half cipher_text = permute(right_half + left_half, FP) return cipher_text, feistel_output def des_ecb_encrypt(plain_text, key): plain_text = pad(plain_text.encode(), 8) cipher_text = '' feistel_output = [] for i in range(0, len(plain_text), 8): block = int_to_64b_bitstring(int.from_bytes(plain_text[i:i + 8], 'big')) curr_cipher_text, curr_feistel_output = des_encrypt(block, key) cipher_text += curr_cipher_text feistel_output.append(curr_feistel_output) return cipher_text, feistel_output def main(): # keygen key = int_to_64b_bitstring(secrets.randbits(64)) # ciphertext counter counter = 16 # Example usage encrypt cipher_text_flag, feistel_output_flag = des_ecb_encrypt(FLAG, key) print('Welcome to your homemade supersafe encryption service made by Jack the Intern') print('Your credit for encrypted messages is at: ' + str(counter)) while True: command = input('Would you like to get the flag [1], encrypt a message yourself [2] or exit [3] \n>').strip() try: if command == "1": print("Flag = ", cipher_text_flag) print("Feistel output = ", feistel_output_flag) elif command == "2": if counter > 0: counter -= 1 data = input('Enter the plaintext you want to encrypt \n>') cipher_text, feistel_output = des_ecb_encrypt(data, key) print("Ciphertext = ", cipher_text) print("Feistel output = ", feistel_output) print("Your credit for encrypted messages is at: " + str(counter)) else: print("You have no credits for encrypted messages left.") elif command == "3": print("Exiting...") break else: print("Please enter a valid input") except: print("Something went wrong.") if __name__ == "__main__": main()

  还是先去了解交互库。

  这个实现了一个 des 加密，并且泄漏了最后一次 feistel_network 的结果。

  交互的操作为：

  1. 获取 cipher_text_flag 和 feistel_output_flag。

  2. 传一个 data 过去，获得 cipher_text 和 feistel_output，这个操作限制次数为 16。

  我感觉我做法可能非预期了，我只需要传 1 次明文。

  肯定得把 key 弄出来，重点关注 feistel_network 函数。

  1 2 3 4 5 6 7 8 9

  def feistel_network(right_half, round_key): states = [] expanded_half = permute(right_half, E) states.append(expanded_half) xored_half = xor_strings(expanded_half, round_key) substituted_half = substitute(xored_half) permuted_half = permute(substituted_half, P) states.append(permuted_half) return states

  然后我们相当于知道了 expanded_half 和 permuted_half，那么我们能求出 xored_half。

  这下如果我们能求 substitute 的逆过程的话，我们就能把 round_key 弄出来。

  那跟进 substitute 和 S_BOXES。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  # S-boxes (Customizable) # Each S-box is a 4x16 matrix # S-boxes taken from FIPS 46-3 Appendix 1 S_BOXES = [ [0, 1, 2, 3, 4, 5, 6, 7], [1, 2, 3, 4, 5, 6, 7, 8], [2, 3, 4, 5, 6, 7, 8, 9], [3, 4, 5, 6, 7, 8, 9, 10], [4, 5, 6, 7, 8, 9, 10, 11], [5, 6, 7, 8, 9, 10, 11, 12], [6, 7, 8, 9, 10, 11, 12, 13], [7, 8, 9, 10, 11, 12, 13, 14] ] def substitute(expanded_half): output = '' for i in range(0, len(expanded_half), 6): chunk = expanded_half[i:i + 6] row = int(chunk[:3], 2) col = int(chunk[3:], 2) val = S_BOXES[row][col] output += format(val, '04b') return output

  一个很有前途的点是，我们一个 val，对应的 row,col 最坏只有 8 种情况，那么所有的就是最多 种，相对来说是非常少的。

  那这样可能的 round_key 也只有这么多种。

  但是，根据 key 生成 round_key 是丢了 8 bit，我们还需要枚举 种，这样就是 种，不太能接受。

  但是，注意到如果我们有多个不同 feistel_ouput 的话，因为 round_key 是不变的，我们每个 feistel_ouput 对应的可能 round_key 求交的话，round_key 的可能就会大大减小。

  实现起来大概 5 个 feistel_ouput 就能确定 round_key 了。

  然后我们只需要传一个长度为 40 的随机明文就能弄到 5 个不同的 feistel_output，操作次数 1。

  最后就是手动写个解密，一点简单的代码而已。

HNP

• task

  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

  from Crypto.Util.number import * from hashlib import sha256 from random import seed, choice from secret import flag from signal import signal, alarm, SIGALRM from string import ascii_letters, digits def handler(signum, frame): print('Time out!') raise exit() def proof_of_work(): seed(getRandomRange(1, 2**128)) proof = ''.join([choice(ascii_letters + digits) for _ in range(20)]) digest = sha256(proof.encode('latin-1')).hexdigest() print('sha256(XXXX + {}) == {}'.format(proof[4: ], digest)) print('Give me XXXX:') x = input() if x != proof[: 4]: return False return True n = 8 A = 2048 B = A // n MASK1 = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff MASK2 = 0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff00000000000000000000000000000000000000000000000000000000000000000000000000000000000007ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc0000000000000000000000000000000000000000000000000000000000000000000000000000000000001fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff def challenge(): N = getPrime(A) X = getRandomRange(1, N) Y = [getRandomRange(1, N) for _ in range(n)] Z = [X * Y[_] % N for _ in range(n)] print(N) for _ in range(n): X_ = Z[_] Y_ = [(Y[_] >> (__ * B)) & MASK1 for __ in range(n)] Z_ = [(X_ * Y_[__] % N) & MASK2 for __ in range(n)] print(Z_) alarm(5) G = int(input('X:')) alarm(30) if G == X: return 1 else: return 0 signal(SIGALRM, handler) alarm(60) if not proof_of_work(): exit() for _ in range(3): if not challenge(): print('Wrong!') exit() else: print('Good!') print(flag)

  我们要求那个 ，首先肯定要求 ，对于一个 ，我们能得到 8 个形如 这样的式子. 其中 是取出了 的 256 个连续 bit 得到。 这是一个 HNP 问题，但由于 MASK2 只有 1700 个 bit，所以 e 本来是非常大的，但 MASK2 的 LSB 都是 1，所以可以除 ，转换成经典的 HNP，用之前 L3HCTF 的一个 HNP 题的脚本来跑就能把 都求出来，然后我们就能求出 。 剩下求 ，同样利用 这个形式的方程，此时我们有 64 组，全部拿出来当经典的 HNP 做就行了，时限问题可以用 flatter 解决。

babypairing

• task

  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

  import os from Crypto.Util.number import long_to_bytes,bytes_to_long p = 74952228632990620596507331669961128827748980750844890766694540917154772000787 a = 7527668573755289684436690520541820188297794210531835381305219764577170135028 b = 23620438740221081546022174030845858657033205037887915215836562897142269481377 F_p = GF(p) F_p2 = GF(p^2) a,b = F_p2(a),F_p2(b) E=EllipticCurve(F_p2,[a,b]) g=E.random_element() sk=F_p.random_element() pk=g*sk def load_element(x1,x2): is_positive=(x1<p) x = F_p2([x1,x2]) y2 = x^3+a*x+b if y2^((p^2-1)//2)==F_p2(-1): return None else : tmp = y2.square_root() #print((int(tmp)>(p-1)//2),is_positive) if (int(tmp[0])>(p-1)//2) ^^ is_positive : return E(x,tmp) else: return E(x,-tmp) def compress_element(P): x,y=P.xy() return (int(x[0]),int(x[1])) if int(y[0])<=(p-1)//2 else (int(x[0])+p,int(x[1])) def int_to32(x,l=17): b32dict="0123456789abcdefghijklmnopqrstuv" ret = "" while x>0: ret = b32dict[x%32]+ret x=x//32 return "0"*max(0,l-len(ret))+ret def enc_element(P): r = F_p.random_element() c2 = g*r c1 = pk*r+P ce1,ce2 = compress_element(c1),compress_element(c2) return "%065x%065x%065x%065x\n"%(*compress_element(c1),*compress_element(c2)) #return int_to32(ce1[0])+int_to32(ce1[1])+int_to32(ce2[0])+int_to32(ce2[1]) def enc_str(s): enc_map,ret = {},"" for c in s : if c in enc_map: cF_p2=enc_map[c] else : prefix = os.urandom(29)+bytes(c,encoding='ascii') x1 = int(F_p.random_element()) for i in range(256): cF_p2 = load_element(x1,bytes_to_long(prefix+bytes([i]))) if cF_p2!=None: enc_map[c]=cF_p2 break ret = ret+enc_element(cF_p2) return ret def dec_element(ct): c11,c12,c21,c22=[ct[i*65:i*65+65] for i in range(4)] C1,C2=load_element(int("0x"+c11,16),int("0x"+c12,16)),load_element(int("0x"+c21,16),int("0x"+c22,16)) P=C1-C2*sk return (compress_element(P)[1]&0xffff)>>8 print("g = load_element(*"+str(compress_element(g))+")") print("pk = load_element(*"+str(compress_element(pk))+")") #g = load_element(*(29278822809335293856257839032454656006652898948724335358857767737708161772420, 4396426956433009559948787995869502944693089612343852188342374458334039665950)) #pk = load_element(*(148673571405127568767045322546948264768210305253661849398897382818523458361167, 23902769016595610010920651447268476259469689719718232568266731055385481225779)) with open("test_passage.txt","r") as f: s = f.readline().strip() with open("ciphertext",'w') as f: f.write(enc_str(s))

  这个题做法很简单，题目描述说是压缩了一段话，而且直接解 ECDLP 不现实，所以就是去判断两个 cipher_text 是不是同一个字母，然后替换密码用 qiupqiup 解。 而这个同类判断就是两个 cipher 的 point 相减，变成一个类 DDH 问题。 这个搜论文可以直接拿 解，所以就没了。

SpRAse

• 这个题就是还原一个 RSA 密钥文件。 做法也很简单，把已知数据提取出来，我们能知道 的值， 的若干 bit，爆搜低位，用已知信息剪枝，高位直接用 copper smith 解就好了。 然后我被提取数据时长度会有 1 byte 左右偏差这个点卡了一天，哭了。

简单写一下场上出的两个题

MDH

• task

  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

  from sage.all import * from secret import flag from hashlib import sha256 from Crypto.Cipher import AES from Crypto.Util.Padding import pad from Crypto.Util.number import getPrime from random import getrandbits p = getPrime(256) G = Zmod(p**3) M = Matrix(G,[G.random_element() for i in range(64)],ncols=8) a = getrandbits(590) b = getrandbits(590) S = M ** (a * b) key = sha256(S.str().encode()).digest() ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex() with open("output", "w") as f: f.write('p = ' + str(p) + '\n') f.write('M = ' + str(list(M)) + '\n') f.write('Ma =' + str(list(M**a)) + '\n') f.write('Mb = ' + str(list(M**b)) + '\n') f.write('ct = 0x' + ct)

  矩阵 DLP 问题，一直认为是 560 bit，21:00 出通知 590 bit，服了。

  考虑对角化。 而 实际上是特征值直接求 次幂，所以对角化可以直接将矩阵 DLP 转化成一般的 DLP。

  但是实际上直接对角化是难以实现的，我们可以退而求其次，找到一个特征向量 和对应特征值 ，这样就有： 同样可以转化。

  在这个转化后，我们还是要解决一个这样的 DLP： 略大于 。

  分别求 ，和 。

  前一个我们有一个经典映射 ，后一个理论上是不可做的。

  但是 实际上是有若干较小质因子的，而 只略大于 ，所以我们只去求 模这些较小因子的答案再 crt 就能大概率出解。

  在这个题里我是能直接求出 589 bit，剩下的直接枚举一下倍数就行。

ezcrc

• task

  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 125 126 127 128 129 130 131 132 133 134 135 136

  #!/usr/bin/env python3 from socketserver import BaseRequestHandler,ThreadingTCPServer import random import os import string from hashlib import sha256 import signal import json from flag import flag assert len(flag) == 42 and flag.startswith(b"DubheCTF{") with open("polys.txt","r") as f: polys = json.load(f) def random_poly(): return polys[random.randint(0,len(polys)-1)] N = 256 BANNER = br''' CCCCC RRRRRR CCCCC GGGG AAA MM MM EEEEEEE CC C RR RR CC C GG GG AAAAA MMM MMM EE CC RRRRRR CC GG AA AA MM MM MM EEEEE CC C RR RR CC C GG GG AAAAAAA MM MM EE CCCCC RR RR CCCCC GGGGGG AA AA MM MM EEEEEEE ''' class Task(BaseRequestHandler): def send(self, msg,newline=True): try: if newline: msg += b'\n' self.request.sendall(msg) except: pass def _recv(self, sz): try: r = sz res = b"" while r > 0: res += self.request.recv(r) if res.endswith(b"\n"): r = 0 else: r = sz - len(res) res = res.strip() except: res = b"" return res.strip(b"\n") def recv(self, sz,prompt=b"> "): self.send(prompt,newline=False) return self._recv(sz) def _recvall(self): BUFF_SIZE = 1024 data = b'' while True: _recv = self.request.recv(BUFF_SIZE) data += _recv if len(_recv) < BUFF_SIZE: break return data def recvall(self,prompt=b"> "): self.send(prompt,newline=False) return self._recvall() def close(self): self.send(b'see you next time~~') self.request.close() def proof_of_work(self): random.seed(os.urandom(8)) proof = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)]) _hexdigest = sha256(proof.encode()).hexdigest() self.send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode()) x = self.recvall(prompt=b'Give me XXXX: ') if len(x) != 4 or sha256(x + proof[4:].encode()).hexdigest() != _hexdigest: return False return True def crc256(self,msg,IN,OUT,POLY): crc = IN for b in msg: crc ^= b for _ in range(8): crc = (crc >> 1) ^ (POLY & -(crc & 1)) return (crc ^ OUT).to_bytes(32,'big') def setup(self): self.send(BANNER) def handle(self): signal.alarm(120) if not self.proof_of_work(): return # initial IN = random.getrandbits(N) OUT = random.getrandbits(N) POLY = random_poly() for i in range(5): self.send(b"what do you want to do?") self.send(b"1.calculate crc") self.send(b"2.getflag") self.send(b"3.exit") try: choice = self.recv(5).decode() if choice == '1': self.send(b"Give me your message") msg = self.recv(100) crc_hex = self.crc256(msg,IN,OUT,POLY).hex() self.send(b"Here is your crc: "+crc_hex.encode()) elif choice == '2': flag_crc = self.crc256(flag,IN,OUT,POLY).hex() self.send(b"Here is your flag: "+flag_crc.encode()) else: self.close() return except: self.send(b"error") pass if __name__ == '__main__': HOST, PORT = "0.0.0.0", 10000 server = ThreadingTCPServer((HOST, PORT), Task) server.allow_reuse_address = True server.serve_forever()

  去年做过一个 ACTF 的题，也是 crc，那个题没出，但是留下了这个：

  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

  def crc256(msg,IN,OUT,POLY): crc = IN for b in msg: crc ^^= b for _ in range(8): crc = (crc >> 1) ^^ (POLY & -(crc & 1)) return int(crc ^^ OUT).to_bytes(32,'big') def equivalent_affine_crc(IN,OUT,POLY,target_bytes): crc=crc256 crc_bits = 256 zero_crc = crc(target_bytes*b"\x00",IN,OUT,POLY) zero_crc=bytes_to_long(zero_crc) target_bits = 8 * target_bytes v2n = lambda v: int(''.join(map(str, v)), 2) n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(crc_bits)) # n2v_t = lambda n: vector(GF(2), bin(n)[2:].zfill(target_bits)) Affine_Matrix = [] for i in range(target_bits): v = vector(GF(2), (j == i for j in range(target_bits))) value = bytes_to_long(crc(long_to_bytes(v2n(v),target_bytes),IN,OUT,POLY))^^zero_crc Affine_Matrix.append(n2v(value)) # crc affine function: crc_128(x) = M*x+ C return matrix(GF(2),Affine_Matrix).transpose(), n2v(zero_crc) def crc_256_reverse(crc_value,IN,OUT,POLY,target): M , C = equivalent_affine_crc(IN,OUT,POLY,target) # crc affine function: crc_128(x) = M*x+ C v2n = lambda v: int(''.join(map(str, v)), 2) n2v = lambda n: vector(GF(2), bin(n)[2:].zfill(256)) res = M.solve_right(n2v(crc_value)+C) return long_to_bytes(v2n(res),16)

  原题是 128，这个是我改的 256。

  那么这个就给了我们一个可以对 crc 求逆的东西。

  然后这个题他给了我们一个 len(flag)==42，flag 的形式是 DubheCTF{…}，把前后删去，正好 32 个字符，是足够我们解的。

  我们是不知道 IN,OUT,POLY 这三个 crc 参数，但是 crc 是线性的，所以：

  crc(m1,IN,OUT,POLY) xor crc(m2,IN,OUT,POLY) = crc(m1 xor m2,0,0,POLY)

  IN,OUT 就可以直接绕过。

  然后求 POLY，观察 crc 的流程，我们发现 crc(byte[256], 0, 0, POLY)=POLY。

  剩下的就是实现了，总共的交互次数是 4 次。

寒假忙着玩，只做了三个题，抢了三个一血。

奇怪的图片plus

• 先想办法拿到 key，注意到它的 check 方式是只 check 黑点，而黑点转化成 byte 是全 0，所以 AES 加密是假的，随便传两个图片过去就好了。

  然后注意到是 OFB mode，flag 图片背景是黑，所以 flag 前 16 个 bytes 是 0，那 cipher 的前 16 个 bytes 就是后面的 iv，直接解密转图片就好了。

lastRSA

• 先想办法求 ，两个 相当于给了两个多项式 ，所以可以多项式 ，求出 。

  然后枚举 ，已知 ，所以可以求出 ，又有 ，可以求出 ，像这样就能分解 。

transformation

• 看到一个意义不明的方程 ，丢到 google 啥的搜，发现叫 ，而且这东西还和 有双射，这下就直接做了。

  这里记录一下双射是啥： 但是 sage 中不支持 前的系数不等于一，但这个也是好做的，略。

rr

• task:

  1 2 3 4 5 6 7 8 9 10

  flag = ... n = ... rr = ... ks = [randint(0, rr**(i+1)) for i in range(20)] c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), (1<<7)-1, n) c2 = pow(flag, (1<<16)+1, n) ks = [pow(69, k, rr**(i+2)) for i, k in enumerate(ks)] print(f"{ks = }") print(f"{c1 = }") print(f"{c2 = }")

  明显就是要还原 ，也就是求一堆 DLP。

  这里面有个重要细节是 在 内随机，DLP 的模数是 。

  然后进行一番搜索，找到这个，他里面提到如果是形如 的 DLP，我们可以通过一个神秘映射直接求出 是多少。

  具体而言，令 ，则有 。

  那么本题就很好做了，用上面的方法把 还原，然后求一个多项式 gcd 就好。

lalala

• task：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  flag = "bi0sctf{%s}" % f"{randint(2**39, 2**40):x}" p = random_prime(2**1024) unknowns = [randint(0, 2**32) for _ in range(10)] unknowns = [f + i - (i%1000) for i, f in zip(unknowns, search("{(.*)}", flag).group(1).encode())] output = [] for _ in range(100): aa = [randint(0, 2**1024) for _ in range(1000)] bb = [randint(0, 9) for _ in range(1000)] cc = [randint(0, 9) for _ in range(1000)] output.append(aa) output.append(bb) output.append(cc) output.append(sum([a + unknowns[b]^2 * unknowns[c]^3 for a, b, c in zip(aa, bb, cc)]) % p) print(f"{p = }") print(f"{output = }")

  这个题比较简单，我们只有 10 个 ，但有 100 个方程，我们直接把所有 都看成变量，就是 100 个变量 100 个线性方程组，可以直接解。

  然后 时我们就知道了 ，直接求出 ，就没了。

daisy_bell

• task：

  1 2 3 4 5 6 7 8 9

  p = getPrime(1024) q = getPrime(1024) n = p*q c = pow(bytes_to_long(flag), 65537, n) print(f"{n = }") print(f"{c = }") print(f"{p>>545 = }") print(f"{pow(q, -1, p) % 2**955 = }")

  考验大家 copper 板子的时候到了！ 最后一行明显是一个可以看成 的多项式，然后和 一起做 copper 就好了。

  但我为啥每次做 copper 都得 玄学调参 加 等好久 呢。

Katyusha's Campervan

• task:

  1 2 3 4 5 6 7 8 9 10 11 12 13

  p = getPrime(1024) q = getPrime(1024) e = getPrime(132) n = p*q hint = pow(e, -1, (p-1)*(q-1)) hint %= p-1 hint %= 2**892 c = pow(3, int.from_bytes(flag), n**5) * pow(randint(0, n**5), n**4, n**5) % n**5 print(f"{n = }") print(f"{e = }") print(f"{c = }") print(f"{hint = }")

  说实话，我认为这个题是 rr 和 daisy_bell 的缝合，不知道为啥放出来。 这个跟 daisy_bell 形式基本一致，直接拿来求出 。

  然后这个 有扰动，注意到 。

  直接 ，这样后面的扰动就没了，然后用 rr 的方法求出 就好了。

challengename

• task:

  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

  flag = open("flag", "rb").read()[:-1] magic = os.urandom(16) p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff a = ###REDACTED### b = ###REDACTED### G = ###REDACTED### q = G.order() def bigsur(a,b): a,b = [[a,b],[b,a]][len(a) < len(b)] return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:])) [:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])] [i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)]) def bytes_to_long(s): return int.from_bytes(s, 'big') def genkeys(): d = random.randint(1,q-1) pubkey = Public_key(G, d*G) return pubkey, Private_key(pubkey, d) def sign(msg,nonce,privkey): hsh = md5(msg).digest() nunce = md5(bigsur(nonce,magic)).digest() sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce)) return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)}) def enc(privkey): x = int(flag.hex(),16) y = pow((x**3 + a*x + b) % p, (p+3)//4, p) F = ellipticcurve.Point('--REDACTED--', x, y) Q = F * privkey.secret_multiplier return (int(Q.x()), int(Q.y())) pubkey, privkey = genkeys() print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y()))) print("Encrypted flag:",enc(privkey)) nonces = set() for _ in '01': try: msg = bytes.fromhex(input("Message: ")) nonce = bytes.fromhex(input("Nonce: ")) if nonce in nonces: print("Nonce already used") continue nonces.add(nonce) print(sign(msg,nonce,privkey)) except ValueError: print("No hex?") exit()

  首先给了两个点 Public_key 和 enc_flag，所以能把曲线直接求出来。

  然后 bigsur 不知道具体是啥东西，但是如果 nonce 传 00 和 0000 都是明显不影响 magic 的。

  然后这个 sign 第二个参数就是那个应该是随机数的 k，这样我们就能在 k 不变的情况下搞到两次签名，这样就有方程： 其中 是这个曲线的阶。有人直接拿 当模数卡了 2h，我不说是谁

  所以就能搞到 ，就没了。

Predictable

• task: no

  a long description:

  1 2 3 4

  Can you help me test out this PRNG I implemented? I'm inserting a backdoor, but I'm sure you can't find it. Oh btw, I did some optimizing, so version 2 is faster. You can still try out version 1 though. They're the same anyway.

  不会的神秘题。

  连上去看到好像是用 Elliptic Curve 去生成这个随机数，交互允许的事情是生成一个随机数，或者你去预测下一个随机数，然后就啥都没有了。

  感觉不太能理解这东西的可做性，就是光盯这个交互是啥都不知道的，然后 description 提到的 backdoor 我也没啥思路，是不是得要 pwn 大手子来啊。

  然后这个 version 也很怪啊，optimize 难道会增加漏洞吗？

Junior RSA

• 先看 RSA。

  容易求出 ，又 ，求个逆就能算 。

  然后现在就已知 和 ， 展开为 ，其中 。

  所以可以求出 ，就能算 ，这样就 都算出来了。

Masquerade

• 看下 task

  1 2 3 4 5

  assert Auth_Code in long_to_bytes(Ticket[2]) \ and Ticket[2]%int(Ticket_Office._key['p']) if Ticket_Office._verify(Ticket[2], Ticket[:2]): print(f"Welcome to the masquerade, Enjoy it! {FLAG}")

  主要是过这两关。

  要绕过这个 函数，进 pycryptodome 里面看源码，长这样：

  1 2 3 4 5 6 7 8 9 10

  def _verify(self, m, sig): r, s = sig y, q, p, g = [self._key[comp] for comp in ['y', 'q', 'p', 'g']] if not (0 < r < q) or not (0 < s < q): return False w = Integer(s).inverse(q) u1 = (w * m) % q u2 = (w * r) % q v = (pow(g, u1, p) * pow(y, u2, p) % p) % q return v == r

  注意到它没有检测 的范围。

  所以这就很简单了，令 取大一点， 可以直接算。

  我是手动交互的。