sky's blog

安全协议考试重点

字数统计: 6,431阅读时长: 23 min
2018/06/29 Share

前言

这是一篇水文,全是为了9号安全协议的考试
吐槽一波。。。矿大今年搞的所有考试都在夏令营这个时间段,真尴尬
搞的我现在一边焦虑考试,一边焦虑夏令营,还对机考提心吊胆
只希望这个月赶紧过去……
跑题了,这篇文章主要总结一下考试重点(别以为我对这个感兴趣,全都为了考试XD)

基础概念

破解算法的种类

1.完全破解
2.全部推导
3.实例破解
4.信息推导

协议的特性

1.各方必须了解协议
2.各方必须一致遵守。
3.协议必须明确
4.协议必须完整

安全协议的种类

1.仲裁协议:涉及可信第三方
2.判决协议:可信第三方,事后可做判决
3.自执行协议:没有可信第三方

协议攻击手段

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

安全协议的特征

1.机密性:只有授权获得数据的人才能获得数据。
2.完整性:数据未被未经授权的实体更改。
3.身份验证:数据确实来源于所声称的发送者。
4.不可否认性:实体不能拒绝发送他们提交的数据。
5.新鲜度:无用的东西是不可猜测的,而且永远不会重复使用。

Dolev-Yao 威胁模型

Dolev Yao威胁模型代表一个可以窃听、拦截和合成任何消息的攻击者,并且仅受所使用的加密方法的约束的限制。
假设攻击者可以:
1.获取通过网络传递的任何消息
2.作为网络的合法用户(即可以发起与任何其他用户的对话)
3.可以成为任何发送者的接收者
4.可以通过冒充任何其他实体向任何实体发送消息。
我们认为:
任何通过网络发送的消息都是攻击者发送的。
因此,接收到的任何消息“可能”都被攻击者操纵了。
攻击者可以控制事物的发送方式
但是攻击者不能做到
1.无法猜出作为安全协议的一部分选择的随机数。
2.如果不知道密钥,攻击者无法从密文中找出明文,也不能从明文中创建密文。
3.无法解决公钥的私钥配对问题
4.无法控制合法用户的计算设备的“内存”

常见攻击方式

1.窃听
2.篡改
3.重放
4.中间人攻击
5.反射
6.拒绝服务

秘密的分割与共享

秘密分割

将一个消息分割成n份,每一块单独看都不具有意义,但所有的块集合起来能恢复出原消息
例如:
消息m,随机数r
m xor r = s
将r交给A
将s交给B
那么只有当A,B同时在场的时候,才可以复原消息m,单独来看都不具备意义

存在问题:
若有人丢失了自己的那一份,则完整的秘密将无法复原

秘密共享—门限方案

将一个群体的签名密钥分发给群体中的每个成员,使得任何成员个数不少于门限值的子集都可以产生签名。
任何成员个数少于门限值的子集都无法以产生签名。
门限签名是最普通、最常用的群体签名。
其方法是将一个群体的签名密钥分发给群体中的每个成员,使得任何成员个数不少于门限值的子集都可以产生签名
而任何成员个数少于门限值的子集都无法以产生签名

将秘密分割为n份,只有其中m个人在一起,才能够复原秘密,这叫做(m,n)门限方案
一般使用函数实现:
例如多次方程:
假设是(2,n)方案,那么则使用1次方程即可:ax+b=y
假设是(3,n)方案,那么则使用2次方程即可:ax^2+bx+c=y
……
假设是(m,n)方案,那么则使用m-1次方程即可:ax^(m-1)+bx^(m-2)……+z=y

阈下信道

即消息本身不包含秘密信息,通过交换完全无害的签名消息,他们可以来回传秘密信息

比特承诺

A向B承诺一个消息,在有效期内,A可以向B证实承诺的消息,但是A无法欺骗B

抛币问题

让彼此互不信任的双方对一个随即位达成共识

智力扑克

