这是关于随机预言模型系列文章的第五部分。 点击如下链接查看之前的文章:

第一部分: 介绍

第二部分: ROM 的形式化,方案和证明简介

第三部分: 我们如何滥用 ROM 来使我们的安全证明工作

第四部分:ROM 使用案例

大约八年前,我开始写一篇特别不够正式的文章,讨论一种特定的密码建模技术,称为“随机预言模型”。 这要追溯到2011年的美好时光,那是一个密码学更加天真和温和的时代。 当时没有人预见到我们所有的标准密码学最终都将被弄的漏洞百出; 你不需要被提醒“加密就是密码学”的意思。 人们甚至用比特币来购物。

第一篇随机预言的文章不知怎地就出现了三个结局,并且一个比一个更荒谬。 我想,在某种程度上,我对整件事感到很尴尬——说实话,这件事挺俗气的——所以我有点半途而废打算放弃了。 这是我后悔的主要原因之一,因为我一直计划要发表第五篇文章,也是最后一篇文章,来结束这一团糟的事情。这篇文章将是本系列文章中最好的一篇,也是我一直想写的一篇。

为了给你提供一些上下文,我会简要地说明随机预言模型是什么,以及你为什么应该关心它。 (当然你最好还是读读这个系列的前几篇文章。)

随机预言模型是一种对哈希函数进行建模的疯狂方法,我们假设这些函数实际上是随机函数,并利用这一假设来证明密码协议中的一些事情,如果没有这样一个模型,这些事情是很难证明的。 几乎所有我们今天使用的“可证明的”密码学都依赖于这个模型,这意味着如果这些证明是“错误的” ,那么这些证明中的许多东西将会受到质疑。

为了梳理这篇文章的其余部分,我将引用第四部分的最后一段话,以下面的内容结束:

你看,我们一直都知道这次旅行不会永远持续下去,我们只是觉得我们还有更多的时间。不幸的是,末日即将来临。就像莱昂纳多·德·卡普里奥在《盗梦空间》无聊的情节中探索的那个虚构的城市一样,随机预言模型在自身矛盾的压力下崩溃了。

正如我之前所承诺的那样,这篇文章会讲述那次“崩溃”,以及它对密码学家、安全专家和我们其他人意味着什么。

首先,为了使这篇文章更加自成一体,我想回顾一下我在本系列文章前面讨论过的一些基本内容。 如果你读过前面的几篇文章,你可以跳过这一部分。

我们将(很快)提醒读者什么是哈希函数,什么是随机函数,什么是随机预言

正如在本系列的前几篇文章中所讨论的,哈希函数(或哈希算法)是计算机科学的许多领域中使用的标准原语。 它们接受一些输入,通常是一个可变长度的字符串,并可重复地输出一个短的、固定长度的“摘要”。 我们经常这样表示这些函数:

加密哈希使用这个基本模板并利用加密应用程序所需的一些重要安全属性。 最著名的是,它们提供了一些众所周知的属性,比如抗碰撞性,这是数字签名等应用程序所需要的。但哈希函数在密码学中到处都会出现,有时出现在意想不到的地方,从加密到零知识协议,有时这些系统需要更强的特性。 这些有时很难用形式化的术语表示: 例如,许多协议需要一个哈希函数来产生极其“随机”的输出。 

在可证明安全性的早期,密码学家意识到理想的哈希函数的行为类似于“随机函数”。 这个术语指的是从所有可能的函数集中均匀采样的函数,这些函数具有适当的输入 / 输出规范(域和范围)。 在一个完美的世界里,你的协议可以,例如,在设置时随机抽取大量可能的函数中的一个,将该函数的标识符放入一个公钥或其他什么东西中,然后你就可以开始工作了。

不幸的是,在实际协议中不可能真正使用随机函数(适当规模的域和范围)。 这是因为抽样和评估这些函数的工作量太大了。

例如,使用很少的256位输入并生成256位摘要的不同函数的数量是令人难以置信的(2 ^ {256}) ^ {2 ^ {256}。简单地“写下”你所选择的函数的恒等式将需要在函数输入长度中呈指数级的内存。由于我们希望我们的加密算法是有效的(意思是,稍微正式一点,它们在多项式时间内运行),使用随机函数几乎是不可用的。

所以我们不使用随机函数来实现哈希。 在“现实世界”中,我们使用比利时人或国家安全局开发的奇怪函数,比如 SHA256、 SHA3和 Blake2。 这些函数具有极快的运算速度和微小的算法来执行计算,其中大多数只占用几十行或更少的代码。 它们当然不是随机的,但据我们所知,输出看起来相当混乱。

尽管如此,协议设计者仍然渴望使用真正的随机函数能够给他们的协议带来安全性。 他们会问,如果我们折中一下,结果会怎样?如果我们使用随机函数来建模我们的哈希函数——只是为了编写我们的安全证明——然后当我们实现(或“实例化”)我们的协议时,我们将使用高效的哈希函数,比如SHA3,会怎么样呢?当然,这些证明并不完全适用于实例化的实际协议,但它们可能仍然很好。

使用这种范式的证明被称为随机预言模型(ROM)中的证明。 关于 ROM 如何工作的完整机制,可以翻阅我之前发表的该系列文章。 你现在需要知道的是,在这个模型中的证明必须以某种方式绕过,即计算一个随机函数需要花费大量指数级的时间。 这个模型处理这个问题的方法很简单: 它没有给每个协议参与者一个关于哈希函数本身的描述(哈希函数对任何人来说都太大了) ,而是给每个参与者(包括对手)一个神奇的“预言” ,这个预言可以有效地评估随机函数 H,并将结果返回给他们。

这意味着任何时候其中一方想要计算函数,他们自己并不能独自完成。 相反,它们会调用第三方,即“随机预言”,“随机预言”拥有一个巨大的随机函数输入和输出表。 在高层次上,这个模型看起来有点像下面这样:

因为系统中的所有参与方都与同一个预言在“对话” ,所以当他们要求预言对给定的消息进行哈希时,都会得到相同的哈希结果。 对于真正的哈希函数来说,这是一个相当好的替代函数。 使用外部的预言可以让我们“掩盖”评估随机函数的成本,这样就没有人需要花费一个指数级的时间来评估一个函数。 在这个人工模型中,我们得到了理想的哈希函数,而且没有任何麻烦。

这看起来已经很可笑了……

绝对是这样!

然而,我认为在你认为随机预言模型是个空洞的事物之前,你应该知道几件非常重要的事情:

1. 当然,每个人都知道随机的预言证明不是“真的”。 大多数认真的协议设计者都会承认,在随机预言模型中证明某些东西是安全的,并不意味着它在“现实世界”是安全的。 换句话说,随机的预言模型证明是伪造的这一事实,这并不是我想让你们知道的秘密。。

2. 总之: ROM 证明通常被认为是一种有用的启发式方法。 对于那些不熟悉“启发式”这个术语的人来说,“启发式”是一个成年人用来保护你毕生积蓄的词,因为他们使用的密码学无法证明任何事情。

OK,开个玩笑! 事实上,随机预言证明仍然是很有价值的。 这主要是因为它可以经常帮助我们检测方案中的缺陷。 也就是说,虽然随机预言证明在现实世界中并不意味着安全性,但不能编写这样的证明通常是协议的危险信号。 此外,ROM证明的存在有希望表明协议的“核心”是正常的,并且任何现实世界中出现的问题都与哈希函数有关。

3. 经过ROM验证的方案在实践中有着相当不错的记录。 如果 ROM 验证每隔一天就会提出一些荒谬而被破坏的方案,我们很可能就已经放弃了这种技术。 然而,我们使用的密码学几乎每天都在 ROM 中得到验证(仅仅是验证) ,而且大多数情况下它确实奏效。

这并不是说,当用特定的哈希函数实例化时,经过 ROM 证明的方案从未被破坏。 但通常情况下,这些破坏是因为哈希函数本身明显存在缺陷(正如 MD4和 MD5不久前都break 掉时所发生的情况) ,尽管如此,这些缺陷通常可以通过简单地切换到一个更好的函数来进行修复。 此外,从历史上看,实际攻击更可能来自明显的缺陷,比如发现哈希碰撞破坏了签名方案,而不是来自某种奇特的数学缺陷。 这就让我们注意到了最后一个关键的点..。

4. 多年以来,许多人相信只读存储器实际上是可以被保存的。 这种希望是由这样一个事实驱动的:即 ROM 方案在实现了强哈希函数时似乎工作得很好,所以也许我们所需要做的就是找到一个哈希函数,使 ROM 证明变得有意义。 一些理论家希望像密码混淆这样的奇特技术能够以某种方式使具体的哈希算法运行良好,使(某些) ROM 证明可以实例化。 

所以这就是 ROM 的状态,或者至少是直到20世纪90年代末的状态。 我们知道这个模型是人造的,但它固执地拒绝爆炸或产生完全无意义的结果。

然后,在1998年,一切都变糟了。

CGH98: 一个“不可实例化”的方案

对于理论密码学家来说,随机预言模型的真正破裂点来自于 Canetti,Goldreich 和 Halevi (以下简称 CGH)在1998年发表的一篇 STOC 论文。 我打算把剩下的时间来解释他们发现的要点。

CGH 所证明的是,实际上,有一些加密方案可以在随机预言模型中被证明是完全安全的,但是,当你用任何具体函数实例化哈希函数时,这种安全性就会变得非常危险。

这是一个非常可怕的结果,至少从可证明的安全社区的角度来看是这样。 从理论上来说,你的证明可能不够有力,这是一回事。 而另一回事则是,你要知道,在实践中,有些方案可以直接通过你的证据,就像终结者渗透到抵抗组织,然后以最严重的方式在你身上爆发。

在我们详细介绍CGH及其相关结果之前,有几点需要注意。

首先, CGH很大程度上是一个理论结果。解决这个问题的密码“反例”方案通常看起来不像我们将在实践中使用的真正的密码系统,尽管后来的作者提供了一些更“现实”的变体。事实上,这些变体是被设计用来做一些“真实的”方案不会做的但却是非常“人为的”事情。这可能会导致读者会以“人为的”这一理由对它们不屑一顾。

这种观点的问题在于,外表并不是判断一个方案的特别科学的方法。 如果证明是正确的,那么“真实的”和“人为的”方案都是有效的密码系统。 这些具体的反例的要点是故意做“人为的”事情,以突出问题的 ROM。 但这并不意味着“现实的”方案不能解决这些问题。

这些“人为”的方案的另一个优点是,它们使基本概念相对容易解释。 作为对这一点的进一步说明:而不是解释CGH本身,我将使用一个由Maurer, Renner和Holenstein (MRH)提出的相同基本结果的公式。

一个签名方案

CGH-style 的反例的基本思想是构造一个“人为的”方案,这个方案在 ROM 中是安全的,但是当我们使用任何具体的函数“实例化”哈希函数时,它就完全崩溃了。

虽然 CGH 可以应用于许多不同类型的密码系统,在这个解释中,我们将使用一个相对简单的系统类型开始我们的例子: 一个数字签名方案。

你可能还记得本系列的前几章内容,一个普通的签名方案由三个算法组成: 密钥生成、签名和验证。 密钥生成算法输出一个公钥和私钥。 签名使用秘钥对消息进行签名,并输出签名。 验证采用结果签名、公钥和消息,并确定签名是否有效: 如果签名检查出来,则输出“True” ,否则输出“False”。

传统上,我们要求签名方案(至少)在选择消息攻击(UF-CMA)下是不可伪造的。 这意味着我们可以考虑一个高效的(多项式时间有限的)攻击者,他可以在选择的消息上要求签名,这些消息是由包含私钥签名密钥的“签名预言”生成的。 我们对安全方案的期望是,即使给出了这种访问权限,也没有攻击者能够在一些他没有要求签名的新消息上签名,除非有极小的可能性。 

在解释了这些基本知识之后,让我们来讨论一下我们将如何使用签名。 这将涉及以下几个步骤:

第一步: 从一些现有的安全签名方案入手。 我们从哪个签名方案开始并不重要,只要我们可以假设它是安全的(根据上面描述的 UF-CMA 定义) ,这个现有的签名方案将用作我们要构建的新方案的构建块。 我们将这个方案命名为 S。

步骤2: 我们将使用现有的方案 S 作为构建块来构建一个“新的”签名方案,我们将调用这个方案。 构建这个新方案主要是将奇怪的花哨功能嫁接到原方案 S 的算法上。

步骤3: 接下来是详细的工作描述,我们认为它是完全安全的ROM。自从我们开始(假定)安全的签名方案后,这个论点主要归结为我们在上一步中的随机预言模型附加功能中添加的功能并不是可攻击的。

步骤4: 最后,我们将证明,当你使用任何具体的哈希函数实例化随机预言时,无论它看起来多么“安全” ,这种情况都是完全不存在的。 简而言之,我们将展示如何用真正的哈希函数替换随机的预言,这里有一个简单的攻击方式,这种攻击总是能够成功地伪造签名。

欲知后事如何,请听下回分解!

这是关于随机预言模型系列文章的第五部分。 点击如下链接查看之前的文章:

第一部分: 介绍

第二部分: ROM 的形式化,方案和证明简介

第三部分: 我们如何滥用 ROM 来使我们的安全证明工作

第四部分:ROM 使用案例

大约八年前,我开始写一篇特别不够正式的文章,讨论一种特定的密码建模技术,称为“随机预言模型”。 这要追溯到2011年的美好时光,那是一个密码学更加天真和温和的时代。 当时没有人预见到我们所有的标准密码学最终都将被弄的漏洞百出; 你不需要被提醒“加密就是密码学”的意思。 人们甚至用比特币来购物。

第一篇随机预言的文章不知怎地就出现了三个结局,并且一个比一个更荒谬。 我想,在某种程度上,我对整件事感到很尴尬——说实话,这件事挺俗气的——所以我有点半途而废打算放弃了。 这是我后悔的主要原因之一,因为我一直计划要发表第五篇文章,也是最后一篇文章,来结束这一团糟的事情。这篇文章将是本系列文章中最好的一篇,也是我一直想写的一篇。

为了给你提供一些上下文,我会简要地说明随机预言模型是什么,以及你为什么应该关心它。 (当然你最好还是读读这个系列的前几篇文章。)

随机预言模型是一种对哈希函数进行建模的疯狂方法,我们假设这些函数实际上是随机函数,并利用这一假设来证明密码协议中的一些事情,如果没有这样一个模型,这些事情是很难证明的。 几乎所有我们今天使用的“可证明的”密码学都依赖于这个模型,这意味着如果这些证明是“错误的” ,那么这些证明中的许多东西将会受到质疑。

为了梳理这篇文章的其余部分,我将引用第四部分的最后一段话,以下面的内容结束:

你看,我们一直都知道这次旅行不会永远持续下去,我们只是觉得我们还有更多的时间。不幸的是,末日即将来临。就像莱昂纳多·德·卡普里奥在《盗梦空间》无聊的情节中探索的那个虚构的城市一样,随机预言模型在自身矛盾的压力下崩溃了。

正如我之前所承诺的那样,这篇文章会讲述那次“崩溃”,以及它对密码学家、安全专家和我们其他人意味着什么。

首先,为了使这篇文章更加自成一体,我想回顾一下我在本系列文章前面讨论过的一些基本内容。 如果你读过前面的几篇文章,你可以跳过这一部分。

我们将(很快)提醒读者什么是哈希函数,什么是随机函数,什么是随机预言

正如在本系列的前几篇文章中所讨论的,哈希函数(或哈希算法)是计算机科学的许多领域中使用的标准原语。 它们接受一些输入,通常是一个可变长度的字符串,并可重复地输出一个短的、固定长度的“摘要”。 我们经常这样表示这些函数:

加密哈希使用这个基本模板并利用加密应用程序所需的一些重要安全属性。 最著名的是,它们提供了一些众所周知的属性,比如抗碰撞性,这是数字签名等应用程序所需要的。但哈希函数在密码学中到处都会出现,有时出现在意想不到的地方,从加密到零知识协议,有时这些系统需要更强的特性。 这些有时很难用形式化的术语表示: 例如,许多协议需要一个哈希函数来产生极其“随机”的输出。 

在可证明安全性的早期,密码学家意识到理想的哈希函数的行为类似于“随机函数”。 这个术语指的是从所有可能的函数集中均匀采样的函数,这些函数具有适当的输入 / 输出规范(域和范围)。 在一个完美的世界里,你的协议可以,例如,在设置时随机抽取大量可能的函数中的一个,将该函数的标识符放入一个公钥或其他什么东西中,然后你就可以开始工作了。

不幸的是,在实际协议中不可能真正使用随机函数(适当规模的域和范围)。 这是因为抽样和评估这些函数的工作量太大了。

例如,使用很少的256位输入并生成256位摘要的不同函数的数量是令人难以置信的(2 ^ {256}) ^ {2 ^ {256}。简单地“写下”你所选择的函数的恒等式将需要在函数输入长度中呈指数级的内存。由于我们希望我们的加密算法是有效的(意思是,稍微正式一点,它们在多项式时间内运行),使用随机函数几乎是不可用的。

所以我们不使用随机函数来实现哈希。 在“现实世界”中,我们使用比利时人或国家安全局开发的奇怪函数,比如 SHA256、 SHA3和 Blake2。 这些函数具有极快的运算速度和微小的算法来执行计算,其中大多数只占用几十行或更少的代码。 它们当然不是随机的,但据我们所知,输出看起来相当混乱。

尽管如此,协议设计者仍然渴望使用真正的随机函数能够给他们的协议带来安全性。 他们会问,如果我们折中一下,结果会怎样?如果我们使用随机函数来建模我们的哈希函数——只是为了编写我们的安全证明——然后当我们实现(或“实例化”)我们的协议时,我们将使用高效的哈希函数,比如SHA3,会怎么样呢?当然,这些证明并不完全适用于实例化的实际协议,但它们可能仍然很好。

使用这种范式的证明被称为随机预言模型(ROM)中的证明。 关于 ROM 如何工作的完整机制,可以翻阅我之前发表的该系列文章。 你现在需要知道的是,在这个模型中的证明必须以某种方式绕过,即计算一个随机函数需要花费大量指数级的时间。 这个模型处理这个问题的方法很简单: 它没有给每个协议参与者一个关于哈希函数本身的描述(哈希函数对任何人来说都太大了) ,而是给每个参与者(包括对手)一个神奇的“预言” ,这个预言可以有效地评估随机函数 H,并将结果返回给他们。

这意味着任何时候其中一方想要计算函数,他们自己并不能独自完成。 相反,它们会调用第三方,即“随机预言”,“随机预言”拥有一个巨大的随机函数输入和输出表。 在高层次上,这个模型看起来有点像下面这样:

因为系统中的所有参与方都与同一个预言在“对话” ,所以当他们要求预言对给定的消息进行哈希时,都会得到相同的哈希结果。 对于真正的哈希函数来说,这是一个相当好的替代函数。 使用外部的预言可以让我们“掩盖”评估随机函数的成本,这样就没有人需要花费一个指数级的时间来评估一个函数。 在这个人工模型中,我们得到了理想的哈希函数,而且没有任何麻烦。

这看起来已经很可笑了……

绝对是这样!

然而,我认为在你认为随机预言模型是个空洞的事物之前,你应该知道几件非常重要的事情:

1. 当然,每个人都知道随机的预言证明不是“真的”。 大多数认真的协议设计者都会承认,在随机预言模型中证明某些东西是安全的,并不意味着它在“现实世界”是安全的。 换句话说,随机的预言模型证明是伪造的这一事实,这并不是我想让你们知道的秘密。。

2. 总之: ROM 证明通常被认为是一种有用的启发式方法。 对于那些不熟悉“启发式”这个术语的人来说,“启发式”是一个成年人用来保护你毕生积蓄的词,因为他们使用的密码学无法证明任何事情。

OK,开个玩笑! 事实上,随机预言证明仍然是很有价值的。 这主要是因为它可以经常帮助我们检测方案中的缺陷。 也就是说,虽然随机预言证明在现实世界中并不意味着安全性,但不能编写这样的证明通常是协议的危险信号。 此外,ROM证明的存在有希望表明协议的“核心”是正常的,并且任何现实世界中出现的问题都与哈希函数有关。

3. 经过ROM验证的方案在实践中有着相当不错的记录。 如果 ROM 验证每隔一天就会提出一些荒谬而被破坏的方案,我们很可能就已经放弃了这种技术。 然而,我们使用的密码学几乎每天都在 ROM 中得到验证(仅仅是验证) ,而且大多数情况下它确实奏效。

这并不是说,当用特定的哈希函数实例化时,经过 ROM 证明的方案从未被破坏。 但通常情况下,这些破坏是因为哈希函数本身明显存在缺陷(正如 MD4和 MD5不久前都break 掉时所发生的情况) ,尽管如此,这些缺陷通常可以通过简单地切换到一个更好的函数来进行修复。 此外,从历史上看,实际攻击更可能来自明显的缺陷,比如发现哈希碰撞破坏了签名方案,而不是来自某种奇特的数学缺陷。 这就让我们注意到了最后一个关键的点..。

4. 多年以来,许多人相信只读存储器实际上是可以被保存的。 这种希望是由这样一个事实驱动的:即 ROM 方案在实现了强哈希函数时似乎工作得很好,所以也许我们所需要做的就是找到一个哈希函数,使 ROM 证明变得有意义。 一些理论家希望像密码混淆这样的奇特技术能够以某种方式使具体的哈希算法运行良好,使(某些) ROM 证明可以实例化。 

所以这就是 ROM 的状态,或者至少是直到20世纪90年代末的状态。 我们知道这个模型是人造的,但它固执地拒绝爆炸或产生完全无意义的结果。

然后,在1998年,一切都变糟了。

CGH98: 一个“不可实例化”的方案

对于理论密码学家来说,随机预言模型的真正破裂点来自于 Canetti,Goldreich 和 Halevi (以下简称 CGH)在1998年发表的一篇 STOC 论文。 我打算把剩下的时间来解释他们发现的要点。

CGH 所证明的是,实际上,有一些加密方案可以在随机预言模型中被证明是完全安全的,但是,当你用任何具体函数实例化哈希函数时,这种安全性就会变得非常危险。

这是一个非常可怕的结果,至少从可证明的安全社区的角度来看是这样。 从理论上来说,你的证明可能不够有力,这是一回事。 而另一回事则是,你要知道,在实践中,有些方案可以直接通过你的证据,就像终结者渗透到抵抗组织,然后以最严重的方式在你身上爆发。

在我们详细介绍CGH及其相关结果之前,有几点需要注意。

首先, CGH很大程度上是一个理论结果。解决这个问题的密码“反例”方案通常看起来不像我们将在实践中使用的真正的密码系统,尽管后来的作者提供了一些更“现实”的变体。事实上,这些变体是被设计用来做一些“真实的”方案不会做的但却是非常“人为的”事情。这可能会导致读者会以“人为的”这一理由对它们不屑一顾。

这种观点的问题在于,外表并不是判断一个方案的特别科学的方法。 如果证明是正确的,那么“真实的”和“人为的”方案都是有效的密码系统。 这些具体的反例的要点是故意做“人为的”事情,以突出问题的 ROM。 但这并不意味着“现实的”方案不能解决这些问题。

这些“人为”的方案的另一个优点是,它们使基本概念相对容易解释。 作为对这一点的进一步说明:而不是解释CGH本身,我将使用一个由Maurer, Renner和Holenstein (MRH)提出的相同基本结果的公式。

一个签名方案

CGH-style 的反例的基本思想是构造一个“人为的”方案,这个方案在 ROM 中是安全的,但是当我们使用任何具体的函数“实例化”哈希函数时,它就完全崩溃了。

虽然 CGH 可以应用于许多不同类型的密码系统,在这个解释中,我们将使用一个相对简单的系统类型开始我们的例子: 一个数字签名方案。

你可能还记得本系列的前几章内容,一个普通的签名方案由三个算法组成: 密钥生成、签名和验证。 密钥生成算法输出一个公钥和私钥。 签名使用秘钥对消息进行签名,并输出签名。 验证采用结果签名、公钥和消息,并确定签名是否有效: 如果签名检查出来,则输出“True” ,否则输出“False”。

传统上,我们要求签名方案(至少)在选择消息攻击(UF-CMA)下是不可伪造的。 这意味着我们可以考虑一个高效的(多项式时间有限的)攻击者,他可以在选择的消息上要求签名,这些消息是由包含私钥签名密钥的“签名预言”生成的。 我们对安全方案的期望是,即使给出了这种访问权限,也没有攻击者能够在一些他没有要求签名的新消息上签名,除非有极小的可能性。 

在解释了这些基本知识之后,让我们来讨论一下我们将如何使用签名。 这将涉及以下几个步骤:

第一步: 从一些现有的安全签名方案入手。 我们从哪个签名方案开始并不重要,只要我们可以假设它是安全的(根据上面描述的 UF-CMA 定义) ,这个现有的签名方案将用作我们要构建的新方案的构建块。 我们将这个方案命名为 S。

步骤2: 我们将使用现有的方案 S 作为构建块来构建一个“新的”签名方案,我们将调用这个方案。 构建这个新方案主要是将奇怪的花哨功能嫁接到原方案 S 的算法上。

步骤3: 接下来是详细的工作描述,我们认为它是完全安全的ROM。自从我们开始(假定)安全的签名方案后,这个论点主要归结为我们在上一步中的随机预言模型附加功能中添加的功能并不是可攻击的。

步骤4: 最后,我们将证明,当你使用任何具体的哈希函数实例化随机预言时,无论它看起来多么“安全” ,这种情况都是完全不存在的。 简而言之,我们将展示如何用真正的哈希函数替换随机的预言,这里有一个简单的攻击方式,这种攻击总是能够成功地伪造签名。

欲知后事如何,请听下回分解!

这是关于随机预言模型系列文章的第四部分。 点击下面的链接查看以前的文章:

第一部分: 介绍

第二部分: ROM 的形式化,方案和证明简介

第三部分: 我们如何滥用 ROM 来使我们的安全证明工作

这是关于随机预言模型的倒数第二篇文章。我最初希望的是,这篇文章要简短、整洁,对于那些对密码学家的工作感兴趣的非专业人士来说,这篇文章很容易理解。 更重要的是,我期望现在确实已经是这样了。

但是终点已经在眼前,我觉得只剩下几件事情我想说了。更妙的是,其中一个主题非常实用,这是本博客的主题一致。

具体来说: 我一直在谈论随机预言模型,但它对生活有什么影响? 这东西在哪里使用?

对这个问题给出一个完整的答案是困难的——这有点像列出所有成分表中含有苯甲酸钠成分的食物。 所以在这篇文章中,我至少会提及几个亮点,也就是说: 这些方案可能与我们的日常安全生活最相关。

RSA 签名和加密

RSA 可能是目前使用的最著名的密码系统。 我不知道为什么它如此受欢迎,但我怀疑其中有几个原因。 首先,RSA 是灵活的,它在一个方案中提供签名和加密。 它相对简单——你可以用计算器计算简单的加密。 它已经存在一段时间了,还没有被打破。 如果我没有提到 RSA 目前没有专利,那我就是失职了。

这一切都很好,但从某种意义上说,这也太糟糕了。 在过去的二十年里,对因数分解问题(也就是 RSA)的攻击一直处于边缘状态。 这意味着 RSA 密钥的大小必须变得更大才能跟得上。 我们迟早会输掉这场比赛。 

对我来说,更有趣的是 RSA 作为一种可证明安全的密码系统的地位。 人们普遍认为 RSA 加密在 RSA 问题困难的情况下是可证明安全的。 然而,事实并非如此,至少考虑到大多数人传统上使用 RSA 的方式。 你可以对 RSA 假设进行简化,但需要采取一些非常具体的步骤。 最重要的是: 你需要调用随机预言模型。

为了解释这一切,我需要带你回到20世纪90年代末,我需要谈谈填充。

如果你曾经看过一个真正的 RSA 实现,你可能知道我们不使用普通的“教科书” 上的RSA (“m^e mod N“)来加密或签名原始消息。 这其中有很多原因。 其中之一就是普通的 RSA 没有随机化,这意味着给定的消息将总是在加密后得到相同的密文。

另一个原因是 RSA 具有可塑性,这意味着你可以用创造性的方式对密文和签名进行处理——例如,用你选择的常数乘以它们。 当你这样做时,解密(resp:verified)消息将以可预测的方式进行更改。 这不利于加密。 对于签名来说,这简直是糟糕透顶。

在对消息进行加密或签名之前,我们通过对消息应用填充来处理这些问题。 填充方案可以添加随机性,在签名的情况下应用哈希,最重要的是,它们通常添加结构,让我们知道消息何时被篡改。

一些历史背景: 在 ROM 之前的 RSA

第一个广泛使用的标准填充方案是在 RSA 的 PKCS#1 标准中描述的。 现在,我们将这些标准称为“PKCS#1 v1.5”标准,这意味着该标准(现在是2.1版本)已经将它们抛在了后面。

回到90年代,这些标准是唯一的游戏。 当然,也有一些迂腐的密码学家反对该标准缺乏正式的安全理由。 但这些麻烦制造者主要局限于学术机构,这意味着真正的安全专业人员可以继续从事业务。

这项业务就是在所有地方实现 PKCS 填充标准。 PKCS #1 v1.5 填充仍然出现在我评估的产品中。 当时最值得注意的是,它使用的是一个名为 SSL 的年轻标准,一些人使用 SSL 来加密通过互联网传输的信用卡号码。

现在,我可以说,几乎没有一个有实际经验的人对 PKCS 有意见。 一个值得注意的例外是来自贝尔实验室的一位聪明的密码破译者,名叫丹尼尔 · 布莱申巴赫。

布莱申巴赫博士对 PKCS 填充标准有一个真正的问题。 事实上,可以说他一生的使命就是摧毁它们。 这种仇恨在2006年达到顶峰,当时他展示了如何用铅笔和纸打破 PKCS 签名的常见实现,不久之后,他驾驶一辆载满烟花的小型货车进入 RSA 数据安全公司的总部。

1998年,布莱申巴赫在 CRYPTO 第一次加入 PKCS。 在一篇可读性惊人的论文中,他提出了针对“使用 PKCS#1”加密标准的协议的第一个实用的自适应选择密文攻击。 因为,正如我刚才提到的,符合这种描述的主要协议是 SSL,这是一件非常了不起的事情。

攻击是这样进行的。

每当有人通过 SSL 连接将他们的信用卡信息发送到网络服务器时,他们的浏览器和服务器就会执行握手协议以获得一个秘密密钥。 特别是,在协议的一个步骤中,浏览器对服务器的 RSA 公钥下称为“ pre-master secret”(预万能密钥)的非常重要的值进行加密,并通过网络将产生的密文发送给它。

这种加密很重要,因为任何人只要立即解密或五年后解密密文,就可以最终恢复 SSL 传输密钥,从而解密服务器和浏览器之间的所有通信。

布莱申巴赫指出的是大多数 web 服务器处理 RSA 消息的具体方式。 具体来说,每当服务器接收到 RSA 密文时,它首先对其解密,然后检查填充是否有效。 对于一个典型的 RSA 密钥,PKCS#1 填充 如下所示:

0x 00 02 { at least 8 non-zero random bytes } 00 { message }

当 SSL 网络服务器不像它看到的填充那样,它可能会反馈一个特定的“坏填充”错误。 布莱申巴赫首先展示了如果他能在网络上拦截一个合法的 RSA 密文“C = M^e mod N” 然后他就可以用选定的值“篡改”它。 换句话说,给定一些C,他会选择一些“s”然后计算:

C' = C * s^e mod N

这个值 C’将解密为“M * s mod N”。 布莱申巴赫表明,对于“s”的某些值,这个被篡改的消息也可能是一个有效的 PKCS 填充消息,这意味着它将以“0x00002”等开头。 这并非完全不可能,主要是因为仅仅查看几个字节本身就是一个非常糟糕的填充检查。

服务器通过一些特殊的错误代码(比如“BAD PADDING”)将填充检查的结果泄漏给发送方是很常见的。 即使他们没有这样做,你有时也可以通过测量服务器返回到你的时间来检测填充检查中的故障。

布莱申巴赫的主要技巧是指出,导致成功的填充检查的“s”值也可以用来学习原始消息 M 的一些东西。长话短说,他展示了如何自适应地选择这些值,以便逐渐将注意力集中到实际的明文上,直到他只有一个候选者。 这就是比赛的情况。

实际的攻击平均需要几百万次解密查询。 这听起来似乎很多,但这意味着你可以在一夜之间解密 SSL 会话,只要没有人关注服务器日志。

随机预言的救赎

出于各种原因,布莱申巴赫的攻击方法是一件大事。 首先,它是实用的。 它在一个广泛部署的系统上工作,甚至可以由非专家实现和执行。 它完全否定了 SSL 提供的保护,除非你愿意日夜监控你的 SSL 网络服务器。

但是对密码学家来说,这次攻击有着特殊的意义。 首先,它证明了自适应选择密文攻击是一个真正的问题,而不仅仅是一个空洞的学术话题。 我怀疑,即使是在这个领域工作的密码学家也对此感到有点惊讶。 有些人可能已经开始寻找一些没什么用的话题。

更重要的是,布莱申巴赫的演示被视为可证明安全的支持者的胜利。 到目前为止,他们的担忧大多被置若罔闻。 现在很多人都在听。

更妙的是,密码研究团体有话要对他们说。 压倒性的共识是立即切换到早在1994年就提出的新的 RSA 填充方案。 这个方案被称为最优非对称加密填充(OAEP) ,它只比 PKCS#1稍微复杂一点。 更好的是,与 PKCS#1不同的是,在随机预言模型中,使用 OAEP(Optimal Asymmetric Encryption Padding) 的 RSA 加密可以被证明减少 RSA 问题的难度。

OAEP 的成功也导致了 PSS 填充方案的采用,它对 RSA 签名基本上也起到了同样的作用。

现在,听一些人说,这就是故事的结局。 这是一个好故事——坏的,未经证实的安全协议被破坏。 新的、可证明安全的协议介入并挽救了局面。

大多数情况下,这个故事是真实的,但也有一些重要的警告。

第一个就是与实现相关的。 正如 PKCS#1由于服务器提供了太多详细错误而被破坏一样,如果服务器泄漏了太多关于其错误条件的信息,即使 OAEP 加密也可能被破坏。 当 OAEP 实现出现问题时,它们真的会变得很糟糕。 James Manger 展示了你可以在1100个查询中破解1024位 RSA-OAEP,假设你的服务器泄漏了一点点关于解密尝试出错的信息。 ****

但是,即使你正确地执行所有操作,OAEP 的安全性证明也只适用于随机预言模型。 这意味着,只有在哈希函数是理想的情况下,它才能提供有效的保证。 这是一个很好的启发式方法,意味着 OAEP 不太可能充满明显的缺陷。

但是如果你深入研究 OAEP 的安全性证明,你会发现它使用的是可以想象到的最强大的随机预言。 OAEP 的基本概念是使用一对散列函数构造一个微小的可逆 Feistel 网络。 美妙之处在于,每次你加密的时候,本质上就是通过随机预言直接发送信息(和一些随机性) ,这种方式允许各种各样的胡说八道。

然后,还原证明可以看到对手的加密算法是什么,当你构建一个针对选择密文攻击非常安全的系统时,这种加密非常有用。 如果你用一个真正的哈希函数来实现 OAEP,就像在现实生活中实际用来实现它的那些函数一样,那么这将永远不会起作用。

所以在一个非常真实的意义上,我们仍然没有一个实用的,可证明安全的方法来使用 RSA 加密。 此外,我们几乎没有理由相信我们会这样做,因为一系列不可能的结果似乎一直阻碍着我们。 *****

所有这些都提出了一个重要的问题。 考虑到 RSA 的所有限制,为什么我们对它如此痴迷?

数字签名算法(DSA / DSS)

你可能会觉得有点奇怪,我在讨论可证明的安全性时提到了 DSA。 这主要是因为,与 DSA 所基于的 Elgamal 签名不同,DSA 标准没有任何安全证明。 ******

对此没有真正可以辩护的理由。 据我所知,NIST 看了一眼 Elgamal 签名,觉得很可爱,但是签名有点太长了。 所以他们用剪刀剪出了一些看起来基本一样的东西,但是没有像 Elgamal 那样很好地减少了离散对数的假设。

这种行为是意料之中的,说实话,这让我对政府标准机构有点失望。

郑重声明,尽管 DSA 根本不是真正可证明的安全方案,但 Elgamal 方案是可证明的。 但不幸的是,Elgamal 方案只能在随机预言模型中证明是安全的。 这意味着,如果你的散列函数具有完全随机和可编程的特性,Elgamal 签名可以简化为离散对数问题的难度。 除此之外,你只能靠自己了。

关键词推导与超越

可能有数不清的密码系统应该在这里提到,但我们不能涵盖所有的。 不过,还有一类“使用散列函数的东西”可能根本就不安全,除非你愿意对散列函数的属性做出一些非常强有力的假设。

我想到的例子是使用哈希来推导加密密钥。 例如,许多基于密码的加密方案使用散列函数将密码和一些 salt 结合起来,从而得到用于加密的密钥。 这种方法在大多数情况下似乎可行(假设是一个高熵密码) ,但是它没有任何强有力的理论支撑。

一般来说,如果你试图从一个“块状”的、非均匀的密码源(如密码)中提取一个均匀随机密钥,正确的工具是所谓的随机提取器。 这些可以在标准模型中实现(没有随机预言) ,但是所有现有的结构都很糟糕。 这听起来很粗鲁,但实际上这是密码学家用来表示方案复杂而缓慢的一个技术术语。

所以在现实生活中,没有人会用这些东西。 相反,他们只是把密码加盐加密,然后假设结果会很好。 如果他们感到兴奋,他们甚至可能把这个问题解决好几次,这就相当于用 AK-47步枪射击一只火鸡。 这可能没什么问题,虽然从技术上来说,你永远不能排除防弹火鸡。 *******

每当人们费心去正式讨论像这样的方案的安全性时(实际上从来没有) ,通常的争论是这样的: 让我们假设哈希函数是一个随机预言。 当然,在随机预言模型中,每个 hash 函数都是一个完美的提取器。 将任何高熵的源代码放入一个理想的哈希函数中,不管输入的内容是多么“凹凸不平”或者“奇怪” ,你都可以从另一端得到一个非常棒的密钥。

因此,即使你最喜欢的密钥推导没有任何正式的安全证据,你可以打赌,某个地方的某个人,已经提出了这个论点,即使只是为了帮助自己在晚上睡得更好。

总结

这本应该是一篇关于随机预言模型的文章,但是我觉得它有了自己的生命。 这不是一件坏事。 我承诺我会花一些时间来讨论实用的密码技术,我已经做到了。

虽然我可以说出关于随机预言模型的一百万件事情,但我只剩下最后一篇文章了。 在某些方面,这将是最重要的文章。

你看,我们一直都知道这次旅行不会永远持续下去,我们只是觉得我们有更多的时间。 不幸的是,末日即将来临。 就像莱昂纳多 · 德 · 卡普里奥在《盗梦空间》无聊的情节中探索的那个虚构的城市一样,随机预言模型在自身矛盾的重压下正在崩溃。

这种崩溃——以及它对密码学家、安全专家和其他所有人意味着什么——将成为我最后一篇文章的主题。

这是关于随机预言模型系列文章的第四部分。 点击下面的链接查看以前的文章:

第一部分: 介绍

第二部分: ROM 的形式化,方案和证明简介

第三部分: 我们如何滥用 ROM 来使我们的安全证明工作

这是关于随机预言模型的倒数第二篇文章。我最初希望的是,这篇文章要简短、整洁,对于那些对密码学家的工作感兴趣的非专业人士来说,这篇文章很容易理解。 更重要的是,我期望现在确实已经是这样了。

但是终点已经在眼前,我觉得只剩下几件事情我想说了。更妙的是,其中一个主题非常实用,这是本博客的主题一致。

具体来说: 我一直在谈论随机预言模型,但它对生活有什么影响? 这东西在哪里使用?

对这个问题给出一个完整的答案是困难的——这有点像列出所有成分表中含有苯甲酸钠成分的食物。 所以在这篇文章中,我至少会提及几个亮点,也就是说: 这些方案可能与我们的日常安全生活最相关。

RSA 签名和加密

RSA 可能是目前使用的最著名的密码系统。 我不知道为什么它如此受欢迎,但我怀疑其中有几个原因。 首先,RSA 是灵活的,它在一个方案中提供签名和加密。 它相对简单——你可以用计算器计算简单的加密。 它已经存在一段时间了,还没有被打破。 如果我没有提到 RSA 目前没有专利,那我就是失职了。

这一切都很好,但从某种意义上说,这也太糟糕了。 在过去的二十年里,对因数分解问题(也就是 RSA)的攻击一直处于边缘状态。 这意味着 RSA 密钥的大小必须变得更大才能跟得上。 我们迟早会输掉这场比赛。 

对我来说,更有趣的是 RSA 作为一种可证明安全的密码系统的地位。 人们普遍认为 RSA 加密在 RSA 问题困难的情况下是可证明安全的。 然而,事实并非如此,至少考虑到大多数人传统上使用 RSA 的方式。 你可以对 RSA 假设进行简化,但需要采取一些非常具体的步骤。 最重要的是: 你需要调用随机预言模型。

为了解释这一切,我需要带你回到20世纪90年代末,我需要谈谈填充。

如果你曾经看过一个真正的 RSA 实现,你可能知道我们不使用普通的“教科书” 上的RSA (“m^e mod N“)来加密或签名原始消息。 这其中有很多原因。 其中之一就是普通的 RSA 没有随机化,这意味着给定的消息将总是在加密后得到相同的密文。

另一个原因是 RSA 具有可塑性,这意味着你可以用创造性的方式对密文和签名进行处理——例如,用你选择的常数乘以它们。 当你这样做时,解密(resp:verified)消息将以可预测的方式进行更改。 这不利于加密。 对于签名来说,这简直是糟糕透顶。

在对消息进行加密或签名之前,我们通过对消息应用填充来处理这些问题。 填充方案可以添加随机性,在签名的情况下应用哈希,最重要的是,它们通常添加结构,让我们知道消息何时被篡改。

一些历史背景: 在 ROM 之前的 RSA

第一个广泛使用的标准填充方案是在 RSA 的 PKCS#1 标准中描述的。 现在,我们将这些标准称为“PKCS#1 v1.5”标准,这意味着该标准(现在是2.1版本)已经将它们抛在了后面。

回到90年代,这些标准是唯一的游戏。 当然,也有一些迂腐的密码学家反对该标准缺乏正式的安全理由。 但这些麻烦制造者主要局限于学术机构,这意味着真正的安全专业人员可以继续从事业务。

这项业务就是在所有地方实现 PKCS 填充标准。 PKCS #1 v1.5 填充仍然出现在我评估的产品中。 当时最值得注意的是,它使用的是一个名为 SSL 的年轻标准,一些人使用 SSL 来加密通过互联网传输的信用卡号码。

现在,我可以说,几乎没有一个有实际经验的人对 PKCS 有意见。 一个值得注意的例外是来自贝尔实验室的一位聪明的密码破译者,名叫丹尼尔 · 布莱申巴赫。

布莱申巴赫博士对 PKCS 填充标准有一个真正的问题。 事实上,可以说他一生的使命就是摧毁它们。 这种仇恨在2006年达到顶峰,当时他展示了如何用铅笔和纸打破 PKCS 签名的常见实现,不久之后,他驾驶一辆载满烟花的小型货车进入 RSA 数据安全公司的总部。

1998年,布莱申巴赫在 CRYPTO 第一次加入 PKCS。 在一篇可读性惊人的论文中,他提出了针对“使用 PKCS#1”加密标准的协议的第一个实用的自适应选择密文攻击。 因为,正如我刚才提到的,符合这种描述的主要协议是 SSL,这是一件非常了不起的事情。

攻击是这样进行的。

每当有人通过 SSL 连接将他们的信用卡信息发送到网络服务器时,他们的浏览器和服务器就会执行握手协议以获得一个秘密密钥。 特别是,在协议的一个步骤中,浏览器对服务器的 RSA 公钥下称为“ pre-master secret”(预万能密钥)的非常重要的值进行加密,并通过网络将产生的密文发送给它。

这种加密很重要,因为任何人只要立即解密或五年后解密密文,就可以最终恢复 SSL 传输密钥,从而解密服务器和浏览器之间的所有通信。

布莱申巴赫指出的是大多数 web 服务器处理 RSA 消息的具体方式。 具体来说,每当服务器接收到 RSA 密文时,它首先对其解密,然后检查填充是否有效。 对于一个典型的 RSA 密钥,PKCS#1 填充 如下所示:

0x 00 02 { at least 8 non-zero random bytes } 00 { message }

当 SSL 网络服务器不像它看到的填充那样,它可能会反馈一个特定的“坏填充”错误。 布莱申巴赫首先展示了如果他能在网络上拦截一个合法的 RSA 密文“C = M^e mod N” 然后他就可以用选定的值“篡改”它。 换句话说,给定一些C,他会选择一些“s”然后计算:

C' = C * s^e mod N

这个值 C’将解密为“M * s mod N”。 布莱申巴赫表明,对于“s”的某些值,这个被篡改的消息也可能是一个有效的 PKCS 填充消息,这意味着它将以“0x00002”等开头。 这并非完全不可能,主要是因为仅仅查看几个字节本身就是一个非常糟糕的填充检查。

服务器通过一些特殊的错误代码(比如“BAD PADDING”)将填充检查的结果泄漏给发送方是很常见的。 即使他们没有这样做,你有时也可以通过测量服务器返回到你的时间来检测填充检查中的故障。

布莱申巴赫的主要技巧是指出,导致成功的填充检查的“s”值也可以用来学习原始消息 M 的一些东西。长话短说,他展示了如何自适应地选择这些值,以便逐渐将注意力集中到实际的明文上,直到他只有一个候选者。 这就是比赛的情况。

实际的攻击平均需要几百万次解密查询。 这听起来似乎很多,但这意味着你可以在一夜之间解密 SSL 会话,只要没有人关注服务器日志。

随机预言的救赎

出于各种原因,布莱申巴赫的攻击方法是一件大事。 首先,它是实用的。 它在一个广泛部署的系统上工作,甚至可以由非专家实现和执行。 它完全否定了 SSL 提供的保护,除非你愿意日夜监控你的 SSL 网络服务器。

但是对密码学家来说,这次攻击有着特殊的意义。 首先,它证明了自适应选择密文攻击是一个真正的问题,而不仅仅是一个空洞的学术话题。 我怀疑,即使是在这个领域工作的密码学家也对此感到有点惊讶。 有些人可能已经开始寻找一些没什么用的话题。

更重要的是,布莱申巴赫的演示被视为可证明安全的支持者的胜利。 到目前为止,他们的担忧大多被置若罔闻。 现在很多人都在听。

更妙的是,密码研究团体有话要对他们说。 压倒性的共识是立即切换到早在1994年就提出的新的 RSA 填充方案。 这个方案被称为最优非对称加密填充(OAEP) ,它只比 PKCS#1稍微复杂一点。 更好的是,与 PKCS#1不同的是,在随机预言模型中,使用 OAEP(Optimal Asymmetric Encryption Padding) 的 RSA 加密可以被证明减少 RSA 问题的难度。

OAEP 的成功也导致了 PSS 填充方案的采用,它对 RSA 签名基本上也起到了同样的作用。

现在,听一些人说,这就是故事的结局。 这是一个好故事——坏的,未经证实的安全协议被破坏。 新的、可证明安全的协议介入并挽救了局面。

大多数情况下,这个故事是真实的,但也有一些重要的警告。

第一个就是与实现相关的。 正如 PKCS#1由于服务器提供了太多详细错误而被破坏一样,如果服务器泄漏了太多关于其错误条件的信息,即使 OAEP 加密也可能被破坏。 当 OAEP 实现出现问题时,它们真的会变得很糟糕。 James Manger 展示了你可以在1100个查询中破解1024位 RSA-OAEP,假设你的服务器泄漏了一点点关于解密尝试出错的信息。 ****

但是,即使你正确地执行所有操作,OAEP 的安全性证明也只适用于随机预言模型。 这意味着,只有在哈希函数是理想的情况下,它才能提供有效的保证。 这是一个很好的启发式方法,意味着 OAEP 不太可能充满明显的缺陷。

但是如果你深入研究 OAEP 的安全性证明,你会发现它使用的是可以想象到的最强大的随机预言。 OAEP 的基本概念是使用一对散列函数构造一个微小的可逆 Feistel 网络。 美妙之处在于,每次你加密的时候,本质上就是通过随机预言直接发送信息(和一些随机性) ,这种方式允许各种各样的胡说八道。

然后,还原证明可以看到对手的加密算法是什么,当你构建一个针对选择密文攻击非常安全的系统时,这种加密非常有用。 如果你用一个真正的哈希函数来实现 OAEP,就像在现实生活中实际用来实现它的那些函数一样,那么这将永远不会起作用。

所以在一个非常真实的意义上,我们仍然没有一个实用的,可证明安全的方法来使用 RSA 加密。 此外,我们几乎没有理由相信我们会这样做,因为一系列不可能的结果似乎一直阻碍着我们。 *****

所有这些都提出了一个重要的问题。 考虑到 RSA 的所有限制,为什么我们对它如此痴迷?

数字签名算法(DSA / DSS)

你可能会觉得有点奇怪,我在讨论可证明的安全性时提到了 DSA。 这主要是因为,与 DSA 所基于的 Elgamal 签名不同,DSA 标准没有任何安全证明。 ******

对此没有真正可以辩护的理由。 据我所知,NIST 看了一眼 Elgamal 签名,觉得很可爱,但是签名有点太长了。 所以他们用剪刀剪出了一些看起来基本一样的东西,但是没有像 Elgamal 那样很好地减少了离散对数的假设。

这种行为是意料之中的,说实话,这让我对政府标准机构有点失望。

郑重声明,尽管 DSA 根本不是真正可证明的安全方案,但 Elgamal 方案是可证明的。 但不幸的是,Elgamal 方案只能在随机预言模型中证明是安全的。 这意味着,如果你的散列函数具有完全随机和可编程的特性,Elgamal 签名可以简化为离散对数问题的难度。 除此之外,你只能靠自己了。

关键词推导与超越

可能有数不清的密码系统应该在这里提到,但我们不能涵盖所有的。 不过,还有一类“使用散列函数的东西”可能根本就不安全,除非你愿意对散列函数的属性做出一些非常强有力的假设。

我想到的例子是使用哈希来推导加密密钥。 例如,许多基于密码的加密方案使用散列函数将密码和一些 salt 结合起来,从而得到用于加密的密钥。 这种方法在大多数情况下似乎可行(假设是一个高熵密码) ,但是它没有任何强有力的理论支撑。

一般来说,如果你试图从一个“块状”的、非均匀的密码源(如密码)中提取一个均匀随机密钥,正确的工具是所谓的随机提取器。 这些可以在标准模型中实现(没有随机预言) ,但是所有现有的结构都很糟糕。 这听起来很粗鲁,但实际上这是密码学家用来表示方案复杂而缓慢的一个技术术语。

所以在现实生活中,没有人会用这些东西。 相反,他们只是把密码加盐加密,然后假设结果会很好。 如果他们感到兴奋,他们甚至可能把这个问题解决好几次,这就相当于用 AK-47步枪射击一只火鸡。 这可能没什么问题,虽然从技术上来说,你永远不能排除防弹火鸡。 *******

每当人们费心去正式讨论像这样的方案的安全性时(实际上从来没有) ,通常的争论是这样的: 让我们假设哈希函数是一个随机预言。 当然,在随机预言模型中,每个 hash 函数都是一个完美的提取器。 将任何高熵的源代码放入一个理想的哈希函数中,不管输入的内容是多么“凹凸不平”或者“奇怪” ,你都可以从另一端得到一个非常棒的密钥。

因此,即使你最喜欢的密钥推导没有任何正式的安全证据,你可以打赌,某个地方的某个人,已经提出了这个论点,即使只是为了帮助自己在晚上睡得更好。

总结

这本应该是一篇关于随机预言模型的文章,但是我觉得它有了自己的生命。 这不是一件坏事。 我承诺我会花一些时间来讨论实用的密码技术,我已经做到了。

虽然我可以说出关于随机预言模型的一百万件事情,但我只剩下最后一篇文章了。 在某些方面,这将是最重要的文章。

你看,我们一直都知道这次旅行不会永远持续下去,我们只是觉得我们有更多的时间。 不幸的是,末日即将来临。 就像莱昂纳多 · 德 · 卡普里奥在《盗梦空间》无聊的情节中探索的那个虚构的城市一样,随机预言模型在自身矛盾的重压下正在崩溃。

这种崩溃——以及它对密码学家、安全专家和其他所有人意味着什么——将成为我最后一篇文章的主题。

你的 Android Keystore 认证有多安全?(上)

安卓 Keystore 和应用程序HOOK

安卓 Keystore 一直被认为是安全的,因为我们不能访问密钥信息。 但是,攻击者实际上可能并不需要密钥内容。 Keystore API 可用于检索密钥引用,然后可以使用它们初始化 Cipher 对象,然后可以使用它们对应用程序存储进行解密或加密。

是的,这是可能的,而且大多数应用程序都很容易受到这类攻击,正如具有设备实际访问权限或特权恶意软件的攻击者可以做到的那样:

a) 启动受害者应用程序

b) 使用 Frida 在受害者应用程序的上下文中执行代码,HOOK 受害者应用程序如下:

1. 使用 Keystore API 检索对 AndroidKeystore 密钥的引用

2. 使用检索到的密钥引用初始化密码对象

3. 在应用程序存储中解密/加密/签名数据

使用 Android Keystore 并不能保证二进制安全性。 为了防止这种攻击,开发人员必须将keystore 密钥标记为只有在以下情况下才能访问:

1. 设备已经解锁

2. 指纹或其他生物识别已被验证

对于此配置,开发人员必须在生成密钥期间将 setUserAuthenticationRequired() 设置为 true。 另一个重要属性是 setUserAuthenticationValidityDurationSeconds ()。 如果设置为 -1,那么只有使用指纹或生物识别技术才能解锁密钥。 如果它被设置为任何其他值,也可以使用设备屏幕锁解锁密钥。

在设备屏幕锁定的情况下,首先通过调用 KeyguardManager.createConfirmDeviceCredentialIntent() 来访问密钥。

需要注意的是,KeyguardManager API 不允许开发人员检查配置了哪种类型的屏幕锁,也不允许验证密码/PIN码/手势图案策略。 因此,这个设备可能有一个不安全的屏幕锁:

1. 简单的手势图案(在大多数设备上是3x3,可以通过尝试常见的图案或检查屏幕上的指纹进行猜测)

2. 简单的PIN码(通常是4-5个数字,常见的PIN码有0000或1234)

3. 另外也可以使用生活中的一些东西作为猜测密码(例如:你的狗的名字)

因此,建议对于银行应用程序等高度敏感的应用程序,密码管理器或安全通讯等应用程序在设置 setUserAuthenticationValidityDurationSeconds() 的值时不应该有除 -1以外的任何值。

这个脚本可用于使用 KeyguardManager 触发“设备解锁”状态,并解锁未将有效期设置为 -1的密钥。

生物特征 / 指纹认证

生物身份认证,特别是指纹身份验证,是在 Android 6.0(API 23)中引入的。 要使用指纹认证,必须符合以下条件:

1.设置需要支持 API 23或之后的API

2.设备上有可用的指纹传感器

3.至少有一个注册的指纹

4.应用程序需要将指纹权限包含在Manifest.xml 文件

生物身份认证可以通过 FingerprintManagerBiometricPrompt 类及其嵌套类来实现,这些类管理身份验证机制和应用程序对话,要求用户进行身份验证。 正如其名称所暗示的那样,FingerprintManager 只支持指纹认证。 FingerprintManager 类是在 API 23中引入的,自从发布 BiometricPrompt 的 API 28之后就不再支持了。在Android6.0(API23)的时候,Android系统加入了指纹识别的API接口,即FingerprintManager,定义了最基础的指纹识别接口。在AndroidP(API28)的时候,官方不再推荐使用FingerprintManager,在代码中添加了@Deprecated。在AndroidP中,原来的FingerprintManager将被BiometricPrompt类替换,Google旨在统一生物识别的方式(虽然目前api中还没有看到虹膜、面部识别等),包括UI,UI也不允许自定义了,必须使用BiometricPrompt.Builder来创建对话框,其中可以自定义title、subtitle、description和一个NegativeButton(也就是cancel键)。

BiometricPrompt 的使用非常类似于 FingerprintManager。使用 FingerprintManager 需要的权限为 android.permission.USE_FINGERPRINT,而使用 BiometricPrompt 则需要 android.permission.USE_BIOMETRIC。生物身份认证最重要的部分是以下方法:

public void authenticate (BiometricPrompt.CryptoObject crypto, 
                CancellationSignal cancel, 
                Executor executor, 
                BiometricPrompt.AuthenticationCallback callback)

该方法使生物识别的硬件开始工作,并开始扫描生物识别身份验证尝试。该方法有两个重要参数:

· crypto——它包含对应该解锁的 keystore 条目的引用。 为了以安全的方式实现生物认证,必须将密钥存储在这个加密对象中,用于某些应用程序关键的加密操作。

· callback——当用户将手指放在指纹传感器上或取消提示时,操作系统将调用这个回调结构

BiometricPrompt.AuthenticationCallback 参数用作回调结构,实现如下方法:

· onAuthenticationSucceeded(BiometricPrompt.AuthenticationResult result)

· onAuthenticationError()

· onAuthenticationFailed()

当系统成功地对用户进行身份验证时,onAuthenticationSucceded 方法会触发。 大多数遇到的生物身份认证实现都依赖于这个方法的调用,而不关心 CryptoObject。 负责解锁应用程序的应用程序逻辑通常包含在这个回调方法中。 该方法通过HOOK应用程序流程,直接调用 onAuthenticationSucceded 方法,从而在不提供有效生物特征的情况下解锁应用程序。

在接受评估的使用指纹认证的应用程序中,约有70% 可以解锁手机,甚至不需要有效的指纹。 此外,在50% 的情况下,解锁应用程序后,应用程序存储的数据被成功解密。

易受攻击的实现通常包含类似于下面所示的代码:

public void onAuthenticationSucceeded(FingerprintManager.AuthenticationResult result) {
Toast.makeText(getActivity(), "Access granted",Toast.LENGTH_LONG).show();
        accessGranted();
}

上面列出的代码不使用 AuthenticationResult 中传递的 CryptoObject,而只是假设身份验证成功,因为调用了 onAuthenticationSucceeded。

为了验证这个测试用例,我们创建了以下2个 Frida 脚本,它们可以用来测试不安全的生物身份认证 / 程序实现并绕过它们:

· 指纹绕过 ——该脚本将在不使用 crypto 对象时绕过身份验证。 身份验证实现依赖于回调 onAuthenticationSucceded 被调用。

· 通过异常处理绕过指纹——当使用CryptoObject但使用方式不正确时,此脚本将尝试绕过身份验证。这个问题的详细描述可以在“加密对象异常处理”一节中找到。

上面的脚本大多使用了钩子,用于重新实现 onAuthenticationSucceeded 回调的 authenticate 方法,而不是使用 onAuthenticationFailed 回调。

但是有可能以安全的方式实现本地身份验证吗?

是的。可以使用 AndroidKeystore。只需按照下面列出的步骤操作:

1. 将setUserAuthenticationRequired和setInvalidatedByBiometricEnrollment设置为true来创建Android密钥存储库。另外,setUserAuthenticationValidityDurationSeconds应该设置为-1。

2. 使用上面创建的密钥库密钥初始化cipher对象。

3. 使用前面步骤中的cipher对象创建BiometricPrompt.CryptoObject

4. 实现BiometricPrompt.AuthenticationCallback.onAuthenticationSucceeded 回调,该回调将从参数中检索cipher对象,并使用该cipher对象来解密其他一些关键数据,如会话密钥,或将用于解密应用程序数据的辅助对称密钥。

5. 调用 BiometricPrompt。使用在步骤3和步骤4中创建的crypto对象和回调函数进行身份验证。

这有那么难吗? :)

加密对象异常处理

有些开发人员使用 CryptoObject,但他们不加密 / 解密对应用程序正确运行至关重要的数据。 因此,我们可以完全跳过身份验证步骤,继续使用应用程序。

针对这种情况,我们发现了一种不同的绕过方法。 脚本需要做的就是手动调用一个未经认证的(不是由指纹解锁的) CryptoObject 成功完成身份验证。 但是,如果应用程序将尝试使用一个锁定的 cipher 对象,将抛出  javax.crypto.IllegalBlockSizeException 异常。 但是,没有什么可以阻止我们在 Frida 脚本中处理异常。

此脚本将尝试调用 onAuthenticationSucceded 并在 Cipher 类中捕获 javax.crypto.IllegalBlockSizeExceptionexceptions 异常。 因此,如果应用程序没有使用这个密钥来解密关键数据,那么你可能会在没有身份验证的情况下进入应用程序;)

那么,又该如何解决这个问题呢? 没有唯一的答案,这取决于本地身份验证的目的。 对于数据存储,最好的解决方案是使用受指纹保护的密钥存储库密钥,该密钥将用于... ... 解密二级对称密钥(因此,每次需要进行加密操作时,不会提示用户)。 此对称密钥应用于解密应用程序存储。 然而,如果你只是需要调用 authenticate,例如为了授权一个交易,你可以使用一个非对称私钥来加签数据,这些数据随后会被发送到验证签名服务端的服务器。

身份验证超时

