Rating: 0

# Google CTF - Anonymous Exchange

>I've bought some bitcoins with my credit cards, and some of them attracted attention, but I don't know which ones. Could you find out?
>Challenge running at anon.ctfcompetition.com:1337

Let's take a look:

```Diff
$ nc anon.ctfcompetition.com 1337
Hey. Could you tell me if my cards ccard0x1 through ccard0x40 have attracted the wrong
type of attention? Flagged cards are displayed in their dumps, and their encryption is
deterministic. I seem to have the wrong encoding on my terminal, so I'll need help
there. I'll patch you into a management interface in a few seconds.

Welcome to our telnet dogecoin exchange!.
We've currently frozen most of the operations pending an investigation into potential
credit card fraud with law enforcement.
- NEWACC to create an account.
- NEWCARD to create a test credit card.
- ASSOC <cardx> <accounty> to associate cardx to accounty.
- BACKUP to generate a anonymized encrypted jsonified maybe-emojified backup.
```

The first thing to do is take a look at the BACKUP function. Here's an example account record:

```JSON
{
"account": "d82b2fb9eae6c10b",
"cards": [
{
"card": "b698929890dce9c6"
},
{
"card": "85ff9e8504f55324"
}]
}
```

Without using any of the other commands, we can investigate the database. There are
about 300 accounts and 500 cards, the exact number changes each time, as does the
associations between accounts and cards. We see accounts with 0, 1, 2 or 3 associated
cards. And we see cards that have 1, 2, or 3 associated accounts. After playing around further
we can verify that associations are indeed restricted to these values.
We are allowed to perform associations with the target cards and test
accounts. Additionally, we get cut off after 55 seconds, which limits the number of operations
we can perform.

Given the category of the challenge is Misc rather than Crypto, it is unlikely we
will need to exploit a weakness in the encryption, beyond the fact we are told it
is deterministic. The determinism means that if a card appears twice in the database,
we know it will be represented by the same string.

**The challenge is still running, so I'd encourage you to fire up netcat and have
a stab at a solution before reading on!**

The quantity of noise in the database means that we cannot hope to distinguish
between a randomly generated account and a single account we create. Every valid
arrangement of accounts already exists in the database. The solution is to generate a
sequence of accounts which we can distinguish. In particular we can build a "path" of accounts,
where each consecutive pair of accounts have a card in common. Although there will no doubt
be short paths in the random data, a path of 32 or so accounts is very unlikely to happen by chance.

```Makefile
+-----------+ +-----------+ +-----------+ +-----------+
| ACCT 1 | | ACCT 2 | | ACCT 3 | | ACCT 4 |
+-----------+ +-----------+ +-----------+ +-----------+
| Card 1 | +-----> Card 2 | +---> Card 4 | +---> Card 6 |
+-----------+ | +-----------+ | +-----------+ | +-----------+ ... and so on
| Card 2 +--+ +--> Card 3 | | | Card 5 | | | Card 7 |
+-----------+ | +-----------+ | +-----------+ | +-----------+
| Card 3 +---- + | Card 4 +---+ | Card 6 +---+ | Card 8 |
+-----------+ +-----------+ +-----------+ +-----------+
```
Notice that the first and second accounts overlap by two cards. This allows us
to determine the start of the sequence. The cards in the backup are not ordered,
so without this modification we would not be able to distinguish between the
start and end of the list. Writing the code to perform these associations is straightforward:

```Python
def createAccountWithCards(r):
r.send("NEWACC\n")
accountName = r.recvline().split(" ")[2]
log.debug("Created Account Name: " + accountName)
return accountName

def performASSOC(r,cardName,accountName):
command = "ASSOC " + cardName + " " + accountName
r.send(command + "\n")
response = r.recvline()
if "KO" in response:
log.warn(command + " " + response)
return -1
else:
log.debug(response)
return 0

acc = createAccountWithCards(altered,0)
performASSOC(altered,"ccard"+hex(1),acc)
performASSOC(altered,"ccard"+hex(2),acc)
performASSOC(altered,"ccard"+hex(3),acc)
log.info("Created ACC with cards [1,2,3]")
for i in range(2,65,2):
acc = createAccountWithCards(altered,0)
performASSOC(altered,"ccard"+hex(i),acc)
performASSOC(altered,"ccard"+hex(i+1),acc)
performASSOC(altered,"ccard"+hex(i+2),acc)
log.info("Created ACC with cards ["+str(i)+","+str(i+1)+","+str(i+2)+"]")
```

>NOTE: I'm using [pwntools](https://github.com/Gallopsled/pwntools) as a framework

Now we need to grab a copy of the backup and search for our path within it. The idea
of the algorithm is very simple, we start with one possible path for
every account in the database (assuming the path starts with that account) and look
for a two card overlap with another account. If we find a match, we add it to the
path and continue looking. We stop when we have a path of length 32. There are of course
quite a few cases to try and we have to be careful not to loop back on ourselves.

The code for the backwards search:

```Python
def getPath(alteredJSON, sequences):
newSequences = []
for seq in sequences: #For every sequence in our list of possible sequences
head = seq[-1] #Get the last account in the sequence
overlap = 2
if len(seq) > 1: #We have already found the first element
overlap = 1
accJSON = getAccountByName(alteredJSON,head)
nextSteps = getPossibleNextAccounts(alteredJSON, accJSON, 1, list(seq))
if len(nextSteps) > 0:
for step in nextSteps: #For each possible next step
newSeq = list(seq) #Create a copy of the list
newSeq.append(step) #Add the next step
newSequences.append(newSeq) #Add it to the list of possible sequences
else: #There are no further elements
if len(seq) == 32: #Finish! We found the path!
return [seq]
return newSequences

def getPossibleNextAccounts(alteredJSON, currentAcc, targetSize, noMatch):
possible = []
#Generate the powerset of the cards, then filter it down to the right size.
for overlapSets in filter(lambda s: len(s) == targetSize, powerset(currentAcc["cards"])):
candidate = getNextAccount(alteredJSON, overlapSets, noMatch)
#There might be multiple overlaps due to random chance
while candidate != "NONE":
possible.append(candidate)
noMatch.append(candidate)
candidate = getNextAccount(alteredJSON, overlapSets, noMatch)
return possible

def getNextAccount(alteredJSON, targetCards, noMatch):
for acc in alteredJSON:
if acc["account"] not in noMatch and targetCards in getAccountCards(acc):
return acc["account"]
return "NONE"
```
So now we have our list of accounts in the path and consequently we can work out which
cards are flagged or not. If you have been following closely, you will realise that we
cannot distinguish between the cards in position 2 and 3, or between the cards in position
63 and 64. This is because I was too lazy to write the additional code that would add an
extra account to allow us to distinguish these two cases. Instead I settled for possibily
having to run the script a couple of times. It will only get the wrong answer if the pairs
have different flagged statuses and it guesses wrongly (50% chance for each) which happens
to be quite rare in practice.

Here is the script running:

#### See the original write up (I can't embed the script here)

And there we go! Quite an interesting challenge - it doesn't require much in the way of pre existing knowledge, just some careful thought.
However, of the 1971 teams that completed the introductory challenge in the CTF, only 31 teams sucessfuly solved this challenge!

The source can be found [here](https://www.dennisjj.co.uk/anonExch.py). Those interested in code gore can find
the script as it was written on the day [here](https://www.dennisjj.co.uk/anonExchORIGINAL.py).