Re: Are RSA opertaions cheap? (was Re: Suggestion for SOI wrt PFS)

["Angelos D. Keromytis" <angelos@cs.columbia.edu>]

In message <Pine.LNX.4.33.0204010938210.26240-100000@janpc-home.cisco.com>, Jan
 Vilhuber writes:
>
>You'd probably see the same symptoms (substitute voice traffic for
>simple data traffic) on your other example from a few weeks ago: The
>palm pilot. I know there are ipsec clients for palm pilots (why you'd
>want to is a bit beyond me, but it seems some people have a legitimate
>use). I'd be willing to bet money that if you did an rsa operation,
>that traffic would effectively stop flowing for the duration of the
>rsa operation. Or the operation would take forever, meaning you'd have
>to tweak the implementation with nice long timeouts.

In pure software, yes (I think an RSA signature with 1024-bit keys takes
something like 30 seconds). However, Palm VII has support for EC crypto
(I'm not sure if it's software or hardware), which is used every time
one connects to the CDPD network --- and it's pretty fast! My cellphone
has TLS certificates for use with WAP (although I'll admit I've never
used WAP, so I can't comment on its performance...)

>The question you must ask yourself is: Do you want ipsec to be
>ubiquitous, i.e. useful on as many devices as we can make it work for?
>Or do you only want it to be used in situations where people have
>450MHz pentiums available? As you may or may not have noticed, many
>groups in and outside the IETF are having to come up with their own
>keying schemes because IKE won't work for them. I've heard "Oh
>please... not IKE" so many times its ridiculous. Protocol complexity
>has something to do with it, but as Mike Thomas pointed out in another
>posting, there were cases (packetcable just one of them) where the
>computations necessary were simply unreasonable.

Actually, the cases I know of had everything to do with protocol
(and spec) complexity --- I'm somewhat familiar with 3GPP, and the
spec was definitely the root cause.

>> So you're saying that you *do* have a business need for a box that can
>> support a sustained SA setup rate of 1000 tunnels/second ? Could you
>> expand on it ?
>
>Sure. You do the math: How many ipsec peers would it take, rekeying at
>(your example) every 20 minutes, to give me a sustained rate of 1000
>tunnels per second?

1.2 million peers on a single box. That's if you actually rekey every 20
seconds (and not every hour or two, or longer, now that we have AES). But
let's keep these numbers for a second.

You'll need 104MB of RAM just to keep the SPI and the keys for each SA (2 SAs
per peer) --- never mind the SPD, credentials, pointers, and all kinds of other
bookkeeping information. If you actually add everything up, you'll find out
that with 1.2 million peers, you definitely need a 64-bit architecture :-)

Now, a box that can route 10Gbit/s and can also do 3DES-SHA1 at the same speed
would be able to exchange about 8kbit/s with each peer. I know of a couple of
recent "products" (unclear if they will be commercially available, hence the
double quotes) that can actually do 10Gbit/s encryption with specialized
hardware (no current bus can actually support this rate), but these tend to
assume very high traffic aggregation --- they don't do very well when there is
a lot (or even *any*) crypto context switching, and they assume instantaneous
SPD lookups (think of them as link encryptors using IPsec). Current commercial
state-of-the-art crypto hardware does about 1Gbit/sec 3DES-SHA1 (we're ignoring
all OS and other network costs for the moment) --- that means about 800 bits/
sec with each peer at *peak* rate, which no bus architecture I know of can
actually support (PCI seems to peak at about 600-700kbit/sec). And this is the
sum traffic of *both* directions.

So, basically, you'll be able to support a keystroke in one direction (TCP
packet with SACK+timestamp and a single byte of data in one direction, and the
corresponding ACK in the other direction) :-)

And that's if you have hardware crypto support for symmetric encryption; if
you do it in software, divide you numbers by a factor of 10 to 100 (perhaps
more, if you're using a puny CPU).

>Why would I NOT want to maximize the number of IPsec peers I can
>handle? Doesn't everyone have a business need to maximize the use of
>their hardware? If I have one keying scheme where the number of peers
>I can support is 1 million, and there's another scheme where (all
>things being equal) the number of peers I could handle is 3 million,
>which do you think I should pick? Which do you think I should work
>towards?

If your box cannot support 3 million peers anyway, but it can support 1 million
peers with a simpler protocol (and corresponding implementation), which should
you work towards ?
-Angelos