有时候第一个身份验证调用可能不是欺骗性的,因为代码实现需要对“二级”解密密钥进行解密(如前所述)。 但是,在此之后的所有调用(例如应用程序超时)有时都是可欺骗的。 这是因为许多移动应用程序将加密密钥保存在内存中,直到进程被终止。 因此,如果在解锁应用程序之后尝试绕过身份验证,那么应用程序很有可能会使用已经存储在内存中的密钥:)

示例参考应用程序

在掌握了 IT 安全知识和一些开发技能后,我们决定创建一个项目,以正确的方式实现生物身份验证/服务。 下面的项目旨在创建一个应用程序,可用作安全本地验证的参考。

https://github.com/mwrlabs/android-keystore-audit/tree/master/keystorecrypto-app

是的,它可以在我们的 github 公共帐户上使用,你也可以支持这个项目!

参考资料:

· Android Keystore 官方文档

· BiometricPrompt 说明文档

· FingerprintManager 说明文档

· Biometric-Auth-Sample (不使用 CipherObject 的脆弱库,可以绕过身份验证)

· android-FingerprintDialog (Google 的示例应用程序使用 CipherObject 对静态字符串进行加密,base64编码的结果显示在用户界面上,但应用程序无需正常运行。 对于生产环境的应用,结果应该在服务器端进行验证,否则结果的正确性对应用程序至关重要。 可以跳过该示例来显示“Purchase successful”消息。)

你的 Android Keystore 认证有多安全?(上)

安卓 Keystore 和应用程序HOOK

安卓 Keystore 一直被认为是安全的,因为我们不能访问密钥信息。 但是,攻击者实际上可能并不需要密钥内容。 Keystore API 可用于检索密钥引用,然后可以使用它们初始化 Cipher 对象,然后可以使用它们对应用程序存储进行解密或加密。

是的,这是可能的,而且大多数应用程序都很容易受到这类攻击,正如具有设备实际访问权限或特权恶意软件的攻击者可以做到的那样:

a) 启动受害者应用程序

b) 使用 Frida 在受害者应用程序的上下文中执行代码,HOOK 受害者应用程序如下:

1. 使用 Keystore API 检索对 AndroidKeystore 密钥的引用

2. 使用检索到的密钥引用初始化密码对象

3. 在应用程序存储中解密/加密/签名数据

使用 Android Keystore 并不能保证二进制安全性。 为了防止这种攻击,开发人员必须将keystore 密钥标记为只有在以下情况下才能访问:

1. 设备已经解锁

2. 指纹或其他生物识别已被验证

对于此配置,开发人员必须在生成密钥期间将 setUserAuthenticationRequired() 设置为 true。 另一个重要属性是 setUserAuthenticationValidityDurationSeconds ()。 如果设置为 -1,那么只有使用指纹或生物识别技术才能解锁密钥。 如果它被设置为任何其他值,也可以使用设备屏幕锁解锁密钥。

在设备屏幕锁定的情况下,首先通过调用 KeyguardManager.createConfirmDeviceCredentialIntent() 来访问密钥。

需要注意的是,KeyguardManager API 不允许开发人员检查配置了哪种类型的屏幕锁,也不允许验证密码/PIN码/手势图案策略。 因此,这个设备可能有一个不安全的屏幕锁:

1. 简单的手势图案(在大多数设备上是3x3,可以通过尝试常见的图案或检查屏幕上的指纹进行猜测)

2. 简单的PIN码(通常是4-5个数字,常见的PIN码有0000或1234)

3. 另外也可以使用生活中的一些东西作为猜测密码(例如:你的狗的名字)

因此,建议对于银行应用程序等高度敏感的应用程序,密码管理器或安全通讯等应用程序在设置 setUserAuthenticationValidityDurationSeconds() 的值时不应该有除 -1以外的任何值。

这个脚本可用于使用 KeyguardManager 触发“设备解锁”状态,并解锁未将有效期设置为 -1的密钥。

生物特征 / 指纹认证

生物身份认证,特别是指纹身份验证,是在 Android 6.0(API 23)中引入的。 要使用指纹认证,必须符合以下条件:

1.设置需要支持 API 23或之后的API

2.设备上有可用的指纹传感器

3.至少有一个注册的指纹

4.应用程序需要将指纹权限包含在Manifest.xml 文件

生物身份认证可以通过 FingerprintManagerBiometricPrompt 类及其嵌套类来实现,这些类管理身份验证机制和应用程序对话,要求用户进行身份验证。 正如其名称所暗示的那样,FingerprintManager 只支持指纹认证。 FingerprintManager 类是在 API 23中引入的,自从发布 BiometricPrompt 的 API 28之后就不再支持了。在Android6.0(API23)的时候,Android系统加入了指纹识别的API接口,即FingerprintManager,定义了最基础的指纹识别接口。在AndroidP(API28)的时候,官方不再推荐使用FingerprintManager,在代码中添加了@Deprecated。在AndroidP中,原来的FingerprintManager将被BiometricPrompt类替换,Google旨在统一生物识别的方式(虽然目前api中还没有看到虹膜、面部识别等),包括UI,UI也不允许自定义了,必须使用BiometricPrompt.Builder来创建对话框,其中可以自定义title、subtitle、description和一个NegativeButton(也就是cancel键)。

BiometricPrompt 的使用非常类似于 FingerprintManager。使用 FingerprintManager 需要的权限为 android.permission.USE_FINGERPRINT,而使用 BiometricPrompt 则需要 android.permission.USE_BIOMETRIC。生物身份认证最重要的部分是以下方法:

public void authenticate (BiometricPrompt.CryptoObject crypto, 
                CancellationSignal cancel, 
                Executor executor, 
                BiometricPrompt.AuthenticationCallback callback)

该方法使生物识别的硬件开始工作,并开始扫描生物识别身份验证尝试。该方法有两个重要参数:

· crypto——它包含对应该解锁的 keystore 条目的引用。 为了以安全的方式实现生物认证,必须将密钥存储在这个加密对象中,用于某些应用程序关键的加密操作。

· callback——当用户将手指放在指纹传感器上或取消提示时,操作系统将调用这个回调结构

BiometricPrompt.AuthenticationCallback 参数用作回调结构,实现如下方法:

· onAuthenticationSucceeded(BiometricPrompt.AuthenticationResult result)

· onAuthenticationError()

· onAuthenticationFailed()

当系统成功地对用户进行身份验证时,onAuthenticationSucceded 方法会触发。 大多数遇到的生物身份认证实现都依赖于这个方法的调用,而不关心 CryptoObject。 负责解锁应用程序的应用程序逻辑通常包含在这个回调方法中。 该方法通过HOOK应用程序流程,直接调用 onAuthenticationSucceded 方法,从而在不提供有效生物特征的情况下解锁应用程序。

在接受评估的使用指纹认证的应用程序中,约有70% 可以解锁手机,甚至不需要有效的指纹。 此外,在50% 的情况下,解锁应用程序后,应用程序存储的数据被成功解密。

易受攻击的实现通常包含类似于下面所示的代码:

public void onAuthenticationSucceeded(FingerprintManager.AuthenticationResult result) {
Toast.makeText(getActivity(), "Access granted",Toast.LENGTH_LONG).show();
        accessGranted();
}

上面列出的代码不使用 AuthenticationResult 中传递的 CryptoObject,而只是假设身份验证成功,因为调用了 onAuthenticationSucceeded。

为了验证这个测试用例,我们创建了以下2个 Frida 脚本,它们可以用来测试不安全的生物身份认证 / 程序实现并绕过它们:

· 指纹绕过 ——该脚本将在不使用 crypto 对象时绕过身份验证。 身份验证实现依赖于回调 onAuthenticationSucceded 被调用。

· 通过异常处理绕过指纹——当使用CryptoObject但使用方式不正确时,此脚本将尝试绕过身份验证。这个问题的详细描述可以在“加密对象异常处理”一节中找到。

上面的脚本大多使用了钩子,用于重新实现 onAuthenticationSucceeded 回调的 authenticate 方法,而不是使用 onAuthenticationFailed 回调。

但是有可能以安全的方式实现本地身份验证吗?

是的。可以使用 AndroidKeystore。只需按照下面列出的步骤操作:

1. 将setUserAuthenticationRequired和setInvalidatedByBiometricEnrollment设置为true来创建Android密钥存储库。另外,setUserAuthenticationValidityDurationSeconds应该设置为-1。

2. 使用上面创建的密钥库密钥初始化cipher对象。

3. 使用前面步骤中的cipher对象创建BiometricPrompt.CryptoObject

4. 实现BiometricPrompt.AuthenticationCallback.onAuthenticationSucceeded 回调,该回调将从参数中检索cipher对象,并使用该cipher对象来解密其他一些关键数据,如会话密钥,或将用于解密应用程序数据的辅助对称密钥。

5. 调用 BiometricPrompt。使用在步骤3和步骤4中创建的crypto对象和回调函数进行身份验证。

这有那么难吗? :)

加密对象异常处理

有些开发人员使用 CryptoObject,但他们不加密 / 解密对应用程序正确运行至关重要的数据。 因此,我们可以完全跳过身份验证步骤,继续使用应用程序。

针对这种情况,我们发现了一种不同的绕过方法。 脚本需要做的就是手动调用一个未经认证的(不是由指纹解锁的) CryptoObject 成功完成身份验证。 但是,如果应用程序将尝试使用一个锁定的 cipher 对象,将抛出  javax.crypto.IllegalBlockSizeException 异常。 但是,没有什么可以阻止我们在 Frida 脚本中处理异常。

此脚本将尝试调用 onAuthenticationSucceded 并在 Cipher 类中捕获 javax.crypto.IllegalBlockSizeExceptionexceptions 异常。 因此,如果应用程序没有使用这个密钥来解密关键数据,那么你可能会在没有身份验证的情况下进入应用程序;)

那么,又该如何解决这个问题呢? 没有唯一的答案,这取决于本地身份验证的目的。 对于数据存储,最好的解决方案是使用受指纹保护的密钥存储库密钥,该密钥将用于... ... 解密二级对称密钥(因此,每次需要进行加密操作时,不会提示用户)。 此对称密钥应用于解密应用程序存储。 然而,如果你只是需要调用 authenticate,例如为了授权一个交易,你可以使用一个非对称私钥来加签数据,这些数据随后会被发送到验证签名服务端的服务器。

身份验证超时

有时候第一个身份验证调用可能不是欺骗性的,因为代码实现需要对“二级”解密密钥进行解密(如前所述)。 但是,在此之后的所有调用(例如应用程序超时)有时都是可欺骗的。 这是因为许多移动应用程序将加密密钥保存在内存中,直到进程被终止。 因此,如果在解锁应用程序之后尝试绕过身份验证,那么应用程序很有可能会使用已经存储在内存中的密钥:)

示例参考应用程序

在掌握了 IT 安全知识和一些开发技能后,我们决定创建一个项目,以正确的方式实现生物身份验证/服务。 下面的项目旨在创建一个应用程序,可用作安全本地验证的参考。

https://github.com/mwrlabs/android-keystore-audit/tree/master/keystorecrypto-app

是的,它可以在我们的 github 公共帐户上使用,你也可以支持这个项目!

参考资料:

· Android Keystore 官方文档

· BiometricPrompt 说明文档

· FingerprintManager 说明文档

· Biometric-Auth-Sample (不使用 CipherObject 的脆弱库,可以绕过身份验证)

· android-FingerprintDialog (Google 的示例应用程序使用 CipherObject 对静态字符串进行加密,base64编码的结果显示在用户界面上,但应用程序无需正常运行。 对于生产环境的应用,结果应该在服务器端进行验证,否则结果的正确性对应用程序至关重要。 可以跳过该示例来显示“Purchase successful”消息。)

引言

拥有特权的恶意软件或者可以实际访问安卓设备的攻击者是一个难以防范的攻击向量。 在这种情况下,你的应用程序如何保持安全性?

本文将讨论 Android keystore 机制以及在尝试实现安全本地身份验证时遇到的困难。 通过提供对 AndroidKeystore 的介绍,你将能够理解与密钥存储库相关的常见漏洞。 本文的核心将重点介绍可用于审计应用程序的本地身份验证的开发工具。 最后将提供关于安全实现的一般指导,并介绍一个可作为参考的应用程序。

Keystore 简介

Android Keystore 是一个允许开发人员在容器中创建和存储密钥的系统,这使得从设备中提取密钥变得更加困难。 这些密钥存储在专门的硬件中,即所谓的可信执行环境。 密钥可以在其内部生成,甚至操作系统本身也不应该直接访问这个安全内存。 Android Keystore 提供 API 来在这个受信任的环境中执行加密操作并接收结果。 它是在 API 18(Android 4.3)中引入的。 一个支持保险箱的 Android Keystore 是目前最安全和推荐的密钥存储类型。

利用 Android 密钥库系统,你可以在容器中存储加密密钥,从而提高从设备中提取密钥的难度。在密钥进入密钥库后,可以将它们用于加密操作,而密钥材料仍不可导出。此外,它提供了密钥使用的时间和方式限制措施,例如要求进行用户身份验证才能使用密钥,或者限制为只能在某些加密模式中使用。

keyStore有什么作用?

· 程序升级
新旧版本的数字证书相同时 Android系统才会认为这是同一程序的不同版本 如果数字证书不同 会 产生冲突 要求更改包名

· 程序的模块化和开发
拥有同一签名的程序可以运行在同一进程中 可以分模块开发 用户在需要的时候下载对应的模块

· 多个程序间共享数据和代码
Android 提供了基于数字证书的权限赋予机制 如果某个权限(permission)的protectionLevel是signature 则这个权限就只能授予那些跟该权限所在的包拥有同一个数字证书的程序。

密钥库系统并不是让程序直接进行存储程序的私密信息的,比如说用户账号密码,其提供了一个密钥安全容器,保护密钥材料免遭未经授权的使用,一个应用程序可以在密钥库中存储多个密钥并且只允许应用自身访问,应用程序可以在密钥库系统中生成,存储,获取存储其中的公钥或者私钥,因此可使用密钥库系统中的密钥来进行数据的加密。

密钥库系统由 KeyChain API 以及在 Android 4.3(API 级别 18)中引入的 Android 密钥库提供程序功能使用。

Android Keystore 支持7种不同类型的密钥存储机制,每种机制各有优缺点。 例如,Android Keystore 使用硬件芯片以安全的方式存储密钥,而 Bouncy Castle Keystore (BKS)是一个软件密钥存储库,并使用放置在文件系统上的加密文件。 Android 文档提供了许多对开发人员有用的代码示例,但是在描述其 keystore 机制时有些令人困惑和费解。 这导致了很多开发人员头疼的问题。 在许多与 keystore 相关的类中,Android 文档通常直接取自 Java 文档。 在没有找到一个简洁明了的解释和一个开发安全本地身份验证的解决方案之后,开发人员搜索到了 StackOverflow,直接复制和粘贴代码,这些代码不安全,可以很容易地用一些 Frida 脚本绕过。 支离破碎的 Android 生态系统也使得使用 keystore 成为一种不愉快的体验,因为需要执行多个兼容性检查,并且需要实现各种代码路径以支持各种设备。

让我们看看下面的截图。 左边是 Android 文档,右边是 Java 文档。

image.png

AndroidKeystore 实现不支持解锁密钥存储库或其特定条目的密码。 文档中显示的代码片段将引发异常。 上面的截图显示 Android 文档中的关于 AndroidKeystore 实现的知识来源并不是100% 的可靠。 由于 Android 支持一种不包含在传统 Java 中的新型密钥存储系统,因此上面的例子不适用于 AndroidKeystore。 在发现了更多的问题之后,我们决定更深入地研究一下 Android 中可用的 keystore 系统。 在本文的后续部分,你可以找到用于测试不安全密钥存储库使用情况的方法。

