[CSAW CTF Qualification Round 2017] - Another Xor (Crypto 100)

發表於 | 分類於 |

題目資訊

Hey, hey can you find my secret.

UPDATE 10:13 Eastern: the flag is whatever is in sys.argv[2]

cipher.py
encrypted

解法

題目給了加密方法跟加密過後的密文
cipher.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import hashlib
import sys
def xor(s1,s2):
    return ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(s1,s2))
def repeat(s, l):
    return (s*(int(l/len(s))+1))[:l]
key = sys.argv[1]
plaintext = sys.argv[2] + key
plaintext += hashlib.md5(plaintext).hexdigest()
cipher = xor(plaintext, repeat(key, len(plaintext)))
print cipher.encode('hex')

encrypted:

1
274c10121a0100495b502d551c557f0b0833585d1b27030b5228040d3753490a1c025415051525455118001911534a0052560a14594f0b1e490a010c4514411e070014615a181b02521b580305170002074b0a1a4c414d1f1d171d00151b1d0f480e491e0249010c150050115c505850434203421354424c1150430b5e094d144957080d4444254643

分析一下cipher.py，可知：

1
2
3
flag = sys.argv[2]
key = sys.argv[1]
plaintext = flag + key + hashlib.md5(flag + key).hexdigest()

找出 flag 跟 key 的長度

先找 flag 跟 key 的長度可以確定兩者在 plaintext 位置。
因為 plaintext 裡有 key ，又是用 key 做 xor 加密，所以在 ciphertext 必定有一段全 xor 起來會是 0 ！
原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
假設：
flag length = 3
key length = 7
plaintext = flag + key (=> plaintext length = 10)
則：
ciphertext[0] = plaintext[0] ^ key[0]
ciphertext[1] = plaintext[1] ^ key[1]
ciphertext[2] = plaintext[2] ^ key[2]
ciphertext[3] = plaintext[3] ^ key[3] = key[0] ^ key[3]
ciphertext[4] = plaintext[4] ^ key[4] = key[1] ^ key[4]
ciphertext[5] = plaintext[5] ^ key[5] = key[2] ^ key[5]
ciphertext[6] = plaintext[6] ^ key[6] = key[3] ^ key[6]
ciphertext[7] = plaintext[7] ^ key[0] = key[4] ^ key[0]
ciphertext[8] = plaintext[8] ^ key[1] = key[5] ^ key[1]
ciphertext[9] = plaintext[9] ^ key[2] = key[6] ^ key[3]
顯然
ciphertext[3] ^ ciphertext[4] ^ ... ^ ciphertext[9] = 0
key length = 9 - 3 + 1 = 7
flag length = 10 - 7 = 3

如此就能寫個 script 來找 key length 了。由於 md5 的部分不重要，所以可以先拿掉，再來對 ciphertext 從後面往前一直做 xor ，直到 xor 為 0。

1
2
3
4
5
6
7
8
9
10
11
12
encrypted = '274c10121a0100495b502d551c557f0b0833585d1b27030b5228040d3753490a1c025415051525455118001911534a0052560a14594f0b1e490a010c4514411e070014615a181b02521b580305170002074b0a1a4c414d1f1d171d00151b1d0f480e491e0249010c150050115c505850434203421354424c1150430b5e094d144957080d4444254643'
cipher_and_key = encrypted[:-64].decode('hex') # eliminate md5 part
xor_all = 0
for i in range(len(cipher_and_key) - 1, -1, -1):
    xor_all ^= ord(cipher_and_key[i])
    if xor_all == 0:
        flag_len = i
        key_len = len(cipher_and_key) - i
        print 'flag length:', flag_len  # 38
        print 'key length:', key_len    # 67
        break

解得
flag length = 38
key length = 67

解出 key

直接拿題目解出長度的情形來說明：

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
已知：
ciphertext
plaintext = flag + key
plaintext length = 105
已算出：
flag length = 38
key length = 67
則可知：
ciphertext[ 0] = plaintext[ 0] ^ key[ 0]
ciphertext[ 1] = plaintext[ 1] ^ key[ 1]
...
ciphertext[37] = plaintext[37] ^ key[37]
ciphertext[38] = plaintext[38] ^ key[38] = key[ 0] ^ key[38]
ciphertext[39] = plaintext[39] ^ key[39] = key[ 1] ^ key[39]
...
ciphertext[66] = plaintext[66] ^ key[66] = key[28] ^ key[66]
ciphertext[67] = plaintext[67] ^ key[ 0] = key[29] ^ key[ 0]
ciphertext[68] = plaintext[68] ^ key[ 1] = key[30] ^ key[ 1]
...
ciphertext[76] = plaintext[76] ^ key[ 9] = key[38] ^ key[ 9]
...
ciphertext[104] = plaintext[104] ^ key[37] = key[66] ^ key[37]
若已知 key[0] ，則可以計算出 key[38] (key[38] = ciphertext[38] ^ key[0])
=> 已知 key[38] ，則可以計算出 key[9] (key[9] = ciphertext[76] ^ key[38])
=> 已知 key[9] ，則可以計算出 key[47] (key[47] = ciphertext[47] ^ key[9])
=> ...

因此只要給定一個 key[0] ，全部跑完就能得到完整 key 了，又 flag 開頭應該是 'flag{' ，所以可以由 ciphertext[0] ^ ord('f') 得到 key[0] 。

解完 key 再對 ciphertext 做一次 xor 就可以了解得 flag 了！

解答 script

完整的script如下：

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
import hashlib
import sys
def xor(s1,s2):
    return ''.join(chr(ord(a) ^ ord(b)) for a,b in zip(s1,s2))
def repeat(s, l):
    return (s*(int(l/len(s))+1))[:l]
encrypted = '274c10121a0100495b502d551c557f0b0833585d1b27030b5228040d3753490a1c025415051525455118001911534a0052560a14594f0b1e490a010c4514411e070014615a181b02521b580305170002074b0a1a4c414d1f1d171d00151b1d0f480e491e0249010c150050115c505850434203421354424c1150430b5e094d144957080d4444254643'
cipher_and_key = encrypted[:-64].decode('hex')
xor_all = 0
for i in range(len(cipher_and_key) - 1, -1, -1):
    xor_all ^= ord(cipher_and_key[i])
    if xor_all == 0:
        flag_len = i
        key_len = len(cipher_and_key) - i
        print 'flag length:', flag_len  # 38
        print 'key length:', key_len    # 67
        break
xored_flag = cipher_and_key[:flag_len]
xored_key = cipher_and_key[flag_len:]
key_num_lst = [0] * key_len
# flag may start with 'flag{', and we only need the first letter
key_num_lst[0] = ord('f') ^ ord(xored_flag[0])
# calc shift and get flag
shift = key_len - flag_len
pre_idx = 0
idx = (pre_idx + shift) % key_len
while key_num_lst[idx] == 0:
    key_num_lst[idx] = key_num_lst[pre_idx] ^ ord(xored_key[idx])
    pre_idx = idx
    idx = (pre_idx + shift) % key_len
key = ''.join(map(chr, key_num_lst))
print 'key:', key
flag = xor(xored_flag, repeat(key, len(xored_flag)))
print 'flag:', flag

解得
key: A quart jar of oil mixed with zinc oxide makes a very bright paint|
flag: flag{sti11_us3_da_x0r_for_my_s3cratz}|