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

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

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

一、制作注册机（也可称为签名过程） 

   1、选择一条椭圆曲线Ep(a,b)，和基点G； 
   2、选择私有密钥k（k   3、产生一个随机整数r（r   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分析了
   文章杂乱写了些，我是扔的砖头，写错了的话，你们就不要扔砖头了砸我了哈，欢迎讨论。
感谢：
    kanxue
    zmworm
    laoqian
    萝卜
    小剑
    看雪论坛上的所有朋友。