WARNING: Please don't use Ramhog! This is a lame algorithm that is easily sped up in an ASIC attack. It was generated by an armature, and never peer reviewed in any way. I broke it in an hour completely. If there were a thriving mining community for ShinyCoin, I would likely have to go build some hardware to out mine everyone by 100X or so per $ invested.
First flaw: the xor-shift PRNG is _not_ cryptographically secure. In particular, given index i and the initial state, I can compute xorshift(i) in constant time. Given that only 1 in 512 memory locations is in any way different from this output (times a constant which does nothing), I can generate the pads in a massively parallel attack, and have 511 out of every 512 locations right. The final locations are trivially computed in a lazy manner on demand.
The final loop only reads a bit over 8 million locations, so I only need to generate a tiny fraction of the actual data. There is also a terrible time-memory trade-off. OMG, this algorithm is lame. Please use something more secure, like Scrypt! One of the three entries in the password hashing competition that are better than scrypt might also be OK: Yescrypt, Lyra2, and Argon2 (in that order of preference).
The flows in Ramhog are so extensive, I don't want to bother listing what I found in just an hour. This algorithm is a lost cause. However, the worst offender is how their PRNG can be computed massively in parallel. The PRNG is:
static inline uint64_t xorshift_next(xorshift_ctx *pctx)
{
uint64_t s0 = pctx->s[ pctx->p ];
uint64_t s1 = pctx->s[ pctx->p = ( pctx->p + 1 ) & 63 ];
s1 ^= s1 << 25; // a
s1 ^= s1 >> 3; // b
s0 ^= s0 >> 49; // c
pctx->s[ pctx->p ] = s0 ^ s1;
return ( pctx->s[ pctx->p ] = s0 ^ s1 ) * 8372773778140471301LL;
}
There are 64 "state" variables, of 64-bits each, for a total state of 4096 bits. The entire state is generated securely with PBKDF2-SHA256. However, after that, all that happens is that state variables get shifted and xor-ed on each other in a _fixed_ pattern. I can represent 64 iteration of xorshift as a 4096x4096 Boolean matrix. To compute the n-th state, I simplly multiply the initial state times this matrix to the power of n/64. For source code to do this sort of Boolean matrix operation, see my Github repo bmat:
https://github.com/waywardgeek/bmatCould you crypto-coin guys please try to have a public review of your PoW algorithms before starting your block chains? Alternatively, could you let a million bucks or so of market cap grow, and then send me a notice to see if I can PWN your currency? I was too late for this one, and also too late for that one based on Momentum (another broken PoW). Heck, I only learned how to crack PoW algorithms over the last 18 months. Are there any new hacked-up PoW coins out there I should attack?
Thanks,
Bill
Show Posts
