Re: 64-bit digest algorithms
by syphilis (Archbishop) 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 | [reply] [Watch: Dir/Any] |
Re: 64-bit digest algorithms
by kvale (Monsignor) on Nov 13, 2008 at 01:59 UTC
|
| [reply] [Watch: Dir/Any] |
|
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.
| [reply] [Watch: Dir/Any] [d/l] |
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.
| [reply] [Watch: Dir/Any] |
|
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.
| [reply] [Watch: Dir/Any] |
|
| [reply] [Watch: Dir/Any] |
|
|
|
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.
| [reply] [Watch: Dir/Any] |
|
|
|
|
|
| [reply] [Watch: Dir/Any] |
|
|
|
Re: 64-bit digest algorithms
by GrandFather (Saint) 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
| [reply] [Watch: Dir/Any] |
|
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.
| [reply] [Watch: Dir/Any] |
|
| [reply] [Watch: Dir/Any] |
|
|
|
Re: 64-bit digest algorithms
by ikegami (Patriarch) 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.
| [reply] [Watch: Dir/Any] |
|
| [reply] [Watch: Dir/Any] |
|
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.
| [reply] [Watch: Dir/Any] |
Re: 64-bit digest algorithms
by zentara (Archbishop) on Nov 13, 2008 at 17:35 UTC
|
Google has alot of stuff for a search for "CRC 64"
| [reply] [Watch: Dir/Any] |
Re: 64-bit digest algorithms (uniprot.org CRC64)
by erix (Prior) 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)
| [reply] [Watch: Dir/Any] [d/l] |