07.crypto @EVMEnc
2023-06-29 15:54:40 # 02.ChainflagCTF

crypto(EVMEnc)

contract

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
pragma solidity ^0.5.10;

contract EVMEnc {

uint public result;
string public key;

uint private delta;
uint public output;

uint32 public sum;
uint224 private tmp_sum=0;

uint32 private key0;
uint224 private t0=0;
uint32 private key1;
uint224 private t1=0;
uint32 private key2;
uint224 private t2=0;
uint32 private key3;
uint224 private t3=0;

constructor() public {
delta = 0xb3c6ef3720;
}

function Convert(string memory source) public pure returns (uint result) {
bytes32 tmp;
assembly {
tmp := mload(add(source, 32))
}
result = uint(tmp) / 0x10000000000000000;
}

function set_key(string memory tmp) public {
key = tmp;
}

function cal_(uint x) public {
uint tmp = Convert(key) / 0x10000000000000000;
result = tmp % x;
}

function Encrypt(string memory flag) public {
uint tmp = Convert(flag);
uint key_tmp = Convert(key) / 0x10000000000000000;
assembly {
let first,second
sstore(5, and(shr(96, key_tmp), 0xffffffff))
sstore(6, and(shr(64, key_tmp), 0xffffffff))
sstore(7, and(shr(32, key_tmp), 0xffffffff))
sstore(8, and(key_tmp, 0xffffffff))

let step := 1
for { let i := 1 } lt(i, 4) { i := add(i, 1) } {

first := and(shr(mul(add(sub(24, mul(i, 8)), 4), 8), tmp), 0xffffffff)
second := and(shr(mul(sub(24, mul(i, 8)), 8), tmp), 0xffffffff)

sstore(4, 0)

for {let j := 0 } lt(j, 32) { j := add(j, 1) } {

sstore(4, and(add(and(sload(4), 0xffffffff), shr(5, sload(2))), 0xffffffff))

let tmp11 := and(add(and(mul(second, 16), 0xffffffff), and(sload(5), 0xffffffff)), 0xffffffff)
let tmp12 := and(add(second, and(sload(4),0xffffffff)), 0xffffffff)
let tmp13 := and(add(div(second, 32), and(sload(6),0xffffffff)), 0xffffffff)

first := and(add(first, xor(xor(tmp11, tmp12), tmp13)), 0xffffffff)

let tmp21 := and(add(and(mul(first, 16), 0xffffffff), and(sload(7),0xffffffff)), 0xffffffff)
let tmp22 := and(add(first, and(sload(4),0xffffffff)), 0xffffffff)
let tmp23 := and(add(div(first, 32), and(sload(8),0xffffffff)), 0xffffffff)
second := and(add(second, xor(xor(tmp21, tmp22), tmp23)), 0xffffffff)

}

sstore(3, add(sload(3), add(shl(sub(192, mul(step, 32)), first), shl(sub(192, mul(i, 64)), second))))
step := add(step, 2)
}

}
}
}

info.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
transaction

1.
0x81200224..................

2.
0xffdd8131000000000000000000000000000000000000000000003100e35e552c1273c959
sload(0) = 208645382789328542577309

3.
0xffdd8131000000000000000000000000000000000000000000001ac3243c9e81ba850045
sload(0) = 29341064342757093333104

4.
0xffdd8131000000000000000000000000000000000000000000005ce6a91010e307946b87
sload(0) = 227103917449451505785192

5.
0xe6dc28ae..................
sload(3) = 1970527074032043059410457910532573615730510348629701619382

analyses

0.

1
2
3
4
5
6
7
function Convert(string memory source) public pure returns (uint result) {
bytes32 tmp;
assembly {
tmp := mload(add(source, 32))
}
result = uint(tmp) / 0x10000000000000000;
}
  1. add(source, 32): Move the pointer of the source string to the start position of its actual data (in Solidity, the first 32 bytes of the string store its length)
  2. mload(add(source, 32)): Load 32 bytes from memory, so tmp now contains the first 32 bytes of the source string
  3. result = uint(tmp) / 0x10000000000000000: This converts tmp to an unsigned integer and performs a division operation. 0x1000000000000000 is the 16th power of 16, which is equivalent to shifting the 256 bit byte sequence to the right by 64 bits. This converts the original bytes32 variable to the first 192 bits of uint. If the length of the input string exceeds 24 bytes (because each byte has 8 bits, 24 bytes are equal to 192 bits), the function will discard the excess.

1

1
0x81200224..................

It is obvious that it is a function selector, it is the result of keccak256("set_key(string)");:

1
2
3
function set_key(string memory tmp) public {
key = tmp;
}

we only know the msg.sender call the set_key(), but he hides the parameter.

2.

1
2
3
4
5
6
7
8
9
10
11
2.
0xffdd8131000000000000000000000000000000000000000000003100e35e552c1273c959
sload(0) = 208645382789328542577309

3.
0xffdd8131000000000000000000000000000000000000000000001ac3243c9e81ba850045
sload(0) = 29341064342757093333104

4.
0xffdd8131000000000000000000000000000000000000000000005ce6a91010e307946b87
sload(0) = 227103917449451505785192

