云樾
踏浪而来
云樾

Tor共享随机子系统规范

1. 介绍

1.1 动机

对于下一代的隐藏服务项目,我们需要Tor网络每天以一种无法提前预测或被攻击者影响的方式产生一个新的随机值。目前我们需要使用此随机值使得HSDir哈希环变得不可预测,这应该能解决各种针对隐藏服务的DoS攻击,并使人们更加难以衡量目标隐藏服务的受欢迎程度及其相应的活动。此外,该随机值可以被其他需要全局随机性的系统所使用,例如与Tor相关的协议(OnioNS)或与Tor不相关的(warrant canaries,授权金丝雀

1.2 前期工作

提案#255指定了一个提交和发布协议(commit-and-reveal protocol),它可以作为外部脚本运行,并将结果提供给权威目录服务(DA)。但是DA管理员认为运行第三方脚本不安全,该脚本打开了多个TCP端口并接受来自因特网的连接。因此,该提案旨在将“commit-and-reveal”嵌入到Tor投票过程中,从而使部署和维护更加顺利。

2. 概述

该提案更改了Tor原本的共识协议,以便在常规投票过程中,DA们在每个午夜产生一个随机数。分布式随机生成器方案是基于commit-and-reveal技术。

该提案还详细说明了如何将最终的共享随机值嵌入共识文档中,以便需要它的Tor客户端能够获取它。

2.1 commit-and-reveal协议介绍

每天,在00:00UTC投票表决一致意见之前,各DA生成一个新的随机值并将其保留一整天。DA以加密方式散列随机值,并将输出结果称为“commitment”值。原始随机值称为“reveal”值。

其思想是,给定一个reveal值,你可以通过加密方式确认它是否对应于一个commitment值;但对于一个给定的commitment值,却不能反推出reveal值。这些值的构造在 [COMMITREVEAL] 章节体现。

2.2 协议总视图

我们的commit-and-reveal协议旨在每天 00:00UTC 产生一个新的共享随机值(Shared Random Value,SRV)。 最终的新共享随机值将被嵌入到共识文件中。

我们的协议分为两个阶段,并使用了Tor的每小时投票程序。每个阶段持续12个小时,这意味着每个阶段都进行12轮投票,简而言之该协议的工作方式如下:

  • Commit阶段:从 00:00UTC 开始,持续12个小时,DA每小时将他们的commitment包含在投票中, 投票中还包含任何收到的其他DA的commitment(如果有)。
  • Reveal 阶段:在 12:00UTC ,该阶段开始并持续到 00:00UTC 协议结束。 在这一阶段,DA必须揭示在上一个阶段提交的commitment值对应的reveal值。 其他DA的commitment和reveal值(如果有)也会添加到投票中。
  • 共享随机性计算:在00:00UTC,共享随机值通过约定后的reveal值进行计算并被加入到共识文件中。

这就结束了每天 00:00UTC的commit-and-reveal协议。

commit-and-reveal协议

2.3 我们如何使用共识? [CONS]

生成的SRV需要随时可供客户端使用,因此我们将它包含在共识文件中。每小时的共识文件都必须包含当天的SRV和前一天的SRV。这是因为根据提案224的[TIME-OVERLAP]部分,Tor客户端在给定时间可能需要这些值中的任意一个来访问隐藏服务。这意味着这两个值也都需要包含在投票中 。

因此共识文件中需要包括:

(a) 当前时间段的SRV

(b) 上一个时间段的SRV

因此需要一种新的SR共识方法来表明哪些DA支持这个新协议。

2.3.1. 在共识文件中插入共享随机值

投票结束后,我们需要注意如何选择将哪些共享随机值(SRV)放入到共识中,以免因DA对commit-and-reveal协议的观点不同而导致打破共识(因为也许他们错过了一些协议)。

因此DA们在生成共识文件之前会先查看收到的投票,并采取以下逻辑:

  • 首先,他们确保达成共识的共识方法高于SR共识方法。
  • 当且仅当SRV已由至少大多数其他DA投票通过时,该DA才将SRV纳入共识。
  • 对于 00:00UTC 的共识文件,当且仅当SRV已由至少AuthDirNumAgreements个DA(其中AuthDirNumAgreements是新引入的共识参数)投票通过时,DA才将SRV包含在共识文件中。

DA在共识中包含最受欢迎的且也符合上述限制的SRV,否则不应包含 SRV。

上述逻辑是为了使通过自然分割(?)来打破共识变得更加困难。

2.4 协议的持久化状态 [State]

DA们需要在正在运行的协议的磁盘上进行持久化操作。 这允许DA在重新启动时可以无缝地加入协议。

在Commit阶段,它由所有DA的commitment构成。 然后在reveal阶段,reveal值也存储在持久化状态中。

如前所述,当前和上一个时间段的SRV(如果有)也必须始终处于该持久化状态中。

2.5 协议说明

Tor官方手稿

该图显示了DA们(A_1,A_2,A_3)的投票结果。 链“ A_1-> c_1-> r_1”表示A_1提交的commitment值:c_1,以及其对应的reveal值:r_1。

该图仅描绘了整个协议的几轮。 它从Commit阶段的前三轮开始,然后跳到该阶段的最后一轮。

而后它从Reveal阶段的前两轮继续,然后跳到该协议运行的最后一轮。 最后,它显示了下一个协议运行(00:00UTC)的Commit阶段的第一轮,在该轮中,计算了最终的SRV。 在虚构例子中,SRV是用3个DA的贡献来计算的,其值a56fg39h

3. 协议

在本节中,我们给出协议的详细规范。 我们描述协议参与者的逻辑和他们发送的消息。 至于消息的编码在下一部分([SPEC])中指定。

3.1 Commit阶段 [COMMITMENTPHASE]

Commit阶段从 00:00UTC 持续到 12:00UTC。

在此阶段,DA会在其投票中提交一个值,同时也将其持久化到磁盘中。

DA还保存了任何收到的其他DA提交的处于持久化状态的commit值。 如果Alice的commit包含在Alice的投票中,我们称之为“权威的”。

3.1.1. Commit阶段的投票

在Commit阶段,每个DA在其投票中包含:

  1. 该协议运行的commitment值
  2. 从其他DA获得的任何权威的commitment
  3. 协议产生的前两个SRV(如果有)

整个Commit阶段持续12个小时,因此DA有多次机会提交其commitment值。 每个DA不得在Commit阶段的后续round中提交第二个commitment值(下一个round含义详见[2.5]中的图)。

如果一个DA在同一Commit阶段发布了第二个commitment值,则其他DA应只考虑第一个发布的commitment。 任何后续提交的commitment都必须被忽略!

3.1.2. Commit阶段的持续状态 [STATECOMMIT]

在Commit阶段,DA将从每个DA处收到的权威的commitment进行持久化存储。每个DA只能有一个commitment被认为是可信的且处于活动状态的(呼应上一节的一个阶段只能发布一个commitment,后续重复发布都会被忽略)。

3.2 Reveal阶段

Reveal阶段从12:00 UTC持续到00:00 UTC。 既然已经就commitment达成了共识,那么现在是DA公开其随机值的时候了。

3.2.1. Reveal阶段的投票

在Reveal阶段,每个DA都在其投票中包含:

  1. 先前在commit阶段提交的commitment值对应的reveal值
  2. 从其他DA处收到的所有commitment值和reveal值
  3. 协议产生的前两个SRV(如果有)

commitments集合已经在Commit阶段确定下来并且必须保持不变。DA不允许在该阶段更改先前已经定下来的commitments

3.2.2. Reveal阶段的持续状态

DA会持久化先前收到的权威的commitments,同时还会保存任何收到与先前commitments相对应且有效的reveal值。

需要注意的是,一个DA刚刚从另一个DA的投票中得到了一个reveal值,它必须等到下一轮投票时才能在其投票中包含这个reveal值。

3.3 在00:00UTC时SRV的计算

最后,在每天的00:00UTC,DA会计算一个新的共享随机值,并且必须将此值添加到共识中,以便Tor客户端可以使用它。

DA们使用[SRCALC]小节中规定的持久化状态下的reveal值来计算SRV。

DA们在 00:00UTC 时开始在投票中加入这个新的共享随机值,取代了之前运行的两种协议中的一种。 DA们也开始在共识文件中包含这个新的共享随机值。

除此之外,当局在 00:00UTC 时会像在Commit阶段的第一轮中一样正常进行表决([COMMITMENTPHASE]节)。

3.3.1. SRV计算方式 [SRCALC]

\begin{aligned}
{\it HASHED\_REVEALS}&=H(ID\_a\ |\ R\_a\ |\ ID\_b\ |\ R\_b\ |\ ...\ )\\
{\it SRV}&=SHA\textrm{--}256(“shared\_random”\ |\ INT\_8({\it REVEAL\_NUM})\ |\ INT\_4({\it VERSION})\ |\\
&{\phantom{SRV=SHA}}{\it HASHED\_REVEALS}\ |\ {\it PREVIOUS\_SRV})
\end{aligned}

其中ID_a是DA:’a’的身份密钥,而R_a则是其当前周期对应的reveal值

此外,REVEAL_NUM是此构造中reveal值的数量,VERSION是协议版本号,PREVIOUS_SRV是上一个SRV。如果先前并没有SRV生成,则PREVIOUS_SRV被设置成32 NUL(\x00)个字节。

为了保持HASHED_REVEALS中的顺序一致,所有的ID_a | R_a对都根据R_a值升序排列。

3.4 引导启动过程

[CONS] 所述,为使HSDir覆盖周期如提案224中所述正常工作,需要两个SRV。因此在系统引导启动(Bootstrap)完毕之前,tor客户端不能使用该子系统的随机性;也就是说,知道共识中包含两个SRV。这应该在三个00:00UTC共识生成之后进行,这需要48小时。

3.5 权威目录服务重启 [REBOOT]

该共享随机协议必须能支持在协议执行过程中权威目录服务的上下线。

在Commit阶段提交commitment然后下线的DA必须将其reveal值持久化到本地磁盘中,以便它如果在Reveal阶段中或之前返回,则它可以继续参与协议。持久化的reveal值必须带有时间戳,以避免在错误的协议运行时发送它。

错过Commit阶段的DA将无法再提交commitment,因此它也无法参与该运行协议。对于一个错过Reveal阶段的DA也是如此。但不参加协议运行的DA在生成投票时仍应保留收到的其他DA的commit和reveal值。

最后,DA们必须以这样一种方式实现它们的持久化状态:它们永远不会在同一协议运行中提交两个不同的值,即使它们必须在中间重新启动(假设它们的持久化文件被保留)。在 [STATEFORMAT] 上可以找到构造持久化状态(持久化文件)的建议方法。

4. 规范 [SPEC]

4.1 投票

本节描述commitments、reveals和SR值如何在投票中被编码,包含DA自己的commitments/reveals和从其他DA处收到的commitments/reveals。Commitments和reveals编码在投票的同一行,但reveals是可选项。

参与的DA需要包括以下行:

“shared-rand-participate”

在它们的投票文件中来表示它们参与了本次协议。

4.1.1. 计算commitments和reveals [COMMITREVEAL]

想要参与协议的DA需要在每次协议运行时生成一对commitment/reveal值,DA应该在当天的第一个Commitment阶段(00:00UTC)之前生成一对新的值。

Reveal值的计算方式如下:

REVEAL = base64-encode( TIMESTAMP || H(RN) )

其中RN是256位随机值的SHA3散列值。我们对随机值进行哈希处理以避免将PRNG中的原始字节暴露到网络中。(见 [RANDOM-REFS]

TIMESTAMP是一个8字节的网络字节序 time_t 值。 DA应将TIMESTAMP设置为他们最初计划将其commit到的投票中的valid-after时间(通常是在 00:00UTC,除非它们在以后的Commit round中启动)。

Commitment的计算公式如下:

COMMIT = base64-encode(TIMESTAMP||H(REVEAL))

4.1.2. 验证commitments和reveals [VALIDATEVALUES]

给定一个COMMIT消息和一个REVEAL消息,应该可以验证它们确实对应。 为此,客户端从REVEAL消息中提取随机值H(RN),对其进行哈希处理,然后将其与COMMIT消息中的H(H(RN))进行比较。 如果比较成功,我们说COMMIT和REVEAL消息相对应。

参与协议的DA还必须检查相应的COMMIT和REVEAL值是否具有相同的时间戳。

DA们应忽略在Reveal阶段中与Commit阶段中发布的commitment值不对应的reveal值。

4.1.3. 将commit/reveal编码入投票中

某DA将它自己产生的和从别的DA处收到的commitments和reveals放入其投票文件中。为此,它的投票中应包含以下内容:

“shared-rand-commit” SP VERSION SP ALGNAME SP IDENTITY SP COMMIT [SP REVEAL] NL

  • VERSION:创建commit所使用的协议版本
  • IDENTITY:DA的SHA1身份指纹
  • COMMIT:编码后的commit [COMMITREVEAL]
  • 处于reveal阶段的DA还能可选择地将编码后的reveal值(REVEAL)放入投票中

每个DA只能有一行,否则该投票被视为无效。最后ALGNAME是对应于计算COMMIT和REVEAL的哈希算法,在version 1中该算法为“sha3-256”。

补充下真实vote文件中的格式:

VERSIONALGNAMEIDENTITYCOMMITREVEALPHASE
1sha3-25614C131DFC5C6F93646BE72FA1401C02A8DF2E8B4AAAAAF+d+oBOK2Cw6KRBunLlqzRkDdn2EdbfL9wl3ho3BojifE8NJA==nullCommit
1sha3-25614C131DFC5C6F93646BE72FA1401C02A8DF2E8B4AAAAAF+d+oBOK2Cw6KRBunLlqzRkDdn2EdbfL9wl3ho3BojifE8NJA==AAAAAF+d+oCvwD/B2OveFij3LHEhGDXuxHuvDeBjAbgWy91wqNZGhg==Reveal

4.1.4. 共享随机值 [SRVOTE]

DA在其投票中包括一个共享随机值SRV,分别对上一个周期和当前周期的SRV使用如下编码:

“shared-rand-previous-value” SP NUM_REVEALS SP VALUE NL

“shared-rand-current-value” SP NUM_REVEALS SP VALUE NL

其中VALUE是以16进制编码的实际共享随机值(计算部分在 [SRCALC])

NUM_REVEALS是用于生成该SRV的reveal值的数量。

为了保持一致的顺序,上一个周期的共享随机值应该列在当前周期的值之前。

NUM_REVEALSVALUEprevious/current
8TdyTKjCDW0GzApCFZzJLb0YMjsCSHasHDp2MRfHRE5U=previous
9EyK5InmChr8o7c3loo2nyY2E31/Oy7D6pJalhsQAKuk=current

4.3 持久化状态格式 [STATEFORMAT]

作为本协议中保持状态的一种方法,DA必须保持协议的持久状态。

它包含preamble、commitment和reveal部分以及一个SRV列表。

preamble(或称之为header)部分包含下面内容:

“Version” SP version NL

[刚开始时,只有一次]

文档格式版本,在此规范内,版本为“1”

“ValidUntil”SPYYYY-MM-DDSPHH:MM:SSNL

[恰好一次]

在此时间之后,此状态将过期,并且不应被使用或信任。有效期到当前协议运行结束(即将到来的中午)

以下详细介绍了commitment和reveal部分,他们和在vote中的编码模式相同,这使得执行起来更加容易。

“Commit” SP version SP algname SP identity SP commit [SP reveal] NL

[每个DA一条]

最后是共享随机值部分:

“SharedRandPreviousValue” SP num_reveals SP value NL

[最多一条]

上一个周期的共享随机值

“SharedRandCurrentValue” SP num_reveals SP value NL

[最多一条]

当前周期的共享随机值

5. 安全性分析

5.1 commit-and-reveal协议的安全性以及未来的发展方向

commit-and-reveal协议的安全性已广为人知,并且具有某些缺陷。 基本上,该协议是不安全的,因为只要控制了b个权威目录服务的对手可以在2^b个结果中选择协议的结果。 然而,一个不是dirauth的攻击者根本不应该影响结果。

我们认为,特别是与目前的情况相比,这一制度提供了足够的安全保障。更安全的解决方案需要更先进的加密和更复杂的协议,所以这似乎是目前可以接受的解决方案。

以下是一些可能的未来方向示例:

  • 基于阈值签名的方案(例如,参见[HOPPER])
  • Lenstra等人的独角兽计划。 [UNICORN]
  • 基于可验证延迟函数的方案 [VDPS]

关于协作随机数生成的更多替代方法,另请参阅[RNGMESSAGING]上的讨论。

5.2 reveal阶段的SRV预测

Reveal阶段共持续12个小时,大多数DA会在Reveal阶段的第一个轮(12:00UTC~13:00UTC)中发送其reveal值。 这意味着攻击者可以在最终SRV生成之前约12小时对其进行预测。

这不会给HSDir哈希环带来问题,因为我们对HSDir节点施加了更高的正常运行时间限制(目前看要想成为HSDir至少得正常运行48小时),因此12小时的可预测性不是问题。

使用此系统共享随机值的任何其他协议都应该注意这个问题。

5.3 分区攻击

这种设计不能免疫某些分区攻击。我们相信它们不会给攻击者带来太多好处,因为它们很容易被发现,而且很难成功,因为攻击者至少需要破坏一台权威目录服务器。另外,由于拜占庭问题,很难(在某些情况下甚至不可能)防范所有此类攻击。然而,本节描述了所有可能的分区攻击以及如何检测它们。

5.3.1. commit阶段的分区攻击

恶意的DA只能将其commit发送给一个DA,这会导致该DA在计算SRV时具有额外的commit值,而其他DA没有这个值。 由于需要多数DA的共同决策才能形成共识,因此这不会影响最终的SRV值。 但是,攻击者可以使用此攻击在24:00计算SRV时从共识决策中删除单个DA。

攻击者还可以通过在Commit阶段将两个不同的commit值发送给不同的DA来划分权威目录服务。

以上所有内容都很容易检测。 来自一个DA的投票中的commit值在不同的DA之间都应相同。 如果不是这样,则表示攻击正在进行或产生非常严重的错误(极不可能)。

5.3.2. Reveal阶段的分区攻击

让我们考虑一种情况:Alice是一个恶意的DA。爱丽丝可以等到Reveal阶段的最后一轮,然后向半数DA发送他的reveal值。这将把DA分成两组:一组认为最终的SRV应该包含这个新的reveal值,而另一组不知道。这将导致最后共识决策发生平局并生成两个不同的SRV。

类似的攻击也可能发生。例如,在Reveal阶段结束前两轮,Alice可以只向一半的DA发送她的reveal值。这样,在最后一轮的揭晓阶段,一半的DA会在他们的投票中包含这个reveal值,而另一半则不会。在Reveal阶段的最后,一半的DA将计算出一个不同于另一半的SRV。

我们认为这种攻击并非特别有效:Alice最终有两个SRV可供选择,这也是commit-and-reveal协议的一个基本问题(因为最后一个人总是可以中止reveal或继续reveal)。攻击者也可以破坏共识,但在当前的投票系统中,还有其他方法可以做到这一点。

此外,我们认为这种攻击非常嘈杂且可检测。首先,它要求DA破坏两个共识,这将引起相当大的噪声。 此外,DA需要发送不同的投票给不同的授权,这是可检测的。 与Commit阶段的攻击一样,此处的检测是确保来自某个DA投票中的commit值在不同的DA处始终相同。

6. Q&A

6.2 为什么commit-and-reveal协议要持续24小时?

读者可能想知道为什么我们要在一整天(24小时)内使用该协议,因为仅仅只需要3轮就足以生成一个共享随机值。

我们决定这样做,是因为所以来的tor投票协议也是以每小时为周期。

我们可以只在每天21:00到00:00间执行共享随机协议,亦或者一天内执行多次。

然而,我们决定,由于共享随机值无论如何都需要包含在每个共识文件中,并且在其中承载commitments/reveals值也不是个大问题。而且,这样我们可以为出现问题的DA提供更多恢复和重新加入协议的机会。

6.3 如果00:00UTC产生共识失败,为什么我们无法恢复?

如果 00:00UTC 产生共识失败,那么意外着一整天的共识文件里都不会有当前的SRV。从理论上讲,我们可以通过计算当天 01:00UTC 的SRV来恢复。 但是,添加此类恢复逻辑的工程问题太大了。 例如,对于刚刚启动的DA来说,要了解一个特定的共识是否创建失败并不容易。

参考

声明:转载文章《Tor共享随机子系统规范》请务必注明出处,谢谢

发表评论

textsms
account_circle
email

云樾

Tor共享随机子系统规范
阐述Tor隐藏服务v3协议中所使用的共享随机子系统规范。
扫描二维码继续阅读
2020-11-29