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:
$ 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:
{
"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.
+-----------+ +-----------+ +-----------+ +-----------+
| 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:
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 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:
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 possibly 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:
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 successfuly solved this challenge!
The source can be found here. Those interested in code gore can find the script as it was written on the day here.