[SUSCTF 2022]Tanner

题目描述中提到:There is a special graph which describe one check matrix, find out where is the hint(maybe in the binary data?) and what is the flag.

我们查看到Png文件结束标志[49 45 4E 44 AE 42 60 82]后有信息信息：
THE FLAG IS the sha256 of the sum ofthe proper codewords(binary plus)which satisfy the condition.(note: with no zeros front)

意思是flag 是满足条件的所有合法码字（按二进制“加法”求和）的 SHA-256 哈希值。
（注意：结果的二进制数前面不能有多余的 0。）

我们看附件这张图展示的是一种叫 Tanner graph（坦纳图） 的结构，用来表示线性分组码（Linear Block Code）中的校验矩阵（Parity-Check Matrix, H）。

方框（f₀–f₄）代表 校验节点（check nodes），
圆圈（c₀–c₉）代表 比特节点（bit nodes）。

每个校验节点对应校验矩阵 H 的一行，每个比特节点对应一列。
有连线表示某个比特在该校验方程中参与异或（XOR）计算。

也就是说，如果矩阵元素 H[i][j] = 1，就在图中连线 fᵢ ↔ cⱼ。
校验条件是：

H * cᵀ = 0   （mod 2）

换句话说，每个 fᵢ 的相连 cⱼ 比特之和 mod 2 必须等于 0。

什么是“合法码字（proper codeword）”

一个 合法码字（或称“有效码字”）就是一个长度为 n 的二进制向量
c = [c₀, c₁, …, c₉]，
它满足上面的校验条件：

H * cᵀ = 0  (mod 2)

也就是说，所有校验节点的异或结果都为 0。

这些合法码字构成了这个线性码的码空间（code space）。

根据上述知识得还原矩阵

c0	c1	c2	c3	c4	c5	c6	c7	c8	c9
1	1	1	1	0	0	0	0	0	0	f0
1	0	0	0	1	1	1	0	0	0	f1
0	1	0	0	1	0	0	1	1	0	f2
0	0	1	0	0	1	0	1	0	1	f3
0	0	0	1	0	0	1	0	1	1	f4

第二步：根据校验矩阵，可以用脚本还原码字

脚本来源：SUSCTF2022misc——Tanner_susctf2022 tanner-CSDN博客

'''
Author: Jack Jparrow
Date: 2022-02-27 12:01:40
LastEditTime: 2022-02-27 12:25:23
LastEditors: Jack Jparrow
Description: 根据校验矩阵求码字
'''
import numpy as np
N = 10
K = 5
b = []
H = np.array([[ 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
            [ 1, 0, 0, 0, 1, 1, 1, 0, 0, 0],
            [ 0, 1, 0, 0, 1, 0, 0, 1, 1, 0],
            [ 0, 0, 1, 0, 0, 1, 0, 1, 0, 1],
            [ 0, 0, 0, 1, 0, 0, 1, 0, 1, 1]])
for i in range(2**N):
    a = format(i, 'b')
    b.append("{:0>10s}".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 o in range(2**N):
    if np.all(np.dot(v[o], H.T) % 2 == w):
        print(v[o])

之后依据

flag 是满足条件的所有合法码字（按二进制“加法”求和）的 SHA-256 哈希值。
（注意：结果的二进制数**前面不能有多余的 0。）

对码字稍加处理，只按行留下二进制数值，进行二进制累加求和

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;

/**
 * @Author: Jack Jparrow
 * @Date: 2022-02-27 14:14:12
 * @LastEditTime: 2022-03-04 14:55:39
 * @LastEditors: Jack Jparrow
 * @Description: 读文件，求和
 */
public class Tanner {
    public static void main(String[] args) {
        int sum=0;// 和

        File myFile = new File("D:\\Desktop\\res.txt");
        try {
            InputStreamReader Reader = new InputStreamReader(new FileInputStream(myFile), "UTF-8");
            BufferedReader bufferedReader = new BufferedReader(Reader);

            String lineTxt = null;

            while ((lineTxt = bufferedReader.readLine()) != null) {

                sum += Integer.parseInt(lineTxt, 2);// 求和
                
                Reader.close();
            }

            System.out.println(Integer.toBinaryString(sum));// 输出结果的二进制形式

        } catch (UnsupportedEncodingException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}

将结果进行sha256加密，加上NSSCTF{}即为flag

得到的 flag 就是题目要求的：

flag=NSSCTF{c17019990bf57492cddf24f3cc3be588507b2d567934a101d4de2fa6d606b5c1}