At 2:05 PM +0100 2/25/02, albert.mietus wrote:
>A 40Mhz 386 is a small system, for a PC/desktop/server. However, it's isn't
>a
>small system in absolute numbers!
>
>There are a lot of "small" systems out there. Embedded systems, like the
>processor in a TV, in car's etc are typical "small".
>Also, systems in (non-PS) printers, PDA's, routers, RadioLAN-gateways, etc
>will typical be "small". (Read: low cost, low power, ...)
>
>I hope we don't exclude them completely, in syslog-sign.
>I assume the are network/security operators that need the extra security of
>syslog-sign. But are not willing to upgrade there systems to "superCPU"
>level.
>
I understand. In my day job, I am the lead architect for an embedded
microprocessor with crypto-assist. But the fact remains that public-key
cryptography is a cpu-intensive operation. There are many situations where
small microprocessors are required, and public-key crypto is not an option.
(Or you base your solution on an embedded microprocessor that has a
hardware modular exponentiator, like the one one I work on.)
>True, I assume
>However, that never can be a reason NOT to allow RSA in the standard.
>
>Most standard offer several alternatives. We can add RSA in the rfc, and
>mention that "generally speaking" DSA is better.
>
It depends on the application. Syslog-sign is one of the very few where DSA
is clearly better than RSA.
>> The other is that DSA signs faster than RSA, but
>> is slower for verification.
>
>I haven't tested this yet. But, the information I have shows RSA is the
>faster one for signing.
>
Check out table 20.3 in Applied Cryptography, second edition. It's on page
489 of my copy. The benchmark is for a 33MHz 80386 using 512 bit keys. Here
are the relevant bits:
DSA RSA DSA (with common p, q, g)
Key Generation: 14s n/a 4s
Signing: 0.03s 15s 0.03s
Verifying: 16s 1.5s 10s
>> In an application where you are doing a lot of
>> signing, but relatively few verifications, DSA is the clear winner.
>
>[Assuming it is the other way around:]
>Often, the signing an verification is done in other systems.
>
>When we use a small system, it will do the signing, and send it to en
>"central" collector. Where the verification is done. There we have the
>option to bay "fast" systems. Or to that on "nightly ours"
>
>So, when we have an option to make signing faster, at the cost of slower
>verification, this would help for small systems (as syslog-device).
>
Then you want to use DSA. For most systems (like certificate based
systems), there are advantages to using RSA. In these, you make a signature
once, and verify the signature a large number of times. So on the basis of
sheer time, you use RSA. In the days when RSA was patented and DSA wasn't,
you'd do some algebra based on the fact that time is money, and substitute
money for time, and come up with a money-cost.
For syslog-sign, though, we're going to do many signatures, and hardly ever
verify them. This is, after all, a logging system, and the typical life of
a log is that it is generated and goes immediately to archival storage and
is never seen again. The log only gets looked at if there's some sort of
problem, and at that point, speed considerations don't matter, as there's a
slow human being trying to make sense of it. The purpose of the signature
is to show that the log hasn't been tampered with.
Another constraint we are dealing with is that syslog packets are small,
only 1K in maximum length. So the larger a signature itself is, the smaller
a syslog-sign window can be across the stream of log messages. The smaller
the window is, the more signing you have to do. DSA signatures are 40 bytes
long (before being asciified, and without overhead -- and it's actually two
160-bit numbers; if you want DSA with greater than 1024 bit keys, you need
a wider hash, and the resulting signature would be twice the size of the
hash). RSA signatures are the size of the key (the size of the public
modulus, if you want to be picky). A 1024 bit RSA key yields a 128 byte
signature, which is over thrice the size of a DSA signature.
If we optimize syslog-sign for slow processors, then you want to make these
design decisions:
* You want an algorithm that is fast for signing.
* You want small signatures, because the smaller the signature, the bigger
your window is, and thus the fewer signatures you have to make.
And as it happens, this is *exactly* the decisions that syslog sign makes.
DSA is between 2 and 3 orders of magnitude faster than RSA for signing, and
creates signatures that are 1/3 the size. I've been doing crypto for a
decade, and this is the first time I've seen an application for signing
where DSA was the clear winner. Every other time, there's always been a
tradeoff. Money, licensing, export laws, and other things have always made
it be a balancing act. For syslog-sign, it's just pure computer science,
and that says to use DSA.
If it turns out that this isn't good enough for your implementation -- that
it's still two slow, there are some things you can do:
* Cut down the key size to 512 bits. This will greatly speed up signature
generation. However, I will note that a 512-bit key as approximately as
secure as single-DES. Ask yourself the question, "Would I use single-DES in
this system in order to keep my 40MHz 386?" If the answer is, "Yes! For my
application, DES is just fine" then cut the key size. (And there are plenty
of places where DES is acceptable.) If the answer is, "No, I couldn't look
my colleagues in the eye and say I use single-DES" then this is not the
right option for you.
* Find some carefully hand-tuned modular math code written in 386
assembler. This will speed up your system 2x to 3x over C code.
* Make sure you use pre-computation in your DSA signatures. This can give
another boost. You still have to burn the same number of computes for the
total signature, but you can do a lot of them ahead of time. This can give
you more throughput.
* Get some sort of hardware accelerator for your DSA signatures. This
probably isn't feasible, because the cost of such a thing will probably be
more than finding yourself a faster system. But you never know.
* Use a log aggregator that has some oomph to it. Have your 386 lob its
syslog messages at a faster computer, and have *that* machine do the
signing.
* Don't use syslog-sign. Public-key crypto is expensive. Look at the table
above. Generating a 512-bit RSA signature on your machine should lock up
the CPU for approximately 12 seconds. Verifying a DSA signature with common
p, q, and g will take approximately 8 seconds. That's stunningly long! If
you can't afford it, you can't afford it. If we put RSA signatures into
syslog-sign, someone will use them (if for no other reason than RSA is more
common), and we'll have all sorts of problems because of speed. It's best
as designers to just forestall that now.
There is one other option available, but I'm going to put that in another
message.
Jon
