Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have designed an SQL aggregate function in Oracle that bitwise XORs all MD5 sums of the values stored in a column.

For example, if my table is:

+-----+----------+---------+
| Key | Sequence |  Value  |
+-----+----------+---------+
|   1 |        1 | 'Hello' |
|   1 |        2 | 'World' |
|   2 |        1 | '1234'  |
|   3 |        0 | (empty) |
|   4 |        1 | 'Hello' |
|   4 |        3 | 'World' |
+-----+----------+---------+

I can run the following query in Oracle:

with t AS (select 1 key, 1 sequence, 'Hello' value FROM dual
           union all select 1, 2, 'World' from dual
           union all select 2, 1, '1234' from dual
           union all select 3, 0, '' from dual /* ... */
          )
   select key, md5_agg(value) from t group by key

and get (unfortunately aggregate functions in Oracle ignore NULL values and '' is considered as NULL)

+---+----------------------------------+
|key| md5_agg(value)                   |
+---+----------------------------------+
| 1 | 7EBD0B1DA67F965F802D31DF25C4B321 |
| 2 | 81DC9BDB52D04DC20036DBD8313ED055 |
| 3 | 00000000000000000000000000000000 |
| 4 | 7EBD0B1DA67F965F802D31DF25C4B321 |
+---+----------------------------------+

I would like to use this approach to compare if the contents of some columns are equal when I compare subsets of the same table (think of finding duplicates in a complex structures that spans over multiple rows in the same table). Here with this results I know that I have the same subsets for keys 1 and 4.

What are the limits of such an approach? Here are the ones I could list:

  • This is interesting only if my column contains distinct values. If my columns contains twice the same string, the xor operation will be a no-op.
  • Due to Oracle limitations, if my column contains empty values, they do not count.

With those limitations in mind, is it still possible to infer, from two equal md5_agg results computed from distinct and non-empty values, that the original values make up the same sets?

In order to reformulate, are there odds that the MD5 sums of distinct strings XOR to 0?

share|improve this question
1  
One property of XOR is its commutativity (and associativity) - A XOR B XOR C = B XOR C XOR A, i.e. you can't detect changes in order, but at the same time, you don't have to sort before aggregating. No idea if this is positive or negative for your use case. –  Paŭlo Ebermann Nov 30 '11 at 10:14
    
@Palo Ebermann♦: You're right. I've chosen XOR exactly because of that, because I want to verify that tables have the same contents, not that SELECT statements return the same results in the same order (no DBMS guarantees the order of rows returned unless you specify ORDER BY). –  Benoit Nov 30 '11 at 10:45
    
If you do some research in previous questions (in crypt, or in stackoverflow, etc) that there's always a possibility that you have some collision, but it's very unlikely, and then you deal with it with different approaches if having a collision is a no-go for you... –  woliveirajr Nov 30 '11 at 10:54
    
If I understand this right - you're looking to use this method to ensure that two different aggregate values imply that the total source data remains unique? I.e. you're wondering if xoring md5 hashes will result in collisions over the data you're aggregating? If so, it might be worth adding that to the question perhaps? Just a thought - the more detail on these sort of things the better the answers, generally. –  Ninefingers Nov 30 '11 at 11:32
    
I understood that the OP is looking for a "given my data, I want to extract subsets. Can I use MD5 with XOR to verify if the subset contains the same content, without having to worry the about their order ?". Collisions would be a problem of giving false positives. And this has very little to do with crypto... using MD5 and XOR doesn't mean he wants security, secrecy... –  woliveirajr Nov 30 '11 at 12:33

2 Answers 2

up vote 3 down vote accepted

There are two points to consider here:

How likely is it that two different strings give the same MD5 hash?

This is known as a hash collision. A good hash function makes this probability as small as possible (this would be about $1/2^{128}$ for MD5). If you have a larger number of strings to hash, the probability of any collision between any of them grows ... but you need about $2^{64}$ strings to have a non-neglectible chance of collision (This is the birthday paradox).

Unfortunately, MD5 is not a good hash function - its collision-resistance is basically broken. It doesn't take much work to create two different strings with the same hash. So if you want to ensure this even in the face of an adversary feeding strings into your database, don't use MD5. Use one of the SHA-2 hash functions instead, they are still considered secure. (They also have a larger output size, which also moves the birthday bound higher.)

Assuming an ideal hash function (e.g. a random oracle), we can reduce the question to this:

Given two sets $A$, $B$ of $k_A$, $k_B$ random bit-strings of same lengths $n$, how likely is it that we have this? $$\bigoplus_{i=1}^{k_A} A_i = \bigoplus_{j=1}^{k_B} B_j$$

Actually, the XOR of random strings (or even many non-random strings with a random one) is again a random string, so this boils down to how likely is it that two random strings of size $n$ are identical?

Here we have the same answer as above: This probability is $1/2^{n}$ for two strings, and after about $2^{n/2}$ such random strings you'll get a good chance for a collision.

So, it looks like your scheme is solid, just make sure to choose a good hash function (not MD5, and even SHA-1 has bad reputation nowadays) with a big enough output size $n$ so that the number of individual strings hashed stays small compared to $2^{n/2}$.

But if the adversary can control a large enough part of your subset (including a subset of a set of around $n$ such strings is enough, and if he can inject those strings arbitrarily, even less are needed, but a bit more pre-calculation to choose them), he can choose those strings in a way that their XOR will give any value he wishes, which then translates to an arbitrary collision in the final "hash". Use the method highlighted in fgrieu's answer instead.

share|improve this answer
2  
I agree that the scheme has little chance to fail by accident, short of the issue of duplicate strings in an input. But if one cares to use a safer hash than MD5, then one is after avoiding deliberate collisions, and then the scheme is terminally weak, see my answer. –  fgrieu Nov 30 '11 at 12:42
    
@fgrieu: Thanks for the note. Such occasions are when I wish I could downvote my own answer. –  Paŭlo Ebermann Nov 30 '11 at 15:09
    
@paulo: but the OP doesn't want protection, collison resistance... it's barely a crypto question, it's much more the use (and collison possibility) using MD5 –  woliveirajr Nov 30 '11 at 16:25

The short answer is no. The scheme gives poor protection against collisions, that is inputs detected as having the same content (within order) when they have not.

As noted in the question, this can occur when entries in an input are duplicated; e.g. ("O","X","O") and ("X") collide.

This can also occur for maliciously crafted entries. For a start, MD5 is broken, in the sense that it is now easy to create different strings/entries that hash to the same MD5 result; replacing one by the other will go undetected. And even if one uses a collision-resistant hash such as SHA-256, it is very easy to construct a set of messages such that the XOR of their hashes equals a given value, by mere Gaussian elimination. See the answer to this question.

On the other hand, short of the issue of duplicated entries in an input, there is little chance that the scheme fails by accident.

A robust scheme would be:

  • hash each string using SHA-256
  • sort the hashes by ascending value
  • hash the concatenation of the sorted hashes using SHA-256
share|improve this answer
1  
Thank you for this answer. I am not concerned about malicious entries for the moment, just about entropy lost when XORing MD5 sums. –  Benoit Nov 30 '11 at 15:59
    
@Benoit: then rest assured, there are only 1 chance out of 10 that there is a collision among $m=2^{63}$ invocations of md5_agg with random distinct arguments (short of obvious issues with duplicates and empties); you likely do not have the computational resources to even approach that; and collisions odds for $m$ much below that are only about $m \cdot (m-1)\cdot 2^{-129}$. –  fgrieu Nov 30 '11 at 20:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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