SekaiCTF Banner

Matryoshka Writeup


Sekai CTF Misc Challenge - Matryoshka

My school’s CTF team competed in SekaiCTF 2022, an incredibly well-produced CTF competition by Project Sekai. After hours of work, my friend and I finally cracked Matryoshka, rated at Expert with only 14 solves by the end of the event. Although we weren’t quick enough to first blood, I wanted to share our writeup, as we thought the challenge was a super fun solve.

The Problem

As the name implies, this challenge contained many different layers to it, each rather unique and unrelated. Matryoshka was rated level 4 - Expert by the team, and was written by Project Sekai team member pamLELcu.

Provided for this problem were two images: Matryoshka.png and Matryoshka-Lite.png, the latter of which was uploaded a few hours into the CTF after feedback that the first image was slightly too complex.

Also provided was an initial hint, stating that

“One extra bit will double the 8 colors you already have, but ain’t these new colors too similar to the old ones?“.

Layer 1

Looking at the provided code and output, it was immediately obvious that the smiley faces were being colored using ANSI Color Codes, and after copying over the code to a local python file and running it a few times, we were able to track how they were generated:

  • Input characters from stdin was converted to 8-bit binary numbers
  • The first four bits of each character were saved in l, and the last four bits in h
  • l and h were then mapped to the corresponding ANSI escape codes - 4-bit numbers 0000-0111 became 40-47, while 1000-1111 became 100-107
  • Two smiley faces were printed for each character in the input string - one colored corresponding to the first four bits, and one colored corresponding to the last four bits
  • These smiley faces were printed in reverse order - despite the variable names implying that the program colored according to the higher-order bits and then the lower-order bits, we found that in a group of two smiley faces, the first smiley was colored according to the last four bits, while the second smiley was colored from the first four bits.

NB: This describes the encoding used in Matryoshka-Lite, but the original Matryoshka image follows much the same pattern, only instead of encoding each character as two smiley faces with differing background colors, it varies both the foreground and background colors of the smiley faces, allowing all 8 bits to be encoded in a single smiley face.

After understanding how the inputs were encoded, it was then relatively easy to begin decoding the encoded glyphs in the image. For example, the first four smileys of the encoding of flag{あなたと私でランデブー?} are cyan, cyan, bright blue, cyan, or 6, 6, c, 6 in hex. Since the python script prints the binary chunks in reverse order, this corresponds to the hex codes 66 6c, or fl.

Using this same method to decrypt the unknown input from data.txt in the image, we found that the sequence of smiley faces corresponded to the hex string 68 74 74 70 73 3a 2f 2f 6d 61 74 72 79 6f 73 68 6b 61 2e 73 65 6b 61 69 2e 74 65 61 6d 2f 2d 71 4c 66 2d 41 6f 61 75 72 38 5a 56 71 4b 34 61 46 6e 67 59 67 2e 70 6e 67, or https://matryoshka.sekai.team/-qLf-Aoaur8ZVqK4aFngYg.png.

Layer 2

Following that link resulted in an image of a registration confirmation for the Project Sekai CTF, with a QR code on the left hand side. What stood out to us immediately was the horizontal lines of noise running across the entire image.

Our first instinct was to scan the QR code, but that was of course too obvious, as it led to an all-too-familiar video.

We then turned to the noise lines, but basic analysis did not reveal anything too promising at first glance, as each line contained over a thousand different colors. We did notice two unique characteristics - each line began with two pixels of color codes #0000FF and #FFEC9D, and each line ended with repeated 5-color blocks of colors #000000, #FFFF00, #0000FF, #FF0000, and #00FFFF, but we had no clue where to go from here. We would have likely remained stumped for several more hours had another hint not been released, stating that:

““Never reinvent your own wheel”, people say. But Apple insisted on thinking differently when parsing PNGs.”

This clue was enough to point us to an interesting quirk of Safari, in which certain old Safari versions would display PNG images differently than all other devices. Not having access to an old Apple device, I decided to do something I should have done weeks ago, and call my parents.

The Dad Strat

In perhaps a new CTF record for widest team age variance, I recruited the services of my father, who I knew for a fact would not have updated his iMac anytime within the last decade. After a brief explanation of what a CTF was and how little running it involved, as well as how to take a screenshot on OSX, I received a picture I had never seen before on my machine:

true

Layer 3

