xqr

XQR

official writeup; challenge created by me

Challenge

I love QR codes! But maybe it's true what they say about having too much of a good thing...

xqr.png

Solution

Intro to XOR

The name of the challenge, "XQR," hints at the fact the the solution will involve XORing the different QR codes. XOR (short for "exclusive or") is a logical operation that takes two inputs and returns true if and only if one input is true and the other is false. Below is a truth table for the XOR operation:

a	b	a ⊕ b
false	false	false
false	true	true
true	false	true
true	true	false

You can XOR more than just booleans, however. For example you can XOR two integers:

42 ⊕ 33 = 11

In the above example, the bits in the binary representation of the digits are what is actually being XORed:

101010 ⊕ 100001 = 001011

XORing Images

The QR codes in xqr.png are made up of black and white pixels. If we treat each black pixel as a 0 or false and each white pixel as a 1 or true, they can be XORed just as we saw above with booleans and bits. Here is another truth table, this time using pixels:

a	b	a ⊕ b
⬛️	⬛️	⬛️
⬛️	⬜️	⬜️
⬜️	⬛️	⬜️
⬜️	⬜️	⬛️

Let's consider a smaller challenge, xqr3x3.png:

To find the flag, we begin with any single QR code xqr.png. Then, one by one, we XOR it with all of the other codes in xqr.png. This process is demonstrated below:

Scanning the final result reveals the flag!

Automating the Solution

Solving a 3x3 challenge isn't too difficult, even by hand (see b&w_xor_using_gimp.xcf for an example of how this can be done), but if we're ever going to solve something as large as xqr.png, we'll need to automate the process.

There are many different ways of doing this, but I used the Pillow (aka PIL) library in Python. PIL makes it easy to process images pixel by pixel, and even includes a function for XORing images. The following code can be used to reconstruct the flag QR code from xqr.png:

from PIL import Image, ImageChops

# the height/width of an individual QR code (including 1 px border)
CODE_SIZE = 27

# each extracted QR code will be temporarily stored here
tmp_qr = Image.new(mode='1', size=(CODE_SIZE, CODE_SIZE), color=1)

with Image.open('xqr.png') as image:
	IMAGE_SIZE = image.size[0]
	# iterate through each QR code
	for start_y in range(0, IMAGE_SIZE, CODE_SIZE):
		for start_x in range(0, IMAGE_SIZE, CODE_SIZE):
			# copy the pixels of the current QR code into tmp_qr
			for y in range(0, CODE_SIZE):
				for x in range(0, CODE_SIZE):
					p = image.getpixel((start_x + x, start_y + y))
					tmp_qr.putpixel((x, y), p)
			# if tmp_qr is the first code, copy its contents to qr_flag
			if start_x == start_y == 0:
				qr_flag = tmp_qr.copy()
			# otherwise, set qr_flag to qr_flag XOR tmp_qr
			else:
				qr_flag = ImageChops.logical_xor(qr_flag, tmp_qr)

qr_flag.save('flag.png')

TL;DR

XOR all of the QR codes together, and the resulting QR code will reveal the flag when scanned!

How It Works

The following is an explanation of how this challenge was created. It will explain the process of creating xqr3x3.png, but the process for creating larger challenges such as xqr.png works exactly the same way.

Using XOR to Hide Information

Let's say we want to hide a secret value, 1337, in a set of numbers. We start by taking an arbitrary set of numbers, and XORing them together:

500 ⊕ 123 ⊕ 999 ⊕ 42 = 578

Next, we XOR our secret value with the result from above:

1337 ⊕ 578 = 1915

Now, XOR the result from the above equation with our first equation, we will discover our secret value!

1915 ⊕ 500 ⊕ 123 ⊕ 999 ⊕ 42 = 1915 ⊕ 578 = 1337

Hiding a QR Code

Now let's do it with QR codes. We'll start with the code that we want to hide, flag.png:

Next, we'll generate a set of 8 codes from random text, resulting in the following codes:

If we XOR all of the random codes together (not including the flag), we obtain the following:

Lastly, we'll XOR the image above with the flag:

You may notice that if you attempt to scan the resulting QR code, it is invalid. That is because it is not a QR code at all! It is an image specially designed to give us our flag QR code back when XORed with the 8 random codes that we started with. It is for this reason, along with the fact that it will be placed in the center of xqr.png, that this image is referred to as the "keystone" in create.py. Going back to our numeric example, the keystone would be analogous to the value of 1915.

Now that we have all the elements of xqr.png, we can put them all together. Notice that the code in the center matches the keystone as calculated above. Surrounding it are the 8 random codes that were generated.

All of these steps are automated in create.py to create massive challenges, such as xqr.png (shown below).