crypto implementation for small footprint devices

[Eric Murray]

On Wed, Jan 10, 2001 at 07:59:13AM -0700, Gé Weijers wrote:
> On Tue, Jan 09, 2001 at 03:42:45PM -0800, Xiao, Peter wrote:
> > Hi,
> > 
> > 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.
> > 
> > Thanks in advance!!
> > 
> > Peter
> 
> It's not the public-key operations themselves that use the space. I've
> managed to squeeze OAEP-formatted RSA encryption into less than
> 20K. The public key was hard-wired, though. You probably want to stay
> away from ASN.1 formatted data if space is a concern.


Unfortunately anything that uses X.509 (like SSL) will require it.
It's possible to write small X.509/ASN.1 decoding packages.  One that I
wrote for a small-device SSL package takes about 11k code (gcc on Intel
PIII) and it's not very optimized- there's lots of room to squeeze it
down farther than the original application required.

Encoding ASN.1 really eats space though, because of the nested nature
of complex ASN.1... unless you do some tricks like I did in US patent
6,111,660.   Using this trick, we were able to encode SET messages
(really ugly ASN.1) using only 4 bytes more than the size of the final
message.  So we could comfortably run client-side SET in less than 24k
of RAM.

-- 
  Eric Murray           Consulting Security Architect         SecureDesign LLC
  http://www.securedesignllc.com                            PGP keyid:E03F65E5