第一次作为较大型比赛的出题人, 各位师傅轻点拷打QAQ.

CheckFlow

本题主要考点是LDPC校验码, 使⽤6 * 12的校验矩阵, 原码⻓度6位, 校验码⻓度6位, 总⻓12位.

LDPC码

⾸先是⽣成过程

为了便于计算, 下⾯使⽤了简化的校验过程, 使⽤了3 * 6校验矩阵作为实例.

原码:
        |0 1 0|
⽣成矩阵:
        |1 0 0 0 1 1|
        |0 1 0 1 0 1|
        |0 0 1 1 1 0|
LDPC校验码⽣成, 就是矩阵乘法(元素乘法使⽤与运算代替, 加法使⽤异或代替):
          |1 0 0 0 1 1|
|0 1 0| * |0 1 0 1 0 1| = |0 1 0 1 0 1|
          |0 0 1 1 1 0|
经过矩阵乘法得到的1 * 6矩阵就是LDPC校验码. 其中: 前三位是原码, 后三位是校验码

其次是校验过程再次观察LDPC码的结构, 可以发现其实校验码只跟⽣成矩阵的后三列和原码相关, 列出关系:

假设: 原码位为 |x0 x1 x2| , 校验位为 |y0 y1 y2|

y0 = x1 ^ x2
y1 = x0 ^ x2
y2 = x0 ^ x1

对上⾯三个关系进⾏变换:

0 = y0 ^ x1 ^ x2
0 = y1 ^ x0 ^ x2
0 = y2 ^ x0 ^ x1

也就是说当原码没有出错的情况下, 校验位和原码规定的位进⾏异或全部会得出0, 出错则得出1.

根据这个关系就可以得到校验矩阵

校验矩阵中的每一行对应一个位的校验, ⾸先对LDPC码进⾏掩码操作, 然后异或得到校验结果

关于LDPC实现检验的原理，可以⾃⾏假设⼀个位和两个位出错这两种情况，再观察三个检验位的具体值, 当然本题只涉及检验矩阵的输出结果是否为0, 所以这不是必须要理解的，感兴趣的可以了解⼀下.

	        |0|
                |1| 
|0 1 1 1 0 0|	|0|
|1 0 1 0 1 0| * |0| = |0|
|1 1 0 0 0 1|   |1| 
	        |0|
                |0|
                |1|

题目分析

去符号C++, 可以⽤bindiff或flair恢复符号, 基本都是string和vector.

⾸先是检验矩阵⽣成

JWA36ZK0Z9M7AVF@1N@72R

每个元素都是4字节, 是6 * 12矩阵

1IA_TRSSO7OJI22NT4K 得到校验矩阵

|1 1 1 0 1 1 0 1 0 1 0 1|
|1 0 0 1 1 0 1 1 0 1 0 0|
|0 1 1 1 0 0 1 0 1 0 0 1|
|0 1 0 0 0 1 1 0 1 1 1 0|
|1 0 1 1 1 0 0 0 1 0 1 0|
|0 0 0 0 0 1 0 1 0 0 1 1|

通过调试查看内存, 容器判断vector, 下⾯还调⽤了函数得到检验矩阵的逆, 但是实际上并不影响最终的判断, 只是结果矩阵的格式从6 * 1变成了1 * 6, 主要是可以从该函数的两个参数中得到容器类型.

