-2
$\begingroup$

There are some protocols that require the user to generate some random key locally (client-side) with no server authority to "approve" or "reject" their key and are based on the assumption that it's extremely unlikely that two user will come up with the same key. Bitcoin is one of these.

What's the probability for two different users to come up with:

  1. The same randomly-generated 128-bit string.
  2. The same randomly-generated 256-bit string.
  3. The same randomly-generated 2048-bit RSA key.
  4. What's the probability that two user will have the same 128/256 bit hash of their public key, because of a hash collision?

How all compare to Bitcoin?

$\endgroup$
  • 2
    $\begingroup$ Welcome to Crypto.SE! Please dont get me wrong, but what research have you done? I'm asking because sharing research efforts helps everyone and is as simple as a minor edit to your Q where you tell us what research you did, what you found, and why it didn’t meet your needs. That shows other users you took time trying to help yourself, it saves us from reiterating obvious answers, and (most important) it helps you to get more relevant, on-point answers. At worst it will help you frame “a better question”; at best it might even answer it. $\endgroup$ – e-sushi Apr 9 '17 at 10:51
  • $\begingroup$ What you are looking for is called a "collision attack". Chances are you are not going to find a collision for any string length higher than 128 bit. $\endgroup$ – SEJPM Apr 9 '17 at 13:15
  • $\begingroup$ Collisions in random keys don't matter much, if you don't know who or for what it is used. The existence alone doesn't mean there is anyone who knows about it. $\endgroup$ – tylo Sep 26 '19 at 6:56
1
$\begingroup$

If there are $n$ people in a room, and their birthdays are independently distributed uniformly among $k = 365$ possibilities, what is the probability that at least two of them share a birthday? Call this probability $P(C; n, k)$, the collision probability among $n$ people with $k$ possible birthdays. This is the complement of the probability $P(D; n, k) = 1 - P(C; n, k)$ that their birthdays are all distinct, which is easier to compute directly:

  • If there's only one person, their birthday is always distinct, and since there are 365 possibilities each with probability $1/365$, the probability of all distinct birthdays among one person is $\frac{365}{365} = 1$ as we would hope.
  • If there's two people, no matter what the first person's birthday is, the second person has only 364 possibilities for a distinct birthday, and each one has probability $1/365$, so the probability of distinct birthdays among two people is $\frac{365}{365} \cdot \frac{364}{365}$.
  • With three people, the third person has only 363 possibilities that are distinct from the first two, so the probability of distinct birthdays among three people is $\frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365}$, etc.

In general, if there are $n$ people and $k$ possible birthdays, the probability that all the birthdays are distinct is $$P(D; n, k) = \frac{k}{k} \cdot \frac{k - 1}{k} \cdot \frac{k - 2}{k} \cdots \frac{k - n}{k}.$$ Since $\frac{k - \ell}{k} = 1 - \frac \ell k$, we can rewrite this as

\begin{equation} P(D; n, k) = \biggl(1 - \frac 1 k\biggr) \biggl(1 - \frac 2 k\biggr) \cdots \biggl(1 - \frac n k\biggr). \end{equation}

Using the handy-dandy property that $e^{-2x} \leq 1 - x \leq e^{-x}$ for any $0 \leq x \leq 1/2$ (proof), we can set a lower bound on the probability that all the birthdays are distinct as long as $n \leq k/2$:

\begin{multline} P(D; n, k) \geq e^{-2/k} e^{-4/k} e^{-6/k} \cdots e^{-2n/k} = e^{-2(1 + 2 + 3 + \cdots + n)/k} \\ = e^{-n(n - 1)/k} \geq 1 - \frac{n (n - 1)}{k} \geq 1 - \frac{n^2}{k}. \end{multline}

This sets an upper bound on the probability that there are any birthday collisions:

\begin{equation} P(C; n, k) = 1 - P(D; n, k) \leq \frac{n^2}{k}. \end{equation}

Obviously, we are really interested not in birthdays but in keys in a cryptosystem here. There are a lot of people out there, over seven billion. Let's round that up to $n = 2^{40}$, which is a large number but plausible if everyone on the planet has hundreds of keys on average, or $n = 2^{64}$, which is a very large but not unimaginable number of keys.

\begin{equation} \begin{array}{cccc} & \text{#keys, $k$} & P(C; n = 2^{40}, k) & P(C; n = 2^{64}, k) \\ \hline \text{AES-128 key} & 2^{128} & 2^{-48} & 1(?) \\ \text{secp256k1 key} & \approx2^{256} & 2^{-176} & 2^{-128} \\\ \text{RSA-2048 key}^* & \approx2^{1013} & 2^{-933} & 2^{-885} \end{array} \end{equation}

* For an RSA-2048 key, the real problem is not just a collision in the modulus but a collision in any of the prime factors. The entry here assumes two-prime RSA with 1024-bit factors, and uses the approximation $\pi(n) \approx n/\log n$ for the prime-counting function giving $\pi(2^{1024}) - \pi(2^{1023}) \approx 2^{1014} - 2^{1013} = 2^{1013}$. Extending to multiprime RSA left as an exercise for the reader.

The curious entry $1(?)$ in the line for AES-128 doesn't mean that the probability of a collision is 1—obviously that doesn't happen until $n = k$; it just means that the bound computed above isn't very tight when $n \approx \sqrt{k}$. Tighter bounds are possible, but as the number of users grows past $\sqrt{k}$, the probability of a collision rapidly increases and converges to $1$. So, except for AES-128, which you shouldn't be using anyway if you want a 128-bit security level, there is a negligible chance that two users will ever happen to choose the same keys—unless, of course, their random number generator is busted, which happens rather more often than we might hope.

What about a collision in the hashes of the keys? This is hard to know exactly for any fixed hash function like SHA-256, but we can model it by a uniform random function $f$, where $f(x)$ is an independent uniform random hash value for each distinct $x$. If the keys generated by the users are $x_1, x_2, \dots, x_n$, and assuming there are the same number of possible keys as possible hashes, what is the probability of a collision among the hashes $f(x_1), f(x_2), \dots, f(x_n)$? Consider two mutually exclusive events:

  • There is a collision among the keys $x_1, x_2, \dots, x_n$, which happens with probability $P(C; n, k)$. Conditional on this, the probability of a collision among the hashes $f(x_1), f(x_2), \dots, f(x_n)$ is obviously 1.
  • The keys $x_1, x_2, \dots, x_n$ are all distinct, which happens with probability $P(D; n, k) = 1 - P(C; n, k)$. Conditional on this, the hashes $f(x_1), f(x_2), \dots, f(x_n)$ are $n$ independent uniform random variables with $k$ possible values, and so the probability of a collision among them is $P(C; n, k)$.

Thus, the probability of a collision among key hashes is $$P(C; n, k) + (1 - P(C; n, k)) \cdot P(C; n, k) \\ = 2 P(C; n, k) - P(C; n, k)^2 \leq 2 \frac{k^2}{n},$$ which is also negligible if the probability of a collision among keys was.

(Extending the analysis to larger keys than hashes, like hashing RSA-2048 keys with SHA-256, left as an exercise for the reader.)

$\endgroup$
0
$\begingroup$

If you generate the hash value with SHA-256 (or another bit value) or (example of another hash algorithm) using BLAKE2 you can stay calm that the collision problem is almost impossible.

If only one bit of the X input is different from the Y input, the generated hash will be completely different.

*This If I understand correctly the question.

$\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.