The 2.3.4 of the info.txt is the result of keccak256("cal_(uint256)");:

1
2
3
4
function cal_(uint x) public {
uint tmp = Convert(key) / 0x10000000000000000;
result = tmp % x;
}

sload(0) returns the content of slot(0), it is result in this contract.

3.

1
2
3
5.
0xe6dc28ae..................
sload(3) = 1970527074032043059410457910532573615730510348629701619382

0xe6dc28ae is the result of keccak256("Encrypt(string)"). sload(3) returns the content of slot(3), it is output in this contract.

4.

Now we know what happened in the info.txt:

1
2
3
4
5
6
7
8
9
10
transaction
1.set_key(string memory tmp)
2.cal_(uint 0x3100e35e552c1273c959)
result = 0x2c2eb0597447608b329d
3.cal_(uint 0x1ac3243c9e81ba850045)
result = 0x6369510a41dbcbed870
4.cal_(uint 0x5ce6a91010e307946b87)
result = 0x301753fa0827117d1968
5.Encrypt(string memory flag)
output =0x505d433947f27742f60b06f350f2583450a1f7221380eeb6

This level is an encryption and decryption question constructed using Solidity language. The question sets an unknown key value and then calls cal_ three times. In the end, we need to get the parameter of Encrypt by the output.

5.

The cal_ can be understood as taking remainder:

1
2
3
0x2c2eb0597447608b329d = tmp % 0x3100e35e552c1273c959
0x6369510a41dbcbed870 = tmp % 0x1ac3243c9e81ba850045
0x301753fa0827117d1968 = tmp % 0x5ce6a91010e307946b87

We can infer tmp by “中国剩余定律”, the result is: tmp=0x6b65795f746869735f69735f6b65795f

6.

Let’s analyses Encrypt():

