Christoph's last Weblog entries

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.

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:

• does something with RSA
• public exponent is slightly uncommon (\(2^{16}+3\) instead of \(2^{16}+1\)) but that should be fine.
• uses openssl prime -generate to generate the RSA key. Doesn't use -safe but should also be fine for RSA purposes
• You need to do a textbook RSA signature on a challenge to get the flag

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')

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)

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()

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.

#!/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