斯坦福大学密码学公开课——Stream Cipher (2)

Attacks on OTP & Stream ciphers

按以往一样，首先拍出上一章节的回顾

Review

1. Attack 1: Two Time Pad is insecure
   OPT的含义是指，一个pad只加密一个密文（One Time），而且是绝对安全的，但如果一个pad用了两次，（即TTP）就变得不安全了。
   
   
   攻击者通过把两个公式结合，可以得到
   
2. Real World examples

• Project Venona(1941-1946 cold war period)
• MS-PPTP (Windows NT)
• 802.11b WEP(bad protocol)
• Disk Encryption(如果仅仅是更改一部分信息，密文也仅仅会变动一部分，这会导致文件位置的泄露，因此磁盘加密一般不使用stream cipher)

3. Summary
   永远不要使用stream cipher key 超过一次..
4. Attack 2: No Integrity (OTP is malleable)
   窃听者可以根据已知内容修改密文内容
   No Integrity

Real World Stream Ciphers

1. RC4 (software mechanism)(used in HTTPS and WEP),问题如下：

• Bias in intial output:
• Prob.of (0,0) is
• Related key attacks(用相似的key也可以成功破译)
  2.Content Scramble System,CSS(hardware mechanism) (used in DVD) has beem badly broken.
  CSS 采用了 linear feedback shift register(LFSR)
  具体资料也可以参考Dan对应的书籍，3.8节也着重讲解了CSS
  Application
  击破CSS的基本方法
  image （原书90页）
  基本的做法是，已知一定数量的密文和明文的前缀（DVD的编码格式），根据前几个已知的结果猜测第一个LFSF可能的结果，然后可以计算出对应的第二个LFSF的值，再用已经得到的两个LFSF的值去比较之后的结果，如果不匹配，就再尝试一轮，一共需要（这里Dan说成了17次方，因为有固定值1的存在，所以不需要那么多）

3. eStream(2008)

   
   image
   

   通过nonce 来解决随机性的问题，每次输入的nonce都不一样保证了pair(k,r)不会被使用超过一次；
   Salsa20(Software & Hardware)

   
   image
   4.最后Dan的slides上还有一个现实生活中生成随机数的方法，但在视频中没有讲解..我就先截下来.
   image

PRG Security

Dan首先讲了，这一章节的目标就是讲清楚PRG的安全性，即一个PRG（伪随机生成器）和随机生成器是不可分辨的。
我们可以用一些统计学的测试(Statistical Test)来判断这个概念.

An algorithm that is used to distinguish a pseudo-random string G(s) from a truly random string r is called a statistical test

这里定义了一个advantage的概念，如果它的值为1，则代表能够明显区分，如果靠近0，则不能区分

image

在密码学的角度上来讲，对于任何一个有效的统计测试，它的adv都应该是negligible.

事实上，只要是安全的PRG便是不可预测的，反之也成立，不可预测的PRG也是安全的。

这个Dan给了一个例子，现在有一个PRG，根据它的后位bit可以预测前位bit，那么他也是不预测的。
理由如下： 因为这样的PRG是不安全的，所以肯定是不可预测的...
最后他给了最常见的计算不可分辨性。

image