首页
社区
课程
招聘
探讨ECC加密被破译的可能性---看雪学院2006金秋读书季[讨论]
发表于: 2006-11-6 13:07 23317

探讨ECC加密被破译的可能性---看雪学院2006金秋读书季[讨论]

2006-11-6 13:07
23317

探讨ECC加密被破译的可能性

   响应kanxue老大的号召,金秋读书节发一篇探讨ECC加密软件被破译的可能性,不针对具体软件。错误难免,敬请指出。本文旨在抛石头砸大牛。
   如果不了解什么是ECC(椭圆加密算法),建议先看看zmworm大牛的《ECC加密算法入门介绍》,非常经典的文章(看雪精华6)。
   这里直接引用zmworm文章的内容,针对那些有ECC概念的朋友。

一、制作注册机(也可称为签名过程)

   1、选择一条椭圆曲线Ep(a,b),和基点G;
   2、选择私有密钥k(k<n,n为G的阶),利用基点G计算公开密钥K=kG;
   3、产生一个随机整数r(r<n),计算点R=rG;
   4、将用户名和点R的坐标值x,y作为参数,计算SHA(Secure Hash Algorithm 安全散列算法,类似于MD5)值,即Hash=SHA(username,x,y);
   5、计算sn≡r - Hash * k (mod n)
   6、将sn和Hash作为 用户名username的序列号

软件验证过程如下:(软件中存有椭圆曲线Ep(a,b),和基点G,公开密钥K)

二、软件验证过程如下:(软件中存有椭圆曲线Ep(a,b),和基点G,公开密钥K)

   1、从用户输入的序列号中,提取sn以及Hash;
   2、计算点R≡sn*G+Hash*K ( mod p ),如果sn、Hash正确,其值等于软件作者签名过程中点R(x,y)的坐标,因为
      sn≡r-Hash*k (mod n)
      所以
       sn*G + Hash*K
      =(r-Hash*k)*G+Hash*K
      =rG-Hash*kG+Hash*K
      =rG- Hash*K+ Hash*K
      =rG=R ;
   3、将用户名和点R的坐标值x,y作为参数,计算H=SHA(username,x,y);
   4、如果H=Hash 则注册成功。如果H≠Hash ,则注册失败(为什么?提示注意点R与Hash的关联性)。
简单对比一下两个过程:
   作者签名用到了:椭圆曲线Ep(a,b),基点G,私有密钥k,及随机数r。
   软件验证用到了:椭圆曲线Ep(a,b),基点G,公开密钥K。
   Cracker要想制作注册机,只能通过软件中的Ep(a,b),点G,公开密钥K ,并利用K=kG这个关系获得k后,才可以。而求k是很困难的。

三、探讨破译ECC的难度
  1、从上面的分析来看,要想制作出ECC的注册机,好像需要知道私钥才有可能,这需要穷举。如果是私钥数据长度很大或者是数据对,这基本上是不可能的。
  2、sn和Hash,H等都是关联的,可以说是牵一发而动全身。
  3、Hash经过复杂运算后,还要使计算的最后结果等于自身,即H=Hash,否则将验证失败。
  4、带ECC程序的本身只有公钥,而没有私钥。私钥只在注册机中存在。
  5、开始的感觉是,带ECC的程序好像有一种东西游离于程序之外,又在控制着程序验证的运行。知道它,却又抓不住他,这就是私钥。破译一个字---》难!
    因此,目前常用的方法是爆破和补丁。

四、探讨破译ECC的可能性
    细想一下,这有点奇怪。程序在我的机子上运行,代码我的机子上跑,而他的验证运行却受程序之外的某种规律(公钥-私钥关系)的控制。很是不爽,我本地运行凭什么受外面的某种关系制约啊,
