kanon the blog

Black Hat MEA Final 2024 upsolve

  • ~16.25K Words
  1. 1. Black Hat MEA Final 2024
    1. 1.1. Trouble in pairs[crypto 16 solves]
      1. 1.1.1. 問題の要約
      2. 1.1.2. Evalの突破
      3. 1.1.3. まとめると

Black Hat MEA Final 2024

一部記号の乱用・誤用がありますがわざとなので無視してください。

Trouble in pairs[crypto 16 solves]

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
#!/usr/bin/env python3
#
# BlackHat MEA 2024 CTF Finals
#
# [Medium] Crypto - ???
#

# Native imports
import os, json, hashlib
from secrets import randbelow
from typing import List, Tuple

# Non-native dependencies
from Crypto.Util.number import getPrime, inverse, isPrime, GCD     # pip install pycryptodome

# Flag import
FLAG = os.environ.get('DYN_FLAG', 'BHFlagY{506f6c796d65726f5761734865726521}')
if isinstance(FLAG, str):
    FLAG = FLAG.encode()


# Global parameters
HASH = hashlib.sha256
AALP = b"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789[:]"


# Challenge class
class FiatSchnorr:
    def __init__(self, pbit: int, qbit: int) -> None:
        self.p, self.q = self.__SafePrimeGen(pbit, qbit)
        while True:
            self.g = pow(2, (self.p - 1) // self.q, self.p)
            if pow(self.g, self.q, self.p) == 1:
                break
        self.sk = [randbelow(self.q) for _ in '01']
        self.pk = [pow(self.g, i, self.p) for i in self.sk]
        
    def __repr__(self) -> str:
        return json.dumps({
            'p' : '0x' + self.__Int2Byte(self.p).hex(),
            'q' : '0x' + self.__Int2Byte(self.q).hex(),
            'g' : '0x' + self.__Int2Byte(self.g).hex()
        })
    
    def __Int2Byte(self, x: int) -> bytes:
        return x.to_bytes(-(-len(bin(x)[2:]) // 8), 'big')
    
    def __Hash(self, lst: List[int]) -> int:
        return int.from_bytes(HASH(b''.join([self.__Int2Byte(i) for i in lst])).digest(), 'big')
        
    def __SafePrimeGen(self, pbit: int, qbit: int) -> Tuple[int, int]:
        while True:
            q = getPrime(qbit)
            for k in range(256):
                r = getPrime(pbit - qbit - 1)
                p = (2 * q * r) + 1
                if len(bin(p)[2:]) != pbit:
                    continue
                if isPrime(p):
                    return p, q
                
    def __Encode(self, x: Tuple[int]) -> bytes:
        y = [self.__Int2Byte(i) for i in x]
        z = [len(i).to_bytes(2, 'big') + i for i in y]
        return b"".join(z)
    
    def __Decode(self, x: bytes) -> Tuple[int]:
        y = []
        while x:
            l  = int.from_bytes(x[:2], 'big')
            y += [int.from_bytes(x[2:l+2], 'big')]
            x  = x[l+2:]
        return tuple(y)
        
    def Encrypt(self, m: bytes) -> bytes:
        r, s = [randbelow(self.q) for _ in '01']
        A = pow(self.g, r, self.p)
        B = pow(self.g, s, self.p)
        C = (pow(self.pk[0], r, self.p) * int.from_bytes(m, 'big')) % self.p
        D = (pow(self.pk[1], s, self.p) * int.from_bytes(m, 'big')) % self.p
        u, v = [randbelow(self.q) for _ in '01']
        E = pow(self.g, u, self.p)
        F = pow(self.g, v, self.p)
        G = (pow(self.pk[0], u, self.p) * inverse(pow(self.pk[1], v, self.p), self.p)) % self.p
        t = self.__Hash([E, F, G])
        H = (u + t * r) % self.q
        I = (v + t * s) % self.q
        return self.__Encode((A, B, C, D, E, F, G, H, I))
    
    def Decrypt(self, ct: bytes) -> bytes:
        try:
            A, B, C, D, E, F, G, H, I = self.__Decode(ct)
            t = self.__Hash([E, F, G])
            assert pow(self.g, H, self.p) == (E * pow(A, t, self.p)) % self.p
            assert pow(self.g, I, self.p) == (F * pow(B, t, self.p)) % self.p
            assert (pow(self.pk[0], H, self.p) * inverse(pow(self.pk[1], I, self.p), self.p)) % self.p == (G * pow(C * inverse(D, self.p), t, self.p)) % self.p
            return self.__Int2Byte((C * inverse(pow(A, self.sk[0], self.p), self.p)) % self.p)
        except:
            return b""
        

# # Challenge set-up
# HDR = r"""|
# |   ____  ____  _____  __  __  ____  __    ____ 
# |  (_  _)(  _ \(  _  )(  )(  )(  _ \(  )  ( ___)
# |    )(   )   / )(_)(  )(__)(  ) _ < )(__  )__)
# |   (__) (_)\_)(_____)(______)(____/(____)(____)
# |   ____  _  _     ____   __    ____  ____  ___
# |  (_  _)( \( )   (  _ \ /__\  (_  _)(  _ \/ __)
# |   _)(_  )  (     )___//(__)\  _)(_  )   /\__ \
# |  (____)(_)\_)   (__) (__)(__)(____)(_)\_)(___/
# |"""
# print(HDR)

fiat = FiatSchnorr(1024, 1012)
assert b"T3ST" == fiat.Decrypt(fiat.Encrypt(b"T3ST"))
print("|\n|  FIAT = {}".format(fiat))


# Server loop
TUI = "|\n|  Menu:\n|    [L]eak\n|    [E]val\n|    [Q]uit\n|"

while True:
    try:

        print(TUI)
        choice = input('|  > ').lower()

        if choice == 'q':
            print('|\n|  [~] Goodbye ~ !\n|')
            break

        elif choice == 'l':
            leak = fiat.Encrypt(os.urandom(32)).hex()
            print('|\n|  LEAK = {}'.format(leak))

        elif choice == 'e':
            userPacket  = input('|\n|  > (hex) ')
            userDecrypt = fiat.Decrypt(bytes.fromhex(userPacket))
			if all([i in AALP for i in userDecrypt]):
                response = eval(userDecrypt.decode())
            else:
                raise Exception('Invalid decryption')
            print('|\n|  RESP = {}'.format(fiat.Encrypt(response).hex()))

        else:
            print('|\n|  [!] Invalid choice.')

    except KeyboardInterrupt:
        print('\n|\n|  [~] Goodbye ~ !\n|')

    except Exception as e:
        print('|\n|  [!] ERROR :: {}'.format(e))

問題の要約

1
2
3
4
5
6
7
8
9
10
11
12
elif choice == 'l':
    leak = fiat.Encrypt(os.urandom(32)).hex()
    print('|\n|  LEAK = {}'.format(leak))

elif choice == 'e':
    userPacket  = input('|\n|  > (hex) ')
    userDecrypt = fiat.Decrypt(bytes.fromhex(userPacket))
    if all([i in AALP for i in userDecrypt]):
        response = eval(userDecrypt.decode())
    else:
        raise Exception('Invalid decryption')
    print('|\n|  RESP = {}'.format(fiat.Encrypt(response).hex()))

公開鍵として、$p,q,g$が与えられ、その後何回でも使える2つの選択肢「Leak, Eval」与えられえます。

  • Leakは適当に選ばれた平文に対するFiatSchnorr暗号の暗号文を返却します。ただ、ここで選ばれた平文は具体的に何なのかはわかりません。
  • Evalは入力された復号を行い、エラーが起きなければ復号した結果＝平文をeval()に入れて実行してくれます。

ここで、FiatSchnorr暗号はなんなのか見ていきます。コードとしては以下になりますが、数式に起こして簡単化していきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Encrypt(self, m: bytes) -> bytes:
    r, s = [randbelow(self.q) for _ in '01']
    A = pow(self.g, r, self.p)
    B = pow(self.g, s, self.p)
    C = (pow(self.pk[0], r, self.p) * int.from_bytes(m, 'big')) % self.p
    D = (pow(self.pk[1], s, self.p) * int.from_bytes(m, 'big')) % self.p
    u, v = [randbelow(self.q) for _ in '01']
    E = pow(self.g, u, self.p)
    F = pow(self.g, v, self.p)
    G = (pow(self.pk[0], u, self.p) * inverse(pow(self.pk[1], v, self.p), self.p)) % self.p
    t = self.__Hash([E, F, G])
    H = (u + t * r) % self.q
    I = (v + t * s) % self.q
    return self.__Encode((A, B, C, D, E, F, G, H, I))

$$ A = g^r,B=g^s, C=Pk_0^r*m, D=Pk_1^s*m, E=g^u, F=g^v$$
$$ G=pk_0^u*PK_1^{-v}, t=Hash(E,F,G), H=u+t*r, I=v+t*s $$

という10本の式ができました。登場人物としては、$g$は初めに共有された値、$r,s,u,v$はその場で決まるランダムな値、$m$は平文、暗号文は$A,B,C,D,E,F,G,H,I$です。ただ、$Pk_i$は公開鍵ですが今回は具体的な値はわかりません。

この時、$Pk_i$がわかってないので、$C,D$の値を私たちが構成できません…omg悲しいですね…

では、これの何が数学的な脆弱性or実装の脆弱性なんでしょうか？それを考える前に、一つこれがAES, RSAなどとは違う点を先に考えてみます。

これは簡単で、同じ平文を暗号化するたびに暗号文の値が変化します。これが大きな違いです。$r,s,u,v$はその場で決まるランダムな値なために起こることですね。

ということは、こちらで制御できる可能性ってあるにはあるんですよね。。。例えば、$$A = g^r$$を例にとって考えます。$A^x$の値が欲しいなと思った時は右辺の値をどうすればよいですか…?

$$A^x = (g^r)^x=g^{xr}$$でいいわけです。ということは、$A$に対して$x$を操作することで、$r$に大きな影響が出そうですよね？

とはいってもです。$xr$の値が分かるというわけではないです。$$g^{xr}$$がわかるということです。

じゃあどうすればよいか？わからないなら消せばいいじゃないかです。掛け算で全てを無に帰す最強の数がありますよね？そう、$0$です。なので、$r=0$とすると$$A^x=g^{xr}=g^{0*r}=1$$より間接的に$r$の影響を無視することができます！！

では、この話を全ての乱数に適応すると？？

$$A = 1\B=1\C=m\D=m\E=1\F=1\G=1*1\t=Hash(E,F,G)\H=0\I=0$$

になりますね？？、オーマイが、$C=m$よりさっきは作ることが難しかったですが、今回は簡単に作れそうですね！なので、平文$m$に対して、暗号文は$(1,1,m,m,1,1,0,0)$というばかげた話になります。

やった、これで第一段階突破！

Evalの突破

次は、Eval関数をうまく使ってFlagを何とかしようぜってことです。

1
2
3
4
5
6
7
8
elif choice == 'e':
    userPacket  = input('|\n|  > (hex) ') #暗号文の入力16進数の文字列で
    userDecrypt = fiat.Decrypt(bytes.fromhex(userPacket)) #暗号文を復号し平文を得る
    if all([i in AALP for i in userDecrypt]): #平文がすべて許された文字で構成されているのか確認
        response = eval(userDecrypt.decode()) #問題ないのであれば、平文をpythonの変数として解釈
    else:
        raise Exception('Invalid decryption') #問題あるのであればエラーを返す
    print('|\n|  RESP = {}'.format(fiat.Encrypt(response).hex())) #解釈したものを暗号化し、表示する

eval(userDecrypt.decode())とあるので、例えば私たちが送る暗号文をFlag[0]とすると、eval(Flag[0])ではFlagに格納している先頭文字列が返却されます。なので、responseに入る文字列はBとなりますが…

んーーー、これresponseに入った結果を再度暗号化してるじゃないか...え、どうしよ案件です。

ここで、最初の問題のコードに立ち戻ります、私達が情報を得ることができるものって何がありますか？？ということです。

1
2
3
4
print('|\n|  LEAK = {}'.format(leak)) # leakの結果
print('|\n|  RESP = {}'.format(fiat.Encrypt(response).hex())) # evalの暗号化結果
except Exception as e:
    print('|\n|  [!] ERROR :: {}'.format(e)) # 全体でエラーをはいた結果

この3つがprintのの中に変数を格納して結果を返してくれるやつです。

あれ、無理やりエラーを吐かせれば3つ目のもので結果得られるんじゃね？？omg

でも無理やりとはいってもどの場所ではかっせかなぁです。

吐かせる場所はここです。

1
response = eval(userDecrypt.decode())

仮に、平文が”abc”とするとeval(abc)した結果は、name 'abc' is not definedより、エラーからevalの内容がわかるということです。

ただ数値の場合は、 cannot convert 'int' object to bytesという怒られ方をしてます。これはエラーの吐く場所が違いますが結果は使えないので無視します。

まとめると

  1. ある平文を$(1,1,m,m,1,1,0,0)$で暗号文を偽装
  2. 平文はflag[:3]といった形をとれば、eval(flag[:3])はBHFと変えてくれます（Flagに格納されている文字列の先頭3bytes）が、私たちが見れるものは暗号化が施されている…
  3. 2の暗号文を見破るためにerror based oracleを構成し、flagの文字列を得る
  4. Good Game yay!!

宿題

この最後のエラー部分がなくなった場合はどう解くのだろうか？？

予想solve数[13-14]程度(2減)

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
#!/usr/bin/env python3
#
# BlackHat MEA 2024 CTF Finals
#
# [Medium] Crypto - ???
#

# Native imports
import os, json, hashlib
from secrets import randbelow
from typing import List, Tuple

# Non-native dependencies
from Crypto.Util.number import getPrime, inverse, isPrime, GCD     # pip install pycryptodome

# Flag import
FLAG = os.environ.get('DYN_FLAG', 'BHFlagY{506f6c796d65726f5761734865726521}')
if isinstance(FLAG, str):
    FLAG = FLAG.encode()


# Global parameters
HASH = hashlib.sha256
AALP = b"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789[:]"


# Challenge class
class FiatSchnorr:
    def __init__(self, pbit: int, qbit: int) -> None:
        self.p, self.q = self.__SafePrimeGen(pbit, qbit)
        while True:
            self.g = pow(2, (self.p - 1) // self.q, self.p)
            if pow(self.g, self.q, self.p) == 1:
                break
        self.sk = [randbelow(self.q) for _ in '01']
        self.pk = [pow(self.g, i, self.p) for i in self.sk]
        
    def __repr__(self) -> str:
        return json.dumps({
            'p' : '0x' + self.__Int2Byte(self.p).hex(),
            'q' : '0x' + self.__Int2Byte(self.q).hex(),
            'g' : '0x' + self.__Int2Byte(self.g).hex()
        })
    
    def __Int2Byte(self, x: int) -> bytes:
        return x.to_bytes(-(-len(bin(x)[2:]) // 8), 'big')
    
    def __Hash(self, lst: List[int]) -> int:
        return int.from_bytes(HASH(b''.join([self.__Int2Byte(i) for i in lst])).digest(), 'big')
        
    def __SafePrimeGen(self, pbit: int, qbit: int) -> Tuple[int, int]:
        while True:
            q = getPrime(qbit)
            for k in range(256):
                r = getPrime(pbit - qbit - 1)
                p = (2 * q * r) + 1
                if len(bin(p)[2:]) != pbit:
                    continue
                if isPrime(p):
                    return p, q
                
    def __Encode(self, x: Tuple[int]) -> bytes:
        y = [self.__Int2Byte(i) for i in x]
        z = [len(i).to_bytes(2, 'big') + i for i in y]
        return b"".join(z)
    
    def __Decode(self, x: bytes) -> Tuple[int]:
        y = []
        while x:
            l  = int.from_bytes(x[:2], 'big')
            y += [int.from_bytes(x[2:l+2], 'big')]
            x  = x[l+2:]
        return tuple(y)
        
    def Encrypt(self, m: bytes) -> bytes:
        r, s = [randbelow(self.q) for _ in '01']
        A = pow(self.g, r, self.p)
        B = pow(self.g, s, self.p)
        C = (pow(self.pk[0], r, self.p) * int.from_bytes(m, 'big')) % self.p
        D = (pow(self.pk[1], s, self.p) * int.from_bytes(m, 'big')) % self.p
        u, v = [randbelow(self.q) for _ in '01']
        E = pow(self.g, u, self.p)
        F = pow(self.g, v, self.p)
        G = (pow(self.pk[0], u, self.p) * inverse(pow(self.pk[1], v, self.p), self.p)) % self.p
        t = self.__Hash([E, F, G])
        H = (u + t * r) % self.q
        I = (v + t * s) % self.q
        return self.__Encode((A, B, C, D, E, F, G, H, I))
    
    def Decrypt(self, ct: bytes) -> bytes:
        try:
            A, B, C, D, E, F, G, H, I = self.__Decode(ct)
            t = self.__Hash([E, F, G])
            assert pow(self.g, H, self.p) == (E * pow(A, t, self.p)) % self.p
            assert pow(self.g, I, self.p) == (F * pow(B, t, self.p)) % self.p
            assert (pow(self.pk[0], H, self.p) * inverse(pow(self.pk[1], I, self.p), self.p)) % self.p == (G * pow(C * inverse(D, self.p), t, self.p)) % self.p
            return self.__Int2Byte((C * inverse(pow(A, self.sk[0], self.p), self.p)) % self.p)
        except:
            return b""
        

# # Challenge set-up
# HDR = r"""|
# |   ____  ____  _____  __  __  ____  __    ____ 
# |  (_  _)(  _ \(  _  )(  )(  )(  _ \(  )  ( ___)
# |    )(   )   / )(_)(  )(__)(  ) _ < )(__  )__)
# |   (__) (_)\_)(_____)(______)(____/(____)(____)
# |   ____  _  _     ____   __    ____  ____  ___
# |  (_  _)( \( )   (  _ \ /__\  (_  _)(  _ \/ __)
# |   _)(_  )  (     )___//(__)\  _)(_  )   /\__ \
# |  (____)(_)\_)   (__) (__)(__)(____)(_)\_)(___/
# |"""
# print(HDR)

fiat = FiatSchnorr(1024, 1012)
assert b"T3ST" == fiat.Decrypt(fiat.Encrypt(b"T3ST"))
print("|\n|  FIAT = {}".format(fiat))


# Server loop
TUI = "|\n|  Menu:\n|    [L]eak\n|    [E]val\n|    [Q]uit\n|"

while True:
    try:

        print(TUI)
        choice = input('|  > ').lower()

        if choice == 'q':
            print('|\n|  [~] Goodbye ~ !\n|')
            break

        elif choice == 'l':
            leak = fiat.Encrypt(os.urandom(32)).hex()
            print('|\n|  LEAK = {}'.format(leak))

        elif choice == 'e':
            userPacket  = input('|\n|  > (hex) ')
            userDecrypt = fiat.Decrypt(bytes.fromhex(userPacket))
			if all([i in AALP for i in userDecrypt]):
                response = eval(userDecrypt.decode())
            else:
                raise Exception('Invalid decryption')
            print('|\n|  RESP = {}'.format(fiat.Encrypt(response).hex()))

        else:
            print('|\n|  [!] Invalid choice.')

    except KeyboardInterrupt:
        print('\n|\n|  [~] Goodbye ~ !\n|')

    except Exception as e:
        print('|\n|  [!] ERROR Then Goodbye ~ !\n|')

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.