0xGame2024 WriteUp

摘要

本文补充了2024年10月比赛0xGame2024的WriteUp。主要方向是crypto和reverse，包括除了AES和DES两题的所有题解。

赛时WriteUp

[Week1] 0xGame2024 WriteUp

[Week2] 0xGame2024 WriteUp

[Week3] 0xGame2024 WriteUp

[Week4] 0xGame2024 WriteUp

Crypto

Number Theory CRT

问题：RSA，在e与N不互素的条件下，求解m

N = 1022053332886345327
p, q = 970868179, 1052721013
e = 294200073186305890
c = 107033510346108389
phi = (p - 1) * (q - 1)

print(f"gcd(e, phi) = {GCD(e, phi)}")
# gcd(e, phi) = 2

由于e与N不互素，只能取 $e\over\gcd(e, N)$ 的模逆即 2d，$2d\cdot {e\over2}=\phi(N)$

D = inverse(e // 2, phi)
M = pow(c, D, N)
print(f"M = {M}")
# M = 919254629320741497

这样就能求出 $m^2=m^{2de}=c^{2d}\mod N$， 现在只需解决这个二次剩余问题即可
先分解N质因数化为两个同余方程$\begin{cases}m_{1}^2=a\mod p\\m_{2}^2=a\mod q\\\end{cases}$，再用CRT求解即可。

def CRT(a, n):
    N = 1
    for i in range(len(a)):
        N *= n[i]
    x = 0
    for i in range(len(a)):
        m = N // n[i]
        x += a[i] * m * inverse(m, n[i])
    return x % N
m = CRT([m1, m2], [p, q])

由于本题数据较小，求解m₁、m₂可以用暴力破解

def brute_force(M, N):
    M = M % N
    for m in range(2, N):
        if pow(m, 2, N) == M:
            return m

或者是tonelli-shanks算法：

def tonelli_shanks(n, p):
    if pow(n, (p - 1) // 2, p) != 1:
        raise ValueError(f"{n} 不是模 {p} 的平方剩余")

    s = 0
    q = p - 1
    while q % 2 == 0:
        q //= 2
        s += 1

    z = 2
    while pow(z, (p - 1) // 2, p) == 1:
        z += 1

    R = pow(n, (q + 1) // 2, p)
    c = pow(z, q, p)
    t = pow(n, q, p)
    M = s

    while t != 1:
        i = 0
        temp = t
        while temp != 1:
            temp = (temp * temp) % p
            i += 1

        b = pow(c, 1 << (M - i - 1), p)
        R = (R * b) % p
        c = (b * b) % p
        t = (t * c) % p
        M = i

    return R

# m1 = brute_force(M, p)
# m2 = brute_force(M, q)

m1 = tonelli_shanks(M, p)
m2 = tonelli_shanks(M, q)
m = CRT([m1, m2], [p, q])
assert pow(m, e, N) == c
print(f"0xGame{{{MD5(m)}}}")
# 0xGame{3932f6728585abbf751a212f69276d3e}

LLL-1 | Redo

这道题先生成了一个4*4的随机矩阵Nosie，将第一行替换为flag的信息，作为矩阵M，乘以一个矩阵C（其实不是正交矩阵）得到B，已知B来还原flag。相信大部分人都是按提示直接LLL出的结果，我也一样，所以今天又重新拿出来理解。

理解这道题为什么用LLL可以直接得出答案需要理解两个点：

1. 在flag信息较小的情况下，M极大概率能用LLL还原出flag。
2. M和C*M表示的格是相同的，对M和C*M进行格基规约是等效的。

第一点，举一个简单的例子，对于二维的格基(10，7)和(21，114514)进行格基规约，一定会保留(10，7)，但(21，114514)一定会被约简。这道题也是，数量级小的flag信息和数量级大的noise同时格基规约，flag信息极大概率会保留，除非两个数量级大的noise相减能得到比flag更小的格基但这几乎是不可能。

第二点，这个性质与三角、正交矩阵没关系，而是因为C行列式等于1，像这样行列式等于1或-1的矩阵叫单模矩阵。C*M相当于一个对M的线性变换，这样的格基构成的格一定在M构成的格中。而格的行列式是个定量，对于同一个格的格基行列式总是相等的，由于C*M行列式没有变化，显然格也是不变的。

LLL-3 | Redo

这题当时用的多元coppersmith做的：多元copper脚本，h+p=a*seed+b，求解p, seed正好只有一组解。

构造格的过程如下，p的数量级是2¹¹⁵，这里的K应该设为2¹¹⁵适宜。

 

Reverse

ZzZ

美化一下关键代码，显然有x1,x5，需要解带位运算的方程组

scanf("0xGame{%8llx-%4s-%4s-%4s-%12llx}", x1, x2, x3, x4, x5);
x = *(unsigned int *)x2;
y = *(unsigned int *)x3;
z = *(unsigned int *)x4;
if ( x1[0] == 3846448765LL
  && 14 * x + 11 * y - z == 0x48FB41DDDLL
  && 9 * x - 3 * y + 4 * z == 0x2BA692AD7LL
  && ((z - y) >> 1) + (x ^ 0x87654321LL) == 3451779756
  && x5[0] == 0xD085A85201A4LL)
    puts("Congratulations! You get the correct flag.");

使用z3求解器求解：

from z3 import *

x1, x5 = 3846448765, 0xD085A85201A4
x, y, z = BitVecs("x y z", 32)

solver = Solver()
solver.add(14 * x + 11 * y - z == 0x48FB41DDD)
solver.add(9 * x - 3 * y + 4 * z == 0x2BA692AD7)
solver.add(((z - y) >> 1) + (x ^ 0x87654321) == 3451779756)

if solver.check() == sat:
    model = solver.model()
    x2, x3, x4 = model[x].as_long(), model[y].as_long(), model[z].as_long()
    print(
        "0xGame{%8x-%4s-%4s-%4s-%12x}"
        % (
            x1,
            x2.to_bytes(4, byteorder="little").decode(),
            x3.to_bytes(4, byteorder="little").decode(),
            x4.to_bytes(4, byteorder="little").decode(),
            x5,
        )
    )

EzAndroid

后悔没做这道签到题，在jadx中搜一下就能找到J6IwkwOvgGFthiofcwab0ka7KrOMpVbfROQ9Jh5C5YMqfyLLdMrNoj4YGVh

base62解码得到0xGame{caff454e-2238-42aa-a75a-75e9f5f1f769}

Justsoso

由题，flag用key加密经过base64编码等于encryptedFLAG，那么只要知道key并逆向ReversC4.encrypt即可。

encryptedFLAG==b64encode(ReversC4.encrypt(flag, key))

getKey()在native层，IDA分析so文件源码：

看上去挺复杂，其实就是把source二倍后异或0x7F，这样就得到了key

public static int[] getKey() {
    String source = "just_0xGame_so";
    int[] key = new int[14];
    for (int i = 0; i < source.length(); i++)
        key[i] = 2 * (int) source.charAt(i) ^ 0x7F;

    return key;
}

加密过程很好逆向，其中inital、i、i2只要随便编一个44位的flag放进encrypt里面跑一下，就能知道末状态的值，将他们作为初始值放进decrypt里面即可。

public static byte[] decrypt(byte[] bArr, int[] iArr) {
    int length = bArr.length;
    int[] initial = { 107, 11, 190, 182, 97, 252, 84, 71, 59, 218, 18, 68, 241, 141, 155, 240, 170, 78, 43, 175, 98, 87, 239, 53, 228, 81, 157, 44, 13, 26, 158, 179, 79, 210, 234, 251, 163, 249, 130, 120, 211, 219, 129, 186, 69, 225, 41, 91, 36, 15, 171, 123, 243, 140, 138, 32, 173, 166, 159, 253, 236, 200, 176, 152, 113, 57, 94, 208, 116, 144, 8, 119, 99, 23, 104, 181, 52, 196, 162, 49, 224, 213, 143, 5, 192, 46, 118, 75, 114, 136, 160, 178, 205, 149, 65, 29, 20, 102, 223, 148, 39, 115, 124, 127, 229, 255, 122, 50, 117, 83, 109, 216, 17, 88, 128, 106, 125, 60, 188, 61, 244, 95, 73, 66, 195, 82, 27, 28, 147, 62, 189, 154, 185, 112, 30, 235, 86, 9, 139, 153, 22, 24, 237, 14, 54, 203, 164, 48, 16, 204, 230, 232, 156, 3, 133, 214, 74, 161, 70, 220, 238, 47, 183, 10, 2, 180, 131, 169, 67, 58, 1, 250, 254, 6, 207, 199, 198, 42, 247, 33, 221, 110, 184, 34, 25, 31, 217, 168, 137, 222, 146, 72, 89, 193, 103, 92, 256, 4, 209, 45, 226, 194, 202, 37, 172, 77, 177, 90, 100, 80, 174, 12, 55, 19, 197, 245, 231, 40, 51, 93, 212, 151, 96, 227, 201, 121, 108, 126, 21, 63, 35, 165, 7, 145, 56, 111, 187, 38, 105, 150, 85, 242, 132, 134, 142, 64, 233, 206, 135, 246, 167, 101, 215, 191, 76, 248 };
    int i = 44;
    int i2 = 12;
    for (int i3 = length - 1; i3 >= 0; i3--) {
        int i4 = initial[i2];
        int i5 = initial[i];
        bArr[i3] = (byte) (bArr[i3] ^ ((byte) initial[(i4 + i5) % 256]));
        initial[i2] = i5;
        i2 = (i2 - i4 + 256) % 256;
        initial[i] = i4;
        i = (i + 255) % 256;
    }

    return bArr;
}

跑一下：

public static void main(String[] args) {
    String encryptedFLAG = "nB9RCjwReif5P1H1MYO6m/hucCGjI6EE9wWEx/E4N+bO5k5ior6MnqAGQfc=";
    String testFlag = "0xGame{111111111111111111111111111111111111}";
    int[] key = getKey();
    encrypt(testFlag.getBytes(), key);

    String FLAG = new String(decrypt(Base64.getDecoder().decode(encryptedFLAG), key));
    System.out.println(FLAG); // 0xGame{fd51ce4b-4556-4cf9-9430-67480614e43b}
}

Register

看官方的WP程序居然能跑起来？但附件由于缺少dll，根本跑不起来。

分析一下程序，已知Str是0xGameUser，先异或一个v7，再进行哈希。

v8就是time(0)，不放源码了，算v7有一个小坑，你看调用的时候是0x1C、v8的顺序，到这个函数之前有个函数偷偷把两个参数换了一下位置。因为逆向经常见到这种一个调用一个而不是直接调用的情况，我当时一直都没发现导致卡死了😢。
​带入后发现很简单v7=time(0)>>28，算出来是6

哈希这部分可以直接拿过来用，或者查一下CryptCreateHash就会发现0x8004u对应SHA-1算法，可以用

CryptCreateHash(phProv[0], 0x8004u, 0, 0, phHash);

算出来：

int main()
{
    char Buf2[68];
    char Str[10] = "0xGameUser";
    time_t v9 = time(0);
    int v3 = 28;
    char v8 = v9 >> v3;
    printf("v8: %d\n", v8);
    for (int i = 0; i < 10; ++i)
    {
        Str[i] ^= v8;
    }

    sub_3D18D0((BYTE *)Str, (int)Buf2, 0xAu);
    printf("0xGame{%s}\n", Buf2);
    // 0xGame{1b4e549d12ccb4bb4936f95fedecebf55494dec8}
    return 0;
}

To be continued......