How a QR code works
typefully.com
typefully.com
Creative stuff, built on a robust standard.
https://twitter.com/zackfreedman/status/1517555638456389632?...
I remember trying to use a QR code in 2015 at a crypto meetup so I could buy a beer with Bitcoin (they organized with the bar that they'd get cash at the end if they played ball). After downloading a QR reader app, taking a picture with my phone, uploading the picture to the app, then realizing there was too much glare and trying again, they eventually just gave me a beer and put a tally mark on a notepad.
Just a few weeks ago I used a QR code to join a WiFi network and it took like 2 seconds (it found the network and entered the password for me). We've come a long way.
oof
I also became aware of the possibility of people putting their own QR code sticker over another. Quite easy to send people to a phishing site... enter your credit card to "buy" that beer...
> Citi Bike says it is aware of a scam in New York City in which thieves are switching the QR code stickers on rental bicycles in order to steal bikes unwittingly unlocked by customers. The scammers wait for a renter to unlock a bicycle using the QR code, then ride away on the bike to which the code actually belongs, officials said.
https://apnews.com/article/lifestyle-nyc-state-wire-34d4ecd5...
QR codes generally are just a bit of data, like a link to a website. If I cover up an existing QR code with my own link to my own website... what would a signature do to help here?
Even if the original QR code had the link printed on it, do you think someone reaching for their 3rd beer would even notice it?
Humans are not conditioned (yet) to validate QR codes. We scan them without thinking twice. Phishing is pretty sophisticated and it is easy to duplicate a website.
A literal JWT (JSON Web Token) could be used, but a binary format could save TONS of space (30-50% smaller) which matters for a QR code.
QR would contain: binary data, datetime it was issued, QR creator ID, URL of signing authority (or a code from an approved list of authorities representing a know URL), a code for the algorithm used, and a signature that signs everything else.
When a user scans the QR, the software recognizes that it uses authorization mode.
It looks up the signing authority based on the ISO code for that authority and sends an API request for the public key sending the datetime and creator ID.
The signing authority returns the public key based on company and time (or a message if the private key has been revoked. If the key checks out, the user visits the URL.
All of this would take a fraction of a second and be entirely transparent to the user (barring revoked permissions or the signature being incorrect).
What prevents me from just signing my own QR code though? I could register a very similar domain, sign it, make it look all official and then siphon funds.
A third party could revoke my signature, but then we are dependent on that third party for everything, which isn't ideal either.
An argument in trusting trust is meaningless. The whole point is that they can be trusted. If you don't believe you can trust them, then nothing is going to change that.
The goal isn't to make such scams impossible, but instead to make them too risky and expensive.
If you're going to do a scam like that on a business level, there's a lot of logistics involved. A mom and pop shop isn't going to be a suitable target, so you're going to be targeting a franchise where you can easily move operations to reduce costs. You have to spend a bunch of time building out a fake website. You have to put multiple boots on the ground to go around changing hundreds of QR codes to improve hit rates.
QR certification means you have to create a new business to apply that makes a paper trail. Creating something very close to an actual franchise is also going to run the risk of setting off alarm bells and getting busted by the FBI. It doesn't make this scam impossible, but adds a big enough hurdle to reduce profitability and increase risk to the point where there are easier scams to pull off.
The other kind of attack is one-off scammers hoping to trap people. In this "QRL" certification scheme (sorry for the bad pun), their scam would never get off the ground because it wasn't certified.
> If you're going to do a scam like that on a business level, there's a lot of logistics involved. A mom and pop shop isn't going to be a suitable target, so you're going to be targeting a franchise where you can easily move operations to reduce costs. You have to spend a bunch of time building out a fake website. You have to put multiple boots on the ground to go around changing hundreds of QR codes to improve hit rates.
They emailed my finance department, said the account number had changed, even used the same bank, and got us to send a payment for an invoice to that new account. Bank happily paid them out. Nuts. Now we have to try to claw the money back, but I don't think we can get it without long legal proceedings against the bank. Imagine though, having the balls to open a bank account after having broken into a company.
The people in the finance department felt awful and surprised that this could even happen to them. Since then, they've now increased the security 1000x and require voice verification and what not...
My point is, just like you say, you can't trust the trust. The only way this would have worked is if QR codes could only be generated by a trusted third party for all QR codes. Even still, it wouldn't work because I could fake the trusted third party.
You have a nice dream, and it gets me thinking that a "LetsEncrypt for QR codes" might be an interesting business service, but it would require a huge amount of convincing people to use you as well as marketing dollars to get the word out. I still don't think it'll stop everything.
It is interesting how much cheaper the QR based payment schemes are in China. Payment processors in the west charge 2-3% typically for tap/dip/swipe. In China, the QR transaction fee is a fraction of that. Also, a bunch of the infrastructure for printing, displaying, and reading the QR codes is pretty cheap.
The OP is talking about adoption.
My symbian phone could read them in 2010.
The running joke for a decade (here in the US anyway) was that nobody had ever actually used one.
iPhones could scan them with the default camera app, but on Android it really depended on the manufacturer.
So you couldn't just say: "point your camera app at the code and open the url that appears.", which made using QR codes pretty much useless unless you had an app where you could build in an scanner for these codes.
Things that become a utility / must-have for daily life (say QR to order food) should have better discoverability and accessibility
I'm not sure if I would call this a "silver lining". In parts of Europe (I noticed it especially in Germany and Austria) they were normalized to a point were a lot of non-techsavvy people now think "QR codes" are kind of synonym to successful "digitalisation".
It's now even more painful to watch misguided attempts to digitalize shitty (business/administrative...) processes. QR codes just feel like the poor man's blockchain.
I am not able to get over this seeming like security theater, not to mention being somewhat indignant to the presumptive ownership of a smart phone to go through this song and dance when a piece of paper would suffice as a record.
I've captured the qr code and found that it's not geo-fenced or time-locked so I can check the child in and out in the comfort of my home, but haven't probed the application further.
An old investor once told me: "Make it really easy for your customers to pay you, and you won't regret it." QR codes make it really easy to do a wire transfer and they prevent random errors from being introduced.
[1] https://www.google.com/search?tbm=isch&q=circular%20qr%20cod...
Some of them however are implemented to be read by a specific non-standard reader, something such as the snap chat codes.
[0]: https://stackoverflow.com/questions/66837985/damaging-qr-cod...
This python package makes it super easy: https://pypi.org/project/qrcode/
All pretty cheap, so it's probably do-able depending on your definition of underpowered. This is assuming they take an orthogonal shot and there's no need for homographic projection (which would make it a lot more difficult to find the tracking markers).
Either way, incredible design, it's mind-blowing to learn more about the elegance and level of sophistication.
Essentially yes. If you are aware of how one-dimensional barcodes are read, it's the same. You would need to check multiple scanlines, but you don't need the full image analysis. It might be the case that modern QR decoders actually look at the full image, but this is hardly necessary.
a) There's enough of a QR there
b) The orientation is {coords}
c) The contents are {contents}
Finder patterns in the QR code can be recognized in the same way as long as your scanline actually hits those patterns. Since it's two dimensional you would need multiple scanlines to recognize all of them, but once you've got three finder patterns and they are not coplanar then there is a good chance that the alignment pattern in the fourth position; again, this can be recognized with a 1:1:1:1:1 pattern and you can make a good guess about its size. This gives the orientation [1], and timing patterns between two pairs of finder patterns finally give a transformation you need to apply to convert pixels into a matrix of modules. You read the version and format info (which has its own error correction codes), unapply a mask, read the actual data and ECC, correct any recoverable error and you are done. The very purpose of masking is to prevent those patterns accidentally occurring in the data section, and the standard defines a set of scoring criteria for masks; if 1:1:3:1:1 pattern occurs in the data after masking the mask is scored so low that it won't be chosen.
As you can imagine, while the concept is fairly simple the actual implementation might be complex. I should note that a large enough QR code can have multiple alignment patterns, because as your QR code gets larger it has a larger chance to be warped, and they help detecting where the warp has occurred. Also most barcodes including QR code have a concept of quiet zone that clearly separates a barcode from surrounding environment, mostly because otherwise you might be unable to recognize the beginning and end of the barcode (or in 2D barcodes, its bounding rectangle).
[1] Exercise: Now thinking about that, how can a UPC reader see whether the barcode is upside down or not?
* how to convert to grayscale
* how to rotate
The rest of this makes abstract sense, but not any sense wrt "i can write code to do it". As another poster said - its "draw the rest of the owl". It would be nice if someone knows about a nice annotated bit of code that starts from picture and ends at "return data;".
In computer vision there is no magic bullet, you will have to sink deep into the details.
In order to do that efficiently, a nice annotated codebase would help a lot. So back to the question:
Do you know of any such codebases?
If you want to dive into computational photography/ computer vision some more, here's a great class for it: https://www.udacity.com/course/introduction-to-computer-visi...
The key is in the finder patterns (mentioned in the article). If you imagine a line cutting through the center area of one and the series of pixel values you get along the line you'll notice that you get a simple symmetric (mostly)White(mostly)BlackWBBBWBW series. These sequences are easy to search for to get a list of finder pattern candidate locations. Rejecting the false positives is a relatively straightforward and local operation, as is refining exactly where the pattern is centered.
With the cleaned up (hopefully short) list of candidate corners you can propose an orientation/scale (technically a homography) to do the necessary sampling to get the rest of the bits. If none of these work out, you ask the user to try take another picture.
Or an explainer for Reed-Solomon codes: https://sidewords.files.wordpress.com/2007/12/thesis.pdf
IIRC the process goes something like this:
Preparation:
- Make your image grayscale
- Clean up your pic somewhat (we did an Fourier analysis on the data to find any repeating distortion like a moiré pattern, plus some averaging of completely white or black pixels)
- Adjust brightness so you have reasonable values throughout
- Somewhere in there you reduce the size to 512x512 or similar to make your life a bit easier in terms of computing power.
Finding the anchor points:
- You create a "mask" of what you're looking for
- You "move" that mask over your whole image, pixel-by-pixel
- For each pixel position, you compute the difference between the image and your mask (this should give you a single value for each position)
- The position with the lowest difference value is probably where your pattern is
Our images were flat, but were rotated a random angle. Our alignment marks were circular, though, which makes the thing a bit a bit simpler. I imagine the actual QR code algorithm skews and rotates its "candidate" mask so it can find codes in a skewed image.
Also, it might just make a first pass looking at big contrasting spots and seeing if they match what a finder pattern should look like. There's tons of ways this can be optimized to run fast on a limited device.
Anyway, once you have the 3 finder "cubes", you can try and see if the alignment mark is where you expect it, and at this point I guess you have your QR position in the original image. What I'd probably do then is go back to the original image, extract the relevant portion of it and then rotate and skew it so it's "square" (there's a matrix transform you can use for this, IIRC). Then you can cut it up into "pixels" by following the timing marks, and the rest is explained in TFA.
I know there's some number magic that happens even if you get some of these wrong, but I imagine it's kind of some kind of reverse checksumming thing going on.
I've used it on oilfield prototypes just printed on weatherpoof laser labels, and they're still readable even with big gouges and divots missing. By contrast, despite the redundancy, you can scrog a QR code with a single unfortunately placed scratch. (As I reconfirmed out this week trying to read the wiki/docs link for a secondhand laser cutting module I picked up: a screw on the rail had dragged through the QR code in a horizontal line - not through the timing section, but enough to make it unreadable. Fortunately, the model is identifiable visually on the mfr's site, so I can be sure what kind of safety goggles I need!)
Given that two timing patterns are perpendicular to each other, how is that possible? Did the line come from the rightmost boundary and stop before the vertical timing pattern? Then there should be no real difficulty in reading that and it might well be a decoder problem.
The finder and alignment patterns in QR-code just take up space and don't seem to help very much, but I can't back that up. Maybe some scanners can really do better with QR?
Bruh that's the whole reason I read the article. That's what I wanted to know.
> There is still a bunch of left over space after our data. This is where the error correction information is stored so that it can be read if partially obscured. The way this works is actually really really complex so I'll leave that out.
I find myself guilty of leaving it out of my page too, writing:
> (Note: The math behind computing the Reed-Solomon error correction codes is omitted because it is long, tedious, and not very interesting.)
Since there is some interest, let me try to explain a bit. Conceptually, it's simple. Put the data bytes (e.g. [A, B, C, D]) into polynomial coefficients (e.g. Ax^3 + Bx^2 + Cx^1 + Dx^0). Compute the Reed-Solomon generator polynomial, which is just a bunch of (x - a_i) terms multiplied together. Then divide your data polynomial by the generator polynomial, keep only the remainder (not the quotient), and that is your ECC polynomial. The catch is that all the polynomial coefficients take place over a finite field, which is a second layer of difficulty when it comes to explaining the math.
It's the scanner that dictates what angles a barcode can be read at. A 2D barcode scanner (which you need to read QR codes AT ALL -- or even a smart phone running Cognex's barcode scanner app) can read regular 1D barcodes from absolutely any orientation.
You can reduce the size of 1D barcodes to increase data density:
http://www.barcodebootcamp.com/labels/barcode-density.html
It's rarely done because easy decoding is usually the priority.
Plus, you can make 1D barcodes extremely small vertically, as commonly seen on the edge of USPS envelopes:
https://www.wsel.com/sites/default/files/IntelligentMailBarc...
...and that way store several lines of 1D codes holding much more information in the space of one QR code.
2D codes are useful in some circumstances, but they're not better than 1D barcodes.
I submitted some patches to ZBar to improve this. See also my answer to this stack overflow question:
https://stackoverflow.com/a/60518608/512904
I don't understand what you mean by this:
> Although the QR format does have an encoding called “byte mode”, each byte in this mode represents an ISO 8859-1 character, not binary data.
I've read the standard but I didn't get the impression that the 8 bit encoding mode was assumed to be text. Can you cite the part that says this?
I looked up what the standard says:
> The default interpretation for QR Code is ECI 000020 representing the JIS8 and Shift JIS character sets.
> 8.3.4 8-bit Byte Mode
> The 8-bit byte mode handles the 8-bit Latin/Kana character set in accordance with JIS X 0201 (character values 00HEX to FFHEX).
> In this mode data is encoded at a density of 8 bits/character.
> 8.4.4 8-bit Byte Mode
> In this mode, one 8 bit codeword directly represents the JIS8 character value of the input data character as shown in Table 6, i.e. a density of 8 bits/character.
> In ECIs other than the default ECI, it represents an 8-bit byte value directly.
So it's just an 8 bit value that may or may not represent a JIS8 character. The referenced table 6 is a lot like the table in the article linked above but for JIS8 instead. There are reserved/unused characters but I didn't get the impression that they were invalid. It seems contradictory to me to prohibit the use of bytes which may be in use in the future. Is this incorrect?
https://en.wikipedia.org/wiki/JIS_X_0208#Unassigned_code_poi...
Gives me the same impression. Plenty of "should not"s and even historical examples where people did something with those characters anyway. So it didn't seem like a big deal to me that binary data might contain those bytes. It even says many unassigned characters were assigned in newer standards which also happens often in Unicode.
The RFC for base 45 is interesting too:
https://datatracker.ietf.org/doc/rfc9285/
> Even in Byte mode, a typical QR code reader tries to interpret a byte sequence as text encoded in UTF-8 or ISO/IEC 8859-1.
> Thus, QR codes cannot be used to encode arbitrary binary data directly.
The implication being that it would work if only we could fix those decoders so they stop trying to convert data to text.
That's been my exact experience. The binary decoding problems in zbar were due to character encoding conversion attempts. I just made it output the bytes unchanged and it worked perfectly with arbitrary binary data. I also studied zxing-cpp and it does both: it converts the binary data to text and keeps a copy of the original bytes. There's even comments saying the standard isn't clear.
We should fix that! Which QR decoders still lack support for binary data decoding?
I submitted patches to zbar to add a binary decoding mode, it's already available in new versions. ZXing and zxing-cpp also have support.
Maybe it's the camera apps that lack support for this.
But even with binary data encoded to baseXX, you still need to decide what the byte stream means. I was mainly looking at how to efficiently encode a hierarchical document containing the most common data types (that anyone can decode and inspect) into a QR code.
I have never heard of Paged Out. It looks neat. I hope they are still putting out issues.
More data AND error correction.
Denso Wave owns a number of patents on QR code technology, but has chosen to exercise them in a limited fashion. In order to promote widespread usage of the technology Denso Wave chose to waive its rights to a key patent in its possession for standardized codes only. In the US, the granted QR code patent is US 5726435, and in Japan JP 2938338, both of which have expired. The European Patent Office granted patent EP 0672994 to Denso Wave, which was then validated into French, UK, and German patents, all of which expired in March 2015.
It kind of reminds me of people showing you art they've made, or a meal they've cooked, who feel the need to start off by saying "I know it's super bad / don't expect much / I really messed up".
– If the thing is indeed bad, then the comment won't save it. Furthermore, I might question why you're showing this thing to me in the first place if you don't believe in it yourself?
– If the thing is actually good, then I get the impression you're just self-deprecating for no reason… Possibly looking for attention? It could also make me look for flaws where I otherwise wouldn't, just for the sake of it, because you have now convinced me — at least subconsciously — that your creation sucks.
Bottom line being: Let the content speak for itself, and leave it up to the audience to decide whether something is interesting or not.
It signifies 'you may not think you are going to find this interesting, you may not be very technical - but trust me, I'm like you and you will find it interesting - and this article will be written in plain, colloquial english which you are likely to understand with a bit of humour'.
It may not work for you, but it provides reassurance for other readers, such as - me.
"Please don't fulminate."
https://news.ycombinator.com/newsguidelines.html
One reason we have those guidelines is that comments like this tend to get upvoted to the top of threads, where they sit gathering mass, letting off fumes, and choking out more interesting discussion. That's where this one was when I saw it a moment ago. Unfortunately, it takes manual intervention to do anything about, which is scarce and intermittent at best.
On a more serious note, I know someone who does this kind of talk in real life, 24/7. He's insufferable.