2022ASISCTF-Crypto Writeup

Posted on
2022ASISCTF-Crypto Writeup

Disinvolute

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
sakii@ubuntu:~/Desktop/Crypto/2022ASISCTF/Disinvolute$ nc 65.21.255.31 12431
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Welcome to disinvolute challenge, with respet you should solve a    |
|  very hard nested DLP problem! For this I have used safe primes to   |
|  insure that secuirty is MAX! This is an impossible mission! YES!!!  |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Options: 
|       [E]ncrypted flag! 
|       [F]acts 
|       [Q]uit
F
| e = 65537
| g = 19
| G = 7
| n = 144142872584786172459712266422830464422782386345677841365550188073106673570519420106043075688750410479307539395113407113583613379908969274320131857313607541074745882137584269736983710363270757495300190904028142555626553906369544683482855730953138026325289124675117428736952390090942851677700926951017512903537
| x = 20481873151021892313739970645942193024412330288818548775532234495313112153793204913641944129920001616711162444758478390470047852791425721983089024020650534903166520827929908464206467532476244729109866189200794243817094131492557343197079483895945482873612445194495516542507554735239184186485578373579033270736
| y = 5755357098438493315863705113701420725665879534340513668592463441617498575435853199199001568044556309619408144130532877709556985080858116610776207887841739667211649363656434552122864692914013136090121706376726673770043997150573084721903345115451181812698336680563183100503976286558850166590243915476970348805243216
| m = bytes_to_long(flag)
| pow(g, pow(G, x), n) == pow(g, pow(G, y), n)
| Options: 
|       [E]ncrypted flag! 
|       [F]acts 
|       [Q]uit
E
| pow(m, e, n) = 116053565257337754925269512324632264953964582663831581498763476007062812544826805376488943503633454327012345603467755182123148623463906970904176594264070680202867948093638787209475410344433401230669971852545722283623914032236394700067020590810829138769116146938490847509030768878697926954592911105967756003587
| Options: 
|       [E]ncrypted flag! 
|       [F]acts 
|       [Q]uit

The facts gives us an equation that : ,which gives us: .

It reminds me of cycling attack, but I can't factorize .

Noticing the description: I have used safe primes.

Using safe primes means:

either s or t is a prime.

So , we could express with s, t:

Since,

Finally, we get an equation:

In this challenge, , since is small, we could brute to find .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *

e = 65537
g = 19
G = 7
n = 144142872584786172459712266422830464422782386345677841365550188073106673570519420106043075688750410479307539395113407113583613379908969274320131857313607541074745882137584269736983710363270757495300190904028142555626553906369544683482855730953138026325289124675117428736952390090942851677700926951017512903537
x = 20481873151021892313739970645942193024412330288818548775532234495313112153793204913641944129920001616711162444758478390470047852791425721983089024020650534903166520827929908464206467532476244729109866189200794243817094131492557343197079483895945482873612445194495516542507554735239184186485578373579033270736
y = 5755357098438493315863705113701420725665879534340513668592463441617498575435853199199001568044556309619408144130532877709556985080858116610776207887841739667211649363656434552122864692914013136090121706376726673770043997150573084721903345115451181812698336680563183100503976286558850166590243915476970348805243216

c = 116053565257337754925269512324632264953964582663831581498763476007062812544826805376488943503633454327012345603467755182123148623463906970904176594264070680202867948093638787209475410344433401230669971852545722283623914032236394700067020590810829138769116146938490847509030768878697926954592911105967756003587



