Zenn
🧐

QRコード生成器だけが残された世界で～統計的手法によるアルゴリズム解析の旅～

2024/12/04に公開
Python
QR コード
tech

以下は、脆弱エンジニアの Advent Calendar 2024 Day4 参加記事となります。

Story

2XXX年――。文明の絶頂にあった人類は、突如として全ての知識を失った。
未曾有の災厄により、書物、データ、歴史の記録が一夜にして消え去り、情報を失った人類は存亡の危機に立たされた。
しかし、生き残った人々は希望を捨てず、荒廃した世界で奇跡的に「QRコード生成器」を発見する。
この機械は任意の文字列からQRコードを生成できたが、そのアルゴリズムは完全なブラックボックスであり、解析するための技術も失われていた。
それでも、人々はこのQRコードに隠された秘密を解き明かせば、知識を再構築できると信じ、統計的手法を用いて解析に挑む。
果たしてその先に待つのは、人類の再生か、さらなる絶望か――。

QRアルゴリズム解析における前提条件

  1. 任意の文字列入力に対するQRコード生成結果が得られる。
  2. ただし、26字以内という文字数制限がある。
  3. 出力QRコードのピクセルサイズは25x25で固定されている。
  4. QRコード生成器は（こう見えて頑丈なので）、無限回の入力を試行できる。

暗号の文脈における選択平文攻撃が利用できるシチュエーションと言えるだろう。(尤も、今回のQRコード生成器は暗号化鍵を持たないため、暗号化ではなく符号化にあたる。) ちなみに共通鍵方式[1]、公開鍵方式[2]を利用するQRコードも存在する。

解析の方針

今回のゴールは、QRコード生成器の出力から入力文字列を解読できること、とする。
まずは、全体的な傾向を掴んだ後、入力を微妙に変えた時の比較解析といったミクロな視点から、クラスター分析によるパターンの解析といったマクロな視点へ広げていくことを検討する。

1.グローバルな解析

最初に、無数のランダムな文字列入力に対する出力の平均と分散を可視化する。

分散が0のところは入力にかかわらず値が固定されている箇所だといえる。
したがって、この段階で 241/625 = 約39% が固定値であるとわかる。
なお、以降の解析において、上記固定値箇所はグレーでマスクし、評価対象外とする。

2.データ構造解析

次は、26文字の文字列をランダムに生成し、N文字目(1≦N≦26)を変更したときの出力の変化を確認する。具体的には、ランダムに生成した500種類の親文字列を基に、それぞれ1文字だけ変更したデータ群を作成し（20通り）、各データ群の分散を計算。その結果得られた500個の分散値の平均を評価する。
はじめに、1文字目を変更することによる出力への影響を確認する。

右端の赤で矢印をつけた場所(7ピクセル分)に注目すると、分散が大きいことから1文字目変更の影響が及ぶ場所、つまり1文字目のデータが格納されている場所だと推定できる。
この推定の正しさを検証するため、他の箇所についても同様に確認する。

変更した文字の位置に対応して、変化する7ピクセルの箇所が移動していることがわかる。
よって、文字列中の位置とQRコードでのデータ格納位置の対応が判明したといえそうだ。
整理すると以下のようなマップとなる。draw.ioからの変換時に意図していない色合いになったことをお詫びしておく。


左の黄色い部分は、分散が大きい箇所であり、微小なデータの違いによって大きく変化する場所だと言える。これは、”誤り検出訂正的なもの”が使われていると推測しても自然な発想だろう、とはいえ、今回の解析では追求しないものとする。
また、26文字しか格納できない点について、矢印で示した4ピクセル分の余りがある以外に格納の余地がないからと推定できるだろう。
上記の解析結果を1次元にしたものが以下である。(わかりやすさのため、1ピクセルのことをbitと表現する。)

また、上記の図において、省かれている空色の部分(15ピクセル x2)に注目すると以下のように重複していることがわかるが、ここでは触れない。

