2024CryptoCTF都过去了，才来补2023CryptoCTF的坑

首先题目源码可在NSS上拿到，这个题本来也并不复杂，就是每次计算(d >> 16) & 0xff时其实都是在 $\mathbb{Z}_{2^{24}}$ 上运算，所以只需要在 $\mathbb{Z}_{2^{24}}$ 上爆破seed即可，网上应该也可以找到这题的WP，就不再细说了

有意思的是，我因为审题失误，所以在做这题的时候怼了个C语言多线程爆破了整个 $\mathbb{Z}_{2^{32}}$ ，既然代码都写了，那就顺便写篇文章记录一下C语言多线程爆破的写法

正文·

revenge·

不妨给原来的Blue Office加点难度，改成以下的样子

#!/usr/bin/enc python3

import binascii
import random
seed = random.getrandbits(32)
flag = b'CCTF{*************************}'

def gen_seed(s):
	i, j, k = 0, len(s), 0
	while i < j:
		k = k + ord(s[i])
		i += 1
	i = 0
	while i < j:
		if (i % 2) != 0:
			k = k - (ord(s[i]) * (j - i + 1))            
		else:
			k = k + (ord(s[i]) * (j - i + 1))
	
		k = k % 2147483647
		i += 1

	k = (k * j) % 2147483647
	return k

def reseed(s):
	return s * 214013 + 2531011

def encrypt(s, msg):
	assert s <= 2**32
	c, d = 0, s
	enc, l = b'', len(msg)
	while c < l:
		d = reseed(d)
		enc += (msg[c] ^ ((d >> 8*3) & 0xff)).to_bytes(1, 'big')
		c += 1
	return enc

enc = encrypt(seed, flag)
print(f'enc = {binascii.hexlify(enc)}')
# enc = b'1b26a1bc7ccb3077239e9c907c04e65c3139d5a39b21102c7e93e42d00861e'

主要修改的地方是encrypt里面的(d >> 8*3) & 0xff，这样改后就不能像原来那样爆破 $\mathbb{Z}_{2^{24}}$ 了

exp·

针对这个revenge，我怼了以下的exp进行求解

首先把enc进行解码，方便我写C的代码

enc = b'1b26a1bc7ccb3077239e9c907c04e65c3139d5a39b21102c7e93e42d00861e'
c = bytes.fromhex(enc.decode())
print(len(c))
print(', '.join([str(x) for x in c]))

'''
31
27, 38, 161, 188, 124, 203, 48, 119, 35, 158, 156, 144, 124, 4, 230, 92, 49, 57, 213, 163, 155, 33, 16, 44, 126, 147, 228, 45, 0, 134, 30
'''

然后就是C语言的多线程爆破

// gcc ./expm.c -lpthread -Ofast -o expm && ./expm
#include <stdio.h>
#include <ctype.h>
#include <unistd.h>
#include <pthread.h>

const int l = 31;
const char c[31] = {176, 203, 99, 22, 57, 248, 165, 171, 32, 255, 115, 133, 146, 99, 131, 248, 154, 113, 187, 196, 237, 45, 87, 20, 46, 5, 243, 157, 67, 79, 206};
const unsigned long max = 4294967295;

const int maxThreads = 32;
unsigned long ndone = 0;
//pthread_mutex_t locker;
typedef struct {
  unsigned int st;
  unsigned int ed;
}para;

void tqdm(unsigned int i) {
    float percentage = (float)i / max;
    printf("\r[%u/%lu] %.1f%%", i, max, percentage * 100);
    fflush(stdout);
}

unsigned int reseed(unsigned int s) {
  return s * 214013 + 2531011;
}

int check(char* s) {
  for (int i=0; i<l; i++) {
    if (!isprint(s[i])) {
      return 0;
    }  
  }
  return 1;
}

int decrypt(unsigned int s) {
  unsigned int d = s;
  char msg[32] = {0};
  for (int i=0; i<l; i++) {
    d = reseed(d);
    msg[i] = c[i] ^ ((d >> 16) & 0xff);
    if (!isprint(msg[i])) {
      return 0;
    }  
  }
  printf("%u, %s\n", s, msg);   //
  return 1;
}

