3 ms·

> Suppose that against all expectations, someone finds a 2^100 attack on AES-128 that is embarrassingly parallel and uses no additional memory. Say

by nullc 7y ago

> Suppose that against all expectations, someone finds a 2^100 attack on AES-128 that is embarrassingly parallel and uses no additional memory. Say you have 10 billion cores, each running at 10 GHz, trying one key per cycle, and you’re aiming for a one-in-a-million success rate: it’d still take you on average more than twelve thousand years of computation to do the ≈ 2^80 required According to the Bitcoin node on my computer, there have been ≈ 2^92.4 executions of the sha-2 compression function used for Bitcoin so far, exactly the sort of embarrassingly parallel memory-less task that the author speculates about. So the author's example of a obviously secure attack resistance level has already been exceeded just by bitcoin mining by a factor of thousands. > For example, “zero-sum distinguishers” [4],arguably the most contrived and meaningless type of attack ever, are about finding a set of input values whose output values sum to zero. I realize that the author is making fun of his own prior work, but I think he exaggerates the uselessness of such an attack. Finding a set of inputs to a hash function such that the hashes sum to zero (or other specific values) can be directly turned into attacks on cryptographic systems that use those hashes. In particular, attacks like that can lead to total breaks in things like threshold signature protocols and blind signing. When cryptographic primitives have surprising structured properties there often seems to be a greater fool hiding right around the corner waiting to build a system that almost magically is broken by the structured property. :)

floodyberry- 7y ago
Unless I'm missing something in the calculation, 2^80 / (10 billion * 10ghz) = 12089 seconds, not years, which does flip his point re: 2^128 being uncomfortably risky if you want to factor in potential improvements.
muldvarp 7y ago
You're not wrong. I wouldn't count on AES-128 staying secure for all of eternity, but I don't like they way you say > just by bitcoin mining like the bitcoin network is a small hobby project in someones basement. The bitcoin network has the same annual energy footprint as the country of Austria. The truth is that even with a purely hypothetical 2^100 attack on AES-128 the NSA wouldn't be able to crack a single key even if all of their funds would go directly into paying for electricity.
- nullc 7y ago
  The energy calculations for bitcoin usually range between wrong and absurdly and painfully wrong. Expenditures on the mining are bounded on the upper end by the income, which sets a current ceiling at about $13 million USD per day. In practice actual expenditures are a fraction of that upper bound, since the hardware still needs to be paid for an it wouldn't be worth doing without a profit. Bitcoin's energy usage level (even the high upper bound) of expenditure is within the estimates of the NSA's budget (10.8billion usd/yr est in 2013). The Manhattan Project had an estimated cost of $23 billion (2018) dollars. If we take the article's target of 2^80 operations (for a one in a million against a 2^100 expected attack), and assume those operations are as efficient as bitcoin miners do sha256(sha256()) -- 0.075J/billion ops. And then we assume you pay 2.5cts per KWH for power (an industrially available rate in low power cost areas of the US) --- that attack would cost $629648 in power. I bet the US has single munitions that cost almost much. The article is just simply mistaken about the intractability, the current existence of computation at a scale it claimed would take ten thousand years shows it nicely-- it doesn't matter that the computation has indeed, been pretty costly. This makes another argument for setting parameters conservatively: order of magnitude errors in attack costs are less likely to be fatal if you do!
  - muldvarp 7y ago
    > The article is just simply mistaken about the intractability, the current existence of computation at a scale it claimed would take ten thousand years shows it nicely Well yeah, the article might be wrong about how untractable it is, but that doesn't mean it is tractable. Even when taking the minimum annual electricity consumption of the Bitcoin network (41.31TWH/yr) and assuming the Bitcoin network did all those hashes in the last year and assuming that a 2^100 attack on AES-128 exists (which it doesn't), you'll still need an absurd amount of energy just to crack a single key. > setting parameters conservatively My argument is that for almost all applications key lengths of 128 bits are pretty conservative. AES-128 will not be the weak link in your application, bad usage of cryptography, memory leaks, use-after-free vulnerabilities, users just doing stupid things, 0-days in your operating system of choice are all easier to exploit than cracking a single AES-128 key. That said, you probably shouldn't use AES-128 if your threat model includes a intelligence agency 50 years into the future. In that case AES-256 will not help you either.

by nullc 7y ago

floodyberry- 7y ago

Unless I'm missing something in the calculation, 2^80 / (10 billion * 10ghz) = 12089 seconds, not years, which does flip his point re: 2^128 being uncomfortably risky if you want to factor in potential improvements.

muldvarp 7y ago

You're not wrong. I wouldn't count on AES-128 staying secure for all of eternity, but I don't like they way you say > just by bitcoin mining like the bitcoin network is a small hobby project in someones basement. The bitcoin network has the same annual energy footprint as the country of Austria. The truth is that even with a purely hypothetical 2^100 attack on AES-128 the NSA wouldn't be able to crack a single key even if all of their funds would go directly into paying for electricity.

nullc 7y ago
The energy calculations for bitcoin usually range between wrong and absurdly and painfully wrong. Expenditures on the mining are bounded on the upper end by the income, which sets a current ceiling at about $13 million USD per day. In practice actual expenditures are a fraction of that upper bound, since the hardware still needs to be paid for an it wouldn't be worth doing without a profit. Bitcoin's energy usage level (even the high upper bound) of expenditure is within the estimates of the NSA's budget (10.8billion usd/yr est in 2013). The Manhattan Project had an estimated cost of $23 billion (2018) dollars. If we take the article's target of 2^80 operations (for a one in a million against a 2^100 expected attack), and assume those operations are as efficient as bitcoin miners do sha256(sha256()) -- 0.075J/billion ops. And then we assume you pay 2.5cts per KWH for power (an industrially available rate in low power cost areas of the US) --- that attack would cost $629648 in power. I bet the US has single munitions that cost almost much. The article is just simply mistaken about the intractability, the current existence of computation at a scale it claimed would take ten thousand years shows it nicely-- it doesn't matter that the computation has indeed, been pretty costly. This makes another argument for setting parameters conservatively: order of magnitude errors in attack costs are less likely to be fatal if you do!
- muldvarp 7y ago
  > The article is just simply mistaken about the intractability, the current existence of computation at a scale it claimed would take ten thousand years shows it nicely Well yeah, the article might be wrong about how untractable it is, but that doesn't mean it is tractable. Even when taking the minimum annual electricity consumption of the Bitcoin network (41.31TWH/yr) and assuming the Bitcoin network did all those hashes in the last year and assuming that a 2^100 attack on AES-128 exists (which it doesn't), you'll still need an absurd amount of energy just to crack a single key. > setting parameters conservatively My argument is that for almost all applications key lengths of 128 bits are pretty conservative. AES-128 will not be the weak link in your application, bad usage of cryptography, memory leaks, use-after-free vulnerabilities, users just doing stupid things, 0-days in your operating system of choice are all easier to exploit than cracking a single AES-128 key. That said, you probably shouldn't use AES-128 if your threat model includes a intelligence agency 50 years into the future. In that case AES-256 will not help you either.