凯哥stack

新冠接触者追踪(二) -- 苹果和谷歌的技术草案

getting-better

序言

在上一篇「 苹果和谷歌联手打造新冠接触者追踪应用? 」中详细介绍了MIT关于在保护隐私的前提下(不记录位置)新冠追踪的思路,近期苹果和谷歌成立的联合小组已经发布了详细技术方案的草案,本文针对该发布的草案做一个详细的解读,同时邀大家一起品味其精巧的设计和独特的思路,文中的技术方案和部分图片来源于苹果官网发布的「 新冠追踪技术草案 」。
该版本原始文件已经随苹果更新而删除,最新版本解读参考「 新冠接触者追踪(三) – 技术草案更新 」,有需要的小伙伴可以留言或者发邮件。

概念

在上述技术草案中,一共有三篇,分别是蓝牙协议设计、密码学的设计、系统API设计三部分,为了方便对整体的理解,这里先将几个概念做个说明。

RPI(Rolling Proximity Identifier) 定时滚动的接触追踪识别码,这个就是前篇博客提到的信标(beacon),安装了接触者追踪APP的手机,定时通过蓝牙向外广播该接触码,每10分钟变化一次。
DTK(Daily Tracing Key) 每日追踪密钥,每24小时变化一次。
TK(Tracing Key) 跟踪密钥,每个手机只生成一次,生成后固定不变。
DK(Diagnosis Keys) 诊断密钥,是一组每日追踪密钥的集合。
使用者 安装了新冠接触者追踪应用的使用者。

密钥的生成设计

接触追踪识别码RPI(Rolling Proximity Identifier)的生成过程:

Contact Tracing Bluetooth Specification v1.1

图1: Key Schedule for Contact Tracing, Contact Tracing Bluetooth Specification v1.1, Apple & Google

跟踪密钥TK(Tracing Key)的生成

32字节长度,每个手机生成后不变,通过算法保证每个用户唯一,应该通过某些用户ID标识通过加密算法生成,该密钥由操作系统组件生成,不容其他APP和服务接触到,来保障用户的隐私, 草案中未提及产生详细的细节。

每日追踪密钥DTK(Daily Tracing Key)

每日跟踪密钥,16字节长度,由跟踪密钥TK派生,其生成方法为:

Daily Tracing Key generated method, Contact Tracing Bluetooth Specification v1.1, Apple & Google

  • Di
    DayNumber,从Unix Epoch Time(1970年1月1日)到当前的天数,其算法如下:

DayNumber, Contact Tracing Bluetooth Specification v1.1, Apple & Google

  • HKDF
    HKDF算法为一种基于key的不可逆的hash算法,具体算法参考RFC5869,由于salt(盐值)为空,info为固定字符“CT-DTK”||Di,key使用TK,因此只要TK不变,每一天的DTK都是固定且可以计算的。

接触追踪识别码

定时滚动的接触追踪识别码,每10分钟变化一次,由蓝牙模块向外广播,生成方法如下:

Rolling Proximity Identifier generated method, Contact Tracing Bluetooth Specification v1.1, Apple & Google

  • dkti
    每日追踪密钥DTK(Daily Tracing Key),这里怀疑是笔误,应该是dtki

  • TINj
    TimeIntervalNumber,从每一天的0点开始初始化为0,每过10分钟累加1,取值范围[0,143],算法如下:

TimeIntervalNumber, Contact Tracing Bluetooth Specification v1.1, Apple & Google

  • HMAC
    HMAC基于key的不可逆的MD5算法,具体参考RFC5869,其中data参数为“CT-RPI”||TINi,key使用DTK,因此,只要得到DTK,每天的每一时刻的RPI都可以计算出来。

诊断密钥DK(Diagnosis Keys)

诊断密钥为确诊新冠患者上传的一组[DTK(Daily Tracing Key), 产生日期],一般是14对,从确诊向前推14天,每天的DTK和日期。

