Decoding small QR codes by hand (2012) | Hacker News Reader

Decoding small QR codes by hand (2012)

blog.qartis.com

311 pointsterryds69 comments

> 99% of the QR codes you encounter don't have any missing bits

I see a lot of cutesy QR codes out there that include a logo in the center.

These are basically intentionally damaged and depend on error correction to recover the missing bits that are covered by the logo.

Not if they're one of these QR codes[0], which was discussed here a few days ago[1]

> Instead of scribbling on redundant pieces and relying on error correction to preserve the meaning, we can engineer the encoded values to create the picture in a code with no inherent errors

But as another commenter noted, this likely increases the scan time required.

[0] https://research.swtch.com/qart

[1] https://news.ycombinator.com/item?id=36128082

This QArt technique can be extended with error diffusion dithering...

Then the uncontrollable pixels can be hidden in areas of the image which would normally be grey, with the uncontrollable bits error contribution passed onwards to the controllable regions of the image.

These are cool and definitely a much more interesting hack than just sticking a company logo in the middle of the code in Photoshop. But I've never seen one of these in the wild.

My pet peeve:

WTF PEOPLE ARE NOT PUTTING A CLEAR TEXT URL NEXT TO THE QR CRAP?!?!?

Especially when the QR code itself points to a URL shortener.

I think the forced tracking is half the point.

An example of this and candidate for worst use of a QR code is found on Wifi APs provided by AT&T. A sticker on the device shows a convenient QR code that will get you connected. If you're thinking it uses industry standard Wifi schema well you don't know AT&T very well. Instead it sends you to att.com. That's right, in order to connect to the wifi so you can get online you must first be online so you can get the password from a website.

Fortunately they still print the SSID and password on the back. But it's clear that AT&T would rather you go through their telemetry portal instead.

