From: William Ahern on
Chris Friesen <cbf123(a)mail.usask.ca> wrote:
> On 04/05/2010 10:34 PM, cinsk wrote:

> > That's why I asked the original question; Is it possible that two
> > CRC-64 ISO values from unique 48-bit data to collide each other?

> I haven't done the math, but I wouldn't expect collisions given that the
> input is shorter than the hash itself.

> There have been cases of duplicate hardware addresses, and duplicate
> software addresses (in virtual machines, for instance, or software
> overriding the hardware address at runtime) is even more likely.
> Assuming the MAC addresses are unique is probably a mistake.

It's a bad idea to assume MACs are unique. I've personally witnessed a case
where the OEM shipped several bulk orders of network cards all with the same
MAC address. The issue took awhile to surface because, IIRC, the effected
batches were never run in the relevant configuration _together_; only
individually tested or run in production against earlier batches.

Given the profit margins on network cards, I wouldn't be surprised if this
is very common today.

I vageuly recollect that the OEM apologized not about the cloned MAC
addresses, but thay they had shipped them all to the same purchaser.
From: Nicolas George on
cinsk wrote in message
<71662e6b-fdb6-411e-a189-4281bf4033b8(a)11g2000yqr.googlegroups.com>:
> If the given string is 48-bit data, and take the CRC64, does it
> collide?

CRC is, mostly, the remainder of an euclidean division. Therefore, I expect
that if you take CRCn and feed it all 2^m possible m-bits strings, with m >=
n, you will find every 2^n possible outputs exactly 2^(m-n) times. And if
m < n, there should be no collisions.

But I agree with the other people in the thread: using a hash function
bigger than its input, and then relying on the fact that there will be no
collision is a terrible design. There are standards way to derive a 64-bits
unique identifier from a MAC address, for example the one used for IPv6
autoconfiguration.
From: Ersek, Laszlo on
On Mon, 5 Apr 2010, cinsk wrote:

> Our software has two parts; part-A for generating unique ID (I know that
> it is a bad idea, but we uses CRC64 from the 48bit string as an unique
> ID), part-B for processing some job based on that unique ID and write a
> log file.
>
> The problem is, the log file from part-B has mysterious entries that
> shows two entities has a same ID. The testing team asks me that whether
> it is possible to generate duplicated ID (CRC64 from 48bit arbitrary
> data) theoretically.
>
> If that is possible, I need to report the tester team that we need to
> change the whole process to generate unique ID.

If you'll have to switch to a new uuid-generator:

OSSP uuid:
http://www.ossp.org/pkg/lib/uuid/
http://packages.debian.org/lenny/libossp-uuid-dev

The uuid library in e2fsprogs:
http://e2fsprogs.sourceforge.net/
http://packages.debian.org/lenny/uuid-dev

See the debian package links for concise descriptions.

lacos
From: Chris Friesen on
On 04/06/2010 02:23 AM, Nicolas George wrote:
> There are standards way to derive a 64-bits
> unique identifier from a MAC address, for example the one used for IPv6
> autoconfiguration.

That only ensures that the mapping from MAC to identifier is unique. It
doesn't ensure that the end identifier is unique (since there are
documented cases of duplicate MAC addresses).

Chris
From: David Schwartz on
On Apr 6, 8:40 am, Chris Friesen <cbf...(a)mail.usask.ca> wrote:

> On 04/06/2010 02:23 AM, Nicolas George wrote:

> > There are standards way to derive a 64-bits
> > unique identifier from a MAC address, for example the one used for IPv6
> > autoconfiguration.

> That only ensures that the mapping from MAC to identifier is unique.  It
> doesn't ensure that the end identifier is unique (since there are
> documented cases of duplicate MAC addresses).

Exactly. IPv6 autoconfiguration specifically does not guarantee that
the address is globally unique. Only that's as unique as the MAC. (If
MACs collide on a LAN, you're hosed anyway. So using IPv6
autoconfiguration on a LAN creates no new problems.)

DS