能够使玩家利用虚拟扑克牌通过一条交流渠道来进行打扑克牌游戏

不经意传输

A掌握某个秘密信息,B不知道信息
协议结束后,B以1/2的概率获得信息s
但是A不知道B是否得到了s

认证与密钥建立协议

关于身份认证

一般的交互传输,很容易产生重放攻击
较为好的做法是引入挑战响应机制
加入Nonce和hash函数,如此一来可以阻止重放攻击

建立一个拥有第三方的密钥建立协议

1.0版本


这显然存在显著攻击问题,一切传输皆明文,攻击者可窃听,伪造,中间人攻击

2.0版本


传输过程中,用服务器与A和B的公共密钥,分别加密KAB
防止明文传输,导致窃听等问题
但存在中间人攻击问题:
攻击1:

中间人只需要拦截最后A给B的消息,并将发送给B的人改成自己,即可和B建立连接
攻击2:

在A给服务器请求和B通信的时候,攻击者拦截消息,将想要通信的人改为自己
则可以轻松让A建立与自己的联系,成功伪造成B

3.0版本


为了让A知道自己和谁在通信,所以服务器在反馈时加入了通信对象
在给A的信息中,加入了即将通信对象B
在给B的信息中,加入了即将通信对象A
但依旧存在伪造攻击

即服务器不能确定,向自己申请的人是否和发送的消息相符
比如我是C,我却说自己是A,服务器无法辨别

4.0版本

为此加入了挑战响应机制

即加入了nonce,服务器即可判断给他发送消息的人是谁

为了保证A不被C假冒(B无法辨别A的身份):

故此加入了双重挑战响应机制,来到了最后的5.0版本

5.0版本


最后得到了较为稳定安全的密钥建立协议

基于Diffie-Hellman的三方密钥建立协议


1.A选择一个随机大整数x,然后将g^x%n发送给B
2.B选择一个随机大整数y,然后将g^y%n发送给C
3.C选择一个随机大整数z,然后将g^z%n发送给A
4.A将(g^zx)%n发送给B
5.B将(g^xy)%n发送给C
6.C将(g^yz)%n发送给A
7.A将(g^yzx)%n发送给B
8.B将(g^zxy)%n发送给C
9.C将(g^yxz)%n发送给A
最后大家都得到了密钥g^xyz%n

基于口令的协议

1.在线字典攻击:加入图形码
2.离线字典攻击:加入salt

EKE协议

防止离线字典攻击:

前向安全签名

概念

把密钥的有效期分成时段,在每个时段的最后,签名者以一个单向的模式,从当前时段的秘密密钥得到一个新的下一个时段秘密密钥,并且安全地删除不再使用的秘密密钥。
整个密钥的生命周期里的公钥不改变,这个方法确保了泄露秘密的时段以前的所有签名的有效性。

解决问题

解决问题:一旦秘密密钥丢失,由这个密钥生成的以前所有签名都变得无效。

station to station 协议



即使得到x和y,也无法计算出k
存在攻击:未知密钥共享攻击

攻击者使用自己的签名替换第三条消息,攻击者对A使用假冒身份B,对B使用真实身份C. A以为与B通信,但B以为与C

零知识证明

设P表示掌握某些信息,并希望证实这一事实的实体
设V是证明这一事实的实体
假如某个协议向V证明P的确掌握某些信息,但V无法推断出这些信息是什么,我们称P实现了最小泄露证明
不仅如此,如果V除了知道P能够证明某一事实外,不能够得到其他任何知识,我们称P实现了零知识证明,相应的协议称作零知识证明协议

零知识证明特性

正确性

P无法欺骗V。换言之,若P不知道一个定理的证明方法,则P使V相信他会证明定理的概率很低

完备性

V无法欺骗P。若P知道了一个定理的证明方法,则P使V以绝对优势的概率相信他能证明

零知识性

V无法获得任何额外的知识

图同构

图同构的概念

