QR error correction helps and hinders scanning (2021) | Hacker News Reader

QR error correction helps and hinders scanning (2021)

huonw.github.io

78 pointslucb1e45 comments

The part that makes higher error correction even more pointless is that errors can only be tolerated well in certain parts of the QR code. If the position markers are damaged, a scanner likely won't even recognize that there is a QR code visible, which obviates any error correction. The article mentions this in the very last sentence/caveat.

It feels a bit like the error correction exists mainly so you can embed fancy logos in your QR code... Avoiding damage to some parts but not others seems unaligned with real world scenarios...

Since the position markers are constant they should be the easiest to recover if damaged. Considering how advanced computer vision is, a QR code can be identified without using them.

Agreed - QR recognition/alignment algorithms can clearly be improved further, and then when they are, higher error correction codes ought to be more reliable as designed.

It's not a case of can they be. It's a case of can they cheaply be.

The camera app on your smartphone likely searches for them by default. That means feeding at least 1-2 frames a second through it.

Basic pattern matching for the position markers is a rounding error overhead vs processing a video feed. Fancy computer vision is not - on lower end devices you may not have enough resources to do both and on higher end devices it'll still impact power usage.

Low tech stupid solution: carry a sharpie.

real CV programmers edit their QR codes with a sharpie

Approximately 10 years ago, I played with an Android app that takes the camera video input, looks for a Sudoku puzzle and then solves it. (AR Sudoku solver)

Detecting a QR code in real time should be possible on all devices by now...

> It feels a bit like the error correction exists mainly so you can embed fancy logos in your QR code

Absolutely not the case. QR codes, like most 2D matrix codes were designed for logistics and supply chain, their leap into the consumer mobile phone arena was an interesting one, but not the original design intent at all (QR was developed at Denso, the automotive parts and logisitics arm of Toyota). The purpose for the error correction is so that the symbol can still be read on a label even if part of it is misprinted or obliterated, it works very well in practice. Industrial scanning software is mature technology, and more sophisticated than you imply (besides, segmenting and aligning barcodes, any barcode, in greyscale images is pretty simple). Position markers are easy to reconstruct and damage can be tolerated.

It's the same for wireless protocols too. Transmitting with less bits per symbol makes the whole packet longer and potentially more prone to interference. Transmitting at a higher symbol rate can often reduce the amount of packets lost which is counterintuitive.

The airline industry uses other kinds of 2D codes, like Aztec Codes[1] or Imagen PDF417 on your boarding passes, including the digital ones you have on your phone. For example: https://fwhibbit.es/wp-content/uploads/2017/07/3-1.png

1 https://en.wikipedia.org/wiki/Aztec_Code

The barcode on the back of North American driver's licenses is also a PDF417. Amusingly enough, it encodes all the text on the front of the license. Name, DOB, weight, height, etc. Retailers that scan your license for alcohol age limit checks get a lot of data they don't technically need.

Finally, a justification for lying about your weight on your license.

I remember that the WeWork location I went to used to scan (and likely siphon/store) all that data as part of the front desk check-in. And they really didn't need it either, but were very insistent on doing so before letting someone know I (a guest) was in the lobby

ProTip™: US Passports are ACCEPTABLE FORMS OF ID (in all US Jurisdictions), and are not able to be scanned for these types of purchases.

For what it’s worth MDL, the digital driver’s license, has this baked in unless the standard changed since I paid attention - your identity authority signs a record saying >18 and >21 (+ photo) and that’s what’s transmitted.

Qld government spent $18m making its own digital license app ignoring that Apple and Google both implement the iso specification for digital ID protection. I've had two interactions online with sw people convinced "they did it better" and I am buggered if I can tell how.

Typically what happens is that consultants implement the IT systems for these departments. Unfortunately it wouldn’t surprise me if the government got snowed into thinking they needed this app / there are kickbacks involved behind the purchasing decision.

Still, it is possible the app has a legit reason like the OS wallet implementation is missing support for their region or OS wallet support is incomplete in some way and this bridges that gap.

18m does seems a tad steep though considering that RDW payed UDL to build a sample reference app for free and one would expect that to be the basis for any 3p implementation delivered. Like that would be 36 very highly paid engineers which is a lot for 2 apps. It’s possible the 18m was also for the backend changes to enable the app which would maybe be more legit and be required changes for the builtin integration. Are you sure it was 18m just for the app?

