TokyoWesterns CTF 2020 Writeups 1

September 21, 2020

crypto writeup pwn

TokyoWesterns CTF 2020 Writeups

Crypto
Pwn
- nothing more to say 2020

First things first, kudos to the team @TokyoWesterns for the excellent CTF, enjoyed playing it.I managed to solve all crypto challenges and a pwn warmup challenge. Our team @teaminvaders0 ended up at position #21.

If there’s any mistake in the writeup or you’re having a hard time understanding the solution or anything else, feel free to DM me @S3v3ru5_.

Twin-d [Crypto]

we were given task.rb and output of it.

flag is encrypted with textbook RSA. As the name of the challenge suggests, twin private exponents are generated (d1, d1 + 2) and their corresponding public exponents (e1, e2) are given.
task.rb output

Using e1 and e2, we can write equations as follows

e1 * d1 = 1 mod phi(n)
e1 * d1 = 1 + k1*phi(n)
d1 = (1 + k1*phi(n)) / e1

d2 = d1 + 2
e2 * d2 = 1 mod phi(n)
e2 * (d1 + 2) = 1 + k2*phi(n)
e2 * d1 + 2*e2 = 1 + k2*phi(n)
((e2 * (1 + k1*phi(n))) / e1) + 2*e2 = 1 + k2*phi(n)
e2 + e2*k1*phi(n) + 2*e1*e2 = e1 + e1*k2*phi(n)
e2 - e1 + 2*e1*e2 = e1*k2*phi(n) - e2*k1*phi(n)
e2 - e1 + 2*e1*e2 = phin(n) * (e1*k2 - e2*k1)

by calculating e2 - e1 + 2 * e1 * e2 we can obtain a multiple of phi(n). we can treat it as phi(n) to calculate the private exponent d1 and decrypt the ciphertext.

FLAG :: TWCTF{even_if_it_is_f4+e}

Sqrt [Crypto]

we were given chall.py and its output.
chall.py

p = 6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
c = 5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160

we have two values p (prime) and c = flag**(2**64) % p.

To get the flag, we have to calculate 2**64 root of c modulo p.

we cannot directly calculate the inverse of 2**64 as in the case of RSA cause the gcd(2**64, p - 1) != 1.

Though we can calculate 2**64 root of c by repeatedly calculating the square root which can done in polynomial time, this is not feasible cause for a given square there are 2 possible square roots x and -x so, the number of roots will increase exponentially.

we have to look at the structure of the group of integers modulo p.
factoring (p-1) results in 2**30 * q where q is a large prime.

q = 6260495806252046929286845900294522859477928195432517298076552742112950886324892284005656588584952135860464814694781314411135020941596864321946343173249814754547221898776857696421175805576386605600709481536943693517957341228010065655986626401676101786949671425529135194729299908929006799985530842254243

As (p-1) = 2**30 * q, there are subgroups with order q, 2**30, 2**29*q…

Note : order here is multiplicative order

Given a random element 0 < m < p, it will have order of form 2**i * q**j with 0 <= i <= 30 and j = 0 or 1. most likely the order will be (p-1) = 2**30 * q

suppose order of m is in form 2**i * q then ti = m ** (2**i) will have order q.

we can use this fact to reduce the number of square root operations required.

As an example, let order of m = (2**30)*q

m**(2**64) can be written as (m**(2**30))**(2**34) = ti**(2**34) where ti = m**2**30.ti will have multiplicative order of q and GCD(2**34, q) == 1

we can easily calculate ti by exponentiating c = m**(2**64) with inverse(2**34, q).

Now, we have ti = m**(2**30), we can use repeated square rooting to calculate m.

we can optimise that algorithm by calculating only one of the possible roots and generate remaining roots using it.

given r1 such that r1**(2**30) == t
calculate all xi such that x1**(2**30) == 1
multiplying each xi with r1 generates all remaining roots as

(r1 * xi)**(2**30) = r1**(2**30) * xi**(2**30) = t * 1 = t

xi can be calculated by first calculating generator of subgroup 
with order 2**30 and succesive powers of the generator will give 
the required xi's.  

The same approach can be used to calculate the flag.

FLAG :: TWCTF{17s_v3ry_34sy_70_f1nd_th3_n_7h_r007}

The Melancholy of Alice [Crypto]

Each character of the flag is encrypted separately using Elgamal Encryption and we are given the ciphertexts encrypt.py

If there’s a way to check given m, ElagamalEncryption(m) == (c1, c2) without additional information we can bruteforce values of m as they are comprised only printable characters. I am not sure but there ain’t a way to do that using only p and g has order of large prime.

Elagamal Encryption:
	pubkey = (p, q, g, g**x) where q is order of g
	privkey = x

To encrypt message m:
	generate a random number r1 from (1, q)
	c1 = g**r1
	c2 = m * ((g**x)**r1)
To decrypt:
	m = c2 * inverse(c1**x)

p = 168144747387516592781620466787069575171940752179672411574452734808497653671359884981272746489813635225263167370526619987842319278446075098036112998679570069486935297242638675590736039429506131690941660748942375274820626186241210376537247501823653926524570571499198040207829317830442983944747691656715907048411
q = 84072373693758296390810233393534787585970376089836205787226367404248826835679942490636373244906817612631583685263309993921159639223037549018056499339785034743467648621319337795368019714753065845470830374471187637410313093120605188268623750911826963262285285749599020103914658915221491972373845828357953524205
g = 2
h = 98640592922797107093071054876006959817165651265269454302952482363998333376245900760045606011965672215605936345612030149799453733708430421685495677502147392514542499678987737269487279698863617849581626352877756515435930907093553607392143564985566046429416461073375036461770604488387110385404233515192951025299

In our case q is not a prime and there are few small factors in q
namely :: 3, 5, 19, 2
using pohlig hellman attack on g**x, g we can calculate the x modulo 2*3*5*19 which resulted in xj = x % 2*3*5*19 = 137.

Though we cannot decrypt the ct, we can check whether given m is a possible message as follows

t1 = c2 * inverse(m, p)
if m is correct message then
	t1 = (g**r1)**x
	c1 = (g**r1)
	use pohlig hellman attack to calculate x % 2*3*5*19
	if dlog == 137
		add m as a possible correct message

There are few false positives while calculating the flag but slight guessing will clean up the junk.

FLAG:: TWCTF{8d560108444cc360374ef54433d218e9_for_the_first_time_in_9_years!}

Circular [Crypto]

To solve this challenge we have to calculate x, y given k, n, message such that

x**2 + k*y**2 = message mod n

I found this paper https://www.researchgate.net/publication/262234058_An_efficient_solution_of_the_congruence

That paper gives an efficient algorithm to solve the exact equation as in our challenge. so, all we need to do is implement the algorithm described in the paper.

solve.py

FLAG :: TWCTF{dbodfs-dbqsjdpso-mjcsb-mfp}

Nothing is more to say 2020 [Pwn]

we were given source code along with the binary,there’s a format string bug.

    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX disabled
    PIE:      No PIE (0x400000)
    RWX:      Has RWX segments

nothing.c

    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX disabled
    PIE:      No PIE (0x400000)
    RWX:      Has RWX segments

As we have unlimited FSB’s exploit plan is

Leak buf address, rbp of main function stack frame
Overwrite return pointer stored on stack byte by byte with (buf + 8) address
send "q"*8 + shellcode as input, "q" breaks the while loop and
 returning from main function, will make to jump to our shellcode

exploit.py

FLAG :: TWCTF{kotoshi_mo_hazimarimasita_TWCTF_de_gozaimasu}