Pathologically Eclectic Rubbish Lister PerlMonks

### 64-bit digest algorithms

by BrowserUk (Pope)
 on Nov 13, 2008 at 01:39 UTC Need Help??
BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

I'm looking for a 64-bit digest algorithm, but all the searches I've tried turn a gazillion hits for various 128-bit and greater algorithms (MD4 MD5 SHA etc) implemented for 64-bit platforms.

Pointers to existing perl solutions would be great, but descriptions/implementations in any language would be good too.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re: 64-bit digest algorithms
by kvale (Monsignor) on Nov 13, 2008 at 01:59 UTC

I'm probably being too literal here, but I don't get where the 'G' appears in the "following equations"?

The calculation of the DAC is given by the following equations where G represents the Exclusive-OR of two vectors.

``` 01  = e(D1)
02  = e(D2 + 01)
03  = e(D3 + 02)
On  = e(Dn + 0n-1)

The algorithm also seems to call for DES encryption and a secret key. I think the the duality of the term 'digest' is screwing me here. "64-bit hashing algorithm" seems to turn up better hits.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: 64-bit digest algorithms
by syphilis (Chancellor) on Nov 13, 2008 at 08:16 UTC
I'm looking for a 64-bit digest algorithm

According to my copy of Handbook of Applied Cryptography, Matyas-Meyer-Oseas, Davies-Meyer, Miyaguchi-Preneel, MASH-1 and MASH-2 all output an n-bit hash (where n is configurable).

I'm left with the impression, however, that very little is known about the security of those hashes when n is as small as 64 - which leads me to think that truncation of the more common (n >= 128) digest outputs may well be as good as anything (and a very simple solution as well).

Cheers,
Rob
Re: 64-bit digest algorithms
by dHarry (Abbot) on Nov 13, 2008 at 08:22 UTC

Just out of curiosity, why?

64 bits message digests are considered unsafe, hardware has become to powerful. 128 bits is only "moderately" safe, if you want your digests to be really secure you have to opt for 512 bits. Or is security not an issue for you?

Update

If you insist on 64 bits message digests I think DES is the way forward, like brother kvale already suggested.

The application has nothing to do with either cryptography or security. Essentially I want a hashing function with (far) less risk/frequency of collisions than a 32-bit hashing function, and far less space utilisation that a 128-bit digest.

Assuming linear distribution (and unlimited space), a 64-bit hash has only a 0.000000023% chance of collisions relative to a 32-bit hash. but uses half as much space as MD5.

I also considered 48-bit, but they're harder to calculate; and 53-bit (because of the possibility of using doubles for the calculations), but most hashing algorithm using shifting and that doesn't work with FP. And both are as rare as rocking horse doo-doo.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

A list of Hash functions. There area a few 64 bits alternatives. Maybe elf64?

HTH

When I was playing around recently I used CRC32, taken once forwards across the input and a second time backwards across it. This certainly increased the effective space of the hash -- my sums is not up to any assertion about whether that gives a full 64 bits of "entropy".

There are also two other respectable 32 bit CRCs -- avoiding the need to reverse the input.

There is also CRC64 itself, but a quick poke at CPAN doesn't reveal an implementation (except buried in some "Bio..." stuff). Wouldn't be too difficult to bang out a table driven CRC64.

You don't want anything crypto-secure, so a CRC could well be sufficient, and a good implementation will run like stink compared to any of the crypto-digest stuff.

Doubles have 52 bits. The 53rd bit is the implied leading "1".

Update: As pointed out by oshalla, the implied bit does count. As pointed out by BrowserUk, I forgot about the sign bit. So there's 54 bits of precision for signed integers.

Re: 64-bit digest algorithms
by GrandFather (Sage) on Nov 13, 2008 at 04:25 UTC

Would it suffice to generate an MD5 or other 128 bit digest then xor the top 64 bits with the bottom 64 bits or are you hoping that a dedicated 64 bit generating algorithm will be faster?

Perl reduces RSI - it saves typing

I'm hoping to find a well tested 64-bit algorithm.

I read somewhere a while ago, (but now cannot find:(), that any truncation of a 128 bit algorithm like MD5 does not stand up well to linear distribution tests--and a linear distribution is my priority. I can't think of any way to verify this assertion?

Fast would be good, but it's a secondary consideration.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

On the face of it the xor of two random bits should have the same distribution as the original bits unless the bits are related in some fashion. I guess the trick is determining whether there is any coupling between the pairs of bits that would be xor'd together.

Perl reduces RSI - it saves typing
Re: 64-bit digest algorithms
by ikegami (Pope) on Nov 13, 2008 at 04:10 UTC

NIST is holding a competition to replace the SHA family of hash functions, and it asked for submissions to be optimized for 64-bit CPU. Unfortunately, it's still very early in the process.

It seems that someone created a module of Digest::Skein, Bruce Schneier and all's submission if you want to take a peek.

I think I should clarify my question. I'm looking for a 64-bit digest algorithm (Ie. one that produces only 64-bit digests), not a cryptographic strength digest algorithm optimised for 64-bit cpus.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Isn't it typical to chop off the bits you don't need from a larger digest? I noticed you "cryptographic strength" is only present in the description of what you don't need.
Re: 64-bit digest algorithms
by zentara (Archbishop) on Nov 13, 2008 at 17:35 UTC
Re: 64-bit digest algorithms (uniprot.org CRC64)
by erix (Parson) on Nov 04, 2012 at 16:21 UTC

I was looking for a CRC64 to checksum (protein) sequences in the same way as uniprot.org, and found Swiss::Knife (probably the code that Uniprot uses themselves). It is at sourceforge.

FWIW here is its CRC64.pm:

```package SWISS::CRC64;

# ** Initialisation
#32 first bits of generator polynomial for CRC64
#the 32 lower bits are assumed to be zero
my \$POLY64REVh = 0xd8000000;
my @CRCTableh = 256;
my @CRCTablel = 256;
my \$initialized;

sub crc64 {
my \$sequence = shift;
my \$crcl = 0;
my \$crch = 0;
if (!\$initialized) {
\$initialized = 1;
for (my \$i=0; \$i<256; \$i++) {
my \$partl = \$i;
my \$parth = 0;
for (my \$j=0; \$j<8; \$j++) {
my \$rflag = \$partl & 1;
\$partl >>= 1;
\$partl |= (1 << 31) if \$parth & 1;
\$parth >>= 1;
\$parth ^= \$POLY64REVh if \$rflag;
}
\$CRCTableh[\$i] = \$parth;
\$CRCTablel[\$i] = \$partl;
}
}

foreach (split '', \$sequence) {
my \$shr = (\$crch & 0xFF) << 24;
my \$temp1h = \$crch >> 8;
my \$temp1l = (\$crcl >> 8) | \$shr;
my \$tableindex = (\$crcl ^ (unpack "C", \$_)) & 0xFF;
\$crch = \$temp1h ^ \$CRCTableh[\$tableindex];
\$crcl = \$temp1l ^ \$CRCTablel[\$tableindex];
}
return wantarray ? (\$crch, \$crcl) : sprintf("%08X%08X", \$crch, \$crcl
+);
}

1;

(I know; this is an old thread -- but I leave this here because it took me some time to find)

Create A New User
Node Status?
node history
Node Type: perlquestion [id://723321]
Approved by CardinalNumber
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (5)
As of 2018-05-26 18:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
World peace can best be achieved by:

Results (194 votes). Check out past polls.

Notices?