6
$\begingroup$

Using MD5 or SHA1 for instance, and applying integers (as seed so to speak) to the hash function, in sequence, and only keeping, say, the first 64 bits of the resulting hash, do we always have a probability close to $1/{2^{64}}$ to have $$\text{hash}_{64}(n) = \text{hash}_{64}(n+1)$$ for every $n\in\big[1,2^{64}]$?

$\endgroup$
6
$\begingroup$

What you are talking about is a counter based algorithm and the integer is then of course called the counter. Usually it is first encoded to a statically sized encoding of the number, as hash functions operate on bits / bytes, not numbers.

Yes, these kind of constructions are considered secure, if the other requirements are met. For instance, you should seed your algorithm correctly. Instead of defining a hash based DRBG of your own, you probably want to use a known good implementation such as Hash_DRBG as defined by NIST.

You should also try and stay away from broken hash functions such as MD5 and SHA-1. Although they are not broken for this purpose, attacks only get better, never worse.

| improve this answer | |
$\endgroup$
  • $\begingroup$ No, numbers can be represented as (or in) bits or bytes - but that's not equivalence; you can have numbers without bits or bytes. There is no such thing as "the input of the hash function" other than that the number in your scheme needs to be encoded in some fashion that is unique. This scheme would work equally well for bits encoded using any static size or a dynamic size (unsigned, big endian, for instance) as long as the entire bit stream is unique for each number... $\endgroup$ – Maarten Bodewes Dec 9 '19 at 18:09
  • $\begingroup$ SHA1 is broken? Could you tell me how, and give some examples of hash functions that aren't? $\endgroup$ – Jez Jun 8 at 9:02
  • $\begingroup$ @Jez Lookup SHAttered. By the way, that's just an example of an enhanced attack, it has been officially broken since 2005 (that is: it doesn't meet it's security goals anymore, regardless of practical attacks since 2005). Neither SHA-2 (SHA-256 / 512) nor SHA-3 are considered broken. SHA-256 is similar to SHA-1 but with much more complicated rounds, and SHA-3 is a sponge construction, which is a rather different concept than a Merke-Damgard hash. $\endgroup$ – Maarten Bodewes Jun 8 at 16:36
3
$\begingroup$

Caveat: that answer is written with my mind in Vulcan mode. That is, I'm answering the question as taken literally (in the first part); or in only a minor variant (second part); and ignoring the question's title, which I find unrelated, especially given the limited span of $n$.

The probability considered is $0$ for each of the many different common ways to define $\text{hash}_{64}(n)$ as the first 64 bits of the MD5 or SHA-1 of integer $n$. Whether $0$ is "close to $1/2^{64}$" is a matter of opinion.

For a few other definitions of $\text{hash}_{64}(n)$, that probability is $1$, which is not "close to $1/2^{64}$" by many accounts.

Justification: it is considered the probability $p$ that for every $n$ in $\big[1,2^{64}\big]$ it holds $\text{hash}_{64}(n)=\text{hash}_{64}(n+1)$.

For fixed function $\text{hash}_{64}$ this is a probability that a certain determined fact holds or not, and thus $p$ is either $0$ or $1$ depending on the function $\text{hash}_{64}$. This also holds (perhaps with a different $p$) if we change every to some.

For the many different common ways to define the function $\text{hash}_{64}$ for an integer parameter as the first 64 bits of the MD5 or SHA-1 of that integer, that probability is $0$. For example, if we define $\text{hash}_{64}$ to be the first 64 bits of the SHA-1 of the shortest big-endian decimal representation of $n$ encoded in ASCII, then $\text{hash}_{64}(1)$ is the SHA-1 of the single byte 0x31 and starts with a $0$ bit, while $\text{hash}_{64}(2)$ is the SHA-1 of the single byte 0x32 and starts with a $1$ bit, thus they do not match.

We could try with MD5 and SHA-1, various common bases (including 2, 8, 10, 16, 64, 256, 232), common suitable alphabets (ASCII, EBCDIC, binary, bytes) and common variants (uppercase or lowercase hex, various base64 idioms), endianness (big, little, various mixed), and width for $n$ (fixed to say 64 with some exception for $n=2^{64}$, 65, 72 or 96 bits, adaptive according to $n$ with various steps like even which is common with hex). But I'm not convinced that we would find any such $\text{hash}_{64}$ with $\text{hash}_{64}(1)=\text{hash}_{64}(2)$. And I'm ready to bet the house $\text{hash}_{64}(2)=\text{hash}_{64}(3)$ won't hold in addition.

When we average the probability asked over all the possible definitions of $\text{hash}_{64}$, we get $2^{\left(64-2^{70}\right)}$. That ludicrously small number is much less than $1/2^{64}$, yet still closer to $1/2^{64}$ than $0$ is.


Now perhaps we should instead consider the probability $p$ that for a random $n$ in $\big[1,2^{64}\big]$ it holds $\text{hash}_{64}(n)=\text{hash}_{64}(n+1)$.

That probability $p$ is $k/{2^{64}}$ for some integer $k$, which can be computed with significant but feasible effort from the exact definition of $\text{hash}_{64}$.

When we average $p$ over all the possible definitions of $\text{hash}_{64}$, we get $1/2^{64}$; thus "close to $1/2^{64}$" for sure.

We can also define the probability $p_k$ that $p$ is $k/{2^{64}}$ for a random function $\text{hash}_{64}$, which is a plausible model for the various $\text{hash}_{64}$ that the question considers. The largest $p_k$ is $p_1$ (meaning $p=1/{2^{64}}$ is the most likely), with $p_0$ extremely close second, both extremely close to $1/e\approx36.8\%$. $p_2$ is about half that, and $p_k$ goes down fast as $k$ grows, down to $p_{2^{64}}=2^{\left(-2^{70}\right)}$, then $p_k=0$ for $k>2^{64}$. It holds $1=\sum p_k$.

We see that $p$ is in the 3-element set $\{0,1/2^{64},1/2^{63}\}$ with probability about $5/2e\approx92.0\%$. We can say $p$ is very often "close to $1/2^{64}$".

| improve this answer | |
$\endgroup$
  • $\begingroup$ If the hash is a RO then the probability must be $1/2^{64}$ for any subsequent to equal. $\endgroup$ – kelalaka Jan 31 '19 at 17:56
  • $\begingroup$ @kelalaka: I do not get "for any subsequent to equal". $\endgroup$ – fgrieu Jan 31 '19 at 23:39
  • 3
    $\begingroup$ @fgrieu For any subsequent [64-bit block] to [be] equal. $\endgroup$ – Future Security Feb 1 '19 at 16:23

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.