百度百科概念,我不做解释
图论当中的术语,假设G=(V,E)和G1=(V1,E1)是两个图,如果存在一个双射m:V→V1,使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1,则称G和G1是同构的,这样的一个映射m称之为一个同构,如果G=G1,则称他为一个自同构
在同构意义下封闭的图族叫做图性质

图同构的困难性

图是否同构是NP完全问题,对于一个非常大的图,判断两个图是否同构是非常困难的。
对于图G1和G2,如果存在一个一一对应的函数F:F的定义域是G1的顶点集。F的值域是G2的顶点集。当且仅当[g1,g2]是G1中的一条边,[F(g1),F(g2)]才是G2中的一条边,称G1和G2同构的。

零知识证明

假设Peggy知道图G1和G2之间同构,Peggy使用下面的协议使Victor相信G1和G2同构:
(1)Peggy随机置换G1产生另一个图H,并且H和G1同构。因为Peggy知道G1和H同构,也就知道了H和G2同构。
(2)Peggy把H送给Victor。
(3)对如下两个问题Victor选择其中的一个,要求Peggy证明。但是,Victor不要求两者都证明。
证明G1和H同构,或者证明G2和H同构。
(4)Peggy按Victor的要求证明。
(5)Peggy和Victor重复步骤(1)至(4)n次

正确性证明

如果Peggy不知道G1和G2之间的同构性,Peggy就只能创造一个图或者与G1同构或者与G2同构。每一轮中Peggy只有50%的机会猜中Victor的选择。又因为Peggy在协议的每一轮都产生一个新图H,故不管经过多少轮协议Victor也得不到任何信息,他不能从Peggy的答案中了解G1和G2的同构性。图同构的零知识证明只具有理论意义,从实现来看,是不实用的。

Hamilton回路

Hamilton回路概念

在图论中,图G中的回路是指始点和终点相重合的路径,若回路通过图的每个顶点一次且仅一次,则称图G为哈密尔顿回路,构造图G的哈密尔顿回路是NPC问题

零知识证明

假定P知道图G的哈密尔顿回路,并希望向V证明这一事实,则:
(1)P随机地构造一个与图G同构的图W,并将W交给V
(2)V随机的要求P做下述两件工作之一:
1.证明图G和图W同构
2.指出图W的一条哈密尔顿回路
(3)P根据要求做下述两件工作之一:
1.证明图G和图W同构,但不能指出图G或者图W的哈密尔顿回路
2.指出图W的哈密尔顿回路,但不证明图G和图W同构
(4)P和V重复以上过程n次

正确性证明

协议执行完后,V无法获得任何信息是自己可以构造图G的哈密尔顿回路,因此该协议是零知识证明协议
事实上,如果P向V证明图G和图W同构,这个结论对V并没有意义,因为构造图G的哈密尔顿回路和构造图W的哈密尔顿图同样困难。
如果P向V指出图W的一条哈密尔顿回路,这一事实也无法向V提供任何帮助,因为求两个图之间的同构并不比求一个图的哈密尔顿回路容易。
在协议的每一轮中,P都随机地执行一个与图G同构的新图,因此不论协议执行多少轮,V都得不到任何有关构造图G的哈密尔顿回路的信息

盲签名

概念

所谓盲签名就是指签名人只是完成对文件的签名工作,并不了解所签文件的内容
而平常的签名内容,都是签名者对所签内容是知道的

特点

(1)签名者不知道所签署的数据内容
(2)在签名被签名申请者泄露后,签名者不能追踪签名

步骤

(1)申请者对待签名文件进行盲化
(2)签名者对文件签名
(3)申请者将签名后文件去盲,即可得到原始数据的签名

部分盲签名

概念

“部分”意味着待签名的消息是由签名申请方和签名方共同生成的
即待签名消息包括签名申请者提交的待签名消息和签名者提供的”身份消息”

改进

允许签名者添加一些诸如签名时间、签名有效期和对签署消息性质的说明性信息等内容
1.保证了待签消息对签名者的盲性
2.阻止了签名申请者提供非法信息而滥用签名
3.有效的保护了签名者的合法权益

