Hacker News new | past | comments | ask | show | jobs | submit login
The Physics of Brute Force (2016) (pthree.org)
34 points by tiord 17 days ago | hide | past | favorite | 12 comments



>where 0 Kelvin is defined as a system devoid of energy

This is not true, in quantum mechanics at zero kelvin (so in its fundamental state) a system has a non zero energy. See this: https://en.wikipedia.org/wiki/Quantum_harmonic_oscillator#Ha...


You're right. Zero Kelvin means no _entropy_.


Is that true either? E.g a metastable glass structure sent to 0k probably still has an entropy?


[edit:] Third law states 0K is impossible. That's the obvious and simplest answer. So everything bellow assumes the limit as you approach 0K.

I think in that case you reach a paradox because temperature is a quantity (typically) defined in thermodynamics, i.e. systems in equilibrium. A metastable glass is not in its ground state, therefore not in equilibrium, therefore not technically within the purview of thermo. This might seem like a cop out, but a similar question was asked in my qualifier. The answer, glass is not technically described my thermo and at 0K the whole thing breaks down [1]

Sure we still talk about entropy and temperature of glass, but it's stretching the definitions.

Another way to look at it, though, is that at 0K there is only one state available to the system (even though it is a glassy one). Therefore call the glass a new state of matter, and set S=0. If that feels weird because it's not the ground state, consider that glass' constituents, Si and O, are not in a ground state either, that'd be Fe. You don't have any problems dealing with metastable Si and O, do you? Either way, 0K makes no sense!

Also, it's weird (actually wrong) to even think about materials at 0K. In classical thermo your heat capacity is zero. In modern physics your atoms' "positions'" are fully determined, therefore their "momentum" is fully undetermined. So 0K is a state that makes zero sense.

[1] I forget the question. I think it was like this: the entropy of glass has a greater slope than the crystal, therefore, if you cool the glass low enough it will achieve a lower entropy than the crystal. How can a glass have lower S than its crystal state?


I don't know for metastable glass but you can read about the third law of thermodynamics which address the question of entropy and low temperature: https://en.wikipedia.org/wiki/Third_law_of_thermodynamics

Especially this might interest you:

"A classical formulation by Nernst (actually a consequence of the Third Law) is:

It is impossible for any process, no matter how idealized, to reduce the entropy of a system to its absolute-zero value in a finite number of operations."


Of course, current computers are nowhere near capable to try out substantial portion of all 256 bit keys. It requires massive amount of energy and time to perform single bit operation, much larger than kT for room temperature T (several orders of magnitude). Not mentioning costs of trying out the resulting bit sequence for validity as a key. That should be the argument for "256 bit keys are enough".

There isn't any fundamental energy cost imposed by physics here, however. Both because 1) bit flipping can be done in a logically reversible way, just go systematically from 0 to 2^256 - 1 so Landauer's assumptions do not even apply 2) Landauer's idea has been criticized for being vague/badly reasoned. Most weirdly, Landauer assumes that erasure of a bit register in general requires that thermodynamic entropy kln 2 per bit is acquired by the environment. It seems people are confused and can't distinguish information entropy and thermodynamic entropy here. In real computers, erasure of bit register decreases information entropy by kln 2 and increases thermodynamic entropy (by HW-specific amount) associated with the register. These are two different kinds of entropies.

In short, real world energy costs are far higher than Landauer's limit due to current tech limitations, and possible energy cost savings in the future aren't hard limited by Landauer's limit at all. Landauer's idea is simply too problematic. Don't rely on it for any argument about real world.

Finally, don't learn physics from computer science guys, even if their name is Bruce Schneier. Just as you wouldn't learn computer science from physics experts.


> "One of the consequences of the second law of thermodynamics, is that it requires energy to do a certain amount of work."

No, that is a restatement of the First law of thermodynamics. Second law states that it is impossible to systematically (cyclically) extract heat and turn it completely into equivalent amount of work.


> So, we'll run this ideal computer at 2.72548 Kelvin.

The record for lowest temperature is 1e-10 Kelvin and there is no theoretical limit as to how many zeroes can be added. So there is no hard limit, given good enough cooling/thermal isolation, the energy cost can be brought down. In theory, it can be brought down to zero.


This is addressed:

> To run a computer cooler than that would require a heat pump, which means adding additional energy to the system than what is needed for our computation.


That does not address it. It is true that heat has to be removed to maintain the lower temperature. But the rate at which this has to be done depends on heat generation and quality of isolation. If temperature inside is 1e-100 K, energy cost of only bit flipping becomes negligible. Energy cost of refrigeration depends then on how good the isolation is. With better and better isolation, the cost goes down, the only limit is zero.


The problem is I don't need to search the whole key space. Even with very goods encryption algorithms, there are faster attacks. They're not FAST attacks, mind you, so the keys are safe, but they are FASTer.


I think most of the time there is some attack on a cipher which is faster than the most obvious brute force attack.

Sometimes the speed-up is a little, sometimes it is a lot.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: