# 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 1337Hey. Could you tell me if my cards ccard0x1 through ccard0x40 have attracted the wrongtype of attention? Flagged cards are displayed in their dumps, and their encryption isdeterministic. I seem to have the wrong encoding on my terminal, so I'll need helpthere. 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 potentialcredit 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 areabout 300 accounts and 500 cards, the exact number changes each time, as does theassociations between accounts and cards. We see accounts with 0, 1, 2 or 3 associatedcards. And we see cards that have 1, 2, or 3 associated accounts. After playing around furtherwe can verify that associations are indeed restricted to these values.We are allowed to perform associations with the target cards and testaccounts. Additionally, we get cut off after 55 seconds, which limits the number of operationswe can perform.
Given the category of the challenge is Misc rather than Crypto, it is unlikely wewill need to exploit a weakness in the encryption, beyond the fact we are told itis 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 havea stab at a solution before reading on!**
The quantity of noise in the database means that we cannot hope to distinguishbetween a randomly generated account and a single account we create. Every validarrangement of accounts already exists in the database. The solution is to generate asequence 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 doubtbe 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 usto 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 thestart and end of the list. Writing the code to perform these associations is straightforward:
```Pythondef 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 ideaof the algorithm is very simple, we start with one possible path forevery account in the database (assuming the path starts with that account) and lookfor a two card overlap with another account. If we find a match, we add it to thepath and continue looking. We stop when we have a path of length 32. There are of coursequite a few cases to try and we have to be careful not to loop back on ourselves.
The code for the backwards search:
```Pythondef 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 whichcards are flagged or not. If you have been following closely, you will realise that wecannot distinguish between the cards in position 2 and 3, or between the cards in position63 and 64. This is because I was too lazy to write the additional code that would add anextra account to allow us to distinguish these two cases. Instead I settled for possibilyhaving to run the script a couple of times. It will only get the wrong answer if the pairshave different flagged statuses and it guesses wrongly (50% chance for each) which happensto 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 findthe script as it was written on the day [here](https://www.dennisjj.co.uk/anonExchORIGINAL.py).