干货 | 基于哈希函数的签名,Part-1

栏目: 数据库 · 发布时间: 6年前

内容简介:编者注:或许增加几点说明会让这篇文章变得更好读一点:(1)文中所讲的数字签名技术,就是我们在密码学中保证身份同一性所用到的最重要的工具。身份同一性的意思即是,如何证明某条消息就是“我”发出的,别人不能伪造,我也不能抵赖。虽然数字签名技术也会用到成对的密钥对,但与我们所说的公钥密码学重点却有所不同。(2)可以将本文视为思考密码学工具的一个教程或者范本,能耐心读下去,也就明白了密码学是怎么样一回事、我们在密码学中是如何思考的。回首近几年,我有幸经历了两个相互冲突、却又令人着迷的时代潮流变迁。第一个潮流变迁是:

编者注:或许增加几点说明会让这篇文章变得更好读一点:(1)文中所讲的数字签名技术,就是我们在密码学中保证身份同一性所用到的最重要的工具。身份同一性的意思即是,如何证明某条消息就是“我”发出的,别人不能伪造,我也不能抵赖。虽然数字签名技术也会用到成对的密钥对,但与我们所说的公钥密码学重点却有所不同。(2)可以将本文视为思考密码学 工具 的一个教程或者范本,能耐心读下去,也就明白了密码学是怎么样一回事、我们在密码学中是如何思考的。

回首近几年,我有幸经历了两个相互冲突、却又令人着迷的时代潮流变迁。第一个潮流变迁是:专家学者们耗费四十年设计的密码学,终于派上用场;从信息加密、 电话安全 、到加密数字货币,我们可以在生活的方方面面发现使用密码学的例子。

第二个潮流变迁是:所有密码学家已经做好准备,迎接以上 美好的幻灭

正文开始之前我得重申一下,本文所讲的不是所谓 量子计算启示录(末日预言) ,也不是要讲 21 世纪密码学的成功。我们要谈论的是另一件未成定局的事情——密码学有史以来最简单的(也是最酷炫的)技术之一:基于散列函数的签名。

干货 | 基于哈希函数的签名,Part-1

在 20 世纪 70 年代末,Leslie Lamport 发明了基于哈希函数(Hash Function,又称散列函数)的签名 ,并经过 Ralph Merkle 等人进一步改进。而后的很多年,这被视为密码学领域一滩有趣的“死水”,因为除了相应地产生冗长的(对比其他复杂方案)签名,基于哈希函数的签名好像没有什么作用。然而近几年来,这项技术似乎有了复苏的迹象。这很大程度归因于它的特性——不同于其他基于RSA或离散对数假设的签名,哈希函数签名被视为可以抵抗量子计算攻击(如 Shor's 算法)。

首先,我们进行一些背景介绍。

背景:哈希函数和签名方法

在正式介绍哈希函数签名之前,首先你得知道密码学中的哈希函数是什么。 哈希函数可以接受一串字符(任意长度)作为输入,经过“消化”后,产生固定长度的输出 。常见的密码学哈希运算,像是 SHA2SHA3 或  Blake2 等,经运算会产生长度介于 256 ~ 512 位的输出。

一个函数 H(.) 要被称作“密码学”哈希函数,必须满足一些安全性的要求。这些要求有很多,不过我们主要聚焦在以下三个方面:

  1. 抗-原像攻击 Pre-image resistance (或俗称“单向性”):给定输出 Y=H(X),想要找到对应的输入 X 使得 H(X)=Y 是一件“极度费时”的工作。(这里当然存在许多例外,但最棒的部分在于,不论 X 属于什么分布,找到 X 的时间成本和暴力搜寻相同。)
  2. 抗-次原像攻击 :这和前者有些微的差别。给定输入 X,对于攻击者来说,要找到另一个 X' 使得 H(X)=H(X') 是非常困难的。
  3. 抗-碰撞 :很难找到两个输入 X1, X2,使得 H(X1)=H(X2)。要注意的是,这个假设的条件比 抗-次原像攻击还要严苛。因为攻击者可以从无垠的选择中寻找任意两个输入。

我们相信所有本文提到的哈希函数示例都能提供上述的所有特性。换言之,没有任何可行的(甚至是概念上的)方法能破解它。当然这种情况也是会变的,如果破解的方法被找到,我们当然会立即停用哈希函数(稍后会讨论关于量子计算攻击的特例)。

我们的目标是使用哈希函数构造数字签名方案,因此简要回顾数字签名这个词能带来很大的帮助。

数字签名方法 源于公钥的使用,使用者(签署人)生成一对密钥:公钥和私钥。使用者自行保管私钥,并能够用私钥“签署”任何消息,从而产生相应的数字签名。任何一个持有公钥的人都能验证该消息正确性和相关签名。

从安全的角度来说,我们希望签名是不可伪造的,或是说“存在不可伪造性”。这意味着攻击者(没有私钥控制权的人)无法在某段消息上伪造你的签名。有关数字签名安全的更多定义请参阅 这里

Lamport 一次性签名

在 1979 年,一位名叫 Leslie Lamport 的数学家发明了 世界上第一个基于哈希函数的签名 。Lamport 发现只要使用简单的哈希函数,或是 单向函数 ,就可以构建出非常强大的数字签名方法。

强大的前提是,用户只需要做一次签名的动作就能保证安全性!后续会做更详细的阐述。

为了更好的讨论,我们假设以下条件:一个哈希函数,它能接受 256 位的输入并产生 256 位的输出; SHA256 哈希函数就是个绝佳的示范工具;我们也需要能产生随机输入的方法。

假设我们的目标是对 256 位的消息进行签名。要得到我们需要的密钥,首先需要生成随机的 512 个位字符串,每个位字符串长度为 256 位。为了便于理解,我们将这些字串列为两个独立的表,并以符号代指:

sk 0 = sk 1 0 , sk 2 0 , ...,sk 256 0

sk 1 = sk 1 1 , sk 2 1 , ...,sk 256 1

我们以列表 (sk~0~, sk~1~) 表示用来签名的 密钥 。接下来为了生成公钥,我们将随机的位字符串通过 H(.) 进行哈希运算,得到公钥如下表:

pk 0 = H(sk 1 0 ), H(sk 2 0 ), ...,H(sk 256 0 )

pk 1 = H(sk 1 1 ), H(sk 2 1 ), ...,H(sk 256 1 )

现在我们可以将公钥 (pk~0~,pk~1~) 公布给所有人知道。比如说,我们可以把公钥发给朋友,嵌入证书中,或是发布在 Keybase 上。

接着我们使用密钥对 256 位消息 M 进行签名。首先我们得将消息 M 重现为独立的 256 位元(Bit,又称“比特”):

M 1 , M 2 , ..., M 256 ∈ {0, 1}

签名算法的其余部分非常简单。我们从消息 M 的第 1 位至第 256 位,逐一相应在密钥列表中的其中一个密钥上取出字符串。而所选密钥取决于我们要签名的消息每一位(bit)的值。

具体一点地说,对于 i = [1,256],如果第 i 位的消息位元 M i = 0,我们会从 sk 0 表中选择第 i 个字符 (sk i 0 ) ,作为我们签名的一部分;如果第 i 位的消息位元 M i = 1,我们则从 sk 1 表进行前述过程(即,如果我们要对消息 M 中的第 3 位进行签名,而该位值为 0,则使用 sk 0 中的第三位,sk 0 3 ,作为我们签名的一部分)。对每个消息位元完成此操作后,我们将选中的字符串连接,得到签名。

过程如图示说明,因为部分过程化简,密钥和消息长度只有 8 个 bit(位元)。要注意的是,每个色块代表的都是不同的随机 256 位字符串。

干货 | 基于哈希函数的签名,Part-1

当某个用户(已经知道公钥 (pk 0 , pk 1 ))收到消息 M 和签名,她能够轻易地验证这个签名。我们以 s i 表示签名中第 i 个组成部分,用户能够检查相应的消息 M i 并计算哈希值 H(s i ) 。如果 M i = 0 ,则哈希值必须匹配公钥 pk 0 中的元素;如果 M i = 1 ,则哈希值必须匹配公钥 pk 1 中的元素。

如果签名中的每个元素经过哈希运算后,都能找到对应的正确部分的公钥,我们就会说这个签名是有效的。以下是验证过程图示,签名中至少有一个签名元素:

干货 | 基于哈希函数的签名,Part-1

如果你开始觉得 Lamport 的计划有些疯狂,你既是对的,也是错的。

首先探讨下这个数字签名方法的弊端。我们会发现, Lamport 方法的签名和密钥实在太大了,大约有数千 bits。而且更要命的是,这个方法存在严重的安全局限:每个密钥只能被用来签名一个消息,所以 Lamport 方法作为“一次性签名” 在这里被拿来举例。

