Contact Tracing 技术实现解析

为了更好地应对 covid-19,AppleGoogle 联合发布了一项技术:「 Privacy-Preserving Contact Tracing」,在保护用户隐私的前提下,追踪联系人。这里的联系人不是通讯录里的联系人,而是真实世界中有过联系的人,更确切地说是在蓝牙范围内的人,路上并肩的行人也属于这个范畴。「追踪」是为了当有人确诊后,可以找到有过近距离接触的人,以便告知该信息。

Apple 和 Google 给出的技术方案从宏观来看是:把设备信息通过蓝牙传递到其他手机上,当有人确诊后,将 ta 的设备信息上传到云端,再推到其他手机上,通过比对本地保存的其他设备信息和接收到的设备信息是否匹配,来判定手机 owner 是否存在被感染风险。

为什么选择低功耗蓝牙,一个是主流移动设备基本都配备了该能力,这样就方便跨设备,甚至跨操作系统通信;同时低功耗可以避免给手机带来性能影响;蓝牙属于近场通信,也非常适合 covid-19 的场景。

其次设备信息这么传递,如何保障隐私不被泄漏呢,我们来看下这个问题

如何避免设备信息传递带来的隐私泄漏风险

如果设备信息就是固定的手机的 udid,或者对应的映射,攻击者就可以利用这个指纹做文章(比如查看另一个人的手机,看是否有某台设备的 udid,以确定两个人是否近距离接触过,或者持续监控/跟踪某台设备)。因此这里的 Key 应该是变的,同时又跟设备紧密相关,别人无法仿造和解密。白皮书里涉及到了 3 个 Key:

image|496x500

Tracing Key (以下简称 TK)

一个设备只生成一次,保存在本地,不会被上传。它的目标是足够随机,不会与其他设备产生的 TK 冲突。

Daily Tracing Key(以下简称 DTK):

一天生成一次,一天内不变,从 Tracing Key 派生而来,使用 HKDF 密钥算法(将较短的密钥生成较长的密钥,同时保证随机性),这个算法使用原始的密钥(Tracing Key)作为输入,使用 DayNumber 作为变量,因为 DayNumber 一天内不变,所以 DTK 一天内也不会变。

image|690x124

这个 Key 的设计目标是隐藏 TK(外部无法根据这个 Key 推测出 TK),同时不会与其他设备的 DTK 冲突。

Rolling Proximity Identifier(以下简称 RPI)

一个广播周期内(比如 10 分钟)生成同一个 HMAC(密钥散列消息认证码)

image|690x61

dkti 表示当天的 Daily Tracing Key,也就是 SHA-256 哈希函数的入参 TINj 表示 TimeIntervalNumber,也就是当天第 j 轮广播周期,比如 10 分钟为一个周期(换一次 RPI)

image|690x104

j 的取值区间就是 [0,143]

RPI 的设计目标是隐藏 DKT,同时支持 DKT 的验证(当某个人确诊后,可以通过 ta 的 DKT 计算 RPI 来验证)。

如何发送 RPI

前面提到的 3 个 Key,只有最后一个 RPI 会发送到其他设备上(TK 永远不会离开设备,DTK 只有确诊后才会提取其中的一个子集作为 Diagnosis Key),RPI 通过蓝牙发送到其他设备(关于低功耗蓝牙协议的说明,可以参考这篇文章)。

发送(广播)流程如下: image|629x500

这里的通信双方分别是:advertiser(广播数据包)和 scanner(扫描响应包),前者在广播时间间隔内会不断广播数据,这些数据中会包含 RPI,scanner 接收到广播数据后会将 payload 中的 RPI 保存到本地。等切换到下一个时间窗口后,会生成并广播新的 RPI。跨天会以新的 DTK 为基础,生成并广播新的 RPI。

这个过程使用的是 Beaconing 协议,也就是接收方无需应答广播者的数据包,只要默默地把数据记下来就行。一个设备同时是广播者和扫描者。

关于空间占用

一个 RPI 的长度是 16 字节,所以空间消耗非常少,即使接收到了 10000 个 RPI,也只会占用 156 K 的空间。但还是要有一个 Rotation 的机制,毕竟时间太长的 RPI 意义已经不大了。

这里还有一个潜在的风险是攻击者可以伪造大量的 RPI 数据给 Scanner,虽然每个 RPI 只有 16 字节,但仍有潜在的存储风险。所以 Scanner 的 scan 行为持续时间不能过长/过频繁,这同时也能节省电量。

如何接收 RPI

对于 Scanner 来说,流程更加简单,只要存储收到的 RPI 即可。如果云端有推送 Diagnosis Keys(确诊者上传的 DTK),就对它使用 SHA_256 算法(结合 TimeIntervalNumber), 将结果与本地存储的 RPI 比对,如果 match,就有被感染的风险,系统会推送通知提醒。

image|690x468

关于 API

苹果和 Google 都放出了 API Interface,虽然没有具体的实现,但光是对比两家的 API 接口就能看出点门道,这个环节个人认为 Google 做得更好,苹果很「意外」地没有使用 Swift 来提供 API,OC 那冗长的语法和 Block,给 API 的友好度打了折扣

image|388x500

相比之下 Google 的 API 看着就舒服多了

image|396x500

小结

这个设计非常巧妙,不仅保护了用户隐私,也减少了服务端的压力,对于服务端只需存储和下发 Diagnosis Keys,不需要计算 Key 与 Key,Key 与设备之间的关联。设备也不会有很大的存储和计算压力。从扩展性来看,将来如果有类似的近距离传播流行病,可以复用这套技术。但 Android 设备因为众所周知的原因在国内推行这套基建会比较困难。

发散一下

这个设计中,主要用到了蓝牙和加密哈希算法,苹果在 iOS 13 中的 Find My 也是基于蓝牙和加密协议来实现的,使得手机即使处于离线状态(不要关机就行),依然可以被定位。原理是要拥有至少两台苹果设备(共享私钥),然后每台设备都以一定间隔发送不断变化的公钥,当被周边的苹果设备获取到后,该设备(就像一个跳板)会用这个公钥来加密当前的地理位置信息,上传到苹果服务器,另一台设备就可以用私钥来解开这个加密信息,得到地理位置。这个过程中上传地理位置的设备信息不会暴露(因为压根就没有上传),别人无法解密这个信息,因为基于蓝牙传输,也不需要依赖网络,不得不说也是非常精巧的设计。