Spiraling Out of Control

Challenge:

A message was left by DEADFACE on one of De Monne's machines. In Ghost Town, mirveal mentioned that he posted a hint on Twitter.

This was the message that was left:

fmbi~i{v1d`t3ygz~”vfbn€

Can you tell us what it says? Submit the flag as flag{plaintext}.

Solution:

The first step in solving this challenge was locating mirveal's Twitter account. Luckily, we saved our notes from last year's CTF and knew D34th's Twitter account. We reviewed the accounts that D34th was following, as well as his followers and noticed a follower named Akio that was using the same avatar as Mirveal on the CTF Story page.

The Akio(Mirveal) Twitter account had a single tweet which was simply an image of a Golden Spiral. The Golden Spiral is a visual representation of the Golden Ratio, which is derived from the Fibonacci sequence. In the Fibonacci sequence, each number is simply the sum of the two preceding numbers, e.g. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and so on.

We did some quick Google research for terms like, fibonacci cipher and fibonacci sequence cipher and found a few articles that described a cipher that was similar to the Caesar Cipher, but each character's shift value was determined by the Fibonacci sequence instead of a static value.

With that in mind we wrote a Python script to test out various approaches and soon ran into the first issue… The Fibonacci sequence quickly reaches values that, when applied as a shift value, would result in an integer outside the range of ASCII characters (Unicode as well). We tried various approaches with Modular arithmetic (i.e. mod 26) to "wrap" the Fibonacci sequence in an attempt to keep the values within the ASCII range, but then observed in the plaintext that each character in the ciphertext required a different modulus.

When using the standard Fibonacci sequence we could see that the first 10 characters were decrypting to flag{dynam. Making a guess that the partial decrypted word was going to be dynamic, followed by an underscore, and the flag ending with a '}', we did a few "brute-force" calculations for the required shift values. After a few rounds of failed calculations were wondered if "dynamic" was actually in "leet speak", so we re-did our calculations, with a '1' instead of an 'i', and produced this table:

Cipher Char(dec)	Desired Char(dec)	Required Shift
1(49)	1(49)	0
d(100)	c(99	-1
`(96)	_(95)	-1
€(128)	}(125)	-3

When we saw the 0, 1, 1, … 3 pattern it was an "ah-ha!" moment (facepalm as well, since mirveal's tweet hinted that the sequence stopped at 34…). We replaced the standard Fibonacci sequence with a sequence that repeated after reaching 34, and the flag was revealed. Below is our final Python script that successfully performed the decryption, with some debugging we left in the script, and the output when run.

Note: The ciphertext contained a few Unicode characters, so we converted them to octal to make the individual characters easier to read:

fmbi~i\u0081{v\u008F1d`t3ygz~\u0094vfbn\u0080

#seq = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811]

seq = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

cipher = "fmbi~i\u0081{v\u008f1d`t3ygz~\u0094vfbn\u0080"

plain = ""

for ix, c in enumerate(cipher):
    #shift = seq[ix] if seq[ix] < 35 else seq[ix] % 26

    pt = c

    try:
        pt = chr(ord(c) - seq[ix])
        plain += pt
    except Exception:
        pass

    print(f"{ix}: CHAR: {c}  FIB: {seq[ix]}  PT: {pt}")

print(plain)

"""
# flag{dynam1c_}

+ 56 55
- 1 89
- 1 144

- 3

"""

$ python3 fib.py

0: CHAR: f  FIB: 0  PT: f
1: CHAR: m  FIB: 1  PT: l
2: CHAR: b  FIB: 1  PT: a
3: CHAR: i  FIB: 2  PT: g
4: CHAR: ~  FIB: 3  PT: {
5: CHAR: i  FIB: 5  PT: d
6: CHAR:   FIB: 8  PT: y
7: CHAR: {  FIB: 13  PT: n
8: CHAR: v  FIB: 21  PT: a
9: CHAR:   FIB: 34  PT: m
10: CHAR: 1  FIB: 0  PT: 1
11: CHAR: d  FIB: 1  PT: c
12: CHAR: `  FIB: 1  PT: _
13: CHAR: t  FIB: 2  PT: r
14: CHAR: 3  FIB: 3  PT: 0
15: CHAR: y  FIB: 5  PT: t
16: CHAR: g  FIB: 8  PT: _
17: CHAR: z  FIB: 13  PT: m
18: CHAR: ~  FIB: 21  PT: i
19: CHAR:   FIB: 34  PT: r
20: CHAR: v  FIB: 0  PT: v
21: CHAR: f  FIB: 1  PT: e
22: CHAR: b  FIB: 1  PT: a
23: CHAR: n  FIB: 2  PT: l
24: CHAR:   FIB: 3  PT: }

flag{dynam1c_r0t_mirveal}

The accepted flag was: flag{dynam1c_r0t_mirveal}