闪星花密v2:对花密的试改进

花密是我介绍过的一款可记忆的独立密码解决方案。不同于随机生成密码然后存储起来管理的方案,花密不需要用户储存管理,也能为每个账户提供高强度的独立密码

当初介绍花密的时候,我还是个初中生,只觉得花密好厉害,但没有查阅其算法的能力。如今,我已学过一些算法,也算是懂得一点密码学的知识。在建立自己的花密镜像后,觉得花密还有提升空间。于是斗胆试着改进一下。

花密算法简介

原版花密算法可以用 JavaScript 这样表示:

    var str = '01279abe' //sunlovesnow1990090127xykab

    var md5one = md5(password, key);
    var md5two = md5(md5one, 'snow');
    var md5three = md5(md5one, 'kise');
    
    var rule = md5three.split('');
    var source = md5two.split('');
    for (var i=0; i<=31; i++) { 
        if (isNaN(source[i])) {
            if (str.search(rule[i]) !== -1) {
                source[i] = source[i].toUpperCase();
            }
        }
    }
    var code32 = source.join('');
    if (isNaN(source[0])) {
        var code16 = code32.slice(0, 16);
    }else{
        var code16 = 'K' + code32.slice(1, 16);
    }

    //code16 is the result

代码量其实没多少,也很简单。它的思路是,根据用户输入的记忆密码(password)和区分代号(key)生成散列值(哈希值或杂凑值,取决于你怎么翻译 hash value) md5one,再对得到的散列值 md5one 散列得到不同值的 md5two 和 md5three,md5two 是生成密码(code16)的主体,md5three 用来调整生成密码中字母的大小写。最后,保证生成密码第一位是字母;如果不是,替换为 K。

这里用到的核心算法是 HMAC-MD5。MD5 是常见的散列函数。如果你还不了解,散列函数根据一个字符串生成固定长度的值,这个过程是不可逆的,并且(一般来说)输入字符串的微小改变都会导致散列值的不同。而 HMAC 函数可以在散列的时候加上 key,在这里实际上相当于加盐。加盐是为了缓解彩虹表攻击。用 HMAC 加盐相比直接追加字符串更安全,比如能预防哈希长度拓展攻击。总之,进行这些操作后,攻击者几乎不可能从生成密码逆推出记忆密码和区分代号——至少理论上是这样的。

原版算法的瑕疵

我们知道,花密的生成密码是以字母开头的、包含大小写字母和数字的 16 位字符串(事实上花密原本也提供 32 位的生成密码,本文不讨论)。而通过算法进一步分析出,因为生成密码会是十六进制形式的哈希值,所以所谓的“大小写字母”其实只包含 AaBbCcDdEeFf,再往后的字母是不会出现的(除了首字符可能是 K)。于是乎,生成密码的可能组合数是 13*(22^15),约为 1.78e+21 或者 2^70.6。这样的强度其实算高了,但 26 个字母只会出现 6 个,显然不能说充分利用了所有空间。理论上,16 位含所有大小写字母和数字的组合数是 62^16,约为 4.77e+28 或 2^95.3,所以提升空间很大。换句话说,攻击者得知你的密码是 16 位大小写字母和数字的组合,会认为最多要尝试 2^95.3 次才算完,然而知道你是在用花密后,马上坍缩到 2^70.6 次,水平只是略接近于 12 位大小写字母和数字的密码

再次说明,这个强度已经算高了。只是,如果我们提升组合数,就能进一步增加暴力破解的难度,符合我们对 16 位密码的期望。同时,如果我们把增加的组合数用于表达散列值,也更能减少生成密码“碰撞”的几率。

另外一个比较明显的瑕疵是,花密使用的散列函数是 MD5。MD5 不安全。我由于水平原因,没法具体解释怎么不安全,大概是已知有手段更容易发生碰撞,但不确定这里是否受影响。不过,既然要进行改进,无妨使用更安全的散列函数。

改进版:闪星花密v2

首先,用 SHA-256 替代 MD5。SHA-256 是目前推荐的安全的散列算法,使用广泛,是 MD5 和 SHA-1 的主要替代者。

编码的部分,不再使用十六进制形式。容易想到一种常见的编码方式是 Base64,把 3 个 8 位字节转化为 4 个 6 位的字节,即一个字符(8 位)能表达 6 位信息,比起 bin2hex 式的只表达 4 位信息要高效许多。但 Base64 编码表的 64 个字符中,包含两个特殊符号,需要特别考虑。

一不做二不休,我索性决定不仅容纳两个特殊符号,还强制使每个生成密码包含特殊符号(说强制是因为 Base64 编码后的串并不一定出现那两个特殊字符)。我将强制引入的特殊符号放到第一位。于是生成密码由原版的以字母开头,变成以符号开头。我想,如今似乎已经见不到那种要求密码以字母开头的网站,却有更多的网站要求密码中包含特殊符号,因而这么做是合理的。事实上,这样做降低了密码强度,只有在别人不知晓你用闪星花密v2的情形下才能说更“安全”(根据现代密码学思想,我们不能依赖算法的保密性,因此最好不要依赖这一点),算是牺牲一点安全性来换取便利,在要求特殊字符的网站不必手动添加符号。特殊符号不放到末尾则是为了裁剪密码时不丢失特殊符号。

