MIT 6.858 计算机系统安全讲义 2014 秋季（三）（1）https://developer.aliyun.com/article/1484157
优化 4：高效乘法。
- 如何将 512 位数字相乘？
- 表示：将其分解为 32 位值（或任何硬件支持的值）。
- Naive 方法：逐对乘以所有 32 位组件。
- 就像你在纸上逐位相乘数字一样。
- 如果两个数字分别具有
n和m个组件，则需要O(nm)时间。 - 如果两个数字接近，则为
O(n²)。
- 卡拉兹巴乘法：假设两个数字具有相同数量的组件。
O(n^log_3(2)) = O(n¹.585)时间。- 将两个数字（
x和y）分成两个组件（x1，x0和y1，y0）。
x = x1 * B + x0y = y1 * B + y0- 例如，将 64 位数字分成 32 位组件时，
B=2³²。
- Naive:
x*y = x1y1 * B² + x0y1 * B + x1y0 * B + x0y0
- 四次乘法：
O(n²)
- 更快：
x*y = x1y1 * (B²+B) - (x1-x0)(y1-y0) * B + x0y0 * (B+1)
- …
= x1y1 * B² + ( -(x1-x0)(y1-y0) + x1y1 + x0y0 ) * B + x0y0 - 只需三次乘法，以及几次加法。
- 递归应用此算法以继续分割为更多的一半。
- 有时被称为 “递归乘法”。
- 有意义地更快（没有隐藏的大常数）
- 对于 1024 位密钥，“
n” 这里是 16 (512/32)。 n² = 256n¹.585 = 81
- 乘法算法需要决定何时使用 Karatsuba 而不是 Naive。
- 两种情况很重要：两个大数 和 一个大数 + 一个小数。
- OpenSSL：如果组件数量相等，则使用 Karatsuba，否则使用 Naive。
- 在一些中间情况下，Karatsuba 也可能胜出，但 OpenSSL 忽略了它，
- 根据这篇论文。
SSL 如何使用 RSA？
- 服务器的 SSL 证书包含公钥。
- 服务器必须使用私钥来证明其身份。
- 客户端使用服务器的公钥加密后向服务器发送随机位。
- 服务器解密客户端的消息，使用这些位生成会话密钥。
- 实际上，服务器还验证消息填充。
- 然而，仍然可以测量直到服务器以某种方式响应的时间。
服务器上 解密流水线 的图示：
* CRT * To Montgomery * Modular exp --> * c_0 = c mod q --> * c'_0 = c_0*R mod q --> * m'_0 = (c'_0)^d mod q / / * Use sliding window for bits / * of the exponent d c * Karatsuba if c'_0 and q have * same number of 32-bit parts \ \ * Extra reductions proportional \ * to ((c'_0)^z mod q) / 2R; --> ... * z comes from sliding window
- 然后，计算
m_0 = m'_0/R mod q。 - 然后，使用 CRT 结合
m_0和m_1得到m。 - 然后验证
m中的填充。 - 最后，以某种方式使用有效载荷（SSL 等）。
为 Brumley 论文中描述的攻击设置
- 受害者 Apache HTTPS 网络服务器使用 OpenSSL，在内存中有私钥。
- 连接到斯坦福校园网络。
- 对手控制校园网络上的某些客户端机器。
- 对手向服务器发送特制的消息中的密文。
- 服务器解密密文，找到垃圾填充，返回错误。
- 客户端测量响应时间以获取错误消息。
- 利用响应时间猜测
q的位。
- 总体响应时间大约为 5 毫秒。
- 请求之间的时间差大约为 10 微秒。
- 什么导致时间变化？
- Karatsuba 与 Naive
- 额外的减少
- 一旦猜测足够多的
q位，就可以因式分解n=p*q，从e计算d。 - 大约 1M 次查询似乎足以获取 1024 位密钥的 512 位
p和q。
- 只需猜测
p和q的前 256 位，然后使用另一种算法。
Brumley 论文中的攻击
- 查看 远程定时攻击是可行的 论文，详细内容请参考末尾的 参考文献 部分。
- 让
q = q_0 q_1 .. q_N，其中N = |q|（比如，对于 1024 位密钥，假设为 512 位）。 - 假设我们知道
q的高阶位j个数字（从q_0到q_j）。 - 构造两个近似值的
q，猜测q_{j+1}是 0 或 1：
g = q_0 q_1 .. q_j 0 0 0 .. 0g_hi = q_0 q_1 .. q_j 1 0 0 .. 0
- 让服务器执行模幂运算 (
g^d) 来猜测。
- 我们知道
g必然小于q。 - 如果
g和g_hi都小于q，花费的时间不应该有太大变化。 - 如果
g_hi大于q，花费的时间可能会明显变化。
g_hi mod q很小。- 较少时间：Montgomery 中减少额外的减少。
- 更多时间：从卡拉茨巴切换到普通乘法。
- 知道所花费的时间可以告诉我们 0 还是 1 是正确的猜测。
- 如何让服务器对我们的猜测执行模指数运算？
- 将我们的猜测发送给服务器，就好像它是随机性的加密。
- 一个问题：服务器将把我们的消息转换为蒙哥马利形式。
- 由于蒙哥马利的
R是已知的，将(g/R mod n)作为消息发送给服务器。
- 如何确定时间差应该是正数还是负数？
- 论文似乎暗示这并不重要：只需寻找大的差异。
- 图 3a 显示了每个比特猜测的测量时间差异。
- 卡拉茨巴与普通乘法发生在 32 位边界处。
- 前 32 位：额外的约简占主导地位。
- 接下来的位：卡拉茨巴与普通乘法的支配。
- 在某个时刻，额外的约简再次占主导地位。
- 如果两种效应的时间差抵消会发生什么？
- 图 3，关键 3。
- 更大的邻域会稍微改变平衡，揭示非零间隙。
- 论文如何获得准确的测量结果？
- 客户机使用处理器的时间戳计数器（在 x86 上为
rdtsc）。 - 进行多次测量，取中位数值。
- 不清楚为什么要中位数；最小值似乎才是真正的计算时间。
- 一个问题：由于滑动窗口，对
g的乘法相对较少。 - 解决方案：通过获取与
g接近的值进行更多的乘法运算（对g_hi同样适用）。 - 具体来说，探测
g的“邻域”（g, g+1, .., g+400）。
- 为什么要探测
g的 400 个值的邻域，而不是测量g400 次？
- 考虑我们试图处理的噪音类型。
- (1) 与计算无关的噪音（例如中断，网络延迟）。
- 当我们多次测量相同的事物时，这种情况可能会消失。
- 参见论文中的图 2a。
- (2) 与计算相关的“噪音”。
- 例如，通过滑动窗口将
g³和g_hi³相乘需要不同的时间。 - 重复的测量将返回相同的数值。
- 不会帮助确定是通过
g还是g_hi进行更多的约简。 - 参见论文中的图 2b。
- 邻域值平均出第二种噪音。
- 由于邻域值相邻，仍具有大致相同数量的约简。
如何避免这些攻击？
- 解密时间的定时攻击：RSA 盲化。
- 选择随机的
r。 - 将密文乘以
r^e mod n：c' = c*r^e mod n。 - 由于 RSA 的乘法性质，
c'是m*r的加密。 - 解密密文
c'以获取消息m'。 - 将明文除以
r：m = m'/r。 - 根据布鲁姆利的论文，OpenSSL 的 CPU 开销约为 10%。
- 使所有代码路径在执行时间方面可预测。
- 困难，编译器将努力消除不必要的操作。
- 阻止了高效的特殊情况算法。
- 难以预测执行时间：指令不是固定时间的。
- 我们能否剥夺对精确时钟的访问？
- 对于我们控制的机器上的单线程攻击者是可以的。
- 可以向合法计算添加噪音，但攻击者可能会进行平均。
- 可以对合法计算进行量化，但会有一定的性能成本。
- 但通过"睡眠"量化，吞吐量仍然可能泄漏信息。
我们应该对这些攻击感到多么担忧？
- 开发利用程序相对棘手（但这是一个一次性问题）。
- 可能会注意到服务器上的攻击（许多连接请求）。
- 尽管在繁忙的 Web 服务器集群上可能不那么容易？
- 对手必须在网络方面靠近。
- 对于对手来说并不是一个大问题。
- 可以对更多查询进行平均，共同定位附近（Amazon EC2），
- 在附近的机器人或浏览器上运行等。
- 对手可能需要知道 OpenSSL 的版本、优化标志等。
- 依赖这样的防御措施是个好主意吗？
- 这会带来多大的障碍？
- 如果对手发动攻击，后果相当严重（密钥泄露）。
其他类型的时序攻击
- 用于猜测密码的页面错误时序[Tenex 系统]
- 假设内核提供了一个系统调用来检查用户的密码。
- 逐字节检查密码，当发现不匹配时返回错误。
- 对手对齐密码，使第一个字节位于页面末尾，
- 密码的其余部分在下一页。
- 以某种方式安排第二页被交换到磁盘。
- 或者完全取消映射下一页（使用等效的
mmap）。
- 测量猜测密码时返回错误所需的时间。
- 如果花费了很长时间，内核必须从磁盘中读取第二页。
- 或者，如果取消映射，如果崩溃，那么内核会尝试读取第二页。
- 意味着第一个字符是正确的！
- 可以在
256*N次尝试中猜出一个N字符的密码，而不是256^N次。
- 缓存分析攻击：处理器的缓存由所有进程共享。
- 例如：访问滑动窗口的一个倍数会将其带入缓存。
- 在缓存中必然会驱逐其他内容。
- 恶意进程可能会用大数组填充缓存，观察被驱逐的内容。
- 根据被驱逐的偏移量猜测指数(
d)的部分。
- 缓存攻击在"移动代码"中可能会有问题。
- 在您的桌面或手机上运行的 NaCl 模块、Javascript、Flash 等。
- 网络流量时序/分析攻击。
- 即使数据被加密，其密文大小仍然与明文大小相近。
- 最近的论文表明可以通过大小、时序推断出许多关于 SSL/VPN 流量的信息。
- 例如，Fidelity 允许客户通过 SSL 网站管理股票。
- 网站为每支股票显示某种饼图图像。
- 用户的浏览器请求所有用户的股票图像。
- 对手可以枚举所有股票饼图图像，知道大小。
- 可以根据数据传输的大小推断用户拥有的股票。
- 类似于本学期早些时候客座讲座中提到的 CRIME 攻击。
参考资料
- 远程时序攻击是实际的
- 为了好玩和利润而缺失缓存
- AES 的高效缓存攻击及对策
- 离开我的笔记本电脑：针对个人电脑的物理侧信道密钥提取攻击
- 跨虚拟机侧信道及其用于提取私钥
- Ed25519：高速高安全性签名
用户认证
注意： 这些讲座笔记略有修改，来自 2014 年 6.858 课程网站上发布的内容。
核心挑战： 人类用户如何向程序证明其身份？
- 是否有任何完全主导密码的解决方案？
- 乍一看，密码似乎很糟糕。
- 低熵
-->容易让攻击者猜到它们。 - 用于密码的备用安全问题也具有低熵。
- 用户经常为多个站点使用相同的密码。
- 正如今天课堂上的论文所述，“密码继续在所有其他终端用户认证方法上占主导地位，这对安全研究人员来说是一个重大尴尬。”
- 但是…是否实际上有一种认证方案完全主导密码？
- 今天讲座的计划：
- 查看当前密码方案的工作原理。
- 讨论认证方案的理想属性。
- 查看其他认证方案与密码的比较。
密码
密码是用户和服务器之间共享的秘密。
- 天真的实现： 服务器有一个将用户名映射到明文密码的表。
- 问题： 如果攻击者入侵服务器，可以恢复所有用户/密码对。
- 改进方案： 服务器存储此表：
user_name --> hash(user_password) - 用户客户端向服务器提供明文密码，服务器对明文进行哈希并进行表查找。
- 优势： 哈希函数难以反转，因此攻击者难以执行暴力攻击。然而…
- 问题：攻击者不必对所有可能的密码启动低效的暴力搜索 – 实际用作密码的字符串集相当小！
- 偏斜分布：前
5000个密码值覆盖20%的用户。 - 雅虎密码研究：经验法则密码包含
10-20 bits的熵。 - 哈希函数优化性能；这有助于攻击者！
- 例子： 一台笔记本电脑可以以每秒约
2M SHA1 ops/sec的速度计算 SHA1。即使密码具有20 bits的熵，也可以每秒破解一个帐户。
- 服务器可以使用计算成本昂贵的密钥派生函数（例如，PBKDF2 或 BCrypt）。
- 这些函数具有可调整的成本，因此它们可以任意缓慢。
- 例如：可以使哈希成本为 1 秒 – 比 SHA1 慢
O(1M)倍。 - 内部通常使用慢哈希进行重复哈希。
- 问题：对手可以构建"彩虹表"。
- 密码到哈希映射表。
- 计算成本高昂，但允许攻击者之后有效地反转哈希。
- 为了最大化成本/效益权衡，攻击者只需为常见密码字典构建一个彩虹表。
- 大致：1 秒昂贵的哈希
|-> 1M 秒 = 10 天来哈希常见密码。之后，可以非常快速地破解任何密码数据库中的常见密码。
- 更好的解决方案：服务器可以使用密码盐。
- 在密码哈希中输入一些额外的随机性：H(salt, pw)。
- 盐值从哪里来？它以明文形式存储在服务器上。
- Q： 如果对手也能破解盐，为什么这样做更好？
- A： 攻击者无法使用单个彩虹表来检查哈希匹配 – 相同密码使用不同盐将具有不同的哈希值！
- 最佳实践：
- 选择一个长的随机盐。
- 每次用户更改密码时选择一个新的盐。
客户端应该如何将密码传输到服务器？
- 不好的主意： 明文发送密码。
- 稍微好一点：通过加密连接发送密码。
- 缺点：连接可能被假冒服务器的攻击者拦截（加密并不一定意味着服务器已经向客户端进行了身份验证！）。中间人攻击者然后可以使用窃取的密码冒充用户。
- Q： 如果客户端发送密码的哈希而不是原始密码呢？
- A： 并不会为我们提供额外的权力，因为哈希仍然可以被攻击者重放。
- 故事寓意： 加密和哈希并不会自动增加安全性 – 你需要考虑你想要实现的安全性质，并具体的加密和哈希可以实现这些目标的方式。
- 更好的主意： 挑战/响应协议。
例子：
Client Server Hi, I'm Alice. ----------------> Challenge C <---------------- H(C || password) -----------------> - Server checks whether the response is H(C || password).
- 忽略中间人（MITM）攻击，服务器现在确信用户是 Alice。
- 如果服务器是攻击者并且之前不知道密码，那么攻击者仍然不知道密码。
- Q： 我们如何防止服务器基于
H()值进行暴力猜测密码？ - A1： 昂贵的哈希+盐。
- A2： 允许客户端也选择一些随机性：防范彩虹表。
- 为了避免在服务器上存储真实密码，使用类似SRP的协议。
- 高级思想： 给定安全参数
g，客户端计算v = g^(hash(salt, password))并将v和salt发送到服务器。客户端和服务器可以利用对g和v的共享知识建立临时密钥（该协议利用了攻击者难以执行模N下的离散对数的事实；RSA 也利用了这一观察结果）。 - 实施挑战/响应通常意味着改变客户端和服务器。
为了防止暴力破解攻击，我们可以实施反锤击防御。
- 例子： 限制密码猜测次数；在太多错误猜测后实施超时期。
- 限制猜测速率非常重要，因为密码的熵很低！
- 许多网站对密码施加要求（例如长度，使用标点等特殊字符）。
- 实际上，重要的是熵！格式要求很少转化为更高的熵。
- 一个称职的字典攻击者可以模拟密码约束并生成彩虹表；即使有约束，人们仍会选择符合先验字符分布的密码。
- Telepathwords:
telepathwords.research.microsoft.com/
- 当您输入潜在的密码字母时，尝试使用启发式猜测下一个字母！
- 常见密码（例如，通过密码数据库泄漏）
- 来自网站的流行短语
- 用户在选择字符时常见的偏见（例如，使用相邻键来输入相邻的密码字符）
- Kerberos v4 和 v5 在没有预身份验证的情况下容易受到离线猜测的影响：
www.gnu.org/software/shishi/wu99realworld.pdf
- 任何人都可以向 KDC 请求使用用户密码加密的票证，即 KDC 不会验证请求（尽管响应将使用
K_c加密）。 - 攻击者可以尝试暴力破解猜测用户的密码–这很容易并行化。由于票据授予票据具有已知格式，攻击者可以确定解密何时成功。
- 在 Kerberos v5 中，票证请求者必须在请求中包含
{ timestamp }_{K_c}，以证明对K_c的了解。
密码恢复非常重要，但经常被忽视。
- 人们经常关注密码的熵，但如果恢复问题可以用来重置密码，密码认证方案的强度为
min(password_entropy, recovery_question_entropy)。 - 恢复问题通常很容易被猜到。在一个著名的例子中，有人通过猜测萨拉·佩林的安全问题的答案获得了对她的雅虎地址的访问权限。
- 固有低熵（“你最喜欢的颜色是什么？” “你最好朋友的名字是什么？”）
- 通过社交媒体资料泄露的答案（“你最喜欢的电影是什么？”）
- 自动生成的问题通常很容易回答（“5 + 5 等于多少？”）
取代密码的追求
在今天的阅读中，作者提出了一堆可以用来评估认证方案的因素（目标是确定密码是否像它们看起来那样糟糕）。作者考虑了三个高级指标：可用性、部署性和安全性。
- **可用性：**用户与认证方案交互的难易程度如何？
- 易学性：
- “不了解方案的用户可以轻松地弄清楚并学会它。”
- 这是密码方案如此受欢迎的一个关键原因！
- 不经常出现的错误：
- “用户必须执行的登录任务通常在由合法和诚实的用户执行时成功。”
- 这是用户选择易于猜测密码的重要原因。
- 用户可扩展性：
- “使用方案登录数百个帐户不会增加用户的负担。”
- …解释了为什么人们经常重复使用密码或为基本密码创建一个简单的每个站点唯一化方案。
- 轻松从认证令牌丢失中恢复：
- 密码的优势在于它们易于重置。
- 无需携带
- 密码的另一个优势。
- 可部署性：将身份验证方法整合到实际系统中有多容易？
- 与服务器兼容：
- “在验证者端，该方案与基于文本的密码兼容。提供者不必更改其现有的身份验证设置以支持该方案。”
- 与浏览器兼容：
- “用户不必更改他们的客户端以支持该方案。如果方案要求安装插件或任何需要管理员权限的软件，则无法提供这种好处。”
- 易访问：
- “能够使用密码的用户不会因残疾或其他身体（非认知）状况而无法使用该方案。”
- 可部署性非常困难：很难让用户或服务器大规模更新！
- 密码在这一类别中表现良好，默认情况下，因为作者将“可部署性”定义为系统与当前密码基础设施整合程度。然而，密码在下一个类别中表现不佳……
- 安全性：身份验证方案可以防范哪些攻击？
- 对物理观察具有弹性：
- “在观察用户进行一次或多次身份验证后，攻击者无法冒充用户。如果方案只能通过重复观察 10-20 次以上才能被破解，我们授予准弹性对物理观察的方案。攻击包括肩窥、拍摄键盘、录制按键声音或热成像键盘。”
- 密码未通过此测试，例如，可以通过拍摄键盘或录制按键声音来捕获密码。
- 对有针对性的冒充具有弹性：
- “通过利用个人细节（出生日期、亲属姓名等）的知识，熟人（或熟练的调查员）无法冒充特定用户。个人知识问题是在这一点上失败的典型方案。”
- 作者表示密码是“准抗性”的，因为他们找不到任何研究表明您的朋友或熟人可以轻松猜出您的密码。
- 对受限制的猜测具有弹性：
- “一个攻击者的猜测速率受到验证者的限制，不能成功猜测出大部分用户的秘密……缺乏这种好处意味着惩罚那些经常让用户选择的秘密从一个小而众所周知的子集中选择的方案。”
- 密码失败是因为熵值低 + 分布倾斜。
- 对不受限制的猜测具有弹性：
- “只受可用计算资源限制的猜测速率的攻击者无法成功猜测出大部分用户的秘密。例如，如果一个能够尝试每个账户最多 2⁴⁰ 甚至 2⁶⁴ 次猜测的攻击者仍然只能达到不到 1%的账户，我们可能会授予这一好处。缺乏这一好处旨在惩罚那些凭证空间不足以抵御来自一个小而众所周知的子集的暴力搜索的方案。”
- 密码失败是因为它们具有低熵和偏斜分布。
- 对内部观察具有弹性：
- “攻击者无法通过拦截用户设备内的用户输入（例如，通过键盘记录恶意软件）或窃听证明者和验证者之间的明文通信来冒充用户（我们假设攻击者也可以击败 TLS，也许通过 CA）。这惩罚了那些不具备重放抵抗性的方案，无论是因为它们发送静态响应还是因为它们的动态响应对策可以通过少数观察被破解。这一好处假定通用设备（如软件可更新的个人计算机和手机）可能包含恶意软件，但专门用于该方案的硬件设备可以做到无恶意软件。”
- 密码失败是因为它们是静态令牌：一旦你有了一个，你可以使用它直到它过期或被撤销。
- 对网络钓鱼具有弹性：
- “模拟有效验证器的攻击者（包括通过 DNS 操纵）无法收集以后可以用来冒充用户向实际验证器进行身份验证的凭据。这惩罚了允许网络钓鱼者让受害者在类似网站上进行身份验证，然后将收集的凭据用于真正网站的方案。”
- 密码失败：网络钓鱼攻击非常普遍！
- 无信任第三方：
- “该方案不依赖于一个可信任的第三方（除了证明者和验证者），后者在遭受攻击或变得不可信任时，可能会危及证明者的安全或隐私。”
- 这一属性提出了一个重要观点：如果我们可以信任一个方当来存储密码、运行密码服务器等，许多身份验证问题将变得更容易。然而，单点故障是不好的，因为攻击者可以将所有精力集中在那一点上！
- 对其他验证者泄露具有弹性：
- “验证者可能泄露的任何信息都不能帮助攻击者冒充用户向另一个验证者进行身份验证。这惩罚了那些在一个提供者内部欺诈或对一个后端的成功攻击危及用户在其他网站账户的方案。”
- 这一属性与无信任第三方有关。为了避免中心化故障点，我们希望引入一些分布式身份验证的概念：然而，这是否意味着系统的强度仅取决于其最薄弱的环节？
- 回想一下 HTTPS，以及一个糟糕的证书颁发机构如何说服浏览器接受任意站点的伪证书。安全性取决于最不安全的 CA 的强度！
- 作者表示，密码失败是因为人们经常在不同网站上重复使用密码。
生物特征识别
生物特征识别： 利用个人外貌或行为的独特方面。
- 密钥空间有多大？
- 指纹： ~13.3 位。
- 虹膜扫描： ~19.9 位。
- 语音识别： ~11.7 位。
- 因此，熵的位数大致与密码相同。
生物特征识别与密码
Usability metric Passwords Biometrics --- --- --- Easy-to-learn: Yes Yes Infrequent errors: Quasi-yes No Scalable for users: No Yes Easy recovery: Yes No Nothing to carry: Yes Yes Usability score: 3.5 vs 3 Deployability metric Passwords Biometrics --- --- --- Server-compatible: Yes No Browser-compatible: Yes No Accessible: Yes Quasi-yes (entering biometrics is error-prone) Deployability score: 3 vs 0.5 Security metric Passwords Biometrics --- --- --- Res-to-Phys-Obs: No Yes Res-to-Trgtd-Imp: Quasi-yes No (e.g., replaying voice recording, lifting fingerprints from surfaces) Res-to-Thrtld-Guess: No Yes Res-to-UnThrtld-Guess: No No (key space isn't much bigger than that of passwords) Res-to-Internal-Obv: No No (captured biometric data can be replayed) Res-to-Phishing: No No No-trusted-3rd-Party: Yes Yes Res-Other-Ver-Leaks: No No (same biometrics are used by all verifiers) Security score: 1.5 vs 3
因此，最终得分是 8 对 6.5。当然，每个类别可以分配非单位权重，但关键是生物特征识别并不明显比密码“更好”！
有些目标似乎很难同时实现。
Memorywise-Effortless + Nothing-to-Carry. Memorywise-Effortless + Resilient-to-Theft. // Either the user remembers something, or // it can be stolen (except for biometrics). Server-Compatible + Resilient-to-Internal-Observation. Server-Compatible + Resilient-to-Leaks-from-Other-Verifiers. // Server compatible means sending a password. // Passwords can be stolen on user machine, // replayed by one server to another.
MIT 6.858 计算机系统安全讲义 2014 秋季（三）（3）https://developer.aliyun.com/article/1484160
