接收方匿名性保护

Broadcast

广播是保护接收者匿名性的方法,通过广播所有参与者都能收到消息,即使发送者也不知道接收者的身份。

性能

通常广播相比点到点通信会需要更高的吞吐量。

寻址

  • 显式地址(explicit address):并不总是必要的,例如IP协议的广播地址。用于减小广播的代价,但是难以提供匿名性。

  • 隐式地址(implicit address):接收者(addressee)站的属性,用于进一步处理。

    • 不可见地址(invisible address):即使同一个地址发送两次,也没有观察者能发现,即地址的重用看起来就像使用了另一个地址。

    实现方法:发送方和接收方协商密钥(公钥或私钥),解密后如果消息有意义,则就是发给自己的。

    • 可见地址(visible address):与不可见地址相反,观察者可以发现某些信息的地址相同。

    实现方法:发送方和接受方协商一个随机数添加在明文消息里,其他人就不知道消息是发送给谁的。

一些要注意的问题:

  • 使用不可见的隐式地址,如何判断解密后的消息有意义?

    1. 加tag,使用长度足够的tag就可以抗碰撞(生日悖论)

    2. 使用哈希或消息认证码,计算

      enc(random_num, msg, hash(random_num, msg))

      enc(key, msg, MAC(key, msg))

  • 使用可见的隐式地址,随机数的生成?

    • 需要注意每个随机数只能用一次,否则会导致linkable的问题
    • 因此通信双方可以协商使用同一个seed生成随机数
  • 不可见地址的代价比可见地址高很多,因为前者涉及到对每一条消息的解密,而后者只需要对比随机数。

地址分发(address distribution):根据地址与身份的关联性公开与否,可以将地址分为公开地址(public address)私有地址(private address)

public address private address
implicit invisible address 使用公钥加密,开销非常大。但是可以用于第一次通信时双方交换对称密钥或随机数seed。 私钥加密。开销大(但是当然比公钥加密小一点)。
implicit visible address 地址可见,且地址与身份之间的关联性是公开的,会暴露信息。不应该被使用。 获得对称密钥或随机数生成seed后可以使用。使用后需要更换随机数。

不可见公开地址的最高效的实现方法就是采用公钥加密系统

不可见私有地址的实现方法是私钥加密,因为私钥只有通信双发持有(private),且通信的地址是明文经过私钥加密生成的(invisible)。

可见私有地址的实现方法就是使用同一个seed生成伪随机数,每次通信使用不同的随机数。

BitMessage(一个广播的例子)

BitMessage是一个基于广播的消息系统,采用隐式不可见私有地址(implicit invisible private)。

地址是加密公钥和验签公钥的哈希值。

消息通过椭圆曲线加密、经过数字签名、添加工作量证明(proof of work)。

添加工作量证明是为了对抗Deny Service Attack。工作量证明的实现方法例如,要求hash(msg, random_num)的前几位全都是0,这时就要尝试所有随机数的可能,直到哈希值的开头符合要求。

消息的广播:

  • 基于P2P的结构
  • 存储-转发:结点存储消息,等待其他节点的请求然后转发消息。
  • 基于pull模型:结点向其他节点发送pull request来获得消息。

因此不仅提供接收者匿名性,还提供发送者匿名性,因为接收者从邻近的结点获得消息,并不知道最初的发送者是谁。

隐式不可见地址与加密

我们可以简单地用对称和非对称加密系统实现隐式不可见私有和公开地址。

此外还可以反过来,用隐式不可见私有或公开地址实现两种加密系统:发送双方协商某种机制,以最简单的为例,当接收方收到一条地址指向它的消息,记为1;若地址不指向它则记为0。按照顺序排列二进制串得到消息。至于公钥加密还是私钥加密,取决于地址的公开性。

还可以协商start code和end code来确定消息的类型。

问题:如果接收方的站收到来自不止一个发送方的消息,怎么保证来自某一个发送方的序列不被打乱?

Queries

广播向所有的接收者发送单独的消息;查询则是每个人都可以查询所有的消息。

消息的接收者发送查询请求来获得消息,pull-based。

查询方法(Private Message Service)

假设数据库有4个内存单元(memory cell),我们需要查询其中一个单元的数据,该数据库有多个副本。

攻击者模型中假设每个数据库服务器都是honest but curious的,即他们之间不会合作。但是为了保证每个数据库都不知道用户对哪一个数据感兴趣,不能直接查询对应单元,而是组合3个副本的不同数据单元的数据,在用户端计算目的数据(称为superposed query)。【整个数据库都应该被使用到,从而数据库服务器不知道哪个记录与用户有关。

组合的数据库数量(例子是3个)要权衡安全性和成本,因为使用越多服务器,成本越高,但是所有的数据库服务器合作的概率越低。

