Sky's blog

Secure Protocol Review

Word count: 4,339 / Reading time: 16 min
2018/06/04 Share

前言

最近略闲,复习一下双语课程—安全协议,复习原因也很简单,一是为了考试,二是巩固密码学知识与应用,便于后面做crpto的题目,同时7月可能要去夏令营,为了不耽误考试,一箭三雕吧。当然技术拙劣,有错误请斧正!

第一章(密码学概述)

基本的论述内容

1
2
3
4
5
6
7
Message, M
Plaintext, P
Ciphertext, C
Encryption function, E
E(M) = C
Decryption function, D
D(C) = M

基本的组成:消息、明文、密文、加密算法、解密算法
(应该还缺个密钥)
为保证机密性:

1
2
3
4
5
6
Authentication
Ascertaining a message’s true origin
Integrity
Verifying that a message has not been modified in transit
Nonrepudiation
A sender should not be able to falsely deny later that he sent a message

需要做到:认证性,完整性,不可否认性
然后是古典密码和现代密码
一般来说古典密码是基于算法保密而保证安全性的
而现代密码是基于密钥保密而保证安全性
然后对于现代密码
1.对称密码
对于对称密码,只有1个密钥,用于加密和解密
2.公钥密码
对于公钥密码,有私钥和公钥,私钥用于解密,公钥用于加密
然后是一些常见的攻击类型:
1.唯密文攻击
2.已知明文攻击
3.选择明文攻击
4.自适应选择明文攻击
5.选择密文攻击
6.选择密钥攻击
7.利用强迫手段获取密钥
8.购买/利诱获取密钥
但是无论哪种攻击方式,都必须确保破解消耗小于明文本身的价值
衡量攻击的复杂性有3个因素:
1.数据复杂性
2.破解过程复杂性
3.存储空间需求
其他加密方式

1
2
3
Existence of a secret message is concealed by hiding it in other messages
Example
Hiding secret messages in graphic images

通俗易懂来说,图片隐写等Misc常见问题,也算加密的一部分
然后是一些经典算法
古典加密中的:
1.代换密码
例如经典的凯撒密码
2.转置密码
例如hill加密(如果我没记错算法的话)
3.还有二战期间的German Enigma
现代加密中的:
1.流密码
最常见的比如RC4
2.还有所谓不可破解的One-Time Pads
即一字一密,但密钥传递成为难题
3.还有一些常见现代密码:
AES
DES
RSA
DSA
前两者为对称密码,后两者为公钥密码

第二章(协议概述)

关于协议的定义

1
A protocol is a series of steps, involving two or more parties, designed to accomplish a task

即协议是一系列的步骤,包含两个或者多个部分,被设计用来完成某个任务
然后是协议的特点

1
2
3
4
All parties must know the protocol
All parties must agree to follow it
Must be unambiguous
Must be complete

所有参与者都必须知道协议过程
所有参与者都必须遵循协议规则
协议必须是明确的
协议必须是完整的
而密码协议是一种使用密码算法来预防和抵御欺骗和窃听的协议
协议中两个可信第三方:
1.第三方:与决策无利害关系
2.仲裁机构:简化协议流程,但增加开销
安全协议的种类:
1.仲裁协议
即协议涉及可信第三方
2.判决协议
有可信第三方,但是用于事后判决
3.自执行协议
没有可信第三方

仲裁协议

即必须有一个可信第三方参与整个协议
例如:
1.Alice将凭证交予可信第三方
2.Bob将支票交给Alice
3.Alice使用支票
4.当Alice使用完支票后,可信第三方将凭证交给Bob。否则将凭证还给Alice

安全问题
1.仲裁者是否可信?
2.仲裁者会对整个协议产生开销(你找了个第三方来,不能不给人家钱吧= =)
3.任何仲裁都存在固有延长
4.仲裁人被攻击者当做整个系统的弱点

判决协议

判决协议代价高昂
判决协议可以细分为两个下级子协议:
1.无仲裁子协议
2.仲裁子协议
只有在有争议的特殊情况下才执行。

