SHC2024 part of crypto

Posted on

做了两道 medium 的分组密码，感觉算是练习了一下不太熟悉的东西。

cry

  • 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
    #!/usr/bin/env python3

    from Crypto.Util.number import bytes_to_long, long_to_bytes
    from Crypto.Util.Padding import pad, unpad
    from Crypto.Cipher import AES
    from secrets import randbelow
    from string import printable
    from os import getenv

    def encrypt(data, keys):
        if isinstance(data, str):
            data = data.encode()

        data = pad(data, 16)

        data += b"<<valid_secret>>"

        for k in keys:
            data = AES.new(k, AES.MODE_ECB).encrypt(data)

        return data


    def decrypt(data, keys):
        if isinstance(data, str):
            data = data.encode()

        for k in keys[::-1]:
            data = AES.new(k, AES.MODE_ECB).decrypt(data)

        if data[-16:] != b"<<valid_secret>>":
            return (f"Could not decrypt; invalid data: {data[:-16]}")

        return f"Decrypted data: {unpad(data[:-16], 16)}"

    def add(vault, keys, key, data):
        vault[key] = encrypt(data, keys) 

    def get(vault, keys, key):
        return decrypt(vault.get(key, b""), keys) 

    def generate_keys():
        return [long_to_bytes(randbelow(2**9)).ljust(16) for _ in range(6)]

    def main():
        vault = {}

        print("Welcome to the future of secret vaults")
        print("Here you can store all your secrets")

        admin_keys = generate_keys()
        user_keys = generate_keys()
        add(vault, admin_keys, "example", "nobody will be able to read this")
        add(vault, admin_keys, "FLAG", getenv("FLAG", "flag{fakeflagfakeflag}"))

        EVALUATION_PERIOD = 5

        while 1:
            print(f"Vault menu: {EVALUATION_PERIOD} TESTING QUERIES LEFT")
            print("  1) add value to vault")
            print("  2) get value from vault")
            print("  3) list available keys in the vault")
            option = int(input("option > "))

            match option:
                case 1:
                    key = input("key  > ")
                    text = input("text > ")
                    assert all(i in printable for i in text)
                    add(vault, user_keys, key, text)
                    print(f"Successfully added the value ({vault[key]})")
                case 2:
                    key = input("key > ")
                    value = get(vault, user_keys, key)
                    print(value)
                case 3:
                    keys = [*vault]
                    print(f"Available keys: {keys}")

            EVALUATION_PERIOD -= 1
            if EVALUATION_PERIOD <= 0:
                print("You used your entire allowance. Goodbye")
                exit(0)

    if __name__ == "__main__":
        main()

    首先大概了解一下 task 在干啥。

    交互库有 admin_key 和 user_key，并且在 vault 里存了经 admin_key 加密的 example 和 flag，example 的明文我们是知道的。

    然后我们交互时：

    1. 用 user_key 加密自己给的一段 plain_text，存到 vault 里，并得到 cipher_text。

    2. 查询 vault 里某一键值对应 cipher_text 经 user_key 解密后的数据。

    3. 查询 vault 里有哪些键值。

    交互次数限制在 5 次。

    发现 admin_key 和 user_key 都是 级别，那么如果 meet in the middle 就是 ，是 级别，爆破可以接受。

    流程就是先用 1 操作随便加密一段，然后用这个密文和自己的明文去求 user_key。

    然后用 2 操作查询 example 密文经 user_key 解密后的假明文，再本地加密得到 example 明文经 admin_key 加密后的密文，用这两个求出 admin_key。

    再用一次 2 操作查询 flag 的密文，操作跟上面同理，key 都知道了，解密出 flag。

    只需要 3 次交互。

    这里 exp 实现上有地方要注意，最后我的实现是这样的：

    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
    def get_key(start,end):
        cipher=[]
        for i in range(2**9):
            cipher.append(AES.new(long_to_bytes(i).ljust(16),AES.MODE_ECB))
        rev=[]
        for k0 in range(2**9):
            s0=cipher[k0].decrypt(end)
            for k1 in range(2**9):
                s1=cipher[k1].decrypt(s0)
                for k2 in range(2**9):
                    rev.append(cipher[k2].decrypt(s1))
        print("11111")
        for up in range(2**3):
            dic={}
            for k0 in range(2**6):
                s0=cipher[k0+up*2**6].encrypt(start)
                for k1 in range(2**9):
                    s1=cipher[k1].encrypt(s0)
                    for k2 in range(2**9):
                        dic[cipher[k2].encrypt(s1)]=((k0+up*2**6)<<18)+(k1<<9)+k2
            print(up)
            for k in range(2**27):
                if(dic.get(rev[k])!=None):
                    return [dic[rev[k]],k]
            print(up)
            del dic

    具体来说在 meet in the middle 的时候，开 大小的 dictionary 并不现实，这样时空开销都不可接受（至少对大部分电脑来说是这样的），我这边最后选择将 拆成 组，分组进行和另一半 check，虽然增加了对另一半的访问次数，但 list 的访问肯定比 dictionary 快得多。

    然后还有个实现细节是 del dic ，因为 clear 操作是不释放内存的，所以我们必须将 dictionary 对象 delete 掉才能保证效率。

    我这里还有个想法是去弄两个 list sort 完再比较，但没实现，不知道会不会更快。

    大概一次要跑 15 分钟到 30 分钟，两次求 key 30 多分钟，还好。

