CCNS2015-专题3(匿名通信技术)范例.ppt

Alice (A) Bob (B) Carol (C) 正 正 正 {相同}Kb {相同}Kb {不相同}Kb Alice要向Bob发送1001 问题1：如何抛币？ 方法：公正抛币协议 问题2：如何将消息发送给指定的人（比如Bob）？ 方法：用Bob的公钥加密结果 密码员进餐问题 Alice (A) Bob (B) Carol (C) 正 正 正 不相同 相同 不相同 Bob说谎，导致结果为NSA付帐，实际上是Carol在付帐。 密码员进餐问题是否存在问题？ 问题：如何检测这种恶意破坏？ 密码员进餐问题 更一般的推广 对每一位将要发送的消息，每个用户产生一个随机位，并发送给一个邻居节点 任一节点i知道两位信息：自己选择的随机位bi和一个邻居节点j的随机位bj 每一个节点（除发送节点外）通告自己所知道的的两个位的异或值结果：Ci＝bi XOR bj 发送者x通告以下结果：Cx=bx XOR bk XOR Mx 所有通告结果的异或值就是消息位 原因：每一位出现两次，在异或操作中被抵消 密码员进餐问题 上述协议的优点： 匿名性很健壮：即便部分主体合谋，也不能破坏匿名性 每一个协议主体均很难通过分析协议过程中的知识来破坏匿名性 上述协议的缺点： 成员间需要一个需要一个成对的信道（否则随机位信息无法被共享） 需要大量的通信和大量的随机位 需要可靠广播信道 无法抵抗恶意破坏者 密码员进餐问题 问题的提出： 协议参与者之间无法得到可靠的广播信道 －Disco舞厅内的嘈杂使得密码员之间无法听清楚别人的宣告内容。 Disco舞厅密码员进餐问题 问题的提出： 协议参与者之间无法得到可靠的广播信道 －Disco舞厅内的嘈杂使得密码员之间无法听清楚别人的宣告内容。 Disco舞厅密码员进餐问题 基本思路： （1）构造一个可靠广播信道：Byzantine General Problem （2）去除可靠广播信道的要求 （3）信道预留技术 两个阶段：第一阶段预留信道，第二阶段发送消息 Disco舞厅密码员进餐问题 通过随机路由来隐藏消息源 Crowds, Freenet, Onion routing 路由节点无法区分所收到的消息是来自真实的发送者或者来自其他路由节点 发送者 接收者 匿名与随机路由 WEB服务器 p 1-p p 1-p （1）路由节点形成一个随机路由路径 （2）诚实的路由节点采用抛币的方式决定将请求发送到web服务器或继续转发Routers Crowds System Crowds的匿名性： 观察者无法确定提交web访问请求的用户是真正的发送者还是一个转发者 观察者所看到的web请求的提交者是真正发送者的概率不会超过50% 概率清白（Probable innocence ）：真正发送者被视作发送者和非发送者的概率相同 Crowds System Crowds协议 STEP 1：发送者随机算则一个Crowds中的节点，采用其加密后发送给该节点 STEP 2：诚实节点收到消息后，利用公正抛币协议以概率p继续转发，则转STEP1；以概率1－p将消息直接提交给信宿。 Crowds的结论： Crowds中的节点数位n，其中有c个坏节点了；诚实节点转发消息的概率为Pf，则如果满足以下条件，Crowds满足概率清白： Crowds System R R4 R1 R2 R R R3 Bob R R R 与Crowds的区别： Crowds是随机选择路径 Onion是发送者控制路由路径的长度，并预先随机选择一条路由路径：某些路由节点是诚实的，某些可能是破坏者 Alice 来自Stanford课件 Onion Routing R4 R1 R2 R3 Bob Alice {R2,k1}pk(R1),{ }k1 {R3,k2}pk(R2),{ }k2 {R4,k3}pk(R3),{ }k3 {B,k4}pk(R4),{ }k4 {M}pk(B) 路由信息用路由节点的公钥加密 每个路由节点只能知道下一个路由节点的身份 来自Stanford课件 Onion Routing Free Haven project has an excellent anonymity bibliography /anonbib/ TOR (second-gene