Keystores 到处都是 keystores

一个 Android Keystore 只是一个 Android 开发者可以使用的 Java 类。 Android Keystore 是 Java Keystore API 的另一个实现,其他类型的 Keystore,比如 BSK,也实现了这个 API。

我们可以使用普通的 Java KeyStore API 来访问 Android KeyStore:

KeyStore ks = KeyStore.getInstance("AndroidKeystore");

Keystore 类型

下面的表格列出了普通安卓系统(直到安卓9)支持的密钥库类型:

image.png

更新的列表可以在这篇博文中找到:

https://developer.android.com/reference/java/security/KeyStore

还有其他的密钥存储类型,例如三星支持它自己的名为 TIMA 的密钥存储类型。

如何使用 Android Keystore?

Java 密钥库 API 包含一个 java.security。 带有插入密钥的方法的 KeyStore 类。 但是,大多数应该在密钥库中插入密钥的调用都会引发异常。 这样做是为了防止开发人员插入硬编码的密钥。 Android Keystore 的假设是密钥永远不能离开可信环境,因此开发人员只能使用 android.security.keystore.KeyGenParameterSpec.Builder。 一个实现本地身份验证的示例引用应用程序可以点击这里查看

存储在密钥存储库中的每个密钥都可以设置以下参数:

· alias - 别名,用来识别密钥

· key size - 密钥大小(API 23)

· purpose –加密 / 解密(API 23)

· 加密模式、算法和填充(API 23)

· 密钥在使用之前是否应该通过密钥存储库进行身份验证(API 23)

· 一个成功的身份验证之后密钥可以被使用的持续时间(API 23)

· 新登记的指纹上的钥匙应该作废吗(API 24) ?

· 密钥存储库在执行加密操作之前是否应该要求解锁屏幕? (API 28) 

· 硬碟安全模组? 密钥应该由 StrongBox  硬件安全模块保护吗?(API 28)

支持的 Android API 版本包含在括号中,以显示在不同的 Android 版本中引入了哪些安全特性。 更多的设置和相关信息可以在适当的 Android 文档中找到。

让我们来讨论一下与密钥库相关的常见漏洞:

· 使用中的不安全密钥存储类型: 例如,如果正在使用 BKS 密钥存储,密钥存储在特权用户可以访问的文件中。 AndroidKeystore 支持硬件支持的容器,应该是首选的。

· 在新的指纹登记中没有失效的密钥: 有物理访问权限的攻击者可以登记他们自己的指纹并使用生物识别锁定的密钥。

· 无需屏幕解锁即可访问的 Keystore: 允许在不解锁屏幕的情况下使用密钥这无疑增加了攻击面。

· 使用中的弱加密算法: KeyGenerator.getInstance 方法中使用了弱加密算法。

· 为密钥存储库或密钥存储库条目设置了的弱密码或者硬编码了密码: 只有在可以设置密码访问密钥存储库时,才会出现这种类型的漏洞。 AndroidKeystore 是推荐的密钥存储类型,但如果应用程序设计需要使用软件支持的密钥存储,则建议设置一个强大的用户派生密码。

Frida 审计脚本

为了加快 keystore 审计并使评估更加健壮,我们准备了一些有用的 Frida 脚本。 这些脚本可以在这里找到。 下面的列表描述了它们的功能。

Keystore tracer

通用的 keystore 调试脚本:

· 列出应用程序使用的密钥存储类型

· 列出特定密钥存储库(或应用程序中的任何密钥存储库)使用的密钥存储库条目别名

· 列出所有关于 AndroidKeystore 密钥的信息。当确定是否可以绕过生物特征识别时非常有用。

· 在寻找有趣的密钥时,在逆向工程中有用的其他实用程序。

KeyGenParameterSpec tracer

· 列出有关在运行时使用 KeyGenParameterSpec API生成的密钥的信息。信息包括密钥大小、加密模式、算法等。

· 在审查应用程序中使用的加密时非常有用。

SecretKeyFactory tracer

· HOOK 掉 PBEKeySpec 构造函数和getInstance() 方法,以提取用于创建 PBKDF 密钥的密码、迭代次数、盐值和密钥大小。

· 在审查应用程序中使用的加密技术时非常有用——不仅仅是密钥库

Cipher tracer

· HOOK 掉 Cipher API,列出关于特定密钥的信息,如密钥大小、加密模式、算法等

· 在检查应用程序中使用的加密技术时非常有用——不仅仅是密钥存储

这些脚本可以通过以下命令启动:

$ frida -U -f com.example.keystorecrypto --no-pause -l SCRIPT-PATH.js

下面的代码片段显示了用于示例应用程序的 Keystore 跟踪程序脚本的输出:

$ frida -U -f com.example.keystorecrypto --no-pause -l keystore-tracer.js
...
[Google Pixel::com.example.keystorecrypto]-> KeystoreListAndroidKeystoreAliases()
...
[
    "'SYMMETRIC_MASTER_KEY'",
    "'ASYMMETRIC_MASTER_KEY'"
]
[Google Pixel::com.example.keystorecrypto]-> DumpKeystoreKeyInfo('SYMMETRIC_MASTER_KEY')
...
{
    "blockModes": [
        "GCM"
    ],
    "digests": [],
    "encryptionPaddings": [
        "NoPadding"
    ],
    "isInsideSecureHardware": true,
    "isInvalidatedByBiometricEnrollment": false,
    "isUserAuthenticationRequired": false,
    "isUserAuthenticationRequirementEnforcedBySecureHardware": true,
    "isUserAuthenticationValidWhileOnBody": false,
    "keyAlgorithm": "AES",
    "keySize": 256,
    "keyValidityForConsumptionEnd": null,
    "keyValidityForOriginationEnd": null,
    "keyValidityStart": null,
    "keystoreAlias": "SYMMETRIC_MASTER_KEY",
    "origin": 1,
    "purposes": 3,
    "signaturePaddings": [],
    "userAuthenticationValidityDurationSeconds": -1
}

如上所示,我们用一个函数发现了两个脆弱点:

· 可以添加新的指纹解锁应用程序

· 不需要对密钥使用进行用户身份验证

Cipher 跟踪程序可以成为检查加密操作非常有用的脚本。 该脚本转储有关应用程序使用的加密算法、模式和填充的信息。 此外,它 HOOK 了 doFinal 方法,并出现在加密 / 解密之前和之后可以理解为数据的操作输入和输出。 Cipher 跟踪输出的下列片段以可读的格式显示所描述的功能:

[Cipher.getInstance()]: type: AES/GCM/NoPadding
[Cipher.getInstance()]:  cipherObj: [email protected]
[Cipher.init()]: mode: Decrypt mode, secretKey: android.security.keystore.AndroidKeyStoreSecretKey spec:[object Object] , cipherObj: [email protected]
[Cipher.init()]: mode: Decrypt mode, secretKey: android.security.keystore.AndroidKeyStoreSecretKey spec:[object Object] secureRandom: [email protected] , cipherObj: [email protected]
[Cipher.doFinal2()]:   cipherObj: [email protected]
In buffer:
  Offset  00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00000000  B1 5A 1E 0F F3 19 AD 80 80 A7 8F 9A E5 F8 4A 1A  .Z............J.
