Vanity发生器 Profanity私钥破解漏洞

漏洞成因

Profanity 随机数不够随机。

• 有可能是种子有限(比如用时间戳做种子)
• 有可能是随机算法强度有问题。

    // Randomize private keys
    std::random_device rd; // 从 /dev/urandom 获取随机数 rd
    std::mt19937_64 eng(rd()); // 使用mt19937_64 扩充rd 到 256位
    std::uniform_int_distribution<cl_ulong> distr; // 该函数也没有随机性
    cl_ulong4 r;
    r.s[0] = distr(eng);
    r.s[1] = distr(eng);
    r.s[2] = distr(eng);
    r.s[3] = distr(eng);
    return r;

扩充步骤 和 分发步骤 均没有随机性。有随机性的步骤仅仅是 从 /dev/urandom中取随机数。

但该随机数长度为32bit 低于私钥的256bit。可以暴破rd 而非 pk，来缩短时间。

暴破难度 从 256bit 减小到 32bit。

通过上述过程得到 seed_pk。

Profanity 通过 $PubKey = kG = (SeedKey + Iterator)*G$ 来找好看的公钥。

Iterator 最多增200万次。

攻击者 已知 PubKey, 除了暴破32bit的SeedKey以外，还需要暴破Iterator。

暴破难度为 2e6 * 2^32 次

但通过对公式变形，$SeedKeyG = PubKey - IteratorG$

可以，先单独计算全部的SeedKey*G,并存入数据库。

接着，再计算2e6次找到对应的Iterator，并查表。

暴破难度 从 2e6 * 2^32 减小到 2e6 + 2^32

基础知识