无仲裁子协议(每次执行)
1.Bob和Alice商议合约
2.Alice在合约上签字
3.Bob在合约上签字
仲裁子协议(存在争议时执行)
1.Bob和Alice同时来到仲裁者前
2.Alice出示证据
3.Bob出示证据
4.仲裁者根据证据进行决策
安全问题
1.协议依靠当事人的诚信
2.是否有可信第三方的存在,即第三方是否可信
优势
1.骗子的身份可以被检测到
2.可起到预防和制止作弊的作用。

自执行协议

没有对可信第三方的要求
协议本身必须保证公平性
一方可以检测对方是否试图作弊,因此,可以立即停止。
不幸的是,没有一个协议可以针对所有情况

针对协议的攻击

1.密码攻击
1.1 针对协议中使用的密码算法的攻击
1.2 针对用于实现算法和协议的密码算法的攻击
1.3 对协议本身的攻击
2.被动攻击
窃听协议中的部分或全部
3.主动攻击
引入新消息,删除消息,中断,修改,回复
4.被动作弊者
遵循协议,但尝试获得更多信息
5.积极作弊者
破坏协议,在进行中企图作弊

商议使用协议

1.Alice和Bob在密码算法上达成一致
2.Alice和Bob使用同一密钥
3.Alice使用约定算法和密钥对明文进行加密
4.Alice向Bob发送密文
5.Bob用约定算法和密钥对密文进行解密

安全问题
1.密钥的秘密分发
2.有可能消息可被解密,甚至伪造虚假消息
3.随用户数量增多,对于n个用户,我们需要n(n-1)/ 2个密钥
解决问题1、3:
此时出现公钥密码,即拥有x可以迅速求得f(x),但是f(x)不能强行逆向运算回x,需要一个陷门
即知道一些秘密消息y的情况下,f(x)可以迅速求得x
即公开1个公钥,自己保留1个私钥,则n个用户,只需要n个私钥和n个公钥即可
解决问题2:
使用hash函数,因为hash函数的难以碰撞,我们可以用其当做消息验证码
即将明文和明文hash一同加密传输,解密后即可验证明文的hash是否等于hash,以确保消息完整性
关于公钥密码的密码协议协商:
1.Alice和Bob约定一个公钥密码算法
2.Bob向Alice发送自己的公钥
3.Alice用Bob的公钥加密消息,并将消息发送给Bob
4.Bob用私钥解密消息
对于公钥密码系统
需要一个管理所有公钥的数据库
协议
1.Alice从数据库中得到Bob的公钥
2.Alice用Bob的公钥加密消息,并将消息发送给Bob
3.Bob用私钥解密消息
安全问题
真实应用中,公钥密钥不用于消息的加解密,而用于密钥的加解密
原因如下:
1.公钥加密速度慢
2.易受明文攻击的影响
公钥密码在协议中的作用实例:
1.Bob把公钥发送给Alice
2.Alice生产一个随机数k,然后用Bob的公钥加密随机数,发送回Bob
3.Bob收到后,利用私钥解密消息,得到随机数k
4.Bob和Alice后续利用这个随机数k作为密钥进行通信
为确保安全性,必须进行签名
签名具有以下特点:
1.真实性
2.不可伪造性
3.不可重用性
4.不可改变的性
5.不能否认性
具有第三方仲裁的协议
1.第三方将KA分发给Alice,将KB分发给Bob
2.Alice用KA加密消息,并发送给第三方
3.第三方用KA解密消息
4.第三方用KB加密消息, 并加密一个凭证,然后发给Bob
5.Bob用KB解密,并读取Alice的消息和第三方的凭证
安全问题
1.第三方的时间延迟
2.第三方是通信系统中的瓶颈部分
3.很难找到可信的第三方
4.第三方必须完全安全
基于公钥的文档公钥密码协议
1.Alice用私钥对文档进行加密,从而签署文档
2.Alice将签署的文档发给Bob
3.Bob用Alice的公钥解密文档,从而验证签名
常见实例(RSA/DSA)
存在问题:可被重放攻击
解决方案:数字签名中加入时间戳
但公钥密码算法对长文档签名效率很低,所以选择hash函数
1.Alice根据文档生成单向哈希散列
2.Alice用私钥加密散列,从而签署文档
3.Alice将文档和签名发给Bob
4.Bob生成文档的单向散列,并用Alice的公钥进行解密签名,用于和哈希值进行匹配
优势
1.速度增加,散列的签名等价于对文档的签名
2.签名可以与文件分开保存
3.收件人对文档和签名的存储要求小得多
4.存档系统可以使用这种协议来验证文档的存在而不存储他们的内容
多重签名验证
1.Alice签署文件的散列
2.Bob签署文件的散列
3.Bob把他的签名发送给Alice
4.Alice把文件、签名和Bob的签名发给第三方
5.第三方验证了Alice和Bob的签名
6.第三方可以独立的验证这两个签名
数字签名的问题
Alice可以签署一份文件,然后声称没有签署。她可以说谎别人偷了他的私钥
解决方案
1.Alice签名一条消息
2.Alice用已签名的消息发送给第三方
3.第三方验证Alice的身份,添加一个时间戳,将其全部签名,并将其发送给Alice和Bob
4.Bob验证第三方的签名,识别Alice的签名
5.Alice验证第三方发送给Bob的消息,如果Alice没有发送信息,那么他会快速响应。
数字签名与公钥密码的结合
1.Alice用私钥签名
2.Alice用Bob的公钥加密签名消息,并发送给Bob
3.Bob用私钥解密消息
4.Bob用Alice的公钥验证消息,并恢复消息
注:该过程必须使用时间戳,以防消息的重放
确认收到消息的反馈
1.Alice用自己的私钥签名消息,并用Bob的公钥加密签名,然后发送给Bob
2.Bob用私钥解密消息,并用Alice的公钥验证消息
3.Bob用自己的私钥签名消息,并用Alice的公钥加密签名,然后发送给Alice
4.Alice用私钥解密消息,并用Bob的公钥验证消息
公钥密码系统的安全问题
1.虽然存放公钥的数据库安全,但是任何人可以访问
2.攻击者可以在传输中替换公钥
解决方案
密钥认证机构或密钥分发中心KDC使用自己的私钥对管理的公钥进行加密

