Re: "Boradcasting" MAC'd data

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 04/19/05 

Date: Tue, 19 Apr 2005 03:33:39 +0000 (UTC)

Michael Brown wrote:
>David Wagner wrote:
>> Personally, I'd be reluctant to try to invent some new approach until
>> you have measured or estimated the cost of the straightforward
>> solution.
>
>The machine can compute standard DSA signatures at a rato of about 130/s
>(it's a somewhat dated machine).

Ok. Sounds like what you've got using dsa1024 is close, but not quite
as fast as you'd like.

Here is my advice, in order of ease of implementaiton:

Step 1) Invest in a faster machine. OpenSSL on my 2100Mhz Athlon can
do 781 dsa1024 signatures/second. A new machine is surely cheaper than
the cost of validating any new cryptographic scheme. If that is not
good enough, consider a crypto accelerator. As usual, start with brute
force before applying cleverness.

Step 3) If that doesn't do the trick, consider precomputing "blank check"
DSA signatures during times of light load. This lets you do all the
heavy lifting (the modular exponentiation) in advance; then, when you
later learn the message, all you have to do is a modular multiplication
or two, which is very fast. Since you talk about varying load on your
server, this sounds like it might fit your needs perfectly.

Step 4) If that is not enough, consider elliptic curve cryptography or
some other faster signature scheme.

If you've considered all of the above and none of them meet your needs,
let me know (yet again! thanks for your patience). Describe your latency
requirements (does the signing machine know packet contents in advance,
or can it afford to delay them a bit?) and reliability of your channel
(drop rate?). I know of several tricks involving hash chaining, Merkle
hash trees, and signature batching that can improve total aggregate
bandwidth, but I'm too lazy to type them in at the moment. Keywords:
stream authentication, broadcast authentication, TESLA, hash chaining,
erasure codes.

I don't mean to give you a hard time; I'm just too lazy to type a lengthy
post on advanced methods unless I'm sure you'll find it worthwhile.

>One other thing that nags
>at me slightly is generation of k values for the signatures. The machine
>does not have a hardware RNG and no user to sit there moving the mouse
>around in circles, so the random numbers would presumably have to come from
>a secure PRNG.

/dev/urandom is your friend. Or, yes, a good stream cipher would be fine.

>> Do you have constraints
>> on number of bytes of per-packet overhead?
>
>"Within reason" :) So 40 bytes or so would not be an issue. A couple of KB
>would be.

Yikes. Did you realize that dsa1024 signatures are about 150 bytes long
(I believe), hence will be difficult to cram into those 40 bytes? Perhaps
you can amortize costs across packets.

Relevant Pages

  • Re: Resources expended to AV management solution.
    ... Its also going to vary depending on how much control you ... is recovery from a Malware outbreak. ... In other words, the cost of failure ... Is the IDS team managing Malware signatures? ...
    (Security-Basics)
  • Re: TAF for $47,000.00 ???
    ... Why the hell would Pat Lawlor sign a pin four times. ... signatures also looks much different than the other. ... How much you figure that ad cost to run with the listing fee's? ...
    (rec.games.pinball)
  • Re: Adding a signature on docs.
    ... Years ago I was told that banks don't look at signatures on checks ... Word MVP FAQ site: http://word.mvps.org ... > they figured the cost of verifying signatures was more than the ...
    (microsoft.public.word.docmanagement)
Quantcast