二维码题目

本文承接上一篇文章《二维码》,主要介绍下CTF中涉及二维码的各种题目

原创文章,未经许可严禁转载

Author:ex@m1ne2


残缺的二维码

1 TMCTF

没想到的是,https://merricx.github.io/qrazybox/ 这个网站有集成对里所码的解码功能,于是不必去了解里所码;「只有二维码左边」的题目也变成套路题了...

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

前往 https://merricx.github.io/qrazybox/,将残缺的二维码填涂上(注意别忘了填涂灰色):

依次点击右上方的ToolsReed-Solomon DecoderDecode,得到结果:


2 SECCON 2013

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

与前面用来做示例的题目一样,只有D区数据,强行读取即可:

这里的灰色可以全填充为白色,因为是强行读取,不要紧

ToolsExtract QR Information


3 MMA CTF

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

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

这道不属于「只剩左边」和「只剩右边」的套路题,特此根据Writeup记录解法

前排提示,需要详细了解Reed-Solomon编码的可以参考文章:http://article.iotxfd.cn/RFID/Reed%20Solomon%20Codes

首先我们还是借助网站,根据格式信息补齐,并绘制上去:

强行读取,会发现:

坑人的是前面的数据对应着 FLAG IS,后面就断了

由于里所码也丢失了部分,因此不能通过直接解码获得内容

手动解决它,首先将上图中的Data blocks复制下来,网站已经帮我们解决了「去掩码」、「读取数据」等步骤,Data blocks中的内容就是摘掉掩码后的各个块的数据

首先,这是一张Version 2的QR Code,搜索得到它的结构图为:

可以看到,D区数据和E区数据都是依次放置的,因此我们无需像之前提到的Version 3那样进行排序

并且可知这张QR Code的纠错等级为Q,再次查阅官方文档可以知道:

该图表从 https://wenku.baidu.com/view/ef77275f312b3169a451a4a4.html?pn=50 处得到

Version 2的QR Code如果纠错等级为Q,那么44块总码字中,有22块纠错码字

注意

上上张Version 2的QR Code结构图只是为了说明Version 2的码字都是顺序存放的,但那张结构图并不是所有Version 2的QR Code的通用结构图,它只是纠错等级为M的Version 2 QR Code结构图

我一直容易误认为同一个等级的QR Code的结构图都是一样的,其实不然,相同等级使得总码字数一样,但不同纠错等级导致了对总码字数的分配不同;纠错等级越高,纠错码字占总码字的比率就越高

具体还要查表,不能只看图

我们先将已有的QR Code数据罗列一下:

1
2
3
4
5
6
7
8
9
10
11
00100000  10100010  10111000  00111010
01011001 10011010 10001000 ????????
???????? ???????? ???????? ????????
???????? ???????? ???????? ??00000?
1??????? ???????? ???????? ????????
???????? ??010001 00100100 1???????
???????? ???????? ?????010 11000011
10000000 10101100 00010000 11100100
10101010 10011001 01100110 ????????
???????? ?????0?0 0000000? ????????
???????? ???????? ???????? ????????

QR Code中的每个块表示8 Bits(码字)的数据,也就是1 Byte,而我们只有16 Bytes的数据是完整的

纠错等级为Q的QR Code的最多能够容纳25%的字节损坏,同时,由于我们并不太了解Reed-Solomon算法,其实在知道损坏的字节的位置时,Reed-Solomon算法的纠错能力能够增强至两倍!

Writeup中的原文是:

until you look carefully at Reed-Solomon’s error correcting capabilities and realize that it can correct up to twice as many erasures – that is, if it knows where the errors are, the error correction capabilities are much stronger.

同时参考我们接下来要使用的Python中的一个库reedsolo,在它的Github演示说明中,有下面的举例:

首先它为字符串 hello world 创建了长度为 $12$ 的纠错码,按理说只能容纳6个错误;但是将错误的位置传递进 decode() 后,能够解码出12个错误的字符串,错误容纳程度翻倍!

它的解释是在不指明错误位置的情况下,Reed-Solomon算法会花费“成本”去检测错误位置


从我们上面的数据来看,我们当然知道损坏的字节在哪 —— 所有带 ? 的字节都损坏了;因此这时最多能容纳50%的字节损坏

Version 2的QR Code共有44 Bytes的内容,也就是说允许我们最多丢失22 Bytes;而我们现在只有完整的16 Bytes,超出了范围

庆幸的是,QR Code最前面的数据没有丢失,而最前面的数据包含两个内容:编码模式(Mode)计数器(Count Indicator)

