Christoph's last Weblog entries

Entries tagged "crypto".

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

• 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.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
while (pow(answer, e, modulus)) % w != challenge:

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.
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.
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.
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.

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.

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()
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()
data = dict()
for i in re.findall(userparse_re, data1)[:100]:
userinfo = get_tweet(i[0])
if userinfo != None:

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.

Created by Chronicle v4.6