0
$\begingroup$

Every now and then, we read that some hashing function has been weakened or broken, but we almost never hear this for asymmetric cryptosystems like RSA or ECC. That's because while asymmetric encryption uses mathematical impossibilities (discrete logarithm or prime factorization computation in polynomial time), hashing functions obfuscate their working by complexification, but it seems impossible to make a collision-free hashing function (that is, there is no algorithm to find collisions faster than bruteforce). Symmetric encryption is in the same case than hashing functions, because these algorithms (like DES) seem to have a shorter lifetime than RSA for example, which has been used for more than 40 years.

My assumption is that there is a difference of nature (and not degree) between on the one hand asymmetric encryption (that isn't vulnerable to cryptanalysis) and on the other hand hashing and symmetric encryption (that are vulnerable to cryptanalysis).

But can we use asymmetric encryption to create a collision-free hashing function? To hash some content, we would encrypt it using a public key that everyone would know (something easy to remember, 55555555 for example), but no one would know the correponding private key. But the result would be of variable length, so to reduce it to a fixed size we would hash it using another hash function. We can use an unsafe hash function, like MD5 for example, in fact it is just the compression feature of the hash function that we want to use here. It is a bit reminiscent of digital signatures, but the other way around. So to summarize, the hashing function would do this:

input —(RSA)—> cyphertext —(MD5)—> hash (128 bits)
         ↑
 key: 55555555

Would such a hashing function be really safe and collision-free?

$\endgroup$
  • 2
    $\begingroup$ Yes, there are (academic) collision-resistant hash functions that reduce collision resistance to the hardness of the underlying problem (like discrete log), but because they're so insanely slow while giving little practical security benefit we don't use them. $\endgroup$ – SEJPM Oct 30 at 13:09
  • $\begingroup$ Can you give the name of some of those hash functions please? $\endgroup$ – JacopoStanchi Oct 30 at 13:12
  • $\begingroup$ ECOH (Elliptic Curve Only Hash) is one of these. It was one of the SHA-3 candidates. Unfortunately, a preimage attack was quickly found. $\endgroup$ – Frank Denis Oct 30 at 13:16
  • $\begingroup$ How could a preimage attack be found if it's supposed to be collision-free? $\endgroup$ – JacopoStanchi Oct 30 at 13:24
  • 5
    $\begingroup$ "Every now and then, we read that some hashing function has been weakened or broken,"; have you heard this about one of the SHA-2 or SHA-3 hashes? "we almost never hear this for asymmetric cryptosystems like RSA or ECC"; it seems to me that the recommended key size for RSA has been creeping up; in addition, I do remember hearing some results against some pairing-friendly elliptic curves... $\endgroup$ – poncho Oct 30 at 13:29
5
$\begingroup$

Short answer: You could do this, but (a) it would be dramatically more expensive, (b) it would not improve security in the way you think it would, and (c) it would by design have back doors.


Every now and then, we read that some hashing function has been weakened or broken, but we almost never hear this for asymmetric cryptosystems like RSA or ECC. That's because while asymmetric encryption uses mathematical impossibilities (discrete logarithm or prime factorization computation in polynomial time), hashing functions obfuscate their working by complexification, but it seems impossible to make a collision-free hashing function (that is, there is no algorithm to find collisions faster than bruteforce). Symmetric encryption is in the same case than hashing functions, because these algorithms (like DES) seem to have a shorter lifetime than RSA for example, which has been used for more than 40 years.

My assumption is that there is a difference of nature (and not degree) between on the one hand asymmetric encryption (that isn't vulnerable to cryptanalysis) and on the other hand hashing and symmetric encryption (that are vulnerable to cryptanalysis).

On the contrary, quite the reverse is true. This notion is a red herring, even if this is a common trope (or perhaps, a common tripe?).

Public-key cryptosystems are designed out of rich mathematical theories that are rife with exploitable relations. This is necessary for them to have separate public keys and private keys—the private key, in some sense, is a back door. But it also exposes them to a rich theory of vulnerabilities, and tends to make them very expensive to compute.

The first RSA challenge published by Martin Gardner in his August 1977 Mathematical Games column in Scientific American (sorry, I don't have a paywall-free link!) with a 125-digit semiprime was estimated to take over 40 quadrillion years to solve, yet was solved in 1994 (paywall-free)—coincidentally revealing my name. The RSA proposal published in 1978 (paywall-free), considering 40 quadrillion years not enough, recommended 200-digit semiprimes out of an abundance of caution—that is, about 664 bits. The RSA-200 challenge was broken in 2005 (archived), fifteen years ago, only 27 years after the 1978 RSA paper.

Why did this happen? It's not because silicon technology sped up by a factor of over a quadrillion. It's because factoring is full of mathematical relations that turn out to be helpful, and we had tremendous mathematical advances—first with the quadratic sieve, and then with the special number field sieve, and then with the general number field sieve. These mathematical advances reduced a 40-quadrillion-year computation into a few bucks on Amazon EC2.

(There's a similar story of dramatic breakthroughs for many classes of elliptic curves, and for newer pairing-based designs that have an even richer mathematical structure, but I'll leave that story to Koblitz, Koblitz, & Menezes who tell it better. Some parts of the ECC story seem to have stabilized, but there's plenty more rich mathematical theory to explore.)

Symmetric cryptography tends to be much easier to make secure. For comparison, we might take a look at DES, which was developed around the same time. Martin Hellman predicted in 1979 that DES would be totally insecure within ten years (paywall-free). Sure enough, within a mere nineteen years (off by less than a factor of two, rather than off by a factor of a quadrillion!), EFF's Deep Crack performed a brute force key search to recover a DES challenge key. Today, again, it's a few bucks on Amazon EC2. Meanwhile, cryptanalytic advances against DES have been quite modest—especially in comparison to RSA, and the ratio is even starker if you take into account the cost to compute DES and the cost to compute RSA for the legitimate user.

Today, we have a plethora of symmetric ciphers and preimage-resistant hash functions have withstood scrutiny for decades with essentially no serious cryptanalytic advances against them. The reason ‘RSA’ persists today is that it is actually a family of cryptosystems that can be scaled up to defend against cryptanalytic advances: we no longer use 512-bit RSA keys; we use 2048-bit RSA keys today—and we're getting nervous about those. But there's only one DES—so we replaced it by AES to raise the generic security, reduce the cost, and address the mild cryptanalytic advances against DES.

What about collision resistance? Generally, collision resistance seems harder to achieve—and costlier to compute—than preimage resistance, or pseudorandomness. The hash functions MD4, MD5, SHA-0, SHA-1, RIPEMD, and HAVAL-128 originally advertised with collision resistance have all been broken. But many of them share common design elements—MD4, MD5, SHA-0, and SHA-1 in particular—which is why we all got really nervous in the mid-2000s about SHA-2 (which shares the design elements) and NIST launched the SHA-3 competition to choose a very different design in case SHA-2 should fall.

But since then, the story seems to have stabilized (archived). We now have a number of hash functions that have held up quite well for much longer than MD4, MD5, SHA-0, or SHA-1 ever did, and they've held up well enough that cryptographers are comfortable reducing the costs—the popular hash function BLAKE2 is like the SHA-3 candidate BLAKE, but cheaper; the newer KangarooTwelve is like the SHA-3 winner Keccak, but cheaper—without losing collision resistance.


‘But I wanna collision-resistant hash function built out of number theory!!’ OK, OK, here you go.

Pick an RSA modulus $n = pq$. (Make sure it is big enough to resist 1994 researchers!) Pick $g \in (\mathbb Z/n\mathbb Z)^\times$ uniformly at random. For an integer $x$, define $H_{n,g}(x) := g^x \bmod n$. (To extend this on bit strings, pad them appropriately and interpret them as integers in, say, little-endian.) Anyone who can find a collision in this can factor $n$ without much more difficulty. (Proof and references to related ideas.)

Of course, there's a back door! Anyone who knows $p$ and $q$ can trivially find collisions: $x$ collides with $x + \operatorname{lcm}(p - 1, q - 1)$. You were asking, after all, for asymmetric cryptography—which means, just like with Dual_EC_DRBG, that there's a back door!

Maybe stick with SHA-2, SHA-3, or BLAKE2?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.