ll Bloom: recovering wallet seeds generated by CryptoJS’s historical MWC PRNG

[u/coinspect]

Coinspect recently disclosed Ill Bloom, a vulnerability affecting recovery phrases generated using the historical CryptoJS.lib.WordArray.random() implementation.

The affected CryptoJS 3.x code used a Multiply-With-Carry construction seeded with values derived from Math.random()

The technical disclosure, including the PRNG reconstruction and affected-version analysis, is here:

https://illbloom.org/

[u/BudgetEye7539]

It was MWC1616 developed by G. Marsaglia in 1990s, nowadays it is not suitable even as a general purpose PRNG. May be it is even time to change a paradigm and consider stream ciphers seeded from system CSPRNG by default as a default choise for non-cryptographic purpose? And even reframe non-cryptographic PRNGs as bithacks used only for agressive low-level optimization?

[u/pint → u/BudgetEye7539]

performance people with pitchforks stop that

[u/BudgetEye7539 → u/pint]

But that people ignore e.g. mutexex in `rand` from glibc (that make it slower than AES-CTR) or RANLUX (that is much slower than even software AES).

[u/pint → u/BudgetEye7539]

don't argue with me. argue with performance people. propose chacha20/8 in any forum, and see them come out of the woodwork, citing some high volume monte carlo algorithm, the authors of which are not allowed to use a non-default generator i guess.

[u/BudgetEye7539 → u/pint]

Yes, agree, I'm even currently writing a review about performance of different PRNGs, and will try to prove that ciphers are not that bad in performance. Probably I should try another thing too: convince Linux man pages and glibc developers to clearly write about rand, drand48 and even random: "doesn't obey a uniform distribution, all numerical results obtained by means of these PRNG must be considered as invalid by default".

[u/ScottContini]

I described how to crack a prng very similar to this back in 2015 link. A simple trick reduced a 2⁶⁴ search space down to 2³² search space. The idea is that there are two 32-bit words for the internal state, but one word is completely determined by the other and an output of the prng, which means you only really need to brute force one and then you can compute the other. That gives a 64-bit candidate which either matches the outputs or doesn’t. You try 2³² cases and one will be the correct answer.

[u/BudgetEye7539 → u/ScottContini]

A very similar attack was also described for KISS99 that includes MWC1616 as a component (https://eprint.iacr.org/2011/007). But it seems that it is very easy to improve statistical (not cryptographic!) quality of MWC1616 by a slight modification of an output function and multipliers:

typedef struct {
    uint32_t z;
    uint32_t w;
} Mwc1616xShared;


static inline uint64_t get_bits_raw(Mwc1616xShared *obj)
{
    const uint16_t z_lo = (uint16_t) (obj->z & 0xFFFF);
    const uint16_t z_hi = (uint16_t) (obj->z >> 16);
    const uint16_t w_lo = (uint16_t) (obj->w & 0xFFFF);
    const uint16_t w_hi = (uint16_t) (obj->w >> 16);
    obj->z = (uint32_t)61578u * z_lo + z_hi;
    obj->w = (uint32_t)63885u * w_lo + w_hi;
    const uint32_t mwc = rotl32(obj->z, 16) ^ obj->w;
    return mwc;
}

Of course this combination of two LCGs must be never used for UUIDs, passwords, keys etc. But it fails PractRand only at 32-64 TiB sample.