主要的验证逻辑就在主函数中, 根据sub_407028()出现的位置在if判断条件中可以猜测是check函数.

  // 总体逻辑: 从小到大输入12位LDPC校验码
  // 校验过程中有两个LDPC变量: back和front
  // back记录上次检验的LDPC码
  // front记录当前检验的LDPC码
  // 校验的具体逻辑是饶了一圈的从小到大正确LDPC码的排列检查: 
        //1. 首先检验当前LDPC码是否正确, 出错则退出
	//2. 检查back < front, 保证LDPC码从小到大排列
	//3. 检查back和front之间是否存在正确的LDPC码, 如果存在则说明漏掉了
	//4. 检查最后一个front到"111111111111"之间是否存在正确的LDPC码, 如果存在说明后面少了LDPC码
  for ( i = 0; ; i += 12 )                      // 轮检验
  {
    v12 = i;
    if ( v12 >= len(v30) )                      // 循环结束条件: 读取全部字符串
      break;
    sub_496C80(v34, v30, i, 12LL);              // 获取一个PDPC码字符串
    sub_493D80(v33, v34);
    sub_493D30(v34);
    if ( len(v33) != 12 )                       // 检查LDPC码长度
    {
      v0 = sub_481E90(&unk_5E32E0, "Length error.");
      sub_480730(v0, sub_481760);
      exit(1LL);
    }
    if ( !(unsigned __int8)check(v33, v27, v28) ) // 检测front的LDPC码是否出错
    {
      v11 = sub_481E90(&unk_5E32E0, "Emmmmmm......Wrong.");
      sub_480730(v11, sub_481760);
      exit(1LL);
    }
    if ( i ) // 针对第一轮"000000000000"校验的判断, 第一轮设置v18变量位-1, 这样下面j进行检测的时候j初始化就是0, 与front相等, 通过检验
	     // 假设输入不是"0000000000": 则会判断0到front之间存在多余的正确LDPC码 (就是"000000000000")
    {
      sub_496AA0(v34, v31);
      v18 = sub_407141(v34);
      sub_493D30(v34);
    }
    else
    {
      v18 = -1;
    }
    sub_496AA0(v34, v33); // v33 = front字符串
    v1 = sub_407141(v34);
    v2 = v18 < v1; // 得到back < front
    sub_493D30(v34);
    if ( !v2 ) // 判断back < front
    {
      v10 = sub_481E90(&unk_5E32E0, "Emmmmmm......Wrong.");
      sub_480730(v10, sub_481760);
      exit(1LL);
    }
    for ( j = v18 + 1; ; ++j ) // 检查back和front之间是否存在正确的校验码, 
    {
      sub_496AA0(v34, v33);
      v4 = sub_407141(v34);
      v5 = j < v4;
      sub_493D30(v34);
      if ( !v5 )
        break;
      sub_4070E1(v34, j);
      sub_493D80(v32, v34);
      sub_493D30(v34);
      if ( (unsigned __int8)check(v32, v27, v28) ) // 存在说明漏了正确的LDPC码
      {
        v3 = sub_481E90(&unk_5E32E0, "Emmmmmm......Wrong.");
        sub_480730(v3, sub_481760);
        exit(1LL);
      }
    }
    v6 = (unsigned int)(i + 12);
    if ( v6 == len(v30) ) // 当读取到最后一个LDPC码的时候
    {
      sub_496AA0(v34, v33);
      v20 = sub_407141(v34) + 1;
      sub_493D30(v34);
      while ( 1 )
      {
        v26 = v29;
        sub_407782(v34, "111111111111", v29); // 最后一个LDPC码
        v8 = sub_407141(v34);
        v9 = v8 >= v20;
        sub_493D30(v34);
        sub_407A48(v29);
        if ( !v9 )
          break;
        sub_4070E1(v34, v20);
        sub_493D80(v32, v34);
        sub_493D30(v34);
        if ( (unsigned __int8)check(v32, v27, v28) ) // 循环检查与最后的LDPC码之间是否存在其他正确点, 如有则说明输入不完整
        {
          v7 = sub_481E90(&unk_5E32E0, "Emmmmmm......Wrong.");
          sub_480730(v7, sub_481760);
          exit(1LL);
        }
        ++v20;
      }
    }
    sub_493D60(v31, v33);
  }

check函数, 可以查看参数内存, 判断容器类型, 具体逻辑如下

a1: 字符串指针, 就是待检验的LDPC码
sub_406D40(): 检查字符串, 并将字符串转换为矩阵
sub_406E17(): 实现的是标准矩阵乘法, ⼀个提⽰点是开头的矩阵乘法原则判断.
矩阵都是vector容器最后检查结果矩阵全0

__int64 __fastcall sub_407028(__int64 a1, __int64 a2, __int64 a3)
{
  __int64 v3; // rax
  __int64 v5; // rax
  int i; // [rsp+2Ch] [rbp-14h]
  sub_406D40(a1, a2);
  sub_406E17(a2, &off_5E23B0, a3);
  for ( i = 0; ; ++i )
  {
    v5 = sub_407822(a3, 0LL);
    if ( i >= (unsigned __int64)sub_4078BC(v5) )
      break;
    v3 = sub_407822(a3, 0LL);
    if ( *(_DWORD *)sub_40784C(v3, i) )
      return 0LL;
  }
  return 1LL;
}

解题脚本

import numpy as np
N=12
K=6
H=np.array([
	[1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1],
	[1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0],
	[0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1],
	[0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0],
	[1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0],
	[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1]])
#print(H)
b=[]
for i in range(2**N): #2^10 = 1024
    a=format(i,'b') # 列举出所有可能的校验码
    b.append("{:0>12s}".format(a))

v=np.zeros((2**N,N)) # 存储所有的校验码的元组
for i in range(2**N): # 从⼩到⼤
    v[i]=b[i]
    for j in range(N): # 存储校验码
        v[i][j]=b[i][j] #v是0000000~1111111

w=np.zeros((1,N-K))
for i in range(2**N):
    if np.all(np.dot(v[i],H.T)%2==w):
        print(v[i])

LameCrow

XCTF2023-预选赛-CheckFlow WP

CheckFlow

LDPC码

题目分析

解题脚本