维坦

之前的一篇文章提到过一种逆向思维求解MD5的方法.

后来发现真的有人这么做了, 其中数据量最大的网站标称自己拥有4T的数据量, 可以解8位以下的数字和字母组合.

即然是之前自己有过的想法, 那就拿F#来具体实现一下吧:

 
#light
 
namespace ViTarn
module MD5
 
open System
open System.Data
open System.Diagnostics
open System.IO
open System.Security.Cryptography
open System.Text
 
// sqlite.phxsoftware.com
#r "System.Data.SQLite.DLL"
open System.Data.SQLite
 
// 数据库名
let dbFile = "db.sqlite"
// 连接字符串
let connString =
    let csb = SQLiteConnectionStringBuilder ()
    csb.DataSource <- dbFile
    csb.ConnectionString
// 秒表
let watch = new Stopwatch ()
watch.Start()
 
// 为调试方便 输出对象并换行
let debug x =
    x |> print_any
    Console.WriteLine ()
 
// 从' '到'~'共95个常用于密码的字符 可以当成95进制看待
let n2cl n =
    let rec prase n l =
        let d = n % 95
        let c = d + 32 |> char
        let d = n - d
        if d > 95 then
            prase (d / 95) (c :: l)
        else
            c :: l |> List.to_array
    prase n []
 
// MD5加密字符串
let md5 (str : string) =
    use md5Hasher = MD5.Create ()
    str
    |> Encoding.Default.GetBytes
    |> md5Hasher.ComputeHash
    |> Seq.map (fun x ->
        x.ToString "x2")
    |> Seq.fold (fun x y -> x + y) ""
 
// 创建数据库
if dbFile |> File.Exists |> not then
    dbFile |> SQLiteConnection.CreateFile
    use conn = new SQLiteConnection (connString)
    let sql = "PRAGMA auto_vacuum = 1; " +
              "PRAGMA encoding = 'UTF-8'; " +
              "PRAGMA page_size = 4096; " +
              "PRAGMA synchronous = OFF; " +
              "CREATE TABLE md5 (p VARCHAR(42)  NOT NULL  COLLATE NOCASE, s VARCHAR(9)  NOT NULL  COLLATE NOCASE);"
    use cmd = new SQLiteCommand (sql, conn)
    conn.Open ()
    cmd.ExecuteNonQuery () |> ignore
    conn.Close ()
 
let main _ =
    let sql = "INSERT INTO md5 " +
              "VALUES(?, ?); "
    use conn = new SQLiteConnection (connString)
    use cmd = new SQLiteCommand(sql, conn)
    cmd.Parameters.AddRange [|new SQLiteParameter(); new SQLiteParameter()|]
    conn.Open ()
    use tr = conn.BeginTransaction ()
    cmd.Transaction <- tr
    for i = 0 to 857374 do
        let s = new String (n2cl i)
        let p = md5 s
        cmd.Parameters.[0].Value <- p
        cmd.Parameters.[1].Value <- s
        cmd.ExecuteNonQuery () |> ignore
        if i % 10000 = 0 then
            i |> debug
    tr.Commit()
    conn.Close ()
 
main ()
watch.Elapsed |> debug
Console.ReadKey()
 

为什么是857374?
95 * 95 * 95 - 1 = 857374

模拟的95进制, 是从"空格"(' ')到波浪线('~')的, 用ASCII表示就是32到126.
所在0 to 857374代表' '到'~~~'

在我的电脑上耗时00:01:08
CPU: AMD3000+
RAM: 1G
以DEBUG模式运行
最终产生的数据库约36M+

一些常见的不可逆算法(例如MD5), 采用对明文进行不可逆运算, 生成密文并保存.
验证时, 对用户输入的密文进行相同的加密运算, 将生成的密文与之前保存的密文进比较, 如果相同则代表密文正确.

想要进行破解, 唯一的办法就是穷举法. 根据密文的长度和可能包含的字符, 生成字典, 假设字典中的某一个字符串为明文, 然后对所有的字符串转化成密文, 与之前保存的密文进行比较, 如果正确, 就猜中了明文.

自从出现这种穷举法破解之后, CPU就开始沦落为苦力, 经常去做这些琐然无味的工作.
试想一下, 将世界上所有的这种破解尝试加起来, 这其中有99%是重复性的无用功. 而且我们一直将这种破解方式的成功率寄希望于计算机性能的不断提高和穷举算法的优化, 有没有其他的路可走呢?

这里有一个新的思路可供选择, 那就是把之前所做的99%的无用功收集起来并合并在一起, 这样一来, 我们就得到了MD5算法明文和密文的对应表, 不需要全部, 16位以内的字母数字符号组合, 就已经足够了.

当然这只是一个想法, 事实上"过去"是无法重现的, 不过或许可以开发出一款在线WEB版的破解工具, 用户提交密文, 如果密文可以在服务器中搜索到, 则直接返回结果, 如果找不到, 则要求用户选择明文的可能组合, 由客户端来生成字典, 之后检索字典中的明文, 去掉服务器数据库中已经存在的明文, 由客户端来运算剩下的明文, 并将增量运算结果提交给服务器, 这样一来在提供服务的同时, 也在搜集和扩充明文与密文的对应表, 久而久之, 最终实现一个类似密码搜索引擎的在线查询网站.

看到这里, 或许你会对这种方法的可行性有所怀疑, 的确, 就目前的存储技术而言, 数据库的存放还是个问题, 但是我相信, 以现在计算机性能的发展速度, 实现这一功能是迟早的事.