步骤:

  • 根据要查询的单元下标,确定set vector,查询位为1,其他为0。例如要查询D[2],则set vector = 0100,查询D[3]则为0010。
  • 生成两个随机数向量用于副本S1和S2,将set vector和这两个随机数向量异或,得到用于副本S3的向量。
  • 用这三个向量分别查询对应的数据库,向量中哪位为1就查询哪一个单元的数据。
  • 每个数据库把查询到的几条数据做异或得到一个和,返回给用户。
  • 用户计算三个数据库副本的返回值的异或值,就能得到目的单元的数据。

注意,客户端与服务端之间的通信需要加密(OTP)。

这种方法通常用于注册,而不是交换实际内容。

缺点

这种查询方法的开销很大:

  • 假设要查询x个数据库,则需要发送x个请求,产生x倍的数据量。
  • 每个数据库中要访问至少半数的记录。
  • 频繁的数据库更新困难,为了数据库的一致性,需要同步写请求。

改进方法

向量的生成改用伪随机数。缺点:失去了信息论安全性。

这样我们只需要给S-1个服务器提供不同的seed,给1台服务器提供完整的查询向量即可。

每台获得seed的服务器自己生成随机数,查询对应的存储单元并计算Sum。

假设S3服务器获得了完整的查询向量,则由他通知其他服务器,客户端需要查询信息。

  • 数据库服务器S1用seed产生伪随机数向量,计算查询结果的Sum,用OTP加密(OTP也使用同一个seed生成随机数)并转发给S2。
  • S2用seed产生伪随机数向量,计算查询结果的Sum,与来自S1的加密消息的异或,再用OTP加密并转发给S3。
  • S3用完整的向量查询,计算Sum与来自S2的加密消息的异或,再用OTP加密返回给用户。
  • 用户把结果和三个服务器的OTP密钥做异或得到结果。

这种方法减小了客户端与服务器之间的带宽,不论使用多少个数据库只需要一个请求和一个响应。(需要提前注册seed)

数据修改与查询

数据修改

考虑这样一种情况:用户已知消息m、m’,第一次通信中查询获得(m XOR m’),应该如何修改存储单元里的数据,使得下一次查询相同的两个数据单元时,能一次性找出这两个单元是否被修改。

思路是:在修改单元中的数据时不采用覆盖的方法,而是用新的数据与旧的数据做异或。这样,假如m’对应的数据单元被修改为m”,则存入的数据实际为(m’ XOR m”)。当用户下一次访问时,两个数据单元的返回值为(m XOR (m’ XOR m”)),把这个结果和第一次查询的结果相异或,得到新的消息m”。

如果没有发生修改,则异或结果为全0。

如果两个单元都发生修改,则查询结果为((m XOR m”’) XOR (m’ XOR m”)),用这个结果和第一次的查询结果相异或,得到(m” XOR m”’)。也即,如果异或后有意义,说明一个单元发生修改;如果没有意义,有可能两个单元都被修改,需要做进一步查询来获得新的值。

查询方法

使用上面的可重写的数据单元相当于使用了一个隐式地址。如果简单地采用上述方法,每次查询的都是同一个数据单元,相当于可见隐式地址。缺点是,对于服务器来说,每次的查询向量是固定的,被重写的单元与用户之间会产生链接性。

改进的方法是采用一组可重写的内存单元,每次使用不同的单元(hopping between memory cells),相当于采用了不可见隐式地址

实现方法:

引入一个固定的存储单元作为保留存储单元(reserved memory cell),用来确定下一次使用的(或者说跳到的)是哪一个数据单元。

  • 地址的拥有者给每个服务器提供一个伪随机数种子
  • 每个服务器在t时刻用产生的随机数替换其保留存储单元中的内容
  • 用户结合所有服务器上的随机数(XOR)来查询对应的单元的内容$S_{\sum\limits_s PBG(t)}$

使用一组存储单元

(PPT的补充内容)

hopping between memory cells $\rarr$ hopping between sets of memory cells

增加地址的数量,对于同一个地址使用多个存储单元,也即用多个单元来存储一条消息

容错

错误可能由以下原因引起:

  • 服务器故障停机
  • 攻击者试图让服务不可用
  • modifying attack

方法

  1. 向其他的服务器提交相同的query vector
  2. 对消息进行认证,从而用户可以检查完整性,检测modifying attack。检查时向不相交的几个服务器集合查询,或设置陷阱(为了检查问题而发送查询请求),比较响应结果。

应该具有的属性:

  • 不能暴露用户对哪个单元感兴趣
  • 目标实体不应该能分辨出普通请求和陷阱请求。

注意:

完整性被破坏并一定是DB服务器的问题,还有可能是在传输中被modifying attacker修改。

参考内容

Efficiency Improvements of the Private Message Service

发表评论

您的电子邮箱地址不会被公开。