Crypto Wallet

Full solution below. Spoilers ahead.

Task description

Lost access to my wallet and can’t find the recovery seed phrase 😿

Can you help me recover the wallet somehow?

The handout is crypto_wallet.apk and task.txt, which holds the text above. This is a mixed task. Reversing the app gets you to a precise question, and the answer to that question comes from location research. The platform lists it under Rev.

Not solved during the competition

I did not solve this while the competition was running. My own search for the four what3words squares came up empty. The seed phrase in this writeup is the result someone else cracked, and everything after that point is me working backwards from it: why those squares pass, why my scan missed them, and how the checks in the app fit together.

What the app asks for

The app, package com.fortid.cryptowallet, is an Ethereum wallet-recovery screen. You type a 12-word phrase, and on a correct phrase it reveals the flag. The classes that matter:

• MainActivity holds the verification and recovery routine.
• NativeVerifier is a JNI (Java Native Interface, the bridge from Java to compiled C) wrapper around libwalletverify.so, declaring native boolean hasPerfectMatching(boolean[]) and native double[] targetCoordinates().
• VicinityClient, ObjectVicinityService and PendingPartnershipVicinityService are a “vicinity” layer that takes an address and a coordinate and reports whether they are close.

I extracted the APK with unzip, decompiled classes.dex to Java-like pseudocode, parsed the native library’s ELF (Executable and Linkable Format) sections in Python to read its .rodata, and re-implemented the cryptography in pure Python so I could check every step offline.

The native library holds four airport coordinates

lib/arm64-v8a/libwalletverify.so is 4,832 bytes and the Java side loads it with System.loadLibrary("walletverify"). It backs two declared native methods:

public final native boolean hasPerfectMatching(boolean[] p0);
public final native double[] targetCoordinates();

targetCoordinates() returns eight doubles, which is four latitude/longitude pairs. Rather than disassemble the function (no gdb or objdump here), I scanned the library’s bytes for little-endian IEEE-754 doubles that fall in a plausible coordinate range. Eight of them sit contiguously at file offset 0x560:

off=0x0560  33.941589     off=0x0568  -118.408530    # LAX
off=0x0570  41.991750     off=0x0578   -87.889806    # ORD
off=0x0580  44.884755     off=0x0588   -93.222284    # MSP
off=0x0590  40.641311     off=0x0598   -73.778139    # JFK

Pair	Coordinate	Airport
A	33.941589, -118.408530	LAX (Los Angeles)
B	41.991750, -87.889806	ORD (Chicago O’Hare)
C	44.884755, -93.222284	MSP (Minneapolis)
D	40.641311, -73.778139	JFK (New York)

hasPerfectMatching(boolean[16]) reads a 4x4 matrix M and returns true when some permutation p of {0,1,2,3} has M[r][p[r]] == true for every row r, which is a perfect matching in the bipartite graph the matrix describes (every address paired to a distinct airport). The 24 permutations it tries are a 96-byte table immediately after the coordinates, at offset 0x5a0:

000005a0: 0001 0203 0001 0302 0002 0103 0002 0301   [0,1,2,3] [0,1,3,2] [0,2,1,3] [0,2,3,1]
000005b0: 0003 0102 0003 0201 0100 0203 0100 0302   [0,3,1,2] [0,3,2,1] [1,0,2,3] [1,0,3,2]
...
000005f0: 0301 0002 0301 0200 0302 0001 0302 0100   [3,1,0,2] [3,1,2,0] [3,2,0,1] [3,2,1,0]

That is all 24 orderings of four items, one permutation per four bytes, which is what a brute-force perfect-matching check over a 4x4 matrix looks like.

The verification routine and its decoy layer

MainActivity runs this on submit:

1. Call targetCoordinates() to get the four points.
2. Split the 12 input words into 4 triples and build four "///word.word.word" what3words-style addresses.
3. For each (address, point) pair call VicinityClient.checkObjectVicinity(addr, point, 900) to fill the 4x4 matrix, then call hasPerfectMatching.
4. If the matching holds, validate the phrase as BIP-39, derive an Ethereum key and check the address.
5. On an address match, derive an AES key from the wallet private key and decrypt the flag.

