r/crypto•
blimpyway

Memory latency time delay functions

Hi everyone, I'm rambling here about using DRAM technological latency limits in order to implement key generator functions in general and time delay functions in particular.

Current DRAM technology, in recent years showed significant improvement in transfer speed for large blocks of data, yet its random access time improvement is much less significant.

That means any cryptographic implementation that demands single-threaded, hard to predict read/writes on a large slice of memory can run only so much faster on a $10k 20 core 3GHz server, or a $1k GPU, vs. a $30 1Ghz Raspberry Pi or a smartphone with the same CPU/memory technology.

It's a potential of equalising hardware power. For example an ARM Pi clone has a 120-170ns (non-cache) memory latency while the fastest 4.2 Intel on Geekbench is advertised at 34ns. 4-5 times faster vs. much larger costs. There are also expensive servers with dozens of cores, but even these usually have much fewer (4-6) memory buses, that puts practical and cost limits on how good they are at random memory accesses.

The key for implementing such functions is to design them "easy" on computational entropy and "heavy" on memory-based entropy.

I know there are algorithms like scrypt configurable to use large memory, but, from what I understand they-re balancing computing and memory cost and I'm not sure how much they are limited by memory latency (most restrictive) instead of data size and transfer rates. ... And here-s my attempt to such a function, not intended for actual hashing or password encrypting, but only for delaying exposure of previously bound secrets in a (yet undisclosed) public random number generator. It's only constraint is to delay revealing a secret key for 10 to 60 seconds.

https://github.com/Blimpyway/publicrandom/tree/master/memhash

It's speed on my system (2.9Ghz I5 laptop 1600MHz DDR3) is ~90-100ns/cycle, and I expect it to be approx twice as slow on a ARM tablet or raspberry PI, and no more than 2.5times faster (36-40ns/cycle) on anything else.

Its default memory buffer size is 256MBytes, when configured to fit in cpu's 3MByte cache, it runs 5-6 times faster. Large servers I've seen have 64MByte caches, that's still 75% cache misses.

If anyone is curious to look at code and/or just test it on your hardware, I would be grateful for your feedback.

Posted Aug 25, 2017, 12:37 PM UTC

313
Loading comments…