Cache Missing For Fun And Profit

未分类

Colin Percival,2005
http://www.daemonology.net/papers/htt.pdf

Abstract

Hyper-Threading 技术从Intel Pentium 4被引入，即在一个processor上有多个执行的thread。Thread之间不仅共享了计算单元，还共享了缓存。共享的缓存提供了thread间的隐蔽信道，而且让恶意的thread可以观测其他thread的执行，在某些情况下可以读取密钥。作者向处理器设计者、OS提供者、密码软件编写者提供了解决这种攻击的方法。

Covert Channel Via Paging

virtual memory page 作为隐蔽信道
有两个进程，Trojan和Spy，他们在不同的权限级别上，可以访问一个大的reference file（只读）。Trojan读取reference file的某些page，从磁盘加载到内存时产生了page fault。之后Spy读取reference file的每个page，并对每次内存访问计时。对于之前Trojan已经读过的page，内存访问会快于没有读过的。因此Trojan可以利用一个page是否被读过，来向Spy传递一个比特的信息。
如果没有共享的reference file，可以fault page out of memory.Trojan和Spy都占据了超过一半的可用内存，OS使用LRU的page eviction策略。为了传比特1，Trojan读取自己所有的内存空间；为了传比特0，Trojan等待和之前相同的时间，但只读自己的一个page。同时Spy不断计算读取自己的内存空间的时间，当Trojan发1时，OS会把Spy的page evict掉，将磁盘中的数据换入内存，相比于0会有明显的时间差。
尽管第二种方法的传输率要慢的多，但表明了在没用共享文件的情况下用共享的缓存来通信。

L1 Cache Missing

Pentium 4有128条cache line，每条64字节，分为32个4路组相连。
128*64/4 = 2048 每2048个字节会进入同一路
Trojan分配2048个字节的数组，传递32 bit的信息时，如果第i个比特为1，就访问数组中的第64*i个字节
Spy分配8192个字节的数组，对于每个[0,32)中的i，计算读取字节64*i，64*i+2048,64*i+4096,64*i+6144所需的时间。这四个字节的地址会被缓存到同一路中.Trojan的内存访问会导致Spy拥有的cache line失效

Spy 代码

    mov ecx, start_of_buffer
    sub length_of_buffer, 0x2000
    rdtsc     #Read Time Stamp Counter 获得开机来的cpu时钟周期数，存在EDX:EAX中
    mov esi, eax
    xor edi, edi
loop:
    prefetcht2 [ecx + edi + 0x2800]  #预取数据，放入L2 cache中

    add cx, [ecx + edi + 0x0000]
    imul ecx, 1
    add cx, [ecx + edi + 0x0800]   #2048
    imul ecx, 1
    add cx, [ecx + edi + 0x1000]   #4096
    imul ecx, 1
    add cx, [ecx + edi + 0x1800]   #6144
    imul ecx, 1

    rdtsc
    sub eax, esi  #取得周期差
    mov [ecx + edi], ax  
    add esi, eax
    imul ecx, 1

    add edi, 0x40    # cache line size 64  bytes
    test edi, 0x7C0  # cache set size 2048 bytes
    jnz loop         # 32 sets

    sub edi, 0x7FE
    test edi, 0x3E
    jnz loop

    add edi, 0x7C0
    sub length_of_buffer, 0x800
    jge loop

L2 Cache Missing

OpenSSL Key Theft

OpenSSL在签名/解密，同时运行L1 Spy，
中国剩余定理加速RSA计算

Garner方程
    令x1  = x mod p, x2 = x mod q
    那么x可表示为 
    x = x2 + h * q,其中 h = (x1-x2)*(1/q mod p)mod p

RSA中计算C^d mod N

x = M
x1 = C^dP mod P = M ^{e*e^-1mod(Q-1)}mod P = M mod P
x2 = C^dQ mod Q = M ^{e*e^-1mod(Q-1)}mod Q = M mod Q
将mod N上的运算分为mod P和mod Q
再次优化

两个关键函数 BN_sqr和BN_mul BN_sqr要比BN_mul快一点,使用了不同的工作空间(Karatsuba乘法)，因此会在cache上留下不同的footprint

部分比特恢复

Solutions and Workarounds

cache fair share

code path and sequence of memory access related to data and key use