The vicinity layer never decides anything, because its one implementation is a stub:

// PendingPartnershipVicinityService.checkObjectVicinity
return new VicinityResult(1,
  "Vicinity verification is not implemented yet. External geospatial partnership "
  + "agreement is pending; recovery requests are temporarily accepted.");

It returns inVicinity = 1 for every call, so the matrix comes back all true, a perfect matching always exists, and the native layer passes for any input. The 900 passed alongside is never read. The layer is still the recovery clue, even though it gates nothing: the phrase is four what3words addresses (three words each, each address a 3 m square), and each square is within 900 m of one of the four airports.

The real gate: BIP-39 to an Ethereum address

Past the decoy, the phrase has to be a real wallet seed. BIP-39 is the standard that turns a list of words into wallet entropy; each word is one of a fixed 2,048-word list, so it encodes 11 bits.

The app maps each input word to its index in assets/bip39_english.txt and silently drops words that are not in the list. The remaining indices are packed 11 bits each: the first 128 bits are the entropy, any bits after that form the checksum, and the app requires checksum == SHA256(entropy)[0] >> 4. For 12 valid BIP-39 words this is exactly the standard BIP-39 check. If words are dropped, fewer than 128 bits survive, the checksum accumulator stays 0, and the test passes roughly one time in 16 anyway, so the app does not strictly demand all-BIP-39 words. A genuine wallet phrase is all-BIP-39, and the solution is too.

Then the standard derivation to an Ethereum address:

• seed = PBKDF2-HMAC-SHA512(NFKD(phrase), "mnemonic", 2048, dkLen=64)
• BIP-32 master = HMAC-SHA512("Bitcoin seed", seed)
• path m/44'/60'/0'/0/0 (hardened indices 0x8000002C, 0x8000003C, 0x80000000, then 0, 0) over secp256k1
• address = keccak256(uncompressed_pubkey)[12:]

The check is a plain string compare against a hardcoded address:

if (v1_47.equalsIgnoreCase("0xdc7d8b278af5f31fed5fe68f50be6d02404fb522")) { ... }

The screen shows that address truncated as 0xdc7d8b…4fb522; the full value lives only in this comparison, so reading the decompiled code is what gives you the whole target.

The flag is tied to the private key

Only inside that if does the app build the key and decrypt:

// address matched; v0_18 holds the 32-byte private key
MessageDigest md = MessageDigest.getInstance("SHA-256");
md.update(v0_18);                                        // private key
md.update("FortID/cryptocurrency-wallet/flag/v1".getBytes(UTF_8));
byte[] aesKey = md.digest();

Cipher c = Cipher.getInstance("AES/GCM/NoPadding");
c.init(DECRYPT_MODE, new SecretKeySpec(aesKey, "AES"),
       new GCMParameterSpec(128, Base64.decode("NaY6LHeKYbf9abvi", 0)));
c.updateAAD("wallet-recovery".getBytes(UTF_8));
byte[] flag = c.doFinal(
  Base64.decode("7ue/WCpa19Wp+mKFu1PHsuTknMRzHqRamlwGVXWJCmMw7smZ/9PzoWkhi80Ezgs9tQ==", 0));

The AES key is SHA256(privKey || "FortID/cryptocurrency-wallet/flag/v1"), and GCM authenticates with a 128-bit tag, so the ciphertext decrypts only under the exact key the correct phrase produces. Patching the address check in the app changes nothing, because the real phrase is genuinely needed to build the key. The ciphertext ships inside the APK and there is no live service.

Why brute force is out and what the search collapses to

Recovering the flag means recovering the private key, which means recovering the phrase, and brute-forcing BIP-39 is 2^128. The intended shortcut is that the phrase is four what3words squares, one near each airport, each with all three of its words in the 2,048-word BIP-39 list. The search becomes: enumerate the all-BIP-39 squares near each airport, then find the combination, in some order of the four triples, whose 12 words pass the checksum and derive to the target address.

I re-implemented the whole derivation and flag decryption in Python and validated it against the canonical all-zero-entropy mnemonic before trusting it:

$ python -I verify_wallet.py
bip39 wordlist len: 2048
abandon vector addr: 0x9858effd232b4033e47d90003d41ec34ecaeda94 expect 0x9858effd232b4033e47d90003d41ec34ecaeda94

abandon repeated eleven times plus about is the BIP-39 vector whose m/44'/60'/0'/0/0 address is published as 0x9858...eda94. My re-implementation reproduces it, so the derivation is correct.

The centre squares are not the seed

The first thing to try is the four squares at the exact coordinates. They are not the seed. Their words are only partly in BIP-39, and no ordering or intra-triple permutation reaches the target address. These four lookups are in the handout as saved what3words pages (upstream/w3w_*.html):

Airport	Centre square	Words in BIP-39
LAX	ridge.combining.liability	ridge only
ORD	slick.agent.across	agent, across
MSP	sock.photo.corner	sock, photo
JFK	happy.rested.water	happy, water

So the seed squares are all-BIP-39 squares somewhere nearby, which means enumeration.

Scanning outward found nothing, and the reason is in the coordinates

Everything in this section comes from my search notes during the event. The what3words API key I had allowed only autosuggest (a membership oracle) and available-languages; the coordinate-to-words calls returned HTTP 402 QuotaExceeded. As an authorised alternative I did coordinate-to-words through geocachingtoolbox.com, parsing its server-rendered output, and cross-checked a sample against what3words autosuggest with clip-to-circle. They agreed.

All-BIP-39 squares turn out to be dense near airports, about one in 20 to 25 squares, because what3words assigns common words in busy areas. I enumerated every square within 50 m of each airport centre (about 3,500 cached requests), giving 45, 40, 40 and 34 all-BIP-39 candidates for LAX, ORD, MSP and JFK. A combination search over all 4! airport-to-triple orderings, checksum-prefiltered and derived at m/44'/60'/0'/0/0, found no match. Two independent solver implementations agreed, as did an earlier complete 24 m sweep.

The mistake was treating the coordinates as exact spots. They are database reference points for whole airports: LAX and JFK match the generic airport points on air-port-codes.com exactly, MSP to within 0.000001 degrees, and ORD looks like a generic point from another source. So the coordinate only says which airport, and the real square can sit anywhere inside the 900 m tolerance, which is why scanning tight rings around the centres kept failing.

The radius is metres, not kilometres, and the other dead ends

The 900 is passed to checkObjectVicinity but never used, so the APK does not name its unit. During the search I argued for kilometres (what3words clip-to-circle takes km, and a perfect-matching check looked pointless if the circles could not overlap). The solution shows it is metres. Converting the solution squares with the geocachingtoolbox.com tool, the distances are:

Square	LAX	ORD	MSP	JFK
///dice.ticket.path	792 m	2,803 km	2,467 km	3,974 km
///slot.escape.oven	2,804 km	676 m	538 km	1,186 km
///sport.glue.survey	2,468 km	536 km	868 m	1,650 km
///reason.manual.myself	3,974 km	1,186 km	1,651 km	343 m

Each square is a few hundred metres from exactly one airport, so the 4x4 matrix is a clean diagonal at a 900 m radius. A 900 km radius would also pair ORD with MSP (537 km), which the author plainly did not intend. 900 m is a round limit just above the farthest square (868 m), so the perfect-matching check only exists so the four triples can be entered in any order, not because the circles overlap.

Other dead ends I tried: the where39 BIP-39 geocoder (all 3-word tiles within 1 km), the exact centre squares under the app’s lenient checksum, every square within 10 m under that lenient rule, a 4-letter-prefix mapping of the centre words onto BIP-39 words, and an exact-phrase web search for published what3words addresses at the four airports (none found). A blind scan out to the full 900 m is about 283,000 squares per airport (roughly 13,000 all-BIP-39), so it is not feasible; the candidate count grows with area and the combination search with N to the fourth, which keeps a bounded scan practical only to about 75 m.

The phrase

I did not find the four squares. They come from the result someone else cracked, who found them by looking at notable places at each airport on the what3words map. The phrase is:

slot escape oven dice ticket path sport glue survey reason manual myself

As the app splits it, these are four addresses, one per airport, with their distances and places:

Triple	Airport	Place (from notes)
///slot.escape.oven	ORD	676 m from the reference point
///dice.ticket.path	LAX	near Gate 75A, 792 m from the reference point
///sport.glue.survey	MSP	868 m from the reference point
///reason.manual.myself	JFK	Terminal 4

The phrase order is ORD, LAX, MSP, JFK, which is the order targetCoordinates() returns the points in (ORD is loaded first in the table). The vicinity layer never constrains the order, so order matters only for the derivation, and the checksum and target address pin it.

Running my re-implementation on that phrase:

$ python -I verify_wallet.py
all 12 words bip39: True
checksum ok: True
derived addr: 0xdc7d8b278af5f31fed5fe68f50be6d02404fb522 match: True

The derived address equals the hardcoded target. Feeding the resulting private key through the same SHA-256/AES-256-GCM steps the app uses, the decryption authenticates and returns 33 bytes:

$ node dec.js
decrypted len: 33 prefix: "FortID{Jus7_" sha256: 5ebf40301fbb

A wrong key would make GCM raise an authentication error rather than return plaintext, so a clean decrypt is itself the confirmation. The full flag is behind the reveal below; the body stops at the recognisable prefix.

Finding the squares from landmarks (follow-up, from notes)

A later test asked whether the squares could be found without already knowing them. I pulled 1,429 named OpenStreetMap features (terminals, gates, parking, stations, shops) within 900 m of the four points and converting each one’s point to what3words, giving 9, 30, 17 and 16 all-BIP-39 squares for ORD, LAX, MSP and JFK, none of them a solution square, so their combinations gave no match.

Each solution square turns out to be a few metres from a landmark: Gate 75A at LAX, Terminal 1 at MSP, the Economy Lot F entrance at ORD, and artwork inside JFK Terminal 4. Scanning every square within 25 m of those four landmarks gave 225 to 229 squares each, of which 18, 19, 10 and 13 were all-BIP-39, and every solution square fell inside its set (2.5 to 20.6 m from its landmark). Testing all 24 orders and every combination (1,067,040 phrases, 66,843 passing the checksum, about 96 seconds) gave exactly one address match, the solution. The honest caveat is that I chose those four landmarks already knowing the answer, so the real difficulty is picking the right landmark at each airport in the first place.

What the three sigpair_*.bin files are

The handout also includes sigpair_42726577.bin, sigpair_504b4453.bin and sigpair_7109871a.bin. These are ID-value pairs pulled out of the APK Signing Block, named by their block ID in hex. None of them affects the recovery gate; they are code-signing metadata:

• 7109871a is the APK Signature Scheme v2 block. The X.509 certificate inside it is self-signed with subject O=FortID, CN=Crypto Wallet CTF (confirmed with openssl x509).
• 42726577 is the verity padding block (its ID spells “Brew”), which is 2,730 bytes and every one of them is zero.
• 504b4453 (its ID spells “PKDS”) is the dependency-info block, 3,976 bytes of opaque data.

They are the kind of thing a full APK parse surfaces, and I include this only so the extra files are not mistaken for part of the puzzle.

Why the design holds and what it teaches

Two layers look like the puzzle and gate nothing: the native perfect-matching check and the four-airport vicinity check both pass for any input, because the vicinity service is a stub. The habit worth keeping is to confirm that a gate actually constrains something before investing in beating it, since the loudest-looking check here was inert.

The layer that does hold is the cryptographic binding. Releasing the flag depends on the wallet private key through an authenticated cipher, so no amount of patching the address compare or the native layer helps; the correct phrase is genuinely required. Constraints like the wordlist, the checksum and the target address make a correct phrase unmistakable once you have it, but they cannot shrink a 900 m search area, so the four triples had to come from outside the APK. Reading the clue at the right resolution, a database reference point for a whole airport rather than an exact spot, is what I got wrong and what a quick check of where the numbers came from would have fixed.

As a design, encoding a seed as a handful of memorable real-world squares is fragile: anyone who learns the four locations owns the wallet, and a real wallet should keep its entropy secret and offline rather than mapped onto guessable coordinates. Re-implementing BIP-39, BIP-32, BIP-44 and keccak and checking them against the all-zero vector is what let me trust every later step without a device or a live service.