Can a hashing function be implemented insecurely?

Question

After working on a an imaginary security related project, it was decided that the project is going to use the imaginary hashing function X.

There are various implementations of the hashing function available as packages, all varying in terms of adoption rates and popularity.

Given that any package returns correct hashes for a small amount (n=10) of test cases, are there any serious security implications that could occur? My understanding is that a hashing function should return a irreversible value, and given that any implementation does this correctly, they should all be equally working & therefore secure.

Right?

To clarify: are you assuming that the hashing function itself is secure (to the best of current knowledge) and you are asking whether there can be an "insecure" implementation of that function? Something along the lines of how insecure implementation of a decryption algorithm can leak information about the correctness of the key through timing attacks? — TripeHound, Jun 28 '19 at 11:14
@TripeHound Yes, I assume that the hashing _algorithm_ is deemed secure. I want to know what security implications could be present in an implementation that yields correct results on a limited amount of test cases. — NikxDa, Jun 28 '19 at 11:33

score 5 · Accepted Answer · edited Jun 16 '20 at 09:49

Unlikely

First of all, the implementation of a hashing function could be faulty in terms of software engineering. That doesn't mean the implementation is insecure per se, but means that you are not returning the expected values according to the specifications.

N=10 test cases is a ridiculously ridiculous amount of testing to certify that a hashing function is ready for production. I am currently speaking about software engineering, not yet security

A concrete example

sha256("Hello Stack") equals 433247cccfd4105b7b60e810e372f3850ba4e518eb5fb0474e198228ddaabf65

Wherever in the world you are, that is the universal hash of that string. The security properties of sha256 are defined in the hash's specification.

If you have a faulty implementation, then it will have to return something necessarily different.

Now suppose for a second your sha256 does the following

yourSha256("Help Stack") equals 433247cccad4105b7b60e810e372f3850ba4e508eb5fb0474e198228ddaabf65

That's basically not sha256, because the correct value is 74aec9297f627396b3914f1a58213dada3ec30b0ed0cc5dafb029d0f326e2ec7

What I am saying is that in the world of hash functions, the properties of uniqueness and randomization have to be demonstrated at specification level, and they apply to the hash's specification. Any code that returns value other than the expected hash is not a correct implementation of the hash.

A bug comparing the hashes

So you have function H(x) that is deemed secure. I won't discuss further. Then you have two implementations org.acme.H (yours) and com.initech.H (another vendor's). You must integrate two systems so that they compute and exchange hashes.

H is secure by definition, but Acme is faulty. That means on the 11th test case it is returning results different than Initech. That will mean whatever interaction between the systems will be inconsistent and/or failing. e.g. the two system use such hash to checksum a file, but since they yield different values they consider the file out of date.

So far, that's not a mere security problem

Exploitable faulty implementation

If you rely on that hash heavily and use it for security purposes, and have no other implementation from any other vendor, you might have vulnerabilities.

E.g. if your faulty hash code starts to return predictable values, an attacker can discover (part of) the plaintext after a number of similar-text attacks.

That is not a problem with the hash definition, but it's the binary code not returning the correct value. Simply because you are not using secure H(x), you are using trash(x) where trash is a brand new weak function.

Other considerations

Cryptographic functions are famous for timing attacks, where the amount of time to encrypt a block (emphasis mine) is variable and reveals info about the key. Hashing functions have the desirable property to take the same amount of time for blocks of equal length. It is worth to note that it is perfectly normal for a hash function to take increasingly time according to the payload size. Namely, the larger the file, the longer the time to hash it. Full stop!

Memory aging and leaked plaintext

I could imagine that a faulty implementation leaves traces of the original plaintext allocated in memory, without properly clearing these areas and returning them to the system. Combined with a buffer overflow attack, that could reveal pieces of plain text if not all.

But that is something unrelated to only 10 test cases. You won't find it with additional cases like assertThat(h(x),is(equalTo(precomputed))) or assertThat(acmeHash(x),is(equalTo(superTestedHash(x)))) which is a great way to test custom implementations

Consideration on timing attack

This is just a consideration. Suppose your correct-but-insecure-implementation of the hash yields a result so that the time it takes to yield it is related to the plaintext itself.

