## Introduction

The University of Texas at Austin (UT Austin) organized a CTF 8th-10th March, 2019 called UTCTF. I participated along with couple other friends under **dcua** as usual. Watch out for their writeup too.

If you directly want to see the scripts, go here

### Table of contents:

Under Construction:

HabbyDabby, VisageNovel, DragonScim 1, DragonScim2, Premium Flag (Web) – As no source code published nor Webserver are up

basic, LSB, Rogue Leader, Regular Zips (Forensics)

**[Basics] Crypto – 200**

*Can you make sense of this file?*

*by balex*

This one was a warm-up challenge, the steps are listed below.

Step – 1: Binary to ASCII

Step – 2: Base-64 decode

Step – 3: Rot-16

Step-4: Substitution Cipher

**Flag: utflag{3ncrypt10n_15_c00l}**

### Jacobi’s Chance Encryption – 750

It’s a fairly basic problem. Idea is to reverse the `encrypt`

which is fairly doable if you flip all 0’s to 1’s and everything else to 0’s.

from pwn import * f = open('flag.enc', 'r') l = f.read() final = '' for m in l.strip().split(','): if not m: final+='' if m != '0': final+='0' else: final+='1' print unbits(final)

** Flag: utflag{did_u_pay_attention_in_number_theory}**

**Tale of Two Cities – 800**

*Looks like this book got a little messed up… there are some weird characters in there.*

*by balex*

After an initial skimming over the text, it was evident that they were taken from here. I just diff’ed that with challenge text.

$ diff tale-of-two-cities.txt 98-0.txt 197c197 < up long rows of miscellaneous criminals; n㐾 hanging a housebreaker on --- > up long rows of miscellaneous criminals; now, hanging a housebreaker on 311c311 < “I say a horse at a canter coming up, Joe.�㐻 --- > “I say a horse at a canter coming up, Joe.” 482c482 < turn the leaves of this dear book that I loved, and vainly hope in ti㐌 --- > turn the leaves of this dear book that I loved, and vainly hope in time 645c645,646 < last night when the horses were unyoked; beyond, a quiet coppice-wood,㐟n which many leaves of burning red and golden yellow still remained --- > last night when the horses were unyoked; beyond, a quiet coppice-wood, > in which many leaves of burning red and golden yellow still remained 812c813 < It was a large, dark room, furnished in a funereal manner㐀th black --- > It was a large, dark room, furnished in a funereal manner with black 931c932 < Our relations were business relations, but confidential. I w㐏at that --- > Our relations were business relations, but confidential. I was at that 1014c1015 < “A daughter. A-㑖atter of business--don't be distressed. Miss, if the --- > “A daughter. A-a-matter of business--don't be distressed. Miss, if the 1085c1086 < and memoranda, are all comprehended in the one line, 'Recalled to㐄fe;' --- > and memoranda, are all comprehended in the one line, 'Recalled to Life;' 1199c1200,1201 w㐓oden shoes. The hands of the man who sawed the wood, left red marksany --- > stained many hands, too, and many faces, and many naked feet, and many > wooden shoes. The hands of the man who sawed the wood, left red marks 1255c1257 < broke off abruptly at the doors. The kennel,㐀 make amends, ran down --- > broke off abruptly at the doors. The kennel, to make amends, ran down 1277c1279,1281 㐴There, his eyes happening to catch the tall joker writing up his joke, --- > another.” > > There, his eyes happening to catch the tall joker writing up his joke, 1463c1467 < uncorrupted, seemed to㐀cape, and all spoilt and sickly vapours seemed --- > uncorrupted, seemed to escape, and all spoilt and sickly vapours seemed 1568c1572 < Rendered in a manner 㐄perate, by her state and by the beckoning of --- > Rendered in a manner desperate, by her state and by the beckoning of 1657c1661 < from direct light and air,㐻ded down to such a dull uniformity of --- > from direct light and air, faded down to such a dull uniformity of 1854c1858 < out--she had a fear of my㐉ing, though I had none--and when I was --- > out--she had a fear of my going, though I had none--and when I was 2037c2041 < Under the over-swinging lamps--swinging ever brighter in the bet㐴 --- > Under the over-swinging lamps--swinging ever brighter in the better 2199c2203 < After hailing the morn with this seco㐷salutation, he threw a boot at --- > After hailing the morn with this second salutation, he threw a boot at 2349c2353 < door-keeper this n㐻 for Mr. Lorry. He will then let you in.” --- > door-keeper this note for Mr. Lorry. He will then let you in.” 2467c2471,2472 㐾en or afterwards, seemed to be concentrated on the ceiling of thet him --- > in his pockets, whose whole attention, when Mr. Cruncher looked at him > then or afterwards, seemed to be concentrated on the ceiling of the 2635c2640 < whereat the jury's countenances displayed a guilty conscious㐇s that --- > whereat the jury's countenances displayed a guilty consciousness that 2775c2780 < myself--timorous of highwaymen,㑎d the prisoner has not a timorous --- > myself--timorous of highwaymen, and the prisoner has not a timorous 2974c2979 < “Have you no remem㑟Offset: 0x3400asion?” --- > “Have you no remembrance of the occasion?”

