发布于 

AES-hamming

复盘一道cybrics的密码题。

题目

题目提到数据发生了错误，但需要我们进行纠错，纠错用上了汉明码。

题目源码如下

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
#!/usr/bin/python3.7
import hashlib
import os

from Crypto.Cipher import AES


NUM_REDUNDANT_BITS = 7


def pos_redundant_bits(data, r):
    # Place redundancy bits to the positions of the power of 2
    j = 0
    k = 1
    m = len(data)
    res = ''

    # Insert '0' to the positions of the power of 2
    for i in range(1, m + r + 1):
        if (i == 2 ** j):
            res = res + '0'
            j += 1
        else:
            res = res + data[-1 * k]
            k += 1
    #res= r0 r1 s-1 r2 s-2
    return res[::-1]
    #res=s-2 r 2 s-1 r 1 r 0 共127
    #    122 123 124 125 126
  
def calc_parity_bits(arr, r):
    n = len(arr)

    # Searching for r parity bit
    for i in range(r):
        val = 0
        for j in range(1, n + 1):

            # If position has 1 in ith significant
            # position then Bitwise OR the array value
            # to find parity bit value.
            if (j & (2 ** i) == (2 ** i)):
                val = val ^ int(arr[-1 * j])
                # -1 * j is given since array is reversed

        # String Concatenation
        # (0 to n - 2^r) + parity bit + (n - 2^r + 1 to n)
        arr = arr[:n - (2 ** i)] + str(val) + arr[n - (2 ** i) + 1:]
    return arr


def calc_final_parity(arr):
    # Add a parity bit to the last bit of 128b string
    return "0" if arr.count("1") % 2 == 0 else "1"


def hamming_encode_block(block):
    bin_block = ''.join([bin(bt)[2:].zfill(8) for bt in block])
    arr = pos_redundant_bits(bin_block, NUM_REDUNDANT_BITS)
    arr = calc_parity_bits(arr, NUM_REDUNDANT_BITS)
    arr += calc_final_parity(arr)
    return arr


if __name__ == "__main__":
    import sys
    if len(sys.argv) < 4:
        print("Usage: python tothemoon_encrypt.py <src filename> <dest filename> <password>")
        exit()

    flag = open(sys.argv[1], "rb").read()
    password = hashlib.md5(sys.argv[3].encode()).digest()
    iv = os.urandom(16)

    binary_blocks = []

    # Encode each 128b block with hamming 120/7 and add a parity bit
    while len(flag):
        current_block = flag[:15]
        if len(flag[15:]) == 0:
            current_block += b'\x00' * (15 - len(current_block) % 15)
        flag = flag[15:]

        binary_blocks.append(hamming_encode_block(current_block))

    binary_flag = "".join(binary_blocks)
    encoded_flag = bytes(int(binary_flag[i : i + 8], 2) for i in range(0, len(binary_flag), 8))

    encryptor = AES.new(password, AES.MODE_CBC, IV=iv)
    encrypted_flag = encryptor.encrypt(encoded_flag)
    secret_data = iv + encrypted_flag

    with open(sys.argv[2], "wb") as w:
        w.write(secret_data)

tothemoon.jpg.enc

（附图如上）

赛中回想

题目大致意思理清了和使用的算法都明晰了，但出现了几个疑问：

  1. 到底错误出现在原图上还是传输中；
  2. 这道题到底要不要爆破；
  3. 15字节内最多一个错误到底怎么用。

然后，就没啦。

赛后复盘

直接粘复盘记录过来。

题目提示主要是用hamming码纠错。

目前情况如下：

  1. 汉明码纠错将一组120bit即15字节转换为16字节，能纠正一位错误或检测两位错误2.对出错位置进行了分析，发现共有0xc8a组，其中错误有128处，有一组错误并自动纠错71组，能检测出两组错误的有57组，且所有错误均分布于0x404之前。

  2. 目前能识读的文段为G3nTl3_4Nd_5oFt_3RroR5_R4T3}

  3. 想到，既然题目说每15个字节最多1处错误，能不能直接按字节枚举错误的划分方式，这样的话，在同一段汉明码内如果出现了两个错误，必然分别出现在两段之内，似乎可以降低复杂度。啊啊啊写不出来wwww

