crypto implementation for small footprint devices

[Bill Stewart]

At 03:42 PM 1/9/01 -0800, Xiao, Peter wrote:
>I am currently looking for crypto implementation that can fit into small
>footprint (in the order of 50K or less) devices. Ideally, an SSL type of
>protocol meets my requirements but it is almost impossible to implement it
>within 50K even with selected cipher suites. So, I am looking for
>alternatives (either symmetric key or public key based). I was thinking
>about WTLS but looks like its implementation can not be significantly
>smaller than that of TLS since it is also based on Public Key cryptography
>(I am wondering how it fits into a cellphone). Can any one tell me what is
>the approximate size of the client implementation of WTLS. Also, would
>anyone send some pointers to me regarding what I am looking for.

There's been a lot of work in the Smart Card community on
fitting crypto into small memory space - I don't know if the
"Independent Smart Card Developers' Organization" is still active
- probable address - https://scard.org
plus there are products from a number of smart card vendors.
Dallas Semiconductor's i-button includes a crypto version.
Certicom has the patents to many of the Elliptic Curve cryptosystem
versions, and they've done a lot of work on products for small environments.
ECC has an advantage over RSA and Diffie-Hellman public key methods
because the key lengths are much shorter, typically 160-256 bits
instead of 1024 or 512.  On the other hand, the math is much more complex
than the bignum modular multiply and exponentiation that RSA and DH use,
so the code space would be larger.  And 128 bytes may be large on a smartcard,
but it's not that big on anything else.

Is your space constraint RAM, or ROM/Flash code space?
It's easy to fit the data space for most crypto algorithms
into a few KB; the complexity is in the code space.
Some of the data transfer formats wrap a lot of header
and encoding around it, but some are simpler.
Unfortunately, ASN.1 and PGP both put lots of complexity
into data formats to squeeze out a few bits of space,
so the code tends to be bloatware.
If you're willing to do your own data formats, or use XDR,
you can eliminate most of this.  (Simple bignums, etc.)
On the other hand, if you want full browser capability,
you'll need to do real SSL, so you can't avoid them.

Most of the crypto algorithms themselves are relatively small -
RSA and Diffie-Hellman are each a few lines (plus a bignum handler).
The RC4 symmetric-key algorithm is extremely small,
and operates on 8-bit bytes rather than bignums or bit-twiddling,
and the 128-bit versions are very secure as long as you
follow a few simple rules about usage.
DES is ugly, and the hash functions are ugly,
but they're still not very large.
The 2-lines-of-perl versions are horrendously ugly,
	http://www.cypherspace.org/~adam/rsa/
and drag in perl's hugeness, but most of the ugliness
is because Perl doesn't have native bignums and
because they were converting from decimal input instead of hex.
The Lisp and Python equivalents are pretty clean and still small :-)

Digital signatures themselves are generally more complex
because you need to handle the name of the thing that's being signed,
and any semantics that thing drags with it.  For instance,
are signatures fully general with N layers deep of key certification,
or are you just going to handle signatures from a built-in key
signing hashes of messages and code updates?  (Or signatures from
keys signed by a built-in key.)

What you need for space depends a lot on your objectives and on
how general you need to be.  Sometimes you can get by with
a few primitives to secure your communication to a central server
and do the more complex stuff on the server.

You're also going to have issues if you want to use the crypto
for protecting television content :-),
since that's typically a fast-moving target that changes
almost as fast as the pirates figure out how to crack it.
But even that crypto normally fits on smartcards.
				Thanks! 
					Bill
Bill Stewart, bill.stewart at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639