Hacker News Reader

Comment by londons_explore | Hacker News Reader

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.

View on HN

How 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.

Probably 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 ;).

This 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.

Couldn't you concatenate the two hashes? Twice the size but you'd have to find a collision for both algorithms.

Finding 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)

then we just need to use ALL of them

Is that true?

In the past (long enough ago that using md5 almost made sense), I used a combination of md5 and sha1 to verify file integrity. Both checksums had to match or the file was rejected.

It seems obvious that that's at least as strong as using sha1 by itself. I've always assumed it was significantly stronger than sha1 by itself, but you're saying it isn't.

Creating an md5 collision isn't terribly difficult these days, but I've never heard of an md5 collision that's also a sha1 collision.

Can you cite a source with more information on this?

(I'm not doubting what you say, I'd just like more information.)

https://www.iacr.org/archive/crypto2004/31520306/multicollis...

Although looking over this again, there is some caveats in that if both hash functions suffer from shortcut attacks, you might not be able to combine both shortcut attacks depending on the details of the shortcut attack.

Regardless, in the sha1+md5 case, even if you cant combine both shortcut attacks (big if. Not sure if that's true or not), the complexity of the sha1 collision is roughly the same as a birthday attack on md5, so i think you still end up with close to same big-oh as if you could combine both shortcut attacks.

Disclaimer: IANAC.

If you xor the hashes together, it may be as weak as the weaker of the two functions, though it probably depends on their structure.

Getting much stronger hashing with double compute time is easy. Double the number of round - most alorithms have about 30-60% security margins. It would probably avoid any breaks of the hash (so 80 bits for SHA1), though it can't be enough if the hash is simply too small (64 bit security for MD5/4/2).

Yeah, this is similar to how people ended up inventing HMAC I think.

Provably secure hashing functions exist. For example Very Smooth Hash.

They just perform poorly.

You are right

> 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.

Mhmm, and what will you pay for that kind of guarantee, hmmm?

I think you responded to the wrong comment.

We'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.

In other words we're still over a quarter of a century away.

> 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

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.

If 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.

For 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.)

I 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.

Thank 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.

Two hashing schemes in parallel has problems too. Suppose your parallel hash is SHA3+Ident, where Ident is either the first 100 bytes of the message or the message padded with NUL up to 100 bytes. Because Ident has no preimage resistance, the combo SHA3+Ident has very poor preimage resistance too.

This thread has relevant info: https://crypto.stackexchange.com/questions/270/guarding-agai...

I still don't understand what you're claiming is wrong with XOR. As I understand it, the XOR of two secure hashes should be at least as strong as each one. Of course you can find ways to deliberately come up with a broken scheme if you really want to do something spectacularly dumb (like XORing a variation of the same algorithm with itself...), at which point the problem isn't really XOR, but assuming you're being reasonable and showing some sense in the process, the likelihood of someone somehow finding an exploitable correlation between them without breaking either one should be astronomically small to not even warrant a second thought.

Just as a mental exercise (im no expert) how about. GoodHash=HF(input) + HF(reversed-input) Your final hash value will still be twice as bjg yes, but reversing the input should yield a different result ? This is of course for non-crypto usage.

By "in parallel" I don't mean XOR. I mean concatenation. So in my example sha256+md5 would concatenate sha256's 256 bit digest, and md5's 128 bit digest, to form a 384 bit digest.

The intuitive explanation for why XOR instead of concatenation doesn't work, is it lets the output of the broken hash function influence the output of the remaining good hash function. That is obviously cause for concern!

> The intuitive explanation for why XOR instead of concatenation doesn't work, is it lets the output of the broken hash function influence the output of the remaining good hash function. That is obviously cause for concern!

The bits of a good hash function should be random. XORing with some unrelated-ish thing should be no problem. So that's not enough of an explanation.

> Suppose you used SHA256(MD5(x)) as your sequential hashing function.

SHA256(concat(MD5(x), x)) would be significantly more effective at the possible expense of performance.

Of course I’m sure that if you’re willing to make a performance trade-off there’s going to be a better single hashing algorithm out there.

Everything 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

> 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.

Hashing 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 :)

There are some here: https://en.m.wikipedia.org/wiki/Security_of_cryptographic_ha...

But, it does say practically provable

>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.

Well, 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)

At 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

If 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.

> 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.

> 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.)

Depends 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.

The 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.

You'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!

I didn't mean "variable" when I said "anything". I was saying it didn't matter. Variable length would be valid, but so is a fixed 200 bit output.

The main thing I wanted to express is that "provably secure" doesn't mean no collisions.

Ya, 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.

Reply on news.ycombinator.com