复盘1：看到WM说通过枚举坏块然后去掉的方式可做，但这种方法根本就没用上题目信息啊啊啊，整合一下出来是这个图

不太认WM的这个做法。

复盘2，原来题目考点是CBC比特反转。

首先，错误到底发生在了哪。答：发生在了密文传输的过程中，本质还是在考AES

其次，错误是怎么产生的。答：原文提到降低到每15字节最多发生一个比特翻转，这句话的实际表达居然是每十六字节一个错误。

再次，怎么判定错误发生在传输而不是明文本身。答：检查出现双错误的字节，发现有连续三个的双错误字节，而其最多只能含有3*16//15+2=5个错误，说明明文本身错误这个假设不成立。

再者，为什么才来复盘。答：意识到是AES本身的错误后，这几天一直在重学CBC翻转攻击，然后开始纠正，但因为对封装好的AES认识不到位，把前边的密文直接作为iv使用导致了奇怪的错误，用了两天重写脚本用统一的iv解决的。

脚本：

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

import hashlib
import os
from Crypto.Cipher import AES
passwd=hashlib.md5("superpass".encode()).digest()
f=open('/home/zuni-w/Desktop/tothemoon.jpg.enc','rb' )
s=f.read()
f.close()
passwd=hashlib.md5("superpass".encode("utf-8")).digest()
iv=s[:16]
enc=AES.new(passwd,AES.MODE_CBC,iv)
cipher=s[16:]
text=enc.decrypt(cipher)
block=[]
ans_block=[]
ed=[]
ink=0
def ham(data):
    m=data
    k=0
    for i in range(1,128):
        for j in range(7):
            k^=((int(m[-i])&(i>>j))<<j)
    return k
def change(data):
    t=''
    m=data
    for i in range(1,len(m)+1):
        if i not in [1,2,4,8,16,32,64]:
            t=m[-i]+t
    return t
while len(text):
    cur=text[:16]
    text=text[16:]
    ar="".join([bin(bt)[2:].zfill(8) for bt in cur])
    lb=ar[:-1]
    ar=ar[:-1]
    block.append(ar)
    ed.append(lb)
    ex=change(ar)
    ans_block.append(ex)
for i in range(len(ans_block)-1,0,-1):
    co=127-ham(block[i])
    
    if co!=127:
        if str(block[i].count('1')%2)==ed[i]:
            print("wrong")

        ar=block[i][:co]+str(1-int(block[i][co]))+block[i][co+1:]
        block[i]=ar
        ans_block[i]=change(ar)
        print(bytes(int(ans_block[i][j:j+8],2) for j in range(0,len(ans_block[i]),8)))
        pad=(i-1)*16
        eb=cipher[pad:pad+16]
        fb="".join([bin(bt)[2:].zfill(8) for bt in eb])
        fb=fb[:co]+str(1-int(fb[co],2))+fb[co+1:]
        fb=bytes(int(fb[i:i+8],2) for i in range(0,len(fb),8))
        rt=enc.decrypt(cipher[:pad]+fb+cipher[pad+16:])
        rb=rt[pad:pad+16]
        ar="".join([bin(bt)[2:].zfill(8) for bt in rb])
        nlb=ar[-1]
        ar=ar[:-1]
        block[i-1]=ar
        ans_block[i-1]=change(ar)
        ed[i-1]=nlb


ansf="".join(ans_block)
ans=bytes(int(ansf[i:i+8],2) for i in range(0,len(ansf),8))
ans=ans.rstrip(b'\00')
f=open('/home/zuni-w/Desktop/tothemoon.jpg','wb' )
f.write(ans)
f.close()

（所以WM那帮人是怎么看出来这个V3rY的)

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站由 [@Zuni](http://example.com/) 创建，使用 Stellar 作为主题。