Hackvent 2019: Day 9

09 Dec 2019
CTF: Hackvent 2019
Link to challenge:
Date Completed: 9 December 2019


HV19.09 Santas Quick Response 3.0


Visiting the following railway station has left lasting memories.

Santas brand new gifts distribution system is heavily inspired by it. Here is your personal gift, can you extract the destination path of it?


We know that the QR code system is inspired by the first image so we do a reverse image lookup to try and find out more information about it. We find many articles such as this one discussing a pattern called Rule 30.

After some light research, we discover that rule 30 can be used to generate a pattern downwards starting from a single black pixel (or 1). The algorithm is:

This video does a better job explaining it than I ever could:

Next, we notice that our invalid QR code has two QR alignment patterns in the correct positions (top left and top right corners) but is missing one in the bottom left corner. That, combined with the fact that the Rule 30 algorithm generates a tree like pattern is a very strong indication that we should overlap the rule 30 pattern over the QR code and use it as  mask from the middle of the first row (so that the current QR alignment patterns are left intact).

This was our approach. For illustration purposes, this is the area that would be left intact:

We attempt common boolean operators such as and, or and xor and check to see if the bottom left QR alignment pattern suddenly appears. Unfortunately, it initial does not appear. After some head scratching we later find out that xor is the right boolean operation and we have to shift the rule30 pattern by 1 to the right.

This is what the final Rule 30 mask looked like:

Note that the mask is not perfect as it eventually overlaps with itself but is was large enough to fully cover our 33×33 QR code.

Finally, here is our python script:

Running our Python script gave us the following QR code which scans to give us our flag!

Flag:  HV19{Cha0tic_yet-0rdered}

No Comments

Posted in Hackvent 2019


Leave a Reply