for k in range(2,2**18):
    if (y-x) % k!=0:
        continue
    phi = ((2*n-6+(y-x)*2//k))//3
    if long_to_bytes(int(pow(c,inverse(65537,phi),n))).startswith(b'ASIS'):
        print(long_to_bytes(int(pow(c,inverse(65537,phi),n))))
        break

Binned

ez

1
2
3
4
5
6
7
8
9
10
from gmpy2 import *
from Crypto.Util.number import *
from z3 import *

n = 125004899806380680278294077957993138206121343727674199724251084023100054797391533591150992663742497532376954423241741439218367086541339504325939051995057848301514908377941815605487168789148131591458301036686411659334843972203243490288676763861925647147178902977362125434420265824374952540259396010995154324589
enc = 789849126571263315208956108629196540107771075292285804732934458641661099043398300667318883764744131397353851782194467024270666326116745519739176492710750437625345677766980300328542459318943175684941281413218985938348407537978884988013947538034827562329111515306723274989323212194585378159386585826998838542734955059450048745917640814983343040930383529332576453845724747105810109832978045135562492851617884175410194781236450629682032219153517122695586503298477875749138129517477339813480115293124316913331705913455692462482942654717828006590051944205639923326375814299624264826939725890226430388059890231323791398412019416647826367964048142887158552454494856771139750458462334678907791079639005383932256589768726730285409763583606927779418528562990619985840033479201147509241313757191997545174262930707521451438204766627975109619779824255444258160
n2= n**2
x = Int('x')
res = solve(n2*x*x+(2*n-n2)*x+2-2*enc==0)
print(long_to_bytes(10054489678067822115481371335232343974958463063132871933014628812175566812121897618218465084557664288954026584252797))

Mariana

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
#!/usr/bin/env python3

from Crypto.Util.number import *
import sys
from flag import flag

def die(*args):
truepr(*args)
truequit()

def pr(*args):
trues = " ".join(map(str, args))
truesys.stdout.write(s + "\n")
truesys.stdout.flush()

def sc():
truereturn sys.stdin.buffer.readline()

def main():
trueborder = "|"
truepr(border*72)
truepr(border, "Welcome to MARIANA cryptography battle, the mission is solving super", border)
truepr(border, "hard special DLP problem in real world, are you ready to fight?     ", border)
truepr(border*72)

trueNBIT = 32
trueSTEP = 40

truepr(border, "In each step solve the given equation and send the solution for x.  ", border)
truec = 1
truewhile c <= STEP:
truetruenbit = NBIT * c
truetruep = getPrime(nbit)
truetrueg = getRandomRange(3, p)
truetruepr(border, f'p = {p}')
truetruepr(border, f'g = {g}')
truetruepr(border, 'Send the solution x = ')
truetrueans = sc()
truetruetry:
truetruetruex = int(ans)
truetrueexcept:
truetruetruedie(border, 'Given number is not integer!')
truetrueif x >= p:
truetruetruedie(border, "Kidding me!? Your solution must be smaller than p :P")
truetrueif (pow(g, x, p) - x) % p == 0:
truetruetrueif c == STEP:
truetruetruetruedie(border, f"Congratz! the flag is: {flag}")
truetruetrueelse:
truetruetruetruepr(border, "Good job, try to solve the next level!")
truetruetruetruec += 1
truetrueelse:
truetruetruedie(border, "Try harder and smarter to find the solution!")

if __name__ == '__main__':
truemain()

Looks like to solve transcendental equations?

In fact the exponent could be negative..

1
2
3
4
5
6
7
from pwn import *
io = remote('65.21.255.31', 32066)
for _ in range(40):
    io.recvuntil(b'p = ')
    p = int(io.recvline())
    io.sendline(str(1-p).encode())
print(io.recvall())

Chaffymasking

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
111
112
113
114
#!/usr/bin/env python3

import numpy as np
import binascii
import os, sys
from flag import FLAG

def die(*args):
truepr(*args)
truequit()

def pr(*args):
trues = " ".join(map(str, args))
truesys.stdout.write(s + "\n")
truesys.stdout.flush()

def sc(): 
truereturn sys.stdin.buffer.readline()

def pad(inp, length):
trueresult = inp + os.urandom(length - len(inp))
truereturn result

def byte_xor(a, b):
truereturn bytes(_a ^ _b for _a,_b in zip(a,b)) 

def chaffy_mask(salt, LTC, m, n):
trueq = n ** 2
truehalf1_salt = salt[:m // 8]
truehalf2_salt = salt[m // 8:]
truexor_salts = int.from_bytes(byte_xor(half1_salt, half2_salt), "big")

trueif xor_salts == 0:
truetruehalf1_salt = byte_xor(half1_salt, os.urandom(m))
truehalf1_binStr = "{:08b}".format(int(half1_salt.hex(),16))
trueif(len(half1_binStr) < m):
truetruehalf1_binStr = "0" * (m - len(half1_binStr)%m) + half1_binStr
truehalf2_binStr = "{:08b}".format(int(half2_salt.hex(),16))
trueif(len(half2_binStr) < m):
truetruehalf2_binStr = "0" * (m - len(half2_binStr)%m) + half2_binStr
true
truevec_1 = np.array(list(half1_binStr), dtype=int)
truevec_1 = np.reshape(vec_1, (m,1))
truevec_2 = np.array(list(half2_binStr), dtype=int)
truevec_2 = np.reshape(vec_2, (m,1))
true
trueout_1 = LTC.dot(vec_1) % q
trueout_2 = LTC.dot(vec_2) % q
true
trueflag_vector = np.array([ord(i) for i in FLAG])
trueflag_vector = np.reshape(flag_vector, (n,1))
truemasked_flag = (flag_vector ^ out_1 ^ out_2) % 256
truemasked_flag = np.reshape(masked_flag, (n,))
truemasked_flag = ''.join([hex(_)[2:].zfill(2) for _ in masked_flag])
truereturn masked_flag.encode('utf-8')

def main():
trueborder = "|"
truepr(border*72)
truepr(border, " Welcome to chaffymask combat, we implemented a masking method to   ", border)
truepr(border, " hide our secret. Masking is done by your 1024 bit input salt. Also ", border)
truepr(border, " I noticed that there is a flaw in my method. Can you abuse it and  ", border)
truepr(border, " get the flag? In each step you should send salt and get the mask.  ", border)
truepr(border*72)

truem, n = 512, 64 
trueIVK = [
true3826, 476, 3667, 2233, 1239, 1166, 2119, 2559, 2376, 1208, 2165, 2897, 830, 529, 346, 150, 2188, 4025, 
true3667, 1829, 3987, 952, 3860, 2574, 959, 1394, 1481, 2822, 3794, 2950, 1190, 777, 604, 82, 49, 710, 1765, 
true3752, 2970, 952, 803, 873, 2647, 2643, 1096, 1202, 2236, 1492, 3372, 2106, 1868, 535, 161, 3143, 3370, 
true1, 1643, 2147, 2368, 3961, 1339, 552, 2641, 3222, 2505, 3449, 1540, 2024, 618, 1904, 314, 1306, 3173, 
true4040, 1488, 1339, 2545, 2167, 394, 46, 3169, 897, 4085, 4067, 3461, 3444, 118, 3185, 2267, 3239, 3612, 
true2775, 580, 3579, 3623, 1721, 189, 650, 2755, 1434, 35, 3167, 323, 589, 3410, 652, 2746, 2787, 3665, 828, 
true3200, 1450, 3147, 720, 3741, 1055, 505, 2929, 1423, 3629, 3, 1269, 4066, 125, 2432, 3306, 4015, 2350, 
true2154, 2623, 1304, 493, 763, 1765, 2608, 695, 30, 2462, 294, 3656, 3231, 3647, 3776, 3457, 2285, 2992, 
true3997, 603, 2342, 2283, 3029, 3299, 1690, 3281, 3568, 1927, 2909, 1797, 1675, 3245, 2604, 1272, 1146, 
true3301, 13, 3712, 2691, 1097, 1396, 3694, 3866, 2066, 1946, 3476, 1182, 3409, 3510, 2920, 2743, 1126, 2154, 
true3447, 1442, 2021, 1748, 1075, 1439, 3932, 3438, 781, 1478, 1708, 461, 50, 1881, 1353, 2959, 1225, 1923, 
true1414, 4046, 3416, 2845, 1498, 4036, 3899, 3878, 766, 3975, 1355, 2602, 3588, 3508, 3660, 3237, 3018, 
true1619, 2797, 1823, 1185, 3225, 1270, 87, 979, 124, 1239, 1763, 2672, 3951, 984, 869, 3897, 327, 912, 1826, 
true3354, 1485, 2942, 746, 833, 3968, 1437, 3590, 2151, 1523, 98, 164, 3119, 1161, 3804, 1850, 3027, 1715, 
true3847, 2407, 2549, 467, 2029, 2808, 1782, 1134, 1953, 47, 1406, 3828, 1277, 2864, 2392, 3458, 2877, 1851, 
true1033, 798, 2187, 54, 2800, 890, 3759, 4085, 3801, 3128, 3788, 2926, 1983, 55, 2173, 2579, 904, 1019, 
true2108, 3054, 284, 2428, 2371, 2045, 907, 1379, 2367, 351, 3678, 1087, 2821, 152, 1783, 1993, 3183, 1317, 
true2726, 2609, 1255, 144, 2415, 2498, 721, 668, 355, 94, 1997, 2609, 1945, 3011, 2405, 713, 2811, 4076, 
true2367, 3218, 1353, 3957, 2056, 881, 3420, 1994, 1329, 892, 1577, 688, 134, 371, 774, 3855, 1461, 1536, 
true1824, 1164, 1675, 46, 1267, 3652, 67, 3816, 3169, 2116, 3930, 2979, 3166, 3944, 2252, 2988, 34, 873, 
true1643, 1159, 2822, 1235, 2604, 888, 2036, 3053, 971, 1585, 2439, 2599, 1447, 1773, 984, 261, 3233, 2861, 
true618, 465, 3016, 3081, 1230, 1027, 3177, 459, 3041, 513, 1505, 3410, 3167, 177, 958, 2118, 326, 31, 2663, 
true2026, 2549, 3026, 2364, 1540, 3236, 2644, 4050, 735, 280, 798, 169, 3808, 2384, 3497, 1759, 2415, 3444, 
true1562, 3472, 1151, 1984, 2454, 3167, 1538, 941, 1561, 3071, 845, 2824, 58, 1467, 3807, 2191, 1858, 106, 
true3847, 1326, 3868, 2787, 1624, 795, 3214, 1932, 3496, 457, 2595, 3043, 772, 2436, 2160, 3428, 2005, 2597, 
true1932, 101, 3528, 1698, 3663, 900, 3298, 1872, 1179, 3987, 3695, 3561, 1762, 3785, 3005, 2574, 6, 1524, 
true2738, 1753, 2350, 558, 800, 3782, 722, 886, 2176, 3050, 221, 1925, 564, 1271, 2535, 3113, 1310, 2098, 
true3011, 964, 3281, 6, 1326, 741, 189, 2632, 373, 1176, 548, 64, 1445, 2376, 1524, 2690, 1316, 2304, 1336, 
true2257, 3227, 2542, 3911, 3460
true]

trueLTC = np.zeros([n, m], dtype=(int))
trueLTC[0,:] = IVK

truefor i in range(1, n):
truetruefor j in range(m // n + 1):
truetruetrueLTC[i,j*n:(j+1)*n] = np.roll(IVK[j*n:(j+1)*n], i)

truefor _ in range(5):
truetruepr(border, "Give me your salt: ")
truetrueSALT = sc()[:-1]
truetrueSALT = pad(SALT, m // 4)
truetrueMASKED_FLAG = chaffy_mask(SALT, LTC, m, n)
truetruepr(border, f'masked_flag = {MASKED_FLAG}')

if __name__ == '__main__':
truemain()

Noticing that the algorithm is reversible because of the function. Attention ,when the input salt is 128-bit, the pad function won't run, then we could easily get the flag .

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
#!/usr/bin/env python3

import numpy as np
import binascii
from pwn import *

def byte_xor(a, b):
truereturn bytes(_a ^ _b for _a,_b in zip(a,b)) 

def chaffy_mask(masflag,salt, LTC, m, n):
trueq = n ** 2
truehalf1_salt = salt[:m // 8]
truehalf2_salt = salt[m // 8:]
truehalf1_binStr = "{:08b}".format(int(half1_salt.hex(),16))
trueif(len(half1_binStr) < m):
truetruehalf1_binStr = "0" * (m - len(half1_binStr)%m) + half1_binStr
truehalf2_binStr = "{:08b}".format(int(half2_salt.hex(),16))
trueif(len(half2_binStr) < m):
truetruehalf2_binStr = "0" * (m - len(half2_binStr)%m) + half2_binStr
true
truevec_1 = np.array(list(half1_binStr), dtype=int)
truevec_1 = np.reshape(vec_1, (m,1))
truevec_2 = np.array(list(half2_binStr), dtype=int)
truevec_2 = np.reshape(vec_2, (m,1))
true
trueout_1 = LTC.dot(vec_1) % q
trueout_2 = LTC.dot(vec_2) % q
true
trueflag_vector = np.array([i for i in masflag])
trueflag_vector = np.reshape(flag_vector, (n,1))
truemasked_flag = (flag_vector ^ out_1 ^ out_2) % 256
truemasked_flag = np.reshape(masked_flag, (n,))
truemasked_flag = ''.join([hex(_)[2:].zfill(2) for _ in masked_flag])
truereturn bytes.fromhex(masked_flag)


m, n = 512, 64 
IVK = [
true3826, 476, 3667, 2233, 1239, 1166, 2119, 2559, 2376, 1208, 2165, 2897, 830, 529, 346, 150, 2188, 4025, 
true3667, 1829, 3987, 952, 3860, 2574, 959, 1394, 1481, 2822, 3794, 2950, 1190, 777, 604, 82, 49, 710, 1765, 
true3752, 2970, 952, 803, 873, 2647, 2643, 1096, 1202, 2236, 1492, 3372, 2106, 1868, 535, 161, 3143, 3370, 
true1, 1643, 2147, 2368, 3961, 1339, 552, 2641, 3222, 2505, 3449, 1540, 2024, 618, 1904, 314, 1306, 3173, 
true4040, 1488, 1339, 2545, 2167, 394, 46, 3169, 897, 4085, 4067, 3461, 3444, 118, 3185, 2267, 3239, 3612, 
true2775, 580, 3579, 3623, 1721, 189, 650, 2755, 1434, 35, 3167, 323, 589, 3410, 652, 2746, 2787, 3665, 828, 
true3200, 1450, 3147, 720, 3741, 1055, 505, 2929, 1423, 3629, 3, 1269, 4066, 125, 2432, 3306, 4015, 2350, 
true2154, 2623, 1304, 493, 763, 1765, 2608, 695, 30, 2462, 294, 3656, 3231, 3647, 3776, 3457, 2285, 2992, 
true3997, 603, 2342, 2283, 3029, 3299, 1690, 3281, 3568, 1927, 2909, 1797, 1675, 3245, 2604, 1272, 1146, 
true3301, 13, 3712, 2691, 1097, 1396, 3694, 3866, 2066, 1946, 3476, 1182, 3409, 3510, 2920, 2743, 1126, 2154, 
true3447, 1442, 2021, 1748, 1075, 1439, 3932, 3438, 781, 1478, 1708, 461, 50, 1881, 1353, 2959, 1225, 1923, 
true1414, 4046, 3416, 2845, 1498, 4036, 3899, 3878, 766, 3975, 1355, 2602, 3588, 3508, 3660, 3237, 3018, 
true1619, 2797, 1823, 1185, 3225, 1270, 87, 979, 124, 1239, 1763, 2672, 3951, 984, 869, 3897, 327, 912, 1826, 
true3354, 1485, 2942, 746, 833, 3968, 1437, 3590, 2151, 1523, 98, 164, 3119, 1161, 3804, 1850, 3027, 1715, 
true3847, 2407, 2549, 467, 2029, 2808, 1782, 1134, 1953, 47, 1406, 3828, 1277, 2864, 2392, 3458, 2877, 1851, 
true1033, 798, 2187, 54, 2800, 890, 3759, 4085, 3801, 3128, 3788, 2926, 1983, 55, 2173, 2579, 904, 1019, 
true2108, 3054, 284, 2428, 2371, 2045, 907, 1379, 2367, 351, 3678, 1087, 2821, 152, 1783, 1993, 3183, 1317, 
true2726, 2609, 1255, 144, 2415, 2498, 721, 668, 355, 94, 1997, 2609, 1945, 3011, 2405, 713, 2811, 4076, 
true2367, 3218, 1353, 3957, 2056, 881, 3420, 1994, 1329, 892, 1577, 688, 134, 371, 774, 3855, 1461, 1536, 
true1824, 1164, 1675, 46, 1267, 3652, 67, 3816, 3169, 2116, 3930, 2979, 3166, 3944, 2252, 2988, 34, 873, 
true1643, 1159, 2822, 1235, 2604, 888, 2036, 3053, 971, 1585, 2439, 2599, 1447, 1773, 984, 261, 3233, 2861, 
true618, 465, 3016, 3081, 1230, 1027, 3177, 459, 3041, 513, 1505, 3410, 3167, 177, 958, 2118, 326, 31, 2663, 
true2026, 2549, 3026, 2364, 1540, 3236, 2644, 4050, 735, 280, 798, 169, 3808, 2384, 3497, 1759, 2415, 3444, 
true1562, 3472, 1151, 1984, 2454, 3167, 1538, 941, 1561, 3071, 845, 2824, 58, 1467, 3807, 2191, 1858, 106, 
true3847, 1326, 3868, 2787, 1624, 795, 3214, 1932, 3496, 457, 2595, 3043, 772, 2436, 2160, 3428, 2005, 2597, 
true1932, 101, 3528, 1698, 3663, 900, 3298, 1872, 1179, 3987, 3695, 3561, 1762, 3785, 3005, 2574, 6, 1524, 
true2738, 1753, 2350, 558, 800, 3782, 722, 886, 2176, 3050, 221, 1925, 564, 1271, 2535, 3113, 1310, 2098, 
true3011, 964, 3281, 6, 1326, 741, 189, 2632, 373, 1176, 548, 64, 1445, 2376, 1524, 2690, 1316, 2304, 1336, 
true2257, 3227, 2542, 3911, 3460
true]

LTC = np.zeros([n, m], dtype=(int))
LTC[0,:] = IVK

for i in range(1, n):
truefor j in range(m // n + 1):
truetrueLTC[i,j*n:(j+1)*n] = np.roll(IVK[j*n:(j+1)*n], i)

io = remote('65.21.255.31',31377)
salt = b'A' * 120 +b'B' *8

io.recvuntil(b"Give me your salt: ")
io.sendline(salt)
io.recvuntil(b"masked_flag = ")
maskflag = io.recvline().decode().strip()[2:-1]
print(maskflag)
print(chaffy_mask(bytes.fromhex(maskflag), salt, LTC, m, n))