夜间模式暗黑模式
字体
阴影
滤镜
圆角
【MiniLCTF 2020】浅析Bilibili的BV号算法

因为要给miniLCTF出题,正好趁机沉下心来研究一下B站的BV号是怎么一回事。顺便把这篇文章当做BilibiliDV题目的官方wp。在看这篇文章之前还是非常建议读者参考知乎的高赞回答。个人感觉在刚公布BV号的事实一天之后就写出了转换脚本,还是挺厉害的!这也是我出题的动机。

参考链接:

如何看待 2020 年 3 月 23 日哔哩哔哩将稿件的「av 号」变更为「BV 号」?- mcfx的回答

题目给的样本文件有一点大,为了方便一点,我就直接给出样本文件的生成脚本,可以自己跑一遍来生成一下:

baseTable = 'd59nD71EcAt38aT24eCN06'
baseArray = {}
for i in range(22):
    baseArray[baseTable[i]] = i

xor = 50790
inc = 114514

startNum = 1000000
endNum = 4000000

dvStaticStr = 'DV t ACD Ne  '
dynIndex = [12, 11, 8, 4, 2]

def encrypt(x):
    x = (x ^ xor) + inc
    dvNum = list(dvStaticStr)
    for i in range(5):
        dvNum[dynIndex[i]] = baseTable[x // 22 ** i % 22]
    return ''.join(dvNum)

def decrypt(x):
    r = 0
    for i in range(5):
        r += baseArray[x[dynIndex[i]]] * 22 ** i
    return (r - inc) ^ xor

file = open('av1000000To3999999.txt', 'w')
for num in range(startNum, endNum):
    file.write('av'+str(num)+' - '+encrypt(num)+'\n')

提前看到生成脚本的编码逻辑其实也没啥关系,这题重要的地方在于怎么去把这个逻辑给找出来,这是最关键的。

0x01 准备工作

一开始的工作是“观察”,找一些表面规律。一般来说,这个阶段应该找到这些事实:

  • 算上开头的DV标识,DV号总长度是13个字符,固定不变。
  • 某些固定位上的字符固定不变,动态位用X表示出来就是这样的:DVXtXACDXNeXX

其实你把固定位上的字符拿出来看一下,是个有意义的一串字符:tACDNe。这样子可能看不出来,倒过来试试:eNDCAt。是不是发现了什么!在之后的工作中其实也有很多这样“有意思的地方”。

其实再观察的仔细一点你会发现,av号每增加一位的时候,对应dv号其实不是那种“翻天覆地”的变化,我把它亲切的称呼为“类似进位的变化规律”:

应当想到这可能是一种单表替换的编码方式,而且这个单表的顺序看起来也被打乱了。而且某些dv号在av递增时改变的位数不止一位,这样的变化情况也不是“等间距”发生的事件,事情慢慢变得麻烦起来了。这个阶段我觉得应该发现的事实有:

  • 可能是数值转换为某种形式后进行了列表替换
  • 随着av号的递增,dv号的改变是从最末位的变化位开始变化,随后往更高位变化

0x02 base?

其实在比赛的过程中我发现已经很少有人能够做到这步了。对于替换表这样的编码方式,频率分析其实是非常重要的一个方法。我们针对样本的最后一位进行分析,并给出分析脚本:

file = open('av1000000To3999999.txt', 'r')
charDict = {}


while True:
    line = file.readline()
    if not line:
        break
    endChar = line[-2]
    if endChar in charDict:
        charDict[endChar] = charDict[endChar] + 1
    else:
        charDict[endChar] = 1

print(charDict)

# result:
# {'8': 136363, 'a': 136363, 't': 136363, '3': 136363,
#  'c': 136363, 'A': 136363, '1': 136363, 'E': 136363,
#  '0': 136365, '6': 136365, 'C': 136366, 'N': 136366,
#  '4': 136364, 'e': 136364, 'T': 136363, '2': 136363,
#  'D': 136363, '7': 136363, '9': 136363, 'n': 136363,
#  'd': 136364, '5': 136364 }
# 从这里我们可以确定 采用了类似 base22 的编码

针对末位变化位来说,你会发现得到字符的范围就在22个字符里面并且样本频率几乎一致。到这里我认为可以实锤了,映射表就是由这22个字符组合而成的。其实这里我也放了一个彩蛋,首先把所有的数字按顺序全部挑出来:8310642795,从0到9都有出现,然后分别把大写字母和小写字母拿出来:atcend/AECNTD,这样可能看不出来,但是调换一下顺序就发现了:endcat/ENDCAT。(嘿嘿)

话说回来,可以实锤这是个类似“base22”的编码方式,最直接的一个原因就是所有的变化位都逃不出22个字符的范围(建议试一下其他的变化位,上面我只尝试了最后一位,因为从最后一位能够很容易找到一个轮换表中的所有字符,对于更高位其实可能会有缺失的现象)。在知道这个情报之后,接下去就可以参照知乎高赞回答的做法:

首先随便找一个av号,比如我找av1114514,它对应的dv号是DV7ttACDDNe7c。然后我去找每个动态位上出现的22种不同情况下av-dv映射:

# 钦定一个av号 得到对应dv号
# av1114514 - DV7ttACDDNe7c
# 找到每个动态位上 22个为一组的集合们

source = open('av1000000To3999999.txt', 'r')
result = open('avFilter2.txt','w')

dynIndex = [0, 2, 6, 9, 10]


def diff(str1, str2, index):
    for i in range(len(str1)):
        if i == index:
            continue
        elif str1[i] == str2[i]:
            continue
        else:
            return False
    return True


for i in range(5):
    result.write('Difference in dvStr[' + str(dynIndex[i]) + ']\n')

    while True:
        line = source.readline()
        if not line:
            source.seek(0)
            break

        avNum = int(line[2:9])
        dvStr = line[14:-1]
        if diff('7ttACDDNe7c', dvStr, dynIndex[i]):
            result.write(str(avNum) + ' - ' + dvStr + '\n')

得到的结果文件是这样的(以倒数第二位dv号为例):

Difference in dvStr[9]
1114514 - 7ttACDDNe7c
1114542 - 7ttACDDNenc
1114552 - 7ttACDDNeDc
1114580 - 7ttACDDNe9c
1114592 - 7ttACDDNedc
1114618 - 7ttACDDNe5c
1117700 - 7ttACDDNetc
1117726 - 7ttACDDNe3c
1117738 - 7ttACDDNeAc
1117766 - 7ttACDDNeEc
1117776 - 7ttACDDNecc
1117804 - 7ttACDDNe1c
1117824 - 7ttACDDNe4c
1117850 - 7ttACDDNeec
1117878 - 7ttACDDNe2c
1117890 - 7ttACDDNeac
1117916 - 7ttACDDNeTc
1117928 - 7ttACDDNe8c
1118002 - 7ttACDDNe6c
1118030 - 7ttACDDNeNc
1118040 - 7ttACDDNe0c
1118068 - 7ttACDDNeCc

本来期望的结果应该是:av号每增加22^n,对应动态位上会发生改变,从我们的筛选结果来看并不是这样的。从原来的破解av转bv的算法中也了解到,异或运算是一个比较难想到的点,在比赛过程中也给出了hint(但是我在看知乎的时候发现算法作者貌似是直接猜测异或了一个大数,虽然后面补充了奇偶性判断的验证方法,但我感觉还是有丶丶经验的成分在里面):

0x03 Xor

这一步在比赛的过程中也死了很多人,听说还把电脑跑炸了?!我觉得很大一部分原因是没有注意到一个细节:

$dvString = Base22[(avNum \oplus Xor)+inc]$

上面是题目的核心算法,有些人直接枚举xor,因为我还另外设置了一个小偏移inc,你在验证的时候一定会出问题,然后就导致了跑到一个很大的xor数也得不到结果的情况。事实上在出题的时候我特意凑到了一个较小的异或值来节省你们的爆破时间的……我在做我自己的题的时候,设计了一个比较取巧的方法:

首先要明确一个事实,因为我的目标是要找到xor值,以及可能存在的偏移inc(事实上我现在是不知道有没有偏移的,但是解题的时候要认定它的存在),异或值要满足全体样本,必然也满足部分样本:

# 可能经过异或运算(因为DV号末尾相同时 av号奇偶性相同 二进制特性)
# 猜测 xor = 2^22 * a + b (0 <= b < 2^22)
# 实际上 xor 与 (2^22 * a) mod 22 和 b 有关
# 但是我限定了 1000000 到 3999999 < 2^22 的av号 只需考虑b的取值就行
source = open('av1000000To3999999.txt', 'r')
result = open('validate1.txt', 'w')  # change the file number


def search(num):
    offset = (num - 1000000) * 27
    source.seek(offset)
    line = source.readline()
    dv = line[14:]
    return dv


# len(str1) == len(str2)
def diff(str1, str2):
    count = 0
    length = len(str1)
    for i in range(length):
        if str1[i] != str2[i]:
            count = count + 1

    return count

dynIndex = [-3, -6, -10, -12]
k = 1  # change the dynamic index
for xor in range(1, 100000):  # 限定在这个范围就行
    charDict = {}
    flag = True
    avNum = 2116543  # change it
    for a in range(22):
        newNum = (avNum + a * (22 ** k)) ^ xor
        newNum2 = (avNum + (a + 1) * (22 ** k)) ^ xor
        # print(str(newNum) + ' - ' + str(xor) + ' - ' + str(a))
        endChar = search(newNum)[dynIndex[k - 1]]
        if endChar in charDict:
            flag = False
            break
        else:
            charDict[endChar] = 1
    if flag:
        result.write(str(xor)+'\n')


# 通过这样的算法筛选 我最终得到了8个满足条件的异或数
# 50784
# 50785
# 50786
# 50787
# 50788
# 50789
# 50790 (这个是正确的 现在还不知道)
# 50791

在全部样本中我随便取一个av值,根据对应的动态位,每次改变(增加)相应的22的n次方后进行异或,得到对应的dv,循环22次,记录动态位的字符。检查对应的动态位字符字典是否出现了相同的字符,如果出现了就说明这不是我想要的xor,因为正确的xor一定满足动态位字符字典不会出现重复的情况。

当然一次遍历之后会出现很多符合要求的异或值,我只要改变av号和对应动态位下标,重复几次就可以得到有限个合适的异或值。

0x04 轮换表和偏移

得到了有限个可能正确的异或数后,接下来看一下有没有偏移的存在。还记得之前得到的一组每个动态位上出现的22种不同情况下av-dv映射数据吗?这里就可以用得上了:

baseTable = ['d', '5', '9', 'n', 'D',
             '7', '1', 'E', 'c', 'A',
             't', '3', '8', 'a', 'T',
             '2', '4', 'e', 'C', 'N',
             '0', '6']

baseDict = {'d': 0, '5': 1, '9': 2, 'n': 3, 'D': 4,
            '7': 5, '1': 6, 'E': 7, 'c': 8, 'A': 9,
            't': 10, '3': 11, '8': 12, 'a': 13, 'T': 14,
            '2': 15, '4': 16, 'e': 17, 'C': 18, 'N': 19,
            '0': 20, '6': 21}

avDict = {'DV7ttACDDNe7c': 1114514, 'DV7ttACDDNenc': 1114542,
          'DV7ttACDDNeDc': 1114552, 'DV7ttACDDNe9c': 1114580,
          'DV7ttACDDNedc': 1114592, 'DV7ttACDDNe5c': 1114618,
          'DV7ttACDDNetc': 1117700, 'DV7ttACDDNe3c': 1117726,
          'DV7ttACDDNeAc': 1117738, 'DV7ttACDDNeEc': 1117766,
          'DV7ttACDDNecc': 1117776, 'DV7ttACDDNe1c': 1117804,
          'DV7ttACDDNe4c': 1117824, 'DV7ttACDDNeec': 1117850,
          'DV7ttACDDNe2c': 1117878, 'DV7ttACDDNeac': 1117890,
          'DV7ttACDDNeTc': 1117916, 'DV7ttACDDNe8c': 1117928,
          'DV7ttACDDNe6c': 1118002, 'DV7ttACDDNeNc': 1118030,
          'DV7ttACDDNe0c': 1118040, 'DV7ttACDDNeCc': 1118068}

# xor 50790
avXorDict1 = {'DV7ttACDDNe7c': 1165300, 'DV7ttACDDNenc': 1165256,
              'DV7ttACDDNeDc': 1165278, 'DV7ttACDDNe9c': 1165234,
              'DV7ttACDDNedc': 1165190, 'DV7ttACDDNe5c': 1165212,
              'DV7ttACDDNetc': 1165410, 'DV7ttACDDNe3c': 1165432,
              'DV7ttACDDNeAc': 1165388, 'DV7ttACDDNeEc': 1165344,
              'DV7ttACDDNecc': 1165366, 'DV7ttACDDNe1c': 1165322,
              'DV7ttACDDNe4c': 1165542, 'DV7ttACDDNeec': 1165564,
              'DV7ttACDDNe2c': 1165520, 'DV7ttACDDNeac': 1165476,
              'DV7ttACDDNeTc': 1165498, 'DV7ttACDDNe8c': 1165454,
              'DV7ttACDDNe6c': 1165652, 'DV7ttACDDNeNc': 1165608,
              'DV7ttACDDNe0c': 1165630, 'DV7ttACDDNeCc': 1165586}
# base22Parsed (相差114514)
# 'DV7ttACDDNe7c': 1279814, 'DV7ttACDDNenc': 1279770,
# 'DV7ttACDDNeDc': 1279792, 'DV7ttACDDNe9c': 1279748,
# 'DV7ttACDDNedc': 1279704, 'DV7ttACDDNe5c': 1279726,
# 'DV7ttACDDNetc': 1279924, 'DV7ttACDDNe3c': 1279946,
# 'DV7ttACDDNeAc': 1279902, 'DV7ttACDDNeEc': 1279858,
# 'DV7ttACDDNecc': 1279880, 'DV7ttACDDNe1c': 1279836,
# 'DV7ttACDDNe4c': 1280056, 'DV7ttACDDNeec': 1280078,
# 'DV7ttACDDNe2c': 1280034, 'DV7ttACDDNeac': 1279990,
# 'DV7ttACDDNeTc': 1280012, 'DV7ttACDDNe8c': 1279968,
# 'DV7ttACDDNe6c': 1280166, 'DV7ttACDDNeNc': 1280122,
# 'DV7ttACDDNe0c': 1280144, 'DV7ttACDDNeCc': 1280100

# xor 50791 (这个和base22Parsed 相差114513)
avXorDict2 = {'DV7ttACDDNe7c': 1165301, 'DV7ttACDDNenc': 1165257,
              'DV7ttACDDNeDc': 1165279, 'DV7ttACDDNe9c': 1165235,
              'DV7ttACDDNedc': 1165191, 'DV7ttACDDNe5c': 1165213,
              'DV7ttACDDNetc': 1165411, 'DV7ttACDDNe3c': 1165433,
              'DV7ttACDDNeAc': 1165389, 'DV7ttACDDNeEc': 1165345,
              'DV7ttACDDNecc': 1165367, 'DV7ttACDDNe1c': 1165323,
              'DV7ttACDDNe4c': 1165543, 'DV7ttACDDNeec': 1165565,
              'DV7ttACDDNe2c': 1165521, 'DV7ttACDDNeac': 1165477,
              'DV7ttACDDNeTc': 1165499, 'DV7ttACDDNe8c': 1165455,
              'DV7ttACDDNe6c': 1165653, 'DV7ttACDDNeNc': 1165609,
              'DV7ttACDDNe0c': 1165631, 'DV7ttACDDNeCc': 1165587}


xor = 50791
# DV number static string
dvStaticStr = 'DV t ACD Ne  '

dynIndex = [12, 11, 8, 4, 2]


def encrypt(x):
    x = x ^ xor
    dvNum = list(dvStaticStr)
    for i in range(5):
        dvNum[dynIndex[i]] = baseTable[x // 22 ** i % 22]
    return ''.join(dvNum)


def base22Parser(x):
    r = 0
    for i in range(5):
        r += baseDict[x[dynIndex[i]]] * 22 ** i
    return r


for key in avDict:
    avDict[key] = base22Parser(key)

print(avDict)
avList = [1114514, 1114542, 1114552, 1114580, 1114592,
          1114618, 1117700, 1117726, 1117738, 1117766,
          1117776, 1117804, 1117824, 1117850, 1117878,
          1117890, 1117916, 1117928, 1118002, 1118030,
          1118040, 1118068]
avDict = {'7': 1114514, 'n': 1114542, 'D': 1114552, '9': 1114580,
          'd': 1114592, '5': 1114618, 't': 1117700, '3': 1117726,
          'A': 1117738, 'E': 1117766, 'c': 1117776, '1': 1117804,
          '4': 1117824, 'e': 1117850, '2': 1117878, 'a': 1117890,
          'T': 1117916, '8': 1117928, '6': 1118002, 'N': 1118030,
          '0': 1118040, 'C': 1118068}

xor = 50790  # change it
# xorList = []
# for num in avList:
#     xorList.append(num ^ xor)
#
# print(sorted(xorList))

avXorDict = {}
for ch in avDict:
    avXorDict[ch] = avDict[ch] ^ xor

print(avXorDict.items())
baseList = sorted(avXorDict.items(), key=lambda x: x[1])

baseTable = []
for item in baseList:
    baseTable.append(item[0])

# baseTable 对于两个数得出的结果都是一样的
# ['d', '5', '9', 'n', 'D',
#  '7', '1', 'E', 'c', 'A',
#  't', '3', '8', 'a', 'T',
#  '2', '4', 'e', 'C', 'N',
#  '0', '6' ]
print('baseTable:')
print(baseTable)

# 经过验证后可以发现满足的异或数为 50790 和 50791

实际上只要把av号们异或一下,排序后根据对应的动态位得到轮换表。知道轮换表之后,把异或后的av号和转换dv后的到的数字比较,应该是一个恒偏移。

这些都知道了以后,题目就算解完了。

0x05 后续

虽然出这道题也是奔着搞你们心态去的,但最后还是有很厉害的学弟做出来了。其实在最近这段时间诸如长时间被一个问题困住的情况挺常见,在以后研究工作中也会是家常便饭。但是一直去发现问题解决问题最后都能得到一个满意的结果。

题目一点都不难,都是大家看得懂的内容。主要是能不能坚持下去/吃得消做,我从零开始自己还原解题思路也花了好几个小时,出题凑数据也花了几天。而且题目取材是来自现实生活,我觉得很有意义,希望大家别用一种做题目的心态去看它。

暂无评论

发送评论 编辑评论


				
上一篇
下一篇