4 ms·

So what are the next steps for cryptographic hash functions? Is it going to just be "make even faster" ? Or are we chasing new properties, or stronger guarantee

So what are the next steps for cryptographic hash functions? Is it going to just be "make even faster" ? Or are we chasing new properties, or stronger guarantees (or hopes?) of existing properties?

ogogmad 5y ago
Not an expert, but it would be nice to provide security proofs. Not a must-have thing, perhaps, but certainly nice to have. One such example of a "provably secure" hash function is this one: 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.... Unfortunately, it's quite slow, and can't be used as a "random oracle". A lot of security proofs assume the random oracle model (but not for hash functions though, which are supposed to implement the "random oracle"). Strictly speaking, the model is incorrect, because a hash function is never a random oracle. I don't know if a suitable substitute has been found.
tptacek 5y ago
Variants of "make even faster" (including "making keys smaller" or "allow to run on more limited hardware") is most of what drives new core cryptographic primitives. There's a tweet from one of the BLAKE authors (@veorq) saying what I think a bunch of cryptography engineers believe, that it's unlikely that SHA2 will ever be directly broken. There are security improvements in new primitives, often based on a notion of "misuse-resistance". SHA2 isn't broken; it remains quite strong. But it's a classic Merkle Damgard design, which means you can take the output of SHA2 and hash more data into it, which breaks simple keyed hash constructions like H(k, m) (this is why we have HMAC!). SHA3 and other modern hashes don't have this property; you can safely build simple keyed hash constructions out of them. You can see the same thing with AEADs (the SIVs vs. GCM) and with curves (Curve25519, for instance, where keys are --- don't @ me --- just simple random byte strings).
- cesarb 5y ago
  > Curve25519, for instance, where keys are --- don't @ me --- just simple random byte strings IIRC, just simple random byte strings with a couple of specific bits forced to 0 and another couple of specific bits forced to 1.
  - tptacek 5y ago
    Don't @ me! :)
- ogogmad 5y ago
  > you can take the output of SHA2 and hash more data into it Isn't this problem fixed by simply dropping some bits from the end? See SHA-224 for instance.
  - tptacek 5y ago
    Yes, though in a MAC construction, you'd just use HMAC anyways. People still use HMAC with SHA3, even though it's unnecessary, and I don't see anything wrong with that either.
- pbsd 5y ago
  There is also more/different functionality (e.g., designing a permutation or a tweakable blockcipher instead of a plain blockcipher, or a hash based on those), or better analyzability---making primitives that are simpler to "prove" (or make an argument for) secure against some classes of attacks. And these days there are also the primitives purposefully designed to run in blockchain....whatever it is, using large GF(p) or GF(2^n) field operations as components. This mostly falls under the "more limited hardware" umbrella.
infogulch 5y ago
An associative / non-commutative hash function over lists. This would mean that the hash of a list, H(list1), could be "concatenated" with another hash, H(list2), to find the hash of the concatenation and be equivalent to H(list1+list2). I think such a construction could be huge for cryptographic verification of data in data structures while avoiding baking in incidental details about the data structure itself. I hesitate to link to it because I already know of a potential attack, but I played around with an implementation that does this with matrix multiplication over galois field elements of reinterpreted hash digests [1]. I mean, the associative / non-commutative part works nicely, but I expect that factoring the matrix is possible which makes it utterly useless as a cryptographic primitive [2]. "don't roll your own crypto" would apply, but I'm obviously not using such an academic exercise in production. [1]: https://blog.infogulch.com/2021/07/15/Merklist-GF.html https://blog.infogulch.com/2021/07/15/Merklist-GF.html [2]: https://math.stackexchange.com/questions/4200988/using-random-invertible-matrices-over-finite-fields-to-define-the-hash-of-a-list?noredirect=1#comment8720609_4200988 https://math.stackexchange.com/questions/4200988/using-rando...
- andyferris 5y ago
  I agree - such a thing would be really, really useful!
- kragen 5y ago
  This is super interesting, thanks! I just wrote a related note in http://canonical.org/~kragen/dernocua.git http://canonical.org/~kragen/dernocua.git in text/hash-consing-ropes.md, linking to those two notes; my interest is using it for hash consing, like symbol interning but for all your strings.
  - infogulch 5y ago
    Something that might interest you even more is the related questions by Jason Hise that I linked to. They explored using 8x8 bit-element matrices as an associative hash of a string and apparently it works pretty good as a hash for string keys in a hashmap. Both questions, answers, and comments all have some interesting context, and Jason answers some questions I had about their usage in comments on the second question. Using 8x8 Binary Matrices as a hash - https://math.stackexchange.com/questions/1902462/using-8x8-binary-matrices-as-a-hash https://math.stackexchange.com/questions/1902462/using-8x8-b... Finding Prime Binary Matrices - https://math.stackexchange.com/questions/1914853/finding-prime-binary-matrices https://math.stackexchange.com/questions/1914853/finding-pri...

