liqingcan
V2EX  ›  问与答

关于穷举一个字符串的 MD5 是他自己的想法

  •  
  •   liqingcan · Oct 4, 2016 · 6390 views
    This topic created in 3696 days ago, the information mentioned may be changed or developed.

    前几天看了站中的一个帖子传送门 简单的说就是一个文本文件中的内容是这个文件的 md5 ,有没有可能找出这个 md5 值,然后我好奇心就起来了,于是我想动手验证一下。 我一开始的想法是,创建一个文本文件,然后计算他的 md5 ,但是感觉频繁的创建文件好像有点伤硬盘,于是我就试验了一下,直接计算一个字符串的 md5 和将这个字符串放在文本文件中在计算 md5 是不是一样。如果一样的话我就不用频繁创建文件了,经过试验这个是可行的。 然后我就写了一小段 python 的脚本来进行验证。 代码:

    import hashlib
    import time
    
    if __name__=="__main__":
        i=0
        md5 = format("%f"%time.time())
        while(True):
            i = i+1
            m=hashlib.md5()
            m.update(md5.encode("utf8"))
            temp = m.hexdigest()
            print("%d\t%s md5-> %s"%(i,md5,temp))
            if(temp==md5):
                print("找到一个相同的了,回车继续")
                print(md5)
                input()
                md5 = temp+format("%f"%time.time())
            else:
                md5 = temp
    

    简单的说,就是先取当前时间作为初始字符串,然后计算 md5 接着将计算出来的 md5 再计算,一直循环到找到一样的,然后我就放到了一台闲置的腾讯云的主机上跑了十几个小时

    跑了有快 4 千万条数据了。 然后我现在就在想,我这个方法有没有可能进入死循环啊?

    Supplement 1  ·  Oct 4, 2016
    怎么改标题啊,发现打字打太快,标题都打错了。出现了一个是他自己的想法。。我想说的是,实验自己的想法
    50 replies  •  2016-10-07 21:41:24 +08:00
    jasontse
    jasontse
    Oct 4, 2016 via iPad
    1
    用十六进制数自增,补齐 32 位,跑一遍直到全 F ,这样就不会死循环了,不过还有大小写的可能性。😂
    skydiver
    skydiver
    Oct 4, 2016 via Android
    2
    找到一个循环也很有价值啊
    bkmi
    bkmi
    Oct 4, 2016 via Android
    3
    哥们,你好歹也多起几个线程啊
    bearqq
    bearqq
    Oct 4, 2016
    4
    md5 多少位?每位哪些可能性?
    弄一堆 for
    就可以完成史诗级的巨慢解
    可保证唯一。

    不要拿 python 做这种蠢事,那才真是拍脑袋写个程序一秒钟,运行起来跑死个人
    yangff
    yangff
    Oct 4, 2016
    5
    就算你这样跑出来了,得到的也是
    hex(x) == hex(md5(hex(x)))
    而不是
    x == md5(x)
    aploium
    aploium
    Oct 4, 2016
    6
    用 py 做这种事......简直 gg

    歪楼的 ps: 不输出 stdout 能快很多
    popok
    popok
    Oct 4, 2016
    7
    py 算这个效率太低了,再说你还要输出,那。。。。。
    liqingcan
    liqingcan
    OP
    Oct 4, 2016
    8
    @jasontse 我本来是这样想的,不过想想,好像写起来比较麻烦
    @skydiver 重点是,找到死循环我也不知道是哪一个。。。
    @bkmi 我觉得同一个脚本直接多次执行不就行了,不过我一个就沾满了腾讯云主机 100%cpu 感觉没有多开的必要
    @bearqq
    @aploium
    @popok 用 python 主要是写起来快,哈哈
    @yangff 为啥?hex 是什么东西?
    metowolf
    metowolf
    Oct 4, 2016
    9
    显然会有循环节的,只是不知道大还是小,如果找到 md5(x)==x 就比较有价值了
    binux
    binux
    Oct 4, 2016
    10
    @yangff
    hex(x) == hex(md5(hex(x)))
    不就是
    x` == hex(md5(x`))

    而 md5 大多数时候就是 hex(md5(())
    zhujinliang
    zhujinliang
    Oct 4, 2016 via iPhone
    11
    用 GPU 跑啊
    liqingcan
    liqingcan
    OP
    Oct 4, 2016
    12
    @metowolf 恩
    @binux 表示数学不好的看不懂你俩讲的是啥……
    @zhujinliang 不会搞。尴尬~
    sherlocktheplant
    sherlocktheplant
    Oct 4, 2016
    13
    @liqingcan md5(string) != md5(hex(string))
    sneezry
    sneezry
    Oct 4, 2016 via Android
    14
    要先证明函数收敛才能这么搞,楼主你其实在做牛顿迭代,这个有解是有前提条件的
    lance6816
    lance6816
    Oct 4, 2016
    15
    可以的,很强势
    大概到太阳变成红巨星那天就能算出来了
    nfroot
    nfroot
    Oct 4, 2016 via Android
    16
    先读源码吧 或许你就能猜到有木有这种可能存在
    liqingcan
    liqingcan
    OP
    Oct 5, 2016
    17
    @sneezry
    @lance6816
    @nfroot 额,好吧,其实我就是心血来潮想试试。
    @sherlocktheplant 我比较想知道 hex ()这个是什么?
    Trim21
    Trim21
    Oct 5, 2016
    18
    写了个穷举算法.........计算 1e6 个数字要 2s,穷举完要 6e36 年,多不多进程也没啥意义了...
    换了 pypy2 居然更慢了!变成了 5s
    liqingcan
    liqingcan
    OP
    Oct 5, 2016
    19
    @sherlocktheplant 好吧,懂了, 16 进制
    GoForce5500
    GoForce5500
    Oct 5, 2016
    20
    Java 不输出结果仅做 MD5 计算和计数的话,在 RMBP15 上开 8 核多线程跑满 CPU ,可以达到 1300 万次 MD5/秒。
    堆 GPU 的话还能快两个数量级。
    Trim21
    Trim21
    Oct 5, 2016
    21
    @GoForce5500 减少到了 17 年...
    loveyu
    loveyu
    Oct 5, 2016
    22
    来个全民计算的活动。先将要计算的字符串拆成一亿份,各种机器像挖矿一样计算就好了,说不定几天就有结果了
    dynos01
    dynos01
    Oct 5, 2016 via iPad
    23
    搞一大堆超算,利用上大量的计算资源,也许很快出结果
    可惜这种项目没什么实际用处吧。。。
    abelyao
    abelyao
    Oct 5, 2016
    24
    @loveyu 想起了 SETI@home 计划…… 我是不是暴露年龄了
    YvesX
    YvesX
    Oct 5, 2016 via iPhone
    25
    你都定义为“穷举”了,为什么要用这种奇怪的算法,还是说其实是想顺便找个循环节出来?
    要是真的穷尽了,你就知道了所有 md5()与 md5(md5())的一一映射……
    脑洞有趣,但有点烧算力啊……
    liqingcan
    liqingcan
    OP
    Oct 5, 2016 via Android
    26
    @YvesX 就是因为穷举数量太多了,所以用了这个,说不定踩到狗屎运就跳出来了………
    RqPS6rhmP3Nyn3Tm
    RqPS6rhmP3Nyn3Tm
    Oct 5, 2016 via iPhone
    27
    不要那 python 做,性能太烂了
    关于你的问题,是的。
    StarBrilliant
    StarBrilliant
    Oct 5, 2016❤️3
    28
    1 、存在 md5(x) == x 的概率是 63.21%,这是一个很大的概率
    2 、但是我们找不到这些 x ,因为对任意一个 x , md5(x) == x 的概率是 0.0000000000000000000000000000000000002939%
    3 、 MD5 的设计使你无法理论预测这样一个 x 值,所以你需要实际计算
    4 、如果计算一次 MD5 需要 1 ms 时间的话,你需要 10790283070806014188970529154.99 年才能算出来

    综上所述,研究这个问题没有意义。
    以及,搞计算机这一行,先学好数学,再买个游标卡尺来写 Python (误)。

    参考:
    http://crypto.stackexchange.com/a/19579
    http://stackoverflow.com/a/235788/2557927
    ryd994
    ryd994
    Oct 5, 2016 via Android
    29
    @GoForce5500 远远不够啊
    md5 有 2^128 个
    13M≈2^24
    要 2^104 秒啊………
    t0byxdd
    t0byxdd
    Oct 5, 2016 via Android
    30
    print 很慢的 不要这么频繁输出没意义的内容 最好别用 python 或者至少弄个多进程并行
    xuboying
    xuboying
    Oct 5, 2016 via iPhone
    32
    import numba
    waruqi
    waruqi
    Oct 5, 2016 via iPhone
    33
    拿 py 来跑也是醉了
    wy315700
    wy315700
    Oct 5, 2016
    34
    至少也得拿个显卡来穷举
    SlipStupig
    SlipStupig
    Oct 5, 2016
    35
    @t0byxdd 这种算数密集型好像多进程也没啥用,直接上 CUDA 或者 OpenGL ,速度不知道比 CPU 快多少
    ipwx
    ipwx
    Oct 5, 2016
    36
    @sneezry 牛顿迭代?。。。数学不好就不要乱用术语。
    sneezry
    sneezry
    Oct 5, 2016
    37
    @ipwx 那我虚心求教,这在数学上的专业术语应该叫什么呢
    ipwx
    ipwx
    Oct 5, 2016
    38
    @sneezry 没什么术语,只是在寻找不动点而已。

    而且就算 MD5(x)=x 存在不动点,也不一定能通过楼主的方法找到,因为毕竟如果 MD5 的自变量空间里面存在某个不与不动点相通的环,而楼主恰巧从这个环的某个元素出发开始迭代,那么永远都只能在这个环里面走,到达不了不动点。
    sneezry
    sneezry
    Oct 5, 2016
    39
    @ipwx 牛顿法是找 0 点的方法,同样用到了迭代,楼主的问题稍加变化就从 f(x)=x 转换为 F(x)=f(x)-x ,继而变成 0 点问题。牛顿法是用切线与 x 轴交点作为下次计算的输入值,楼主用的是函数值。那么我说这是一个特殊情况的牛顿逼近又有什么不妥呢?
    yangff
    yangff
    Oct 5, 2016
    40
    @sneezry 来写一下 md5'(x)=?吧
    yangff
    yangff
    Oct 5, 2016
    41
    @sneezry 另外,这玩意大概可以叫不动点迭代……
    当然你抠着脚趾头都知道这玩意不一定能收敛……
    sneezry
    sneezry
    Oct 5, 2016
    42
    @yangff 哈哈,这个说到点上了, md5 是离散函数。算我偷换概念,离散函数就谈不上牛顿逼近。学艺不精,惭愧
    twl007
    twl007
    Oct 6, 2016
    43
    我记得山大的王小云不就是做这个的么 = = 貌似叫 hash 碰撞?好像她的论文公开了吧?
    herozhang
    herozhang
    Oct 6, 2016
    44
    prefix 12:
    54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762

    suffix 12:
    df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78

    ref:https://plus.google.com/+ThomasEgense/posts/SRxXrTMdrFN
    herozhang
    herozhang
    Oct 6, 2016
    45
    可以先从 CRC 开始尝试,然后是 MD5 、 SHA 系列
    哈哈
    ipwx
    ipwx
    Oct 6, 2016
    46
    @twl007 @herozhang 你们再仔细读一遍楼主的帖子再说。
    ryd994
    ryd994
    Oct 6, 2016 via Android
    47
    @loveyu 不可能,看我 29 楼的
    大约是 10^23 年
    我今天用 C 和 OpenSSL 写了一下,单核大约 5-10M hash/s
    和上面的数据差不多
    也就是说,就算地球上人手一台电脑跑着,大概也可以考虑一下人类灭亡之类的事情了
    loveyu
    loveyu
    Oct 6, 2016
    48
    @ryd994 现在的确不大可能,不过以后的计算速度上来了也许就有希望了!
    sutra
    sutra
    Oct 6, 2016
    49
    直接查彩虹表吧。
    GoForce5500
    GoForce5500
    Oct 7, 2016
    50
    @ryd994 经过将近八千亿次运算已弃坑……
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Privacy   ·   Solana   ·   4301 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 85ms · UTC 07:28 · PVG 15:28 · LAX 23:28 · JFK 02:28
    ♥ Do have faith in what you're doing.