Subject: [P2PSIP] SHA-1 too much for small device CPU?

From: Michael Chen <[email-masked]>
Date: Mon, 26 Mar 2007 21:04:25 -0800

From what I can see, the most CPU intensive operation in the dSIP draft 
is the hashing function SHA-1 for Chord.  Other operations are not 
unlike conventional SIP.

My concern is SHA-1 or any other hashing function may be too much for 
small device CPUs to achieve a reasonable respond time while processing 
DHT requests.

Do any one know the computational expense of SHA-1 (say in terms of CPU 
cycles)?  If we use that and the clock speed of a typical embedded CPU, 
we can calculate how long does it take to compute a SHA-1 hash on a IP 
address string.

Thanks

--Michael

_______________________________________________
P2PSIP mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/p2psip

---

From: Ali Fessi <[email-masked]>
Date: Tue, 27 Mar 2007 17:55:56 +0200

Computation of cryptographic hash functions shouldn't be a problem.

Here some experimental numbers:

Based on performance tests of IPSec in the Linux kernel, the computation 
of the SHA-1 value of a packet with 64 bytes length requires less than 
40,000 CPU cycles.

So, for example, using a PDA with 200Mhz, it should take less than 0,2 
milliseconds on a idle CPU.

I think that's good enough. It you need to hash an IP address or a user 
URI, as for P2PSIP, it will be even faster, since the length of the 
input is less than 64 bytes. (the time required to compute a SHA-1 value 
increases monotonically with the input length)

So, I think there is no reason to worry about that.

cheers,
  ali

-- 
Ali Fessi
Computer Networks and Internet
University of Tuebingen, Germany

---

From: Michael Chen <[email-masked]>
Date: Tue, 27 Mar 2007 09:13:32 -0800

Ali,

Your numbers explain everything.  Even for a 80Mhz CPU, the time is 0.5 
milliseconds, which is not bad at all.

I am curious though about the source of this statistic or the program 
one can run to get the 40,000 number.  Would you please elaborate?

Thanks

--Michael

---

From: "Turner, Jim \(NBC Universal\)" <[email-masked]>
Date: Tue, 27 Mar 2007 09:20:47 -0700

Is there a draft somewhere, either for this group, or on other sites like OpenDHT, or other, that describes the failure mode in a large distributed network when a hash "collision" occurs? What is the impact on the system, and how does the software correct for this? I'm familiar with traditional hash "buckets", but I'm curious about the impact on systems like we're discussing...

Thanks,
Jim

-----Original Message-----
From: Ali Fessi [mailto:[email-masked]]
Sent: Tue 3/27/2007 11:55 AM
To: Michael Chen
Cc: [email-masked]
Subject: Re: [P2PSIP] SHA-1 too much for small device CPU?

cheers,
  ali

---

From: EKR <[email-masked]>
Date: Tue, 27 Mar 2007 09:27:02 -0700

"Turner, Jim \(NBC Universal\)" <[email-masked]> writes:
> Is there a draft somewhere, either for this group, or on other sites
> like OpenDHT, or other, that describes the failure mode in a large
> distributed network when a hash "collision" occurs? What is the
> impact on the system, and how does the software correct for this?
> I'm familiar with traditional hash "buckets", but I'm curious about
> the impact on systems like we're discussing...

This is such a low probability event it's basically not considering
outside an attack on the system.

-Ekr