哪里有这种逻辑呢?典型的霸王条款!心里实在哽不下这口气。哈哈!
    发挥逆向思维想想,既然验证成功的程序能在我的机子上运行,说明他肯定符合某种规律,而这种规律存在于本机的程序中,并不一定是程序之外的那种约束关系!如果这种假设成立的话,那么就说明有很多种规律可以适合于验证关系!
  1、分析注册机:
   K=k*G
   R=rG
   Hash=F(user,R)=F(user,r,G)=SHA(user,x,y)
   sn=r-Hash*k

   sn,Hash,user三者关联,       即:    sn=r-Hash*k=r-k*SHA(user,x,y)

  2、分析程序验证:
   sn,Hash
   R=sn*G+Hash*K
   H=F(user,R)=SHA(user,x,y)
   验证H是否等于Hash

  3、验证程序的关联:

      H=F(user,R))=F(user,sn,G,Hash,K)=SHA(user,x,y)

      如果确定user,确定G,确定K(这些都可以从软件中逆向出来的)
      既然验证要求H=Hash,那么我们就

           令H=Hash,则有H=F(user,sn,G,H,K)=F(...,sn,...,H)
           即  H=F(...,sn,...,H)

      这其中,只有H和sn是变化的,给定sn,就可以给出相应的H;其它量都是常量。

   4、关键的问题:搞清楚F函数的关系,逆向出程序中已有的信息,用符合条件的user,任意sn(只要符合长度等基本限制),理论上就可以计算出符合这个关系的Hash。
      这样的话,就和私钥没有关系了。也就是用某个关系间接代替了公私钥的关系。

   5、ECC是穷举,也就是说可能举出很多符合条件的;实际上穷举也就是没有固定的对应值,因此,这即是其最大的漏洞。

      因此,有无穷对满足H=F(...,sn,...,H)关系的密码对。

   6、进一步探讨:
      对于方程H=F(...,sn,...,H),有些时候并不一定有解析解。
      如果有解析解的情况,就是 H=HASH=f(sn...),其它量为常值看待,很容易给出。这样的注册机,其实是要求输入user和sn两个量来确定HASH,而不是通常的一个量。
      
      如果方程没有解析解的情况,好像也要穷举?比如 X=a+b**(X+c),这里X为变量,a,b,c为常量。 例如
       HASH=user+2**(a*sn+b*HASH)         (1)
    等通常是没有解析解的
      如果我们要相信私钥起作用的话,那肯定没有办法了。穷举也许是最笨的办法,我们为什么不能构建其它的关系来满足方程达到可以产生解析解呢?只要这些构建的关系能够通过程序的诸如数据长度等基本的验证机制就行了。上面的方程可以这样构建额外的关系就可以简化并构成简单的联立方程组,而构成这样的关系方程实在太多,比如:
        令a*sn+b*Hash=0   方程(1)就变为
          HASH=user+1                      (2)
       联立求解上面方程,够简单的吧。
    如果有某种限制条件,我们同样可以令
         a*sn+b*Hash=1,2..........,既然穷举,我们举几个特例就可以饶过这些基本的判断了。
   7、ECC验证
      真正的ECC加密比上面的复杂,但基本原理一样。只不过他采用了椭圆曲线映射验证机制,过程更复杂,也需要更多的构建搭桥技术。
五、结论
    ECC能否破解?答案是:能!
    只是如果程序验证函数的复杂程度如果够难的话,那就看你的逆向功底和数据函数构建能力了。理论上,只要另外构建一个或多个关系函数,这样就可以代替私钥了,凡是穷举好像都可以这样做,而且做出的注册机应该有无穷多个。
    有个ECC的模型(穷举算法,不是真正的ECC),看看写的一个非常简单的CRACKME就会发现这一点,laoqian分析了http://bbs.pediy.com/showthread.php?threadid=34323
   文章杂乱写了些,我是扔的砖头,写错了的话,你们就不要扔砖头了砸我了哈,欢迎讨论。
感谢:
    kanxue
    zmworm
    laoqian
    萝卜
    小剑
    看雪论坛上的所有朋友。


