Technik zum Lesen von QR-Codes ohne Computer

 (qr.blinry.org)
4 Punkte von GN⁺ 2024-01-23 | 1 Kommentare | Auf WhatsApp teilen
  • Es wird ein schrittweises Verfahren beschrieben, mit dem sich QR-Codes von Hand entschlüsseln lassen – von der Struktur eines Version-1-Codes mit 21×21 Modulen bis zum Entmaskieren und Umwandeln in Bytes
  • Spezialbereiche wie Finder-Pattern, Timing-Pattern, Formatinformationen und Quiet Zone sind für die Erkennung nötig, müssen beim eigentlichen Lesen der Daten aber übersprungen werden
  • Die Daten werden wiederhergestellt, indem man zuerst aus den Formatinformationen Maskenmuster und Fehlerkorrekturstufe bestimmt und dann die QR-Code-Module an allen schwarzen Positionen der Maske umkehrt
  • Gelesen wird ab der rechten unteren Ecke in Zickzack-Reihenfolge jeweils über zwei Spalten; im Byte-Modus werden nach 8 Bit Längenangabe die folgenden 8-Bit-Gruppen zu Zeichen-Bytes
  • Der Bereich für die Fehlerkorrektur muss nicht von Hand gelöst werden; bei einfachen QR-Codes reicht es, so viele Bytes zu lesen, wie das Längenfeld angibt, und sie per ASCII-Tabelle umzuwandeln

Einen QR-Code zum Lesen von Hand vorbereiten

  • Für einen Übungs-QR-Code gibt es drei Möglichkeiten
    • Beliebigen Text eingeben und damit den unten beschriebenen QR-Code aktualisieren
    • Einen vorhandenen QR-Code mit der Kamera scannen und das Lesen daran lernen
    • Mit zufälligen englischen Wörtern üben; das Wort wird nicht angezeigt und eignet sich daher als Training
  • Der Beispiel-QR-Code hat die Größe 21×21 Module
  • Die einem Pixel entsprechende Einheit in einem QR-Code heißt Modul (module)
  • Die Größe eines QR-Codes wird über die Version (version) unterschieden
    • Die kleinste Version hat 21×21 Module
    • Mit jeder weiteren Version wächst die Kantenlänge um 4
    • Ein QR-Code mit 21×21 Modulen ist Version 1

Spezialbereiche im QR-Code, die übersprungen werden

  • Das Finder-Pattern hilft dem Scanner, den QR-Code zunächst zu erkennen
  • Die leere Zeile rund um das Finder-Pattern muss beim Lesen des Inhalts übersprungen werden
  • Ein QR-Code der Version 1 hat kein Alignment-Pattern
    • Das Alignment-Pattern ist ein zusätzliches Muster, das dem Scanner beim korrekten Lesen des QR-Codes hilft
  • Das Timing-Pattern besteht aus zwei Linien mit immer abwechselnd schwarzen und weißen Modulen und hilft dem Scanner, den QR-Code korrekt zu lesen
  • Die Formatinformationen bestimmen Maskenmuster und Fehlerkorrekturstufe
    • Es gibt vertikale und horizontale Formatinformationen
    • Das Timing-Pattern unterbricht beide Linien
  • Die Quiet Zone ist der weiße Rand um den QR-Code
    • Sie hilft dem Scanner, Anfang und Ende des QR-Codes zu erkennen

Das Maskenmuster aufheben

  • QR-Codes verwenden eine Maske (mask), um große zusammenhängende schwarze oder weiße Flächen zu vermeiden
  • Insgesamt gibt es 8 Maskenvarianten
  • Im Beispiel werden schwarze Module als 1 und weiße Module als 0 gelesen, um die Bits des Maskenmusters zu bestimmen
    • Die Beispiel-Bits sind binär 110
    • 110 entspricht dezimal 6
  • Für jeden Maskentyp gibt es ein vordefiniertes Muster
  • Das Muster des Beispiel-QR-Codes sieht wie ein Teil eines Schwarz-Weiß-Regenbogens aus
  • Die Maske wird wiederholt über den Datenbereich gelegt; an jeder Position, an der die Maske ein schwarzes Modul hat, wird das entsprechende Modul des QR-Codes umgekehrt
  • Ein DIY zine mit einer Übersicht aller Maskentypen ist verfügbar