00000010  5E DA C4 F0 D6 E0 0C 7D 56 14 6F 92 CA 4E B2 C0  ^......}V.o..N..
00000020  CD 42 A9 5F 06 05 BA 6B 9D 36 3A 73 61 87 34 C7  .B._...k.6:sa.4.
00000030  F8 BB 0C 2D 21 8A 80 2E FB 0B 41 EB 63 7B B4 12  ...-!.....A.c{..
00000040  BE A6 48 19 D2 C3 C7 97 9E 93 5E 6B 57 07 15 A0  ..H.......^kW...
00000050  A3 4F A6 07 C7 27 10 2B D0 81 3E 17 F6 C3 69 7D  .O...'.+..>...i}
00000060  25 F7 B2 0D 25 8D 72 6B 56 5B 95 4C FB CD 5F 69  %...%.rkV[.L.._i
00000070  74 A8 5E 91 29 0C 3D E5                          t.^.).=.        
Result:
  Offset  00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00000000  7B 22 63 6C 61 73 73 69 63 43 69 70 68 65 72 4B  {"classicCipherK
00000010  65 79 22 3A 6E 75 6C 6C 2C 22 63 6C 61 73 73 69  ey":null,"classi
00000020  63 4D 61 63 4B 65 79 22 3A 6E 75 6C 6C 2C 22 6D  cMacKey":null,"m
00000030  6F 64 65 72 6E 4B 65 79 22 3A 22 38 77 30 32 5A  odernKey":"8w02Z
00000040  61 47 4B 35 46 30 6D 64 46 38 66 76 61 5A 6C 4A  aGK5F0mdF8fvaZlJ
00000050  38 5A 50 74 54 37 74 42 74 72 37 66 45 58 4F 63  8ZPtT7tBtr7fEXOc
00000060  78 4E 6D 56 64 55 22 7D                          xNmVdU"}

安卓 Keystore 和应用程序 HOOK

所以我们有一个 Android Keystore,它被认为是安全的,因为我们不能访问密钥。 但是,攻击者实际上可能并不需要密钥内容。 Keystore API 可用于检索密钥引用,然后可以使用它们初始化 Cipher 对象,然后可以使用它们对应用程序存储进行解密或加密。

是的,这是可能的,而且大多数应用程序都很容易受到这类攻击,具有设备实际访问权限或拥有特权的恶意软件的攻击者可以做以下事情:

· 启动受害者的应用程序

· HOOK 受害者的应用程序并使用 Frida 在受害者应用程序的上下文中执行代码,可以做到如下事情:

· 使用Keystore API检索对AndroidKeystore密钥的引用。

· 使用检索到的密钥引用初始化密码对象。

· 在应用程序存储中解密/加密/签名数据。

啊! 使用 Android Keystore 并不能保证二进制安全性。 为了防止这种攻击,开发人员必须将密钥库密钥标记为只有在以下情况下才能访问:

· 设备已经解锁

· 指纹或其他生物识别技术已被验证

对于此配置,开发人员必须在生成密钥期间将 setUserAuthenticationRequired() 设置为 true。 另一个重要属性是 setUserAuthenticationValidityDurationSeconds()。 如果设置为 -1,那么只有使用指纹或生物识别技术才能解锁密钥。 如果它被设置为任何其他值,也可以使用设备屏幕锁解锁密钥。

在设备屏幕锁定的情况下,首先通过调用  KeyguardManager.createConfirmDeviceCredentialIntent()来访问密钥。

需要注意的是,KeyguardManager API 不允许开发人员检查配置了哪种类型的屏幕锁,也不允许验证密码或PIN码或手势图案模式策略。 因此,这个设备可能有一个不安全的屏幕锁:

· 简单的图案(在大多数设备上是3x3,可以通过尝试常见的图案或检查屏幕上的指纹来猜测)

· 简单的PIN码(通常是4-5个数字,常见的PIN码或特别简单的如0000或1234这样的连续PIN码)

· 可猜测的密码(你的狗的名字)

因此,建议对于银行应用程序等高度敏感的应用程序,密码管理器或安全信使的 setUserAuthenticationValidityDurationSeconds() 不应该有除 -1以外的任何值。

此脚本(https://github.com/mwrlabs/android-keystore-audit/blob/master/frida-scripts/keyguard-credential-intent.js)可用于使用 KeyguardManager 触发“设备解锁”状态,并解锁未将有效期设置为 -1的密钥。

引言

拥有特权的恶意软件或者可以实际访问安卓设备的攻击者是一个难以防范的攻击向量。 在这种情况下,你的应用程序如何保持安全性?

本文将讨论 Android keystore 机制以及在尝试实现安全本地身份验证时遇到的困难。 通过提供对 AndroidKeystore 的介绍,你将能够理解与密钥存储库相关的常见漏洞。 本文的核心将重点介绍可用于审计应用程序的本地身份验证的开发工具。 最后将提供关于安全实现的一般指导,并介绍一个可作为参考的应用程序。

Keystore 简介

Android Keystore 是一个允许开发人员在容器中创建和存储密钥的系统,这使得从设备中提取密钥变得更加困难。 这些密钥存储在专门的硬件中,即所谓的可信执行环境。 密钥可以在其内部生成,甚至操作系统本身也不应该直接访问这个安全内存。 Android Keystore 提供 API 来在这个受信任的环境中执行加密操作并接收结果。 它是在 API 18(Android 4.3)中引入的。 一个支持保险箱的 Android Keystore 是目前最安全和推荐的密钥存储类型。

利用 Android 密钥库系统,你可以在容器中存储加密密钥,从而提高从设备中提取密钥的难度。在密钥进入密钥库后,可以将它们用于加密操作,而密钥材料仍不可导出。此外,它提供了密钥使用的时间和方式限制措施,例如要求进行用户身份验证才能使用密钥,或者限制为只能在某些加密模式中使用。

keyStore有什么作用?

· 程序升级
新旧版本的数字证书相同时 Android系统才会认为这是同一程序的不同版本 如果数字证书不同 会 产生冲突 要求更改包名

· 程序的模块化和开发
拥有同一签名的程序可以运行在同一进程中 可以分模块开发 用户在需要的时候下载对应的模块

· 多个程序间共享数据和代码
Android 提供了基于数字证书的权限赋予机制 如果某个权限(permission)的protectionLevel是signature 则这个权限就只能授予那些跟该权限所在的包拥有同一个数字证书的程序。

密钥库系统并不是让程序直接进行存储程序的私密信息的,比如说用户账号密码,其提供了一个密钥安全容器,保护密钥材料免遭未经授权的使用,一个应用程序可以在密钥库中存储多个密钥并且只允许应用自身访问,应用程序可以在密钥库系统中生成,存储,获取存储其中的公钥或者私钥,因此可使用密钥库系统中的密钥来进行数据的加密。

密钥库系统由 KeyChain API 以及在 Android 4.3(API 级别 18)中引入的 Android 密钥库提供程序功能使用。

Android Keystore 支持7种不同类型的密钥存储机制,每种机制各有优缺点。 例如,Android Keystore 使用硬件芯片以安全的方式存储密钥,而 Bouncy Castle Keystore (BKS)是一个软件密钥存储库,并使用放置在文件系统上的加密文件。 Android 文档提供了许多对开发人员有用的代码示例,但是在描述其 keystore 机制时有些令人困惑和费解。 这导致了很多开发人员头疼的问题。 在许多与 keystore 相关的类中,Android 文档通常直接取自 Java 文档。 在没有找到一个简洁明了的解释和一个开发安全本地身份验证的解决方案之后,开发人员搜索到了 StackOverflow,直接复制和粘贴代码,这些代码不安全,可以很容易地用一些 Frida 脚本绕过。 支离破碎的 Android 生态系统也使得使用 keystore 成为一种不愉快的体验,因为需要执行多个兼容性检查,并且需要实现各种代码路径以支持各种设备。

让我们看看下面的截图。 左边是 Android 文档,右边是 Java 文档。

image.png

AndroidKeystore 实现不支持解锁密钥存储库或其特定条目的密码。 文档中显示的代码片段将引发异常。 上面的截图显示 Android 文档中的关于 AndroidKeystore 实现的知识来源并不是100% 的可靠。 由于 Android 支持一种不包含在传统 Java 中的新型密钥存储系统,因此上面的例子不适用于 AndroidKeystore。 在发现了更多的问题之后,我们决定更深入地研究一下 Android 中可用的 keystore 系统。 在本文的后续部分,你可以找到用于测试不安全密钥存储库使用情况的方法。

Keystores 到处都是 keystores

一个 Android Keystore 只是一个 Android 开发者可以使用的 Java 类。 Android Keystore 是 Java Keystore API 的另一个实现,其他类型的 Keystore,比如 BSK,也实现了这个 API。

我们可以使用普通的 Java KeyStore API 来访问 Android KeyStore:

KeyStore ks = KeyStore.getInstance("AndroidKeystore");

Keystore 类型

下面的表格列出了普通安卓系统(直到安卓9)支持的密钥库类型:

image.png

更新的列表可以在这篇博文中找到:

https://developer.android.com/reference/java/security/KeyStore

还有其他的密钥存储类型,例如三星支持它自己的名为 TIMA 的密钥存储类型。

如何使用 Android Keystore?

Java 密钥库 API 包含一个 java.security。 带有插入密钥的方法的 KeyStore 类。 但是,大多数应该在密钥库中插入密钥的调用都会引发异常。 这样做是为了防止开发人员插入硬编码的密钥。 Android Keystore 的假设是密钥永远不能离开可信环境,因此开发人员只能使用 android.security.keystore.KeyGenParameterSpec.Builder。 一个实现本地身份验证的示例引用应用程序可以点击这里查看

存储在密钥存储库中的每个密钥都可以设置以下参数:

· alias - 别名,用来识别密钥

· key size - 密钥大小(API 23)

· purpose –加密 / 解密(API 23)

· 加密模式、算法和填充(API 23)

· 密钥在使用之前是否应该通过密钥存储库进行身份验证(API 23)

· 一个成功的身份验证之后密钥可以被使用的持续时间(API 23)

· 新登记的指纹上的钥匙应该作废吗(API 24) ?

· 密钥存储库在执行加密操作之前是否应该要求解锁屏幕? (API 28) 

· 硬碟安全模组? 密钥应该由 StrongBox  硬件安全模块保护吗?(API 28)

支持的 Android API 版本包含在括号中,以显示在不同的 Android 版本中引入了哪些安全特性。 更多的设置和相关信息可以在适当的 Android 文档中找到。

让我们来讨论一下与密钥库相关的常见漏洞:

· 使用中的不安全密钥存储类型: 例如,如果正在使用 BKS 密钥存储,密钥存储在特权用户可以访问的文件中。 AndroidKeystore 支持硬件支持的容器,应该是首选的。

· 在新的指纹登记中没有失效的密钥: 有物理访问权限的攻击者可以登记他们自己的指纹并使用生物识别锁定的密钥。

· 无需屏幕解锁即可访问的 Keystore: 允许在不解锁屏幕的情况下使用密钥这无疑增加了攻击面。

· 使用中的弱加密算法: KeyGenerator.getInstance 方法中使用了弱加密算法。

· 为密钥存储库或密钥存储库条目设置了的弱密码或者硬编码了密码: 只有在可以设置密码访问密钥存储库时,才会出现这种类型的漏洞。 AndroidKeystore 是推荐的密钥存储类型,但如果应用程序设计需要使用软件支持的密钥存储,则建议设置一个强大的用户派生密码。

Frida 审计脚本

为了加快 keystore 审计并使评估更加健壮,我们准备了一些有用的 Frida 脚本。 这些脚本可以在这里找到。 下面的列表描述了它们的功能。

Keystore tracer

通用的 keystore 调试脚本:

· 列出应用程序使用的密钥存储类型

· 列出特定密钥存储库(或应用程序中的任何密钥存储库)使用的密钥存储库条目别名

· 列出所有关于 AndroidKeystore 密钥的信息。当确定是否可以绕过生物特征识别时非常有用。

· 在寻找有趣的密钥时,在逆向工程中有用的其他实用程序。

KeyGenParameterSpec tracer

· 列出有关在运行时使用 KeyGenParameterSpec API生成的密钥的信息。信息包括密钥大小、加密模式、算法等。

· 在审查应用程序中使用的加密时非常有用。

SecretKeyFactory tracer

· HOOK 掉 PBEKeySpec 构造函数和getInstance() 方法,以提取用于创建 PBKDF 密钥的密码、迭代次数、盐值和密钥大小。

· 在审查应用程序中使用的加密技术时非常有用——不仅仅是密钥库

Cipher tracer

· HOOK 掉 Cipher API,列出关于特定密钥的信息,如密钥大小、加密模式、算法等

· 在检查应用程序中使用的加密技术时非常有用——不仅仅是密钥存储

这些脚本可以通过以下命令启动:

$ frida -U -f com.example.keystorecrypto --no-pause -l SCRIPT-PATH.js

下面的代码片段显示了用于示例应用程序的 Keystore 跟踪程序脚本的输出:

$ frida -U -f com.example.keystorecrypto --no-pause -l keystore-tracer.js
...
[Google Pixel::com.example.keystorecrypto]-> KeystoreListAndroidKeystoreAliases()
...
[
    "'SYMMETRIC_MASTER_KEY'",
    "'ASYMMETRIC_MASTER_KEY'"
]
[Google Pixel::com.example.keystorecrypto]-> DumpKeystoreKeyInfo('SYMMETRIC_MASTER_KEY')
...
{
    "blockModes": [
        "GCM"
    ],
    "digests": [],
    "encryptionPaddings": [
        "NoPadding"
    ],
    "isInsideSecureHardware": true,
    "isInvalidatedByBiometricEnrollment": false,
    "isUserAuthenticationRequired": false,
    "isUserAuthenticationRequirementEnforcedBySecureHardware": true,
    "isUserAuthenticationValidWhileOnBody": false,
    "keyAlgorithm": "AES",
    "keySize": 256,
    "keyValidityForConsumptionEnd": null,
    "keyValidityForOriginationEnd": null,
    "keyValidityStart": null,
    "keystoreAlias": "SYMMETRIC_MASTER_KEY",
    "origin": 1,
    "purposes": 3,
    "signaturePaddings": [],
    "userAuthenticationValidityDurationSeconds": -1
}

如上所示,我们用一个函数发现了两个脆弱点:

· 可以添加新的指纹解锁应用程序

· 不需要对密钥使用进行用户身份验证

Cipher 跟踪程序可以成为检查加密操作非常有用的脚本。 该脚本转储有关应用程序使用的加密算法、模式和填充的信息。 此外,它 HOOK 了 doFinal 方法,并出现在加密 / 解密之前和之后可以理解为数据的操作输入和输出。 Cipher 跟踪输出的下列片段以可读的格式显示所描述的功能:

[Cipher.getInstance()]: type: AES/GCM/NoPadding
[Cipher.getInstance()]:  cipherObj: [email protected]
[Cipher.init()]: mode: Decrypt mode, secretKey: android.security.keystore.AndroidKeyStoreSecretKey spec:[object Object] , cipherObj: [email protected]
[Cipher.init()]: mode: Decrypt mode, secretKey: android.security.keystore.AndroidKeyStoreSecretKey spec:[object Object] secureRandom: [email protected] , cipherObj: [email protected]
[Cipher.doFinal2()]:   cipherObj: [email protected]
In buffer:
  Offset  00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00000000  B1 5A 1E 0F F3 19 AD 80 80 A7 8F 9A E5 F8 4A 1A  .Z............J.
00000010  5E DA C4 F0 D6 E0 0C 7D 56 14 6F 92 CA 4E B2 C0  ^......}V.o..N..
00000020  CD 42 A9 5F 06 05 BA 6B 9D 36 3A 73 61 87 34 C7  .B._...k.6:sa.4.
00000030  F8 BB 0C 2D 21 8A 80 2E FB 0B 41 EB 63 7B B4 12  ...-!.....A.c{..
00000040  BE A6 48 19 D2 C3 C7 97 9E 93 5E 6B 57 07 15 A0  ..H.......^kW...
00000050  A3 4F A6 07 C7 27 10 2B D0 81 3E 17 F6 C3 69 7D  .O...'.+..>...i}
00000060  25 F7 B2 0D 25 8D 72 6B 56 5B 95 4C FB CD 5F 69  %...%.rkV[.L.._i
00000070  74 A8 5E 91 29 0C 3D E5                          t.^.).=.        
Result:
  Offset  00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00000000  7B 22 63 6C 61 73 73 69 63 43 69 70 68 65 72 4B  {"classicCipherK
00000010  65 79 22 3A 6E 75 6C 6C 2C 22 63 6C 61 73 73 69  ey":null,"classi
00000020  63 4D 61 63 4B 65 79 22 3A 6E 75 6C 6C 2C 22 6D  cMacKey":null,"m
00000030  6F 64 65 72 6E 4B 65 79 22 3A 22 38 77 30 32 5A  odernKey":"8w02Z
00000040  61 47 4B 35 46 30 6D 64 46 38 66 76 61 5A 6C 4A  aGK5F0mdF8fvaZlJ
00000050  38 5A 50 74 54 37 74 42 74 72 37 66 45 58 4F 63  8ZPtT7tBtr7fEXOc
00000060  78 4E 6D 56 64 55 22 7D                          xNmVdU"}

安卓 Keystore 和应用程序 HOOK

所以我们有一个 Android Keystore,它被认为是安全的,因为我们不能访问密钥。 但是,攻击者实际上可能并不需要密钥内容。 Keystore API 可用于检索密钥引用,然后可以使用它们初始化 Cipher 对象,然后可以使用它们对应用程序存储进行解密或加密。

是的,这是可能的,而且大多数应用程序都很容易受到这类攻击,具有设备实际访问权限或拥有特权的恶意软件的攻击者可以做以下事情:

· 启动受害者的应用程序

· HOOK 受害者的应用程序并使用 Frida 在受害者应用程序的上下文中执行代码,可以做到如下事情:

· 使用Keystore API检索对AndroidKeystore密钥的引用。

· 使用检索到的密钥引用初始化密码对象。

· 在应用程序存储中解密/加密/签名数据。

啊! 使用 Android Keystore 并不能保证二进制安全性。 为了防止这种攻击,开发人员必须将密钥库密钥标记为只有在以下情况下才能访问:

· 设备已经解锁

· 指纹或其他生物识别技术已被验证

对于此配置,开发人员必须在生成密钥期间将 setUserAuthenticationRequired() 设置为 true。 另一个重要属性是 setUserAuthenticationValidityDurationSeconds()。 如果设置为 -1,那么只有使用指纹或生物识别技术才能解锁密钥。 如果它被设置为任何其他值,也可以使用设备屏幕锁解锁密钥。

在设备屏幕锁定的情况下,首先通过调用  KeyguardManager.createConfirmDeviceCredentialIntent()来访问密钥。

需要注意的是,KeyguardManager API 不允许开发人员检查配置了哪种类型的屏幕锁,也不允许验证密码或PIN码或手势图案模式策略。 因此,这个设备可能有一个不安全的屏幕锁:

· 简单的图案(在大多数设备上是3x3,可以通过尝试常见的图案或检查屏幕上的指纹来猜测)

· 简单的PIN码(通常是4-5个数字,常见的PIN码或特别简单的如0000或1234这样的连续PIN码)

· 可猜测的密码(你的狗的名字)

因此,建议对于银行应用程序等高度敏感的应用程序,密码管理器或安全信使的 setUserAuthenticationValidityDurationSeconds() 不应该有除 -1以外的任何值。

此脚本(https://github.com/mwrlabs/android-keystore-audit/blob/master/frida-scripts/keyguard-credential-intent.js)可用于使用 KeyguardManager 触发“设备解锁”状态,并解锁未将有效期设置为 -1的密钥。

本系列文章的译文:

你必须知道的密码学理论:随机预言模型(一)

你必须知道的密码学理论:随机预言模型(二)

在我开始写这一系列文章时,我希望能够写出一篇能真正让外行人了解随机预言( Random Oracle)模型的系列文章。 我在前面那几篇不太专业的文章中把这个问题已经解决了。 然而,现在我已经在三号位了,还有一大堆技术问题需要解决。

在接下来的本系列文章中,我们将讨论一些可靠、实用的密码学问题。

快速回顾一下

在前两篇文章中,我们已经讨论了一些内容。 我们讨论了加密哈希函数及其性质,并讨论了为什么密码学家的“理想”哈希函数是一个随机函数。 我们注意到,随机函数在现实生活中永远不会起作用(存储太大,计算太慢) ,因此我们得出了一个奇怪的结论: 我们假装我们的哈希是随机函数,只是为了安全分析的目的。 然后当然我们会使用真正的哈希函数,比如 SHA。

当然,即使是这样,我们也需要改变宇宙的结构,因为我们想要限制我们的“对手”在合理的时间内运行,而如果他们忙于评估随机函数,他们就无法做到这一点。因此,我们创造了一种新的计算模型(又名“思想实验”) ,称为随机预言模型。 在这个模型中,所有的哈希都是由一个叫做预言的神奇的第三方计算出来的。

如果你对随机预言模型有一点了解,比如说在阅读前面的文章时,你可以原谅自己认为它并没有那么糟糕。 基本上,我们假设哈希函数是超级“随机”函数。 可能比一个真正的函数要多一点,但是很重要。

但不幸的是,远不止这些。

这可能是世界上最短的可证明的安全课程

为了解释我的意思,我们首先需要了解一点可证明的安全性,特别是一种叫做约简证明的证明。

当我们说一个加密方案是“可证明的安全”时,我们通常指的是在某种假设下它是安全的。 对于大多数实际的方案来说,这个假设本质上是数学性质的。 例如,我们可以假设很难分解大的复合数,或者很难在格中找到最短的向量,从而找到一个加密方案。 在这种情况下,“难搞”并不意味着“我不知道该怎么做”。它的意思是: 没有(有效的)算法可以做到这一点。1

现在,我提到这些都是假设。 我们并不完全知道这些问题是困难的。 然而,我们倾向于认为,如果一些聪明的人已经注意到这个问题有一段时间了,但是没有人在解决这个问题上取得任何进展,那就意味着这可能并不容易。 在某些情况下,问题甚至可能属于一类有用的问题,例如,它可能是一个 NP-Hard 问题(译者注:NP-hard 请参见百度百科的解释)。

即使你不愿盲目相信这些假设,安全性证据仍然是有用的。 分析一个新的密码系统可以消耗大量的时间和精力。 如果我们至少可以将每个新方案“简化”为少数几个数学问题中的一个,我们就可以倾注我们的脑力来解决这些问题,因为我们知道我们的工作将适用于每个使用这些问题的方案。

所有这些带出了我的主要观点,即,这些证明是如何工作的。 具体来说,这种证明的一般流程如下:

1. 假设问题 X 很难。1

2. 证明如果存在一个(有效的)算法来“破坏”我们的加密方案,那么就存在一个(有效的)算法来解决问题X。

3. 含蓄地指出(2)意味着如果方案可以被打破,那么问题X就不会很难。

如果第(1)点为真,那么第(3)点显然不可能为真。 根据这个逻辑,我们可以得出这样的结论: 如果问题 X 很难,那么就不可能有算法破解我们的加密方案。

当然,我还没有解释如何实际完成步骤(2) ,这是非常重要的。 这也是最美妙的部分。 你看,在大多数简化中,步骤(2)实际上包括编写一个解决问题 X 的有效算法。

你可能觉得我疯了。 我刚刚声称 X 问题不能有效地解决,现在我又告诉你们,我们写了一个算法可以解决这个问题。 但它的天才之处在于,我们的求解算法不能很好地工作。 它缺少一个重要的子程序。

这个子例程在 API 级别上与“破解”我们的加密方案的算法是一样的。

因此,这就是争论的症结所在:假设有一种算法有效地“破坏”了我们的加密方案,那么我们可以把它塞进我们的“求解器”算法留下的洞里。这将产生一个有效地解决 X 问题的算法,因此,它完全满足我们在点(2)中所要求的。

黑匣子

有了这个基础,我只需要再说一点。 有一个基本的简化证明必须遵守的限制。 我们的“问题 X 解决程序”算法必须使用“加密方案破坏程序”的子程序作为一个黑盒。它无法对破坏程序算法的内部工作方式做出假设。

让我更清楚地说明这一点。例如,我们不能在“求解器”算法中对破坏程序算法进行反编译,或者窥视它的内部内存寄存器,然后假定它们将包含我们需要的部分结果。

这是因为我们的简化只有当它与打破方案的每一个可能的算法一起工作时才有效。 因为我们不能预先猜测这样的算法在内部是如何工作的,我们不能依赖于它的内部工作。 破解加密程序的算法会被可怕地混淆,以至于我们无法理解它,即使我们把代码握在手中。

因此,在传统的黑盒简化中,我们可以指望破坏程序算法有一个标准的“ API”(我们将在某个时候进行定义)。 它通常接受公钥和密文(或签名等) ,并输出一些有用的信息,这些信息构成了我们对“破坏”的定义。 尽管它并不总是需要成功,但我们希望它能够以合理的概率成功。 但是算法中发生的所有事情都必须对我们隐瞒。

脏衣服的故事

你不会认为这和可证明的安全性有任何关系。

让我们暂停一下,来考虑一下名人新闻领域的一些相关问题。

想象一下,你是一个揭发丑闻的名人记者,被指派去挖掘布拉德 · 皮特和安吉丽娜 · 朱莉最近收养的孩子的独家新闻。 皮特和乔利夫妇非常注重隐私,他们甚至不愿意承认自己正在领养孩子。 你是个聪明的记者,更重要的是,你没有道德。

你知道,如果你能看一眼家里的洗衣房,你就能知道整个故事了。 性别,大小,体重,最喜欢的颜色。 甚至饮食(安吉丽娜坚持使用环保的布尿布)。 在一个完美的世界里,你可以开车去皮特 / 朱莉的洗衣公司,塞给某人500美元,你的整个故事就会写在衣服上。 如果你真的很狡猾,你可以开始自己的名人洗衣服务,骗他们直接寄给你。

但这都是一厢情愿的想法。 皮特和朱莉不会把要洗的衣服送出去——他们在家里洗衣服。 事实上,你甚至不确定他们是否会洗衣服。 你听说过安吉丽娜每次用完衣服都要烧掉的传言。

如果你看不出它的相关性,可以琢磨一下这个类似于简化证明的例子。对你来说,“破解程序”算法是一个黑匣子。你可以看到输入进去,也可以看到输出,但你却看不到它在这两者之间做了什么。如果你的降价取决于看它的脏衣服,你最好拿出一个更好的削减。它自己洗衣服。

回到随机预言模型

随机预言模型是不同的。 在我之前的文章中,我解释说这就像现实世界一样,只有一个例外: 没有人能够自己计算哈希。 每一方——包括敌方(“破解程序”算法的同义词)——都必须通过向特定的外部方发送消息来进行哈希。 该方使用随机函数计算哈希,并将其发送回调用方。

为了使这一点非常清楚,在 Random Oracle 模型中,每个人都要送洗的衣服。

在随机预言模型中,预言为包括敌方在内的所有各方计算哈希。

如果我们建立一个简化,则意味着我们可以利用从这些调用中泄露的额外信息,就像我们的八卦记者可以利用名人的洗衣房。 我们知道算法必须进行这些哈希调用,因此必须在 API 中存在一个“端口”来进行这些调用。 一旦我们制定了这个规定,我们的简化就可以进入这个端口,拦截敌方的哈希调用,查看它要求的消息,甚至可能篡改它返回的结果。更正式地说,在随机预言模型中,对手(也就是我们的“破解程序”算法)不再完全是一个黑盒子。 在一个非常重要的方面,我们可以看到它。 如果它想要进行哈希操作,它就必须在自身之外进行调用。

在一个极端的情况下,我们的简化甚至可以运行自己的假“预言”(又名洗衣服务) ,只要我们始终回复令人信服的答复。

虽然这看起来没什么大不了的,但实际上却很重要。 就像布拉德·皮特和安吉丽娜·朱莉的丑闻可以揭示明星们私生活的主要细节一样,“破解程序”算法选择哪些信息来哈希可以揭示明星们内心想法的主要细节。 通过篡改这些响应,我们也可以从根本上改变它的操作。 这些细节可以区分证明的还原是有效的还是无效的。

评估

在这一点上,我认为值得深呼吸一下,问问我们自己到底陷入了什么境地。 当我们开始做这些无意义的事情时,我们想要的只是一个更好的哈希函数。 这个函数看起来比我们构造的任何实际函数都要随机一些。

在这个过程中,我们意识到随机函数是完全不切实际的。 甚至为了假装我们可以使用它们,我们不得不篡改我们的计算模型,把随机函数放到各个参与方之外。 毕竟,它们是在多项式时间内运行的,不可能求出这样的函数。

这些步骤似乎都是完全合理的,然而我们在某个地方遇到了麻烦。 我们违背了最神圣的还原主义安全原则。 我们现在不再说“我们的论点对任何对手都有效” ,而是说“我们的论点只对那些善意地告诉我们任何他们需要解决的问题的对手有效”。

真正的对手不是这样的。 如果有人想出一个算法来破坏真正使用了哈希函数(比如 SHA256)的 RSA-OAEP 实现,那么该算法不需要告诉我们它是什么哈希算法。 它只是在内部做这件事。 如果它的代码是模糊的,我们甚至不能连接到我们的简化,如果我们的简化依赖于知道(或篡改)哈希调用。

本系列文章的译文:

你必须知道的密码学理论:随机预言模型(一)

你必须知道的密码学理论:随机预言模型(二)

在我开始写这一系列文章时,我希望能够写出一篇能真正让外行人了解随机预言( Random Oracle)模型的系列文章。 我在前面那几篇不太专业的文章中把这个问题已经解决了。 然而,现在我已经在三号位了,还有一大堆技术问题需要解决。

在接下来的本系列文章中,我们将讨论一些可靠、实用的密码学问题。

快速回顾一下

在前两篇文章中,我们已经讨论了一些内容。 我们讨论了加密哈希函数及其性质,并讨论了为什么密码学家的“理想”哈希函数是一个随机函数。 我们注意到,随机函数在现实生活中永远不会起作用(存储太大,计算太慢) ,因此我们得出了一个奇怪的结论: 我们假装我们的哈希是随机函数,只是为了安全分析的目的。 然后当然我们会使用真正的哈希函数,比如 SHA。

当然,即使是这样,我们也需要改变宇宙的结构,因为我们想要限制我们的“对手”在合理的时间内运行,而如果他们忙于评估随机函数,他们就无法做到这一点。因此,我们创造了一种新的计算模型(又名“思想实验”) ,称为随机预言模型。 在这个模型中,所有的哈希都是由一个叫做预言的神奇的第三方计算出来的。

如果你对随机预言模型有一点了解,比如说在阅读前面的文章时,你可以原谅自己认为它并没有那么糟糕。 基本上,我们假设哈希函数是超级“随机”函数。 可能比一个真正的函数要多一点,但是很重要。

但不幸的是,远不止这些。

这可能是世界上最短的可证明的安全课程

为了解释我的意思,我们首先需要了解一点可证明的安全性,特别是一种叫做约简证明的证明。

当我们说一个加密方案是“可证明的安全”时,我们通常指的是在某种假设下它是安全的。 对于大多数实际的方案来说,这个假设本质上是数学性质的。 例如,我们可以假设很难分解大的复合数,或者很难在格中找到最短的向量,从而找到一个加密方案。 在这种情况下,“难搞”并不意味着“我不知道该怎么做”。它的意思是: 没有(有效的)算法可以做到这一点。1

现在,我提到这些都是假设。 我们并不完全知道这些问题是困难的。 然而,我们倾向于认为,如果一些聪明的人已经注意到这个问题有一段时间了,但是没有人在解决这个问题上取得任何进展,那就意味着这可能并不容易。 在某些情况下,问题甚至可能属于一类有用的问题,例如,它可能是一个 NP-Hard 问题(译者注:NP-hard 请参见百度百科的解释)。

即使你不愿盲目相信这些假设,安全性证据仍然是有用的。 分析一个新的密码系统可以消耗大量的时间和精力。 如果我们至少可以将每个新方案“简化”为少数几个数学问题中的一个,我们就可以倾注我们的脑力来解决这些问题,因为我们知道我们的工作将适用于每个使用这些问题的方案。

所有这些带出了我的主要观点,即,这些证明是如何工作的。 具体来说,这种证明的一般流程如下:

1. 假设问题 X 很难。1

2. 证明如果存在一个(有效的)算法来“破坏”我们的加密方案,那么就存在一个(有效的)算法来解决问题X。

3. 含蓄地指出(2)意味着如果方案可以被打破,那么问题X就不会很难。

如果第(1)点为真,那么第(3)点显然不可能为真。 根据这个逻辑,我们可以得出这样的结论: 如果问题 X 很难,那么就不可能有算法破解我们的加密方案。

当然,我还没有解释如何实际完成步骤(2) ,这是非常重要的。 这也是最美妙的部分。 你看,在大多数简化中,步骤(2)实际上包括编写一个解决问题 X 的有效算法。

你可能觉得我疯了。 我刚刚声称 X 问题不能有效地解决,现在我又告诉你们,我们写了一个算法可以解决这个问题。 但它的天才之处在于,我们的求解算法不能很好地工作。 它缺少一个重要的子程序。

这个子例程在 API 级别上与“破解”我们的加密方案的算法是一样的。

因此,这就是争论的症结所在:假设有一种算法有效地“破坏”了我们的加密方案,那么我们可以把它塞进我们的“求解器”算法留下的洞里。这将产生一个有效地解决 X 问题的算法,因此,它完全满足我们在点(2)中所要求的。

黑匣子

有了这个基础,我只需要再说一点。 有一个基本的简化证明必须遵守的限制。 我们的“问题 X 解决程序”算法必须使用“加密方案破坏程序”的子程序作为一个黑盒。它无法对破坏程序算法的内部工作方式做出假设。

让我更清楚地说明这一点。例如,我们不能在“求解器”算法中对破坏程序算法进行反编译,或者窥视它的内部内存寄存器,然后假定它们将包含我们需要的部分结果。

这是因为我们的简化只有当它与打破方案的每一个可能的算法一起工作时才有效。 因为我们不能预先猜测这样的算法在内部是如何工作的,我们不能依赖于它的内部工作。 破解加密程序的算法会被可怕地混淆,以至于我们无法理解它,即使我们把代码握在手中。

因此,在传统的黑盒简化中,我们可以指望破坏程序算法有一个标准的“ API”(我们将在某个时候进行定义)。 它通常接受公钥和密文(或签名等) ,并输出一些有用的信息,这些信息构成了我们对“破坏”的定义。 尽管它并不总是需要成功,但我们希望它能够以合理的概率成功。 但是算法中发生的所有事情都必须对我们隐瞒。

脏衣服的故事

你不会认为这和可证明的安全性有任何关系。

让我们暂停一下,来考虑一下名人新闻领域的一些相关问题。

想象一下,你是一个揭发丑闻的名人记者,被指派去挖掘布拉德 · 皮特和安吉丽娜 · 朱莉最近收养的孩子的独家新闻。 皮特和乔利夫妇非常注重隐私,他们甚至不愿意承认自己正在领养孩子。 你是个聪明的记者,更重要的是,你没有道德。

你知道,如果你能看一眼家里的洗衣房,你就能知道整个故事了。 性别,大小,体重,最喜欢的颜色。 甚至饮食(安吉丽娜坚持使用环保的布尿布)。 在一个完美的世界里,你可以开车去皮特 / 朱莉的洗衣公司,塞给某人500美元,你的整个故事就会写在衣服上。 如果你真的很狡猾,你可以开始自己的名人洗衣服务,骗他们直接寄给你。

但这都是一厢情愿的想法。 皮特和朱莉不会把要洗的衣服送出去——他们在家里洗衣服。 事实上,你甚至不确定他们是否会洗衣服。 你听说过安吉丽娜每次用完衣服都要烧掉的传言。

如果你看不出它的相关性,可以琢磨一下这个类似于简化证明的例子。对你来说,“破解程序”算法是一个黑匣子。你可以看到输入进去,也可以看到输出,但你却看不到它在这两者之间做了什么。如果你的降价取决于看它的脏衣服,你最好拿出一个更好的削减。它自己洗衣服。

回到随机预言模型

随机预言模型是不同的。 在我之前的文章中,我解释说这就像现实世界一样,只有一个例外: 没有人能够自己计算哈希。 每一方——包括敌方(“破解程序”算法的同义词)——都必须通过向特定的外部方发送消息来进行哈希。 该方使用随机函数计算哈希,并将其发送回调用方。

为了使这一点非常清楚,在 Random Oracle 模型中,每个人都要送洗的衣服。

在随机预言模型中,预言为包括敌方在内的所有各方计算哈希。

如果我们建立一个简化,则意味着我们可以利用从这些调用中泄露的额外信息,就像我们的八卦记者可以利用名人的洗衣房。 我们知道算法必须进行这些哈希调用,因此必须在 API 中存在一个“端口”来进行这些调用。 一旦我们制定了这个规定,我们的简化就可以进入这个端口,拦截敌方的哈希调用,查看它要求的消息,甚至可能篡改它返回的结果。更正式地说,在随机预言模型中,对手(也就是我们的“破解程序”算法)不再完全是一个黑盒子。 在一个非常重要的方面,我们可以看到它。 如果它想要进行哈希操作,它就必须在自身之外进行调用。

在一个极端的情况下,我们的简化甚至可以运行自己的假“预言”(又名洗衣服务) ,只要我们始终回复令人信服的答复。

虽然这看起来没什么大不了的,但实际上却很重要。 就像布拉德·皮特和安吉丽娜·朱莉的丑闻可以揭示明星们私生活的主要细节一样,“破解程序”算法选择哪些信息来哈希可以揭示明星们内心想法的主要细节。 通过篡改这些响应,我们也可以从根本上改变它的操作。 这些细节可以区分证明的还原是有效的还是无效的。

评估

在这一点上,我认为值得深呼吸一下,问问我们自己到底陷入了什么境地。 当我们开始做这些无意义的事情时,我们想要的只是一个更好的哈希函数。 这个函数看起来比我们构造的任何实际函数都要随机一些。

在这个过程中,我们意识到随机函数是完全不切实际的。 甚至为了假装我们可以使用它们,我们不得不篡改我们的计算模型,把随机函数放到各个参与方之外。 毕竟,它们是在多项式时间内运行的,不可能求出这样的函数。

这些步骤似乎都是完全合理的,然而我们在某个地方遇到了麻烦。 我们违背了最神圣的还原主义安全原则。 我们现在不再说“我们的论点对任何对手都有效” ,而是说“我们的论点只对那些善意地告诉我们任何他们需要解决的问题的对手有效”。

真正的对手不是这样的。 如果有人想出一个算法来破坏真正使用了哈希函数(比如 SHA256)的 RSA-OAEP 实现,那么该算法不需要告诉我们它是什么哈希算法。 它只是在内部做这件事。 如果它的代码是模糊的,我们甚至不能连接到我们的简化,如果我们的简化依赖于知道(或篡改)哈希调用。