In this challenge, we are given a server which accepts encrypted commands and returns the resulting output. First we define our oracle go(cmd).
import urllib2
def go(cmd):
return urllib2.urlopen('http://delphi-status-e606c556.ctf.bsidessf.net/execute/' + cmd).read()
This simply return the status from the server. It is common for this kind of CTF challenges to use some block-cipher variant such as some of the AES modes.
The first guess I had was that AES-CBC was being used. That would mean that if we try to flip some bit in a block somewhere in the middle of the ciphertext, the first decrypted part would remain intact, whilst the trailing blocks would get scrambled.
Assume that we have four ciphertext blocks 
and the decryption is 
Now, we flip a bit in 
so that we get 
then we have 
Turns out this is not the case. In fact, the error did only propagate one block and not further, i.e.,
Since 
def xor(a, b):
return ''.join(chr(ord(x) ^ ord(y))
for x, y in zip(a, b))
cmd = '8d40ab447609a876f9226ba5983275d1ad1b46575784725dc65216d1739776fdf8ac97a8d0de4b7dd17ee4a33f85e71d5065a02296783e6644d44208237de9175abed53a8d4dc4b5377ffa268ea1e9af5f1eca7bb9bfd93c799184c3e0546b3ad5e900e5045b729de2301d66c3c69327'
response = ' to test multiple-block patterns' # the block we attack
split_blocks = [cmd[i * 32: i * 32 + 32]
for i in range(len(cmd) / 32)]
block = 3 # this is somewhat arbitrary
# get command and pad it with blank space
append_cmd = ' some command'
append_cmd = append_cmd + '\x20' * (16 - len(append_cmd))
new_block = xor(split_blocks[block].decode("hex"),
response).encode('hex')
new_block = xor(new_block.decode("hex"),
append_cmd).encode('hex')
split_blocks[block] = new_block
cmd = ''.join(split_blocks)
#print cmd
print go(cmd)
We can verify that this works. Running the server, we get
This is a longer string th\x8a\r\xe4\xd9.\n\xde\x86\xb6\xbd*\xde\xf8X\x15I some command e-block patterns\n
OK, so the server accepts it. Nice. Can we exploit this? Obviously — yes. We can guess that the server does something like
echo "{input string}";
First, we break off the echo statement. Then we try to cat the flag and comment out the rest. We can do this in one block! Here is how:
append_cmd = '\"; cat f* #'
Then, the server code becomes
echo "{partial + garbage}"; cat f* #{more string}";
The server gives the following response:
This is a longer string th:\xd7\xb1\xe8\xc2Q\xd7\xe8*\x02\xe8\xe8\x9c\xa6\xf71\n FLAG:a1cf81c5e0872a7e0a4aec2e8e9f74c3\n
Indeed, this is the flag. So, we are done!
![\mathbb{F}_2[x] / P(x)](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BF%7D_2%5Bx%5D+%2F+P%28x%29&bg=ffffff&fg=000000&s=0 "\mathbb{F}_2[x] / P(x)")
. We use the following mapping: 
, 
, 
, 
, 
, 
, 
, ![[M(x)x^{64} + C(X)] \mod P(x).](https://s0.wp.com/latex.php?latex=%5BM%28x%29x%5E%7B64%7D+%2B+C%28X%29%5D+%5Cmod+P%28x%29.&bg=ffffff&fg=000000&s=0 "[M(x)x^{64} + C(X)] \mod P(x).")
![H(x) = ([K(x)+O(x)]x^{64} + [K(x)+I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x) \mod P(x).](https://s0.wp.com/latex.php?latex=H%28x%29+%3D+%28%5BK%28x%29%2BO%28x%29%5Dx%5E%7B64%7D+%2B+%5BK%28x%29%2BI%28x%29%5Dx%5En+%2B+M%28x%29%29x%5E%7B64%7D+%2B+C%28x%29%29x%5E%7B64%7D+%2B+C%28x%29+%5Cmod+P%28x%29.&bg=ffffff&fg=000000&s=0 "H(x) = ([K(x)+O(x)]x^{64} + [K(x)+I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x) \mod P(x).")
![H(x) = \underbrace{([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)}_{\textnormal{Independent of the key}} + K(x)(x^{128}+x^{128+n}) \mod P(x).](https://s0.wp.com/latex.php?latex=H%28x%29+%3D+%5Cunderbrace%7B%28%5BO%28x%29%5Dx%5E%7B64%7D+%2B+%5BI%28x%29%5Dx%5En+%2B+M%28x%29%29x%5E%7B64%7D+%2B+C%28x%29%29x%5E%7B64%7D+%2B+C%28x%29%7D_%7B%5Ctextnormal%7BIndependent+of+the+key%7D%7D+%2B+K%28x%29%28x%5E%7B128%7D%2Bx%5E%7B128%2Bn%7D%29+%5Cmod+P%28x%29.&bg=ffffff&fg=000000&s=0 "H(x) = \underbrace{([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)}_{\textnormal{Independent of the key}} + K(x)(x^{128}+x^{128+n}) \mod P(x).")
![\left(H(X) + ([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)\right)(x^{128}+x^{128+n})^{-1} = K(x) \mod P(x).](https://s0.wp.com/latex.php?latex=%5Cleft%28H%28X%29+%2B+%28%5BO%28x%29%5Dx%5E%7B64%7D+%2B+%5BI%28x%29%5Dx%5En+%2B+M%28x%29%29x%5E%7B64%7D+%2B+C%28x%29%29x%5E%7B64%7D+%2B+C%28x%29%5Cright%29%28x%5E%7B128%7D%2Bx%5E%7B128%2Bn%7D%29%5E%7B-1%7D+%3D+K%28x%29+%5Cmod+P%28x%29.&bg=ffffff&fg=000000&s=0 "\left(H(X) + ([O(x)]x^{64} + [I(x)]x^n + M(x))x^{64} + C(x))x^{64} + C(x)\right)(x^{128}+x^{128+n})^{-1} = K(x) \mod P(x).")
, then it can be used to unravel the message, i.e.,
and 
. Given these exponents, we can use the Euclidian algorithm without modification to find a linear combination that is 
. Scanning through the list, we find that two exponents, 
and 
, are relatively prime, i.e.,
-to-
through a mixnet. Then, the following procedure is performed.
to the message.
of the recipient.
and some additional randomness 
.
of the mixnet.
. The following is then performed by the mixnet:
to that address.
partners which are regularly communicated with, and the aim is to unravel the recipients. Denote the total number of users in the system 
, the number of senders in each batch is denoted 
(where 
), and the number of recipients in a batch is denoted 
since more than one sender can send messages to the same recipient. It is assumed that all senders uniformly chooses their recipient among the set of their partners in each communication.
for some 
.
. .
is recorded (again, when Alice is known to communicate). If the following is satisfied
and 
,
. With high probability, this is reduce the cardinality of 
have cardinality 1, i.e., contain only one recipient. Of course, since all sets were disjoint, the communicating parters of Alice have been unraveled.
be the number of batches recorded, then the expected number of recorded communications with a non-parter of Alice is 
, while for a partner it is 
.
. Clearly, determining the communicating partners of Alice is not hard.
. The assumptions made in [1] are also a bit unrealistic, in particular the assumption about a uniform recipient distribution among all other communicating parties.
, partition the graph into disjoint partitions such that each partition contains exactly one node, which we will denote ‘middle node’, and all nodes being adjacent to the middle node. For a more detailed description, see [1].
. The black nodes are forced to be middle nodes, and therefore either a green or a red node must be middle node. To provide dependence among variables, the variables must be linked at least once using operator-subgraphs. These are shown as dashed lines. The long-dashed lines are connected using Equality graphs, while the short-dashed are connected with Negation graphs. For instance, if we set 
, then the same variable the remaining clauses must be forced to 
. Likewise, the oracle for The Plague’s problem will output 
bit operations.
. To transfer secret vector 
to the tag, it uses a function 
, the shared secret 
and random coins. This procedure is given below.
makes the GRS-attack on the vector 
cumbersome, we can still make a slight modification of the attack.
. We the run the protocol 
times until we obtain a 
or 
, based on some threshold parameter. From this line of execution, we can decide the value of 
. Repeating the process 
gives us the secret vector 
.
and 
via the function 
, we can form a new secret vector 
, and generate 
from 
of the vector 
, where each 
. However, we do not care which permutation.
is defined as follows.
-vectors and pertube that position for each 
in the secret is non-zero, then 
and a pertubed vector 
, find a vector 
such that 
and 
agrees in as many points as possible.
and permute 
columns from the 
first rows of 
indexed by bits in the 
-field.
columns in the first the 
columns that is zero in the 
, output it. If none is found, repeat from 1.