Kodierungsmodus und Lesereihenfolge

  • Die Entschlüsselung des Inhalts beginnt damit, zuerst den Kodierungsmodus zu prüfen
  • Die Kodierungsinformation befindet sich immer in der rechten unteren Ecke
  • Auch der Kodierungsmodus muss zunächst durch Anwenden der Maske freigelegt werden
    • Im Beispiel werden dazu mithilfe des Cheat Sheets zwei Kästchen XOR-verknüpft
  • Zu den Kodierungsmodi gehören Numeric, Alphanumeric, Byte, ECI und Kanji
  • Der Kodierungsmodus des Beispiel-QR-Codes ist Byte (4)
  • Der Inhalt beginnt in der rechten unteren Ecke
    • Gelesen wird im Zickzack zwischen zwei Spalten nach oben
    • Danach im Zickzack in den nächsten zwei Spalten links davon nach unten
    • Alle Spezialbereiche werden dabei immer übersprungen

Länge und Bytes entschlüsseln

  • Die ersten 4 Bit sind der Kodierungsmodus
  • Im Byte-Modus geben die nächsten 8 Bit die Länge des Inhalts an
  • Danach bildet jeweils jede Gruppe aus 8 Bit ein Inhalts-Byte
  • Auch die Längeninformation muss durch Anwenden der Maske freigelegt werden
  • Im Beispiel lautet die entmaskierte Längeninformation 00001100
    • Dezimal ist das 12
    • Das bedeutet, dass der gesamte Inhalt 12 Byte lang ist
  • Das erste entmaskierte Byte ist 01001000
    • Hexadezimal ist das 0x48
    • Das entsprechende ASCII-Zeichen ist H
  • Das zweite entmaskierte Byte ist 01100101
    • Hexadezimal ist das 0x65
    • Das entsprechende ASCII-Zeichen ist e
  • Die übrigen Bytes bleiben als Übung offen; man kann aufhören, sobald man so viele Zeichen gelesen hat, wie das zuvor gelesene Längenfeld angibt

ASCII-Tabelle und Fehlerkorrektur

  • Mit einer ASCII-Tabelle lassen sich hexadezimale Werte in Zeichen umwandeln
  • Kleinbuchstaben beginnen bei a mit 0x61 und enden bei z mit 0x7A
    • Die Zeichen dazwischen lassen sich durch Abzählen finden
  • Nicht jeder verbleibende Bereich enthält Inhalt
  • QR-Codes enthalten außerdem Fehlerkorrektur (error correction)
    • Dadurch bleibt ein QR-Code lesbar, auch wenn Teile beschädigt, unscharf oder fehlend sind
    • Die Fehlerkorrektur wird mathematisch erzeugt, wird für das Lesen von Hand hier aber nicht behandelt
  • Nachdem man das Verfahren zum manuellen Entschlüsseln einfacher QR-Codes gelernt hat, kann man mit der Schaltfläche für zufällige Codes kurze englische Wörter üben oder mit der Schaltfläche Scan code echte QR-Codes scannen
  • Der Quellcode liegt auf Codeberg
    • Besonders willkommen ist ein PR, der den UTF-8-Kodierungsmodus erklärt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-01-23
