介绍

论文介绍

《Clock around the clock:Time-based device fingerprinting》是一篇发表在2018年CCS(CCF-A)上的论文。前几天写材料看了这篇论文,觉得思想还挺大道至简的。用师兄的话说就是,可能如果你想到这idea,做都没做就觉得不work然后放弃了的那种…

作者是Iskander Sanchez-Rola,来自西班牙德乌斯托大学(University of Deusto)。

作者在文中提出了C语言本地提取指纹的方法以及通过Web远程提取指纹的方法CryptoFP。本地提取指纹的方法比较准确,而通过Web提取指纹的方法不够准确,作者在文中提到:the result of this experiment show that the web imple- mentation of our technique is less precise than the native imple- mentation, due to a more coarse-grain precision offered by the HTML5’s performance.now timer.

复现情况

这里我复现的是文中提到的Web指纹的方法。因为这篇论文的核心算法比较简单,所以复现只花了一天时间。但是效果不是很理想…

核心思想

本文的核心思想就是通过测量特定函数在目标设备上的执行时间,用多次测量的运行时间放大目标设备的细微的时钟差异,将运行时间矩阵作为指纹特征矩阵来标识一个设备。

client – fingerprint --> server

主要工作

指纹生成阶段

  1. 利用crypto的相关函数,比如作者采用的是js的window.crypto.getRandomValues 函数。进行m次实验,每次实验中用n个不同的参数调用getRandomValues函数,得到n个数据,每个数据代表的是执行函数所花费的时间。

  2. 最后得到一个n×m的矩阵。具体来说,一列表示m次实验中的一次实验,一列共有n行,也就是n个数据。矩阵的第i行表示取出每次实验中的第i个数据。

这里我在代码实现的时候,由于时间是毫秒,我怕精度不够,就乘了个100.

[0.10.120.140.10.120.13.........0.10.120.13](1)\left[ \begin{matrix} 0.1 & 0.12 & 0.14 \\ 0.1 & 0.12 & 0.13 \\ ... & ... & ... \\ 0.1 & 0.12 & 0.13 \end{matrix} \right] \tag{1}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
code for the paper: "Clock around the clock: Time-based device fingerprinting"
@author: l3t1tb3
*/


let config = {
m: 50, // row of fp, 50
n: 1000, // column of fp, 1000
};


/*
* user defined API:
* two dimentional array to string
*/
Array.prototype.toStr = function() {
let arrLen = this.length;
let arrStr = "[";

for (let i = 0; i<arrLen; i++) {
arrStr += "[";
for(let j=0; j<this[i].length; j++){
arrStr += "" + this[i][j] + ",";
}
arrStr += "]";
if (i < arrLen - 1) {
arrStr += ",";
}
}

arrStr += "]";

return arrStr;
};


/*
* generate fingerprint for your device
*/
let gen_fp = (config) => {
// init fp
let fp = new Array();
for (let i = 0; i < config.n; i++) {
fp[i] = new Array(config.m);
}

// measure m round with n times each
for (let i = 0; i < config.m; i++) {
for (let j = 0; j < config.n; j++) {
stTime = performance.now(); // this api is much accurate than Date.now()
measureFunc(j); // the crypto function
edTime = performance.now();
logTime = edTime - stTime;

fp[j][i] = logTime*100; // the time interval is too small, so we enlarge it by 100 times
}
}

fp = fp.toStr();

return fp;
};


/*
* call the cryoto function
*/
let measureFunc = (j) => {
let array = new Uint32Array(j);
window.crypto.getRandomValues(array);
};


/*
* post fingerprint to server
*/
let post_fp = (fp) => {
$.ajax({
url: '/post/fp',
type: 'post',
dataType: 'json',
data: {
"fp": fp
}
}).done(function(data){
console.log("[+] successfully: ", data);
if(data["result"] === "True"){
$("#ip").text(data["ip"]);

let fpLike = "";
for(let i=0; i<data["fp-like"].length; i++){
fpLike += data["fp-like"][i] + ","
}
$("#fp-like").text(fpLike);
}

}).fail(function(xhr, status){
console.log("[-] failed: ", xhr, status);
});
};

指纹比较阶段

  1. 首先,定义一个函数GetNumCoincidences。对于指纹fp1,为每一行计算这行的众数,也就是计算出每次实验中第i个数据组成的数组的众数,保存到数组fp1_mode中。

    接下来需要统计fp2中包含了fp1对应行众数的行数量,将结果保存到变量num_coindences。也就是说,对于fp2的每一行,如果在该行中存在数据与fp1_mode[i]相同,则num_coindences+=1,并继续判断下一行

  2. 最后,分别统计fp2中包含了fp1对应行众数的行数量以及fp1中包含了fp2对应行众数的行数量,将二者的结果求和,并除以行数的两倍(n×2),与阈值t进行判断。超过阈值时,说明两种情况总的行数量> t×总的行数量,则判定为两个指纹是同一个设备。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class CompareFP(object):                                                                                                             
