CTF Team at the University of British Columbia

[ACTF 2022] FFSK

26 Jun 2022 by - Angus


Intro

This is the challenge entitled “FFSK” from Azure Assassin Alliance CTF 2022.

The given description is as follows:

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

激情澎湃的球迷迷恋这个地方。遇上球赛季,酒吧里的热情、呐喊、啤酒、摇滚,足球 让这个城市充满活力和希望。

从三万英尺的云端望去,往日的生活成了一个遥远微小的地图。

阳光明媚的日子,开始出发,北京时间00:50 开始起飞,一个梦的距离,就可以到达荷 兰阿姆斯特丹,短暂停留之后,然后转机飞往英国

南航的飞机配置完备,全程可以充电,还有wifi,影视屏有面前最新的电影。睡睡醒醒 ,在飞机上觅到一部《北京爱情故事》,让我在三万英尺的空中哭的稀里哗啦。

A modem.wav file is provided. As the name suggests, it’s a WAV file that sounds like modem communication, and presumably is a signal of some sort.

During the competition, it was solved by exactly one team - us!

First off, some meta musing stuff

If you’re boring enough (like me) to have done a bunch of escape rooms, puzzle hunts, and the like, you’ll eventually get an idea of what a “good challenge” is. In my opinion, the important things:

  1. You shouldn’t have to guess (that much).
  2. You should know when you’re making progress.
  3. Red herrings are generally bad.
  4. If you use something to make progress, you shouldn’t have to use it again.

Usually, this isn’t too relevant for a CTF - you only need to figure out one exploit or two to get a flag - but this challenge gave the impression that there’d be many more than two steps required for a solution. So it’s useful to think of this like an escape room, where we have an inventory of items, and each item will serve exactly one purpose to make progress in the challenge.

Building an inventory

I can read maybe a couple Chinese characters, but thankfully [insert search engine of choice] does a much better job. Eventually I found a blog post with identical text, and it described a trip to Manchester, which happens to be a big city in the UK.

Searching for “the second commercial modem for computers” leads to the Wikipedia page for the Bell 103 modem. This excerpt will be relevant:

The Bell 103 modem used audio frequency-shift keying to encode data. Different pairs of audio frequencies were used by each station:

  • The originating station used a mark tone of 1,270 Hz and a space tone of 1,070 Hz.
  • The answering station used a mark tone of 2,225 Hz and a space tone of 2,025 Hz.

And the challenge itself is named “FFSK”, which evidently stands for fast frequency-shift keying. There aren’t too many details on the “fast” part, but the other words certainly line up.

Thus, we’ve used up the challenge name and description, and in return, we’ve got a fairly good hunch that the given WAV file uses FSK to encode data, and it’s using the frequencies used by the Bell 103. And something to do with Manchester?

To convince ourselves of this, we can write copy Stack Overflow code to compute the power spectrum of the given signal:

powerspectrum

Those four peaks correspond to 1070, 1270, 2025, and 2225 Hz - the frequencies used by the Bell 103. So we’re on the right track!

Standing on the shoulders of amateur radio operators

Here’s a fantastic program which will be incredibly useful throughout this challenge.

It even comes with built-in presets for the Bell 103, so we run it and get…