公平盲签名

概念

可以在需要的时候让一个可信任第三方发布信息,允许签名人把消息——签名对和签名时的具体内容联系起来,实现对签名申请人的追踪

新特性

引入可信中心,通过可信中心的授权,签名者可追踪签名
在需要的时候让一个可信任第三方发布信息,允许签名人把消息——签名对和他签名时候的具体内容联系起来,揭开签名,实现对签名申请者的追踪

公平盲签名方案

方案1:
给定盲化的消息,仲裁者能让签名者有效识别出相应的消息签名对
方案2:
给定消息签名对,仲裁者能让签名者有效的鉴别出申请签名的用户,即识别出签名时的盲化消息

一次性签名

至多可以用来对一个消息进行签名,否则签名就可能被伪造,我们称这种签名为一次性数字签名

群签名

群的成员可以代表群进行签名,签名可用单一的群公开密钥验证。
一旦消息被签名,除了指定的群管理者,没有人能够确定该签名是哪个特定的群成员签署的。
特点:
正确性、匿名性、不可伪造性、不可关联性、可跟踪性、抗合谋攻击性、防陷害攻击

环签名

环签名是作为一种没有管理者的类群签名方案,环中任何一个成员都可以代表整个环进行签名
而验证者只知道这个签名来自这个环,但不知道谁是真正的签名者
特点:
无须设置
签名者的完美匿名性

组成结构

多个发送者
一个签名者
一个可信的第三方

非否认协议

概念

防止不诚实者否认他们参与了某项事务而拒绝承担相应的责任而设计的协议

功能需求

1.确保通信主体不能对通信事件抵赖
2.确保在协议执行的任何阶段,任何通信主体不能获得优于其他主体的好处

非否认服务

1.发送方非否认:提供一种保护使得发送方不能否认他发送过某条消息
2.接收方非否认:提供一种保护使得接收方不能否认他接受过某条消息
3.发送方非否认证据:非否认服务向接收方提供不可抵赖的证据,证明接受到的消息的来源
4.接收方非否认证据:非否认服务向发送发提供不可抵赖的证据,证明接收方已收到了某条消息

非否认协议的步骤

1.服务请求
2.证据产生
3.证据传递和存储
4.证据验证
5.纠纷解决

非否认协议性质

1.非否认性
2.可追究性
3.公平性
4.时限性
5.非滥用性

Zhou-Gollman协议


1.A发送密文c=Ek(m)、标签l、接受者名字B的签名。
B使用这个信息作为A在协议标识l下发送了Ek(m)的证据
2.B使用一个签名作为响应,表示在协议标识l下接收到了Ek(m)。
A将使用这个信息作为B在协议标识l下接收到了Ek(m)的证据
3.A接着把密钥K与协议标识l发送给可信服务器。
如果A进行欺骗而发送一个错误的密钥K’,他就不能得到他需要的证据,因为Ek(m)与K’不能提供证据说明A发送了m。
4和5中,A与B都可以从可信第三方获取密钥

最后,A可以证明B对消息m的正确性负责,且B可以证明A对消息m的正确性负责

公平交换协议

概念

要么每一方都得到他所期待的信息或者物品
要么每一方都没有得到任何有意义的东西
当一个系统涉及两个或者多个互不信任的主体,就必须要考虑满足所有主体的安全性
从主体利益的角度考虑,如果一个系统不会损害其中任何一个诚实主体的利益,那么该系统具有公平性
从交换结果考虑,如果在交换结束后,要么每一方都得到了他所期待的信息或者物品,要么每一方都没有得到任何有意义的东西,我们也认为系统具有公平性

基本要求