1
2
3
4
5
6
0010 [查表可知,编码模式为字母数字模式(Alphanumeric Mode)]
000010100 [查表并分析,QR Code中的信息长度为20字节]
01010111000 ["FL"]
00111010010 ["AG"]
11001100110 [" I"]
1010001000? ["S?"]

可以前往 https://www.thonky.com/qr-code-tutorial/alphanumeric-mode-encoding 学习QR Code的字母数字模式(Alphanumeric Mode)

上面的分析可知,这张QR Code中共有20个字符,根据Alphanumeric Mode,每两个字符占据11 Bits,因此这20个字符共需要110 Bits;再加上前面4 Bits的编码模式和9 Bits的计数器,总共占据4 + 9 + 110 = 123 Bits

这123 Bits就是这张QR Code的必要信息

我们知道,QR Code中将123 Bits的信息存放后,如果后面还有空位,需要添加 0000 表示结束,然后再添加若干个 0 补全为8的倍数;最后再添加无意义的占位符 11101100 00010001

由于$123 ÷ 8 = 15 ... 3$,因此在第16 Bytes的数据中,前3 Bits是必要数据,然后会紧接一串 0000,最后再添加一个 0 补全为8的倍数;再最后的17 - 22 Byte会是占位符 11101100 00010001

我们查看回我们的D区数据:

1
2
3
4
00100000  10100010  10111000  00111010  01011001  10011010
10001000 ???????? ???????? ???????? ???????? ????????
???????? ???????? ???????? ??00000? 1??????? ????????
???????? ???????? ???????? ??010001

可以看到,第16 Byte的数据前3 Bits是必要数据,之后的确紧跟着一串 0000,表明我们的分析正确,随后添加上填充的 0 和占位符,变成:

1
2
3
4
00100000  10100010  10111000  00111010  01011001  10011010
10001000 ???????? ???????? ???????? ???????? ????????
???????? ???????? ???????? ??000000 11101100 00010001
11101100 00010001 11101100 00010001

恢复了6 Bytes的内容后,我们已知的块数从16增加到了22,刚好是纠错等级为Q的Reed-Solomon算法的极限!


由于不熟悉Reed-Solomon算法,下面借助Python的reedsolo库来进行计算

Python的reedsolo库的安装和使用请参考 https://github.com/tomerfiliba/reedsolomon

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import reedsolo
reedsolo.init_table(0x11d)

qr_bytes = ['00100000', '10100010', '10111000', '00111010', '01011001', '10011010', '10001000', '????????', '????????', '????????', '????????', '????????', '????????', '????????', '????????', '??000000', '11101100', '00010001', '11101100', '00010001', '11101100', '00010001', '00100100', '1???????', '????????', '????????', '?????010', '11000011', '10000000', '10101100', '00010000', '11100100', '10101010', '10011001', '01100110', '????????', '????????', '?????0?0', '00000000', '????????', '????????', '????????', '????????', '????????']

b = bytearray()
erasures = []
for i, bits in enumerate(qr_bytes):
if '?' in bits:
erasures.append(i)
b.append(0)
else:
b.append(int(bits, 2))

mes = reedsolo.rs_correct_msg(b, 22, erase_pos=erasures)
for c in mes[0]:
print("{08b}".format(c))

首行的 reedsolo.init_table(0x11d) 是旨在初始化预计算表,至于为什么传入值 0x11d,不清楚...

代码中,我们首先将我们手动恢复自完整22 Bytes的数据存放在列表 qr_bytes 中,列表中的元素都是长度为8的字符串

然后对列表进行遍历,如果元素中有 ?,表示它是丢失的,将它的位置存放入列表 erasures 中,然后向bytearray类型的 b 列表中添加 0,表示缺失(也可以添加其它数表示,无关紧要,因为已经在 erasures 中标识了);如果元素中没有 ?,表示它是完整的,直接将这个元素从二进制转换成十进制数,添加进bytearray

十进制数值添加进bytearray,会自动转换成bytes类型数据

最后,我们拥有了装载原先 qr_bytes 数据的 b 列表,只是它是bytearray类型的;还拥有了丢失字节的位置 erasures

直接将这些信息传入函数 rs_correct_msg,其中指定了要处理的信息 b,纠错码的字节数 $22$、丢失的字节的位置 erasures;得到 mes

变量 mes 的是一个列表,它是Reed-Solomon算法对传入的信息 b 进行恢复的结果;mes[0] 是Reed-Solomon计算出的原始信息(类似QR Code中的D区),而 mes[1] 则是Reed-Solomon计算出的纠错信息(类似QR Code中的E区):

1
2
mes
# (bytearray(b' \xa2\xb8:Y\x9a\x88/\x86\xe2\xb6\x99J\xc3\x15\x00\xec\x11\xec\x11\xec\x11'), bytearray(b'$\xca\xfcq\xa2\xc3\x80\xac\x10\xe4\xaa\x99f:d:\x00\xe2~\xeb\xdc\x0e'), [7, 8, 9, 10, 11, 12, 13, 14, 15, 23, 24, 25, 26, 35, 36, 37, 39, 40, 41, 42, 43])

mes[2] 则是之前传入的 erasures,表示丢失字节的位置

也就是说,我们成功恢复了数据,整个数据中,原始数据部分在 mes[0],纠错码数据在 mes[1];随后我们将 mes[0] 中的数值都转换成8 Bits二进制数,打印输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
00100000
10100010
10111000
00111010
01011001
10011010
10001000
00101111
10000110
11100010
10110110
10011001
01001010
11000011
00010101
00000000
11101100
00010001
11101100
00010001
11101100
00010001

上面便是这张QR Code中D区的数据;对它进行分析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
0010 [查表可知,编码模式为字母数字模式(Alphanumeric Mode)]
000010100 [查表并分析,QR Code中的信息长度为20字节]
01010111000 ["FL"]
00111010010 ["AG"]
11001100110 [" I"]
10100010000 ["S "]
01011111000 ["G+"]
01101110001 ["JQ"]
01011011010 ["GA"]
01100101001 ["H:"]
01011000011 ["FW"]
00010101000 ["3X"]
0000 [结束符]
0 [向8的整数倍填充]
11101100 00010001 [填充字节]
11101100 00010001
11101100 00010001

最终得到QR Code中的信息:FLAG IS G+JQGAH:FW3X


此外,XMAN选拔赛中也有类似的题目:

很明显就是之前的解题步骤,脚本可套用


4 SECCON 2014

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

前往 https://merricx.github.io/qrazybox/,将残缺的二维码填涂上(注意别忘了填涂灰色):

依次点击右上方的ToolsReed-Solomon DecoderDecode,得到结果:


失败记录

这道题目的Writeup是手撕Reed-Solomon算法的,但是我不了解算法、也不想借助QrazyBox这个工具,而是用Python的reedsolo库解决,前面的SECCON 2013已经有成果了

首先这张QR Code的必要信息是:纠错等级H,也就是说有30%的纠错能力;Version 3的QR Code共有70个块,而纠错等级为H则意味着其中有26个数据块、44个纠错码块

QR Code只剩左边的纠错信息,而读取它的信息并不困难,得到:

1
2
3
4
5
6
7
8
9
'????????', '????????', '????????', '????????', '????????', '????????', '????????', '????????', 
'????????', '????????', '????????', '????????', '????????', '????????', '????????', '????????',
'????????', '????????', '????????', '????????', '????????', '????????', '????????', '????????',
'????????', '????????', '01011010', '01011111', '00110101', '10101111', '10110101', '10001111',
'00100011', '00110100', '01100100', '00110100', '10101101', '00100010', '10011011', '10011111',
'01000011', '00001111', '01110000', '10110110', '01100100', '11111011', '10111111', '00000111',
'11001100', '11001001', '01110101', '10111111', '11100110', '11100011', '11100001', '01011110',
'10000000', '11010001', '01100011', '00001100', '00101011', '01000101', '10100010', '10111101',
'00000101', '01101001', '01100001', '00111110', '10100111', '11110100'

前面的26个数据块全部丢失,所以全用 ???????? 替代

然后按照之前的脚本,执行代码:

1
mes = reedsolo.rs_correct_msg(b, 44, erase_pos=erasures)

始终出现 reedsolo.ReedSolomonError: Too many (or few) errors found by Chien Search for the errata locator polynomial! 的错误

翻看Writeup,发现竟然有“猜”这一步骤:(原文是日文,所以记录的可能不准确)

  • 假设开头的 SECCON 是字母数字模式,之后的 {...} 是8 Bits字节模式;也就是说,它采用QR Code中的混合模式

  • 混合模式中,第一个模式可以根据 SECCON 直接猜测,得到前面块的内容:

    1
    2
    3
    4
    5
    0010[假设"SECCON"是字母数字模式,所以标识码为0010]
    000000110[这里的Count Indicator就是6]
    10011111010["SE" = 45 × 28 + 14 = 1274,转二进制]
    01000101000["CC" = 45 × 12 + 12 = 552,转二进制]
    10001001111["ON" = 45 × 24 + 23 = 1103,转二进制]
  • 混合模式中,第二个模式它说是 {...},其中 ... 是长度为16的字符串

    我实在不知道 $16$ 是怎么知道的,可能是原题给出了

    继续推测:

    1
    2
    3
    0010[8 Bits字节模式的标识码]
    00010010[十进制数18的二进制表示,表示"{...}"中的省略号有16个字符]
    01111011[字符"{"ASCII码为123,转二进制]

    最后根据计算,前面的字母数字模式占用46 Bits,而8 Bits字节模式中,按理说会占用4 + 8 + 8 × 18 = 156 Bits,所以主要的数据会占用46 + 156 = 202 Bits;再者,这张纠错等级为H的Version 3 QR Code能够容纳26 × 8 = 208 Bits的数据,所以最后的208 - 202 = 6 Bits会是无意义的填充

    又因为flag最后以 } 结尾,而 } = 125 = 01111101,所以有:

    1
    2
    ??011111[第25个D区数据块]
    01000000[第26个D区数据块]

原先我们的D区数据全是 ????????,现在一通猛如虎的分析下来,变成了:

1
2
3
4
'00100000', '00110100', '11111010', '01000101', '00010001', '00111101', '00000100', '10011110', 
'11??????', '????????', '????????', '????????', '????????', '????????', '????????', '????????',
'????????', '????????', '????????', '????????', '????????', '????????', '????????', '????????',
'??011111', '01000000'

哪怕经过这样的工作,在执行代码时还是会出现 reedsolo.ReedSolomonError: Too many (or few) errors found by Chien Search for the errata locator polynomial! 错误

也花了很多时间在这题上,所以失败了也记录下来,也该结束QR Code的学习了

按理说一定是可以解的,但是代码仍错误;并且这种“猜”的思路有可能是错的,因为把QR Code扔QrazyBox上能直接解码Reed-Solomon,QrazyBox可不会猜测内容是 SECCON{...}

艰难,惨


01字符串

QR Code由黑白两色的码元组成,因此可以分别代表0和1;所以一张QR Code有时候也被转换成01字符串

链接: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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from PIL import Image

str = "111111100010..."
pic = Image.new("RGB", (250,250))
Black = Image.new("L", (10, 10), 255)
White = Image.new("L", (10, 10), 0)

i = 0
for y in range(25):
for x in range(25):
if str[i] == '1':
pic.paste(White, (10*x, 10*y))
else:
pic.paste(Black, (10*x, 10*y))
i += 1
pic.show()

自动扫描

有时候,直接用手机扫描二维码可能会有安全隐患;而Python的第三方库pyzbar支持直接读取以图片形式呈现的QR Code

pyzbar

安装直接就是:

1
pip install pyzbar

但是它需要另一个库的协助:PIL或者pillow,借助其中的 Image 对象


常规使用方法是,假设我们有一张QR Code的图片,名为 examine_qr.png

想要获得其中的内容,代码为:

1
2
3
4
5
6
7
8
9
10
import pyzbar.pyzbar as pyzbar
from PIL import Image

img = Image.open("examine_qr.png")
barcodes = pyzbar.decode(img)

for barcode in barcodes:
barcodeData = barcode.data.decode('utf-8')
print(barcodeData)
# examine

我们主要使用的是pyzbar库中的 decode() 函数,它需要接收一个 Image 对象,然后读取解码其中的条形码

如果是QR Code,那么调用 pyzbar.decode() 函数将会得到一个列表(list),其中的元素都是 pyzbar.pyzbar.Decoded 对象

因为一张图片中有可能包含多张QR Code,所以用list承接;该list中会依次存放每张QR Code的数据

获得的 pyzbar.pyzbar.Decoded 对象通常有以下属性:

  • data

    就是该二维码的内容

    上面代码中,遍历每一张二维码,然后获得它的 data 字段;data 字段的内容都是Bytes类型的,因此需要解码

  • type

    如果扫描的是QR Code,那么 type 字段的值就是 QRCODE

    由于我们现在主攻QR Code,因此暂时不管其它二维码

  • rect

    从图片最左上角的像素开始建系,rect 字段的值是一个 Rect 对象,该对象分别用 lefttopwidthheight 4个属性值来描绘QR Code在这张图片中的位置

    lefttop 分别表示QR Code的最左上角的像素离原点的距离、weightheight 表示整张QR Code的宽度和高度(单位都是像素)

  • polygon

    该字段的意思是"多边形",它的值是一个list,其中存储着QR Code 4个角的坐标,表现形式为:polypgon = [Point(x=8, y=10), Point(x=8, y=325)]

