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.

If you directly want to see the scripts, go here

Table of contents:

[Basics] Crypto

Jacobi’s Chance Encryption

Tales of Two Cities

Alice sends bob a meme

[Basics] Reversing

Mov

Crackme

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

Attachments

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

Attachments

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 0th 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 + 829x^2 + 512x

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