FFSK - WriteUp

众所周知歪歪歪英文很烂求轻喷

0. Intro

In the game period, only one team had solved this problem: MapleBacon, a genius team at the University of British Columbia. I’m happy about their praise, but after checking their solution I think what truly “impressive” is their creativity and persistence.

Strongly recommend reading their awesome solution: https://maplebacon.org/2022/06/actf-ffsk/

FSK = Frequency-shift keying.

FFSK = Double FSK or Fast FSK, whatever.

This problem is designed to invite participants to have a look at the principle of communication.

1. Description

A journey to solve a misc problem always begins from a problem description. Here’s it:

I’ve bought the second commercial modem for computers in a big city of the UK.

激情澎湃的球迷迷恋这个地方。遇上球赛季，酒吧里的热情、呐喊、啤酒、摇滚，足球让这个城市充满活力和希望。
从三万英尺的云端望去，往日的生活成了一个遥远微小的地图。
阳光明媚的日子，开始出发，北京时间00:50 开始起飞，一个梦的距离，就可以到达荷兰阿姆斯特丹，短暂停留之后，然后转机飞往英国
南航的飞机配置完备，全程可以充电，还有wifi，影视屏有面前最新的电影。睡睡醒醒，在飞机上觅到一部《北京爱情故事》，让我在三万英尺的空中哭的稀里哗啦。

Just Google it, and you’ll realize what it means:

• second commercial modem→Bell 103, corresponds with the file name “modem.wav”

• a big city in the UK: Manchester, which refers to the famous coding method.

• The source of the long Chinese paragraph: https://kknews.cc/zh-hk/travel/e6yjp34.html

  It describes a trip to Manchester, which is indeed a big city in the UK.

2. Bell 103

Here’s an article that shows how the Bell 103 protocol works: https://vigrey.com/blog/emulating-bell-103-modem

So two key points need your attention. First, characters are stored in ASCII code and are little-endian; second, it has 2 channels for communication: one for the server-side(2025/2225 Hz), and another for the client-side(1070/1270 Hz).

You can also find it from the spectrogram of the .wav file.

2. Server channel

Using the minimodemtool (See MapleBacon’s write-up) is functional.

Also, you can find some useful tools in GitHub: https://github.com/laurenschneider/audiodecoder

It may be a faster way. In fact, the solve.py is based on its code.

After all, you’ll see this on the server channel:

HINT_Hamming@ddddPdddddddPdddPdPP(20).ECCode; Content: Why do you use such
a slow method with a high Bit Error Ratio for communication? It took me a lot of
effort to correct bit-flips, making sure the communication was less
error-prone...that is 2 say, THE ORIGINAL PROTOCOL IS WRAPPED BY SOME OTHER
TRANSFORMATIONS! Fortunately, we can now communicate properly on another channel
while enjoying a vacation in this BIG CITY--I mean, IEEE 802.3.....Wait, what is
the new protocol? Guess by yourself!

3. Client channel

We can extract the bit string on this channel using the same method but just make some tweaks of frequency. You’ll get a bit string of 53640 bits.

Notice that the bit string contains only “01” “10”, that is what Manchester is all about. The IEEE 802.3mentioned in the server channel message is actually to make sure you decode in the right way: there are 2 opposite ways to map 01/10 to 1/0, but what is widely used is defined in IEEE 802.3, which says “01”→1 and “10”→0

Then the key problem is to solve Hamming code. From the given information, you’ll realize the block size is 20bits. Implement it by yourself or just Google/GitHub/StackOverflow it.

Find every “1” bit in a block, XOR their positions, and magically you got the error bit position(0 if no error) which is a well-designed feature of Hamming code, then just flip the bit.

Actually, every block has, and only has an error bit: that’s an intended design to notify you that you’re on the right way