I could be wrong (my physics background isn't that strong either) but I think Dyson's "time without end" paper http://www.aleph.se/Trans/Global/Omega/dyson.txt shows that eventually the universe will cool down enough to make all keys brute-force attackable despite Bremermann's limit.
Given a finite amount of attacker computation you're willing to defend against, you can get a real advantage from key stretching (though not from mere salting). If you want a password strength of 256 bits, you can memorize a password of 226 bits and require work equivalent to 2³⁰ key-hashing operations to derive the actual encryption key or crypted password. This is normally called a KDF; reasonable ones are scrypt, bcrypt, and Argon2. If you make the work factor unreasonably large, you won't be able to use the password in practice, because you have to do that work every time you use it. For the same reason that this is a safe way to derive keys for decrypting data at rest, in a client-server system, you can generally do this work on the client safely, so it doesn't pose a denial-of-service risk.
Is this proof that the universe cannot understand itself? It seems weird that there can be a set of information in the universe that can be hidden from the rest of the universe.
I can't say I understood and evaluated all the physics here (I skimmed parts) but I was pretty surprised by how small the estimate was. I would've assumed that, were we to have one or two thousand years more cryptographic history, we'd end up using ginormous keys (maybe on the order of 1 MiB?). But this suggests that 512 or 1024 bits might be all we need.
This is probably a decent estimate, but there's a couple of routes of attack it fails to account for.
First it uses the current average temperature of the universe. Lowering the temperature can be done by just waiting a while before turning the machine on. I assume that powering a sufficiently powerful fridge is not an option, given the origin of the theoretical limit, but I can't quite point out why it wouldn't work.
Secondly it assumes that an unsuccessful attempt must flip at least some bits in an semi-permanent manner. This is obviously true of all current computers, but doesn't have to be true for all possible apparatuses. A specialized hyper-efficient password cracking system should be expected to get below this limit. Will we ever build one? Who knows.
Arguably this latter 'loop-hole' is just pointing out that quantum computers or more efficient algorithms could do better, so maybe we should absorb it into the definition of 'brute-force'.
If you wait for the temperature to drop, and the universe is expanding, distant galaxies will recede to the point that they are now moving away faster than the speed of light and their matter is no longer available to contribute.
I know you're making a pun, but I will say one big benefit of deadlifting is a lot of things that would cause back-pain no longer do so. You don't have to lift a whole lot either, just enough to start building back muscles, and all of a sudden I can do things that would normally produce endless lower back pain.
That's the closest link I could think of, but "deadlifting" is at best a very specific and small step toward the implicit goal of "become immune to all physical harm". It doesn't make sense, so I figure there has to be something I'm missing.
I suspect this can be bypassed with knowledge about the size of the target system.
Intuitively, there are a finite number of passwords that can be stored on earth, so a large enough system should be able to enumerate them? Whilst also existing in the observable universe.
You only have to store a single 340-bit password (or something equivalent) in order to secure something with a 340-bit password. You can do this by, for example, writing down a 103-bit number on paper, which you can do on a business card with a pencil. Your argument seems to depend on the defender needing to store all possible 340-bit passwords, which they don't.
By "target system" you mean "system from which the password originated", right? But unless you think true randomness is impossible, and also that all possible sources of pseudo-random input on Earth come from terrestrial sources and not, say, incoming cosmic radiation, then knowing the size of the "Earth" system is no constraint at all. A heuristic for focusing your search, maybe, if you think the password is likely to be something easily memorable for a human, but that's nothing to do with the size of the system, just commonly-transmitted information there.
The phrase "stored on Earth" is a red herring. You don't need to store all possible passwords for those passwords to be possible to generate here. And really, a consequence of the article is that if enumerating even a couple hundred bits is prohibitive, then enumerating all possible information that could be generated by and stored in an earth-size system, as you seem to be suggesting, is no better.
> By "target system" you mean "system from which the password originated", right?
Yeah that’s correct.
> The phrase "stored on Earth" is a red herring. You don't need to store all possible passwords for those passwords to be possible to generate here.
A password used to protect a system must be persistently stored inside that system.
The number of passwords that can be generated on earth is greater than the number that can be persistently stored on earth.
For example, an iPhone must locally store a user’s unlock PIN code. However, it could theoretically generate a 20TB password for an external site in chunks without ever storing the full password locally.
Energy is a binding for password generation; but size is a constraint for password storage, which likely kicks in a lot earlier.
The password being persistently stored is not really a requirement here. That depends on the cryptosystem involved, among other things. What if I encrypt a ciphertext and throw away/forget the key?
Anyway, the constraint you're proposing here is, only passwords that can be encoded in all possible configurations of matter making up the earth? And you do have to contend with all possible configurations, if all you know is the size of the system, or even the mass and composition. As tedunangst put it, that's a lot of bits. I think we'll hit the 300-400 bit computational limit first.
It doesn't account for quantum computing? Cracking passwords seems like one of those things that should get an exponential speedup with quantum computing.
Speaking of physically immune schemes, I remember some protocol which relied on a gigantic amount of data present behind a link that was, on purpose, very low bandwidth (physically low bandwidth: not by software as in rate limitation. That was the whole point: the link was physically low bandwidth).
So the data was impossible to exfiltrate remotely: it simply wasn't physically possible to do remotely (it would be way too slow).
I forgot the name and what the data was used to protect/derive: maybe some authentication scheme?
Anyone knows what I could be talking about? I'm pretty sure I saw that posted here on HN in the past.
>I forgot the name and what the data was used to protect/derive: maybe some authentication scheme?
It's a variant of salted passwords, where the "salt" is a huge file that sits on a server somewhere. To validate any given password, it only requires accessing a few bytes that are deterministically but randomly determined. This isn't a problem when validating passwords, but if you're an attacker trying to exfiltrate the file (so you can run offline bruteforce attacks on it), the huge file becomes prohibitively expensive to exfiltrate.
The closest I can think of is ULF radio, which has two properties - extreme range and penetration, at the expense of extremely low bandwidth. My understanding is that it is used to communicate with underwater subs, but likely on the form of simple ascii or Morse code keywords.
I thought we had already established that the best way to beat that one is to have two passwords. First is Hunter2 and unlocks the keyboard for the second one: A variation of the Moonlight Sonata in off key.
I could be wrong (my physics background isn't that strong either) but I think Dyson's "time without end" paper http://www.aleph.se/Trans/Global/Omega/dyson.txt shows that eventually the universe will cool down enough to make all keys brute-force attackable despite Bremermann's limit.
Given a finite amount of attacker computation you're willing to defend against, you can get a real advantage from key stretching (though not from mere salting). If you want a password strength of 256 bits, you can memorize a password of 226 bits and require work equivalent to 2³⁰ key-hashing operations to derive the actual encryption key or crypted password. This is normally called a KDF; reasonable ones are scrypt, bcrypt, and Argon2. If you make the work factor unreasonably large, you won't be able to use the password in practice, because you have to do that work every time you use it. For the same reason that this is a safe way to derive keys for decrypting data at rest, in a client-server system, you can generally do this work on the client safely, so it doesn't pose a denial-of-service risk.
Is this proof that the universe cannot understand itself? It seems weird that there can be a set of information in the universe that can be hidden from the rest of the universe.
I can't say I understood and evaluated all the physics here (I skimmed parts) but I was pretty surprised by how small the estimate was. I would've assumed that, were we to have one or two thousand years more cryptographic history, we'd end up using ginormous keys (maybe on the order of 1 MiB?). But this suggests that 512 or 1024 bits might be all we need.
This is probably a decent estimate, but there's a couple of routes of attack it fails to account for.
First it uses the current average temperature of the universe. Lowering the temperature can be done by just waiting a while before turning the machine on. I assume that powering a sufficiently powerful fridge is not an option, given the origin of the theoretical limit, but I can't quite point out why it wouldn't work.
Secondly it assumes that an unsuccessful attempt must flip at least some bits in an semi-permanent manner. This is obviously true of all current computers, but doesn't have to be true for all possible apparatuses. A specialized hyper-efficient password cracking system should be expected to get below this limit. Will we ever build one? Who knows.
Arguably this latter 'loop-hole' is just pointing out that quantum computers or more efficient algorithms could do better, so maybe we should absorb it into the definition of 'brute-force'.
If you wait for the temperature to drop, and the universe is expanding, distant galaxies will recede to the point that they are now moving away faster than the speed of light and their matter is no longer available to contribute.
I thought this would be about deadlifting.
I know you're making a pun, but I will say one big benefit of deadlifting is a lot of things that would cause back-pain no longer do so. You don't have to lift a whole lot either, just enough to start building back muscles, and all of a sudden I can do things that would normally produce endless lower back pain.
Or, if you're like me, it can be the start of your back pain!
Real question: why?
I had a similar thought, along the lines of https://xkcd.com/538/
That's the closest link I could think of, but "deadlifting" is at best a very specific and small step toward the implicit goal of "become immune to all physical harm". It doesn't make sense, so I figure there has to be something I'm missing.
That was exactly what I was expecting, but the article was pretty good nonetheless
That's funny. I thought of a different XKCD. Deadlifting for a brute force-attack. https://xkcd.com/37/
Since we're doing "XKCD's relevant to the intersection of deadlifting and cryptography" - https://xkcd.com/189/
I suspect this can be bypassed with knowledge about the size of the target system.
Intuitively, there are a finite number of passwords that can be stored on earth, so a large enough system should be able to enumerate them? Whilst also existing in the observable universe.
You only have to store a single 340-bit password (or something equivalent) in order to secure something with a 340-bit password. You can do this by, for example, writing down a 103-bit number on paper, which you can do on a business card with a pencil. Your argument seems to depend on the defender needing to store all possible 340-bit passwords, which they don't.
By "target system" you mean "system from which the password originated", right? But unless you think true randomness is impossible, and also that all possible sources of pseudo-random input on Earth come from terrestrial sources and not, say, incoming cosmic radiation, then knowing the size of the "Earth" system is no constraint at all. A heuristic for focusing your search, maybe, if you think the password is likely to be something easily memorable for a human, but that's nothing to do with the size of the system, just commonly-transmitted information there.
The phrase "stored on Earth" is a red herring. You don't need to store all possible passwords for those passwords to be possible to generate here. And really, a consequence of the article is that if enumerating even a couple hundred bits is prohibitive, then enumerating all possible information that could be generated by and stored in an earth-size system, as you seem to be suggesting, is no better.
> By "target system" you mean "system from which the password originated", right?
Yeah that’s correct.
> The phrase "stored on Earth" is a red herring. You don't need to store all possible passwords for those passwords to be possible to generate here.
A password used to protect a system must be persistently stored inside that system.
The number of passwords that can be generated on earth is greater than the number that can be persistently stored on earth.
For example, an iPhone must locally store a user’s unlock PIN code. However, it could theoretically generate a 20TB password for an external site in chunks without ever storing the full password locally.
Energy is a binding for password generation; but size is a constraint for password storage, which likely kicks in a lot earlier.
The password being persistently stored is not really a requirement here. That depends on the cryptosystem involved, among other things. What if I encrypt a ciphertext and throw away/forget the key?
Anyway, the constraint you're proposing here is, only passwords that can be encoded in all possible configurations of matter making up the earth? And you do have to contend with all possible configurations, if all you know is the size of the system, or even the mass and composition. As tedunangst put it, that's a lot of bits. I think we'll hit the 300-400 bit computational limit first.
> A password used to protect a system must be persistently stored inside that system.
No it isn't; any system which is even remotely decent will only store the (usually salted) hash of passwords used on it.
There are a lot of bits available on the earth.
It doesn't account for quantum computing? Cracking passwords seems like one of those things that should get an exponential speedup with quantum computing.
Not exponential, cubic instead of quadratic.
Bigger issue in the context of this article is that it ignores reversible computing, which would nullify the core part of the thesis.
From what I read, trying to crack AES 256 with quantum is like cracking 128, so impossible
Speaking of physically immune schemes, I remember some protocol which relied on a gigantic amount of data present behind a link that was, on purpose, very low bandwidth (physically low bandwidth: not by software as in rate limitation. That was the whole point: the link was physically low bandwidth).
So the data was impossible to exfiltrate remotely: it simply wasn't physically possible to do remotely (it would be way too slow).
I forgot the name and what the data was used to protect/derive: maybe some authentication scheme?
Anyone knows what I could be talking about? I'm pretty sure I saw that posted here on HN in the past.
>I forgot the name and what the data was used to protect/derive: maybe some authentication scheme?
It's a variant of salted passwords, where the "salt" is a huge file that sits on a server somewhere. To validate any given password, it only requires accessing a few bytes that are deterministically but randomly determined. This isn't a problem when validating passwords, but if you're an attacker trying to exfiltrate the file (so you can run offline bruteforce attacks on it), the huge file becomes prohibitively expensive to exfiltrate.
The closest I can think of is ULF radio, which has two properties - extreme range and penetration, at the expense of extremely low bandwidth. My understanding is that it is used to communicate with underwater subs, but likely on the form of simple ascii or Morse code keywords.
Loving reading this but.. 'TLDR - at the bottom' is wicked
There are a couple of other worthy jokes in the text, BTW.
you don't need such complicated and hard to remember passwords--use something like bcrypt
Now do the wrench attack.
I thought we had already established that the best way to beat that one is to have two passwords. First is Hunter2 and unlocks the keyboard for the second one: A variation of the Moonlight Sonata in off key.
Freezing doesn’t always work for me while I’m at the dentist.
Does that help me build resistance to physical torture?
Decoy hard drives may work against coercion