Prev: Costum Build-Enviroment (search for libs at a certain placefirst)
Next: error [socket]
From: cinsk on 5 Apr 2010 22:54
Hi,

Sorry if this is out of concern of this newsgroup (I don't know where
I should post).

If the given string is 48-bit data, and take the CRC64, does it
collide?

The problem is that, one of the source codes that I need to verify,
uses CRC64 value as a hash value, where the input data is 48bit mac
address.

I need to make sure if the CRC64 value collide with other or not when
the input data is arbitrary 48-bit string.

Unfortunately, I'm very poor at math and CRC64, so I don't know if it
is possible or not.

Regards,


From: cinsk on 5 Apr 2010 23:04
On Apr 6, 11:54 am, cinsk <cin...(a)gmail.com> wrote:
> Hi,
>
> Sorry if this is out of concern of this newsgroup (I don't know where
> I should post).
>
> If the given string is 48-bit data, and take the CRC64, does it
> collide?
>
> The problem is that, one of the source codes that I need to verify,
> uses CRC64 value as a hash value, where the input data is 48bit mac
> address.
>
> I need to make sure if the CRC64 value collide with other or not when
> the input data is arbitrary 48-bit string.
>
> Unfortunately, I'm very poor at math and CRC64, so I don't know if it
> is possible or not.
>
> Regards,

I didn't mention that we uses ISO 3309 standard.
(generator poly is x^64 + x^4 + x^3 + x + 1)
From: David Schwartz on 6 Apr 2010 00:05
On Apr 5, 7:54 pm, cinsk <cin...(a)gmail.com> wrote:

> The problem is that, one of the source codes that I need to verify,
> uses CRC64 value as a hash value, where the input data is 48bit mac
> address.
>
> I need to make sure if the CRC64 value collide with other or not when
> the input data is arbitrary 48-bit string.
>
> Unfortunately, I'm very poor at math and CRC64, so I don't know if it
> is possible or not.


If "no collisions" is a requirement, CRC64 is a terrible choice. Why
not just send the 48-bit value itself? That will save you 16 bits,
save you some CPU, and is, of course, guaranteed not to collide.

DS
From: cinsk on 6 Apr 2010 00:34
On Apr 6, 1:05 pm, David Schwartz <dav...(a)webmaster.com> wrote:
> On Apr 5, 7:54 pm, cinsk <cin...(a)gmail.com> wrote:
>
> > The problem is that, one of the source codes that I need to verify,
> > uses CRC64 value as a hash value, where the input data is 48bit mac
> > address.
>
> > I need to make sure if the CRC64 value collide with other or not when
> > the input data is arbitrary 48-bit string.
>
> > Unfortunately, I'm very poor at math and CRC64, so I don't know if it
> > is possible or not.
>
> If "no collisions" is a requirement, CRC64 is a terrible choice. Why
> not just send the 48-bit value itself? That will save you 16 bits,
> save you some CPU, and is, of course, guaranteed not to collide.
>
> DS

Yes, I found that CRC64 (ISO) is considered weak for hashing, but the
software is already implemented, so I couldn't do anything for now.

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. It could be very
expensive for our current situation, sadly..

If not, I need to check whether the original 48 bit data source is
unique or not. Unfortunately, we do not have enough history data to
prove this.

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?

Thanks.


Thus,
From: Chris Friesen on 6 Apr 2010 01:31
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.

Chris
 |  Next  |  Last
Pages: 1 2
Prev: Costum Build-Enviroment (search for libs at a certain placefirst)
Next: error [socket]