[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入!

收藏
免费 7
支持
分享
最新回复 (24)
雪    币: 47147
活跃值: (20410)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
2
最初由 newsearch 发布
探讨ECC加密被破译的可能性

响应kanxue老大的号召,金秋读书节发一篇探讨ECC加密软件被破译的可能性,不针对具体软件。错误难免,敬请指出。本文旨在抛石头砸大牛。
........


呵~谢谢支持!
2006-11-6 13:13
0
雪    币: 332
活跃值: (479)
能力值: ( LV9,RANK:330 )
在线值:
发帖
回帖
粉丝
3
有思想,但是还要实践检验,唉。看得头都疼了!
2006-11-6 13:36
0
雪    币: 260
活跃值: (102)
能力值: ( LV9,RANK:170 )
在线值:
发帖
回帖
粉丝
4
非常值得学习!支持!
2006-11-6 13:39
0
雪    币: 212
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
希望能提供ECC算法的源代码,谢谢
2006-11-6 14:19
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
6
写的非常好,学习中
2006-11-6 20:51
0
雪    币: 671
活跃值: (723)
能力值: ( LV9,RANK:1060 )
在线值:
发帖
回帖
粉丝
7
这个要慢慢看!
2006-11-6 21:02
0
雪    币: 405
活跃值: (10)
能力值: ( LV9,RANK:1130 )
在线值:
发帖
回帖
粉丝
8
学习下。特别喜欢下面这句

    ECC能否破解?答案是:能!
2006-11-7 10:55
0
雪    币: 207
活跃值: (13)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
9
cracker就是要变不可能为可能!
2006-11-7 14:22
0
雪    币: 721
活跃值: (350)
能力值: ( LV9,RANK:1250 )
在线值:
发帖
回帖
粉丝
10
思路新颖。
newsearch兄弟,从这一句:
    H=F(...,sn,...,H)
看,好像ECDSA的安全几乎等价于散列函数SHA嵌入自身摘要后还要等于自身,这样,穷举可能会找到一些。按照与王晓云教授寻找SHA碰撞的方法类似,估计找到所需时间不会很长。
2006-11-10 10:54
0
雪    币: 257
活跃值: (369)
能力值: ( LV12,RANK:370 )
在线值:
发帖
回帖
粉丝
11
最初由 happytown 发布
思路新颖。
newsearch兄弟,从这一句:
H=F(...,sn,...,H)
看,好像ECDSA的安全几乎等价于散列函数SHA嵌入自身摘要后还要等于自身,这样,穷举可能会找到一些。按照与王晓云教授寻找SHA碰撞的方法类似,估计找到所需时间不会很长。


同意的说。
其实公私钥对的情况,如果要逆推去追私钥,几乎是不可能的事情,除非特别简单或者运气特别好,呵呵。中间构建函数,即成了正向计算,这个过程就容易得多。举一些特例,即可。看了你的CRACKME29,没有详细分析,用了穷举?
2006-11-10 12:07
0
雪    币: 721
活跃值: (350)
能力值: ( LV9,RANK:1250 )
在线值:
发帖
回帖
粉丝
12
最初由 newsearch 发布
...看了你的CRACKME29,没有详细分析,用了穷举?

有人穷举出来了吗?
2006-11-10 13:13
0
雪    币: 257
活跃值: (369)
能力值: ( LV12,RANK:370 )
在线值:
发帖
回帖
粉丝
13
不用穷举算法,可以作注册机的
2006-11-10 13:34
0
雪    币: 721
活跃值: (350)
能力值: ( LV9,RANK:1250 )
在线值:
发帖
回帖
粉丝
14
最初由 newsearch 发布
不用穷举算法,可以作注册机的

我以为你采用了穷举的方法。
你做出了注册机?
2006-11-10 14:21
0
雪    币: 99
活跃值: (2393)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
15
指出两点错误:
1、算私钥不需要穷举
2、基于DLP(ECDLP)的签名算法不但私钥很重要,而且还有一个重要的随机数。上文分析就漏了这个重要的随机数,也就是r。如果这个随机数是固定的,直接就可以算出私钥。
2006-11-14 21:20
0
雪    币: 332
活跃值: (479)
能力值: ( LV9,RANK:330 )
在线值:
发帖
回帖
粉丝
16
我们知道Recca曾经利用随机数生成器的弱点破解了ASProtect的注册方案,....引自:
http://bbs.pediy.com/showthread.php?s=&threadid=35163

这个flexlm似乎也有随机数生成器!!!看看有弱点马。
2006-11-20 22:57
0
雪    币: 5340
活跃值: (598)
能力值: (RANK:170 )
在线值:
发帖
回帖
粉丝
17
仔细看了作者的论述,说一下自己的看法.
按作者的思路,进行推导:
假设 点R为原点,即
则 H=SHA(username,x,y) = SHA(username) 这样我们就可以求出常量H.
所以R≡sn*G+Hash*K ( mod p ) 可以转化为:
0 ≡ sn*G+H*K ( mod p )
令点 SN = - H*K,则
0 ≡ sn*G - SN ( mod p )
SN ≡ sn * G ( mod p )
这时要求SN,又变成 K=kG 的问题了-__-|| ,貌似楼主忽略了ECC曲线上除法的难度.

很久没关注ECC了,忘得差不多了,不对之处,还请大家指正
2006-11-21 08:26
0
雪    币: 257
活跃值: (369)
能力值: ( LV12,RANK:370 )
在线值:
发帖
回帖
粉丝
18
最初由 zmworm 发布
仔细看了作者的论述,说一下自己的看法.
按作者的思路,进行推导:
假设 点R为原点,即
则 H=SHA(username,x,y) = SHA(username) 这样我们就可以求出常量H.
所以R≡sn*G+Hash*K ( mod p ) 可以转化为:
........


非常高兴,引出了大牛!
zmworm兄,我的意思并不是靠特例就直接攻击ECC;如果是特例的话,同样避免不了K=kG这个关系。如果中间构建一些函数,构成方程组的关系,比如直接令H=Hash,如果需要则再构建一些关系,那么再取特例就有可能了。
2006-11-21 09:24
0
雪    币: 230
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
19
写的不错~~~

支持一下

我会继续关注你的帖子的~~~
2006-11-21 10:26
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
20
有创意,值得学习.
2006-11-21 11:07
0
雪    币: 44
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
fyd
21
全力支持!
2006-11-30 15:34
0
雪    币: 234
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
22
1.好像不是在破译ECC而是在制作注册机,注册机同时用到ECC和SHA,不是去寻找ECC的私钥而是去攻击SHA
2. "令a*sn+b*Hash=0   方程(1)就变为
          HASH=user+1                      (2)"

      sn*G+H*K =  R
      H = SHA(user,R)                user,R 外面一层是SHA,SHA是不可逆的 ,不能等价于某种简单的计算

     可以令R为常量,但是H还是解不出啊,什么样的SHA会这样容易解出呢

3.ECC现在还没有好的办法破解,可以利用ECC产生序列号别人很难写出注册机,但很难阻止合法用户爆破
2008-12-19 13:57
0
雪    币: 52
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
23
哦  看过  很强大··
2008-12-21 21:43
0
雪    币: 2
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
24
我要学算法是不是要先去学点什么基础啊,我一点都看不懂,我汇编都看完了
2009-10-15 13:14
0
雪    币: 11
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
25
听君一席话,胜读十年书!顶!:学习中!
2010-3-13 07:36
0
游客
登录 | 注册 方可回帖
返回
//