More Than Code

密码协议(1) 引论与密钥交换协议

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

《密码协议》课程笔记（1） 引论+密钥交换协议

引论

密码协议基础

  • 协议：两个或者两个以上的参与者为了达到特定的目的，采取的一系列步骤（没有严格的界限来区分密码协议和一般协议）
    • 规定了一系列有序执行的步骤
    • 有两个或者两个以上的参与者
    • 协议都有明确的目的
  • 密码协议的要求：
    • 安全需求——加密（执行过程中的敏感数据不被非授权者所知）、认证（保证参与者的合法身份）和不可抵赖性（协议执行过程可以追查）
    • 鲁棒性——有恶意参与者时能部分地正确执行
  • 分类：
    • 仲裁协议——仲裁者是可信第三方，协议的执行一直需要仲裁者
    • 裁决协议——裁决者只在有争议的时候才参与协议的执行
    • 自动执行协议——协议本身公平，不需要可信第三方

密码协议模型

image-20220327203810799

  • 参与密码协议的主体：协议参与者、协议攻击者、可信第三方（协议参与者都信任的一个主体或者一个组织）、仲裁者——攻击者和参与者没有严格的界限
  • 网络可能是同步的，也可能是非同步的。同步网络中，所有信息在某一个时钟周期内传送。大部分密码协议的研究都在同步网络条件下
  • 参与者分为诚实参与者、半诚实参与者和恶意攻击者
  • 攻击者的能力：拥有无限计算能力的攻击者，只有概念多项式时间计算能力的攻击者——信息论安全的、密码学安全的
    • 安全信道：参与者的通信既不会被攻击者窃听，也不会被攻击者篡改
    • 认证的信道：攻击者可以窃听参与者的通信，但是不能篡改通信内容
    • 未认证的信道：窃听+篡改
    • 被动攻击者（窃听者）：只是窃听或获取不诚实参与者在协议进行中的所有输入，不控制其行为
    • 主动攻击者：窃听+控制行为

密码协议设计分析概述

  • 密码协议安全性分析的基本方法：
    • 使用自然语言论证的标准模型
    • 开发专家系统
    • 使用Random Oracle模型
    • 使用BAN类逻辑
    • 使用CSP（Communicating Sequential Processes）等模型检查方法

密钥交换协议

数学前提

  • 随机变量X、Y之间的统计距离：

    image-20220426142423867

    • \(\Omega\)为变量X和Y的采样空间
    • 统计距离为1，当且仅当X和Y不相容（每个随机事件\(\omega\)，要么X发生，要么Y发生）
    • \(0\leq\Delta(X,Y)\leq 1, \Delta(X,X)=0,\Delta(X,Y)=\Delta(Y,X),\Delta(X,Y)+\Delta(Y,Z)\geq \Delta(X,Z)\)

  • 三种假设：

    • Discrete Logarithm DL假设（给\(g^x\)，难求\(x\)）
    • (Computational) Diffie-Hellman DH假设（给\(g,\ g^x,\ g^y\)，难求\(g^{xy}\)）
    • Decision Diffie-Hellman DDH假设（知道\(g,\ g^x,\ g^y,\ g^z\)，难以确定是否\(z=xy\ mod\ n\)）
    • 证明困难程度依次下降

  • 随机自规约：一个问题的实例\(I\)满足：

    • \(I\)构造出一个或多个随机实例\(I'\)，后者是独立于前者的均匀分布
    • 如果得到随机实例的解，则从\(I'\)的解得到\(I\)的答案
    • 以上两步要在多项式时间内完成

    image-20220328132907732

    image-20220328132946056

    image-20220428122506270

  • 计算安全的形式：一个方案为\((t,\epsilon)\)安全，如果每个运行时间最多为t的攻击者最多以\(\epsilon\)的概率攻破——当运行时间和成功概率为安全参数n（双方生成密钥时，以n为安全参数，攻击者也知道）的函数时：

    • 多项式时间概率算法：多项式时间内运行的概率算法
      • 多项式时间算法：在最坏情况下时间复杂度为\(O(n^k)\)的算法，n为问题规模，k为常数
      • 多项式时间算法的基础上，还允许算法获取到随机数（另一种表述为，算法执行中存在一个随机选择下一步的过程，相同输入经过该算法可能会得到不同结果）
    • 可忽视函数：（小的成功概率，指比任何关于n的多项式的倒数级别更小）比任何多项式的倒数都增长得慢的函数，称为可忽略的，例如\(2^{-n}\)

    image-20220426151856426

    • 渐进安全：如果每一个PPT（概率多项式时间）攻击者攻破一个方案的概率是可忽略的，则方案是安全的

密钥交换

密钥交换也称密钥协商，利用此类协议，通信双方（或多方）在一个公开信道上相互传递某些信息建立一个共享的密钥，用于对称密码协议，实现保密性、数据完整性等密码服务。

有些密钥交换协议会假设Ａ和Ｂ在运行协议前已经共享了一个密钥。

两方Diffie-Hellman密钥交换

  • 协议内容

    • 双方约定素数阶有限域\(F_p\)和其乘法循环群一个生成元\(g\)

      image-20220328133644178

    • 将协商出的共享秘密值\(k\)用于一个哈希函数的输入，其输出作为会话密钥——因为k是循环群中的元素，不能直接用作对称密钥，并且可能存在较多冗余，哈希函数能够去除这种冗余

  • 被动攻击：能够抵御

    • 安全性依赖于求解离散对数（CDH）问题的困难性——攻击者截取\(g,g_a,g_b\)，求解\(k=g^{ab}\)
    • 必须假设使用的循环群中DDH问题是困难的——攻击者只想知道与\(k\)有关的任何信息

  • 中间人攻击：

    image-20220328134606212

    • 此时攻击者E就可以计算\(k_1=g_a^e\ mod\ p\)和\(k_2=g_b^e\ mod\ p\)
    • 不具有密钥的认证功能——协议参与者没有对收到的信息进行认证，以确信消息确实来自认定的通信方

  • 端到端协议（station-to-station）：对Diffie-Hellman的改进，假设Torrent为可信中心

    • 约定：

      image-20220328140101876

    • 过程：（使用参与方的数字签名保证信息来源真实性）

      image-20220328140151147

  • 基于密码加密的协议
    • 假设两个参与者共享一个口令
    • \(E\)为一个加密算法，以口令和消息作为输入，输出为密文，记为\(C=E_{pw}(m)\)；\(D\)为解码算法
    • 过程：
      • 参与者A选择均匀选择一个\(x_A\in Z_n\)，发送\(E_{pw}(y_A),y_A=g^{x_A}\)给B
      • 类似的，参与者B也发送\(E_{pw}(y_B)\)给A
      • 则共享密钥为\(k=g^{x_Ax_B}\)
    • 被动攻击者只能看到加密后的内容，不会泄露pw的信息，而且\(x_A\)服从均匀分布，也是未知的
    • 主动攻击者需要猜出pw，才能实现中间人攻击
相关文章推荐