1.RSA体制
基于大数分解的困难性

2.Rabin体制
基于分解因子的困难性

3.散列函数
基于不可碰撞性,单向性

消息认证三元组(K T V)
K:密钥生产算法
T:标签算法
V:验证算法

1.接收方确信消息未被更改过
2.接收方确信消息来自真实的发送方

数字签名五元组(P A K S V)
P:所有消息组成的有限集
A:所有签名组成的有限集
K:所有密钥组成的有限集
S:签名算法
V:验证算法

RSA签名

私钥签名,公钥验证
因为私钥是唯一不公开的,可以保证签名者的身份
而公钥是公开的,任何人可以用来验证签名者的身份

1.不要直接对数据签名,而应对数据的hash值签名
2.要采用先签名后加密的数字签名方案,不能使用先加密后签名的数字签名方案

DSA签名

一般的离散对数签名

EIGamal签名

Schnorr签名

Okamoto签名

基于椭圆曲线的数字签名算法ECDSA

基本安全协议

秘密分割

例如将消息加密,密文给Bob,密钥给Alice
只有当Bob和Alice在一起时才可解密

存在问题:
Alice或Bob带着秘密走了,那么消息永远无法复原

秘密共享

(m,n)门限方案

将信息分割成n个部分,任何m部分都可以重构消息
优势
1.某个密钥暴露,整个系统也不会受到攻击
2.某个密钥丢失/损坏,系统依旧可以复原

阈下信道

1.Alice随即产生一个无害消息
2.Alice对这个无害信息签名,她在签名中隐藏她的阈下信息
3.Alice通过Walter发送签名消息给Bob
4.Walter不能发现这个无害消息隐匿的阈下信息,并传递给Bob
5.Bob检查这份无害消息的签名,确认消息来自于Alice
6.Bob忽略无害的消息,而用和Alice共享的秘密密钥,提取阈下信息

基于ElGamal数字签名的阈下信道方案

基于RSA数字签名的阈下信道方案

反阈下通信——比特承诺

1.Alice将消息放在箱子中,并将箱子送给Bob,保留箱子的钥匙(唯一打开箱子的办法)
2.Alice想要向Bob证实消息的时候,将钥匙和待确认的消息给Bob
3.Bob打开箱子并验证信息

使用对称密码算法的比特承诺

1.Bob产生一个随机比特串R,并发送给Alice
2.Alice生产一个由她想承诺的比特b组成的消息,然后用密钥K对(R,b)进行加密,并将加密结果发送给Bob
3.当Alice想要证明消息的时候,将密钥发给Bob
4.Bob解密消息,验证最初的随机比特串R,验证承诺比特

随机比特串R:用于防止Alice爆破密钥,找到一个解密后可得到仅部分bit不同的消息的攻击
例如:Alice承诺消息010101,密钥为K
而在承诺以后,Alice对密文进行爆破解密,直到可以解密出
110101这样的密文,然后将此时的密钥G发送给Bob,即篡改了承诺

使用单向函数的比特承诺

1.Alice生产两个随机比特串,R1和R2
2.Alice产生消息(R1,R2,b)
3.Alice计算该消息的单向函数值,并将结果以及其中一个随机串R1发送给Bob
4.Alice要证明自己的消息时,将(R1,R2,b)均发给Bob
5.Bob计算该消息的单向函数值,将值与之前收到的比较,并将R1与之前的R1的比较

Alice不可能进行欺骗,因为除非Alice找到R2’和想篡改的b’
并且使H(R1,R2’,b’) = H(R1,R2,b)
这对于单向函数的不可碰撞性,显然是极度困难的

使用伪随机数序列发生器的比特承诺

1.Bob产生随机比特串Rb,并发送给Alice
2.Alice为伪随机比特发生器生成一个随机种子,然后对Bob随机比特串中的每一比特,她回送Bob下面两个中的一个:
(a)若Bob比特为0,发生器的输出
(b)若Bob比特为1,发生器输出与她的比特的异或
3.当Alice需要验证的时候,将随机种子发送给Bob
4.Bob完成第二步,确认Alice的行动是合理的

只要Bob的随机比特串足够长,伪随机比特发生器不可预测,这时Alice就无法进行欺诈

应用场景:
公平的硬币抛掷问题
1.Alice必须在Bob猜测前抛币
2.得到Bob的猜测结果后,Alice不再抛币
3.Bob在猜测前不知道硬币的抛掷结果

单向函数抛币协议
1.Alice选择一个随机数x,她计算f(x)
2.Alice将f(x)发给Bob
3.Bob猜测x是奇数/偶数,并将猜测结果发给Alice
4.Alice公布结果,并将x发给Bob
5.Bob验证f(x)是否等于之前接收到的f(x)

不可欺骗性来自于单向函数的不可碰撞性
若Alice可以找到一个奇数x,一个偶数x’
且f(x)=f(x’),则Alice每次都可以欺骗Bob
但这基本不可能

CATALOG
  1. 1. 前言
  2. 2. 第一章(密码学概述)
  3. 3. 第二章(协议概述)
    1. 3.1. 仲裁协议
    2. 3.2. 判决协议
    3. 3.3. 自执行协议
    4. 3.4. 针对协议的攻击
    5. 3.5. 商议使用协议
      1. 3.5.1. RSA签名
      2. 3.5.2. DSA签名
      3. 3.5.3. 一般的离散对数签名
      4. 3.5.4. EIGamal签名
      5. 3.5.5. Schnorr签名
      6. 3.5.6. Okamoto签名
      7. 3.5.7. 基于椭圆曲线的数字签名算法ECDSA
  4. 4. 基本安全协议
    1. 4.1. 秘密分割
    2. 4.2. 秘密共享
      1. 4.2.1. (m,n)门限方案
    3. 4.3. 阈下信道
      1. 4.3.1. 基于ElGamal数字签名的阈下信道方案
      2. 4.3.2. 基于RSA数字签名的阈下信道方案
    4. 4.4. 反阈下通信——比特承诺
      1. 4.4.1. 使用对称密码算法的比特承诺
      2. 4.4.2. 使用单向函数的比特承诺
      3. 4.4.3. 使用伪随机数序列发生器的比特承诺