如何利用密码学以及数论基础攻击一个“宣称安全”的密码系统

最近在对基于区块链构建的信任社会(未来社会形态)非常感兴趣,区块技术去中心化的特性,让没有金融机构成为了可能(包括央行,以及各种商业银行)。

除了在数字货币领域大放异彩外,在包括供应链,网络购物,公平合约等方面的应用也非常广泛。其中智能合约的特性十分的吸引我。

不过我今天并不想讨论区块技术,因为区块技术建立在密码学的技术之上,今天我们讨论如何利用密码学以及数论基础攻击一个宣称安全的密码系统。

在密码学中,算法,秘钥以及协议构成了一个完整的密码系统。

算法是密码系统的基础,它是将一组或多组输入信息转化成一组或多组输出信息的数学方法,算法的输出会被秘钥影响,秘钥不同,输出也不同。因此,加密同样的信息,A用秘钥Ka加密与B用秘钥Kb加密输出的信息是完全不同的。

秘钥是密码系统的核心,奥秘在于算法存在一个最优解(最优解有很多种解释,例如超递增序列,因式分解两素数之和等),这个秘密就是秘钥。如果一个人想要解密别人的密文,在不知道秘钥的情况下,他只能尝试解数学难题,这对于普通人拥有的资源来说,直到宇宙毁灭也无法得出答案。

有了算法和秘钥,没有协议就不是一个密码系统。协议是指由多方参与的,确定要去完成一些事情。如果没有多方参与,或者没有去完成一些目标就不叫协议。协议有很多种,最明显比如秘钥交换协议(例如A和B要在一个加密的通道中传递信息,在这之前A和B要协商一个秘钥并交换,使得A可以加密消息发送给B并确保B可以解密信息)。

密钥交换协议

在一个安全的密码系统中,必须是算法,秘钥,协议都安全,如果其中一个是不安全的,那么整个系统就是不安全的。

大多数流行的公开算法,已经被广泛的证明是安全的,它们经历过很多理论数学家的分析。秘钥的安全性由秘钥长度,以及你是否妥当的保管你的秘钥来决定。如果你做的不错,那么秘钥也是安全的。

协议却不是如此了,协议很脆弱。举个例子,A将重要的信息加密发送给B,只有B有秘钥可以解密这些信息,C在网路上监听到了A发送给B的秘密,但是C没有秘钥无法解密信息,怎么办。上面说过,秘钥是这个数学难题的最优解,如果没有秘钥,C就只能尝试解数学难题,恐怕C这一生都无法解开,但是C的老板要求他必须在72小时内解密信息,不然C所在的公司就要遭受重大损失。于是C决定铤而走险,他绑架了B,并对B进行严刑拷打,B扛不住,交出了他的秘钥,C拿着B的秘钥解密了秘密,并干掉了B。

上面的例子说明了协议在整个密码系统中是一个易攻击的薄弱环节,这样的攻击类型很多(贿赂,美色诱惑,威胁等)。

我们来尝试把这种攻击带入到软件破解上来,同样的结论也是攻击协议,而非攻击算法和秘钥。同样来举个例子,软件D采用RSA公开秘钥算法来对用户的信息以及软件产品序列号摘要进行加密,并发送给软件D公司的注册服务器,软件公司D的计算机收到用户A发送给它的加密信息,用自己的私钥解密并把用户信息与数据库中的信息进行对比,如果序列号不在D公司的数据库中说明这个产品的不是D公司销售的产品,如果序列号在D公司的数据库中,并且A用户信息不在数据库中,那么A是第一次注册,将A的信息与序列号绑定在一起保存在数据库中,此序列号将不能再给其他人使用。如果序列号和A都在数据库中,并且序列号与A绑定,那么D公司用私钥加密一段许可信息发送给A,A每次使用D软件的时候验证这段信息,如果是D公司发送的许可信息允许使用,如果不是不允许登陆。

看起来很不错,RSA是安全的公开密钥算法,并且秘钥被D公司保存起来,除非你能贿赂D公司的员工获得秘钥,或者攻破D公司的网路,否则秘钥也是安全的。因此攻击算法和秘钥是不现实的。那么,我们可以从协议的角度入手,看看有没有弱点。

先简单说一下RSA算法:

  1. 选择两个大素数 p 和 q,假设 p=3,q=11
  2. 计算 n = p × q = 3 × 11 = 33
  3. 计算 ∅(n) = (p – 1) × (q – 1) = 2 × 10 = 20
  4. 选择 e 且 1 < e < ∅(n) , e 与 n 互为素数. 假设 e = 7
  5. 计算 d,使 (d × e) % ∅(n) = 1. 假设 d = 3,且 d = (3 × 7) % 20 = 1,满足条件
  6. 公开 e, n => (7, 33)
  7. 保密 d => 3
  8. 加密公式 C = Me % n
  9. 解密公式 M = Cd % n