desperate-intern

  • 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
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    import secrets
    from Crypto.Util.Padding import pad, unpad

    FLAG = "fake_flag"

    # Initial permutation table
    IP = [58, 50, 42, 34, 26, 18, 10, 2,
          60, 52, 44, 36, 28, 20, 12, 4,
          62, 54, 46, 38, 30, 22, 14, 6,
          64, 56, 48, 40, 32, 24, 16, 8,
          57, 49, 41, 33, 25, 17, 9, 1,
          59, 51, 43, 35, 27, 19, 11, 3,
          61, 53, 45, 37, 29, 21, 13, 5,
          63, 55, 47, 39, 31, 23, 15, 7]

    # Final permutation table
    FP = [40, 8, 48, 16, 56, 24, 64, 32,
          39, 7, 47, 15, 55, 23, 63, 31,
          38, 6, 46, 14, 54, 22, 62, 30,
          37, 5, 45, 13, 53, 21, 61, 29,
          36, 4, 44, 12, 52, 20, 60, 28,
          35, 3, 43, 11, 51, 19, 59, 27,
          34, 2, 42, 10, 50, 18, 58, 26,
          33, 1, 41, 9, 49, 17, 57, 25]

    # Expansion table
    E = [32, 1, 2, 3, 4, 5,
         4, 5, 6, 7, 8, 9,
         8, 9, 10, 11, 12, 13,
         12, 13, 14, 15, 16, 17,
         16, 17, 18, 19, 20, 21,
         20, 21, 22, 23, 24, 25,
         24, 25, 26, 27, 28, 29,
         28, 29, 30, 31, 32, 1]

    # Permutation table
    P = [16, 7, 20, 21, 29, 12, 28, 17,
         1, 15, 23, 26, 5, 18, 31, 10,
         2, 8, 24, 14, 32, 27, 3, 9,
         19, 13, 30, 6, 22, 11, 4, 25]

    # Permutation choice 1 table
    PC1 = [57, 49, 41, 33, 25, 17, 9,
           1, 58, 50, 42, 34, 26, 18,
           10, 2, 59, 51, 43, 35, 27,
           19, 11, 3, 60, 52, 44, 36,
           63, 55, 47, 39, 31, 23, 15,
           7, 62, 54, 46, 38, 30, 22,
           14, 6, 61, 53, 45, 37, 29,
           21, 13, 5, 28, 20, 12, 4]

    # Permutation choice 2 table
    PC2 = [14, 17, 11, 24, 1, 5,
           3, 28, 15, 6, 21, 10,
           23, 19, 12, 4, 26, 8,
           16, 7, 27, 20, 13, 2,
           41, 52, 31, 37, 47, 55,
           30, 40, 51, 45, 33, 48,
           44, 49, 39, 56, 34, 53,
           46, 42, 50, 36, 29, 32]

    # Number of rotations for each key
    shift_table = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

    # S-boxes (Customizable)
    # Each S-box is a 4x16 matrix
    # S-boxes taken from FIPS 46-3 Appendix 1
    S_BOXES = [
            [0, 1, 2, 3, 4, 5, 6, 7],
            [1, 2, 3, 4, 5, 6, 7, 8],
            [2, 3, 4, 5, 6, 7, 8, 9],
            [3, 4, 5, 6, 7, 8, 9, 10],
            [4, 5, 6, 7, 8, 9, 10, 11],
            [5, 6, 7, 8, 9, 10, 11, 12],
            [6, 7, 8, 9, 10, 11, 12, 13],
            [7, 8, 9, 10, 11, 12, 13, 14]

    ]

    def int_to_64b_bitstring(number):
        b = bin(number)[2:]
        if len(b) != 64:
            b = '0'*(64-len(b)) + b
        return b


    def permute(block, table):
        res = ''
        for i in table:
            res = res + block[i - 1]
        return res

    def rotate_left(key, bits):
        return key[bits:] + key[:bits]

    def generate_round_keys_enc(key):
        round_keys = []
        key = permute(key, PC1)
        left_half = key[:28]
        right_half = key[28:]

        for round_num, shift_bits in enumerate(shift_table):
            left_half = rotate_left(left_half, shift_bits)
            right_half = rotate_left(right_half, shift_bits)
            round_key = permute(left_half + right_half, PC2)
            round_keys.append(round_key)
        return round_keys

    def xor_strings(s1, s2):
        return ''.join(str(int(a) ^ int(b)) for a, b in zip(s1, s2))


    def substitute(expanded_half):
        output = ''
        for i in range(0, len(expanded_half), 6):
            chunk = expanded_half[i:i + 6]
            row = int(chunk[:3], 2)
            col = int(chunk[3:], 2)
            val = S_BOXES[row][col]
            output += format(val, '04b')
        return output

    def feistel_network(right_half, round_key):
        states = []
        expanded_half = permute(right_half, E)
        states.append(expanded_half)
        xored_half = xor_strings(expanded_half, round_key)
        substituted_half = substitute(xored_half)
        permuted_half = permute(substituted_half, P)
        states.append(permuted_half)
        return states

    def des_encrypt(plain_text, key):
        cipher_text = ''
        round_keys = generate_round_keys_enc(key)

        plain_text = permute(plain_text, IP)
        left_half = plain_text[:32]
        right_half = plain_text[32:]

        for round_key in round_keys[:-1]:
            feistel_output = feistel_network(right_half, round_key)
            new_right_half = xor_strings(left_half, feistel_output[-1])
            left_half = right_half
            right_half = new_right_half
        feistel_output = feistel_network(right_half, round_keys[-1])
        new_right_half = xor_strings(left_half, feistel_output[-1])
        left_half = right_half
        right_half = new_right_half

        cipher_text = permute(right_half + left_half, FP)

        return cipher_text, feistel_output

    def des_ecb_encrypt(plain_text, key):
        plain_text = pad(plain_text.encode(), 8)
        cipher_text = ''
        feistel_output = []
        for i in range(0, len(plain_text), 8):
            block = int_to_64b_bitstring(int.from_bytes(plain_text[i:i + 8], 'big'))
            curr_cipher_text, curr_feistel_output = des_encrypt(block, key)
            cipher_text += curr_cipher_text
            feistel_output.append(curr_feistel_output)
        return cipher_text, feistel_output

    def main():
        # keygen
        key = int_to_64b_bitstring(secrets.randbits(64))
        # ciphertext counter
        counter = 16
        # Example usage encrypt
        cipher_text_flag, feistel_output_flag = des_ecb_encrypt(FLAG, key)
        print('Welcome to your homemade supersafe encryption service made by Jack the Intern')
        print('Your credit for encrypted messages is at: ' + str(counter))
        while True:
            command = input('Would you like to get the flag [1], encrypt a message yourself [2] or exit [3] \n>').strip()
            try:
                if command == "1":
                    print("Flag = ", cipher_text_flag)
                    print("Feistel output = ", feistel_output_flag)
                elif command == "2":
                    if counter > 0:
                        counter -= 1
                        data = input('Enter the plaintext you want to encrypt \n>')
                        cipher_text, feistel_output = des_ecb_encrypt(data, key)
                        print("Ciphertext = ", cipher_text)
                        print("Feistel output = ", feistel_output)
                        print("Your credit for encrypted messages is at: " + str(counter))
                    else:
                        print("You have no credits for encrypted messages left.")
                elif command == "3":
                    print("Exiting...")
                    break
                else:
                    print("Please enter a valid input")
            except:
                print("Something went wrong.")


    if __name__ == "__main__":
        main()

    还是先去了解交互库。

    这个实现了一个 des 加密，并且泄漏了最后一次 feistel_network 的结果。

    交互的操作为：

    1. 获取 cipher_text_flag 和 feistel_output_flag。

    2. 传一个 data 过去，获得 cipher_text 和 feistel_output，这个操作限制次数为 16。

    我感觉我做法可能非预期了，我只需要传 1 次明文。

    肯定得把 key 弄出来，重点关注 feistel_network 函数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def feistel_network(right_half, round_key):
        states = []
        expanded_half = permute(right_half, E)
        states.append(expanded_half)
        xored_half = xor_strings(expanded_half, round_key)
        substituted_half = substitute(xored_half)
        permuted_half = permute(substituted_half, P)
        states.append(permuted_half)
        return states

    然后我们相当于知道了 expanded_half 和 permuted_half，那么我们能求出 xored_half。

    这下如果我们能求 substitute 的逆过程的话，我们就能把 round_key 弄出来。

    那跟进 substitute 和 S_BOXES。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    # S-boxes (Customizable)
    # Each S-box is a 4x16 matrix
    # S-boxes taken from FIPS 46-3 Appendix 1
    S_BOXES = [
            [0, 1, 2, 3, 4, 5, 6, 7],
            [1, 2, 3, 4, 5, 6, 7, 8],
            [2, 3, 4, 5, 6, 7, 8, 9],
            [3, 4, 5, 6, 7, 8, 9, 10],
            [4, 5, 6, 7, 8, 9, 10, 11],
            [5, 6, 7, 8, 9, 10, 11, 12],
            [6, 7, 8, 9, 10, 11, 12, 13],
            [7, 8, 9, 10, 11, 12, 13, 14]

    ]

    def substitute(expanded_half):
        output = ''
        for i in range(0, len(expanded_half), 6):
            chunk = expanded_half[i:i + 6]
            row = int(chunk[:3], 2)
            col = int(chunk[3:], 2)
            val = S_BOXES[row][col]
            output += format(val, '04b')
        return output

    一个很有前途的点是，我们一个 val，对应的 row,col 最坏只有 8 种情况，那么所有的就是最多 种，相对来说是非常少的。

    那这样可能的 round_key 也只有这么多种。

    但是，根据 key 生成 round_key 是丢了 8 bit，我们还需要枚举 种，这样就是 种，不太能接受。

    但是，注意到如果我们有多个不同 feistel_ouput 的话，因为 round_key 是不变的，我们每个 feistel_ouput 对应的可能 round_key 求交的话，round_key 的可能就会大大减小。

    实现起来大概 5 个 feistel_ouput 就能确定 round_key 了。

    然后我们只需要传一个长度为 40 的随机明文就能弄到 5 个不同的 feistel_output，操作次数 1。

    最后就是手动写个解密，一点简单的代码而已。