Dancing on the Lip of the Volcano: Chosen Ciphertext Attacks on Apple iMessage

CCA

Christina Garman,Matthew Green et al. Johns Hopkins University,Technical report

对端对端消息加密协议iMessage的安全性分析，可在2^18次查询下*回溯*解密某些iMessage消息

The iMessage Protocol
RSA-OAEP,AES128-CTR,ECDSA，在前人逆向的基础上

（ID_sender,ID_recipient,C1,C2,sig)
Apple维护一个目录，存储和分发用户id和公钥的对应关系
若干接收方的ID包含在plist
有附件(图片、视频)的消息：发送方生成256bit的AES key，将附件加密后传到云端，得到一个URL。将URL和key发送给接收方

Protocol Analysis
1. 公钥目录:单点故障，单账户多设备，单设备多账户
2. 前向安全、重放
3. 低版本与公钥目录通讯中缺少certificate pinning，可被MITM，修改接收方公钥
4. 非标准加密：缺少认证，可被替换签名

Attack on Encryption
1. 替换发送方签名
2. 修改AES密文

gzip DEFLATE算法变种，LZ77压缩 + Huffman编码
LZ77：滑动窗口，用之前窗口中出现过的字符串的开始下标和距离来编码字符串 < backward distance,length > 窗口最大值32KB,距离最大值258B
Huffman：所有字符(0~255)和length编码在一棵Huffman树中， 256 + 1(EOB) + 29 = 286个符号
因此压缩后的内容为 (huffman树T，符号集合S，CRC校验码C)

选择密文：假设攻击者得到了T，知道某个符号s在S中的偏移。因为是AES-CTR，对密文的异或就是对明文的异或，攻击者对s异或上某个掩码M,会出现以下情况

Case 1:s xor M解码后落在0~255，并且符号s没有重复出现过。修改后解出的内容与原来有一个字节的不同。
CRC的线性性 构造正确的CRC码 CRC(A xor B) = CRC(A) xor CRC(B)
枚举一个字节的所有值i，总会得到一个成功的解密
得到i后，若

decode(T,s xor M) = decode(T,s) xor i

只有唯一的解s，则成功恢复出明文的一个字节

Case 3-4：解出的内容与原来有多处不同，CRC码无法用之前的更正。尝试新的M

Case 2：符号s重复出现过，deflate引用之前的符号，导致解压出的内容与原来在s出现的地方不同。直接跳过这个符号s，选择下一个符号，或者对每个s可能出现的地方枚举

Case 5-7：5、7无解，跳过s。case 6类似于case 2

恢复Huffman树：
对于有附件的消息，解密成功后会自动请求对应的URL.得到url后可以获得关于huffman树的足够信息？？？

检测是否成功解密
解密成功后请求URL，本地网络中的攻击者可以观察到这一点;或者修改URL中的hostname成为攻击者控制的资源。

对附件消息的攻击
1. 替换签名
2. 改变sender id
3. 恢复Huffman 树
4. 恢复明文中的附件密钥
5. 恢复明文

Implentation and Evalution
MITM： pushproxy 拦截APN,mitmproxy 拦截TLS附件下载，都需要安装CA根证书

2^18次查询，恢复AES密钥232/256, 35小时，平均解密失败超时时间 390ms
其中418次查询是成功解密
模拟实验来探索攻击的有效性
skip encryption and decryption for performance

Mitigations
短期修复：
1. 检测RSA密文是否有重放
2. 重新生成公私钥对
3. Pin certificate
4. reorganize message layout:禁止gzip中huffman树的动态生成，发送方id应位于plist头部

长期修复：
1. 替换加密机制：如TextSecure/Axolotl protocol ,改进前向安全性和消息认证，
2. 实现key transparency

open question：
gzip format oracle
other protocol