No. I misremembered, it's $53m AUD

https://www.themandarin.com.au/233815-queensland-digital-lic...

That's probably total development and some operations costs

Yeah and likely not just the app but also the backend infra to support the signing and whatnot.

It’s a shame that there’s so many disparate motor vehicle agencies. They should standardize their IT solutions to amortize development costs as I fear the vendors they pay double dip with the pricing of solutions.

What they should do is create one and publish it under an open source license so the others can use it.

A very ethical but likely illegal life ProTip™®©: microwave a passport for 1 sec to burn out the RFID. The printed matter is sufficient to "read" a passport, while carrying around an unsecured, black box RFID readable at a distance is a privacy nightmare.

If I recall correctly, the RFID data is “encrypted” using the name and birthdate on the passport, making it fairly hard for someone to remotely scan and get usable usable data.

Name and birthday isn't enough entropy to resist even a naive brute force attack.

Why didn't they encrypt it with a random key and then put a QR code of the key on the inside of the passport? Or just use a magnetic stripe or similar instead of something that can be remotely accessed by an attacker?

It's not "encrypted by" but "authenticated by", see https://www.cs.ru.nl/~erikpoll/ufrj/C_ePassport.pdf slide 10 and 11.

You pretty much need the full MRZ or be lucky you get the right part (date of birth, document expiry and document number used) data at the bottom, it's unlikely you can brute force this in the fleeting time available with a run-by scan. If you have a digitised document number it is a lot easier but otherwise you need continuous access to the chip and when you have that you can also just read it.

See ICAO 9303 for details. (BAC specifically)

Nationality is NOT one of these encrypted data fields (i.e. you can determine if an American is walking nearby, but not their name/DOB/etc).

I've been to multiple countries where they read the RFID in the passport for automated border control, and if you don't have an RFID-capable passport they revert to manual inspection where you may be asked uncomfortable questions.

I'd rather use an RFID-safe pouch to store my passport and use the RFID-based automatic border control.

What sort of uncomfortable questions?

The kind of uncomfortable questions asked by racist border agents who assume anyone with a darker skin color will have obtained a visa fraudulently, or will overstay their legitimate visa.

"You an American, there, BOY!?!"

My fun, pre-RFID traveling days... always ended up with me in secondary screening. Millions of non-citizens, waived right-on-through... and then these two Texian gringoes... getting their beat-up, licensed & insured Z71 thermally scanned at every possible Rio Grande crossing.

Decades later, traveling insland (with gray hair and wiser comlexion) and I smoked a joint while a drug-sniffing dog walked by, unaware of his worthlessness (as intended).

It's all theater, welcome to Our Play.

Government-issued identification, which passports (US or otherwise) are, are always acceptable forms of identification. I'm not sure this is a protip.

You know what is a protip though? When applying for a US passport you can also choose to get a passport card. It's a plastic card that is the same dimensions as a driver's license and is valid for use in place of a passport when traveling between US-Canada-Mexico by land, and it's also an acceptable form of identification in general because it's a government-issued identification.

Yes and no. For example, a concealed handgun license (a state-issued government ID) is not acceptible for (e.g.) opening a PO Box.

I grew up in Central Texas (HOURS to get out-of-state), and many drinking establishments would ONLY accept a Texas ID/Passport for alcohol purchases — this isn't "legal" but "how it was."

I'll take your ProTip, though, and get myself an ID Passport Card (I presume this is not scannable).

Combined one of the section headings in the text, which basically gives away the conclusion, with the caveat that it's about undamaged QR codes. As you can expect more damage (such as when tattooing one, or paper that goes around), higher error correction does make sense; same when overlaying graphics/logos.

I found this surprising. I'll be displaying QR codes on a screen, so for me L easily makes the most sense in order to be able to make it larger with fewer squares inside of it.

Why are we even using black and white tags?

https://austingwalters.com/chromatags/

Because printing binary black and white is cheaper to print and cheaper to read.

That was the case in 2005, but now nearly every camera in public and industrial use supports color except save some in particular logistics uses that would need upgrading. The only reason it remains is legacy and convention. Yes, it requires different printers, but that's not an insurmountable supply chain change, especially if it's reduced to a few distinct colors that don't need to be mixed. This is a missed opportunity to encode more data into a given area and/or to make it more readable.