用上面的公式加密,假如消息是2,C = 27 % 33 = 29,密文就是29。解密的话就是M = 293 % 33 = 2。

回到刚才的软件破解问题上,软件产品中有e和n,如果能够分解n我们就能够构造d,也就知道了D公司的秘钥,由于分解n是一个数学难题,我们不知道最优解很难解出答案。我们采用另一种方法,破坏协议,首先我们自己选择2个大素数,构造另一个n,并分别求出对应的e和d。然后我们架设一个服务器,用来模仿D公司的验证服务器。

我们侵入D公司的软件,用我们自己的n和e替换D公司的n和e,这时软件D会用我们的公开秘钥加密用户信息以及序列号,这段信息是无法送给D公司验证的,因为D公司没有我们的保密秘钥,无法解密信息,因此这样还无法完成软件的验证。

下一步,我们使软件D将加密好的信息发送给我们刚才架设的模仿D公司的服务器,这台机器拥有我们的保密秘钥,它成功的解密信息,并直接构造一个验证通过的数据块,并用保密秘钥加密发送给D软件。D软件用我们的公开秘钥解密信息,验证一切正常,并将这段信息保存到计算机中。每次D软件启动时,重新检查是否存在验证通过信息块,并用我们设给它的公开秘钥解密,解密成功后通过验证,启动D软件。只要通过一次验证,D软件就无需再次与D公司服务器进行交互,因此完成了破解。

再次说明,算法,秘钥,协议是一个密码系统的组成部分,任何一个方面不安全,整个系统就是不安全的。当下,很多厂商对算法和秘钥很关注,在算法的选择与秘钥的长度上下足了功夫。但他们的系统并不像他们想象的那么安全,因为他们忽视了协议。

PS. 本文仅仅是基于理论方面的讨论,真正的软件破解过程比本文描述的要复杂的多,在real world中尝试发现n和e可能要困难的多。至于Patch程序代码,改变程序运行流程来达到破解目的与本文讨论的主题无关。

原文发布于微信公众号 - FreeBuf(freebuf)

原文发表时间:2017-07-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏钱曙光的专栏

一周极客热文:你工作了几年以及待遇大概多少?

本周被盖到400+楼的最最最热门文章是《大家聊聊待遇:工作几年,待遇大概多少??》。由于回复的内容“炒鸡”多,小编也无法很好的整理并得出高大上的结论,我想大家还...

21410
来自专栏Java学习网

编程能力七段论

编程能力七段论 前言   程序员的编程技能随着经验的积累,会逐步提高。我认为编程能力可以分为一些层次。   下面通过两个维度展开编程能力层次模型的讨论。   一...

3265
来自专栏佳爷的后花媛

翻译--黑客解剖

原文地址:戳这里 译文如下:第一次翻译,如有不当请指出,多谢。 这里说下hacker和cracker的区别啊。“Hacker”们建设,而“cracker”们...

1263
来自专栏精讲JAVA

程序员们,曾经是否有个bug让你开始怀疑人生

相信程序员们都有一个共同的女朋友。这个女朋友总是阴魂不散,时不时还不忘调戏下男朋友程序员,而且你依然对她欲罢不能、想入非非。

1022
来自专栏java达人

通过人工智能编写自修改/自完善的程序

作者:Kory Becker 译者: Mr派 来源:http://www.primaryobjects.com/2013/01/27/using-artific...

2188
来自专栏非著名程序员

如何处理前任程序员留下的代码

作为软件工程师不可避免会遇到的一个场景是:我们在改变或添加一个功能到不是我们创建的、我们不熟悉的、与我们负责的系统部分无关的代码中时,会遇到麻烦。虽然这可能会是...

842
来自专栏牛客网

百度智能云提前批面经

【每日一语】人类的努力应该是没有边界的,我们千差万别,不管生活看上去有多糟糕,总有你能够做的事情,并且能够成功。有生命的地方,就有希望。——《万物理论》

1834
来自专栏上善若水

007-golang-GO 编程高手的五个阶段

第一个阶段(菜鸟): 刚刚学习了这门语言。 已经通过一些教程或者培训班了解基本的语法,可以写短的代码片段。

2393
来自专栏FreeBuf

解密Myspace密码的姿势

*本文原创作者:泰格实验室,本文属FreeBuf原创奖励计划,未经许可禁止转载 一、背景 MySpace成立于2003年9月,作为比FTI(Facebook、...

24910
来自专栏C/C++基础

腾讯2016春季校园实习招聘技术岗复试(二面)问题汇总(CC++后台)

2016.4.12日下午在广州东圃参加了腾讯安全技术面的二面。一面是两天前下午4点多结束,晚上大概十点多接到复试(二面技术面)的通知。晚上回来就开始整体一面的问...

1182

扫码关注云+社区

领取腾讯云代金券