Scanning this new QR code prompted me to add a COVID-19 vaccination record to my Health app - apparently, we were up to date on our shots, having recieved 3 doses of the Moderna vaccine from Yamaha and Crypton Media CV-01 (references to the vocaloid software that Project Sekai is based on).

We poked around at the immunization records, but were unable to find anything useful in the data. Discouraged, we took a break for a few hours to try our hand at some of the other challenges.

Returning to Matryoshka, we thought that maybe Apple’s Health app was not equipped for CTF challenges and perhaps was stripping out useful data. Decoding the QR code with an online tool revealed that it had the payload

shc:/56762959532654603460292540772804336028702865676754222809286237253760287028647167452228092863457452621103402467043423376555407105412745693904292640625506400459645404280536627540536459624025250555056338566029120106413333400028742635076939734552056936583171064558751131556353203754372575033328200705643838552934743139500009536061356931346955643709527105115665600005602172234467374542085807222475347132034424395261373056004444002400085237353061222027453167672627082630290769235375711135114127401104212540537525556303742533507136503255653563264154433970205436100050743522116306752331635775741156433654585503107626684254686208403754634470273768056171327607656125712725523234611005361121030308333867583166536725643767425270646323270003005623700860226659203405252357762043663326362209257233442225631073757558424358121058221221247175065067275426364058293454221133236771205077255211441131752363046604226175031256730654443172527522070726232026532434301128375372255668000400627667676055323160225036622041105858255222692922334259596624276377446745261173582545412027102861666538363053246255715622773453607507284404720407630733005623703641432800427011066429357722525365740010257264576557765569557135536228273331723728623059574332602964335058526177070375095735563159552930336664240727603959105433044575393334503567543958542929065332126645230910313334672722391208422438276434441236775655650958267743437110394352455760210354655321596331533463522358444058636442336866670845305568693721662269635473434227715411302507646165766341072469394221072671236868392755064436586159754123754210552170093809524555337700313654703040673106437576344009087611676326535274567421423023706811744311775220407005454032310440346554616620552130066153666738533667226435276755422240350073103639763904405705005555244371301010730641435756764057646755286006396271642377067569577743576669054164110561644535096843257762673432272976686542737404354077010832356003656226634535455971326660756506220359605868077353056052347436404527397258656831553804624139525240420467593362371139026720436433630272626572681040385977300452644174

The shc:/ protocol confirmed that this was in fact a vaccination record, encoded as a Smart Health Card. Looking online for SHC decoder tools, we came across this tool. Plugging the data in revealed that along with our vocaloid vaccine doses, the payload contained information about the patient, which Apple likely stripped, assuming that the patient would already have their health information stored in the Health app.

{
   "fullUrl": "resource:0",
   "resource": {
         "resourceType": "Patient",
         "name": [
            {
               "family": "CTF",
               "given": [
                     "Project",
                     "SEKAI"
               ]
            }
         ],
         "birthDate": "2020-09-30",
         "contact": [
            {
               "name": {
                     "text": "flag"
               },
               "telecom": [
                     {
                        "system": "url",
                        "value": "data:text/html;base64,PGF1ZGlvIHNyYz0iaHR0cHM6Ly9tYXRyeW9zaGthLnNla2FpLnRlYW0vOGQ3ODk0MTRhN2M1OGI1ZjU4N2Y4YTA1MGI4ZDc4OGUud2F2IiBjb250cm9scz4="
                     }
               ]
            }
         ]
   }
},

Layer 4

Decoding the base64 string in the telecom field of the SHC payload revealed the next layer - <audio src="https://matryoshka.sekai.team/8d789414a7c58b5f587f8a050b8d788e.wav" controls>.

This WAV file contained words of some sort behind a painful background noise. At this point, I believe my friend and I simply ran the file through several denoising websites until it was clear enough to distinguish what was being said - using the NATO phonetic alphabet, the flag SEKAI{KandoRyoko5Five2Two4Four} was read out.

However, I quite liked the official solution posted by the Project Sekai team. Opening the WAV file in Audacity, we see that it is a stereo signal with two very similar high amplitude channels. The two channels are not in fact identical, and splitting the stereo track into two mono audio channels and playing the two at the same time removes all noise and plays back crystal clear audio. I thought this was a very clever intended solution, and ended up taking inspiration from it for a challenge I authored later.