I was participating in the STACK the Flags 2020 CTF by GovTech Singapore over the weekend and found that one of the challenges for the "Miscellaneous" category was particularly very interesting so decided to do a writeup for it since I have learnt so much during the challenge.
This is the first ever CTF writeup that I have written so apologies in advance if there are any mistakes and errors. I have tried to write it in a more elaborate way so that I can share my thought process and the things I have learnt along the way.
With this, let's jump right into it!
The challenge was to decode the partially visible QR code provided below.
Prior to this competition, I had no knowledge at all on how QR codes work so i took this as an opportunity to learn about it.
Firstly, after analyzing the image provided, the text below was pretty easy to understand for anyone, which basically says "Note to self: Secret is in the QR code" so I knew that the flag will show up if I can figure out what's in the QR code.
Now on the QR code, I have tried to scan it with different QR scanner applications on my phone just in case but as expected, none of them worked since the QR code is only visible partially.
Hence, I have tried to search on "how to decode a partially visible QR code" on google and found a number of interesting articles such as this and this, which were of huge help for me to understand how QR codes work.
Now there are basically two ways to decode this: the easy method and the difficult method.
I will share about the easy method first because the hard method contains several technical information not everyone might want to read.
Easy method (using QRazyBox)
During my google search above, I have also come across this tool called QRazyBox which can help to decode partially visible / mal-formed QR codes. I thought that this was very helpful and uploaded the image provided by the challenge but the tool did not recognize the QR.
I also tried to crop just the QR part and upload but it still showed the same error message so I knew I needed to clean up this QR code by myself because it is likely that the top left big square of the QR code (which I have later learnt that its used for positioning of the QR code) was missing.
Hence, I tried to recreate the visible parts of the QR code in Microsoft excel manually (because it is easier to shade the different bits). It was a bit tedious but was worth it after seeing the clean QR.
Now when i tried to upload this cleaned QR to the QRazyBox, it works.
Using the Tools > Extract QR Information, I've managed to get the flag in the QR code. However, the flag seems to be incomplete.
At this point of time, I have already obtained the flag via the difficult method which I tried first so I already know what to fix but if this was not the case, below were the things I would first suspect:
- There was no closing curly bracket "}" at the end
- Based on the pattern of the flag, "Recovery" should be "R3c0v3ry" instead of "R;c0v3ry"
- Hence, there were a few different flags that I could try as below:
govtech-csg{QR_3rr0r_R;c0v3ry_M4giC!~}
govtech-csg{QR_3rr0r_R;c0v3ry_M4giC!}
govtech-csg{QR_3rr0r_R;c0v3ry_M4giC}
govtech-csg{QR_3rr0r_R3c0v3ry_M4giC!~}
govtech-csg{QR_3rr0r_R3c0v3ry_M4giC!} [Correct flag]
govtech-csg{QR_3rr0r_R3c0v3ry_M4giC}
Difficult Method (Manual)
During the initial Google search, even though I had the impression that QRazyBox would be the way to solve this challenge, since I wanted to take this opportunity to learn about how QR codes are built too, I decided to take the manual route by following this awesome writeup.
Starting part is the same since I needed to rebuild the QR code in the excel.
The top left part was missing in the original QR but I could make a guess and add in a square with the same size since this is a standard for all the QR codes.
I needed to understand the basics to rebuild this so after some reading ups, I have learnt that the three large squares (called the "finder patterns") and the small square at the bottom right part of the QR is mainly used for alignment purposes of the QR code so that the scanner knows what is the orientation it is looking at.Same goes for the two lines (one horizontal and one vertical) called "timing patterns" indicated in yellow in my reconstructed QR code as below.
Also there is something called "format info", which are very important pieces of information about the QR code typically displayed in 2 identical sets of 15 bits around the "finder patterns".
Now I have learnt that in the challenge's partially available QR code, I do not have the top left part of the information but I have the bottom part which contains bits #8 to #14, which actually contains the most important parts of the QR's format info (especially bits #14 to #10).
For QR codes, bits are read in binary with black representing 1 and white representing 0.
Hence, in my partial QR, I can read them as below (the order has to be from #14 to #10):
1 0 0 1 1
However, this cannot be used as is since QR codes are XOR'd with a mask of 1 0 1 0 1 so I needed to reverse this first before using.
Original — 1 0 0 1 1
XOR reverse — 1 0 1 0 1
Result — 0 0 1 1 0
Again, in here, the first two bits (#14 and #13) are mainly used for error correction so I can ignore for now and focus on the last three bits 1 1 0, which indicates the mask type that is being used for the whole QR.
Basically, below are the different mask types.
From these, I have identified the mask type I need to use (110) and created side by side with my QR in the excel.
After removing the irrelevant parts, the mask became like below and ready to be XOR-ed.
Now for the QR codes, we have to read the data starting from the bottom right to top left in the zig-zag pattern like below.
Starting from the bottom right corner of our QR code, the first four bits are showing the type of QR (#1 to #4 below). Here our values (after being XOR-ed with the mask we identified earlier) is 0 1 0 0, which means that this QR code is 8-bit byte type (the other types are numeric — 10bits, alphanumeric — 9 bits).
The next 8 bits (from #5 to #12) show up to how much binary information this QR code can handle, which is not important for my purpose here so I will skip that.
The bit after #12 would be the start of our data so I have continued to do the XOR-ing with the mask to get the below. I just did it partially because the data beyond this is unrelated.
This gives me the binary values as below, which upon conversion to ASCII, gives me the flag. However, the last byte (yellow-shaded part which corresponds to the character "~" ) is not the correct value since this area was missing in the original QR.
After noticing some minor errors in the flag (inconsistencies in the format such as "3" for "E", "0" for "O", "4" for "A") and understanding the context of the flag which is likely to be saying QR_Error_Recovery_Magic!, I could make an informed guess on the flag preliminarily as
govtech-csg{QR_3rr0r_R3c0v3ry_M4giC!~
But still the closing curly bracket is missing so I assumed that the final byte of "~" could probably be "}" hence trying to submit the flag below worked!
govtech-csg{QR_3rr0r_R3c0v3ry_M4giC!}
This method is quite tedious and manual but along the way, I have managed to learn a lot about the different parts of the QR codes and how to read them so this was definitely worth spending my whole evening on.
Hope this also helps to articulate my thought process behind this challenge and the way I managed to obtain the flag manually without the help of external tools.
References
- https://medium.com/@r00__/decoding-a-broken-qr-code-39fc3473a034
- https://www.youtube.com/watch?v=kHTWTyV7VJQ&ab_channel=CodeQuriouZ
- https://www.thonky.com/qr-code-tutorial/module-placement-matrix#:~:text=The%20timing%20patterns%20are%20two,QR%20code%20between%20the%20separators.
- https://developpaper.com/qr-code-details-2/
- https://aioo.be/2015/07/28/Decoding-a-partial-QR-code.html