DubheCTF 2024

Posted on

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

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 次。