4 ms·
Can we have a hash function that is theoretically secure, rather than just "we shuffled a bunch of bits, and nobody yet knows how to unshuffle them, but in 20 y
by londons_explore 5y ago
Can we have a hash function that is theoretically secure, rather than just "we shuffled a bunch of bits, and nobody yet knows how to unshuffle them, but in 20 years someone might discover how to"?
For example, encrypting the data with a public key where nobody knows the private key ought to do the job, for example, public key=pi. Then use the encrypted data as the 'hash' (or some shortened version of it by discarding bits).
Yes, I know it would be slower, but it might be better to pay the performance cost than to have to move everything to a new algorithm every 20 years.
- capableweb 5y ago> Yes, I know it would be slower, but it might be better to pay the performance cost than to have to move everything to a new algorithm every 20 years. What if your way reveals to be insecure as well in 20 years? Who knows what will happen in that time-frame, it's a long time in our interconnected world. What if instead of trying to find something that works forever, you embrace change and make it easy to change the algorithm instead? So when you need to change in the future (not "if"), you can easily just switch a value to change to the new one. Have solid testing created already for. Don't assume invariants that changes between the different hash functions, like length or what bytes there will be in them.
- TillE 5y agoWhat's different about encryption algorithms that make them not fundamentally "shuffling a bunch of bits"? Anyway, BLAKE is based on ChaCha.
- ogogmad 5y agoThere's this (called SWIFFT): https://en.wikipedia.org/wiki/SWIFFT#:~:text=In%20cryptography%2C%20SWIFFT%20is%20a,the%20LLL%20basis%20reduction%20algorithm https://en.wikipedia.org/wiki/SWIFFT#:~:text=In%20cryptograp.... There are also trivial constructions that exploit the difficulty of Discrete Log. But they are slow. You do have to be careful when using these hash functions, because they satisfy potentially undesirable properties like H(a + b) = H(a) + H(b), which make them unusable as random oracles. There haven't appeared any cracks in SHA2 for the nearly two decades in which it's existed. So unless it's possible to have a sudden and totally inexplicable break, we'll probably be safe for many decades hence.
- acchow 5y ago> Can we have a hash function that is theoretically secure, rather than just [...] and nobody yet knows how > For example, encrypting the data with a public key where nobody knows the private key ought to do the job Errr... public key cryptography is only "theoretically secure" because we assume "nobody yet knows how..." to solve some hard problems like prime factoring, discrete log, etc.
- poizan42 5y agoIf you can compute a hash in polynomial time then you can also verify a potentiel pre-image (i.e. input) in polynomial time, which puts the problem of finding a pre-image in NP. Hence proving pre-image attack resistency would imply P!=NP unless computing the hash itself can't be done in polynomial time. So for the time being the answer is no, we can't have a hash function that is theoretically secure. Your suggestion just moves the problem onto proving that the public key cryptography is secure, which suffers from the same problem.
- contravariant 5y agoTechnically the time is constant since some finite set of inputs is enough to generate all hashes. At the very least we'll need to be careful with respect to what the time is 'polynomial'. For what it's worth I see no reason you couldn't identify some NP-hard problem for which the original input is the solution. This means that reversing the hash directly is out of the question, but this only works if you the way you generate the NP-hard problem is itself difficult (or ideally random) enough that it can't be reverted. Sounds like a lot of effort, but who knows, it might be worth the effort in some cases.
- CaptainNegative 5y agoThe difficult part of basing a one-way function around NP-hardness isn't so much the reduction itself as it is the ability to sample from the "hard core" core the distribution. For example, say you base the hardness of your OWF on the NP-hard problem of finding a Hamiltonian Cycle in an n-node graph. Your reduction could be completely valid and sound, meaning that pre-imaging your function would require solving an NP-hard problem. But, maybe suprisingly, HamCycle is actually extraordinarily easy for an overwhelming majority of n-node graphs. This is the result of a phase transition that happens when the degree of a random graph passes O(log n) or so, where suddenly the probability of such a graph having a HamCycle becomes 1-o(1) > 0.999999 for n sufficiently large, and a simple greedy algorithm can find them (ref. Pósa '76). And most graphs have average degree closer to n/2 than log(n), meaning that finding a HamCycle is trivial. The crux, finally, is that basing your problem on an overwhelmingly trivial problem, even if technically NP-hard, is still not going to work for security. It will be little consolation that perhaps one customer's account was not broken into when the other hundred million accounts were cracked in milliseconds. A solution to this problem would require researchers to find an NP-hard problem that is hard on average when sampled from an efficiently-sampleable distribution (plus a couple other techcnical caveats). Whether or not there is a good way to do that, for any NP-hard problem, is still mostly a major open question, and not for lack of trying.
- tptacek 5y agoIt would be slower but it would also likely be less secure. Hashes are (roughly) based on a block cipher cryptography, which is arguably a more straightforward research project --- the rate of practical advancements on (say) finite field dlog cryptography is scarier than that of (say) new applications of differential cryptanalysis on block cipher cores. Hashes have kind of a bad rap because we happened to get a whole string of 1990s-vintage hash functions that survived into the 2010s. AES had mostly just DES-EDE to replace. You can find somewhere a tweet from JP Aumasson, one of the Blake/Blake2/Blake3 authors, suggesting that we might never break SHA-2. SHA1 had a low (again: 1990s) security margin (2^80 collision resistance), among other problems (notably: susceptibility to differential cryptanalysis). (It's also possible that I've said something dumb enough that one of the other Blake authors will smack me down and improve the thread). The reasons for looking at SHA3 and Blake2 or Blake3 don't have that much to do with security, as much as they have to do with speed and flexibility.
- wolf550e 5y agoI think this is the twitter thread: https://twitter.com/realhashbreaker/status/1128276207718600704 https://twitter.com/realhashbreaker/status/11282762077186007...
- pvg 5y agoMore directly and earlier, and, amusingly, a reply to tptacek is: https://twitter.com/veorq/status/834872988445065218 https://twitter.com/veorq/status/834872988445065218 The line of thinking is more fully (if less sha2-specifically) covered in Aumasson's 'Too much crypto' paper, which has also had HN discussions.