小谈CSS加密和LFSR

September 14, 2014 | 08:23 密码学

今天在学习Cryptography I的课程时,了解到一种叫Content Scramble System(CSS)的加密技术,以及相关的LFSR(Linear Feedback Shift Rigister)机制,当时看视频时一头雾水,经过一个下午的找资料、研究,总算稍微弄明白一些,在此简单做个笔记。

概述

CSS是一种流加密技术,主要用于早期的DVD加密。由于美国政府的种种规定,用于DVD的CSS的密钥长度被限制为40bit,这也为之后被破解埋下祸根。

线性反馈移位寄存器

在介绍CSS的原理之前,让我们先来看一下这个叫线性反馈移位寄存器(LFSR)的东西。所谓LFSR,首先是个寄存器,其次它还是一个移位器,每个时钟周期会向输出端移动一位。然后“反馈”是什么意思呢?就是每个时钟周期内,各个位置上的状态,会决定下一时刻的输入。最后,整个系统是线性的,这便十分利于它应用到加密等领域。

啰嗦了一段话,直接上电路图吧!

LFSR电路图

上面是Wikipedia上给出的逻辑电路。首先这是一个16位的LFSR,左边是输入,右边是输出。我们前面提到,各个位上的状态,会决定下一时刻的输入,到底是怎么样一个决定法呢?具体来说,LFSR会将某些“特定位置”上的状态,进行异或操作,然后作为下一时刻的输入。而这些“特定位置”,我们称为tap。如图,可以看到,第11、13、14、16位上的当前状态进行了异或,得到结果0,作为下一时刻的输入。

这里是一个动态图。

LFSR动态图

上述的tap,我们可以用一个多项式来表示,称为反馈多项式

$$x^{16} + x^{14} + x^{13} + x^{11} + 1$$

最后一个1跟tap无关,你可以把它想成是\(x^0\)。

对于LFSR,我们发现它必然会形成一种循环。试想,对于一个8位的LFSR,最多也就有2的8次方种状态,这其中还要舍弃全0的情况,也就是最多有255种状态。那可不可能把这255种状态都循环一遍呢,这是可能的。如下,我们利用一个简单的小程序,看看哪些情况下,LFSR会遍历所有的255种可能:

start_state = 0x80
lfsr = start_state
width = 8
tap = 0
num = 0
max = 2**width - 1
while tap < max:
    bit = 0
    count = 0
    tap += 1
    for x in xrange(max):
        n = width - 1
        bit = 0
        while n >= 0:
            bit = ((tap >> n) & (lfsr >> ((width-1)-n)) ) ^ bit
            n -= 1
        bit = bit & 1
        lfsr =  (lfsr >> 1) | (bit << (width-1) )
        count += 1
        if lfsr == start_state:
            break
    if lfsr == start_state and count == max:
        num += 1
        print hex(tap),
print '\ntotal num: %d' % num

代码中有这样一个判断if lfsr == start_state and count == max,这边我的设想是,由于在某些情况下,LFSR会陷入一个小循环中,如以6个时钟周期为单位的循环,而对于这样的小循环,我的程序在for循环中并不能及时发现并跳出,因此就在此处多加上一个判断条件过滤掉这种情况。

得到的结果如下:

0x8e 0x95 0x96 0xa6 0xaf 0xb1 0xb2 0xb4 0xb8 0xc3 0xc6 0xd4 0xe1 0xe7 0xf3 0xfa

total num: 16

可以看到,这一结果与CMU上一份表格给出的一致。也可以用别的长度的LFSR来进行验证。

后面,Wikipedia上又给出进一步说明,指出对于一个LFSR来说,要想达到最大循环,一个必要条件是,反馈多项式必须是本原多项式,即各项的次数的集合互素(注意是整体不是某两个),关于这里就不展开讨论了。

CSS加密原理

介绍完线性反馈移位寄存器之后,我们回到CSS加密上。在CSS加密中,40位的密钥,被分成两段,分别长16位和24位,亦即2字节和3字节。然后,它们被分别放入一个17位和25位的LFSR中,作为tap。这里你可能要问,这两个LFSR怎么会各多出来一位呢?原因是,为了避免出现tap全为0的情况,我们会给每个LFSR初始设置一位,并用1填充。具体地,对于左边输入右边输出的LFSR来说,我们会在将密钥片段放入LFSR中后,在每个LFSR的从右往左数第4位后面,加上一位并设初值1,至此形成17和25位的两个LFSR,并保证tap不可能为全0。

这张幻灯片很好的说明了这一问题。

LFSR-17

然后继续说到我们的加密过程,LFSR每移动8位为一个周期,一个周期内,每个LFSR都会输出1个字节。然后我们会把这两个结果相加,并与上一周期的进位做逻辑运算(具体过程待考),同时舍弃进位供下一周期的使用,然后将这个字节与明文做异或运算,从而得到密文。如此循环下去,直到所有明文都被进行了加密。这就是CSS加密技术在DVD加密中的基本应用。

LFSR加密过程

缺陷

正如前文所述,40位的密钥长度,给了CSS加密太多被破解的可能。更加严重的是,如果我们恰巧知道明文的前6位(如我们知道明文是某种特定格式),那么我们甚至只需进行\(2^{16}\)尝试就可以将其破解。

大致的做法如下:

  • 假设一个LFSR-17的初值
  • 利用这一初值,输出4字节
  • 使用密文中该位置上的4字节,减去这4字节(这里有个迭代,关于进位等),得到LFSR-25的输出
  • 用LFSR-25的这4字节的输出,来判断其状态
  • 再使用各LFSR跑两字节,进行验证,如果不对,再对LFSR-17进行下一个假设

小结

关于CSS的中文资料,我找到的不多,因此我就通过学习研究,对CSS加密技术和LFSR进行了一些简单介绍,希望能给大家一些帮助。可能有些地方有错误或者不够准确,欢迎批评斧正。

目前,CSS加密也逐渐为更高级、密钥长度更大的加密技术所替代,然而,由于其硬件友好的特性(CSS的设计十分便于硬件实现),仍然会有存在于遗留系统中。

参考资料

Creative Commons BY-NC-ND 3.0