"""
Tool for comparing two fingerprints
"""
def __init__(self, m=50, n=1000, t=0.5):
self.m = m
self.n = n
self.t = t # threshold

def get_mode(self, arr):
counter = Counter(arr)
counter = sorted(counter.items(), key = lambda kv:(kv[1], kv[0]), reverse=True)

return counter[0][0]

def get_num_coincidences(self, fp1, fp2):
# generate fp1_mode for each row in fp1: n×m, e.g. n rows and m columns
# a row means all the ith data in the experiments of m times
fp1_mode = []
for i in range(self.n):
fp1_mode.append(self.get_mode(fp1[i]))

num_coincidences = 0
for i in range(self.n):
check = False
curr_mode = fp1_mode[i]
for j in range(self.m):
if check:
break
if fp2[i][j] == curr_mode:
num_coincidences += 1
check = True

return num_coincidences

def fp_check(self, fp1, fp2):
num1 = self.get_num_coincidences(fp1, fp2)
num2 = self.get_num_coincidences(fp2, fp1)
num = num1 + num2
ratio = num / (self.n * 2)
print("[+] ratio:", ratio)
res = ratio >= self.t

return res

实验

实验设置

用实验室主机,自己的笔记本电脑和手机进行了测试。(没设备呀…

PC系统浏览器
实验室主机win10Chrome 86.0.4240.75
笔记本电脑win10Chrome 80.0.3987.132
笔记本电脑win10Firefox 72.0.2
手机Android 10.0.0.168Quark 4.3.3.145

实验结果

实验效果并不理想。可能是哪里的细节没处理好。

  1. 首先,自己的实验室主机和笔记本去访问server,得到的两个指纹的ratio为1。

    1说明不管是fp1 vs fp2还是fp2 vs fp1,当前指纹的每一行都有与另外一个指纹每一行的众数相同的存在。

    看了下从前端post上来的指纹数据,确实有很多数据是一样的。

  2. 在笔记本的Firefox上得到的测量数据,很多都是0,非0的数据都是100。由于大部分都是0,因此从Firefox上提取出来的指纹矩阵,每一行的众数肯定是0。

    1
    2
    >> gen_fp(config)
    "[[100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100,0,0,0,0,0,0,0,0,0…"
  3. 手机的指纹可以很好地和电脑(台式机、笔记本)区分开。

尝试改进

指纹比较的准确度

用众数来判断一行中相同的item数量

由于作者在论文中提到的是用fp1每行的众数来判断fp2包含对应众数的行的数量。

可能fp1中第i行的众数为x,尽管这个x只在fp2第i行出现过1次,但是num_coincidences的数量也会自增1。这种方法的条件过于宽松。

因此,我第一次尝试是将这部分的思路改成了:用fp1每行的众数来判断fp2每一行里等于该众数的item数量。只要有相同的,num_coincidences就自增1。相应的,在fp_check()函数里,分母就要变成self.n * self.m * 2。因为第一次比的时候,num是在n×m的矩阵中得到的,第二次将fp2作为基准,用fp1去比较的时候,num也是在n×m的矩阵中得到的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class CompareFP(object):     
...
def get_num_coincidences(self, fp1, fp2):
# generate fp1_mode for each row in fp1: n×m, e.g. n rows and m columns
# a row means all the ith data in the experiments of m times
fp1_mode = []
for i in range(self.n):
fp1_mode.append(self.get_mode(fp1[i]))

num_coincidences = 0
for i in range(self.n):
curr_mode = fp1_mode[i]
for j in range(self.m):
if fp2[i][j] == curr_mode:
num_coincidences += 1

return num_coincidences

def fp_check(self, fp1, fp2):
num1 = self.get_num_coincidences(fp1, fp2)
num2 = self.get_num_coincidences(fp2, fp1)
num = num1 + num2
ratio = num / (self.n * self.m * 2)
print("[+] ratio:", ratio)
res = ratio >= self.t

return res

第一次用实验室主机访问[0],第二次笔记本的Chrome访问[1],第三次用笔记本的Firefox访问[2],第四次用笔记本的Chrome访问。可以看出,第四次访问的时候,相同设备的结果[1]和[2]明显比不同设备的结果[0]要来的大。可以尝试设置不同的阈值,来保证准确率。

两个fp对应位置相同时num_coincidences自增1

还有另外一个思路,就是判断两个指纹矩阵对应位置的数值相同时,num_coincidences才自增1。访问的顺序和上面的一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class CompareFP(object):     
...
def get_num_coincidences(self, fp1, fp2):
# generate fp1_mode for each row in fp1: n×m, e.g. n rows and m columns
# a row means all the ith data in the experiments of m times
fp1_mode = []
for i in range(self.n):
fp1_mode.append(self.get_mode(fp1[i]))

num_coincidences = 0
for i in range(self.n):
for j in range(self.m):
if fp1[i][j] == fp2[i][j]:
num_coincidences += 1

return num_coincidences

def fp_check(self, fp1, fp2):
num1 = self.get_num_coincidences(fp1, fp2)
num2 = self.get_num_coincidences(fp2, fp1)
num = num1 + num2
ratio = num / (self.n * self.m * 2)
print("[+] ratio:", ratio)
res = ratio >= self.t

return res

可以看出,条件更为严苛以后,ratio的值更低了。这种方法条件又过于严苛。所以还是上面那只用众数来判断一行中相同的item数量的方法好一些。

去除噪音

前面实验结果提到,Firefox上的测量结果效果不理想,指纹矩阵中大部分的数据都是0,可能是API在Firefox底层实现和Chrome不同的原因。

显然,对于其他的设备而言,只要一行中出现了0,那么行数统计结果num_coincidences肯定会自增1。最后很有可能求出来的ratio就超过了0.5,导致算法判定两个指纹属于同一个设备。: (

尝试修改,在前面用众数来判断一行中相同的item数量的代码基础上修改,将0作为噪音剔除。当这行全是0的时候,仍然返回0。

1
2
3
4
5
6
7
8
9
10
class CompareFP(object):     
...
def get_mode(self, arr):
counter = Counter(arr)
counter = sorted(counter.items(), key = lambda kv:(kv[1], kv[0]), reverse=True)
if counter[0][0] == 0 and len(counter) >= 2: # here, 0 is noise, we'd better remove it.
return counter[1][0]

return counter[0][0]

访问顺序和上面的实验相同。可以看出,这次能更好地区分开。

不过问题还是很明显,就是同一个设备的矩阵相似ratio只有0.4几…

矩阵比较

另外,作者在比较指纹矩阵的时候,用了众数来判断。其实还可以尝试从矩阵的相似度这个角度进行比较。

作者的建议

作者在文中提到Web的计时API performance.now()不够精确是导致Web指纹准确率不够理想的原因之一。并提出了一些建议:

  1. 不使用HTML自带的计时API,而是其它的技术。比如利用Schwarz等人提出的时钟插值技术
  2. 利用WebAssembly,一个旨在引入一个新的二进制格式的web应用程序。不仅可以提高CryptoFP的web版本的精度,而且可以使用任何函数实现web版本。这个API将允许编译C/C代码,以及其他的,以及使用公共硬件能力以本地速度执行它。这项技术目前处于早期阶段,但将来可以用来完全实现本地指纹识别方法。(其实可能是允许开发人员自己在web端去调用一些C、C的函数,然后更精确地去计时。)

总结

《Clock around the clock:Time-based device fingerprinting》这篇18年的CCS顶会论文有种大道至简的思想。仅通过一个crypto函数的运行时间,就能作为设备的指纹信息。

在这里我对这篇文章的主要方法做了一个简单的复现,代码在我的仓库中: Clock around the clock:Time-based device fingerprinting

可能的原因:

  1. 文中哪里提到的trick我没注意到
  2. 作者由于篇幅的原因没有把trick写到文中
  3. measureFunc那边调用函数的方式有问题。文中只提到把j作为参数传进去,但是传进去以后做了什么操作并未提及
  4. 我只是为了复现这个算法,实验只用了两三个设备,从结果上来讲可能会出现一些特殊情况
  5. Web的计时API performance.now()如文中所说的不够精确

疑惑:

  • 比较奇怪的是,Firefox里调用measureFunc后的结果几乎都为0,唯一的不为0的数全是100。
  • 后来看这篇论文的PPT,发现作者PPT上的指纹比较思路和我在改进那边提出的用众数来判断一行中相同的item数量不谋而合。但是PPT里的指纹比较算法和论文里的不一样呀。

局限:

  • measureFunc在执行的过程中不能被操作系统的调度程序中断。因此,太大的函数可能经常被中断,影响测量结果。太小的函数计时又不够准确。
  • 本文的方法依赖于计时的准确度,也就是测量运行时间的函数API的精确度。
  • 阈值t=0.5,是作者经过实验得到的。可能只适用于当前的数据集,有点过于理想。

Q&A(作者在会议上做pre时的提问与回答):

  • 移动设备是否可行?移动设备的浏览器缺乏相关的API

  • 笔记本设备的电池电量会影响实验结果吗?会,笔记本电量低时cpu会降频,指令执行时间会变长

    我记得HTML5有个获取电量的API。能否把电量作为参考因素之一,然后结合电量与cpu频率的关系,计算出与执行时间的关系

  • Apple设备是否可行?(作者在论文中只提到了Linux, windows)作者未进行实验,但是根据时钟差异的原理,本文方法理论上是可行的

    另外,对于利用函数执行时间来生成指纹的方法,计算机中的时间测量准确度是一个相当重要的因素。如果能在本质上提高时间测量的准确度,已有的方法肯定可以提高一个档次。

ok,就先到这里吧,我去看论文去了。XD