首页
社区
课程
招聘
[讨论]XOR加密算法的一个重要伪命题
2009-10-30 10:27 14968

[讨论]XOR加密算法的一个重要伪命题

2009-10-30 10:27
14968
常规的XOR就是每个字节直接XOR密钥,
但是也存在很多变形的XOR加密方法,比如
  XOR与字符串长度有关
  XOR与位置有关
  XOR每个字节都与上一个字节有关
  XOR密码取自随机种子
  XOR密码取自固定字符串密码-密码的每个字节逐个参与XOR

那么,变形那么多,反推的方法是否唯一呢?
也就是说:XOR是否有天生的漏洞可以支持用单一方法反推,不管加密时候的变形。

  从原理上说,是否有通用的方法直接BRUTAL FORCE反推XOR密码?

[伪命题]:
  XOR算法存在漏洞,无论加密的时候采取何种纯XOR变形,都可以采用通用的XOR测试方法反推XOR密钥。

------------------------------

  我非常希望这个伪命题完全成立,那样的话:我们可以直接用暴力反推XOR密码,方式可以是跑数字,或者是跑字典。这样可以彻底解决XOR对字符串的加密。

  我的数学非常差,但是又对XOR密码感兴趣。希望各位数学意识好的帮助推定这个命题。

  如果这个伪命题为真,那么我们最优化的反推方法会是怎样的?
  我现在使用的暴力破解是跑整数反推XOR密钥,但是有的不灵。

[培训]科锐软件逆向50期预科班报名即将截止,速来!!! 50期正式班报名火爆招生中!!!

收藏
免费 0
打赏
分享
最新回复 (10)
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-30 10:46
2
0
看了LZ 的敘述,我想LZ 誤解了一些內容。
XOR与字符串长度有关
XOR与位置有关
XOR每个字节都与上一个字节有关
XOR密码取自随机种子
XOR密码取自固定字符串密码-密码的每个字节逐个参与XOR

以上這些,是應用 XOR 的方法,這個 method 只是借用了XOR 的特性,你要先瞭解 這個 method ,才有辦法去反這個 method,或是說~去解這個 method,或 crack 這個 method。
本身不是 XOR 有問題。
雪    币: 271
活跃值: (90)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
qwert123 1 2009-10-30 10:54
3
0
谢谢rockinuk的回复。

如果是这样,那就是说:不存在XOR本身的漏洞,只能针对每种方法去提供对应的反推?

这在直接跟踪程序的时候会比较容易,但是,现实里,我们真的会遇到知道一部分密文及其对应的明文,但是METHOD我们无从知晓??这样我们该如何逆向呢?

比如:
  我可以知道一组正确无误的明文/密文,简单分析是通过XOR异或加密。
  如果XOR加密本身没有漏洞,那我只能尽量取得更多的明文/密文样本,以便取得他使用的METHOD。
  
  呵呵,不过这样真的很累。关键有时候明文/密文样本不足,而且又只面对这些样本,没有程序可供跟踪。
雪    币: 271
活跃值: (90)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
qwert123 1 2009-10-30 11:04
4
0
其实,对于XOR字符串解密我的核心想法就是想取巧。

如果假定在知道一些明文/密文样本量的前提下,我希望有种针对XOR特性的通用反推方法。

如果XOR密钥只能针对特定的METHOD来反推,那有没有哪种方法可以帮助分析或反推出这种METHOD呢?

看了一些资料和源程序,有的程序为了防止暴力反推密码,增加了异或的次数;而一些使用BRUTAL FORCE的程序,测试了一下,似乎不具有通用性 - 也就是无法针对各种变形。

如果明文/密文样本量充足,我可以建立字典来实现BRUTAL FORCE,但是,有时候难就难在样本量不充足。

所以,我很想知道XOR加密是否存在数学上的漏洞 - 不管其加密的METHOD,都可以直捣黄龙,哈,异想天开。
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-30 13:23
5
0
是的。

For example:
假設 C 為密文(ciphertext), A 為 明文(plaintext), B 為 key(secret key).
若 C= A⊕B, 且已知 C , 則要求得 secret key 就是計算 B=A⊕C, 再將計算出來的B 去驗證 B⊕C= A?
若是,那就正確;若不是,就是計算有問題。
以上只是單一的一個例子。
在程序中,很多都是 time sequency 的 status,要追蹤那種 serials,就要 step by step 的追。在追的過程中,去重建它的算法(Reconstructure algorightm)。
在crackme 的過程中,去推出 key genarator 是怎麼設計的,和上面講的,有著異曲同工之妙。



1)
這個反 method,就是尋找 plaintext 及 cipher 之間的彼此關係,你找出之間的關聯性(relationship),就能掌握破解的關鍵。
這點是偏 practical 多,theoretical 的少。
2) 還有另一個方法,就是找出這個算法的漏洞,或是 mathematical model 的缺陷。
這點可以完全是偏重 teoretical 面,或許也可以有 practical。
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-30 20:27
6
0
An NP decision procedure for protocol insecurity with XOR.pdf (361.9 KB)
這個很理論,難度很高,法國或是德國人寫的內容。

Obfuscation of The Standard XOR Encryption Algorithm.pdf (118.4 KB)
這個有理論也很實務,qwert123  大大參考看看。

Note on the integer geometry of bitwise XOR.pdf (228.1 KB)
這個也是理論與實務參半,可是內容還是理論表達的多一點。

Cryptanalysis of two chaotic encryption schemes based on circular bit shift and XOR operations.rar
這個論文,qwert123 大大應該會喜歡,到底它市理論還是實作,看看就會明瞭。
上传的附件:
雪    币: 129
活跃值: (1095)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
HotPower 2009-10-31 21:55
7
0
XOR是密码学中不可或缺的基本运算符,它最大的特点是2次还原。
传统的流密码就是用随机密钥流与明文XOR得到密文流,即一次一密无法破解。
公开密钥密码体系的起源也是来自XOR即“挂锁问题”。它是一个很有趣的问题:
设双方为AB,C为窃密方,明文为M,则2次可完成明文的安全传递。
1. A方发送A XOR M给B方,B和C都无法破解A XOR M,因为他们都没有密钥A。即A方“挂锁”。
2.B方反向发送B XOR A XOR M给A方,A方无密钥B,C方更没有密钥A和B。即B方“挂锁”。
3.A方收到B XOR A XOR M后,再用A进行XOR,即A XOR B XOR A XOR M=B XOR M.即A方“解锁”。
4.A发送B XOR M给B方,C方还是无密钥B.B收到B XOR M后,再用B进行XOR,即B方“解锁”。
最终得到B XOR B XOR M=M.即双方2次“挂锁”和“解锁”,使明文安全地从A传递给B,C一直无法破解。

“挂锁”问题的运算符与次序无关,它是A加密,B加密,A解密,B解密。而一般为A加密,B加密,B解密,A解密的次序。
所以很难找到,故公开密钥密码体系要比传统密码体系创建难度大不知多少倍。

总之,XOR运算最符合计算器处理,但它是线性的算法,很容易破解。

雪    币: 264
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
k4b 2011-6-6 21:24
8
0
hotpower说的“挂锁问题”好像一点不保密啊.大家看:
1. A方发送A XOR M给B方,B和C都无法破解A XOR M,因为他们都没有密钥A。即A方“挂锁”。
2.B方反向发送B XOR A XOR M给A方,A方无密钥B,C方更没有密钥A和B。即B方“挂锁”。
注意:这时的c方也有A XOR M .他也可以(B XOR A XOR M) XOR (A XOR M) = B.得到密钥B.
3.A方收到B XOR A XOR M后,再用A进行XOR,即A XOR B XOR A XOR M=B XOR M.即A方“解锁”。//这里原文写错了吧,应该是:即A  XOR M XOR B XOR A XOR M=B.即A方“解锁”。对吧?
4.A发送B XOR M给B方,C方还是无密钥B.B收到B XOR M后,再用B进行XOR,即B方“解锁”。
注意:这时C方也可以(B XOR M) XOR B =M,得到明文.
这保什么密啊.
雪    币: 49
活跃值: (11)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
yajiedesig 2011-8-7 17:19
9
0
回楼上,当然不保密啦,这只是个演示。演示“挂锁”这这种思想而已,下面说了可靠“挂锁”算法是很难找到的。到现在可用的也就RSA,ECC。
雪    币: 165
活跃值: (387)
能力值: ( LV13,RANK:357 )
在线值:
发帖
回帖
粉丝
瞧红尘 2 2011-8-15 09:00
10
0
位移、或、非、异或、同或、加减乘除,单一摆出来都像捏死一只蚂蚁一样简单。
    他们都是一对一的绝对运算,线性相关,且能直接反向计算。
   
    真正的就是组合起来,计算值多对一这样就无法简单逆向了。

我们假设两个简单的函数   y=f(x)=  x mod 11 ,  f2(x)= x mod 3
      f(35)=2
      他的逆向  f-1(2)  无法计算得到35,它是多对一,没有逆函数的。
满足条件的结果是很多2,13,25……
     f2(35)= 35 mod 3 = 2
       f2-(2)=  2、5、8……
       这类条件组合起来就 g(x)=f(x)+f2(x)=(x mod 11) + (x mod 3)
       求g-(x),    g-(4)要得到结果,
       这样的顺函数计算结果简单,逆向缺很不方便,当然这个并不难得到结果,但多次这类循环,

       最麻烦的不是这种,而是又把前面的结果在计算一次得到 xf(x),使得逆向时候有像处理超越方程一样,很不爽.

      一个这样的方式简单,但如果多层这一类无法简单逆向要逆向也需要不少尝试(部分暴力).
雪    币: 62
活跃值: (27)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
publickey 2011-8-15 18:21
11
0
XOR本质是多项式加法
游客
登录 | 注册 方可回帖
返回