I quite don't see much security issue. Hash functions are public, so that you will run it on your machine. You have to know the plaintext before running it.

Compared to time attacks in crypto functions, the problem there is that you use the timing not to break the cyphertext or plaintext, but to break the key which is the other secret element. In hashing there is no key, so plaintext and hash digest are always known.

Thanks for this, it is exactly what I was looking for. Apart from possible memory leaks, are there other such cases where an implementation can have security issues even though it is returning a correct value? — NikxDa, Jun 28 '19 at 12:06
I additionally want to point out that by `n=10`, I do not mean 10 hash test cases overall - I mean 10 custom tests to verify that 10 random inputs yield the expected hashes, not necessarily any algorithm-related tests. The probability of an algorithm returning correct results for 10 random inputs but failing on the 11th random input should be rather small, no? — NikxDa, Jun 28 '19 at 12:10
You really need billions of cases. Could you turn some software switch so that the 10 random inputs become 1 trillion inputs? — usr-local-ΕΨΗΕΛΩΝ, Jun 28 '19 at 12:14
In that case I would need to rely on another implementation to verify results. How would one go about making sure that any hashing algorithm is implemented correctly without writing those proposed billions of tests or relying on a different implementation? — NikxDa, Jun 28 '19 at 12:18
I have amended my answer with a consideration on a time attack. About relying on another implementation, I won't answer for now. As a SW engineer I can tell that IETF protocol standards explicitly require multiple implementations to be tested against each other (https://www.ietf.org/how/runningcode/implementation-reports/). Maybe you (both of us) should post on Stackoverflow "how did the authors of crypto functions verify that their code yields the correct values?" — usr-local-ΕΨΗΕΛΩΝ, Jun 28 '19 at 12:21

score 1 · Answer 2 · answered Jun 28 '19 at 11:59

1

It doesn't matter what library / package you use as long as they all work the same way (meaning they all indeed return the same hash value for an identical input). Using for example a crypto library in C# or a crypto package in Java, both creating SHA2 hashes, are ultimately identical because they return the same value for any given input and are thus secure.

A bad implementation of a hash function would be if you manually change some constants. See this question about changing hash functions for more information. That would basically be the same as creating a new hash function that hasn't been tested for it's security.

answered Jun 28 '19 at 11:59

AleksanderCH

711
3
10
23

1

Thanks for pointing this out, but that was not my question. I am looking for possible insecurities in an implementation that returns a verifiably correct result on a small set of random test cases. – NikxDa Jun 28 '19 at 12:03
1

My bad, then have a look at the answer from usr-local-ΕΨΗΕΛΩΝ. As answered, a secure hash algorithm should be rigorously tested and a set of only 10 test cases is way too small. – AleksanderCH Jun 28 '19 at 12:06

score 1 · Answer 3 · answered Jun 28 '19 at 18:36

There is no generic answer because you have not detailed the scenario. In particular, this distinction is relevant:

Scenarios where the hash function input is public (i.e., the attacker is assumed to know it).
Scenarios where the hash function input is secret (i.e., not supposed to be known to attackers)

Public input scenarios are, e.g., public key signatures, where the input to the hash function is a document that is given in the clear to the parties along with the signature. In these scenarios it's hard not to agree with your rough assessment:

My understanding is that a hashing function should return a irreversible value, and given that any implementation does this correctly, they should all be equally working & therefore secure.

...with the proviso that "irreversible" here isn't a useful characterization, and instead we should refer to the cryptographic hash function property trio: preimage resistance, second preimage resistance, collision resistance.

Secret input scenarios are those where at least some part of the hash function input is secret; e.g., when the hash function is used in the HMAC construction as a symmetric message authentication code (MAC). Here one does generically have to worry about various sorts of side-channel attack, like:

Timing attack: If the adversary can choose the non-secret parts of the hash function input and precisely measure how long it takes for the function to return, can they make any good inferences about the secret part of the input? The mitigation is constant-time implementations—implementing the algorithm so that the runtime variation doesn't depend on the value of the input (except possibly its length).
Power attack: Attacks have been demonstrated where secrets are inferred from measuring small fluctuations in how much electricity a cryptographic device consumes.
etc.