The results shows couple of Mandarin characters and a weird `Offset: 0x3400`

. Let’s break this down, All those Mandarin letters belong to CJK Unicode Family. CJK Family mainly includes Chinese, Japanese and Korean code-points (which also explains full-form of CJK). The characters we found are in sub-category Unified ideographs extension A. The range of those characters 0x3400 to 0x4DBF. These ranges are not static, these were added into Unicode 3.0 in 1999. The ranges may vary if you look at my this write-ups after 10 years. Hence, it explains why the Offset is given as `0x3400`

.

We first of all gather all the Mandarin characters, which gives us this

㐾㐻㐌㐟㐀㐏㑖㐄㐓㐀㐴㐀㐄㐻㐉㐴㐷㐻㐾㐇㑎㑟

The offset here means that we have to get the hex code-point of those characters and subtract it with 0x3400. That would give us how ‘higher’ those letters are if our base is the range of Unified Ideographs Extension A. I’m glad the offset was provided in the question, else it can be confusing but tricky unless you apply Unicode skills. If you are interested in Unicodes, make sure to check my previous writeup.

Now the final output after all that math turns out to be [62, 59, 12, 31, 0, 15, 86, 4, 19, 0, 52, 0, 4, 59, 9, 52, 55, 59, 62, 7, 78, 95] . Decimal to ASCII doesn’t lead to any flag. Now, the hint was released which points to OEIS. The sequence is as follow

[0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186]

Assuming, the flag starts with `utflag{`

we can try to think it reverse manner.

u -> 20th place in Alphabet series if a=0

62 is the 0th index value in our main array.

62 – 20 = 42

We search 42 in the OEIS sequence which is at 20th index. That means we started with 20th index in alphabet series and we ended up at 20th index in OEIS.

To reverse this, we have to create new hashmap/dict which contains letters from ‘a’ to ‘z’ whose values will be real_val_of_alphabets (from 0 to 25 increment) + oeis array values

For instance:

‘a’ = 0 + 0 , ‘b’ = 1+1 , ‘c’ = 2+2 , ‘d’=3+4 , ‘e’ = 4+5 and so on.

Now, we have to see our `codepoint`

array which was [62, 59, 12, 31, 0, 15, 86, 4, 19, 0, 52, 0, 4, 59, 9, 52, 55, 59, 62, 7, 78, 95] and find the value from `0`

th element to `len(codepoint)-1`

th element in our hashmap and find what was the letter it matched to.

So, 62 -> ‘u’ , 59 -> ‘t’, 12 -> ‘f’ and so on.

Here is the code to automate it

# -*- encoding: utf-8 -*- mand=u"㐾㐻㐌㐟㐀㐏㑖㐄㐓㐀㐴㐀㐄㐻㐉㐴㐷㐻㐾㐇㑎㑟" codepts =[] offset = 0x3400 for m in mand: ans = int(hex(ord(m)),16) - offset codepts.append(ans) hashmap_char= { 'a':0, 'b':1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6, 'h':7, 'i':8, 'j':9, 'k':10, 'l':11, 'm':12, 'n':13, 'o':14, 'p':15, 'q':16, 'r':17, 's':18, 't':19, 'u':20, 'v':21, 'w':22, 'x':23, 'y':24, 'z':25, '{':26, '|':27, '}':28 } oeis = [ 0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186] f_dict = {} for k,v in hashmap_char.items(): f_dict[k] = v + oeis[v] flag="" for i in xrange(0, len(codepts)): flag+=f_dict.keys()[f_dict.values().index(codepts[i])] print flag

We run it as:

**Flag: utflag{characterstudy}**

### Alice sends Bob a Meme – 1650

*Eve is an Apple Employee who has access to the iMessage KeyStore (because there is nothing stopping them). They know Alice and Bob use iMessage instead of Signal, therefore they decrypted their messages and see that Alice has sent Bob a meme. Eve suspects more is going on. Can you confirm their suspicions?*

