Solution to 35C3 Junior CTF challenge DANCEd

DANCEd

crypto

500 (variable)

Writeup

This was the challenge description:

``````Sign up now, for the dance class you always wanted to visit! Totally secure, totally awesome! But be quick, the first few spots are already taken!

nc 35.207.159.114 1337

Source

Difficulty estimate: Medium
``````

And we also got the source for the server, written in Go, here.

The server logic is pretty straightforward. You log in to it using Telnet and can do two things that matter: either register yourself for a dance class, or list all the existing registrations which are encrypted.

Reading through the server code shows that for each encryption, a 64 byte “random” number is generated based on the number of previous registrations, 2 secret numbers and a lot of fixed values. That random number is then XORed to the combination of dance class and name. We guess that the flag is in the name of the first registrant.

To be able to decrypt the first registration, we first need to figure out the two secret numbers that are used to generate the 64 byte number. The generating function looks like this:

``````func doubleRound(block *[4][4]uint32) {
for i := 0; i < 4; i++ {
block[(1+i)%4][i] = block[(1+i)%4][i] ^ bits.RotateLeft32(block[(0+i)%4][i]+block[(3+i)%4][i], 7)
block[(2+i)%4][i] = block[(2+i)%4][i] ^ bits.RotateLeft32(block[(1+i)%4][i]+block[(0+i)%4][i], 9)
block[(3+i)%4][i] = block[(3+i)%4][i] ^ bits.RotateLeft32(block[(2+i)%4][i]+block[(1+i)%4][i], 13)
block[(0+i)%4][i] = block[(0+i)%4][i] ^ bits.RotateLeft32(block[(3+i)%4][i]+block[(2+i)%4][i], 18)
}
for i := 0; i < 4; i++ {
block[i][(1+i)%4] = block[i][(1+i)%4] ^ bits.RotateLeft32(block[i][(0+i)%4]+block[i][(3+i)%4], 7)
block[i][(2+i)%4] = block[i][(2+i)%4] ^ bits.RotateLeft32(block[i][(1+i)%4]+block[i][(0+i)%4], 9)
block[i][(3+i)%4] = block[i][(3+i)%4] ^ bits.RotateLeft32(block[i][(2+i)%4]+block[i][(1+i)%4], 13)
block[i][(0+i)%4] = block[i][(0+i)%4] ^ bits.RotateLeft32(block[i][(3+i)%4]+block[i][(2+i)%4], 18)
}
}

func generateKeyStream(count uint32) []byte {
key := [8]uint32{0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff}
block := [4][4]uint32{
{0x61707865, key[0], key[1], key[2]},
{key[3], 0x3320646e, nonce[0], nonce[1]},
{count, 0x00000000, 0x79622d32, key[4]},
{key[5], key[6], key[7], 0x6b206574}}

for i := 0; i < 10; i++ {
doubleRound(&block)
}
for c := 0; c < 4; c++ {
for r := 0; r < 4; r++ {
fmt.Printf("%08x ", block[c][r])
}
fmt.Printf("\n")
}

var stream []byte
current := make([]byte, 4)
for c := 0; c < 4; c++ {
for r := 0; r < 4; r++ {
binary.LittleEndian.PutUint32(current, block[c][r])
stream = append(stream, current...)
}
}
return stream
}
``````

Analyzing the doubleRound() function shows that no information is lost in the transformations that happen, so it can easily be reversed like this:

``````func doubleRoundReverse(block *[4][4]uint32) {
for i := 3; i >= 0; i-- {

block[i][(0+i)%4] = block[i][(0+i)%4] ^ bits.RotateLeft32(block[i][(3+i)%4]+block[i][(2+i)%4], 18)
block[i][(3+i)%4] = block[i][(3+i)%4] ^ bits.RotateLeft32(block[i][(2+i)%4]+block[i][(1+i)%4], 13)
block[i][(2+i)%4] = block[i][(2+i)%4] ^ bits.RotateLeft32(block[i][(1+i)%4]+block[i][(0+i)%4], 9)
block[i][(1+i)%4] = block[i][(1+i)%4] ^ bits.RotateLeft32(block[i][(0+i)%4]+block[i][(3+i)%4], 7)
}

for i := 3; i >= 0; i-- {

block[(0+i)%4][i] = block[(0+i)%4][i] ^ bits.RotateLeft32(block[(3+i)%4][i]+block[(2+i)%4][i], 18)
block[(3+i)%4][i] = block[(3+i)%4][i] ^ bits.RotateLeft32(block[(2+i)%4][i]+block[(1+i)%4][i], 13)
block[(2+i)%4][i] = block[(2+i)%4][i] ^ bits.RotateLeft32(block[(1+i)%4][i]+block[(0+i)%4][i], 9)
block[(1+i)%4][i] = block[(1+i)%4][i] ^ bits.RotateLeft32(block[(0+i)%4][i]+block[(3+i)%4][i], 7)
}
}
``````

