4 ms·

Whenever you say how long something takes, you need to specify how much computing power is used to achieve it in that duration (FLOPS or whatever appropriate un

Whenever you say how long something takes, you need to specify how much computing power is used to achieve it in that duration (FLOPS or whatever appropriate unit). Then you see what it costs to manufacturer and operate the device that operates at that speed. Then you spend double to have 2 such devices and parallelize the job, completing it in half the time. Repeat that last part until the time is reasonable (TFA is all about this). It doesn't break down until you exceed the available natural resources and our ability to put them to work.

SAI_Peregrinus 5y ago
Typically we calculate assuming the total energy needed at the Landauer limit at 3K. It's usually going to be multiples of the entire sun's energy output for billions of years, more if not using a quantum computer. Money isn't the relevant metric at the scales of modern cryptography.
- amluto 5y ago
  But the Landauer limit, even at 300K, for a first preimage of even a completely secure hash is essentially zero. Define: f(s, n, h) = 1 if there exists an n-bit preimage of h that starts with s, else 0 Computing f by brute force costs one bit erasure to prepare room for the answer. (And takes 2^(n - len(s)) operations, but we’re imagining a civilization that can build Dyson spheres and has quantum, and hence at least somewhat reversible, computers. We’re talking about the Landauer limit in particular.) Now choose an appropriate n (slightly greater than the length of the hash) and compute f for s=[0] and s=[1]. After at most two tries, you’ll get a match, assuming a preimage exists. Call the first match s_1. Now repeat for s_1||0 and s_1||1. Call the first match s_2. Repeat this up to s_n. Now s_n is the lexicographically first n-bit preimage! This costs O(n) energy at the Landauer limit. All crypto is broken! Never mind that the actual computation involved exceeds 2^n.
  - SAI_Peregrinus 5y ago
    With reversible computing, yes. I strongly suspect that'll never be practically realized, or in the event that they are that the slowdown will be large enough that other fundamental limits on the speed (rather than the energy) of computing will instead dominate.
jodrellblank 5y ago
Brute-forcing 2^256 is impossible at any price; if you could convert all the matter in the Sun to energy and capture all the energy and drive the lowest power computers physics allows, you wouldn't have a billionth of the required energy: https://security.stackexchange.com/questions/6141/amount-of-simple-operations-that-is-safely-out-of-reach-for-all-humanity/6149#6149 https://security.stackexchange.com/questions/6141/amount-of-...

SAI_Peregrinus 5y ago

Typically we calculate assuming the total energy needed at the Landauer limit at 3K. It's usually going to be multiples of the entire sun's energy output for billions of years, more if not using a quantum computer. Money isn't the relevant metric at the scales of modern cryptography.

amluto 5y ago
But the Landauer limit, even at 300K, for a first preimage of even a completely secure hash is essentially zero. Define: f(s, n, h) = 1 if there exists an n-bit preimage of h that starts with s, else 0 Computing f by brute force costs one bit erasure to prepare room for the answer. (And takes 2^(n - len(s)) operations, but we’re imagining a civilization that can build Dyson spheres and has quantum, and hence at least somewhat reversible, computers. We’re talking about the Landauer limit in particular.) Now choose an appropriate n (slightly greater than the length of the hash) and compute f for s=[0] and s=[1]. After at most two tries, you’ll get a match, assuming a preimage exists. Call the first match s_1. Now repeat for s_1||0 and s_1||1. Call the first match s_2. Repeat this up to s_n. Now s_n is the lexicographically first n-bit preimage! This costs O(n) energy at the Landauer limit. All crypto is broken! Never mind that the actual computation involved exceeds 2^n.
- SAI_Peregrinus 5y ago
  With reversible computing, yes. I strongly suspect that'll never be practically realized, or in the event that they are that the slowdown will be large enough that other fundamental limits on the speed (rather than the energy) of computing will instead dominate.

jodrellblank 5y ago

Brute-forcing 2^256 is impossible at any price; if you could convert all the matter in the Sun to energy and capture all the energy and drive the lowest power computers physics allows, you wouldn't have a billionth of the required energy: https://security.stackexchange.com/questions/6141/amount-of-simple-operations-that-is-safely-out-of-reach-for-all-humanity/6149#6149 https://security.stackexchange.com/questions/6141/amount-of-...