The meme in the image, is a Diophantine equation. Diophantine equation are covered in CTFs in past, the primary challenge being the excellent cryptography problem *Sofies Verden* from ASIS Quals 2017 which involved Sophie Germain identity. It’s a very well known math question turned into a clickbait meme which indeed 99.95% cannot solve (More like finding all the positive solutions). Anyways, the solution to such problem lies in converting the equation into Elliptic Curve.

The problem is something as

a/(b+c) + b/(c+a) + c/(a+b) = N

N(a+b)(b+c)(c+a) = a(c+a)(a+b) + b(b+c)(a+b) + c(b+c)(c+a)

and the cubic model is computed such as from the following research paper.

We find the curve first,

sage: 4*13^2+12*13-3 829 sage: 32*(13+3) 512

Hence, our curve is now y^2 = x^3 + 829*x^2 + 512*x

I binwalk’d the image to find out two files namely `alice.txt`

and `bob.txt`

. The points us to the fact that it’s about ECDH (Elliptic Curve Diffie Hellman). Traditionally, Diffie-Hellman is a key-exchange over a public channel.

In DH, Both parties agree over prime modulus and a generator. We call it p and g respectively. Alice and Bob have their own set of private-key namely a and b. Now, Alice generates their public-key using

A = pow(g, a, p)

and Bob does the same using their private-key

B = pow(g, b, p)

Both the public-key are exchanged & both parties reaches to shared secret key (i.e k = pow(g, a*b, p))

Now, coming to ECDH. I ripped off this image in order to give a better clarity on the topic

The generator here shown as G is chosen as a point on the curve. As you now know, I have the curve, so I need a point which is on that curve. The modulus is provided as M. P and Q both are the point on the curves too. We can prove that using,

For Alice:

sage: (x,y)=(88610873236405736097813831550942828314268128800347374801890968111325912062058, 76792255969188554519144464321650537182337412449605253325780015124 ....: 365585152539) sage: M=108453893951105886914206677306984937223705600011149354906282902016584483568647 sage: (x**3 + 829*x**2 + 512*x) % M 34396641751505811655185387280465330637221522808091140769874333846906504394141 sage: (y**2)%M 34396641751505811655185387280465330637221522808091140769874333846906504394141

For Bob:

sage: (x,y)= (27543889954945113502256551007964501073506795938025836235838339960818915950890, 7592296957398702158364168521744128483246795405529527250535718582 ....: 4478295962572) sage: (x**3 + 829*x**2 + 512*x) % M 44457576863253255146857212842604584291668416287701298166721667908962751007374 sage: (y**2)%M 44457576863253255146857212842604584291668416287701298166721667908962751007374

The modulus M is indeed prime. No tricks involved here. Generator point on the curve can be retrieved if you define the curve over Finite fields, where ground field is `GF(M)`

for our prime `M`

.

sage: EE.gens() ((79218731191285575388815722542324414947282033006078108723420202919633596945165 : 82434376497957979363301482120254426339107668701491715933015661496473414628997 : 1),)

Note that `EE`

is the Elliptic Curve we retrieved defined over the Finite Field. We don’t have singular (apparently, Elliptic curves are non-singular by definition, but humans ¯_(ツ)_/¯ ).

Second, apparent thing to check is whether the curve’s group order is equal to the finite field aka prime modulus. If such case happens, then there exists a linear algorithm to solve DLP for curves of trace one. (N.Smart, 1997). Can be fairly easy.

sage: EE.order() 108453893951105886914206677306984937224124703598890507204412378872931154667424 sage: M 108453893951105886914206677306984937223705600011149354906282902016584483568647

So, no Smart attack here. Let’s check the `order`

sage: is_prime(EE.order()) False

Excellent. The `order`

is a composite number.

sage: ee.order().factor() 2^5 * 3^2 * 617 * 1031 * 460919 * 1284352459083875752760636625085191848403737033002118694776855821

Meaning that Pohlig-Hellman attack could be effective here. It’s very well explained here. The problem now is in the form of `Q=nP`

where P,Q are known.

We are also given a bound n < 84442469965344 to make our job simpler. We can use Pollard’s Lambda / Pollard’s Kangaroo to do the job instead of BS-GS which ships with `discrete_log`

. Alternatively, we could use `discrete_log_rho`

too, but that’s for some other day.

solve.sage

max_val = 84442469965344 M = 108453893951105886914206677306984937223705600011149354906282902016584483568647 # long weierstrass format EE = EllipticCurve(GF(M),[0,829,0,512,0]) P = EE((88610873236405736097813831550942828314268128800347374801890968111325912062058, 76792255969188554519144464321650537182337412449605253325780015124365585152539)) # Q = Pn Pn = EE((27543889954945113502256551007964501073506795938025836235838339960818915950890, 75922969573987021583641685217441284832467954055295272505357185824478295962572)) order = EE.order() subresults = [] factors = [] modulus = 1 # Find partial solutions per each factor for prime, exponent in factor(order): if prime > 10**9: break _factor = prime ** exponent factors.append(_factor) P2 = P*(order//_factor) Pn2 = Pn*(order//_factor) subresults.append(discrete_log_lambda(Pn2, P2, (0,_factor), '+')) modulus *= _factor # Join partial solutions n = crt(subresults,factors) while n < max_val: if P*n==Pn: print("n=%d"%n) break n+=modulus

We get n=1213123123131 , which is apparently our

**Flag: 1213123123131**

### [Basic] RE

*I know there’s a string in this binary somewhere…. Now where did I leave it?*

*by balex*

This was just

strings calculator | grep ‘utflag’

**Flag: utflag{str1ng5_15_4_h4ndy_t00l}**

### MOV – 1200

*You probably know what this is.*

*by jitterbug_gang*

Binary takes no inputs and produces no output. It uses movfuscator to compile the program into “mov” instructions. Without wasting time on static analysis, I fired up demovfuscator on it. Attached *gef* to the patched binary and placed a breakpoint at main, `master_loop`

generates `SISEGV`

, next is to grep in memory for flag regex, and telescope the hell out of it. In just one go, no need to wait byte-by-byte retrieval as master_loop already finished it stuff which the un-patched binary seems to do when building up the flag.

> telescope 0x85f7094 0x085f7094│+0x0000: "utflag{sentence_that_is_somewhat_tangentially_rela[...]" 0x085f7098│+0x0004: "ag{sentence_that_is_somewhat_tangentially_related_[...]" 0x085f709c│+0x0008: "entence_that_is_somewhat_tangentially_related_to_t[...]" 0x085f70a0│+0x000c: "nce_that_is_somewhat_tangentially_related_to_the_c[...]" 0x085f70a4│+0x0010: "that_is_somewhat_tangentially_related_to_the_chall[...]" 0x085f70a8│+0x0014: "_is_somewhat_tangentially_related_to_the_challenge[...]" 0x085f70ac│+0x0018: "somewhat_tangentially_related_to_the_challenge}" 0x085f70b0│+0x001c: "what_tangentially_related_to_the_challenge}" 0x085f70b4│+0x0020: "_tangentially_related_to_the_challenge}" 0x085f70b8│+0x0024: "gentially_related_to_the_challenge}"

**Flag: utflag{sentence_that_is_somewhat_tangentially_related_to_the_challenge}**

### CrackMe – 1200

*Just crack me*

First we need to prepare the environment for the binary to run, It’s a password checker, where it takes the input, does some operations over it, uses `memcmp`

to compare it with `test`

which is also obfuscated. I use Binary-Ninja for the top-level analysis. Again, I reviewed all the functions, specifically `csu_init()`

used `ptrace()`

a low-key Anti-Debug mechanism to ruin over Dynamic debugging. I used `NOP`

it out to patch the original binary.

So, my idea was this. You update the patched binary recursively, change the `memcmp`

third argument from 1 to 64 and perform brute-force byte-by-byte. No need to static retrieval at all. There is a reason why I avoid static retrieval here and relied on total dynamic analysis. Sometimes CTF’s are crunch, you don’t have time to waste reversing stuff, understanding & implementing it back. The competitive part of CTF’s need skills, accuracy and speed.

Anyhow, Back to this. So, I carefully found the off-set to where to patch and I already know what to patch it with. The patch function looks like

def bin_patch(lenbf): d = bytearray(open('./crackme', "rb").read()) OFFSET = 0xd98 d[OFFSET]=lenbf f = open('crackme', 'wb') f.write(bytes(d)) f.close()

Now, idea is pretty simple. You use `string.printable`

charset. Start with length 1, then brute-force input until you find `Correct Password`

and then you break it, Append to the current state and move forward with length 2 and so on. I unfortunately cannot publish the whole solver script here as I used our Internal Library for automating this which is specifically for our core team members. So, sorry about that. But, this part should be fairly doable with determination and coding skills. I leave it as an exercise for the reader.

Within no time, we got

**Flag: utflag{1_hav3_1nf0rmat10n_that_w1ll_lead_t0_th3_arr3st_0f_c0pp3rstick6}**

TO-DO

Forensics

Webs – Once Source is Published or Servers are up