这种安全局限为什么存在呢?回想一下, Lamport 签名表明了在各个消息位元上可能的两个密钥之一。假如只需要签署一条信息,这个签名方法完全没问题。然而,如果我签署了两条在每一个对应位置 i 的 bit 值都不同的消息,然后连同密钥一起发送出去,这可能导致大问题!

假设攻击者从不同的消息得到两个有效的签名,她便能够发起 “混合搭配(mix and match)”攻击,成功伪造签署第三条我从未签名过的信息。以下图示说明这个攻击过程:

干货 | 基于哈希函数的签名,Part-1

这个问题的严重程度取决于你签名的消息的相异程度,以及有多少消息被攻击者给截获了。但总的来说,这肯定不是件好事。

让我们总结一下 Lamport 签名方法;它很简单、快速,但它在实际应用上还有很多不足之处。或许我们可以做一点优化?

从一次性签名到多次签名:基于默克尔树 (Merkle's tree) 的签名

Lamport 签名方法是个好的开端,但是无法用单一密钥签名多条信息,是它最大的弊端。Martin Hellman 的学生 Ralph Merkle 由此得到大量启发,他很快地想到了一个聪明的解决办法。

虽然我们不打算在这里展开解释默克尔方法的步骤,我们还是来试着理清 Ralph 的想法。

我们现在的目标是用 Lamport 签名方法签署 N 条信息。最直观的方法是,以最初的 Lamport 方法生成 N 个不同的密钥对,然后将所有公钥关联起来,集合成一个超巨大的 mega-key。(mega-key是我现编的术语。)

如果签名者继续拿着这么一把密钥集合,她就可以对 N 条不同消息进行签名,严格上来讲这也只是一把 Lamport 密钥。看起来,这样就解决了密钥重用的问题。验证者也有对应的公钥能够验证所有收到的消息。没有任何的 Lamport 密钥被使用两次。

很明显的,这种方法很糟糕,因为时间成本太高了。

具体地说,上述这种天真的方法中,为了达到要求的签名次数,签名者必须分发比普通 Lamport 公钥还要大数倍的公钥(签名者还要继续拿着同样巨大的私钥)。人们很可能会对这种结果感到不满,也会反思有没有办法避免这种负作用产生。接下来,让我们进入 Merkle 方法。

Merkle 方法希望能找到一个能签署多条不同消息的方法,同时避免公钥的成本线性激增。Merkle 方法的实现如下:

  1. 首先,生成 N 个独立的 Lamport 密钥,我们以 (PK 1 , SK 1 ), ..., (PK N , SK N ) 表示之。
  2. 接下来,将每一个公钥分别放到 Merkle hash tree (见下图),并计算根节点哈希值。这个根节点就会成为Merkle签名方法中的 “主公钥”。
  3. 签名者报关全部的 Lamport 密钥(公钥和私钥),用于签名。

关于 Merkle tree 的更多描述请点击 这里 。概略地说,Merkle 方法提供了一种能收集不同的值,并用一个 “根” 哈希(例子中使用的哈希函数,长度为 256 bits)代表所收集的值的方法。给出这个根哈希,就能 简单“证明” 某个元素存在于这个给出的哈希树。而且这个证明的大小和叶节点数量成对数关系。

干货 | 基于哈希函数的签名,Part-1

- Merkle tree,来自维基百科的解释。Lamport 公钥被放进叶节点中,然后根节点成为主公钥。 -

要签名的时候,签名者从 Merkle tree 中直接选择公钥,并用对应的 Lamport 密钥签名。接着她将得到的签名结果连接 Lamport 公钥并附上“Merkle 证明”。Merkle root 可以来佐证该默克尔树中包含选中的公钥(即整个方法使用的公钥)。最后签名者将整个集合当作消息签名发送出去。

(验证者只要直接将这个“签名”分别解压为 Lamport 签名、 Lamport 公钥、 Merkle 证明,就能进行验证。验证者能够依靠拿到的 Lamport 公钥验证 Lamport 签名,并用 Merkle 证明这把公钥的确存在于 Merkle tree 中。只要满足这三个条件,验证者就能确信签名是有效的。)

这个方法的缺点是会将“签名”大小增加两倍以上。不过,现在 Merkle 方法主要的公钥只是一串简单的哈希值,使得这个方法比上面提到的原始 Lamport 方法更为简洁。

最后还有个优化部分,密码学强度的 伪随机数发生器 能够输出生成各式各样的密钥,同时“压缩”密钥数据本身。这使得原先庞大的位元(显然是随机的)能够转换为简短的“种子(seed)”。

很赞啦!

让签名和密钥更有效率一点

Merkle 方法使得一次性签名转变为 N 次性签名。构造这种方法仍然需要基于某些一次性签名方法,比如 Lamport 方法;但不幸的是,Lamport 方法的(带宽)成本仍相对高昂。

有两种主要的方法可以降低这些成本。第一种也是 Merkle 提出的 ;为了更好的解释许多强大的签名方法,我们优先说明这项技术。

回想一下 Lamport 方法,要对一条 256 位的消息进行签名,我们需要一个包含 512 个独立密钥(和公钥)位串的向量,签名本身就是 256 个密钥位串的集合。(这些数字会被需要签名的消息位元激活,位元可以是 "0" 或 "1" ,因此需要从两张不同的密钥表中提取适合的密钥元素。 )

这里引发了新的思考:如果我们不对所有的消息位元进行签名,会怎么样呢?

更详细点说,在 Lamport 方法中,我们通过输出密钥位串对一条消息的每个位元进行签名——无论它的值是什么。如果我们不要同时签名一条消息中 0 和 1 的位元,而是只签名 1 的位元,那又会如何呢?这么做能够将公钥和私钥的大小减半,因为我们可以完全丢掉整条 sk 0 列。

现在我们只有单一列位串的密钥 sk 1 ,...,sk 256 ,对消息的每个位元 M i = 1我们都会输出一个字符串 sk i ;对于消息的每个位元 M i = 0我们都会输出......无(因为许多消息都会包含很多的 0 位元,这么做能缩减签名大小,这些 0 位元将不再带来任何成本)。

这种方法的明显缺陷是:它 极度 不安全,所以请不要这么做!

举例来说,假设有个攻击者观察到一条已经被签名的消息,消息开头是“1111...”。现在攻击者想要在不破坏签名的情况下,将消息编辑成“0000...”,只需要删掉这条签名中的几个组成部分即可!简言之,虽然要将 0 位元“翻转” 成 1 位元很困难,但反之要将 1 换成 0 就非常简单了。

现在有了个解决办法,而且它非常巧妙。

让我们接着瞧瞧。虽然无法避免攻击者将消息中的 1 改成 0 ,但我们能发现这些改动。只要将一个简单的“校验和(checksum)”附加到消息上,然后将消息和校验和一起签名。对于签名验证者来说,她必须验证整份签名的两个值,也需要确定收到的校验和是正确的。

我们使用的校验和非常小:它由简单的二进制整数组成,表示原始消息中的所有 0 位元数。

如果攻击者试图修改消息内容(或是校验和),使得部分 1 位元变成 0 位元,并没有手段可以阻止她。但是这种攻击会增加消息中的 0 位元数,这会使得校验和无效,验证者从而会拒绝这个签名。

当然,机智的攻击者可能还会试图混淆校验和(校验和也和消息一起被签名),增加校验和的整数值来匹配她篡改的位元数。然而最关键的是,因为校验和是二进制整数,如果要增加校验和的值,攻击者势必得将一些 0 位元转换成 1 位元。又因为校验和也被签过名,这种签名方法从源头阻止这种转换(将 0 换成 1),因此攻击者无法得逞。

干货 | 基于哈希函数的签名,Part-1

(如果你继续记录下去,的确会增加被签名的“消息”的大小。在我们的例子中,一条 256 位的消息的校验和,需要额外的 8 位元及增加相应的签名成本。不过,如果这条消息包含许多 0 位元,这么做对于缩减签名大小仍然非常有效。)

原文链接: https://blog.cryptographyengineering.com/2018/04/07/hash-based-signatures-an-illustrated-primer/

作者:Matthew Green

翻译&校对:Ian Liu & 阿剑


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

UNIX网络编程 卷2

UNIX网络编程 卷2

W.Richard Stevens / 人民邮电出版社 / 2009-11 / 89.00元

《UNIX网络编程 卷2:进程间通信(英文版·第2版)》是一部UNIX网络编程的经典之作。进程间通信(IPC)几乎是所有Unix程序性能的关键,理解IPC也是理解如何开发不同主机间网络应用程序的必要条件。《UNIX网络编程 卷2:进程间通信(英文版·第2版)》从对Posix IPC和System V IPC的内部结构开始讨论,全面深入地介绍了4种IPC形式:消息传递(管道、FIFO、消息队列)、同......一起来看看 《UNIX网络编程 卷2》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

html转js在线工具
html转js在线工具

html转js在线工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具