Meinungen auf Hacker News

  • Ende der 90er oder Anfang der 2000er wollte ich den Inhalt von Atari-8-Bit-Disketten auf den PC übertragen.
    Ich kannte zwar SIO2PC-Kabel und -Software, die den SIO-Port des Atari mit dem seriellen Port des PCs verbanden, hatte damals aber nicht die Elektronikkenntnisse, um so etwas selbst zu bauen.
    Am Ende schrieb ich auf dem Atari ein Basic-Programm, das die Diskette sektorweise auslas und die Daten mit den großen 4-Farb-Pixeln des Grafikmodus 3 auf den Bildschirm zeichnete. Dann schloss ich den Atari an die TV-Karte des PCs an und ließ ein Delphi-Programm fortlaufend Screenshots aufnehmen und die Daten dekodieren.
    Wegen leerer Sektoren geriet die Korrektur der Pixelpositionen durcheinander, also fügte ich ein Maskenmuster, eine Prüfsumme und sogar die Sektoradresse hinzu. Auf diese Weise konnte ich den Inhalt aller Disketten auf den PC übertragen.
    Ich halte das bis heute für meine größte Ingenieursleistung.
    Etwa zehn Jahre später entwickelte ich ein SIO2PC-Programm namens AspeQt, und der modernere Community-Fork RespeQt ist in diesem Bereich immer noch das am häufigsten genutzte Tool; auf AtariAge gibt es dafür sogar ein eigenes Unterforum: https://forums.atariage.com/forum/184-respeqt-sio2pc-softwar...

    • Das erinnert mich daran, wie die iPod-Firmware der ersten Generation und die Schlüssel per Reverse Engineering analysiert wurden.
      Angeblich ließ man die LCD-Hintergrundbeleuchtung Bitmuster blinken und las diese Daten mit einer Kamera aus: https://mastodon.social/@bagder/111538350617290554
    • Je verbreiteter geschlossene Systeme werden, desto mehr Zukunft scheint diese Art von displaybasierter Datenexfiltration definitiv zu haben.

  • Die Erklärung „Fehlerkorrektur ist komplizierte Mathematik, darum kümmert man sich beim Lesen von Hand nicht darum“ bräuchte etwas mehr Details.
    Ich verstehe, dass die Mathematik schwierig ist, aber ich würde gern wissen, ob die Fehlerkorrekturdaten am Ende angehängt werden, nach jedem Byte kommen oder irgendwo dazwischen eingefügt sind.
    Außerdem wüsste ich gern, ob man einen unbeschädigten QR-Code trotz vorhandener Fehlerkorrektur von Hand lesen kann, indem man nur den mathematischen Teil überspringt.

    • Bei Barcodes wird die letzte Ziffer als Prüfsumme verwendet; man addiert und multipliziert die Ziffern und führt dann etwa eine Berechnung wie % 10 aus, sodass eine Zahl von 0 bis 9 herauskommt.
      Daher besteht eine Wahrscheinlichkeit von 1/10, dass die Prüfsumme zufällig stimmt, obwohl die Daten falsch sind; außerdem ist die letzte Ziffer für die eigentliche eindeutige Barcode-ID des Produkts ohnehin nicht wichtig.
      Bei einem Artikel, den ich bei Home Depot zurückgeben wollte, war der Barcode eingerissen und die Prüfsummenziffer beschädigt. Ich versuchte verzweifelt, sie auszurechnen, bevor der Mitarbeiter sie manuell nachschlug, aber am Ende war der Mitarbeiter schneller; das vergesse ich nicht.
      https://www.gs1.org/services/how-calculate-check-digit-manua...
      https://www.simplybarcodes.com/barcode_check_digit_calculato...
    • Die Daten in einem QR-Code werden als Bitstream in einem von mehreren Alphabeten kodiert; Bytes sind nur eines davon.
      Danach wird der Bitstream je nach Größe und Fehlerkorrekturstufe in Blöcke aufgeteilt, die Fehlerkorrekturdaten für jeden Block werden berechnet, und anschließend werden die Blöcke interleaved.
      Deshalb scheitert diese Methode unabhängig von der Fehlerkorrekturstufe bei QR-Versionen über 5, und auch bei den Versionen 3 bis 5, wenn die Fehlerkorrekturstufe hoch ist.
    • An Artisanal QR Code zeigt, wie man eine Prüfsumme mit einer Arithmetik von Hand berechnet, die einer schriftlichen Division ähnelt.
      Tatsächlich werden je nach Art der Information zwei etwas unterschiedliche Codes verwendet, Reed-Solomon und BCH.
      https://www.quaxio.com/an_artisanal_qr_code.html

  • Verwandte Beiträge:
    Decoding small QR codes by hand (2012) - https://news.ycombinator.com/item?id=36173441 - Juni 2023, 69 Kommentare
    How a QR code works - https://news.ycombinator.com/item?id=32837565 - September 2022, 114 Kommentare
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=24119124 - August 2020, 41 Kommentare
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=18360847 - November 2018, 34 Kommentare

  • Der Artikel selbst ist schon hervorragend, aber noch beeindruckender ist, dass alle Abbildungen je nach Eingabewert dynamisch generiert werden.

  • Die Erklärung, wie man QR-Codes liest, war gut; für das Dekodieren gängiger eindimensionaler Barcodes wie UPC ist dieser Artikel ebenfalls brauchbar:
    https://scanbot.io/blog/how-do-barcodes-work/

  • Vor etwa 10 Jahren habe ich versucht, einen QR-Code von Hand zu lesen, habe aber wegen des Maskenmusters aufgegeben
    Noch bevor man den Datentyp herausfindet, muss man das Maskenmuster per XOR anwenden
    Ich frage mich, wie sehr dieses Maskenmuster echten QR-Code-Readern tatsächlich hilft
    Letzten Monat habe ich nach den optimalen Einstellungen für die Fehlerkorrektur gesucht; bei unbeschädigten Fällen wie einer vollständig auf dem Bildschirm angezeigten Matrix war die Antwort „keine“, und diese Schlussfolgerung zu finden war nicht einfach
    Ich habe keine Materialien gefunden, die verschiedene Einstellungen und Scan-Implementierungen unter realen Bedingungen vergleichen. Also habe ich selbst kleine QR-Codes auf dem Bildschirm mit verschiedenen Fehlerkorrekturstufen angezeigt und durch Wackeln der Kamera Leseprobleme simuliert, konnte aber keinen signifikanten Unterschied zwischen den Einstellungen feststellen
    Es gibt mindestens vier Ausrichtungsmarker, dazu große Ränder und Timing-Pattern; da frage ich mich, ob weiße Klumpen, die ohne Maske entstehen, wirklich so einen großen Unterschied machen
    Der zweite Grund, warum ich den Versuch aufgegeben habe, QR-Codes visuell zu lesen, war, dass meistens darunter die URL als Alternativtext stand. Später habe ich zwar ein paar Fälle ohne Alternativtext gesehen, aber das war sehr selten

    • Fehlerkorrektur ist seltsam
      Wenn man sie nicht verwendet, braucht die Nachricht weniger Platz und der QR-Code wird kleiner
      Wenn man in einen festen Platz passen muss, etwa beim Drucken von Stickern, kann man die Pixel physisch größer machen, und für zuverlässiges Lesen waren größere Pixel hilfreicher als Fehlerkorrektur
      Je nach Nachrichtenlänge gibt es Fälle, in denen man die Fehlerkorrekturstufe erhöhen kann, ohne die endgültige QR-Größe zu ändern; dann bekommt man beides
    • Fehlerkorrektur ist nicht für Leute gedacht, die sich fragen: „Wie mache ich die Nachricht kleiner, um die Lesbarkeit des QR-Codes zu erhöhen?“
      Sie ist für Leute gedacht, die eine vollständige URL mit Unmengen an Tracking-Parametern in einen Version-25-Code mit 117x117 packen und auf ein großes Schild kleben, damit die Daten auch dann überleben, wenn Vogelkot darauf fällt oder jemand einen Sticker darüberklebt
    • Letztes Jahr habe ich ein ähnliches Experiment gemacht, und zumindest bei 3D-gedruckten QR-Codes war die Variante ohne Fehlerkorrektur am besten
      Es ging darum zu sehen, wie klein man sie drucken kann, damit sie noch erkannt werden; wie im Nachbarkommentar scheint der Grund zu sein, dass die einzelnen Pixel größer werden

  • Ein Video zum Dekodieren von QR-Codes von vor etwa 10 Jahren: https://www.youtube.com/watch?v=KA8hDldvfv0 (20 Minuten)
    Ich habe auch eine interaktive Webseite, auf der man Schritt für Schritt einen QR-Code erstellt. Im Grunde ist es der umgekehrte Prozess: https://www.nayuki.io/page/creating-a-qr-code-step-by-step

  • Ich wurde neugierig auf Fehlerkorrektur; offenbar können QR-Codes mit unterschiedlichen wiederherstellbaren Anteilen von 7 % bis 30 % entworfen werden
    Interessant: https://docs.beaconstac.com/en/articles/6018654-what-is-erro...

    • Fehlerkorrektur ist wirklich ein interessantes Thema
      Shannon fand Mitte des 20. Jahrhunderts die theoretische Grenze, aber niemand wusste, wie man diese Grenze erreicht
      Als man in den 1990ern mit den Patenten auf Turbo-Codes plötzlich nahe an diese Grenze herankam, reagierte die Wissenschaft mit Unglauben
      Natürlich ermöglichen solche Technologien schnelle und zuverlässige Mobilfunknetze

  • Bei einem abgeleiteten Puzzle der 2023 Mystery Hunt gab es eine Aufgabe, bei der man einen QR-Code von Hand dekodieren musste, der so stark beschädigt war, dass selbst Fehlerkorrektur ihn nicht mehr wiederherstellen konnte
    Ich habe mir alle in diesem Kommentarbereich genannten Guides angesehen; sie waren nützlich, aber nicht großartig
    Deshalb finde ich es gut, wenn es mehr solcher ausführlicher Artikel gibt, und dieser hier wirkt eindeutig sehr ausgereift
    Falls es jemanden interessiert: Das Puzzle ist hier, und die QR-Dekodierung kommt im späteren Teil vor: https://puzzles.mit.edu/2023/abcde.puzzlefactory.place/puzzl...

  • Laut Wikipedia wurde der QR-Code 1994 von einem japanischen Autoteilehersteller zur Kennzeichnung von Autoteilen erfunden
    Ich frage mich, ob man ihn hätte verbessern können, wenn er heute erfunden worden wäre
    Hätte man ihn kleiner oder leichter lesbar machen können?

    • Es gibt nichts, was ein deutlich besseres neues Design grundsätzlich verhindert
      Auch 1994 waren Barcodes schon überall, aber das hat den Aufstieg des QR-Codes nicht verhindert
      Vielleicht gibt es aber auch nicht mehr viel Verbesserungspotenzial, außer man ändert das Konzept grundlegend und geht in Richtung NFC oder Ähnliches
    • Wenn er heute erfunden worden wäre, wäre er wohl sechseckig