> nearly every camera in public and industrial use supports color

This is essentially false. Plenty of industrial cameras are black and white because of their speed and light collecting advantages. This matters for high speed identification. Going to color would not be an upgrade.

"missed opportunity"

Limited information density just isn't nearly as big an issue as you seem to believe.

Colors work great until they don't, for non emissive sources they depend on ambient lighting. A black and white code can be read with under virtually any color lighting (it doesn't even have to be in the visible spectrum). And if you've seen anyone futzing getting a read of an eticket off an emissive device such as a screen, that is just much worse once color is brought in.

Most auto ID applications have limited keys and identifiers encoded in the symbol. Just as color cameras are ubiquitous, the same goes for network connectivity, you don't need to store massive amounts of data in the symbol. If color symbols were really that much of a win they would have been adopted in industry. Attempts by groups that don't understand the subject have been made over the years, this is not new:

https://en.wikipedia.org/wiki/High_Capacity_Color_Barcode

"Yes, it requires different printers"

This is quite an understatement. There's no cheap upgrade path from monochrome thermal printing technology (or laser engraving), that's why they have never been replaced all these years.

Color imagers were readily available long before 2005. Color printing has not changed much at all in the past 20 years. If color symbols made sense they would have been adopted a long time ago. They are almost always the wrong approach, too many problems for too little payoff, that's why they are uncommon.

Cameras sensors can pick up denser patterns in black and white, especially under imperfect lighting, and the extra data density is not all that much.

Anybody who has tried to color correct for lighting conditions is shaking their head at this idea. Dealing with color is always a headache.

Humans can't even reliably tell whether a dress is black and blue, or it is white and gold. Color is complicated.

Chromatags probably have their uses, but when put in practice like qr codes are, they don't have most of the "features". Monochrome means you can use cheap/shitty printers, you can theme them to go well with your brand, etc.

Same reason we use binary computers? The greater noise margin on each bit typically offsets the requirement to have more/smaller/shorter bits compared to a multilevel signal.

Printing. Printing is done in the CMYK color space. Cyan, Magenta, Yellow, blacK. When you print in color, it is basically four different printers printing onto the same piece of paper. Ideally everything is all lined up correctly, but if you want to do it on an industrial scale, good alignment costs time and money. Big printed color color posters tend to have shitty alignment. A color tag needs to have good alignment; if the cyan, magenta, yellow print runs are misaligned, chances are a color tag won't be able to read it. But the black run is always aligned to the black run. So it will always work.

Lighting. The Sun, incandescent, and halogen lights have pretty good color reproduction. But LED lights and fluorescent lights do not. LED lights and fluorescent lights are designed to look acceptable to human eyes. And they can be reasonably good at it. But cameras are not human eyes; color gets all fucky when you look at it through a camera.

Cameras. The tag you linked to uses the LAB color space; one channel is brightness, one channel is blue vs yellow, one channel is red vs green. Cameras almost always have BGGR arrays; on a 4 megapixel camera, you will have 1 million blue pixels, 2 million green pixels, and 1 million red pixels. So if you use a normal camera to read a tag in the LAB space, you have 4 million pixels reading the brightness channel, 3 million pixels reading the red-green channel, and 1 million pixels reading the blue-yellow channel.

The weasel word in the title is undamaged. But the story is actually about QR codes being damaged. The original image isn't damaged, but its impression is damaged in transit while being scanned. QR codes crammed with more information (such as more error correction) have smaller pixels for the same view angle, and those are more easily damaged during the scan. An undamaged QR code with large pixels (low information) might scan perfectly without any error correction at all, but as the information density increases, so does the potential for error (error not caused by damage in the QR code being scanned).

If we make a QR code so dense that the scanner cannot make out any of the pixels, it becomes completely unreliable, even if 80% of it is error correction bits.

Basically, error correction defends against processes that cause random erasure or flipping of bits. Error correction is not meant to defend against fundamental channel bandwidth problems.

Said another way if I understand correctly, erasure codes help as long as message + erasure fits into channel bandwidth. If it doesn’t, then erasure codes hurt. Is that right?

Reply on news.ycombinator.com