1
2
3
4
5
6
Sold: 92 times
Type: crypto
Risk: Low
Seller: 3ul3r
The local water supplier Silver Water Industries is planning their IPO. To appeal to current crypto investors, they even implemented a military grade token encryption.
Introduction
We are given a go program which generates a random token and we have to guess the correct token so it outputs us the flag.
Approach
In the code we see that when it encrypts the token it uses some exponential-modulo operation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func encryptByte(b uint8, N *big.Int) []*big.Int {
z := big.NewInt(-1)
enc := make([]*big.Int, 8)
for i := 0; i < 8; i++ {
//Calculates if the bit is set or not
bit := b & uint8(math.Pow(2, float64(7-i)))
x := genX(N) //Generates a random number of size N
x.Exp(x, big.NewInt(2), N) // (x^2 % N)
if bit != 0 { //If the bit is on
x.Mul(x, z) // x * -1
x.Mod(x, N) // Final eq -> -(x^2) % N =/= x^2 % N
}
enc[i] = x
}
return enc
}
As we can see, if the number we get hasn’t got a solution for the equation (x^2) % N then, the bit is on.
Coding solution
I used sage for coding the solution, but I found some problems when using the solve_mod module, as it overflowed the max size of C. Instead of using the solve_mod I made it manually by using the following code.
1
2
3
4
5
6
7
8
9
10
11
12
X = Zmod(N) #We set a ring of integers modulo N
total = 0
for j in range(8):
bufferval = int(values[i][j])
a = X(bufferval) # We give a name in that ring to the element we get from IO
try:
a.nth_root(2) # We ask sage for the 2nd root of the element
except: #If it doesnt exist, then it went through the -(x^2) % N operation
total+=pow(2,7-j)
flagsolver += chr(total)
As we have the algorithm to solve the equation, we can implement it with some pwntools IO and automate it totally.
Exploit
The exploit ends up looking like this
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
from pwn import *
conexion = remote('flu.xxx',20060)
N = int(conexion.recvline().decode())
values = []
for i in range(20):
bufferthing = conexion.recvline().decode()
bufferthing = bufferthing.replace("[","")
bufferthing = bufferthing.replace("]","")
bufferthing = bufferthing.replace("\n","")
buffervalues = bufferthing.split(" ")
goinplz = []
for item in buffervalues:
goinplz.append(int(item))
values.append(goinplz)
X = Zmod(N) #We set a ring of integers modulo N
flagsolver = ''
for i in range(20):
total = 0
for j in range(8):
bufferval = int(values[i][j])
# We give a name in that ring to the element we get from IO
a = X(bufferval)
try:
a.nth_root(2) # We ask sage for the 2nd root of the element
except:
#If it doesnt exist, then it went through the -(x^2) % N operation
total+=pow(2,7-j)
flagsolver += chr(total) # We add the char
log.info(f"Token: {flagsolver}")
conexion.sendline(flagsolver.encode())
conexion.recvline().decode()
log.warn(conexion.recvline().decode())
And the output is:
1
2
3
4
5
6
7
8
9
Use $sage exploit.sage
After compiling it to python you can use
$python3 exploit.sage.py
For prettier result
[+] Opening connection to flu.xxx on port 20060: Done
[*] Token: ipFtW0bvi9piDuAuKzaJ
[!] flag{Oh_NO_aT_LEast_mY_AlGORithM_is_ExpanDiNg}
[*] Closed connection to flu.xxx port 20060
CHALLENGE SOURCE CODE
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
package main
import (
"bufio"
"crypto/rand"
"fmt"
"math"
"math/big"
"os"
)
func genN() *big.Int {
var p *big.Int
var q *big.Int
var err error
for {
p, err = rand.Prime(rand.Reader, 64)
if err != nil {
panic(err)
}
res := new(big.Int)
if res.Mod(p, big.NewInt(4)); res.Cmp(big.NewInt(1)) == 0 {
break
}
}
for {
q, err = rand.Prime(rand.Reader, 64)
if err != nil {
panic(err)
}
res := new(big.Int)
if res.Mod(q, big.NewInt(4)); res.Cmp(big.NewInt(3)) == 0 {
break
}
}
N := new(big.Int)
N.Mul(p, q)
return N
}
func genX(N *big.Int) *big.Int {
for {
x, err := rand.Int(rand.Reader, N)
if err != nil {
panic(err)
}
g := new(big.Int)
g.GCD(nil, nil, x, N)
if g.Cmp(big.NewInt(1)) == 0 {
return x
}
}
}
func encryptByte(b uint8, N *big.Int) []*big.Int {
z := big.NewInt(-1)
enc := make([]*big.Int, 8)
for i := 0; i < 8; i++ {
bit := b & uint8(math.Pow(2, float64(7-i)))
x := genX(N)
x.Exp(x, big.NewInt(2), N)
if bit != 0 {
x.Mul(x, z)
x.Mod(x, N)
}
enc[i] = x
}
return enc
}
func generateRandomString(n int) string {
const letters = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-"
ret := make([]byte, n)
for i := 0; i < n; i++ {
num, err := rand.Int(rand.Reader, big.NewInt(int64(len(letters))))
if err != nil {
panic(err)
}
ret[i] = letters[num.Int64()]
}
return string(ret)
}
func main() {
N := genN()
token := []byte(generateRandomString(20))
fmt.Println(N)
for _, b := range token {
fmt.Println(encryptByte(uint8(b), N))
}
fmt.Println("")
reader := bufio.NewReader(os.Stdin)
input, err := reader.ReadString('\n')
if err != nil {
panic(err)
}
input = input[:len(input)-1]
if string(token) == input {
fmt.Println("flag{<YOUR_FLAG_HERE>}")
}
}