Mod - TAMUctf - Walkthrough
Find the original flag by brute forcing a modular equation.
I recently attended the TAMUctf, one of the challenges in the Crypto category was Mod. The challenge description was short and easy:
Simply mod. Surely it’s simple
The code of the challenge also was quite easy.
1
2
3
4
5
6
7
import re
with open("flag.txt") as f:
flag = f.read()
assert re.fullmatch(r"gigem\{[a-z0-9_]{38}\}",flag)
flag_num = int.from_bytes(flag.encode(), 'big')
assert flag_num % 114093090821120352479644063983906458923779848139997892783140659734927967458173
== 58809011802516045741268578327158509054400633329629779038362406616616290661238
We have a simple modulo operation of the flag with a number, the result always should equal another number. Before the integer representation of the flag is calculated modulo, the flag is matched against an regex, the regex checks if the beginning is gigem{ and that the flag only contains letters numbers and underscores. In addition to that the last character should equal }.
The first observations are:
- If you check the number
114093090821120352479644063983906458923779848139997892783140659734927967458173, which is the divider, you will find out that it’s a prime.1 2 3
sage: is_prime(11409309082112035247964406398390645892377984813999789278314065973 ....: 4927967458173) True - We know basic information about the flag, we know that the flag contains 38 unknown characters, but these characters are only
a-z0-9_.
To solve that challenge we simply need a program which tries every n*p+r to find the flag, where n is the counter and p is the prime and r the reminder.
Although this sounds easy we can calculate the number of tries we need to do if we have 0 to z characters. Let’t assume that the minimum flag number is if all bytes in the flag are 0’s. The maximum flag number is all z’s.
1
2
3
4
5
6
7
sage: x = "gigem{"+"0"*38+"}"
sage: bytes_to_long(x.encode())
948698674773477176758298472605504707237472068623327043069542925303519062278364279612468941719520762160754813
sage: x = "gigem{"+"z"*38+"}"
sage: bytes_to_long(x.encode())
948698674773479598067132083931272128064773792686692248341213488911132053716461382006153190607399158288120445
Note; We use 0 as the number because it has the lowest byte size, so the integer number of the flag is the lowest.
The first look isn’t that bad, because of the gigem{, beginning doesn’t look that different but if you divide these numbers by the divider and then calculate the difference you see the problem.
1
2
3
4
5
6
7
8
9
10
11
948698674773479598067132083931272128064773792686692248341213488911132053716461382006153190607399158288120445
sage: 94869867477347717675829847260550470723747206862332704306954292530351906227
....: 8364279612468941719520762160754813//11409309082112035247964406398390645892
....: 3779848139997892783140659734927967458173
8315128181257569530728471842280
sage: 94869867477347959806713208393127212806477379268669224834121348891113205371
....: 6461382006153190607399158288120445//11409309082112035247964406398390645892
....: 3779848139997892783140659734927967458173
8315128181257590752949871800225
sage: 8315128181257590752949871800225-8315128181257569530728471842280
21222221399957945
We would need twenty-one quadrillion two hundred twenty-two trillion two hundred twenty-one billion three hundred ninety-nine million nine hundred fifty-seven thousand nine hundred forty-five tries.
This is not achievable with our current computers.
As you saw we need some key optimizations for our program, the first one is that we can skip 255 steps and only need to calculate n for the 256. step. This is the divider is a prime.
The second key optimization is that we can skip the next n steps of the number is below 0 and above z.
The last optimization I found was to don’t use python, you can compare the performance of go and python really good by this example:
1
2
3
4
5
6
7
8
9
10
def performance_theater(p, c, iterations):
start_time = time.time()
n = 1
m = 1
for _ in range(iterations):
m = p * n + c
end_time = time.time()
print(f"Final value of n: {n}")
print(f"Execution time: {end_time - start_time:.6f} seconds")
With the result:
1
Execution time: 5.570468 second
And the same for go.
1
2
3
4
5
6
7
8
9
10
11
func performanceTheater(p, c *big.Int, iterations int) {
startTime := time.Now()
for i := 0; i < iterations; i++ {
m := big.NewInt(1)
m.Mul(m, p).Add(m, c)
}
endTime := time.Now()
fmt.Printf("Execution time: %.6f seconds\n", endTime.Sub(startTime).Seconds())
}
The result is stunning less than 1/100 of the time.
1
Execution time: 0.053936 seconds
So now let’s implement this, I used as said go because of the good performance, then I added the step over case if the characters aren’t in the range of 48 to 57 (0-9) and 95 (_ to z). Lastly I implemented a simple a check if the output is printable. Also note the isFullyPrintable() function which I check the chars in reverse, because lower chars are likely to be not the right string.
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
package main
import (
"bytes"
"fmt"
"math/big"
"os"
"time"
"strconv"
)
func longToBytes(n *big.Int) []byte {
return n.Bytes()
}
func bytesToLong(b []byte) *big.Int {
return new(big.Int).SetBytes(b)
}
func isFullyPrintable(byteArray []byte) bool {
n := len(byteArray)
for i := n - 2; i >= 0; i-- {
b := byteArray[i]
if (b < 32 || b > 126) && (b != 9 && b != 10 && b != 13) {
return false
}
}
return true
}
func main() {
x := new(big.Int)
x.SetString("8315128181257569530728471842280", 10)
p := new(big.Int)
p.SetString("114093090821120352479644063983906458923779848139997892783140659734927967458173", 10)
c := new(big.Int)
c.SetString("58809011802516045741268578327158509054400633329629779038362406616616290661238", 10)
startTime := time.Now()
d := new(big.Int).Mul(x, p)
d.Add(d, c)
steps := 1
need := byte('}')
for {
if new(big.Int).And(d, big.NewInt(0xFF)).Uint64() == uint64(need) {
break
} else {
d.Add(d, p)
}
}
for {
someM := longToBytes(d)
steps++
if isFullyPrintable(someM) {
fmt.Println(string("Finally extracted the flag:"))
fmt.Println(string(someM))
fmt.Println(string("Total steps needed: "))
fmt.Println(strconv.Itoa(steps))
endTime := time.Now()
fmt.Printf("Total execution time: %.6f seconds\n", endTime.Sub(startTime).Seconds())
os.Exit(0)
}
for i := 6; i < min(12, len(someM)); i++ {
char := someM[i]
if !(char >= 48 && char <= 57 || char >= 97 && char <= 122) {
dataInt := bytesToLong(someM[i:])
var res *big.Int
switch {
case char > 122:
res = new(big.Int).Div(new(big.Int).SetBytes(bytes.Repeat([]byte{0xFF}, len(someM)-i)), p)
res.Sub(res, new(big.Int).Div(dataInt, p))
case char < 95 && char > 57:
res = new(big.Int).Div(new(big.Int).SetBytes(bytes.Repeat([]byte{'a'}, len(someM)-i)), p)
res.Sub(res, new(big.Int).Div(dataInt, p))
res.Sub(res, big.NewInt(1))
case char < 48:
res = new(big.Int).Div(new(big.Int).SetBytes(bytes.Repeat([]byte{'0'}, len(someM)-i)), p)
res.Sub(res, new(big.Int).Div(dataInt, p))
res.Sub(res, big.NewInt(1))
}
mod := new(big.Int).Mod(res, big.NewInt(256))
if mod.Cmp(big.NewInt(0)) != 0 {
toAdd := new(big.Int).Sub(big.NewInt(256), mod)
res.Add(res, toAdd)
}
x.Add(x, res)
d.Add(d, new(big.Int).Mul(res, p))
break
}
}
d.Add(d, new(big.Int).Mul(p, big.NewInt(256)))
}
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
The total execution time is now less than 40 seconds to find the flag.
1
2
3
4
5
6
$ ./flag_finder
Finally extracted the flag:
gigem{3v3ry1_kn0wz_l1l_15_alw4yz_7h3_answ3rz}
Total steps needed:
232766351
Total execution time: 36.951816 seconds