So what are the next steps for cryptographic hash functions? Is it going to just be "make even faster" ? Or are we chasing new properties, or stronger guarantees (or hopes?) of existing properties?

ogogmad 5y ago

Not an expert, but it would be nice to provide security proofs. Not a must-have thing, perhaps, but certainly nice to have. One such example of a "provably secure" hash function is this one: 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.... Unfortunately, it's quite slow, and can't be used as a "random oracle". A lot of security proofs assume the random oracle model (but not for hash functions though, which are supposed to implement the "random oracle"). Strictly speaking, the model is incorrect, because a hash function is never a random oracle. I don't know if a suitable substitute has been found.

tptacek 5y ago

Variants of "make even faster" (including "making keys smaller" or "allow to run on more limited hardware") is most of what drives new core cryptographic primitives. There's a tweet from one of the BLAKE authors (@veorq) saying what I think a bunch of cryptography engineers believe, that it's unlikely that SHA2 will ever be directly broken. There are security improvements in new primitives, often based on a notion of "misuse-resistance". SHA2 isn't broken; it remains quite strong. But it's a classic Merkle Damgard design, which means you can take the output of SHA2 and hash more data into it, which breaks simple keyed hash constructions like H(k, m) (this is why we have HMAC!). SHA3 and other modern hashes don't have this property; you can safely build simple keyed hash constructions out of them. You can see the same thing with AEADs (the SIVs vs. GCM) and with curves (Curve25519, for instance, where keys are --- don't @ me --- just simple random byte strings).

cesarb 5y ago
> Curve25519, for instance, where keys are --- don't @ me --- just simple random byte strings IIRC, just simple random byte strings with a couple of specific bits forced to 0 and another couple of specific bits forced to 1.
- tptacek 5y ago
  Don't @ me! :)
ogogmad 5y ago
> you can take the output of SHA2 and hash more data into it Isn't this problem fixed by simply dropping some bits from the end? See SHA-224 for instance.
- tptacek 5y ago
  Yes, though in a MAC construction, you'd just use HMAC anyways. People still use HMAC with SHA3, even though it's unnecessary, and I don't see anything wrong with that either.
pbsd 5y ago
There is also more/different functionality (e.g., designing a permutation or a tweakable blockcipher instead of a plain blockcipher, or a hash based on those), or better analyzability---making primitives that are simpler to "prove" (or make an argument for) secure against some classes of attacks. And these days there are also the primitives purposefully designed to run in blockchain....whatever it is, using large GF(p) or GF(2^n) field operations as components. This mostly falls under the "more limited hardware" umbrella.

infogulch 5y ago

An associative / non-commutative hash function over lists. This would mean that the hash of a list, H(list1), could be "concatenated" with another hash, H(list2), to find the hash of the concatenation and be equivalent to H(list1+list2). I think such a construction could be huge for cryptographic verification of data in data structures while avoiding baking in incidental details about the data structure itself. I hesitate to link to it because I already know of a potential attack, but I played around with an implementation that does this with matrix multiplication over galois field elements of reinterpreted hash digests [1]. I mean, the associative / non-commutative part works nicely, but I expect that factoring the matrix is possible which makes it utterly useless as a cryptographic primitive [2]. "don't roll your own crypto" would apply, but I'm obviously not using such an academic exercise in production. [1]: https://blog.infogulch.com/2021/07/15/Merklist-GF.html https://blog.infogulch.com/2021/07/15/Merklist-GF.html [2]: https://math.stackexchange.com/questions/4200988/using-random-invertible-matrices-over-finite-fields-to-define-the-hash-of-a-list?noredirect=1#comment8720609_4200988 https://math.stackexchange.com/questions/4200988/using-rando...

andyferris 5y ago
I agree - such a thing would be really, really useful!
kragen 5y ago
This is super interesting, thanks! I just wrote a related note in http://canonical.org/~kragen/dernocua.git http://canonical.org/~kragen/dernocua.git in text/hash-consing-ropes.md, linking to those two notes; my interest is using it for hash consing, like symbol interning but for all your strings.
- infogulch 5y ago
  Something that might interest you even more is the related questions by Jason Hise that I linked to. They explored using 8x8 bit-element matrices as an associative hash of a string and apparently it works pretty good as a hash for string keys in a hashmap. Both questions, answers, and comments all have some interesting context, and Jason answers some questions I had about their usage in comments on the second question. Using 8x8 Binary Matrices as a hash - https://math.stackexchange.com/questions/1902462/using-8x8-binary-matrices-as-a-hash https://math.stackexchange.com/questions/1902462/using-8x8-b... Finding Prime Binary Matrices - https://math.stackexchange.com/questions/1914853/finding-prime-binary-matrices https://math.stackexchange.com/questions/1914853/finding-pri...