启发

  • 算法数据压缩之妙

    安装该APP的手机不需要记录自身发出的RPI,前面提到的,只要TK不变,每一天的DTK可以推算,每天每时发出的RPI都可以计算出来,对于确诊的患者,也不需要上传所有发出的RPI,只需要上传DTK和日期,接收者根据这组信息就可以计算出当天所有发出的RPI,不光手机端保存的数据减少,云上存储的数据大大降低,不得不赞叹该数据模型的美妙。

  • 隐私的保护

    除了不记录位置外,虽然RPI可以从DTK计算,但是由于确诊患者只会上传14天的DTK,除了这14内发送的RPI可以计算外,在14天之前,以及确诊以后时间的RPI无法通过计算得到,在减少数据量的前提下同时做到了完美的隐私保护。

  • 精巧的边缘计算

    在该数据模型下,云上存储的数据非常少,无论是用户通过蓝牙接收的数据,还是收到诊断密钥后的接触计算都是在用户的手机端进行,充分的利用了用户手机的存储和计算能力,除了能缓解云计算和存储资源外,更大成都的保护了用户数据的泄漏风险。

  • 不足之处

    一旦跟踪密钥TK(Tracing Key)被泄漏,该手机历史上产生的上述所有密钥都可被计算出来,TK + DayNumber -> DTKDTK + TimeIntervalNumber -> RPI,造成重大隐私泄漏问题,推测应该有更换机制,以备万一时可以更新来修复问题。

系统交互方式(续)

整个跟踪系统的工作模式,还是用原来的交互图来标示一下,如下图,大致分为5个流程,后面重点介绍前两个流程:

  • RPI(Rolling Proximity Identifier)广播
  • RPI(Rolling Proximity Identifier)扫描
  • 新冠确诊后上传DK(Diagnosis Keys)和对应的日期到云
  • 云推送DK(Diagnosis Keys)和对应的日期给其他使用者
  • 使用者手机本地计算接触信息给出报告或者预警

凯哥版权

图2: 追踪系统交互流程,凯哥stack

RPI广播过程

使用者的手机会定时发送RPI(Rolling Proximity Identifier),该信息通过Advertising Physical Channel PDU发送,类型为ADV_NONCONN_IND(Type 0x3),格式如下:

凯哥版权

图3: ADV_NONCONN_IND PDU,凯哥stack

在PDU的AdvData中承载RPI(Rolling Proximity Identifier),由3部分组成,其格式如下:

  • BLE通用探测模式
  • 16-bit 服务的UUID,固定为0xFD6F
  • 服务数据块,包含16字节RPI(Rolling Proximity Identifier)

Contact Tracing Bluetooth Specification v1.1

图4: The Contact Detection Service payload, Contact Tracing Bluetooth Specification v1.1, Apple & Google

广播流程如下:

如下图,所有带有Local后缀的均在本端手机,带有Remote后缀的均在对方手机:

  • 首先,如果手机第一次安装APP会产生一个跟踪密钥,每个手机只生成一次,生成后固定不变
  • 通过加密模块派生每日密钥,并通过每日密钥派生RPI(Rolling Proximity Identifier),每15分钟改变一次
  • 通过ADV_NONCONN_IND PDU广播,广播间隔大概200-270ms

Contact Tracing Bluetooth Specification v1.1

图5: Advertising Flow, Contact Tracing Bluetooth Specification v1.1, Apple & Google

RPI扫描过程

使用者的追踪APP会定时扫描的方式记录附近人的RPI(Rolling Proximity Identifier),并保存在自己的手机上,流程如下:

  • 每5分钟间隔启动扫描请求,获取ADV_NONCONN_IND PDU,检查服务UUID为0xFD6F的数据包
  • 解析数据包获取RPI(Rolling Proximity Identifier),并记录时间点和信号强度(便于识别时间和接触距离)

Contact Tracing Bluetooth Specification v1.1

图6: Scanning Flow, Contact Tracing Bluetooth Specification v1.1, Apple & Google

参考材料
[1]: https://www.apple.com/covid19/contacttracing

凯哥stack

著作权归作者所有,禁止转载


专题:

本文发表于 2020-04-24,最后修改于 2020-04-26。

本站永久域名kaige86.com,也可搜索「 凯哥stack 」找到我。

期待关注我的 ,查看最近的文章和动态。


上一篇 « Nginx+hexo建站小结 下一篇 » 新冠接触者追踪(三) -- 技术草案更新

推荐阅读

Big Image