1
2
3
4
5
6
7
8
uint tmp = Convert(flag);
uint key_tmp = Convert(key) / 0x10000000000000000;
assembly {
let first,second
sstore(5, and(shr(96, key_tmp), 0xffffffff))
sstore(6, and(shr(64, key_tmp), 0xffffffff))
sstore(7, and(shr(32, key_tmp), 0xffffffff))
sstore(8, and(key_tmp, 0xffffffff))
  • uint key_tmp = Convert(key) / 0x10000000000000000;: this is the value of tmp we calculate before: 0x6b65795f746869735f69735f6b65795f
  • sstore(5, and(shr(96, key_tmp), 0xffffffff)): storage[5] := v, it equal to that:
1
v = (0x6b65795f746869735f69735f6b65795f >> 96) & 0xffffffff

sstore 6,7,8 is the same theory as sstore 5, in the end, we get:

1
2
3
4
5
6
7
8
tmp = flag  #Convert(flag)  48 hex
key_tmp =0x6b65795f746869735f69735f6b65795f
sstore5 = 0x6b65795f
sstore6 = 0x74686973
sstore7 = 0x5f69735f
sstore8 = 0x6b65795f
sstore2 = 0xb3c6ef3720 #delta = 0xb3c6ef3720;
sstore3 = 0 # not initalize

7.

之前所求的tmp就是这里的key_tmp,那么存储在storage[5]到storage[8]都是固定值可以直接求出。后续部分用到的sload(2)是取storage[2]的值,按照源码分析对应的是变量delta=0xb3c6ef3720。storage[3]对应的output用来存储结果,由循环部分每次循环计算的结果移位拼接而成。将Encrypt函数重写成python,转化过程中需要注意符号的优先级,结果如下:

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
tmp = flag  #Convert(flag)  48 hex
key_tmp =0x6b65795f746869735f69735f6b65795f
sstore5 = 0x6b65795f # 0x6b65795f 74686973 5f69735f 6b65795f >>96
sstore6 = 0x74686973
sstore7 = 0x5f69735f
sstore8 = 0x6b65795f
sstore2 = 0xb3c6ef3720
sstore3 = 0
step = 1
sstore4listall = []//mark
for i in range(1,4):
first = (tmp >> ((24 - i * 8)+4) * 8) & 0xffffffff
second = (tmp >> (24 - i * 8) * 8) & 0xffffffff
sstore4 = 0
sstore4list = []
for j in range(0, 32):
sstore4 = ((sstore4 & 0xffffffff) + (sstore2 >> 5)) & 0xffffffff
sstore4list.append(sstore4)//mark
tmp11 = (((second * 16) & 0xffffffff) + sstore5 ) & 0xffffffff
tmp12 = (second + sstore4) & 0xffffffff
tmp13 = ((second >> 5) + sstore6) & 0xffffffff
first = (first + (tmp11 ^ tmp12 ^ tmp13)) & 0xffffffff
tmp21 = (((first << 4) & 0xffffffff) + sstore7) & 0xffffffff
tmp22 = (first + sstore4) & 0xffffffff
tmp23 = ((first >> 5) + sstore8) & 0xffffffff
second = (second + (tmp21 ^ tmp22 ^ tmp23)) & 0xffffffff
sstore4listall.append(sstore4list)//mark
sstore3 = sstore3 + ((first << (192 - (step * 32))) + (second << (192 - (i * 64))))
step = step + 2
print(hex(sstore3))
#sstore3 = 0x505d433947f27742f60b06f350f2583450a1f7221380eeb6

8.

由以上这段加密过程求解flag,下面分析加密算法。算法主体是两层循环,第一层循环了3次,tmp为24字节,第一次循环求出的first和second是tmp的高位的0-4字节以及5-8字节,后续循环每次取8字节前部分为first变量,后部分为second变量。通过第二层循环后将first与second再度拼接组合,循环三次后为最终的输出。

第二层循环32次,其中的sstore4为storage[4]的存储值,初始为0并且随着循环不断变化,但是在3*32次的循环中与输入的flag无关,这96个数值是固定的,这里我设立了一个数组sstore4list用来存储记录,方便后续的解密。第二层的循环中的tmp11,tmp12,tmp13三个变量仅与second有关,first依据这三个值变化,tmp21,tmp22,tmp23三个变量仅与first有关,second依据这三个值变化,循环32次后为最后得到后续拼接的first与second。

依据主要逻辑可以理解为以下形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
tmp = [a,b,c]
output =[]
t = 0
for i in range(0,3):
first = tmp[i][:16]
second = tmp[i][17:]
for j in range(0, 32):
tmp1 = unknow_1(second,sstore4[t])
first = (first + tmp1)& 0xffffffff
tmp2 = unknow_2(first,sstore4[t])
second = (second + tmp2)& 0xffffffff
t = t+1
output.append([first,second])

9.

现在逻辑就清晰多了,先分组后加密在组合,类似于常见流密码的加密方式,对以上加密过程解密的逻辑可以理解为以下形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
tmp = []
output =[a,b,c]
t = 0
for i in range(0,3):
first = output[i][:16]
second = output[i][17:]
for j in range(0, 32):
tmp1 = unknow_1(second,sstore4[t])
first = (first - tmp1)& 0xffffffff
tmp2 = unknow_2(first,sstore4[t])
second = (second - tmp2)& 0xffffffff
t = t+1
tmp.append([first,second])

总结:获取slot3的数值output,它是调用Encrypt()的结果,我们需要做的是根据这个结果来反推它的输入key。那么,我们就要理解加密干了些什么,然后根据加密方式,倒推出解密方式,从而获得key值

solve

中国剩余定理求解key_tmp:

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
class Numbertheory():
"""
本模块用于数论中出现的问题。
"""

@staticmethod
def CRT(moudle, a):
"""
中国剩余定律/孙子定律

参数:
moudle: 模列表
a: 同余值列表

返回值:
中国剩余定律结果

例子:
moudle = [3, 5, 7]
a = [2, 4, 3]
结果:59
"""
M = reduce((lambda x, y : x * y), moudle)
result = 0
for mi in moudle:
Mi = M // mi
inv_Mi = gmpy2.invert(Mi, mi)
result = (result + a[moudle.index(mi)] * Mi * inv_Mi) % M
return result % M
1
2
3
moudle = [0x3100e35e552c1273c959, 0x1ac3243c9e81ba850045, 0x5ce6a91010e307946b87]
a = [0x2c2eb0597447608b329d, 0x6369510a41dbcbed870, 0x301753fa0827117d1968]
print(Numbertheory.CRT(moudle,a))

解密代码实现:

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
sstore3 = 0x505d433947f27742f60b06f350f2583450a1f7221380eeb6
key_tmp =0x6b65795f746869735f69735f6b65795f
sstore5 = 0x6b65795f
sstore6 = 0x74686973
sstore7 = 0x5f69735f
sstore8 = 0x6b65795f
sstore2 = 0xb3c6ef3720
tmp = 0
step = 1
sstore4listall = []
for i in range(1,4):
sstore4 = 0
sstore4list = []
for j in range(0, 32):
sstore4 = ((sstore4 & 0xffffffff) + (sstore2 >> 5)) & 0xffffffff
sstore4list.append(sstore4)
sstore4listall.append(sstore4list)

for i in range(1,4):
first = (sstore3 >> ((24 - i * 8)+4) * 8) & 0xffffffff
second = (sstore3 >> (24 - i * 8) * 8) & 0xffffffff
sstore4 = 0
for j in range(0, 32):
sstore4 = sstore4list[31 - j]
tmp21 = (((first << 4) & 0xffffffff) + sstore7) & 0xffffffff
tmp22 = (first + sstore4) & 0xffffffff
tmp23 = ((first >> 5 )+ sstore8) & 0xffffffff
second = (second - (tmp21 ^ tmp22 ^ tmp23)) & 0xffffffff
tmp11 = (((second << 4) & 0xffffffff) + sstore5) & 0xffffffff
tmp12 = (second + sstore4) & 0xffffffff
tmp13 = ((second >> 5) + sstore6) & 0xffffffff
first = (first - (tmp11 ^ tmp12 ^ tmp13)) & 0xffffffff
tmp = tmp + ((first << (192 - (step * 32))) + (second << (192 - (i * 64))))
step = step + 2
print(hex(tmp))