Hack.lu CTF 2021 - Silver Water Industries [Crypto]
Post
Cancel

# Hack.lu CTF 2021 - Silver Water Industries [Crypto]

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>}") } }