1.有效性:若两个参与者行为正确,在没有第三方干涉的情况下, 仍能获得各自所需要的东西
2.秘密性:交换必须保护用户的隐私信息
3.高效实用性:协议的效率要高,以保证实用性
4.不可否认性:在进行有效的交换后,交换的任何一方都不能对他所传递和收到的信息进行否认
5.公平性:在交换结束后,要么每一方都得到他所期待的物品,要么每一方都没有得到有意义的东西
6.终止性:在协议发生的任何时间,每个参与者都可以单方面的终止协议而不破坏协议的公平性
7.第三方可验证性:发生纠纷时第三方可以进行仲裁,对不诚实的一方可以进行制裁。
8.无滥用性:在多方公平交换模型中,参与交换的任意子集在协议的任何时刻,都无法向第三者证明他们有能力中止协议

秘密的同时交换

拥有第三方的秘密交换

1.A发送一份签名的副本给第三方
2.B发送一份签名的副本给第三方
3.第三方通知A,B已经收到所有人的签名副本
4.A签名两份副本,并发给B
5.B签名两份副本,然后给A一份,自己保留一份
6.A和B通知第三方已完成
7.第三方销毁自己手上的签名副本

第1~3步:第三方拥有每个人签名的副本,防止第4步,A签名后,B签名不给A

面对面同时签名

1.A签上自己名字的第一个字,然后发送给B
2.B签上自己名字的第一个字,然后发送给A
3.如此循环,直到签名结束
4.当交换多轮后,可以大致上认为两者都已经签名完成

非面对面同时签名

1.A和B就签约应当完成的日期达成一致意见
2.A和B确定一个双方都愿意的概率差,A的概率差为a,B的概率差为b
3.A给B发送一份p=a的已签消息
4.B给A发送一份p=a+b的已签消息
5.循环往复,直至p=1

如果这个协议不能顺利完成,任何一方都可以把合约拿给法官,并同时递上另一方的最后签的消息
最后法官在0和1之间随机选择一个数
如果这个值小于另一方签名的概率,则双方都接受合约约束
如果这个值大于另一方签名的概率,则双方都不受约束

非面对面同时签名(密码协议版)

1.A和B都随机选择2n个DES密钥,分成一对一对,共n对
2.A和B都产生n对消息
3.A和B都用自己选择的每对密钥加密自己产生的n对消息(每对中,左密钥加密左消息,右密钥加密右消息)
4.A和B互相交换自己加密的2n份消息
5.A从自己的每一对密钥中选择一个发送给B,共计n个密钥,利用不经意传输
6.B从自己的每一对密钥中选择一个发送给A,共计n个密钥,利用不经意传输
7.A和B都用自己收到的一半的密钥解密自己能解密的那一半消息,确保解密消息是有效的
8.A和B交替发送自己2n个DES密钥的第一个bit,并如此循环,直到所有密钥发送给对方
9.A和B解密剩下的那一半消息,得到签署的合约
10.A和B交换在5,6步不经意传输中使用的私钥,确保对方没有欺骗

电子选举

安全需求

1.只有经授权的投票者才能投票
2.每个人投票不得超过一次
3.任何人都不能确定别人投谁的票
4.没有人能复制其他人的选票
5.没有人能修改其他人的选票
6.每个投票者都可以保证他的选票在最后的选举计数中被计算在内
7.任何人都知道谁没有进行投票

基于盲签名的电子选举协议



1.投票者生成消息集M,内容包括n个参与选举的候选人和投票者个人的唯一标识符ID
2.投票者对消息集M进行盲签名
3.投票者将签名后的消息发送给可信第三方
4.可信第三方验证消息的正确性,即候选人是否正确,ID是否唯一,是否有重复投票
5.可信第三方用自己的密钥加密签名,反馈给投票者
6.投票者用可信第三方的密钥加密自己投票的人和自己的唯一标识符ID
7.投票者将加密结果包装成消息集M’
8.投票者将消息M’发送给可信第三方
9.可信第三方验证ID是否唯一,是否重复
10.可信第三方宣布投票结果

电子现金

攻击方式