$ minimodem --rx --file modem.wav 300
### CARRIER 300 @ 1250.0 Hz ###
U��`f�fM��ߚ��if�Y����Zi�/j�KxY3��Z�i�jZ�~�5�8f�c
                                                ��eV#�EǪ��U�+�5��ۖ�YU��Zb���UifY��f+����Y��e�ؙj�Y�����0Z��U����{���U��-f�e�����Yُ�j�0�Vib5K��bM�?�s������-إ��~ߚefbfac+��Zs�ө�if��ؕf�ff�`V���^V��z�5�e�3�M��o�禕����{��Õ�eΖe��ZUMV�i��
                                      `e�V��Ugȩi��u��Z�i�3MK+Kn�;�eK-
                                                                     +�e��Y����iif��c���j��l�����M�ȧ�?KZf�;�cV��k�K�~33��jÚ
                             i���Ț�Z~MΞnUj�eYS�c�ۚ5'����Y�Ú@3?=����S��h���U�������ߥإ����~�ZY�����egZVL`��jZK�i�~{-Se������j��s��SSSS�j���f�ؖ�jYϩ�]�ZUK��i;��j���n~?�YM-j���Yi�i��nYl�-K�^��3K�Z����e��ÖZ�+��e�����eo��fv
                           ����+V[#����Z��ji����UM����b��r����i�SU�5#jffn���֖�3�Ym#iKS�Uj�ef-��s���L��Ue��X��U�j@������KMMÜ�SY��niZj�`Mi��z��KUK,�f��n�cS�Y��K䂦�����jYeb�-�[��#MK+Õ����fnUV�e���Ye�Mi��#ت�?����۩�~`if�sff��c�eMU��eU�;Z���5fZi�+U��M�i��ྦ���nYi��j�����ؖ����=��ەS��ie#�����US�V�i���e�j�;k5�nj�۩�{��e3���k�if���bV���geۖ��US
                                                S�n�U+���e���c;��i�bs-�-+3
### NOCARRIER ndata=955 confidence=1.863 ampl=0.140 bps=298.50 (0.5% slow) ###

[further results snipped as they're much the same...]

Hmm. It looks like it confidently decoded a bunch of garbage. The output also shows that it interpreted the signal using 1250 Hz, though - examining the minimodem source shows that it uses the 1270/1070 Hz pairing by default, so the program must have shifted the frequency slightly to better match the data. We haven’t used the other pairing of 2225/2025 Hz though. What does that give?

$ minimodem --rx -M 2225 -S 2025 --file modem.wav 300
### CARRIER 300 @ 2250.0 Hz ###
�����:HIT_Hammin'@d$ddPdddddddPddddPP(28).CCode; C'nW��; 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 PROTOCL IS WRAPPED BY SOME OTER
TRANSFORMATION! Fortunately, we can now communicate properly on another channel
while enjoying a vacation in this BG CITY--I mean, IEEE 80r.3.....Wait, what is
the new protocol? Guess by yourself!
### NOCARRIER ndata=503 confidence=2.049 ampl=0.148 bps=300.02 (0.0% fast) ###

This looks way better! The start of the message is kind of garbled (and unfortunately, ignoring it will prove problematic later on…), but everything else is parseable. Another reference is made to a “big city”, and combined with the “IEEE 80r.3” leads to Manchester code, specifically the IEEE 802.3 convention.

OK, so let’s do a quick inventory check:

We don’t know what the last thing is, so the other thing seems good to work on now that we can guess that the initial decoding was garbage because it required an additional Manchester-decoding step.

Reversing the Manchester code is simple enough - a falling edge (1 followed by 0) is a 0, and a rising edge (0 followed by 1) is a 1. Notably, there should never be three consecutive 0s or 1s in the signal.

Oh say can you C

Fortunately (unfortunately?), minimodem is written in C and is fairly easily to build from source, so I spent a few hours trying to decipher and add to the code. I ended up realizing that instead of attempting to be clever and join bits together, it was a lot easier to read the entire signal in and calculate each bit in one pass, and ran the following snippet:

// in minimodem.c:
// make the buffer large enough to read the entire signal in one go
samplebuf_size = 40000000;

// in fsk.c:
// code to manually read all bits
for (int i = 0; i < 107280; i++) {
    memcpy(fskp->fftin, samples+ (i*bit_nsamples), bit_nsamples * sizeof(float));
    fftwf_execute(fskp->fftplan);
    float mag_mark  = band_mag(fskp->fftout, fskp->b_mark,  magscalar);
    float mag_space = band_mag(fskp->fftout, fskp->b_space, magscalar);
    // mark==1, space==0
    debug_log("%d", (mag_mark>mag_space));
}
// no need to do anything else in this run
exit(0);

This gave a bit string that miraculously had no instances of three 0s or 1s in a row, so Manchester decoding worked and gave a string of 107280/2 = 53640 bits.

In retrospect, all this code does is break up the initial signal of 17164800 samples into 107280 sections, and determine whether each section looked more like a 1270 Hz (mark) signal, or a 1070 Hz (space) signal. It would’ve been much simpler to write a Python script, but…too late.

Quick maths break

There are a lot of magic numbers here, but everything actually divides very nicely, so props to the challenge author for making it so.

The initial signal contains 17164800 samples of a single audio channel at 48000 Hz. The Bell 103 uses a baud rate of 300, which means that 160 samples should be used to decode each bit. Thus, there are 17164800/160 = 107280 bits to be decoded, which is conveniently an even number so Manchester decoding works with no problems.

As stated previously, a Good Challenge should minimize guessing and give good indicators of progress, so when things seem to work out in a coincidence, it’s likely very intentional.

OK, now what?

At this point, I tried feeding the 53640-bit string back into minimodem’s decoding algorithm with little success. Thankfully, I only ended up wasting a few hours (only), because the organizers released a few hints:

  1. 所有人都认为,吃鸡蛋前,原始的方法是打破鸡蛋较大的一端。可是当今皇帝的祖父 时候吃鸡蛋,一次按古法打鸡蛋时碰巧将一个手指弄破了,因此他的父亲,当时的皇帝, 就下了一道敕令,命令全体臣民吃鸡蛋时打破鸡蛋较小的一端,违令者重罚。 老百姓们 对这项命令极为反感。历史告诉我们,由此曾发生过六次叛乱,其中一个皇帝送了命,另 一个丢了王位…关于这一争端,曾出版过几百本大部著作,不过大端派的书一直是受禁的 ,法律也规定该派的任何人不得做官。 ——乔纳森·斯威夫特,《格列佛游记》
  2. Hamming code block size: 20bits
  3. Bell 103

The third hint is useless, since we’ve already used that information. The first hint is a Gulliver’s Travels quote that mentions “Big Endian”, which is the only remotely relevant term in the quote. And the second hint…let’s go back to our inventory:

Imagine a very loud slap - that was me bringing my palm and forehead together after realizing the “garbled” part of the first signal decoding was probably not actually meant to be garbled. Playing around with some of the minimodem arguments (namely -c and -l) gave a very slightly different, but very much more useful message:

�����rHINT_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!

The message itself is cleaned up a bit, and notably “TRANSFORMATION” in the original decoding became plural form, but the beginning of the message now clearly references Hamming code, giving a mapping of which bits are used for parity checking and which bits are used for data.

Hamming it up

The math again works out perfectly: we can split 53640 bits perfectly into blocks of 20 bits.

Conveniently, the Wikipedia article uses 20-bit blocks as an example, so the procedure I followed here was:

  1. Read the Wikipedia article.
  2. Give up.
  3. Copy the first search engine result for Hamming code implementation.

This surprisingly worked out, albeit with some missteps where I thought that the “big endian” clue was supposed to be used here. Once I got the code working, a couple clues that I was on the right path revealed themselves:

  1. Every block of 20 bits had a single bit error.
  2. And all of the error indices were between 1 and 20, which isn’t guaranteed since 5 parity bits could indicate an error between indices 1 and 32.

Applying the error correction and removing the parity bits results in a new string of 40320 bits. We just have this and the “Big Endian” hint left in our inventory…

Fixed-width fonts FTW

This step happened mostly by accident. I printed out the resulting string from the previous step in a Python shell, and here’s what part of it looked like:

bits

It’s much less obvious without being able to scroll up and down, but:

and this pattern repeats with a period of 10 columns. This was incredibly lucky, as my terminal happened to be 190 columns wide.

If this hadn’t happened, I might’ve lucked out by resizing my terminal window and noticing the identical columns. Failing that, I (hopefully) would’ve realized that there was another thing left in the inventory: the actual FSK decoding of the signal that we’d left behind many steps ago. The convention for a single ASCII character is 1 stop bit, followed by 8 ASCII character bits, followed by 1 stop bit. The MSB should always be 0, and the start and stop bits happen to be identical, even though they don’t have to be, so this all indicates that we’re looking at padded ASCII characters.

This is also where the “Big Endian” hint finally reveals its use - kind of: it got me careful to check endianness of the ASCII characters, so I had to reverse the bit order to parse them correctly. Which means that they were little-endian, but in any case they decoded to sane-looking characters. (Also, yet again, the string of 40320 bits evenly divided into blocks of 10 bits.)

The final steps

The sane-looking characters in question were:

 data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAFMAAABTCAYAAADjsjsAAAALf0lEQVR4n
O1dZ4gVPRfO6tp7F0XFuopi1xV7ARsqtj+ioFjRP4odFUVELKAo6A8LKqxdxN77H1HE3hUVsWLvrnXfe
fJx8p2Zm8zMnTv3vso7D2Rv7iQnk8mdk5yckk3LsSAihIJ0/Jk4caK4ePFi6I3nzZtXHDhwwLPex48fR
e/evWU+d+7c4vDhw9p66CP6SkA91I8H3bp1E9+/f4+Lxg8aNWokBN7Mjh074u0MPeXPnz/HD16/fq1or
MEx1jt27Jit/R8/fvhqnwN9SsazYgxzhf4T/YeR7rzQuHFj0b59+8ANvnnzRqxbt05btn37dvHw4UOZr
1q1qujTp4/MFyhQQIwfP17VW7x4scr3799fVK5cWebxyestXbpUpKWlufanSpUqol+/ftqyIUOGiJIlS
3o/lAEnT54UFy5c+P8FJ5tbnY2bdThu3rxpZPMuXbqosu7du2vpwbqCsQ9Y2wRMCcKD/Tp37mxkc/Q1E
WCsRMTmyUEMm3N8+vRJXL9+3bORUqVKiRo1anjWq127tnj37p3MlytXTpw9e1bmsSI3bdpUS2O9PaJQo
UIyX7RoUVGnTh1VlpmZKX79+uV5Tz+4d++eePXqlWe9unXrisKFC+sL8bqa2PzMmTO+VrKBAwcqGjc25
9i7d6+qV6JECXXdyeY8dejQISG2BExsjmfw86wYk4jNUwBXNk8mcuXKJYV6gD4BrM78+8+fP8Xv379lH
p/fvn3zbDtPnjyy/VTjX3szsRPBwCA9f/5cXcf8SdeR2rVrp8pOnTolLDb1TH52XclAxOYhIhrMEJHSO
XP69Oni/PnzMt+sWTMxZ84cT5oFCxYIa+8e132aNGkSqH+JIqWDiYE8dOiQzPvV9mDQ/xZEbB4iXN9M7
GwsYdazkZYtW/q6mSV0i9KlS8t8mTJlxPr1633RJYIKFSoIS6D2rOf3GTAmRrjtgIIgyA4omSlSdPyli
GFz6CNv3boVuMEHDx4Yyx4/fiyVJwAUHhkZGTKPnc3du3dVPboOPHr0SHz58kXmCxYsKCpVqqTKbt++r
fI1a9ZUux7c5/Pnzwn11Q8wVjbgdU2V2cKkz3QzW0C5QWVORQfXZ6INAtqm625sHmaK2DxkSDaHYgF72
rCRL18+23d+H8iZ2dnZMu+mvOA06enpisYJtEFlbjpOZ5/CglTOJLScJQDTah6PddJPcrJ5MhGxeYiIB
jNEyDlz6tSp4tKlS/JC3759xciRI2UeItK4ceNkHgrXPXv2KEKutMDOZsqUKTIPsWT48OEyj3lk9+7dn
p0oUqSI2Lp1q8xDTOratasqmz9/vmjYsKHM49OPrnLmzJni3LlznvU4Fi5cKI4fPy7zUJTMnTtXWw/jQ
aLjiBEj7GZk8LofG5A1MLb5gYs5ybQBuZl6TXATjUzgNiA8mwmZmZmq3qJFi2xlEZuHCMnmMJmS+MFNo
8WLFxfWr/y/iun2zRJUY6RGIzYEYAYlGpTv27dPlTVv3lwqOJyAnYfqkb2HAHPw169fZR5KEvSVsH//f
nBWTHsvXrxQeZhveR84YBIhsy2e4e3btzIPrxYToBAhZQe8UmyIm4figDUINpa15jtVFkTR4bYDCpISV
XQ4EbF5iJC8C/9Ia+KXF+BEhQSA/T58+KAlxAqMFd4J7D7ev38v837MsgDMu5hSCMRuTqCPXLlgLVyeH
h1ugNKF2gO7cxMzB/qT4+ETLMcCr2cQjw7Oshx8NXejCeLR4UxB/DM5MjIyVFtZWVnGepBkvPoSKTpCh
qdBzWT4wmuPacAJrMYmGu5LiTzVwye1Bbbl9GjPxGJBWJxLJbgP3Ys/D+8b0ejuBRqb9OHG5m7gQjtPY
J144VefGUaChKGDX6GdIzJbJBHRYIaImDlz27ZtKowFjqXLly+XeYgl1uuv6g0YMEBMnjxZ5o8ePSrmz
Zsn87DZmEyr8M7QORVAzLL24DKPOYjTDxo0SMyYMUPmoYyZMGGCKjOFrkybNk050sKJFvcl9OrVSzvX3
7hxQ9tnAM9NoiPGgzvc2gDeN9mAsKknZGdnG8UciBU6emcyiVMcbooOv6EridqAnHMmF40iZ9cUQbI5N
vk5GvGDv84wo0JvSQA7k/4PuwheRgDLwqdSBzhjXb58OeZ6POLOiRMntGzu19ELShOYj51o0KCB7TtCe
YjN79y5o8zI2DHRc0tljyffGWDSZ3KEoehwY3M/KWyPjkifmSJEgxki5GBarCC3TEiTJk1ShRAv6DrF4
ngBLitEA2Uu5hpKXLQyAXMgp9HNxTpAIczpKEGBbEK9evVUXzds2ODrPhwYK6KXY4iLmPRp4ndquum6T
jbTwZo6FA0+nRp6PwhCgx8hXjq+2OUECLvnY4W2IjYPEfKn3Llzp1r616xZoyJd+S+HgHceAbt27Vqxc
eNGmd+1a5cqq169uhJNoBzmNNhdderUSebBFjoRBvfkNGi7TZs22s6DtUk0wk6HQgk3b94s2wcgviEym
HD//n2ti4wxhM8B7Lp0XArlsBxMbOcIkCdNmm5+HR2ih0ZDVAatPV2H7w+noR+MaHThyeioicYJaNqJt
TGQRMdpkOftgSYRvyrEb5oQsXmISIOwCcUA7UYg/bdq1cqTkJttnz59qpQjeEOI/cGCo0aNUjTwCMHOC
QBbzp49O6ZdLAR8BQabP3nyROYxLZACA8BbR28m3nJ6A9F22bJlZf7ly5c27w5IFPGe64FpUGfvWr16t
dixY4fMy10TBvNPCt53wk05zBUdsCOZ6iWaoOTRIVJ0JBGSR6BjJHbh/uRBAOGeVlKT6RQA+1GAlRu4a
ReszIP8jxw5ovzYTXIwNg5uHhqEq1evimfPnmnLcB8dm2MRpmdVR/GkCia7kd8UxKMjiOOW3xQpOpKIa
DBDhBxMBNKTW0yYibu8AHB8hUebM0G0CgK4t+jac1OooE/UPyh6/QDiHrXNbVhw8KW2MIZy1cFW0RTFE
CZMC1LQCAjTTsZNjuRRGU6ljtt9qI/8uAoserTwYQwjNg8RMTorHOlF/ulBgBA6cnYNArxV165ds/WHd
j34NJ1ThLJixYp5to+dHr2R1apV09Zp3bq1WLVqlfruJuJxxAwmZDm/ByslC/z+3OCFGEoeL8nh1xBXq
1YtzzqQlYOMQcTmIcJVNY0jvWbNmuXZCPy8x4wZ41kP4SFXrlyJuY7dRVZWlsxbsq/04iDgkNKhQ4dq2
xs8eLDnIoKdDW/PhNOnT6s8+shpcOqiLy0+JPdUHV9m2gEFDV3xE9UbRuKKDm7q5SlSdISMlJ4ew4/Ig
aLDdpBnAEDJQGyuU0QACDMxnYDIAdYmRQeUI7yvXLZs0aJFzGYEgEdHSgeTh9AhNqdHjx4JtedmxiVgU
A4ePOhZD3MkmXvdaJYsWWJsI2LzEBENZohI6WD27NlT7nGRVqxYIffISPyUQjrtgBI/TBoHJhM9EhfUy
5cvr67D7kT0Y8eOtdFwHUT9+vXV9U2bNqnrUAZzGlM8E5x9qQ4ikVM6Z8IARgfOYyBMCg7TdSw2/MD6H
OaFgetUhi0ptYG86ZB7TuN2HxPwDFQPzxaxeYhwfTNxWLEluHs24nqkFwNWQgoFxMHQEDMAGPbpXzDg1
+am5mXLlinRBp+8P1zVBnpie27HgkMrp+FKiy1btii2x06PbFKgwRnwBC52DRs2TB1qjd0ZtS2dE9x2Q
EHwJwTvB0EUvP+HQXp0wJmK/NPD/HcM0FBT4D2wcuVKpULDAkEnFmLC52bWihUrqjx2SjTJ4yz40aNHa
++L8BZ+LxMQxkJKC+Qp0B8+SKTuc/sXDpiaSL+K4H/aKclz6jGYf+vxZRx+PTp4uJ/fqF4Tm/MUKTpCh
nzfpTdCEuBU90MZQO5+PDwEqyVFpTmNYegbRQPzs0CcaNu2rXRn9IJTaUFTCoR+P4BEoXNJx/T4DxR8h
ZK81B6uAAAAAElFTkSuQmCC

👀 👀 👀, as the saying goes.

Pasting all this into a browser gave a QR code:

qr

There was a QR code challenge in this CTF that had only one solve, but thankfully this code could be scanned and contained the text ACTF{wow_h0w_IEEE_U_r}, which is the end of our journey.

Takeaways