AVR-GCC/GAS MD5-Implementierung oder anderer Hash

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From German to

Threaded View
Hallo Gruppe,

auf einem AVR (mega16 oder mega32) möchte ich den kryptografischen Hash
MD5 einsetzen.

Gerade hab ich die offizielle Implementierung von RSA Securities
portiert; leider wird das Resultat recht groß (~ 7000 Bytes). Das ist
fast der Halbe AVR voll - zur Not würde es schon gehen. Die meisten
Operationen sind natürlich 32 Bit-optimiert, deshalb wird es wohl leider
auch nicht _viel_ besser gehen.

Hat jemand eine AVR-optimierte Implementierung von MD5 oder kann mir
einen anderen (kryptografischen!) Hash empfehlen (für den es
möglicherweise eine Implementierung gibt?

Viele Grüße,
Johannes

--
durch dei Verdunstung kült das sogar ziemlich gut
das ist wie schweiß. Hünde müssen da hecheln so wie Lüfter.
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
Johannes Bauer schrieb:

Quoted text here. Click to load it

In der Diplomarbeit
http://elib.uni-stuttgart.de/opus/volltexte/2004/1827/pdf/DIP-2106.pdf
hat jemand SHA-1 auf einem AtMega in C programmiert und in 1670 Bytes
Flash untergebracht. Dort ist kein Quellcode gegeben, aber es bietet
einen Anhaltspunkt, was möglich ist.
Eine passende englischsprachige NG wäre übrigens sci.crypt.

CU Christian
--
Christian Zietz  -  CHZ-Soft  -  czietz (at) gmx.net
WWW: http://www.chzsoft.com.ar /
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
Johannes Bauer schrieb:

Quoted text here. Click to load it

Wie viele Bytes musst Du denn hashen? Ich habe mich gerade mal
hingesetzt und den SHA-1-Hash für einen Block (max. 55 Bytes) mit
avr-gcc implementiert. Das ist jetzt nicht großartig optimiert und
braucht ca. 1.5kByte Flash, knapp 100 Bytes RAM und ca. 60000 Takte für
einen Block.

CU Christian
--
Christian Zietz  -  CHZ-Soft  -  czietz (at) gmx.net
WWW: http://www.chzsoft.com.ar /
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
Ich schrieb:

Quoted text here. Click to load it

Ich habe weiter programmiert und habe jetzt SHA-1 für beliebige
Datenmengen auf einem AVR laufen. (Voraussetzung: Daten liegen in einem
Stück vor oder können - ggf. mit Ausnahme des letzten Blocks - in
Blöcken von konstant 64 Bytes Länge geliefert werden.)
Das ganze bei einem Verbrauch von vielleicht 1.8kBytes Flash, 120 Bytes
RAM und bei weiterhin ca. 60000 Taktzyklen pro Block, was bei 8MHz einem
Durchsatz von gut 8kByte/s entspricht.

CU Christian
--
Christian Zietz  -  CHZ-Soft  -  czietz (at) gmx.net
WWW: http://www.chzsoft.com.ar /
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash

[SHA-1 Implementierung]
Quoted text here. Click to load it

Wow, das ist GROßARTIG!

Vielen Dank erstmal für den Tipp mit der Diplomarbeit, die ich gleich
ausgedruckt und verschlungen habe. Tolle Sache, dass Diplomarbeiten
veröffentlicht werden, das findet man leider nicht so oft.

Zu deiner Implementierung: ich hätte gedacht, dass SHA-1 noch
aufwendiger als MD5 ist - dass du so ein gutes Ergebnis bekommst, ist
beeindruckend. Hast du das in Assembler geschrieben oder in C? Ist die
32 Bit-Emulation wirklich so schlecht?

Veröffentlichst du deinen Code? Unter welche Lizenz wirst du ihn stellen?

Viele Grüße,
Johannes

--
durch dei Verdunstung kült das sogar ziemlich gut
das ist wie schweiß. Hünde müssen da hecheln so wie Lüfter.
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
On Wed, 20 Sep 2006 23:33:42 +0200, Johannes Bauer

Quoted text here. Click to load it

32-Bit ist für einen 8-Bit Prozessor immer schlechter als 8-Bit. Für
solche Aufgaben solltest Du dir die Listings des Compilers anschauen.
Dort sieht man sehr schnell, wo man optimieren kann. Ich habe damals
ein Programm mit 22kB nur durch Optimierungen auf 14kB gebracht. Und
das ohne alles neu zu schreiben oder etwas wegzulassen. Wenn Du z.B.
20 mal auf ein Element eines Arrays zugreifst, kannst Du auch gleich
einen Pointer direkt auf das Element erzeugen. Das spart jedesmal die
Addition des Indexes und wird z.B. häufig bei einem Array aus Structs
verwendet. Ganz nebenbei ist eine Speicheroptimierung meistens auch
eine Geschwindigkeitsoptimierung.

Gruss,
Florian

Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
Johannes Bauer schrieb:

Quoted text here. Click to load it

Ich habe nun kein MD5 zum Vergleich programmiert, aber wenn ich mir
dessen Implementation angucke, sieht es nicht weniger aufwendig aus. Nur
die Anzahl der Runden ist geringer. Dafür wird eine Tabelle mit
Sinus-Werte benötigt, die ich bei der Implementierung auf einem uC
vorberechnen würde. Das braucht dann halt zusätzlich Flash.

Quoted text here. Click to load it

Ich habe es in C geschrieben und natürlich laufen 32-bit-Berechnungen
auf einem 8-bit-uC nicht besonders effektiv. Es gibt in meinem Code
Stellen, an denen ich zugunsten eines niedrigen Speicherverbrauchs (ROM
oder RAM) auf etwas Performance verzichtet habe. Ein C- oder gar
AVR-Assembler-Guru könnte sicherlich noch mehr herausholen. (Obwohl der
avr-gcc schon ziemlich gut optimiert.)

Quoted text here. Click to load it

Lizenzmäßig habe ich mich bisher nicht festgelegt. Wofür brauchst Du
das? Ich bin mir sicher, dass wir uns einig werden können. Es ist halt
so, dass ich kein Problem habe, ein Hobby-/Uni-Projekt kostenlos zu
unterstützen, aber bei einer kommerziellen Verwendung schon gerne eine
ideelle oder materielle Anerkennung hätte.
Wenn Du das lieber per Mail besprechen möchtest: czietz (at) gmx.net

CU Christian
--
Christian Zietz  -  CHZ-Soft  -  czietz (at) gmx.net
WWW: http://www.chzsoft.com.ar /
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash

Quoted text here. Click to load it

Es geht immernoch um das Getränkeautomaten-Projekt, ein freies Projekt
von mir, das ich nach Abschluß unter die GPL stellen werden (inkl.
Dokumentation und vollem Sourcecode).

Nichts komerzielles also. Mach ich nur zum Spaß an der Freude. Und weil
hier genug technisch versierte, verspielte Studenten herumlaufen, ist
eine Man-in-the-Middle-Attacke auf den Automaten nicht auszuschließen -
weswegen ich einen Authentifikationsmechanismus benutze, der eine
kryptografische Hashfunkion benutzt; overkill vielleicht ein bischen
aber ziemlich cool ;-)

