Fast MD program
David Vincenzetti
tampering detector'', something I felt there was a great need for in the Unix
community.
The program first scans the files we want to be tampering-protected, records
their attributes like st_size, st_mtime and size, then calculate a checksum.
Then all the file-records are enciphered and saved, using DES in CBC mode.
If a file changes some way you can detect the changes when you decode
the records database and compare the records with the real file attributes.
There are lots of options and facilities to make the checking process
easy and fast.
THE PROBLEM IS: SPEED, WHEN CALCULATING THE CHECKSUMS. I first tried MD4,
confident that it is one of the fastest secure widely known message digest
program, but it is unacceptably slow:
[gmon(1) output]
%time cumsecs seconds calls msec/call name
55.2 4.06 4.06 729 5.57 MD4Update
36.0 6.71 2.65 87727 0.03 Transform
Then I tried CRC32, a very common algorithm used everywhere, but I have doubts
about its security, if not unsecurity at all. (Could someone please tell me
about the security of CRC32?). Also CRC32 is unacceptably slow:
[gmon(1) output]
%time cumsecs seconds calls msec/call name
88.7 4.07 4.07 606 6.72 UpdateCRC
So, what could I do? The program is ready to be published, it only lacks
some performance due the slowness of CRC32 and MD4. Are there any other
message digest algoritms providing a ``non-high'' security that are very
fast? Hints, anyone?
Ciao, David
--
David Vincenzetti
Dept of CS, University of Milan: vi...@ghost.dsi.unimi.it
Dept of CS, Polytechnic of Milan: vi...@cdc835.cdc.polimi.it
Real $home: 8th street 39, 20090 Segrate, Milan, Italy
Darryl Okahata
> THE PROBLEM IS: SPEED, WHEN CALCULATING THE CHECKSUMS. I first tried MD4,
> confident that it is one of the fastest secure widely known message digest
> program, but it is unacceptably slow:
How fast do you need it? On a 68030-type machine, MD4 crunches at
over 350,000 bytes/second (counting user+sys time only). My 68040
machine crunches at over 750,000 bytes/second. Modern RISC machines
will scream at an even faster amount.
I suspect that you'll find I/O to be the bottleneck in any
"UNIX file tampering detector" -- the disks just can't deliver the data
fast enough. For me, the above numbers drop by a factor of 2-3 if you
take into account disk I/O times.
Note also that turning on profiling slows down code -- your code
will run faster with profiling turned off.
-- Darryl Okahata
Internet: dar...@sr.hp.com
DISCLAIMER: this message is the author's personal opinion and does not
constitute the support, opinion or policy of Hewlett-Packard or of the
little green men that have been following him all day.
David Vincenzetti
> How fast do you need it? On a 68030-type machine, MD4 crunches at
>over 350,000 bytes/second (counting user+sys time only). My 68040
>machine crunches at over 750,000 bytes/second. Modern RISC machines
>will scream at an even faster amount.
I use a hp-s700 workstation with achieves 80000 dhrystone with light
system load. The program's bottleneck is, without any doubts, the checksum
calculating; I believe that CRC32 is totally insecure, so I would use
RSA's MD4 (MD[2, 5], Snefru-[2, 4, 8] are much slower).
What I would need is a fast MD4 implementation, faster than the one available
via ftp at rsa.com. Does such an implementation exist? Hints, anyone?
Keith W. Campbell
>dar...@hpnmdla.sr.hp.com (Darryl Okahata) writes:
>
>> How fast do you need it? On a 68030-type machine, MD4 crunches at
>>over 350,000 bytes/second (counting user+sys time only). My 68040
>>machine crunches at over 750,000 bytes/second. Modern RISC machines
>>will scream at an even faster amount.
>
>I use a hp-s700 workstation with achieves 80000 dhrystone with light
>system load. The program's bottleneck is, without any doubts, the checksum
>calculating; I believe that CRC32 is totally insecure, so I would use
>RSA's MD4 (MD[2, 5], Snefru-[2, 4, 8] are much slower).
>
>What I would need is a fast MD4 implementation, faster than the one available
>via ftp at rsa.com. Does such an implementation exist? Hints, anyone?
Which version of MD4 are you talking about? I have two, both of which
are from RSADSI. The first version processes 1388k bytes/second on a Sparc-1
while the second (newer, more flexible) only operates at 665k bytes/second.
Obviously implementation is a major factor (a little more than 2 in this case).
As for MD5, it should only take 35-40% more time to digest messages. It
invoves 1/3 more rounds (64 as opposed to 48) and each round is only slightly
more complex.
--
Keith W. Campbell Bell-Northern Research
P.O. Box 3511, Station C, Ottawa, Canada, K1Y 4H7
e-mail: ke...@bnr.ca voice: (613) 765-4564
Phil Karn
speed figures others have mentioned for the better CPU architectures.
MD-4 (and MD-5) were clearly designed for machines with lots of 32-bit
registers, and it blazes on them (e.g., Sparc). Unfortunately it runs
much more slowly on brain-damaged, register-starved 16-bit environments
like the Intel chips, and there doesn't seem to be much you can do about
it. It certainly would help, though, if the standard MS-DOS C compilers
had a "386" mode to at least let MD-4 use what few 32-bit registers ARE
available on the 386 and 486.
But all this is relative. Even MD-4 runs far faster than DES on Intel
chips. A year or so ago I devised a cipher that used MD-4 as its
nonlinear function. Even though it used MD-4 much less efficiently
than in its intended purpose, my cipher ran 4x DES's speed on the
Intel machines, and 13x the speed of DES on Sparcs.
Phil
Jouko Holopainen ti
>[...] Unfortunately it [MD4] runs
>much more slowly on brain-damaged, register-starved 16-bit environments
>like the Intel chips, and there doesn't seem to be much you can do about
>it.
I have written optimized ASM program to that. Not too fast, but damn
lot faster than C version. Runs on any 80*86. If interested, mail me
and I might post it to comp.binaries.ibm-pc. Or anyone interested.
--
Jouko Holopainen : jh...@stekt.oulu.fi
Happiness I cannot feel
And love to me is so unreal
David Vincenzetti
>I have written optimized ASM program to that. Not too fast, but damn
>lot faster than C version. Runs on any 80*86. If interested, mail me
>and I might post it to comp.binaries.ibm-pc. Or anyone interested.
I would be interested in an optimized C version of MD4. The version I
have is that available at rsa.com, contained in the ``md4.doc'' file.
Ciao, David
--
David Vincenzetti (PK available by finger)
Dept of CS, University of Milan: vi...@ghost.dsi.unimi.it