一种简单易懂的基于计算量证明的 CAPTCHA

发表于： 2024-06-12

字数： 3016 阅读：≈ 7分钟浏览：评论：

之前我写过《一个基于工作量证明的CAPTCHA工具》，里面介绍的方法涉及到比较深的数学原理，实在是不适合普通程序员实现。

其实就算是我自己，实现起这个方法来也是很累，虽然我自己也封装了一个库，但有时候只是想轻量级地实现一下这类基于工作量证明的 CAPTCHA，引入一个额外的库是有一点麻烦。

本文就介绍了一个对于程序员来说非常简单易懂的基于工作量证明的 CAPTCHA 实现方法。

具体实现

首先服务器还是要生成一个类似任务的东西，客户端需要根据这个任务，生成对应的计算量证明。我们的计算量证明是基于散列算法的，这个任务可以是任意字符串。在下文中表述为 $Q$.

同时服务端会告知客户端一个难度系数 $n$. 接着，客户端按照下面的方法计算工作量证明：

计算 $n$ 个散列值，分别是 HASH(Q+str(1)), HASH(Q+str(2)) … HASH(Q+str(n))。这里的 Q + n 表示字符串相加.
接着我们得到了 $n$ 个散列值，分别是 $H_{1}…H_{n}$
取每个散列值的最后几个字节，然后将这些字节拼接起来，拼接结果就是工作量证明结果。
服务端收到工作量证明后，选择一个随机数 r，然后计算 HASH(Q+str(r))，然后将结果的最后几个字节数据与工作量证明中第 r 段数据进行比对，如果相同，则认为客户端通过了工作量证明。

举个实例

前端的计算

假设服务器给出的 $Q$ 是 "abc"，难度 $n$ 是 3，使用的散列函数是 SHA256，那么客户端可以计算得到 $H_{1}$…$_H{3}$：

1
2
3
4
5
6
H_1 = SHA256("abc" + "1" )= SHA256("abc1")
    = dbfcfd......e20d37
H_2 = SHA256("abc2")
    = 4bdd0b......71e968
H_3 = SHA256("abc3")
    = 851ca7......e3b59c

接下来取每个结果的最后两个字节，即

1
2
3
substr(H_1, -2) = 0x0d37
substr(H_2, -2) = 0xe968
substr(H_3, -2) = 0xb59c

然后将这三个结果拼接起来，得到 0x0d37e968b59c 这一串二进制数据。这段二进制数据就是工作量证明的结果。

后端的计算

后端生成一个随机数，r = 2，接着计算

1
2
SHA256("abc" + "2") = SHA256("abc2") = 
4bdd0bbfe3f4c52cc2c8ff02f1fef29663dd9938f230304915805af1fa71e968

取最后两个字节的数据，得到 0xe968
客户端提交的 0x0d37e968b59c 这串二进制数据中的第二段数据也是 0xe968，于是可以证实客户端确实完成了计算量证明。

原理详解

计算量的对比

首先我们看到，在上面的实例中，我们取 $n = 3$，于是前端计算了 3 次散列值，而后端只计算了 1 次散列值。前端所需要的计算量是后端的 3 倍。显然，前端所需的计算量是后端的 $n$ 倍。调整 n 的数值，我们就可以很轻松地设定工作量证明的难度了。

为什么能够实现工作量证明

后端只需要计算一次散列值，就可以确认前端有没有完成工作量证明，这似乎很反直觉，但仔细思考一下就会发现这其实是符合逻辑的。

我们从攻击者的角度来分析一下。如果我想绕过工作量证明，那就只能提供 $n$ 个随机数据作为工作量证明。当后端收到这个虚假的工作量证明之后，还是按照正常的流程，生成一个随机数 r，然后检查第 r 个散列值是否正确。

在上面的例子中，我们取散列值的最后两个字节，由于工作量证明是假的，后端的计算结果只有不到六万分之一（$\frac{1}{256*256}$）的概率会与假工作量证明相同，从而认为客户端通过了计算量证明。换句话说，攻击者只有不到六万分之一的概率能够“恰好”通过计算量证明的检查。

来看另一种情况，如果后端要求提供 $ n = 1000$ 的计算量证明，但攻击者投机取巧，计算了 500 个真实的散列值，然后随机生成了 500 个假的随机数作为计算量证明，将半真半假的计算量证明提交上来会发生什呢。

显然，攻击者需要的计算量只有原来的一半，但对于后端来说，选择哪一段数据进行检查也是随机的，所以后端只有一半的概率选取到真正的计算量证明进行验证，可见此时攻击者能够通过计算量证明的概率也只有一半，在期望上，攻击者能够通过计算量证明所需要付出的计算量仍然接近 $n = 1000$.

更深入的技术细节

取散列值的最后多少个字节？

在上面的例子中，我特别取了散列值的最后 2 个字节，这不是随意取的。如果只取 1 个字节的话，在攻击者提供虚假证明的情况下，无论 n 有多大，攻击者能够通过验证的概率都是 1/256.

如果要求 $n < 256$，那么只需要取散列值的最后一个字节即可。同样，如果取散列值的最后 3 个字节，那么 $n$ 最大可以达到 $ 256 * 256 * 256 = 16777216 $，前后端的计算量之比可以达到一千万倍，这再怎么说也足够了。

网络开销