Viele Grüße,
Johannes

--
durch dei Verdunstung kült das sogar ziemlich gut
das ist wie schweiß. Hünde müssen da hecheln so wie Lüfter.
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
Johannes Bauer schrieb:

Quoted text here. Click to load it

OK, ich habe kein Problem damit, auch meinen Code unter die GPL zu
stellen. Gib mir noch ein paar Stunden Zeit, ein paar Worte Doku zu
tippen, dann stelle ich es online.

CU Christian
--
Christian Zietz  -  CHZ-Soft  -  czietz (at) gmx.net
WWW: http://www.chzsoft.com.ar /
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash

Quoted text here. Click to load it

*freu* Vielen Dank, Christian!

Grüße,
Johannes

--
durch dei Verdunstung kült das sogar ziemlich gut
das ist wie schweiß. Hünde müssen da hecheln so wie Lüfter.
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
Ich schrieb:

Quoted text here. Click to load it

So. Solange bis ich das Teil in meine Webseite integriert habe, findet
sich meine GPL SHA-1 Implementierung inkl. engl. Doku unter
http://www.chzsoft.com.ar/storage/sha1.zip .

Noch ein paar Hinweise: Es gibt (kleinere) Einschränkungen, näheres
steht in README. Das Teil ist nicht besonders optimiert, das überlasse
ich gerne anderen. Und ich übernehme keine Garantie.

CU Christian
PS: Johannes, berichte mal, wenn der Getränkeautomat fertig ist.
--
Christian Zietz  -  CHZ-Soft  -  czietz (at) gmx.net
WWW: http://www.chzsoft.com.ar /
We've slightly trimmed the long signature. Click to see the full one.
Re: AVR-GCC/GAS MD5-Implementierung oder anderer Hash
Ich schrieb:

Quoted text here. Click to load it
[...]

OK, die neue Download-Adresse ist jetzt
http://www.chzsoft.com.ar/cms/downloads/sha1.zip .
Ich habe noch eine kleinere Erweiterung vorgenommen: Ein
Compilerschalter erlaubt es, optional eine Version (mit leicht erhöhtem
Flash- und RAM-Verbrauch) zu erzeugen, die mehr als 64kiB hashen kann.

CU Christian
PS: Wow, 37 Downloads bisher!
--
Christian Zietz  -  CHZ-Soft  -  czietz (at) gmx.net
WWW: http://www.chzsoft.com.ar /
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline