MD5 for 8052 without stdlib, ...

Started by lordbyte October 31, 2006
Hi!

For an embedded project I have to implement the md5-algorithm on a 8052
CPU. First I thought it might be a more or less easy task, but after
looking a little deeper into the problem I got in touch with a few
problems:

- 8052 is only a 16 bit processor. Most md5 (reference) implementations
are based on 32 biut
- For my project I only have 32k of flash memory. If I use one of the
available implementatios with stdlib/stdio, I get an executeable which
is about 21k to 25k big - maybe a lot too much.

Does anyone has an idea in which direction to look for a solution? Did
some other guys here some work with md5 on very small and/or limited
embedded platforms?

Further I also want to investigate SHA1, but for the beginning md5
should be enough. :)

Cheers
  Markus

lordbyte wrote:

> For an embedded project I have to implement the md5-algorithm on a 8052 > CPU.
Who assigned you this task - did you just choose it arbitrarily because it sounds like a fun thing to do, or did the MD5 requirement evolve out of some other requirement of the system in general? Who selected the hardware?
> - 8052 is only a 16 bit processor
In what universe? MCS51 is an 8-bit architecture.
> Most md5 (reference) implementations are based on 32 biut
MD4 and MD5 were /designed/ for 32-bit architectures. MD2 was designed for 8-bit architectures.
> - For my project I only have 32k of flash memory. If I use one of the > available implementatios with stdlib/stdio, I get an executeable which > is about 21k to 25k big - maybe a lot too much.
Much of that is probably printf. Why does your application need stdio? MD5 doesn't require it, although some randomly downloaded sourcecode intended for desktop computers is quite likely to pull in stdio.h for fun.
Hi!

> Who assigned you this task - did you just choose it arbitrarily because > it sounds like a fun thing to do, or did the MD5 requirement evolve out > of some other requirement of the system in general? Who selected the > hardware?
I am a student and the task was assigned to me from my prof. The hardware is fixed and I should "investigate" the use of MD5 and SHA1 on it.
> > - 8052 is only a 16 bit processor > In what universe? MCS51 is an 8-bit architecture.
Maybe I just got a wrong information, sorry. I didn't see the CPU so far. I only played a littloe bit with a software debugger. :) Sorry form my wrong information!
> MD4 and MD5 were /designed/ for 32-bit architectures. MD2 was designed > for 8-bit architectures.
Looks like I have to suggest to use MD2. Thanks for you reply! I will discuss the problems with my prof in the next meeting. Hopefully we can get forward. :) Cheers Markus
lordbyte wrote:
> Hi! > >> Who assigned you this task - did you just choose it arbitrarily because >> it sounds like a fun thing to do, or did the MD5 requirement evolve out >> of some other requirement of the system in general? Who selected the >> hardware? > I am a student and the task was assigned to me from my prof. The > hardware is fixed and I should "investigate" the use of MD5 and SHA1 on > it. > >>> - 8052 is only a 16 bit processor >> In what universe? MCS51 is an 8-bit architecture. > > Maybe I just got a wrong information, sorry. I didn't see the CPU so > far. I only played a littloe bit with a software debugger. :) Sorry > form my wrong information! > >> MD4 and MD5 were /designed/ for 32-bit architectures. MD2 was designed >> for 8-bit architectures. > Looks like I have to suggest to use MD2. > > Thanks for you reply! I will discuss the problems with my prof in the > next meeting. Hopefully we can get forward. :) > > Cheers > Markus
It should be possible to do it (I am only vaguely familiar with the MD5 algorithm). I implemented the DES encryption algorithm (admittedly a long time ago!) on the 8051 which IIRC also had 32bit data values as well as large tables with lots of bitwise masking & XORing. It certainly didn't take up as much space as yours seems to although I can't really say if the two algorithms are comparable form that perspective. Since you mention stdlib/stdio I assume you're using C? I coded it in C (Franklin Compiler) which had support for 32bit integers. Most of the operations should be able to be done without using the libraries (it was in my case anyway) since the operations are mostly quite low level i.e XOR, AND, etc. Rather than use memcpy() for example, just write your own loops for array copying etc. Also check out the 'union' declaration - it can be very handy for accessing the same data in different ways without taking up more space. Of course any tables you need will occupy code space unless they can be generated algorithmically on the fly (usually not possible). If the only task your project has to do is the MD5, then what is the problem if your code occupies ~25k out of 32k? HTH Chris.
Hi!

> It should be possible to do it (I am only vaguely familiar with the MD5 > algorithm). I implemented the DES encryption algorithm (admittedly a > long time ago!) on the 8051 which IIRC also had 32bit data values as > well as large tables with lots of bitwise masking & XORing.
[...]
> If the only task your project has to do is the MD5, then what is the > problem if your code occupies ~25k out of 32k?
I will try to explain the "big picture" of the project: The embedded device is integrated in a - let's say - light switch. Its energy comes from a very small dynamo wich will generate enough power to operate the CPU for a few milliseconds. In this time, the CPU has to generate a hash value for a certain key and has to transmit it over some kind of wireless link to an receiver station. The device has also attached a small flash memory. By pressing the button, a counter has to be incremented (and written to the flash device), the counter plus a "key" have to be hashed and transmitted wireless to the basestation. As far as I know there also has to be some kind of "routing algorithm" implemented on the whole device. My part is to invetigate and implement the hash-functions. My prof told me that he prefers md5 and sha1, if this is possible. Because the length of the packet that should be transmitted is also very limited, he tought it might be possible to use some kind of "half md5". Faced with all these problems, maybe we just go for another hashing algorithm which is more easy to implement in the small memory and with only 8bit. Thanks so far fo all your replies! Markus
Markus wrote:

> The device has also attached a small flash memory. By pressing the > button, a counter has to be incremented (and written to the flash > device), the counter plus a "key" have to be hashed and transmitted > wireless to the basestation. As far as I know there also has to be some > kind of "routing algorithm" implemented on the whole device.
It sounds like you are trying to implement a rolling-code system. Look at the Microchip HCS300 which is purpose-built for this task. It can transmit the state of up to 4 buttons or switches, plus a serial number, plus the Keeloq rolling-key code. It will require two orders of magnitude less energy than a microcontroller-based crypto implementation. Or you can look at Atmel app note AVR411 "Secure Rolling Code Algorithm for Wireless Link" <http://www.atmel.com/dyn/resources/prod_documents/doc2600.pdf> MD5 is not the right tool for the job here unless the other end of the link already exists and can't be changed.
If possible use AES, in some hash-mode. AES has no known practical attacks
and it was designed to run on a 8 bit processor. Second choice DES or RC4.

Wim



Wim Ton wrote:
> If possible use AES, in some hash-mode. AES has no known practical attacks > and it was designed to run on a 8 bit processor. Second choice DES or RC4. >
For the microcontroller, I would use XTEA. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com