DOUBLE-SIDED QR-CODE
UPDATE: Also, made it to SIGBOVIK 2019 (the conference of the Association for Computational Heresy Special Interest Group on Harry Quakerproof Bovik) with my paper “On Double-Sided QR-Codes” :)
TLDR: Using some dirty hacks and math tricks I was able to generate the “double-sided” QR codes. Such a code could carry two different messages in a straight and mirrored position.
Note: some QR-code readers could flip between two messages just with the slightest angle change. I believe they use affine transformations without restrictions on the mirroring. If your reader gives you the same message on the both sides, try to tilt it a bit.
BASIC ANATOMY OF QR CODES
Let’s recap basic things about the QR-code structure. We’ll consider the simplest type, Version 1-L. This means our code will have only 21x21 pixels and the lowest possible error correction level (7%, but not exactly).
FIXED PIXELS
A part of the code is always fixed and filled with so-called function patterns (with funny names like finder or separator), but let’s not get deep into this fixed structure, just take it as it is:
CONTROL CODE
The most important variable part of a QR-code is so-called control code. It contains only 5 bits of a control information which specify parameters of decoding process. It’s vital, so it’s highly protected: there is 3-fold redundancy for the Bose–Chaudhuri–Hocquenghem code correction and the whole thing repeats on the code twice:
PAYLOAD DATA AND ERROR CORRECTION
The rest of the space is divided between the payload data and error correction data. In our case we have 152 bits of actual data aligned like this:
The 56 bits of the error correction data occupies the rest:
CONTROL CODE CONTENT
Let’s get back to the control code part and briefly describe its content. As I wrote, it contains only 5 bits of the actual information. Two of them encode the error correction type (in our case it’s “01” for L-type which stands for “Low”).
Another three bits contain the number of one of 8 possible XOR-masks applied to the main payload data. Here they are:
10 more bits added for the BCH(15,5) error correction.
LET’S DO SOME MIRRORING!
Now it’s time to check and see where different parts of the code map after the mirroring.
MIRRORING STATIC AREA
The static area is almost symmetrical and maps into itself except the one pixel called Dark Module (I’m not joking):
MIRRORING CONTROL CODE
That’s where the fun starts!
The both copies of the control code map into themselfs reversed plus the second copy is slightly affected by the mysterious Dark Module (which always equals to 1).
So, ideally we need the palindromic control code with “1” right in the middle. Also we want the L-type error correction and we prefer the symmetrical XOR masks (beсause it will be much easier to deal with symmetrical XOR when we will do the mirroring of the payload data):
Is it possible to construct the desired control code value? Yes, if we use the BCH(15,5)’s ability to correct up to 3 bits. And we could do it on the both sides. This idea is a little bit tricky so let me reformulate it: we are looking for 15 bit binary string which has up to 3 bits difference with the desired code AND up to 3 bits difference with the reversed desired code.
Since there are only 2⁵ = 32 different valid codes we could use a bruteforce to check all vectors inside spheres with a 3-bit radius around each of the valid code. We’ll get only 2³*2⁵ = 2⁸ candidates (actually less, since they are repeating). And don’t forget the Dark Module influence…
Let’s check, do we have any matches?
There are plenty of them. We will use this one:
100101010100001 <=> 100001010101001
It gives us 1-L code with same symmetrical XOR mask on the both sides:
DATA MIRRORING
Finally, we need to check how heavy our payload (+correction) data are overlapped. It doesn’t seem to be too good, even just the payload area has a lot of conflicts after the mirroring:
However things are really better when the payload is short:
But, but… What could we store with only 30–40 bits of data?
PAYLOAD STRUCTURE
The payload data itself has some internal structure which depends on the used encoding mode. The QR-code standard gives us a choice from several different encoding modes:
- Numeric Mode — only numbers,
- Alphanumeric Mode — 2 symbols in 11 bits, no cases, short alphabet,
- Byte Mode — typical 8 bits per char,
- Kanji Mode — 16 bits per char, wide alphabet,
- ECI Mode and others — too complex for us.
We’ll use the Alphanumeric Mode, because it’s thrifty and has most of useful chars. How a typical payload data will look like?
- Code of encoding mode, 4 bits: 0010 for Alphanumeric Mode,
- Length of data in characters, for 1-L Code with Alphanumeric it’s 9 bits,
- Data itself, 2 symbols in 11 bits, 6 bits for last odd symbol,
- Terminator.
The terminator itself has a complex structure:
- Terminating sequence “0000” (4 bits),
- Additional zeros for 8-bit padding (0–7 bits),
- Filling pattern “11101100 00010001” till the end of data (whole 19 bytes).
Anyway, there are some good news from my field tests: nobody cares about the terminator and filler.
HOW SHORT IS OUR PAYLOAD?
Let’s just try and put 5 symbols on each side, i.e. “HELLO” on the first side:
- Encoding mode: 0010
- Len: 000000101
- Data: 01100001011 01111000110 011000
- No terminator.
The total length of our payload is 41 bits. Where does it go on the code area?
The whole intersection is only 4 bits and it gets its’ place inside the encoding mode code (“0010” vs “0100”), so the real difference is only 2 bits so long.
IS ERROR CORRECTION REALLY HELPFUL?
No.
It couldn’t be changed directly as it’s a complex function of the payload data. Meanwhile it has big overlaps over itself and over the data area:
So, now we have 2 error bits from the data intersection + 20 new possible overlapped bits. But… it does the error correction! Maybe it’s enough to correct itself? Well, it`s complicated…
COMPLICATED ERROR CORRECTION
We used 1-L QR code, so we do have the joy of error correction. How much bits could be corrected? It’s up to 24 bits as long as they are located in 3 or less different padded bytes. For each side.
So if we can put each of our error bits on one or another side and arrange all errors in two groups, up to 3 bytes on one side and up to 3 bytes on another, we could make it. For example, like this:
We used only 4 of 6 available error bytes, so there are some more space to use. But how to do it without direct control of the error correction data?
LET’S BRUTEFORCE
Let’s recap the regions of the interest:
- a + b + c + d + g + h = data¹
- a + d + e + b + g + f = data²
- f + i + e = control¹(data¹)
- h + i + c = control²(data²)
Here is the knot:
- f = some q(h)
- h = some r(f)
But we could for example change g to anything we want. So let’s bruteforce: change g until f will match to q(h) (and vice versa). It should take some time: 10 to 20 minutes on my Core i5–2500K @ 3.30GHz with pypy. Still not so bad.
IS IT THE LIMIT?
No. We could do much, much better. Let’s see how many errors we could cover with 3 bytes on the each side:
This simple approach gives us a 6 symbols message on the one side and a 10 symbols message on the other one. And there is still some redundancy!
But how to find the match? Bruteforce will take ages…
ANALYTICAL SOLUTION
Let’s recall the QR-code standard uses Reed–Solomon codes for the error correction. Thus the whole error correction area is a known multidimensional boolean function of data: we could write it down twice (for the two sides) plus equations which bind the value of the same bit on the different sides and solve the system of these equations analytically just in seconds:
SOME MORE NOTES
RULES BROKEN
Which rules of the QR-code standard we’ve broken?
- a lot of error correction used, but it’s okay,
- terminator is lost, but nobody cares (according to the tests, see below),
- recommended filling pattern was not used (same).
Nothing critical.
IS IT POSSIBLE TO SQUEEZE URL INTO 11 CHARS?
Yep. Even into 9 chars. You just have to find a 4-chars domain url shortener: t.co, q.gs, u.to, j.mp, x.co, u.bb, v.ht, v.gd, …
Then try to find 2- or 3-chars vacant custom code on it: the code should be in [A-Z0–9$%*+\-./:], since we used the alphanumeric endoding. Finally, remove the protocol prefix and voila:
Half of tested readers were able to recognize it as a link :)
QR-CODE READERS FIELD TEST
I made a fast field test of available QR-code readers if they are able to read the both sides of my codes. Here are some results.
Some android apps:
(+) QR Code Scanner, Unitag
(+) QRCode Reader, TWMobile
(+) QR Code Reader, scan.me
(+) QR Droid Code Scanner
(+) QR Droid Private
(-) QR & Barcode Scanner, GammaPlay.com — reads the same message twice
(-) Barcode Scanner, ZXing team — could read only one side
Some iOS apps:
(+) Scan QR Code and Barcode — QuickMark v1.2.2, quickmark.com.tw
(+) IPhone QuickMark v4.8.2
(+) Qrafter 11.6
(+) QR Code Reader v.16, scan.me
(+) NeoReader v4.9.3, NeoMedia
(-) Scanvi v1.6 — reads the same message twice
(-) Kaspersky QR Scanner v1.0.3.14 — reads the same message twice
(-) QR Reader for iPad from TapMedia Ltd — reads the same message twice
Others:
(+) nokia e90 built-in reader
(+) online reader https://zxing.org/w/decode.jspx
(+) online reader https://webqr.com/
(+) online reader http://www.onlinebarcodereader.com/
(+) online reader http://decodeit.ru/qr
(-) online reader http://www.patrick-wied.at/static/qrgen/
(-) online reader http://blog.qr4.nl/Online-QR-Code_Decoder.aspx
