Affine math in base32
BITSCTF 2017 fanfie: Breaking an Affine Cipher on a Base32 Flag
A 34-character base32 string is the flag after a substitution on its alphabet. The known prefix BITSCTF{ gives enough letter pairs to see that the substitution is a linear map modulo 32.
- 01
Inspect
The ciphertext is 34 characters from the base32 alphabet, and the task says the flag was base32 encoded and then encrypted.
- 02
Hypothesize
The flag begins with BITSCTF{, so its base32 form gives known plaintext for the first eight ciphertext characters.
- 03
Test
Matching the letter indices shows a fixed linear relation, which is an affine cipher with multiplier 13 and shift 4.
- 04
Solve
Inverting the map, restoring the padding and base32-decoding the result yields the flag.
The challenge text
The fanfie task from BITSCTF 2017 is worth 20 points in the crypto category. Its description is a single line asking for the base32 form of the flag, plus one ciphertext: MZYVMIWLGBL7CIJOGJQVOA3IN5BLYC3NHI. The string has 34 characters, all from the base32 alphabet of RFC 4648, which is the letters A to Z followed by the digits 2 to 7. Those 32 symbols each carry five bits, so every group of eight characters stands for five bytes.
Two facts frame the task. The flag is converted to base32 first, and only then somehow scrambled. And the scrambled output is still base32 text, so the transformation works on the 32-symbol alphabet and not on bytes. That points at a substitution of one symbol for another.
Known plaintext from the flag format
Flags in this contest start with BITSCTF{ and end with a closing brace. Thirty-four base32 characters correspond to 170 bits, which is 21 bytes plus two spare bits, and 21 bytes is exactly the eight characters of BITSCTF{ plus 12 inner characters plus the closing brace. The plaintext therefore has a fully known shape, with only 12 unknown bytes in the middle.
The first five bytes, BITSC, form a complete base32 block and encode to IJEVIU2D. Writing that under the first eight ciphertext characters gives pairs: I becomes M, J becomes Z, E becomes Y, V becomes V, I becomes M, U becomes I, 2 becomes W and D becomes L. Every plaintext symbol maps to a single ciphertext symbol, and the repeated I maps to M both times. A fixed mapping from symbol to symbol is a monoalphabetic substitution, and the number of such mappings is huge unless the key has structure.
Spotting the structure
Numbering the alphabet from 0 for A to 25 for Z, then 26 to 31 for the digits 2 to 7, turns the pairs into numbers. Plaintext index 8 (I) maps to ciphertext index 12 (M). Index 9 (J) maps to 25 (Z), 4 (E) to 24 (Y), 21 (V) to 21 (V), 20 (U) to 8 (I), 26 (the digit 2) to 22 (W) and 3 (D) to 11 (L).
Differences between inputs and outputs show the pattern. Moving the input from 8 to 9 moves the output from 12 to 25, a step of 13. Moving from 3 to 4 moves 11 to 24, again 13. That constant slope is the signature of a linear map, so the cipher has the form E(x) = a x + b mod 32. Plugging in a = 13 and solving for b with the pair (3, 11) gives 39 + b = 11 mod 32, so b = 4. Every other pair then checks out: 13 times 8 plus 4 is 108, which leaves 12 modulo 32, matching I to M.
This is an affine cipher on a 32-symbol alphabet. The multiplier has to share no factor with 32 to be invertible, so it must be odd, and 13 qualifies.
Inverting the cipher
Decryption needs the modular inverse of 13 modulo 32. Since 13 times 5 is 65, which is 1 modulo 32, the inverse is 5. The decryption map is D(y) = 5 (y minus 4) mod 32. A short script applies it to every character and then restores the base32 padding.
import base64
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567"
ct = "MZYVMIWLGBL7CIJOGJQVOA3IN5BLYC3NHI"
pt = "".join(alphabet[5 * (alphabet.index(c) - 4) % 32] for c in ct)
pt += "=" * (-len(pt) % 8)
print(base64.b32decode(pt))
The 34 characters need six equals signs to reach 40, a multiple of eight. The decoded bytes read BITSCTF{…}, with an inner part that is itself base64 text.
A joke inside the flag
The inner twelve characters are valid base64 and decode to the name of a nineteenth-century cryptographer, Kerckhoffs. The task title is an anagram of affine, and the flag points at Kerckhoffs’s principle, the idea that a cipher should be secure when only the key is secret. Here the cipher family is public, the key space has only 512 values, and the known prefix exposes the key at once, which illustrates the principle from the opposite side.
Common wrong turns
Most failed attempts treat the string as base64 or run frequency analysis on a 34-character sample, which is far too short for statistics. Another trap is applying the cipher to bytes after decoding, when it acts on the base32 text. A third is forgetting that the padding has to be re-added before decoding, which makes the decoder raise an error. The shortest route is to notice that the known prefix leaves almost nothing to guess.
What transfers to other challenges
When a ciphertext keeps the alphabet of its encoding, the cipher is operating on symbols. Convert letters to indices, line up known plaintext, and look at differences. A constant slope means a linear key. Small key spaces fall to brute force regardless. The same use of a known file header appears in the zip checksum challenge, and structured-looking cipher output can also be spotted visually, as shown in the comparison of compression and encryption.
Questions readers ask
How many affine ciphers are possible over a 32-letter alphabet?
The multiplier must be odd to be invertible modulo 32, which leaves 16 choices, and the shift can be any of 32 values. That is 512 keys in total, a space that even a hand-written loop can exhaust without any known plaintext.
Why does the base32 alphabet have 32 symbols?
RFC 4648 base32 uses A to Z and the digits 2 to 7, which gives 32 symbols so that each carries exactly five bits. Output is padded with equals signs to a multiple of eight characters.
What is the hidden joke in the task name?
The title fanfie is an anagram of affine, the cipher used. The decoded flag also contains the base64 of a name that points to Kerckhoffs's principle, which says a system should stay secure even if everything except the key is public.
New to capture the flag? Formats, teams and a first-month plan in one place.
Read the CTF guide