在我自己的实现中，我取难度 $n = 10000$，意味着后端的计算量只有前端的万分之一。在这个参数下，我需要取散列值的后 2 个字节，总共有 10000 段散列值，长度共 20k 字节，经过 base64 编码后大约有 30KB.

这个数据量还是可以接受的，首先对于客户端来说，30KB 的数据也就一张素材图片的大小，而且只在特定的接口需要，完全不是什么问题。对于服务器来说就更不是问题了，这个流量对于服务器来说是下行流量，目前大多数云服务商对下行流量都是不收费的，完全不会造成额外的费用负担。

唯一的缺陷

唯一的缺陷就是无法抗并行计算的攻击。攻击者可以使用显卡并行计算散列值，从而更有效率地进行攻击。不过这个缺陷问题不大，使用下面提到的“一些使用的小技巧”，可以在一定程度上弥补这个缺陷。

一些实用的小技巧

如果某个 IP 地址频繁提交工作量证明，我们可以提高这个 IP 地址的工作量证明要求。这样可以在加大机器人工作量的同时，尽可能地地降低对正常用户的影响。当然也可以使用其他客户端追踪方法，不一定需要使用 IP 地址进行追踪。
将散列算法换成 scrypt 等内存密集型的算法，可以一定程度上抵御并发，并增加机器人的计算难度
使用轻微修改版的散列算法，比如，将 SHA256 中的某个常数改一下。这是一个非常鸡贼但有用的抗攻击方法。攻击者不知道改了哪个常数，甚至会被误导，死活没法计算得到正确的散列值。就算攻击者发现了这一点，他也很难用使用硬件进行加速，只能使用软件实现这个轻微修改版的算法。这进一步拉近了攻击者和普通用户之间的算力差距。

示例代码

下面是我自己在生产环境中使用的代码片段，一段前端的代码和一段后端的代码。这段代码还应用了一些实用的小技巧：

计算 HASH(Q + str(n)) 的时候，把 Q + str(n) 扩展了一下，在字符串尾部添加了一些额外的字符，增加每一个散列值的计算时间，这样可以控制客户端计算工作量证明所需要的时间。
服务器返回的 Q 并不是普通的随机字符串，而是随即字符串加上一些额外的信息，如用户编号、Nonce、时间戳、难度 $n$ 等。这样可以方便服务器进行额外的验证，同时由服务器来控制工作量证明难度。

前端 TypeScript 代码片段

 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
type vvCaptchaOptions = {
    // 服务端返回的问题
    question: string
    // 每一次要计算的散列数据的大小
    size?: number
    // 要计算的散列值数量
    count?: number

    onprogress? : (progress: number) => void
}



export default async function vvCaptcha(opts: vvCaptchaOptions) {
    // 1. 数据合法性检查
    if (opts.size === undefined) {
        opts.size = 1 * 1024
    }
    if (opts.count === undefined) {
        opts.count = 10000
    }

    if (opts.size <= 0) {
        throw new Error("size must be a positive number")
    }
    if (opts.count <= 0) {
        throw new Error("count must be a positive number")
    }

    // 2. 计算散列值
    const result = new Uint8Array(opts.count * 3)
    const textEncoder = new TextEncoder()
    for (let i = 0; i < opts.count; i++) {
        const dataChunk = opts.question + i.toString()
        let data = dataChunk.repeat(Math.ceil(opts.size / dataChunk.length))
        data = data.slice(0, opts.size)

        const hashRaw = await crypto.subtle.digest('SHA-256', stringToUint8Array(data))
        const hashArray = new Uint8Array(hashRaw)
        result[i*3+0] = hashArray[0]
        result[i*3+1] = hashArray[1]
        result[i*3+2] = hashArray[2]

        if (i % (Math.round(opts.count / 100) + 1) == 0) {
            if (opts.onprogress !== undefined) {
                opts.onprogress(i / opts.count)
            }
        }
    }

    // 将结果编码为 Base64
    const b64 = btoa(String.fromCharCode.apply(null, [...result]))

    return b64
}



function stringToUint8Array(str :string) {
    const uint8Array = new Uint8Array(str.length);
    for (let i = 0; i < str.length; i++) {
      uint8Array[i] = str.charCodeAt(i);
    }
    return uint8Array;
  }
  

后端 golang 代码片段

 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
// 验证一个问题数据的回答是否正确
func (vv VVCaptchaQuestion) IsValid(answer string, size, count int) (bool, error) {
	// 检查是否已经过期
	if vv.ExpireTime < int(time.Now().Unix()) {
		return false, errors.New("VVCaptcha 问题已过期")
	}

	// 检查回答是否正确
	r := rand.Int() % count
	ourAnswer := vv.Answer(r, size, count)
	theirAnswerBuf, err := base64.StdEncoding.DecodeString(answer)
	if err != nil {
		return false, fmt.Errorf("回答不是合法的 Base64 字符串: %v", err)
	}
	if len(theirAnswerBuf) < count*3 {
		return false, errors.New("回答长度不正确")
	}
	theirAnswer := theirAnswerBuf[r*3 : (r+1)*3]

	if ourAnswer[0] != theirAnswer[0] || ourAnswer[1] != theirAnswer[1] || ourAnswer[2] != theirAnswer[2] {
		log.Printf("VVCaptcha 回答不正确: ourAnswer=%v, theirAnswer=%v", ourAnswer, theirAnswer)
		return false, errors.New("VVCaptcha 回答不正确")
	}

	return true, nil
}