Given this, we can perform the following steps to decrypt the flag.

• Make a reservation with a name consisting of 56 characters, to get 64 bytes of ciphertext
• XOR that ciphertext with the known plaintext, in order to get the generated key
• Run that key through our reversed function to unshuffle all the bits and get us the two secret numbers
• Use those two numbers and position number 0 to decrypt the first entry

This worked, and we got the flag: 35C3_DJ_B3RNSTE1N_IN_TH3_H0USE

Solution to 35C3 Junior CTF challenge pretty linear

pretty_linear

crypto

500 (variable)

Writeup

We were given a PCAP file full of recorded network traffic, and the source code for the server.

The server code that generated the network traffic looks like this:

``````    print(' '.join(map(str, challenge)))
response = int(input())
if response != sum(x*y%p for x, y in zip(challenge, key)):
exit(1)

print('ACCESS GRANTED')
``````

`challenge` and `key` are both arrays consisting of 40 integers that are 16 bytes in length and the response is another 16 byte integer. `challenge` is sent in plain text from the server to the client, and therefor known to us. `key` is a shared secret between the client and the server and never sent over the network. We need to calculate that key in order to crack the challenge. `response` is also sent over the network, from the client to the server.

Line three has the algorithm that is used to ensure that the client and the server both know the same `key`. We can expand that to a more readable form like this:

``````response = c[0] * k[0] % p + c[1] * k[1] % p + ... + c[39] * k[39] % p;
``````

Both variables `response` and `c` are known and `p` is hard coded to 340282366920938463463374607431768211297 in the source code.

Looking into the PCAP file we see that we have 40 of these interactions. Combining those gives us an equation system with 40 equations, each of them containing 40 variables. This is a problem that can be solved by a linear equation solver, but before we can do that we need to get the data out of the PCAP file in a structured form.

We wrote the following program to get the data out of the PCAP file, and also generate a sage program that solves the equation system in Z over 340282366920938463463374607431768211297.

``````from collections import defaultdict
import pyshark
import string
cap = pyshark.FileCapture('c5c0d261333729feb801834d5168ba4c-surveillance.pcap')

streams = defaultdict(list)

for p in cap:
t = p['tcp']
if p:
data = "".join([chr(int(c, 16))
for c in t.get('payload').split(":")])
streams[t.stream].append(data)

print("R = IntegerModRing(340282366920938463463374607431768211297)")

challenges = []
responses = []
for k, v in streams.items():
challenge, response, out = v
print(out)
challenges.append(list(map(int, challenge.split())))
responses.append(int(response))
print("M = Matrix(R, [")
first = True
for c in challenges:
if not first:
print(",")
first = False
print(c, end="")
print("])")
print("b = vector(R,[")
first = True
for r in responses:
if not first:
print(",", end="")
first = False
print(r)
print("])")
print("print(M.solve_right(b))")
``````

Running the generated sage program gives us the key, and lets us attack the next part of the server code:

``````    cipher = AES.new(
sha256(' '.join(map(str, key)).encode('utf-8')).digest(),
AES.MODE_CFB,
b'\0'*16)
print(binascii.hexlify(cipher.encrypt(flag)).decode('utf-8'))
``````

Like this:

``````import os
import math
import sys
import binascii
from hashlib import sha256
from Crypto.Cipher import AES

key = (151166356399959194245460055888166966126,
23349654305343746371904146512921179610,
303231127335861985008837572586617401477,
52564325979162295713031020943288299431,
318561098467762156502271721157519784045,
263049694618319332492436935081367988962,
151925705582116739255625584197651639678,
46319333286788790879399387215584902926,
144250191566113115015826218788418570765,
95097625879948609497612754022619234195,
40890527924981050968775993543458295905,
73015657936779070795829412187806965634,
17764129701686300306686689106838999642,
325835500394544926294581718484613749556,
71443020776832402486826429105359001130,
328905290970722092344104084599942510400,
246319993494260311894585740502008352891,
339251916682414225894494357646852524504,
270753355547506496805860877660621175158,
266604583518913012106937436764867155955,
132952188910249324219774647464400732439,
229485064954594431373138165566214808548,
273124499649767430591820642695664426994,
161206428662237066098654588615704724656,
191676246712534509807283243359699775780,
110791878778380133926865862999743362183,
121869512181659437298676494294916884080,
81324902884339942138294016318959955113,
219404824444265280645688236691554688702,
169041597038940530794876375975659802012,
131851490945732599957487956170326572223,
337190018815691236060142455413012785269,
215436829468576180414177636304832181536,
174614268507338543165725749934608091983,
316523955444804263394840392424504742312,
215434679427738924369625297037020081680,
103769840624100781721896803697739863413,
302813910848119681638497129402557822574,
104414047167186149419822776294661649936,
124689157029586638342169541932443340723)

chipher = "923fa1835d8dbdcd9f9b0e6658b24fce54512fbba71d7a0012c37d2c9dd094a6278593d8d9f7a4aa9fecb66042"

cipher = AES.new(
sha256(' '.join(map(str, key)).encode('utf-8')).digest(),
AES.MODE_CFB,
b'\0'*16)
print(cipher.decrypt(binascii.unhexlify(chipher)).decode('utf-8'))
``````

The flag was: 35C3_G4uss_w0uld_b3_so_pr0ud_of_y0u_r1ght_n0w

35C3 is over

And we are sad, but we are also very happy that we got to experience all the fantastic things that happened, and got to listen to so many high quality talks.

To help people find out what the best talks were so you can watch them from home, we have compiled a curated list by having our members rang what they watched and then apply the Schulze voting algorithm.

Here is the list. All entries link to the video streams over at media.ccc.de.

Hope you have some great chaosflix-and-chill time.

Better password hashing in PostgreSQL with SCRAM-SHA-256

Many connections to PostgreSQL servers are not protected by TLS and for those it’s important that the password isn’t sent as clear text over the network.

PostgreSQL has supported MD5 hashing with salt for a long time, and as we all know MD5 is considered very broken by today’s standards. Not only is MD5 weak, the login sequence only contains 32 bits of new entropy per connection, so if you can listen to multiple connection attempts then you can easily perform a replay attack on the MD5 packet.

Let’s look on how an MD5 based login sequence looks.

Client sends a startup message

length protocol param name param value
int32 int32 str str
88 3 user test

The first element is just a standard length, the second is the protocol version that the client wants to use. PostgreSQL has been on protocol version 3 since version 7.4. One interesting thing about the protocol field is that it’s reused when trying to start a TLS connection. The value 80877103 means that a TLS connection will be initiated instead.

After that a number of parameter name/value pairs are sent. The most important for this topic is the user one, that sets the username.

The packet looks like this as a hex dump:

``````0000   00 00 00 58 00 03 00 00 75 73 65 72 00 74 65 73
0010   74 00 64 61 74 61 62 61 73 65 00 74 65 73 74 00
0020   61 70 70 6c 69 63 61 74 69 6f 6e 5f 6e 61 6d 65
0030   00 6a 61 76 61 5f 73 71 6c 32 5f 63 6c 69 65 6e
0040   74 00 63 6c 69 65 6e 74 5f 65 6e 63 6f 64 69 6e
0050   67 00 55 54 46 38 00 00
``````

Server responds with an Authentication request

type marker length type type specific data
byte int32 int32 various, int32 with md5
‘R’ 12 5 0xfce5c980

What the server responds with is controlled by the pg_hba.conf file. In this case it has a line that looks like this that instructs it to use MD5:

``````# TYPE  DATABASE        USER            ADDRESS                 METHOD
host    all             all             ::1/128                 md5
``````

The type specific data in case of MD5 is a salt value that should be hashed together with the password.

The packet looks like this as a hex dump:

``````0000   52 00 00 00 0c 00 00 00 05 fc e5 c9 80
``````

Client sends a Password message

type marker length value
byte int32 str
‘p’ 40 md5374c5f834de33f6297af8f17aa050229

The hashing method in use here is `"md5" + md5(md5(user + password) + salt)`.