3.マスクパターン解析

データ構造解析においては、1文字目を変化させたときに大きく変化する箇所からデータ格納位置を特定できた。一方で、文字列中の変更していない2～26文字目の部分についても、実際の出力は変化している。これは、データ内容に依存しない要素の存在が示唆される。
よって、以下の解析を行う。

適当な26字の文字列("ABABABABABABABABABABABABAB")を用意し、13~24文字目を固定、それ以外をランダムに変化させた時の、図に示した領域の出力についてクラスタリングを行う。
クラスタリングには、scikit-learn, K-meansを利用した。

十分なサンプル数のもと(n=8000), 8クラスへのクラスタリング時に、シルエットスコアが1、つまり各クラス内のデータが完全に一致することがわかる。

上記における各クラスの出力値は以下の通りである。

上記の出力は、13~24文字目の”ABABABABABAB”のデータ格納箇所に対して、8通りのマスクを適用したものと考えてよいだろう。
最後に、上記においてクラスター１に合致したQRコードの出力をサンプリングし、平均値を求める。

図6におけるHeader, Footer領域、図7で示した領域が固定化されていることがわかる。
詳細は割愛するが、クラスター1～8と図中にマスクパターン識別子として矢印で示した3ピクセルが対応関係にあることがわかる。

4.マスクパターンの特定

最後に上記で示されたマスクの特定を試みる。
少し苦しいが、７ビットの総当たりで、"A":0x41, "B":0x42を特定したとする。
A:01000001 B:01000010でビット反転を行えば、マスクパターンを特定できる。

他のマスクパターンについても同様にして求めることができる。
以上の解析結果より、任意のQRの出力から、マスクパターンの特定とアンマスクを行い、データ格納順に入力文字列を復元できる方法を特定したといえる。

おわりに

今回は、事前知識を使わずにQRコードの仕組みについての解析を行ったつもりです。(少々論理展開が苦しいところがあるので、よりロジカルな解析フローがあれば教えてください。)
いまさらQRコードネタとは何番煎じだよ、という声も聞こえてきそうですが、つい先日、QuizknockさんもQRコード題材の動画を投稿されてましたね、(しかもデンソーさんの公式案件です)。このテーマ自体は以前から考えていたもので、以下に示すQRコード3部作の第1部にあたります。

  1. QRコードとデータサイエンティスト ← 今回のトピック
  2. QRコードと機械学習エンジニア
  3. QRコードとハッカー

まずは、QR生成の仕組みを把握したうえで、擬似的な生成器を作り、最後に攻撃する、という流れなんですが… また、機会があれば続編を書きます。

Source code

QRコード生成器

import segno
import numpy as np
import matplotlib.pyplot as plt

def gen_vis_qr(text):
    # Check if the input text exceeds 26 characters
    if len(text) > 26:
        print("Error: The input text is too large.")
        return None
    
    # Generate QR code with explicit byte mode, version 2-M (up to 26 bytes)
    qrcode = segno.make(text, mode='byte', micro=False, version=2, error='M', boost_error=False)
    
    # Convert the QR code to a NumPy 2D boolean array
    matrix = np.array(qrcode.matrix, dtype=bool)
    
    # Visualize
    plt.figure(figsize=(6, 6))
    plt.imshow(matrix, cmap="binary")
    plt.axis("off")
    plt.show()
    return matrix

今回用意したQRコード生成器は、26文字以内の文字列に対し、version:2, error訂正レベル:M, byte modeによりQRコードを出力するものでした。

参考文献

  1. JIS X 0510：2018 (ISO/IEC 18004：2015)
    https://kikakurui.com/x0/X0510-2018-01.html
  2. Segno - Python QR Code and Micro QR Code encoder
    https://segno.readthedocs.io/
脚注

  1. SQRCコード ↩︎

  2. DSQRコード ↩︎

Discussion