On 06/09/2011 04:53 PM, Solar Designer wrote:
On Thu, Jun 09, 2011 at 04:22:16PM -0500, Marsh Ray wrote:
Which neatly fits 2^32 trials per watt-second. A real engineer would
probably design the chips to minimize energy-per-trial, but I think our
estimate is probably still within an order of magnitude or two.
Last I checked, in the US electric power is around $0.07 per kWh in
areas considered "cheap". So each trial costs $4.53e???18 in electric power.
For an 64-bit key, you expect the adversary to need 2^63 trials for
which he might pay a power bill of $597.
That's scary. Even more so if you actually multiply by $0.07, which
gives $42.
Hmm, I thought I had included that.
I left my trusty old HP RPN calculator at home today and while a good
craftsman never blames his tools, apparently I'm not good enough to get
the same answer twice out of Ubuntu's. So double-checking my numbers and
suggestions on an RPN calculator app for Linux are welcome.
This means that for relatively small key size like this, the primary
cost for using an ASIC implementation is in creating that implementation
and in making it solve the specific task, not in electricity.
... and we all know folks who would do that sort of thing just for the
fun learning experience.
But what if the attacker doesn't want to pay the $100K minimum foundry
cost? How much of a penalty does he pay for using FPGAs, or even a
heavily optimized CPU+GPU codebase? Perhaps it's a huge hit, but even a
100x loss amounts to less than 7 bits of key length.
It also means that a good KDF should not be limited to using iterations,
but should also consume much die area - like scrypt does (requiring RAM)
or/and through lots of parallelism (in one KDF instance). If
implemented in software (on CPU or GPU), it should more fully use the
resources of that computer system (CPU/GPU execution units, RAM).
I think Scrypt has the right idea with consuming RAM or, more precisely
RAM nonlocal latency. CPU frequencies have gone from MHz to GHz, memory
has gone from MB to GB, even bus speeds have increased a few times, but
the time required to fetch a cold address from DRAM has changed least of
all.
I suspect an ideal work-factor function would thus look something like
RC4 (which is actually well defined over any state size) but with a few
GB of state rather than the 256 bytes that it's normally used with. Due
to some small patterns in the RC4 keystream it would still use a proper
hash function for distilling the final output hash value.
A few GB of state would hopefully put it in that size range where it's
too large to fit on any attacker's ASIC, while at the same time being of
a size for which a defender's commodity hardware is heavily optimized.
- Marsh
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