特殊符号理论上可以使用所有 ASCII 可打印符号。但我遇到的一些网站,只认其中一部分,否则仍然认为你不符合它们的强度要求。另外考虑到具体的场景如 Oracle Identity Manager、Microsoft Active Directory,有些符号不能出现。于是我决定,首字符限定从 !@#$% 中产生,因为网站应该都至少认这几个在键盘上连续的符号;其后的符号只允许出现 /\,代替 Base64 原本的 +/,这算是为了好看,只在很小的程度上能避免让人发现这是 Base64 编码(这个目的其实没意义,原因同上)。

原本还想使用诸如 PBKDF2 的方式,多次迭代使得彩虹表更难产生,想来意义不大,还增加耗电,作罢。

实现代码如下:

(注:由于所使用库不同,这里的 sha256.hmac 参数顺序为 sha256.hmac('key', 'Message to hash'),与上例中 md5 相反)

    var symbol = "!@#$%!@#$%!@#$%!@#$%!@#$%!@#$%";
    var head, hash, code16;
    hash = sha256.hmac(key, password);
    hash = sha256.hmac.update("ShansingPv2", hash).array();
    code16 = hash.slice(0, 12);
    code16 = btoa(String.fromCharCode.apply(null, code16));
    head = code16.charCodeAt(0);
    if (head >= 65 && head <= 90) head = symbol[head-65];
    else if (head >= 97 && head <= 122) head = symbol[head-97];
    else if (head >= 48 && head <= 57) head = symbol[head-47];  //-48+1, history issue
    else if (head === 43) head = symbol[3]; // + -> $
    else if (head === 47) head = symbol[4]; // / -> %
    code16 = head + code16.slice(1).replace(/\+/g, "/").replace(/\//g, "\\");

    //code16 is the result

基于 Base64 的特性,要生成 16 位(字符)的密码,就取 12 字节的值。这里的问题是,SHA-256 原本提供的散列值是 256 (二进制)位的,直接截断为 12*8=96 位是否安全。我找寻到的资料说是安全的,除了显然会增加碰撞概率外。(这是相对于 256 位来说的。而相对于原版最多 4*16=64 位,这里的碰撞可能更小。)

因为 Base64 已经能提供大写和小写字母,所以不需要另外决定生成密码中字母的大小写。

容易算出,闪星花密v2 生成密码可能的组合数是 5*(64^15),约 6.19e+27 或 2^92.3,非常接近我们对 16 位密码的期望。

简单比较

根据我的简单测试,闪星花密v2 与原版算法速度差不多。

列出特性对比如下:

比较项花密闪星花密v2
核心算法HMAC-MD5HMAC-SHA256
首字符类型字母AaBbCcDdEeFfK特殊符号!@#$%
允许的非首字符AaBbCcDdEeFf和所有数字所有大小写字母和数字,和符号/\
log2(组合数)*≈70.6≈92.3

*参考值:16位含大小写字母和数字的密码 ≈95.3。

在线试用:https://shansing.com/passwords/ (勾选“使用闪星花密v2算法”)

注意,尽管我想尽力设计出完善的算法,但成品的相关效果(包含安全性)没有保证。本人不是密码学专业人士,水平可能非常业余,请谨慎使用。当然,如果发现不妥,非常欢迎在下面留言指出。

2019-6-25 17:28 P.S.更新闪星花密v2代码,但未作实际变动。

若无特别说明,本文系原创,遵循 署名-非商业性使用 3.0 (CC BY-NC 3.0) 协议,转载文章请注明来自【闪星空间】,或链接上原文地址:http://shansing.com/read/477/

6 条评论

  1. 讲解很透彻,好评!算法流程简化到可以简单记忆的话,就算手头没有花密网站也可以快速写代码生成密码啦~

  2. 大大的帅哥 大大的帅哥

    很厉害,但是有的网站不大支持符号作为密码。我觉得每次都输入一次密码和标识符很麻烦,能否让第一个框就储存密码,第二个框是自己设置的下拉列表,每次不用输密码在下拉列表选一个网站就生成密码,点击复制 很爽很爽的

    1. 感谢支持。如果网站不支持含符号的密码,我通常认为它是落伍的,会使用原版花密算法,这样生成的最终密码就没有符号了。

  3. 大大的帅哥 大大的帅哥

    能够在第一版基础上增加其他26个大小写字母和其他算法已经很安全了,大神,能不能储存标识符作为列表,初始密码也储存就更好,适合我这种懒人。

    1. 之后会考虑网页版增加本地存储功能,存储记忆密码和设置项。区分代号可能不会储存,因为通常来说不会很长,而项却很多,因而允许下拉框选择提升的便利性也不大。

  4. 大大的帅哥 大大的帅哥

    我用excel的宏做了一个md5的密码板,输入一个密码 所有网站的密码都出来了,还可以指定密码位数,嘻嘻,但没你的算法安全

发表评论»

NO SPAMS! 不要发垃圾评论哦!

表情