我们最主要的用法就是 print(Decoded.data.decode('utf-8'))


此外,当QR Code不清晰时,能够通过图像处理来增强识别效果;主要依靠PIL库:

1
2
3
4
5
6
7
8
from PIL import Image, ImageEnhance

img = Image.open("examine_qr.png")
# img = ImageEnhance.Brightness(img).enhance(2.0) #增加亮度
# img = ImageEnhance.Sharpness(img).enhance(17.0) #锐利化
# img = ImageEnhance.Contrast(img).enhance(4.0) #增加对比度
# img = img.convert('L') #灰度化
img.show()

参考文章:https://www.cnblogs.com/xushengming/p/9872061.html

而QR Code由于定位图案的存在,定位效果是非常好的,哪怕倾斜的QR Code也能读取

CTF题目中可能给出大量的QR Code图,这时通过脚本读取能大幅加快速度


码元替换

普通的QR Code的码元由黑白两色组成,在CTF中,有时候会将这两种码元分别用两种图片替代,我们需要识别出来,并转换成QR Code

参考DASCTF 5月赛 & BJDCTF 3rd的Misc题目「/bin/cat 2」

链接:https://pan.baidu.com/s/1nwOATM1T6YLNws6WOXDkUw
提取码:79z5

下载得到 cat.gif

模糊上看,这的确是一张QR Code

将上图转换成可扫描的QR Code,主要有两种方法:

图像识别

首先数一数,宽有58张小图、高有29张小图;而 cat.gif 的分辨率是2900×1450,因此每张小图的分辨率为50×50

QR Code都是正方形矩阵,但是 cat.gif 的宽度是高度的两倍,因此可以知道图片的宽度被放大了两倍,应该缩短;编写代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from PIL import Image

img = Image.open("cat.gif")
img_1 = img.crop((0, 0, 50, 50))
img_2 = img.crop((100+0, 100+0, 100+50, 100+50))

width, height = img_1.size
dif = []
for y in range(height):
for x in range(width):
if img_1.getpixel((x, y)) != img_2.getpixel((x, y)):
dif.append((x, y))
mark = dif[0]

data = ""
for y in range(0, img.size[1], 50):
for x in range(0, img.size[0], 100):
if img.getpixel((x+mark[0], y+mark[1])) == img_1.getpixel(mark):
data += "1"
else:
data += "0"

pic = Image.new("RGB", (290,290))
Black = Image.new("L", (10, 10), 255)
White = Image.new("L", (10, 10), 0)

i = 0
for y in range(29):
for x in range(29):
if data[i] == '1':
pic.paste(White, (10*x, 10*y))
else:
pic.paste(Black, (10*x, 10*y))
i += 1
pic.show()

代码中,首先导入 cat.gifimg 对象(由于Python无法处理动态图,所以这时的 img 是Gif动图的第一帧)

然后使用 Imagecrop() 裁剪函数,该函数接收一个tuple,分别是 (左上角横坐标, 左上角纵坐标, 右上角横坐标, 右上角纵坐标);随便选定两个位置进行裁剪,其中 img_1 是:

img_2 则是:

随后一个二重循环,遍历两种小图的每个像素,将它们像素值不同的位置存放入数组 dif 中;dif 中的每个元素都可以作为判断是哪种小图的依据

随便取 mark = dif[0],然后对 cat.gif 进行遍历,由于 cat.gif 的宽度是高度的两倍,所以纵向遍历的步长是50,而横向遍历的步长是100;比较 cat.gif 中每个小图的第 mark 个像素是否与 img_1 的相同,相同则在 data 中添加 1、不同则添加 0

有了 data 后,题目转换成前面的01字符串类型,套用代码将QR Code绘制出来即可;最终得到:

再套上pyzbar的脚本自动读取也可以


图像处理

另外一种方法,img_1img_2 虽然看上去相似,但可能在某个颜色通道上的数值有较大的差异

cat.gif 截图保存为 cat.png,然后扔进StegSolve,浏览各个通道发现,在R通道2上,图像显示为:

直接扫描即可

支付宝扫码能力更强,站远一点可以扫

如果不能扫描,可以进行下一步的处理,如提升对比度等


end