二维码

二维码

二维码基本可分为行列式二维码矩阵式二维码

行列式二维码就是条形码,而矩阵式二维码中,最流行的就是QR Code


QR Code

作为最流行的二维码,QR Code的全称为Quick Response Code,是近年来在移动设备上超流行的一种编码方式

QR Code一共有40个标准版本(Version),Version 1是$21 × 21$的矩阵、Version 2是$25 × 25$的矩阵......每提升一个Version,矩阵大小会增加4

QR Code的大小计算公式是:$(V - 1) × 4 + 21$

最高的Version 40:$(40 - 1) × 4 + 21 = 177$,所以是$177 × 177$的矩阵

我们首先从最简单的Version 1来看看QR Code的结构


Version 1

首先是一张Version 1的样例图片:

然后是Version 1的结构图:

在QR Code中,码元(module)是基本单位,Version 1的$21 × 21$矩阵就是由$21 × 21$个module组成的正方形

最基础的QR Code只有黑白两色,可以将module理解为单位黑色像素点

我们首先留意到三个角的图案,它被称为定位标识


定位标识

英文名为Position Detection Pattern,它存在于各个Version的QR Code中,作用是快速在影像中找到QR Code的位置

由于有定位标识,所以在扫描时,哪怕没有对正,计算机也能快速定位到QR Code并正确读取当中的数据:(类似数学中的坐标系转换

无论在哪个Version中,定位标识▣的大小都是固定的:$7 × 7$ modules


回到Version 1的结构图中:

三个定位标识▣周围都有一条白边,使其与中间的QR Code 数据分隔开

白边的英文名为Separators for Position Detection Patterns,译作分隔符;它的作用是辅助定位标识,使得整个QR Code在被扫描的过程中能够更快地定位

每条白边与定位标识相联系,大小固定为$1 × 8$ modules;倘若将白边定位标识看作一个整体,那么整体的"定位标识"的大小应该是$8 × 8$ modules


定时标识

结构图中,相邻的两个定位标识▣之间有一条黑白相间的带,它被称为定时标识(Timing Pattern)

Timing Pattern是一条宽1 module的黑白交替带,由黑色开始和结束,差1 module与白边处于同一直线上

随着Version的提升,QR Code的大小随之增加,看上去同样大小的QR Code图片,会随着Version的提升密度增大:

Timing Pattern用于指示密度,在非正对扫描时,它还用于辅助建立坐标系


Version 2

让我们上升一个Version,查看Version 2的样例QR Code:

可以看到,减去左右定位标识$8 × 8$的宽度后,$25 × 25$的Version 2的数据的宽度只有:$25 - 8 - 8 = 9$ modules

Version 2的QR Code结构相比较Version 1而言,新增了右下方的小定位标识▣


校正标识

校正标识的英文名为Alignment Pattern,它只存在于Version$\geq$2的QR Code中,并且随着Version的提升,它的数量也会增加

举例Version 8的结构图:

可以看到Version 8包含6个校正标识

校正标识用于进一步辅助建立坐标系,它的格式也是固定的:


综上,由定位标识(Position Detection Pattern)定时标识(Timing Pattern)校正标识(Alignment Pattern)三者构成QR Code的定位图案

定位图案的存在能够帮助计算机在扫描QR Code时快速建立坐标系,并根据此来解读出其中数据

对于一张QR Code,除去了定位图案外,剩下的部分可以分为2部分:

  • 功能性数据
  • 数据和纠错字码

功能性数据

格式信息(Format Information)

以Version 1的QR Code举例,留意下图的绿色区域:

对于一张QR Code而言,需要一些特殊的地方来存储一些必需的数据,而上图的绿色区域存储的是格式信息(Format Information)

得益于所有Version的定位标识的大小都是$7 × 7$,因此绿色区域的大小在所有Version中都是固定的

格式信息(Format Information)需要15 bits的位置来进行存储,为此我们将上图的绿色区域进行编号:

首先,下面编号 6 上方的module,被染黑了

被染黑的module被称为Dark Module

前面有提,绿色区域用于存储占15 bits的格式信息,而QR Code中,每个module都可以看作是一个比特位,1 0 分别用 代表

绿色区域一共有31个module,为了存储15 bits的信息,先将一个module去除掉,而去除掉的module就是上图中的Dark Module

Dark Module的位置是固定的

去除掉后,剩余的30 modules,可以对半分为两个15 modules;由于我们只需要15 modules来存储格式信息,为此,QR Code规定,这两个15 modules都存储相同格式信息

左上角的15 modules与剩余的15 modules的信息是完全一样的,基于图上编号的顺序,如果检测到不一样,那么计算机会认为这是一张错误的QR Code

重复存储格式信息看上去会造成空间不必要的浪费,信息冗余,然而信息冗余却是信息安全的一道防线

同时,当QR Code的某个部分被遮挡、损坏,冗余信息的存在有可能确保QR Code的正确被扫描读取

格式信息(Format Information)都包含什么内容?

这篇文章是从一个CTFer的角度去学习二维码的,如果继续深入,那要深入的地方实在太多了,恐怕得完完全全将QR Code的生成原理探究清楚

这不是我们的目的,为此在这里我们选择浅尝辄止,只需要知道,对于所有Version的QR Code,定位标识附近有存储格式信息的30 modules,存储了2次重复的格式信息;此外还有一个固定的Dark Module

顺便一提,格式信息的15 bits中,2 bits用于表示纠错等级(Error Correction Level)、3 bits用于表示掩码(Mask)、10 bits用于表示通过BCH Code计算的纠错位

不需要理解这三个分别是什么,只需留意下,在上图中,编号 0、1 的位置存储纠错等级、编号 2、3、4 的位置存储掩码,这在后面需要涉及到


版本信息(Version Information)

功能性数据分为两部分,除了上面结束的格式信息,剩下的就是版本信息(Version Information)

版本信息存在于Version$\geq$7的QR Code中,它们的位置则是下图的蓝色区域:

两处蓝色区域都是$3 × 6$或$6 × 3$的区域,共占据18 modules

格式信息重复存储了2次一样,18 bits的版本信息也有一样的冗余度,两处蓝色区域存储的是一样的版本信息,而存储顺序为:

版本信息从Version 7到Version 40,都是固定的18 bits二进制字符串,我们可以通过截图的方式做个部分记录:

具体可到网站https://www.thonky.com/qr-code-tutorial/format-version-tables#list-of-all-format-information-strings 上查阅


QR Code就占用了上面的特殊位置来存储功能性数据,除去定位图案功能性数据,剩下的位置都属于数据和纠错字码

纠错等级

使用过QR Code的同学可能体会过,哪怕QR Code有一部分的残缺,可还是能够扫描出正确的信息。这得益于QR Code具备"纠错功能",能够在一定程度上恢复残缺的数据

举例,我们经常会在QR Code中心添加图像,如:

很显然,图像破坏了数据的完整性,却依旧能扫描出数据

这得益于剩余区域中不全是数据

QR Code规定存在4个纠错等级

  • L:7%字码可被修正
  • M:15%字码可被修正
  • Q:25%字码可被修正
  • H:30%字码可被修正

将一张QR Code剔除定位图案功能性数据后,剩余区域可分为2种内容:数据(Data Codewords)纠错字码(Error Correction Codewords)

随着纠错等级的提升,二维码能够容纳的数据就越少,而纠错字码则越多

以纠错等级为25%为例,如果QR Code中间要放一张图片,那图片占QR Code的最大比例为$25% × 25% = 0.0625$

由于纠错等级有4种,$2^2=4$,占用2 bits空间,因此在前面的格式信息(Format Information)中留了2 modules用于放置纠错等级信息


数据、纠错字码

关于创建一张QR Code的简单步骤:

  1. 选择最优的编码模式
  2. 对数据进行编码,以便放入QR Code中
  3. 生成纠错字码
  4. ......

第二步对源数据进行编码后,得到若干组直接存放在QR Code中的数据;随后的第三步,在得到了源数据对应的编码数据后,必须再使用这些数据生成纠错字码

QR Code的纠错字码主要通过里德-所罗门纠错算法(Reed-Solomon Error Correction)来实现

纠错字码数据是关联的,在扫描QR Code时,计算机通过比较数据纠错字码来确定是否正确地读取了数据;如果它发现没有正确地读取数据,还会利用纠错字码来纠正数据的错误,进而正确读取出信息

我们来看一张$29 × 29$的Version 3 QR Code的结构:

黄色区域部分被分为3类:

  • D (Data)为前缀的数据区域
  • E (Error Correction)为前缀的纠错字码区域
  • 位于左下方,名字为 X空白区域,该区域留作备用

D1 从右下角开始,它到 D2 之间隔着 D14... 各个区域这么"怪异"地放置着,是基于QR Code的生成机理的

每个Version的QR Code的区域放置都是基于QR Code的生成原理的,不能简单地理解为:"D 从右下角开始,往上往左,间隔一个区域到达下一个 D 区"

我们来看一张Version 7的结构图:

D1D2 之间间隔着 D14D27D40D53区域

对于不打算深入学习的我们,只需知道数据(Data Codewords)大致位于二维码右侧,而纠错字码(Error Correction Codewords)大致位于二维码左侧

再返回这张图:

我们来单独看看数据区域

D1 为例,它是一个$2 × 8$ modules

在生成QR Code的过程中,把编码好的数据填充到QR Code的module上的顺序是这样的:

从右下角出发的蛇形路线
在生成**数据**时,其实源数据已经被"打乱"了,打乱的目的就是为了能够在生成QR Code时直接将数据一一填充

填充完 D1 后,按照顺序直接填 D14,而不是先填 D2、等到第14次的时候再回来填 D14

填充的时候是以$2 × 4$ modules区域为基本单位的,而在每个区域中,QR Code采用$Z$字型路线:

因此,如果我们要肉眼读取QR Code的数据,务必记得这么Amazing的顺序


掩码(Mask)

在填充完数据纠错字码后,可能会出现大片的连续黑白区域在QR Code上

为了避免这种情况,QR Code规定,在填充完之后需要对整个QR Code应用一些全局的Mask:

Mask共有上图的8种,填充完后会在其中挑选一个效果最好的Mask,对整张QR Code的非定位图案、非功能性数据区域进行Xor运算

如何挑选出效果最好的Mask也是有依据的

如此做后,得到的QR Code就能避免大片的黑白连续区域这种情况,更利于识别

而且Mask Xor这一步是必须的,计算机在解码QR Code的过程中,会根据格式信息(Format Information)中标明的3 modules信息,再对QR Code进行Xor运算,得到真正的数据信息

众所周知,对同一变量异或两次,还是等于本身:a ^ b ^ b == a


回到介绍格式信息的那张图片中,我们可以标注出2 bits的纠错等级和3 bits的掩码

这里可以记录一下:

2 bits纠错等级

  • 11L级,7%字码可被修正
  • 10M级,15%字码可被修正
  • 01Q级,25%字码可被修正
  • 00H级,30%字码可被修正

3 bits掩码

Mask Pattern(掩码模式) 位于格式信息中的编码 Mask Pattern(掩码模式) 位于格式信息中的编码
0 101 4 001
1 100 5 000
2 111 6 011
3 110 7 010

后面10 bits是基于BCH Code计算的纠错位,略过不讲,但对于一张QR Code,一旦确定了纠错等级掩码,就意味着知道了完整的格式信息

详细的格式信息字符串可以查阅网站:https://www.thonky.com/qr-code-tutorial/format-version-tables#list-of-all-format-information-strings


编码模式(Mode)

在将特定的文本转化成QR Code前,第一步其实是要选择编码模式

QR Code拥有多种编码模式

  • 数字模式(Numeric Mode

    包含 $0$ 到 $9$ 的十进制数字

    编码方式:$2^{10} = 1024 \lt 1000$,所以把每3个数进行分组,每组转换成10 bit二进制数

  • 字母数字模式(Alphanumeric Mode

    除了 $0$ 到 $9$ 的十进制数字,还有26个大写字母(不包含小写字母),符号 $%*+-./: (空格)

  • 字节模式(Byte Mode

    Byte Mode默认采用ISO-8859-1字符集中的字符

    可以在https://www.htmlhelp.com/reference/charset/latin1.gif中查看ISO-8859-1的所有字符

    事实上,UTF编码是兼容ISO-8859-1

    因此当待编码的信息中出现了中文字符,那么会转变使用UTF-8编码

  • 日文模式(Kanji Mode

还有其它的编码模式,如ECI模式(Extended Channel Interpretation)、结构化附加模式(Structed Append Mode)、FNC1模式

但最常用的是上面的 $4$ 种

每种编码模式都对应一个4 bits的指示符(indicator):

Mode Name Mode Indicator
Numeric Mode 0001
Alphanumeric Mode 0010
Byte Mode 0100
Kanji Mode 1000

在编码之前,会先把待编码的字符扫描一遍,选择更合适的编码模式


计数(Count)

一张指定规格的QR Code是有容纳字符上限的

假如某种规格的QR Code最多只能容纳20个字符,那么如果要把一个长度为30的字符串变成QR Code,就一定不会选择这种规格

但是如果字符串的长度是19,那么很可能选择这种规格

在这种情况下,有1个字符的位置是空缺的,那么就需要标识出来,以免过度解码;这就是需要计数器(Count Indicator)

Count Indicator就是待编码字符串的长度,转换成二进制数

上图是从https://www.thonky.com/qr-code-tutorial/data-encoding中摘录的Count Indicator转换成二进制数的位数,不同Version、不同编码模式都会导致不同的位数

QR Code中空余的地方依次存放 11101100 00010001,直到到达QR Code的最大存储限制为止


我们来演示一下编码模式指示(Mode Indicator)计数器(Count Indicator)的实际使用过程

举例将 examine 编码,首先根据Byte Mode的规则,将每个字符转换成8 bit二进制数:

e01100101x01111000a01100001m01101101i01101001n01101110e01100101

然后拼接成:01100101011110000110000101101101011010010110111001100101

此时,需要加上两部分内容:模式对应指示(Mode Indicator)计数(Count Indicator)

Byte Mode 对应的Indicator是 0100,而字符串 examine 长度为 $7$,转换成8 bit二进制数 00000111

最后把这三部分拼接起来:

01000000011101100101011110000110000101101101011010010110111001100101

这也就是最终将 examine 按照Byte Mode编码得到的结果


QR Code Test

我们以一道CTF的题目来验证我们所学的,格式为Flag{xxx}

链接:https://pan.baidu.com/s/12hFjZqCmsWynjdUt1gyJtg
提取码:m8ul

解答

下载得到一张只有一半的QR Code图片

发现大小为$29 × 29$,Version 3,而Version 3的格式图为:

恰好我们得到的是右半边,也就是说,我们并没有丢失数据D 区),丢失的只是部分纠错字码E 区)

纠错字码的存在只是为了保证数据的正确读出,在丢失了一半QR Code这么极端的情况下,我们仍可以只从 D 区中读取出数据

首先,这残缺的QR Code给予了我们部分的格式信息

这里存储着格式信息的后8 bits,11100111

我们到list-of-all-format-information-strings这个网站上查阅,发现只有字符串 001110011100111 的后8 bits符合上图的情况

因此,这张QR Code的格式信息就是 001110011100111,它告诉我们,纠错等级 00 为H级、掩码 111 为Mask 2

有了掩码,我们可以将这张残缺的QR Code进行Xor运算,就能得到真正的数据了

我们借助工具网站https://merricx.github.io/qrazybox/ 来继续

按照残缺QR Code的右边绘制上去,并选定纠错等级为H、掩码为Mask 2:

点击右上方的 Tools ,再选择 Data Masking ,选择Mask 2与上图进行Xor,得到真正的数据:

还记得将数据填充进QR Code的顺序吗?$Z$字型

单独看看右下方,按照$Z$字型读取出每个区域的数据:

读取出区域1的数据为 01000001,在Version 3中,区域1上面的是区域14,它的数据为 01000100

由于数据( D 区)没有损坏,因此能够读出所有的 D 区信息,按区域顺序把读取出来的信息拼接起来,得到:

1
0100000101110100011001101100011000010110011101111011010011110101000101010111010010010100001101011111001101000100010001010011001100010100000101011111010100110011000000110011001101000101001101111101000011101100

这里就是包含flag的信息了

首先根据最前面的 0100 判断出编码模式Byte Mode,Version 3的Byte ModeCount Indicator为8 bits,也就是 00010111,转换成十进制就是 $23$

这表明QR Code中的信息字符共有 $23$ 个

$23 × 8 = 184$,我们只需在剩下的二进制数中截取前 $184$ bits,每8 bits解码成对应字符即可

1
2
3
4
5
str = "0100011001101100011000010110011101111011010011110101000101010111010010010100001101011111001101000100010001010011001100010100000101011111010100110011000000110011001101000101001101111101000011101100"
str = str[:23*8]
for i in range(0, len(str), 8):
print(chr(int(str[i:i+8], 2)), end="")
# Flag{OQWIC_4DS1A_S034S}

我们可以借助工具来强行解码(Force Decode),这个工具就是打开的网站https://merricx.github.io/qrazybox/

Force Decode指不理会E区数据,直接从D区中提取出数据

先把之前的Xor撤销掉,回到图片:

点击右上方的 Tools ,然后选择 Extract QR Information

下方的注释也有说了,该功能是"强制解码,尽可能地从当前QR Code中得到信息",就我们这张QR Code而言,它并未丢失 D 区的数据,所以它理所应当能够得到完整的信息:

反汇的信息十分齐全,可以亲自检验一下Data blocksFinal data bits部分,体会下QR Code中的区域是不连续的


还有一道类似的题,格式为SECCON{xxx}

链接:https://pan.baidu.com/s/1VfTqVDdw8fvB_DSDa6B-HQ
提取码:2hb9

【以上参考】

联图网 生成二维码 https://www.liantu.com/

酷壳 "二维码原理"文章 https://coolshell.cn/articles/10590.html

博客文章 https://yous.be/2014/12/07/seccon-ctf-2014-qr-easy-write-up/

QR Code英文教程 https://www.thonky.com/qr-code-tutorial/introduction

夏风 博客文章 https://blog.xiafeng2333.top/ctf-13/

QRazyBox 二维码在线绘制工具 https://merricx.github.io/qrazybox/


还有一道与二维码有关的题目,随手放这了,跟文章内容没什么关系

链接:https://pan.baidu.com/s/1-Ea2FTbgGZLMbDaSmQU3Jw
提取码:xexx

解答

得到 qrcode.txt,发现里面是二进制数据

复制到Python中,len() 一下,长度为625,恰好是$25^2$,猜测是一张二维码的数据

二维码的每个module都可以对应一个比特位

使用Python的pillow模块写脚本:

1
2
3
4
5
6
7
8
9
10
11
12
from PIL import Image
str = "111111100010..."
pic = Image.new("RGB", (25,25))
i = 0
for y in range(25):
for x in range(25):
if str[i] == '1':
pic.putpixel((x,y), (0,0,0))
else:
pic.putpixel((x,y), (255,255,255))
i += 1
pic.show()

运行代码发现的确是一张二维码,扫描得flag

嫌弃生成的二维码太小的话可以改用函数 paste()


收集的其它题目

  1. 由日本队TokyoWesterns主办的2015年首届MMA CTF

    Write-ups网站:https://www.robertxiao.ca/hacking/ctf-writeup/mma2015-qrcode/

  2. 残缺的左边二维码

    Write-ups网站:http://eleclog.quitsq.com/2014/12/seccon-ctf-2014-online-forensics-400.html

  3. 20180915_trendmicro

    Write-ups网站:https://github.com/pberba/ctf-solutions/tree/master/20180915_trendmicro/forensics_crypto_1_100

  4. SECCON CTF 2013

    Write-ups网站:http://eleclog.quitsq.com/2014/01/seccon-ctf-2013-online-forensics-400.html