void* gao(void* args) {
  para par = *(para *)args;
  for (unsigned int s=par.st; s<=par.ed; s++) {
    decrypt(s);
    //pthread_mutex_lock(&locker);
    ndone += 1;
    //pthread_mutex_unlock(&locker);
  }

  pthread_exit(0);
}


int main() {
  pthread_t tids[maxThreads];
  para par[maxThreads];
  for (int i=0; i<maxThreads; i++) {
    par[i].st = (max / maxThreads) * i;
    par[i].ed = (max / maxThreads) * (i+1)-1;
  }
  par[maxThreads-1].ed = max;

  for (int i=0; i<maxThreads; i++) {
    //printf("%u, %u\n", par[i].st, par[i].ed);
    pthread_create(tids+i, NULL, gao, par+i);
  }

  while (ndone < max)
    tqdm(ndone);

  return 0;
}

C语言的多线程·

在C语言中，起多线程用的是<pthread.h>库中的pthread_create函数，这个函数的签名如下

int pthread_create(pthread_t * thread, 
                   const pthread_attr_t * attr, 
                   void * (*start_routine)(void *), 
                   void *arg);

参数thread是一个地址，指明线程起来后，线程id的存放位置
参数attr用于指明线程的属性，传NULL的话就是使用默认配置
参数start_routine就是需要调用的函数，函数的返回类型为void*
参数arg就是调用start_routine时所传入的参数

在exp中，我要调用gao函数，参数是par[i]，线程id存在tids[i]中，使用默认的线程配置，所以我的调用语句就是

1	pthread_create(tids+i, NULL, gao, par+i);

线程分配·

在这个revenge中，需要从 $0$ 到 $2^{32}$ 爆破seed，为了减少创建线程产生的开销，最好的方法是先指定一个总的线程数（exp中的maxThreads），然后把 $0$ ~ $2^{32}$ 平均切分成线程数那么多份，最后在每个线程中爆破对应的切片

比如在exp中我使用以下方法进行切分，其中st就是线程中的爆破起点，ed就是终点

para par[maxThreads];
for (int i=0; i<maxThreads; i++) {
  par[i].st = (max / maxThreads) * i;
  par[i].ed = (max / maxThreads) * (i+1)-1;
}
par[maxThreads-1].ed = max;

理论上 pthread_create应该有其他方法传入多个参数，但我在网上搜了一轮，发现最好还是把参数塞到一个结构体中，然后给函数传入这个结构体（如果查到别的方法再补充），我用的结构体长下面的样子

typedef struct {
  unsigned int st;
  unsigned int ed;
}para;

爆破·

分配好线程后就是枯燥的爆破了，这里没啥好说的

但是要注意 start_routine的返回类型和参数类型都是void*，然后使用pthread_exit(0);代替函数的return

void* gao(void* args) {
  para par = *(para *)args;
  for (unsigned int s=par.st; s<=par.ed; s++) {
    decrypt(s);
    //pthread_mutex_lock(&locker);
    ndone += 1;
    //pthread_mutex_unlock(&locker);
  }

  pthread_exit(0);
}

加锁·

在我的exp中，我还使用了一个ndone变量记录爆破完成的seed个数，用来测试爆破的速度和在main函数中判断爆破的终止

这里ndone是个全局变量，理论上写入需要加锁，加锁可以使用<pthread.h>库的pthread_mutex_t变量，先定义一个锁，比如

1	pthread_mutex_t locker;

然后使用pthread_mutex_lock(&locker);进行加锁，使用pthread_mutex_unlock(&locker);进行解锁

但因为exp中的ndone += 1是个原子操作，所以不加锁也没关系

实测加了锁后爆破会慢很多

速度测试·

为了在爆破时观察爆破速度，我还模拟了一个Python中的tqdm进度条

void tqdm(unsigned int i) {
    float percentage = (float)i / max;
    printf("\r[%u/%lu] %.1f%%", i, max, percentage * 100);
    fflush(stdout);
}

其中参数i就是ndone变量，即已经爆破的个数，max就是全局变量写死的2**32（虽然这个写法不太好，也凑合用）

实测在我的渣笔记本上，开32线程爆完2**32也只需要一分钟

总结·

有空再整理成模板（：