1.超额花费(多重花费):多次使用同一笔电子现金
2.洗钱:商家从非法活动中获得电子现金,为隐藏电子现金的来源,伪造一个虚拟的交易账单
3.伪造:通过一些老的支付抄本,伪造有效的电子现金

安全需求

1.不可伪造性
2.私密性
3.不可否认性

使用一般盲签名的优缺点

改进版部分盲签名的优势

继续改进公平盲签名的优势

点击赞赏二维码,您的支持将鼓励我继续创作!
CATALOG
  1. 1. 前言
  2. 2. 基础概念
    1. 2.1. 破解算法的种类
    2. 2.2. 协议的特性
    3. 2.3. 安全协议的种类
    4. 2.4. 协议攻击手段
    5. 2.5. 安全协议的特征
    6. 2.6. Dolev-Yao 威胁模型
    7. 2.7. 常见攻击方式
  3. 3. 秘密的分割与共享
    1. 3.1. 秘密分割
    2. 3.2. 秘密共享—门限方案
    3. 3.3. 阈下信道
    4. 3.4. 比特承诺
    5. 3.5. 抛币问题
    6. 3.6. 智力扑克
    7. 3.7. 不经意传输
  4. 4. 认证与密钥建立协议
    1. 4.1. 关于身份认证
    2. 4.2. 建立一个拥有第三方的密钥建立协议
      1. 4.2.1. 1.0版本
      2. 4.2.2. 2.0版本
      3. 4.2.3. 3.0版本
      4. 4.2.4. 4.0版本
      5. 4.2.5. 5.0版本
    3. 4.3. 基于Diffie-Hellman的三方密钥建立协议
    4. 4.4. 基于口令的协议
    5. 4.5. EKE协议
  5. 5. 前向安全签名
    1. 5.1. 概念
    2. 5.2. 解决问题
    3. 5.3. station to station 协议
  6. 6. 零知识证明
    1. 6.1. 零知识证明特性
      1. 6.1.1. 正确性
      2. 6.1.2. 完备性
      3. 6.1.3. 零知识性
    2. 6.2. 图同构
      1. 6.2.1. 图同构的概念
      2. 6.2.2. 图同构的困难性
      3. 6.2.3. 零知识证明
      4. 6.2.4. 正确性证明
    3. 6.3. Hamilton回路
      1. 6.3.1. Hamilton回路概念
      2. 6.3.2. 零知识证明
      3. 6.3.3. 正确性证明
  7. 7. 盲签名
    1. 7.1. 概念
    2. 7.2. 特点
    3. 7.3. 步骤
  8. 8. 部分盲签名
    1. 8.1. 概念
    2. 8.2. 改进
  9. 9. 公平盲签名
    1. 9.1. 概念
    2. 9.2. 新特性
    3. 9.3. 公平盲签名方案
    4. 9.4. 一次性签名
    5. 9.5. 群签名
    6. 9.6. 环签名
    7. 9.7. 组成结构
  10. 10. 非否认协议
    1. 10.1. 概念
    2. 10.2. 功能需求
    3. 10.3. 非否认服务
    4. 10.4. 非否认协议的步骤
    5. 10.5. 非否认协议性质
    6. 10.6. Zhou-Gollman协议
  11. 11. 公平交换协议
    1. 11.1. 概念
    2. 11.2. 基本要求
    3. 11.3. 秘密的同时交换
    4. 11.4. 拥有第三方的秘密交换
    5. 11.5. 面对面同时签名
    6. 11.6. 非面对面同时签名
    7. 11.7. 非面对面同时签名(密码协议版)
  12. 12. 电子选举
    1. 12.1. 安全需求
    2. 12.2. 基于盲签名的电子选举协议
  13. 13. 电子现金
    1. 13.1. 攻击方式
    2. 13.2. 安全需求
    3. 13.3. 使用一般盲签名的优缺点
    4. 13.4. 改进版部分盲签名的优势
    5. 13.5. 继续改进公平盲签名的优势