(And then there's how the signal on it was so weak that it couldn't penetrate interior walls more than 10 meters away. But that's another story.)

What forced tracking? If you're going to visit the URL, there is no extra tracking that can be provided by the QR or the shortener. Same if you aren't going to visit it

The QR code means that you can include a tracking id into the URL

There’s no reason for it to be the same URL. It could be used to give a false sense of trust. Perhaps that’s why?

If somebody can alter a restaurant's menu to point to a malicious site, they can just as well alter the QR code. Same goes for the payment information on a parking lot.

The QR scan/generate app I use always presents me the scanned data in text form and asks me to verify if I want to visit the URL or not. I don't know why anyone would chois an app that doesn't afford the user that basic level of control.

I use the Privacy Friendly QR Scanner, developed by a German university research group. More info available here: https://secuso.aifb.kit.edu/english/105.php

Indeed. I think these days that's also in the built-in scanners; certainly the QR code in this blog post no longer executes the embedded JavaScript when I scan it on my iPhone, though I'm sure it did back in 2017 when I wrote it:

https://kitsunesoftware.wordpress.com/2017/04/10/executable-...

I use the same one, installed via F-Droid (on Android 12). For me it can't adjust the focus of the camera, one has to open a camera app, adjust the focus, close camera, open QR app .. if you know of a fix then I'd be very happy.

I don't think so. When you are drawing a poster, you don't necessarily think in terms of security. Most people drawing a poster are graphics designer, not security researcher. You think in terms of readability, convenience and esthetics. I don't think most people check the URL under a QR Code before flashing anyway.

Since most people don't type URLs themselves and can scan a QR code, it might not even occur to you that having the URL in plain text can be useful. It also takes space and it's not necessarily pretty.

(I do put the URL when making a visual with a QR Code, and require the URL to be there if I'm involved but not making the visual)

My other pet peeve: Why don't QR scanner apps also just scan plain text URLs with simple OCR?

OCR works well on regular text because it can use language stats for error correction. On URLs?

Ping the URL in the background, if it returns a 404, iteratively change the least-confident character recognitions to the next best guess until it returns a 200 and then return that to the user. For example if it doesn't know whether a character is "I" or "l", and another character is a "0" or an "O", try all 4 combinations and show the correct one before the user even realizes.

If a piece of an URL looks like a word, factor that into your confidence scores as well, e.g. "somefoo.com/illusion/" is far more likely to be the correct URL, especially for something printed on paper, than "somefoo.com/iIIusion/", "somefoo.com/iIlusion/", or "somefoo.com/ilIusion/"

You don't even to do a full GET request, you can just use HEAD to save on mobile bandwidth.

For URLs that are printed on paper (e.g. at a restaurant table), have the backend do this and cache the correct URLs based on geolocation.

That's a pretty fragile and fault-prone method, and is extremely prone to typo squatting. I'm glad something like this isn't popular today, because it would very quickly be capitalized on by scammers, who wouldn't even have to rely on humans making typos anymore.

If it doesn't have error checking and checksums, it shouldn't be relied upon by the general public.

Why would typo squatting be part of the threat model?

Let's say you're at a restaurant, they have one of those stupid QR codes to view the menu (I really wish they would print the damn menus, but that's another story ...). Why not just an URL of "myrestaurant.com/menu" and you just scan that URL? Who would typo-squat an alternate menu and paste it on the restaurant tables?

If there's a venue in which typo-squatting is a potential threat, QR-squatting would be an even bigger threat because even if only 5% of people have sharp enough eyes to spot a typo squat, probably only 0.0001% of people are good at decoding QR codes in their brain and would spot a QR squat. The typo squat is easier to spot.

If you really wanted, we could also establish an optional checksum protocol for URLs e.g. http://myrestaurant.com/menu#cs=123

If the checksum fails, the phone can try (a) all possible 1-2 character edits for error correction, which should take only a couple milliseconds (b) auto-Google the URL to see if there is a fixed version of the URL (c) error out if both of the above fail.

They’re saying that an attacker would register variations of similar looking domains relying on the OCR misreading the correct URL. They aren’t suggesting that an attacker would paste the invalid URL in real life menus.

The whole point of QR codes is to paste URLs in real life. For non-real-life use cases even QR codes are unnecessary and people would just use links. For that, yes, typo-squatting and phishing are issues.

I'm suggesting that for real life we could just use URLs and OCR instead of QR codes.

> I'm suggesting that for real life we could just use URLs and OCR

No, because that's not reliable, and way more complicated and error-prone.

It's the same reason bar codes are used instead of directly the id they code.

Your earlier solution doesn't convince me. It's interesting, but not practical, and reading the URL should work even if internet is off or the server is down.

(Having a checksum next to the URL may start making OCR practical though)

This is really neat! I’ve wanted to know the QR code contents a few times without actually scanning with my phone so I actually built a super simple app to do this. Nothing fancy, just dumping the raw contents of the code to a string.

https://apps.apple.com/us/app/barcode-qr-scanner-rawcode/id1...

Happy to add any features folks might be interested in!

Super interested. As with most things Apple, the lack of control is infuriating, and I hate how the QR scanner auto visits the scanned link rather than just decoding the data.

I thought I’d take a quick look to see what your app offers.

Here’s some feedback:

* On launch, it asks for Camera permission. I declined and the app crashed. Next launch, it opens to the blank screen with a (scan) icon and an Edit option, both on the top right. Tap on the scan icon and the app crashes. Tap on Edit and it changes to Done (there are no previous scans, obviously). It should ideally provide instructions to enable Camera permissions in the Settings app and also say why it needs it and how it’ll be used.

* The App Privacy section for your app declares that it collects usage data and diagnostic data. It would be good to know more details of what’s collected (preferably in the app description). Generally, people wouldn’t expect such a (simple use case) app to collect and transmit information (unless they explicitly ask for it to be done).

Just FYI, you can also do this with the inbuilt Shortcuts app - create a shortcut to scan a QR code then copy its contents to the clipboard for example.

Use a better QR scanner app. I use Privacy Friendly Apps' "Privacy Friendly QR Scanner", which always presents you with the scanned URL or text in the app before doing anything, and asks you to verify that you want to visit the site. It also includes the ability to generate your own QR codes.

See https://secuso.aifb.kit.edu/english/105.php for that and other apps developed by that research group.

It's not very good, I just tried it on an image and it didn't work. The built-in iPhone QR code reader inside the camera app could pick it up without any issues.

One thing that cleared up some confusion for me: The tattoo photo shows a version 2 QR code (as he writes) but the schematic images are for a version 1 code[1].

That's also why the bottom right alignment pattern is missing in the schematics. He didn't forget it, it's just not there in a v1 code.

[1] https://www.qrcode.com/en/about/version.html

I also saw this. So one would then simply leave this part out on the way down? Is the alignment pattern always on the same location? I guess so.

I think the pattern has a fixed location that is defined by the version. And yeah, that was my understanding as well, you just skip the corresponding bits when doing the "zigzag reading". But I'd also like to see an example, in particular as that would be different from how the other "large" alignment patterns are handled.

> I think the pattern has a fixed location that is defined by the version.

Correct, the alignment patterns only depend on the version, not the error correction level or text encoding.

Source: I read the spec and wrote my own QR encoder library.

Scilabus made a nice video about it for French speaking people [1].

On a linux computer, I take a screenshot and run zbar, a cli tool available in the repositories.

[1] https://m.youtube.com/watch?v=wKB-ZI2gXsk

How do camera apps recognize where the QR code is in the image, and what part of the image it should decode? I guess it also often has to some processing on it, as it will be scewed/bent/etc.

Looking at this guide, it's easy to understand the steps. But I don't get how one actually would apply them in code to a picture of a QR code. How?

QR codes have certain zones that scanners look for.

To determine orientation scanners look for “alignment markers”.

Do you have an article that goes into the details of implementing a reader, and does not just tell you 'use pyzbar'?

That would probably be a machine vision problem, but I'm also curious to know how you turn the pixels of a photo into a series of bits.

Typically by looking at „runs“ of black and white pixels (after image has been binarized/thesholded). For a QR code marker, you would look for a 1-1-3-1-1 pattern, which would indicate that this image row crosses a QR code finder pattern.

But do they do this at different angles? If so, which? How do they deal with (possibly partially) obscured alignment markers? How do they determine the angle and size of squares? How does one sample each square (center point, average of square, min, max...)? Should I convert my image to grayscale first? If so... which of the RGB-to-grayscale methods should I use for best results? Should I pre-process the picture to enhance sharpness and reduce focus artifacts? Should I bruteforce each frame of the video stream in look for the alignment markers? Etc. etc.

I think I have the general idea on how all that works, but... isn't there an official spec/algorithm on how one is supposed to do this? The devil is in the details.

I've also been looking for a course that goes over this step by step, and step 1 is not pip install opencv/pyzbar/pytorch...

Yes exactly. Do I need to look for 1-1-3-1-1 markers in _all_ 359 directions? What about warping/distortion of the surface etc? All the details is what I'm interested in seeing.

If you have a rough idea how it works, include these in your google queries to get results that go into details ;)

Some more things to include:

- perspective correction may be needed (the surface with the QR code is not parallel to the image plane, so pixels further away get smaller)

- if the algorithm takes parameters, such as color filters / black-vs-white thresholds, try with different parameter sets in sequence. The user is pointing the camera at the code for a relatively long time, compared to the time it takes to process an image.

- pixely images should produce a recognizable pattern in the fourier transform of the image. This gives you the size AND rotation at once.

(edit: formatting)

The 1-1-3-1-1 (with tolerance) works at angles as well, as long as the code is not perspectively warped. You are right in assuming that there‘s a lot more to it than that. Localization and decoding (usually these are considered separately) 2D codes is an active research field, and there are a lot different approaches.

Disclaimer: I an the author of STRICH (https://strich.io) and have dived relatively deep into the topic.

Also, you can always look at how libraries such as ZXing do it. Especially for QR codes, there is a lot of code available on the internet.

To take a “draw the rest of the fucking owl” approach to explaining this. Picking up QR codes is just like picking up normal barcodes, or decoding any sort of structured signal from a noisy environment (the kinda thing that at the heart of all RF comms).

Basically the entire of subject area of electronics and signal processing exists to find clever ways to solving all the problems you mention. So for people that do for a living, there’s a huge set of standard algorithms and approaches you can apply to solve the problem of “detecting QR codes”, in the same way there’s standard approaches to sorting a list, or building a B-tree, or creating a query planner.

It’s realistically not possible to summarise the process into a HN comment, because that would require explaining decades of signal processing research in a handful of sentences.

To give a flavour for solving this problem, QR code alignment markers are designed to be easy to detect, regardless of angle or being partially obscured. Their large simple pattern means you can use crude algorithms to find all alternating back and white patterns in your image, then analyse those patterns to detect which ones are noise and which ones might be alignment markers. Stuff like the regular spacing of the alignment patterns, plus the timing strips between them, give you anchors to rapidly check if your looking at a set of actual alignment markers, or just things that happen to have the same shape as alignment markers. At which point you can start the expensive process of attempting to decode the QR data.

As for what algos to use to go from colour to greyscale, well that’s up to you to figure out. Building a crude QR code decoder is “easy” building a fast robust one is hard, and quite valuable. Nobody is gonna give you that kinda secret sauce for free, not when they can charge you for the hundreds of hours of R&D involved.

There’s an official spec for QR codes, it might even give you basic guidance on how build a very basic QR code decoder. But asking for a detailed spec on a fast robust QR decoder is like asking the IEEE for a detailed spec on how to build a 10Gbs Ethernet controller. It ain’t gonna happen, because building such a thing is hard, even once you know what signals you’re decoding.

I get what you mean, but the same situation applies when describing the algorithm to decode QR codes (it involves "deep" stuff like Reed-Solomon) and yet info on that is far more prevalent.

Why is that the case?

Nobody expects a detailed tutorial, but it's hard to even come by a list of techniques that are known to work (or maybe I'm just trash at search).

What you can do is read a paper that’s relevant to your problem (let‘s say QR code perspective correction), and then dig through the references. Good papers usually have plenty of good references.

You can find plenty of information out there on various standard image and signal processing algorithms. Basic stuff like 2D convolutions form the backbone of many image processing techniques, and they’re well documented.

But just like Reed-Solomon encoding is a very specific algorithm, with many different applications, of which QR codes is one. What you’re looking for is similar, it’s a huge set of very specific algorithms with huge set of applications, of which one is QR codes.

QR codes are simply too niche for anyone to have put together a pubic document on what exact image processing techniques you might use to decode them. If you want to teach people about 2D signal processing, then QR codes are probably not a good starting point.

I would also argue that Reed-Solomon encoding is not “deep” anything. It’s one of many different 1D signal error correction algorithms that exist. For people who work on signal processing as day job, Reed-Solomon is about as “deep” as quick-sort is to programmers.

As for why quick-sort is well documented with many open implementations, and QR codes aren’t. I would argue it’s simple due to the industry they developed in. QR codes started in manufacturing, being used for inventory management, almost certainly by embedded and electronic engineers. All of those industries pre-date the open source movement by decades, trade secrets are still important for them, so they’re not naturally inclined to share IP.

There are various computer vision algorithms for detecting lines in images, like Hough transform[1]. You can combine it with an edge detection algorithm[2] for increased reliability. You would then look for quadrilaterals that have some space around them (as required by the QR code spec), transform them into squares, binarize the pixels (there are different approaches to that too, but a simple threshold would work in simplest cases), and only then would you start looking for the corner markers and trying to actually decode the QR code. At least that's how I'd do it if I were to build a QR code reader from scratch.

I built a similar thing for Telegram a while ago[3] for recognizing the text in the machine-readable zone of passports and ID cards. It does different things after the initial detection/transform/binarization steps, but those would be the same for a QR code reader.

[1] https://en.wikipedia.org/wiki/Hough_transform

[2] https://en.wikipedia.org/wiki/Edge_detection

[3] https://github.com/DrKLO/Telegram/blob/master/TMessagesProj/...

Regardless of what specification you're implementing, I always recommend "mentally executing" the algorithms for at least small test cases, as when you inevitably need to debug your implementation, you will be forced to do so anyway, and it increases your familiarity with what it should be doing. As the saying goes: "how can you tell the machine what to do, if you don't know how to do it yourself?"

For those who want to go the extra step and try the error correction by hand too, this article will be useful: https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_f...

(Side note: the example image of a QR tattoo evoked slight feelings of trypophobic disgust.)

This is how I was taught encryption algos - by hand on paper (simplified like fewer rounds in des) and they've stuck with me in a lot more detail for over a decade.

Somewhat related: How to recover a broken QR by hand. https://www.robertxiao.ca/hacking/ctf-writeup/mma2015-qrcode...

The real challenge is writing a QR reader that can follow the same principles to read even more corrupted codes.

Can’t wait for someone to do this on a post-apocalyptic TV show

I often wonder if the was an apocalypse and society rebuilt having forgotten the past what archeologists would make of thing ls like QR codes, and would they be able to work them out?

I also wonder if they'd grossly underestimate the complexity of the whole thing, like we tended to do with ecosystems and biological organisms.

Something like "no way this one random half-row of pixels on the left and the four pixels in the bottom right have a completely different meaning than the rest of the pixels!"

Also, I figure, it would be very difficult to reconstruct the mask patterns if you don't already know the formulas in advance. Someone might be able to figure out the codes that use the simple masks, but I figure, there'd still be many "unreadable" QR codes left that use the more complex masks.

Related, this page has a step by step process of how the encoding process works:

https://www.nayuki.io/page/creating-a-qr-code-step-by-step

Previously discussed here:

2020: https://news.ycombinator.com/item?id=24119124

2018: https://news.ycombinator.com/item?id=18360847

Wow, thanks for the first link, that was exactly what I was looking for after reading TFA. But I wish I could scan a qrcode and let this website explain it to me, instead of generating one with the same content, as I couldn't replicate the one in front of me with this page.

> I wish I could scan a qrcode and let this website explain it to me

Here you go: https://qrlogo.kaarposoft.dk/qrdecode.html

Doesn't seem to work for me, I used one of their example logo qr codes on their website and all give the error "Cannot decode a function pattern"

While I understand the teaching approach, this sound like the type of task which, even if it came up as a completely random one-off need, I would feel is much easier to solve in code. The inevitable bugs in my script are at least repeatable and I can iterate until I have a solution, whereas a single bit error in the manual process will waste the entire effort with no progress.

And experience has shown that, more often than not, such hack scripts find ways to grow into mission critical services. Sure, it's an ancient Mayan qr code that is unique in the world and we just so happen to have found precise decoding instructions; but are you sure the one of the stone bits isn't just a piece of fossilized bird poo that was not present in the original? Are you sure all the stone pieces were found? are you sure no other ancient qr codes will be found in the future?

Life is too short not to automate everthing.

To me, decoding a QR code by hand is a cool feat, like solving a Rubik’s cube. It is very unlikely that you will ever need to do it.

And like you said, it’s an excellent way to teach implementors of automated QR code readers/writers.

Is there any reason why so many different masks are required and why the mask patterns are so elaborate? In particular the last few masks seem mostly designed to make life hard for (human) decoders :)

The idea that the ability to decode could be lost makes me me wonder what info you would need as a kind of Rosett Rosetta stone for a future or alien civilization. I'm thinking what would you have on a wall of stone?

Would it be possible to represent the whole decode process with all options, and do it purely pictorially?

The seti project sent such a message.

See https://en.m.wikipedia.org/wiki/Cosmic_Call which points to https://www.plover.com/misc/Dumas-Dutil/messages.pdf . Read annex B of that message.

We spent a night decoding it with minimal hints, which was reasonably easy. Basically, page 1 defines numbers as dots, binary and their own symbol set. Then they define math operations. This allows them to describe some physical and chemical relations, from which the metric system is derived. This allows them to create descriptions of physical thing which, combined with some crude graphics, let them tell about our home planet.

If that's possible, explaining qr codes should also be possible

Someone made a decoding video tutorial a decade ago: https://www.youtube.com/watch?v=KA8hDldvfv0

Holly shit. How bored was this guy. Kudos for the dedication. Reminds of that silicon valley scene. How many guys they can j off. Funny shit.

Some weird comments there, eg:

> I am stuck decoding a qr code.... I have tried several ways. It was sent a long time ago so maybe it has expired. Any takers?

I don't think they read the post...

Reply on news.ycombinator.com