The packet looks like this as a hex dump:

``````0000   70 00 00 00 28 6d 64 35 33 37 34 63 35 66 38 33
0010   34 64 65 33 33 66 36 32 39 37 61 66 38 66 31 37
0020   61 61 30 35 30 32 32 39 00
``````

Improved security with SCRAM-SHA-256

In order to improve the situation the hashing system SCRAM-SHA-256 was introduced, as defined in RFC 5802 and RFC 7677.

It’s a more complicated protocol, but it’s significantly more secure.

Let’s go over the packet exchange of that also.

Client sends a startup message

Same as above, not repeated.

Server responds with an Authentication request

type marker length type type specific data
byte int32 int32 various, str with SASL
‘R’ 23 10 SCRAM-SHA-25

This authentication system uses the SASL packets, types SASL (10), SASL_CONTINUE (11) and SASL_FINAL (12).

The type specific data is a list of mechanisms which the client can choose one of, in this case it has only one field.

The packet looks like this as a hex dump:

``````0000   52 00 00 00 17 00 00 00 0a 53 43 52 41 4d 2d 53
0010   48 41 2d 32 35 36 00 00
``````

Client responds with the first password message

type marker length mechanism length parameter string
byte int32 str int32 str
‘p’ 54 SCRAM-SHA-256 32 n,,n=,r=/z+giZiTxAH7r8sNAeHr7cvp

When sending a password packet back as part of a SASL exchange it has a few more fields. Most notable is the parameter string, whose content is determined by RFC 5802.

Notable is that this message also contains a username in the attribute `n`, but the server doesn’t use that so we leave it blank.

The attribute `r` is the client specified nounce, in other words the entropy that the client supplies.

The packet looks like this as a hex dump:

``````0000   70 00 00 00 36 53 43 52 41 4d 2d 53 48 41 2d 32
0010   35 36 00 00 00 00 20 6e 2c 2c 6e 3d 2c 72 3d 2f
0020   7a 2b 67 69 5a 69 54 78 41 48 37 72 38 73 4e 41
0030   65 48 72 37 63 76 70
``````

Server sends a SASL CONTINUE message

type marker length type type specific data
byte int32 int32 various, str with SASL CONTINUE
‘R’ 92 11 r=/z+giZiTxAH7r8sNAeHr7cvpqV3uo7G/bJBIJO3pjVM7t3ng,s=4UV68bIkC8f9/X8xH7aPhg==,i=4096

The server asks us to perform 4096 iterations of the hashing in attribute `i`, the RFC specifies that the complete exchange without network lag should take at least 0.1 seconds. So this value will likely increase with future versions of PostgreSQL.

In attribute `r` the server has taken the entropy that the client supplied and added its own.

`s` is a server generated salt for the user.

The packet looks like this as a hex dump:

``````0000   52 00 00 00 5c 00 00 00 0b 72 3d 2f 7a 2b 67 69
0010   5a 69 54 78 41 48 37 72 38 73 4e 41 65 48 72 37
0020   63 76 70 71 56 33 75 6f 37 47 2f 62 4a 42 49 4a
0030   4f 33 70 6a 56 4d 37 74 33 6e 67 2c 73 3d 34 55
0040   56 36 38 62 49 6b 43 38 66 39 2f 58 38 78 48 37
0050   61 50 68 67 3d 3d 2c 69 3d 34 30 39 36
``````

Client performs the hashing and returns another password message

type marker length parameter string
byte int32 str
‘p’ 108 c=biws,r=/z+giZiTxAH7r8sNAeHr7cvpqV3uo7G/bJBIJO3pjVM7t3ng,p=AFpSYH/K/8bux1mRPUwxTe8lBuIPEyhi/7UFPQpSr4A=

Here the client has done the actual work of hashing the password and sending the proof of that in attribute `p`.

`c` is channel binding data. This isn’t used by the pgAdba connection code yet, so we will come back to this in the future.

The packet looks like this as a hex dump:

``````0000   70 00 00 00 6c 63 3d 62 69 77 73 2c 72 3d 2f 7a
0010   2b 67 69 5a 69 54 78 41 48 37 72 38 73 4e 41 65
0020   48 72 37 63 76 70 71 56 33 75 6f 37 47 2f 62 4a
0030   42 49 4a 4f 33 70 6a 56 4d 37 74 33 6e 67 2c 70
0040   3d 41 46 70 53 59 48 2f 4b 2f 38 62 75 78 31 6d
0050   52 50 55 77 78 54 65 38 6c 42 75 49 50 45 79 68
0060   69 2f 37 55 46 50 51 70 53 72 34 41 3d
``````

