Poly Fun

Its a simple symmetric key encryption, I am sure you will be able to solve it (what do you mean the key looks weird)

Author : Revak Pandkar

challenge.py
encoded_flag.txt
encoded_key.txt

Here’s the source file:

1
import numpy as np
2
import random
3

4
polyc = [4,3,7]
5
poly = np.poly1d(polyc)
6

7

8
def generate_random_number():
9
    while True:
10
        num = random.randint(100, 999)
11
        first_digit = num // 100
12
        last_digit = num % 10
13
        if abs(first_digit - last_digit) > 1:
14
            return num
15

16

17
def generate_random_number_again():
18
    while True:
19
        num = random.randint(1000, 9999)
20
        if num % 1111 != 0:
21
            return num
22

23

24
def transform(num):
25
    number = random.randint(1, 100000)
26
    org = number
27
    number *= 2
28
    number += 15
29
    number *= 3
30
    number += 33
31
    number /= 6
32
    number -= org
33
    if number == 13:
34
        num1 = random.randint(1, 6)
35
        num2 = random.randint(1, 6)
36
        number = num1 * 2
37
        number += 5
38
        number *= 5
39
        number += num2
40
        number -= 25
41
        if int(number / 10) == num1 and number % 10 == num2:
42
            number = generate_random_number()
43
            num1 = int(''.join(sorted(str(number), reverse=True)))
44
            num2 = int(''.join(sorted(str(number))))
45
            diff = abs(num1 - num2)
46
            rev_diff = int(str(diff)[::-1])
47
            number = diff + rev_diff
48
            if number == 1088:
49
                org = num
50
                num *= 2
51
                num /= 3
52
                num += 5
53
                num *= 4
54
                num -= 9
55
                num -= org
56
                return num
57
            else:
58
                number = generate_random_number_again()
59
                i = 0
60
                while number != 6174:
61
                    digits = [int(d) for d in str(number)]
62
                    digits.sort()
63
                    smallest = int(''.join(map(str, digits)))
64
                    digits.reverse()
65
                    largest = int(''.join(map(str, digits)))
66
                    number = largest - smallest
67
                    i += 1
68

69
                if i <= 7:
70
                    org = num
71
                    num *= 2
72
                    num += 7
73
                    num += 5
74
                    num -= 12
75
                    num -= org
76
                    num += 4
77
                    num *= 2
78
                    num -= 8
79
                    num -= org
80
                    return num
81
                else:
82
                    org = num
83
                    num **= 4
84
                    num /= 9
85
                    num += 55
86
                    num *= 6
87
                    num += 5
88
                    num -= 23
89
                    num -= org
90
                    return num
91
        else:
92
            org = num
93
            num *= 10
94
            num += 12
95
            num **= 3
96
            num -= 6
97
            num += 5
98
            num -= org
99
            return num
100
    else:
101
        org = num
102
        num += 5
103
        num -= 10
104
        num *= 2
105
        num += 12
106
        num -= 20
107
        num -= org
108
        return num
109

110

111
def encrypt(p,key):
112
    return ''.join(chr(p(transform(i))) for i in key)
113

114

115
key = open('key.txt', 'rb').read()
116
enc = encrypt(poly,key)
117
print(enc)

Basically, this file contains a lot of checks on some operations that tell us what number is returned. To be honest, this is very easily cheesed by simply reusing the transform function on every possible character, and then creating a map that maps from output of the transform function to the corresponding character. The actual intended solution is to notice that every single check is always the same result no matter what (each sequence of operations always results in the same number), so therefore it is easy to figure out what the final result should be. (Note that each check can be easily tested with short Python scripts), and develop the same map from that.

Once you have the map, it’s easy to decode the key. Now, you’re supposed to realize that the flag must first be decoded from base64 (it is clearly in the correct format) but then blindly guess (based on the fact that it’s symmetric encryption) to use AES ECB. Not exactly sure why they even required you to guess that it’s AES ECB, as there are many more symmetric cryptoschemes, but yeah.

Here’s my full implementation:

1
import numpy as np
2
import random
3
import base64
4
from Crypto.Cipher import AES
5

6
polyc = [4,3,7]
7
poly = np.poly1d(polyc) # 4x^2 + 3x + 7
8

9
# for i in range(1, 100001):
10
#     number = i
11
#     org = number
12
#     number *= 2
13
#     number += 15
14
#     number *= 3
15
#     number += 33
16
#     number /= 6
17
#     number -= org
18
#     if(number != 13): print(org)
19

20
# for i in range(1, 7):
21
#     for j in range(1, 7):
22
#         num1 = i
23
#         num2 = j
24
#         number = num1 * 2
25
#         number += 5
26
#         number *= 5
27
#         number += num2
28
#         number -= 25
29
#         if not (int(number / 10) == num1 and number % 10 == num2):
30
#             print(num1, num2)
31

32
def generate_random_number(): # first and last digit are more than 1 apart
33
    while True:
34
        num = random.randint(100, 999)
35
        first_digit = num // 100
36
        last_digit = num % 10
37
        if abs(first_digit - last_digit) > 1:
38
            return num
39

40
# for i in range(1000):
41
#     number = generate_random_number()
42
#     num1 = int(''.join(sorted(str(number), reverse=True)))
43
#     num2 = int(''.join(sorted(str(number))))
44
#     diff = abs(num1 - num2)
45
#     rev_diff = int(str(diff)[::-1])
46
#     number = diff + rev_diff
47
#     if number == 1088:
48
#         print(number)
49

50
def generate_random_number_again(): # not a multiple of 1111
51
    while True:
52
        num = random.randint(1000, 9999)
53
        if num % 1111 != 0:
54
            return num
55

56
# for a in range(100):
57
#     number = generate_random_number_again()
58
#     i = 0
59
#     while number != 6174:
60
#         digits = [int(d) for d in str(number)]
61
#         digits.sort()
62
#         smallest = int(''.join(map(str, digits)))
63
#         digits.reverse()
64
#         largest = int(''.join(map(str, digits)))
65
#         number = largest - smallest
66
#         i += 1
67
#     if i > 7: print(i)
68

69
m = dict()
70
for i in range(118):
71
    num = i
72
    org = num
73
    num *= 2
74
    num += 7
75
    num += 5
76
    num -= 12
77
    num -= org
78
    num += 4
79
    num *= 2
80
    num -= 8
81
    num -= org
82
    # print(chr(poly(num)), chr(i))
83
    m[chr(poly(num))] = chr(i)
84

85
enc_key = open("encoded_key.txt", "r").read()
86

87
key = b''
88
for i in enc_key:
89
    key += m[i].encode()
90
# print()
91
# print(m.keys())
92
print(key)
93

94
# literally just guess it's b64 --> AES
95
enc_flag = open("encoded_flag.txt", 'r').read()
96
enc_flag = base64.b64decode(enc_flag)
97

98
c = AES.new(key, AES.MODE_ECB)
99
pt = c.decrypt(enc_flag)
100
print(pt)

Run the script to get the flag!

1
VishwaCTF{s33_1_t0ld_y0u_1t_w45_345y}

Thoughts

Crypto challenge that was secretly rev + forensics