MD5 for 8052 without stdlib, ...

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