Server ends the authentication exchange with a SASL FINISH message

type marker length type type specific data
byte int32 int32 various, str with SASL FINISH
‘R’ 54 12 v=d1PXa8TKFPZrR3MBRjLy3+J6yxrfw/zzp8YT9exV7s8=

The server sends a server signature so that the client can verify the server in attribute `v`.

The packet looks like this as a hex dump:

``````0000   52 00 00 00 36 00 00 00 0c 76 3d 64 31 50 58 61
0010   38 54 4b 46 50 5a 72 52 33 4d 42 52 6a 4c 79 33
0020   2b 4a 36 79 78 72 66 77 2f 7a 7a 70 38 59 54 39
0030   65 78 56 37 73 38 3d
``````

Performance testing our Asynchronous PostgreSQL library

We have done some performance testing between the pgjdbc driver and the pgAdba driver for PostgreSQL.

The test was performed 20 times for each number of threads, with a warm-up set before. The raw data can be found as text or csv

A linear regression gives that pgAdba is 16.6% faster than pgjdbc.

Method

The test was designed to expose the connection library, rather than the postgresql database itself. So if your application does a large number of very cheap sql queries then this might be relevant.

The test is done by performing a large number of http requests against an spring boot web server, for each request the server takes the url of the requests, sends it to the database server as a string, which echo the request right back without any disk I/O, and the server returns the url as a string to the client.

The test code for the async library pgAdba is:

``````    @RequestMapping("/{val}")
public CompletableFuture<String> index(@PathVariable("val") String val) {
Submission<List<RowColumn>> sub = session.<List<RowColumn>>rowOperation("select \$1 as t")
.collect(Collectors.toList())
.submit();

return sub.getCompletionStage().thenApply(rc -> rc.get(0).at("t").get(String.class)).toCompletableFuture();
}
``````

and the code for the blocking pgjdbc driver looks like this:

``````    @RequestMapping("/{val}")
public String index(@PathVariable("val") String val) throws SQLException {
PreparedStatement ps = connection.prepareStatement("select ? as t");
ps.setString(1, val);
ResultSet rs = ps.executeQuery();
if(rs.next()) {
return rs.getString("t");
} else {
throw new RuntimeException("error");
}
}
``````

The machine that the test ran on had a local database server, that the web server communicated with over localhost, for minimal latency between the web server and the database server.

Configuration and setup of the test

System configuration to ensure that we don’t run out of open sockets while the test runs: `echo 1024 65000 > /proc/sys/net/ipv4/ip_local_port_range`

`sysctl -w net.ipv4.tcp_tw_reuse=1`

System Hardware:

• CPU: Intel i7-4500U 1.8 GHz
• 8 gig of ram

Software versions:

• OS: Ubuntu 18.04.1 LTS
• Spring boot: 2.0.5.RELEASE
• pgjdbc: 42.2.5
• postgresql: 10.5-0ubuntu0.18.04

jmeter command: `jmeter -n -t jmeter-performance-test-5.jmx -l /tmp/res-5 -e -o /tmp/out-5`

Java command to run spring boot: `java -server -XX:+UseParallelGC -XX:+AggressiveOpts -XX:+UseLargePages -Xmn1g -Xms2g -Xmx2g -jar target/pgadba-example-application-spring-boot-0.1.0.jar`

pgjdbc code here

The image was produced with R like this

``````mydata <- read.csv(file="/home/capitol/project/hackeriet/blog/assets/performance-data-pgadba.csv", header=TRUE, sep=",")

library(ggplot2)

ggplot() + geom_smooth(data=mydata, aes(x = threads, y = async, colour = "pgAdba"))
+ geom_smooth(data=mydata, aes(x = threads, y = sync, colour = "pgjdbc"))
+ xlab("Number of threads") + ylab("Queries per second") + ggtitle("")
+ geom_point(data=mydata, aes(x = threads, y = async, colour = "pgAdba"))
+ geom_point(data=mydata, aes(x = threads, y = sync, colour = "pgjdbc"))
+ expand_limits(x = 0, y = 0) + theme_light()
``````