6 ms·
Our mistake is using cryptosystems that only last 20 years. We should be using 100 year crypto. That's crypto that a crypto expert is willing to bet her entir
by londons_explore 6y ago
Our mistake is using cryptosystems that only last 20 years.
We should be using 100 year crypto. That's crypto that a crypto expert is willing to bet her entire net worth will be unbroken in 100 years.
Today, no such schemes exist.
But as far as I know, any two different hashing schemes applied sequentially has never been broken.
Therefore, why not get the Americans to develop their best hashing algorithm, the Chinese to develop their best algorithm, and then use A(C(data)).
Alternatively, bite the performance bullet, and use a provably secure hash algorithm. Build specialized hardware for the problem to speed it up.
- reificator 6y ago> Our mistake is using cryptosystems that only last 20 years. > We should be using 100 year crypto. That's crypto that a crypto expert is willing to bet her entire net worth will be unbroken in 100 years. This sounds nice but let's wait until modern electronic computers have even been around 100 years so we can have an idea of what that means.
- glitchc 6y agoMhmm, and what will you pay for that kind of guarantee, hmmm?
- deleted 6y ago[deleted]
- reificator 6y agoI think you responded to the wrong comment.
- Splognosticus 6y agoWe're remarkably close--ENIAC was first powered up in 1946. Kinda cool when you think about it--electronic computers are WWII-era technology and a lot of us reading this now will see their 100-year anniversary.
- reificator 6y agoIn other words we're still over a quarter of a century away.
- saagarjha 6y agoHashing twice doesn't actually help in many cases that hashes are used. And I don't think there is a such thing as a "provably secure hashing algorithm", although I would very much be interested in learning about the topic if you have a reference :)
- edoceo 6y agoThere are some here: https://en.m.wikipedia.org/wiki/Security_of_cryptographic_hash_functions https://en.m.wikipedia.org/wiki/Security_of_cryptographic_ha... But, it does say practically provable
- tptacek 6y agoEverything in cryptography is more complicated than you'd hope it would be. On this one, see for instance: https://cryptopals.com/sets/7/challenges/52 https://cryptopals.com/sets/7/challenges/52
- petertodd 6y ago> But as far as I know, any two different hashing schemes applied sequentially has never been broken. Suppose you used SHA256(MD5(x)) as your sequential hashing function. If I can find two messages m1, and m2 that have the same MD5 digest, the outer SHA256 will also collide. MD5 is sufficiently broken that finding such messages is easy: https://github.com/thereal1024/python-md5-collision https://github.com/thereal1024/python-md5-collision Two different hashing schemes applied in parallel is better. However even there many uses of hashing functions require all the bits in the output digest to be equally unpredictable.
- tptacek 6y agoIf one of your hashes is iterated, you also have the multicollision problem: once you find a collision in your weak, iterated hash, you can quickly produce more collisions, so that the strength of your construction just devolves to that of the stronger hash.
- delhanty 6y agoFor clarity, which part of petertodd's comment are you replying to? (I'm learning a little cryptography from this thread, so the above is a straight question.)
- bawolff 6y agoI believe he is responding to "Two different hashing schemes applied in parallel is better." My understanding is if you have a collision in the stronger function, you have an infinite family of collisions in the stronger function due to the length extension attack, from there you should be able to base the collision for the weaker function on one of the stronger function's (length extended) collisions.
- delhanty 6y agoThank you for that reply - particularly the informative explanation. I was sort of assuming it must be a reference to the parallel schemes because with SHA256(MD5(x)), once you had an MD5 collision you would be done.
- nemothekid 6y ago>Therefore, why not get the Americans to develop their best hashing algorithm, the Chinese to develop their best algorithm, and then use A(C(data)). If you can find a collision in C(x), then A(C(x)) will have a collision as well.
- fiddlerwoaroof 6y agoWell, then make your hash: A(C(x))+C(A(x)) Just concatenate all the permutations of hashing functions. Although, maybe just concatenating the single-hash values is just as secure. A(x)+C(x)
- tatersolid 6y agoAt four times the computation, which is a pretty big problem when you’re trying to authenticate every packet on a >= 10 Gb/s network Using a better hash like Blake2 makes a lot more sense
- fiddlerwoaroof 6y agoIf the point of using two hashes is resistance against people breaking one of the hashing algorithms used, you’re always going to have to pick more than one algorithm to get that benefit. However, I don’t think nesting the calculations is actually necessary: Blake2(msg)+sha512(msg) would give you the same protection.
- Moodles 6y agoHow would hashing twice help with a collision? Surely if your hash function is A(C()) then if you find a collision in C() then that is also a collision in A(C())? Also, just saying “we should use 100 year crypto” is about as useful as saying “we should hurry up and cure cancer”. Nobody has a probably secure hashing function. It’s actually a huge problem in cryptography that a lot of the time hashing is modelled as a perfect random oracle and there are schemes which are secure only if modelled with a random oracle, but insecure when instantiated with any concrete hashing function.
- marta_morena_28 6y agoProbably means (A(text) XOR C(text)) or something. Then you would need to find a collision in both algorithms for the same input and that will be arguably much harder. I.e. just because someone demonstrates a lack of knowledge in his/her post, you can still show some flexibility for positive interpretation ;).
- cryptopls 6y agoThis is only as strong as the stronger of A and C. If we had picked MD2 and MD4 to xor in the 90's we'd be no better off today. If there was a trivial way to get much stronger hashing with double the compute time we'd do it.
- adzm 6y agoCouldn't you concatenate the two hashes? Twice the size but you'd have to find a collision for both algorithms.
- bawolff 6y agoFinding the two collisions are not independent of each other so its more like finding the collision in whichever function is stronger. (I.e. finding a collision in md5 + sha1 is roughly as hard as finding a collision in just sha1)
- umanwizard 6y ago> bite the performance bullet, and use a provably secure hash algorithm Do these exist? (Genuine question; I’m not familiar with the state of the art.)
- verandaguy 6y agoDepends what you mean by "provably secure." Hashing algorithms are usually only practical because of what compromises they make to achieve "good enough." - At the most basic level, (practical) hashing cannot map all inputs to the same number of outputs, since consistent output length is usually highly desirable. This means that for sufficiently long inputs you will get collisions. What determines how good a hash is is often how hard that is to do. - If your inputs map 1:1 to outputs, rainbow tables become harder but you open yourself up to a number of other possible attacks starting with the obvious length analysis. - Hashing also often has to be very performant, which leads to its own compromises, but in many applications (like message digests) throughput performance is given a lot of weight. In the most formal way, I guess it's possible to have a provably secure hash for all possible attacks, but this would most likely require a 1:1 mapping between inputs and outputs. This would be impractical for a few reasons.
- Dylan16807 6y agoThe output has to be indistinguishable from random, and colliding n bits needs to take an exponential amount of time. Output length can be anything. As long as it's indistinguishable from random, the chance of collision will be exponentially rare, and you can truncate or concatenate to get the length you want.
- verandaguy 6y agoYou're correct on all points, though this kind of implementation (with variable-length output) is fairly rare AFAIK. Having a fixed-length output lets you reliably define for example a database field length. I'd love to see a practical implementation of that though, if you know where to find that kind of project off-hand!
- pixl97 6y agoYa, there are also speed considerations when it comes to hashing that are more important than total security. If your mobile phone catches on fire, or your bandwidth is cut by half the extra security isn't worth the trade. Also go back to 1920 and design a public crypto system that can't be broken today.
- stordoff 6y ago> Therefore, why not get the Americans to develop their best hashing algorithm, the Chinese to develop their best algorithm, and then use A(C(data)). Would it not be better to report both A(data) and C(data) (or maybe all three), so you have to simultaneously find a collision in both? Using A(C(data)), finding a collision in C(data) gives a collision in A(C(data)) as well. Further, there are other considerations - it doesn't matter how secure the hash is if it's unusably slow.
- bawolff 6y ago> A(C(data)) This is just as weak as C. Any collision in C is by definition a collision in A(C(data). You probably meant A(data) ^ C(data) [XOR] which is mostly as weak as the stronger of A and C. Google multicollisions in iterated hash functions for more details.