1
$\begingroup$

The project I'm working on requires me to find a way to create a unique key based on data stored in a table. The table in question consists of x columns and y rows.

In order to create the key I want to hash the data using md5 in the following way:

"|" || md5[(x_1,y_1)]  || "|" || md5[(x_2,y_1)]  || "|" || md5[(x_n,y_1)]  || "|"

My question is: How can I calculate the chance of duplicate keys for different data using this method?

Given: I know the amount of columns (x), I know the size of the data in the columns, I know the amount of rows (y).

The idea comes from this video: https://www.youtube.com/watch?v=fNrs7C86nkI

In the video he says he will do "the math" later but this is not in the video.

$\endgroup$
8
  • 2
    $\begingroup$ Will the data be chosen with the goal of trying to cause a collision? $\;$ $\endgroup$
    – user991
    Apr 8, 2015 at 8:56
  • $\begingroup$ No, the data can be however many things, like costumer data, or product information stuff like that, I will not influence this data to cause a collision. (hope this answers your question) $\endgroup$ Apr 8, 2015 at 9:05
  • $\begingroup$ en.wikipedia.org/wiki/Universal_hashing $\;$ $\endgroup$
    – user991
    Apr 8, 2015 at 9:08
  • $\begingroup$ (On the other hand, one possible risk is someone getting read access to the database and then signing up with "customer data" that was chosen specifically to cause a collision.) $\;$ $\endgroup$
    – user991
    Apr 8, 2015 at 9:12
  • $\begingroup$ I'll take a look at the universal hashing $\endgroup$ Apr 8, 2015 at 9:19

1 Answer 1

3
$\begingroup$

If I understand your question correctly, you want to generate a short value $v(T)$ from a table $T$ such that if $T_1$ and $T_2$ have the same size and the same elements in each corresponding cell, then $v(T_1) = v(T_2)$, and if the tables have different sizes or different elements then $v(T_1) \ne v(T_2)$.

What you need for that is two ingredients:

  • A unique representation for tables.
  • A cryptographic hash applied to said unique representation.

“Unique representation” means that distinct tables have different representations. For example, if your table cells don't contain the character |, then | + T[0,0] + | + T[1,0] + || + T[0,1] + | + T[1,1] + | (where + is string concatenation) is a unique representation of a 2x2 table, and the representation generalizes to arbitrary-size tables with no collision. However, if your table cells can contain the character |, this representation is not unique: you cannot distinguish T[0,0] = a|, T[1,0] = b from T[0,0] = a, T[1,0] = b.

If you can't assume anything about the content of table cells, a convenient and secure method is to take a cryptographic hash of each cell independently, and build the hash of the table by hashing a string made up of hashes. (This is a special case of a Merkle tree.) Don't forget to include the table geometry in the representation. One way to do that is by putting the number of lines and columns at the beginning of the string: $$v(T) = H(m + \mathtt{|} + n + \mathtt{|} + H(T[0,0]) + H(T[1,0]) + \dots + H(T[m,n])$$ where $+$ is concatenation, $m \times n$ is the table size, numbers are represented in decimal and hashes in hexadecimal. Another possible representation is to hash a row by hashing the concatenation of the hashes of the cells in that row, and hash the table by hashing the concatenation of the hashes of the rows.

Moving on to the question of how likely duplicate keys are, there are three cases to consider. Suppose that $H$ is a $k$-bit cryptographic hash.

  1. All the data is essentially random. In this case, the chance that two tables have the same hash is negligible as long as you have significantly fewer than $2^{k/2}$ entries in the list of tables. This figure comes from the birthday problem. For example, a 128-bit hash lets you have several billion billion entries before the chance of a collision becomes high; with a billion entires, the probability is less than $10^{-18}$.
  2. An attacker can choose some of the contents of the table, for example one of the fields is a free-form string, and the objective of the attacker is to craft two distinct tables with the same hash. This is an attack on the collision resistance of the hash. Breaking collision resistance can allow an attacker to inject a harmless record into your database, then substitute a bad one for it. When it comes to attacks, you can no longer reason in terms of probability, because attackers don't behave randomly. MD5's collision resistance is broken: there are cheap ways of generating strings with the same MD5 and with some content in common. Hash trees may be fine, but that depends on the exact structure of your data. So you must use another hash. SHA-256 is the standard hash nowadays.
  3. An attacker wants to craft a table with the same hash as another table that is already in the database and not chosen by the attacker. This is harder than the previous attack; it's an attack on second preimage resistance. MD5 is not broken in this respect; however it would be a bad idea to use it because there is a risk that the attack on collision resistance could be improved to an attack on the second preimage.

TL;DR:

  • Encode the data in your table such that the representation is unambiguous.
  • You can take a hash of each piece, then take a hash of a sequence of hashes and other data: such hash trees are fine.
  • Don't use MD5. Use SHA2-256 (or SHA2-512).
  • If implemented correctly, not only is the probability of a collision too small to worry about (it's less than the probability that your processor will flip a bit at the wrong time), but better than that, there is no possibility for an attacker to arrange a collision.
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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