I‘m wondering if they could avoid yet another breaking protocol change if SHA256 proves to be insecure (at some point in the future) if they made use of Multiformats [0]. At least IPFS went this way (Multiformats grew out of the IPFS development).
Generally speaking this is called “cryptographic agility” and the security community has decided that it’s an antipattern. The alternative is to have a specified suite of security mechanisms pinned to each version. You can still have backwards compatibility, but it helps avoid downgrade attacks.
Multiformats is not really cryptographic agility, it's just adding a small tag that indicates what type of data something is (what kind of encoding, what kind of hash, what kind of binary payload, etc). The benefit is that the tags are standardised rather than being tied to a protocol version or some other out-of-band information. Whether or not you start making negotiation decisions based on that header is what determines whether you have cryptographic agility.
I'm also not sure I'd say the security community as a whole feels that cryptographic agility is an anti-pattern, there are plenty of vocal voices on all sides of that argument. I personally agree that you gain very little from cryptographic agility but have to pay a fair amount, but I don't think it's as settled as you make it out to be.
> I'm also not sure I'd say the security community as a whole feels that cryptographic agility is an anti-pattern, there are plenty of vocal voices on all sides of that argument. I personally agree that you gain very little from cryptographic agility but have to pay a fair amount, but I don't think it's as settled as you make it out to be.
I totally agree with this assessment, and rereading my comment, I say that as though it’s a lot more settled than it is.
I think it’s probably harmless to tag those sorts of bits of data, but also JWT has shown us that having that metadata in band does lead to people using it for those kinds of decisions whether they’re supposed to or not.
The Wikipedia link is very reassuring regarding the security of SHA256. All attacks are very far away from going anywhere close to attacking full SHA256 and no major progress has been made lately.
The password hashing remark is correct, but irrelevant. SHA256 is not a good password hash, because it's not made to be a password hash. Don't use it for passwords.
The weaknesses that broke MD5/SHA1 were known since 1994. No similar weakness is known for SHA256.
Because SHA256 is fast to compute. This means that an attacker can quickly try many passwords, either from a dictionary of common passwords or simply brute forcing a short password.
Also, if you use SHA256 bare without salt you are vulnerable to precomputed dictionaries. There is a fascinating way to make these dictionaries shorter called Rainbow Tables.
Better key derivation functions take a lot of time and memory to make it costly for the attacker to a lot of guesses at the password and they have built in salt. Examples would be SCrypt or Argon2.
Because it wasn't designed for it. For password hashing you want a hash that has a salt (so that the same password on two accounts doesn't have the same hash on the database) and is as slow as possible (that is, fast enough to validate on logins) to increase brute-force time.
Historically Bcrypt was a good option, but I think Argon2[0] is the current best option.
I thought adding a salt to a password before hashing it was standard practice, regardless of the hashing function. At least that's how UNIX derivatives have done it for the past 25+ years.
A password hash is a function with 3 inputs: the password, the difficulty factor, and a customization structure (most often just a salt, sometimes more). A cryptographic hash is a function with 1 input: the message.
Password hashing functions have variable performance in time and usually memory and cache use, controlled by the difficulty factor. Cryptographic hashes have fixed performance.
Password hashing functions take a salt and possibly other customization data (a secret "pepper", a fixed domain-separation string if it's also a key derivation function, etc).
It's possible to build password hashes from cryptographic hashes. One must be very careful about encoding the multiple inputs into a single "message" for the cryptographic hash, to avoid cannonicalization attacks.
If you want to be reassured then sure.
My take from reading that is in 2016 there was practical collision attacks demonstrated, which would be amplified with specialized hardware (compare to
bitcoin mining).
Btw cheers!
I recall you from correspondence years ago regarding fuzz testing linux packages.
This is 1. not about SHA256, but about the truncated sha2 algorithms and, more important, 2. it's an attack on reduced-round versions of these algorithms.
That's a common thing in cryptoanalysis to do. You're basically saying "we have no way of attacking the full algorithm, so let's build a version which is much less secure and try to attack that". That's a valid thing to do for research purposes, but it needs to be interpreted correctly. "I can break this massively weaker version of the algorithm" is very different from "I have shown a practical attack on the real algorithm".
Absolutely, you are correct - the papers does not describe SHA256 as broken, but it is one step of many on the path for SHA256 to become broken in the future - which is in reply to your earlier comment:
> You're proposing to add extra complexity for some hypothetical scenario that is unlikely to happen
> but it is one step of many on the path for SHA256 to become broken in the future
I disagree. It's evidence that the given path is not fruitful for breaking SHA256 in the future. When numerous researchers worldwide have attacked a function, and only broken X out of N rounds, for X << N, and future research hasn't been able to improve X for years, that's pretty good evidence that the technique used isn't going to continue to apply for more rounds. The existence of a multi-billion dollar bug bounty for breaking SHA256 (Bitcoin) that's gone unclaimed for years is further evidence that it's quite strong.
This is not true. Modern cryptography is not breakable via brute force any more, nor will it ever be. You can prove that the amount of energy required assuming a thermodynamically ideal computer is more than will ever be available in our galaxy, with classical computing.
Breaks of symmetric crypto or hashes that are practical require an actual cryptographic weakness, whose existence is not a given.
Then there's quantum computing, but that also doesn't break symmetric crypto outright, it just makes it weaker. I'm not sure if anyone has run the math, but we'd probably still be talking galaxy sized quantum computers to get anywhere.
>Modern cryptography is not breakable via brute force any more
Specifically, modern symmetric crypto (and hashing which is a related but different thing) is fine. It's public-key crypto that has always been the worry thanks to Shor's Algorithm, and all modern widely used crypto there is indeed vulnerable if an actual scalable general quantum computer could be constructed. There are a variety of post-quantum cryptographic algorithms under development including some ones that would be ugly slow but likely effective bandaids if required, but that's still a not totally unreasonable concern for certain threat profiles. But yes GP was totally wrong about "all methods are broken when compute becomes faster".
>I'm not sure if anyone has run the math
"The math" here is just Grover's Algorithm, that lowers the cost of generic brute forcing to O(sqrt(n)). So a 128-bit symmetric key could be cracked on average like 2^64 or a 256-bit key like 2^128. Obviously this is utterly trivially countered by doubling the exponent. Even 2^128 is still ridiculous, and going to a 512-bit key brings us right back to 2^256 which is impossible. 128-bit keys should indeed be phased out entirely (and that seems to be well on the way anyway), and perhaps 256-bit too at some point (even if it's only the very paranoid or very long termers, it's also not big stretch on modern hardware at all, so eh), but fundamentally yes symmetric crypto is fine.
I know about Grover's Algorithm, but the reason I didn't want to make any hard claims is that with hashes you also have to worry about collision attacks. Those give you an O(sqrt(n)) time advantage themselves in classical computing, at the expense of space for storing existing hashes (birthday attack), and you can play with the balance as a space-time tradeoff. I can't claim to have any idea how those interact with quantum crypto, plus once you introduce storage at a large scale I imagine you start running into speed of light and communication energy cost issues.
So one thing im thinking could work is to do a sort of probabilistic birhtday attack. Like you could do a binary search, where in every step you narrow down on the bucket with more data.
So like lets say a year had 256 days and you want to find colliding birthdays. First you would check how many birthdays in 0-127 vs 128-255. This takes just two counters - very little storage. Then lets say the former has more. You'd try 0-63 vs 64-127. Etc.
But yeah this will of course miss collisions. But I think if you have enough children (where enough is still pretty close to sqrt(n)) it should have a good chance of finding a collision.
And subdividing into many buckets at a time will miss less collisions, but require more storage - a tradeoff can be used.
This is why they create laws to require you unlock your phone when crossing borders.
I have been constantly surprised that there isnt a phone/company that specifically markets to "buy this temp phone to cross a border"
--
Also, WRT Quantum computing, what are your thoughts on the talk by D-Wave CEO where he said "we can reach into different dimensions" -- and soon after, D-Wave went super silent?
What is the state of quantum currently - did they discover something super secret?
That is not true. There is nothing provable about hash functions. The best that you can say is that there is no known algorithm that can calculate a pre-image for any given hash function in less than some super linear time. You certainly cannot prove that no such algorithm exists. If you can prove it please publish a paper you will be revolutionize mathematics.
> The best that you can say is that there is no known algorithm that can calculate a pre-image for any given hash function in less than some super linear time.
If your algorithm is not linear in the size of the key/hash space, it's not a brute force algorithm. It's a cryptographic break.
There is no proof that such algorithm does not exist, nor is there any proof that it does. Therefore you can't claim it definitely does. That's my point.
AFAIK, this is more of a belief than a fact. I would be very curious if you would show me a rigorous proof that e.g. SHA256 requires like on the order of 2^256 of operations to find a preimage of a random 256-bit string.
The total energy output of a supernova is enough to count up to 2^220, making a lot of generous (invalid) assumptions. You'd need 2^36 supernovas to just count up to 2^256, never mind actually running SHA256. At minimum.
There are circa 2^38 stars in the Milky Way, and they're not going to all go supernova. Add in the actual cost of compute and it just isn't happening, not in this galaxy.
For 128-bit crypto we can look at a more earthly calculation. Using the same math as that article, but at room temperature, and taking the total solar irradiance on the Earth as an energy source, it would take this long to count up to 128 bits (calculated using Google):
Definitely more on the plausible side, but we're already moving away from 128-bit crypto and there's a staggering number of generous assumptions being made here; we aren't going to be getting thermodynamically ideal computers using a significant fraction of the total solar irradiance on the Earth any time soon.
Just to give you an idea of how far away we are from that, looking at actual SHA256 calculations:
22222 MH/J is the highest, or 4.5 × 10^-12 joules per hash. That's a factor of 2^30 worse, so if we used the total solar irradiance of the Earth to power Bitcoin miner style ASICs, it would take about 272 years to go through 128 bits' worth of brute forcing something of similar complexity to SHA-256.
The factor is more like 2^36 relative to the first "temperature of outer space" calculation. That happens to be about the number of galaxies in the observable universe, so using current technology, it would take somewhere on the order of all the stars in the observable universe going supernova to power through a single SHA-256 brute force.
I swear there was a pertinent article link that goes through how it's physically impossible to construct a computing device fast enough to break SHA-256, even at the most fundamental scale.
The magnet URL format is at least using multihash:
> Like the urn:btih: prefix for v1 SHA-1 info-hashes, there’s a new prefix, urn:btmh: for full v2 SHA0256 info hashes. For example, a magnet link thus looks like this:
1) Take a popular game torrent 2) add crypto mining code 3) pad it so the SHA1 stays the same 4) seed it, the magnet links will pick up your version 5) profit!
That's a preimage attack. For example, the entire bitcoin network today needs something on the order of a trillion years for a preimage attack on MD5, multiply by another trillion for a SHA1 preimage attack.
There's no indication whatsoever of this happening.
In the time since SHA1 came under attack, a lot more research has happened on hash function security. If this has shown anything, it's that SHA256 is more secure than people used to think.
People seem to have this widely believed idea that "all crypto will be broken eventually". But in pretty much all cases you can trace back that broken crypto was known to be weak for a long time. SHA256 is not known to be weak (with the slight caveat that it doesn't protect against length extension attacks, but this is a known property that matters only in very rare circumstances).
That's not a given. As far as I know, there is no proof of the security or lack thereof of this kind of function.
Increases in computing power alone can't render SHA256 insecure; that can be proven by thermodynamic/size-of-the-universe arguments. You need an actual cryptographic weakness.
[0] https://multiformats.io/