Kryptographie für Arduino

Nachdem ich nun letztens meinen kleinen Arduino-Speichermanager fertig gestellt habe, geht es nun darum, etwas produktives damit anzufangen. In meinem Fall lag das erste Hauptaugenmerk auf kryptographischen Algorithmen - das heißt: Verschlüsseln und Hashen. Dabei musste ich natürlich immer den Speicher im Auge behalten.

Um es mir nicht ganz so schwer zu machen, begann ich mit einer einfachen Übung: der Implementierung der Base64-Encodierung. Das kannte ich bereits. Bei Base64 geht es im Grunde um folgendes: Normalerweise kann ein Computer nur eine begrenzte Anzahl an Zeichen ordentlich darstellen - die sogenannten druckbaren Zeichen. Im Fall von ASCII (das fast alle Rechner in abgewandelter Form beherrschen), sagt Wikipedia hierzu folgendes:

Die Zeichenkodierung definiert 128 Zeichen, bestehend aus 33 nicht druckbaren sowie 95 druckbaren. Letztere sind, beginnend mit dem Leerzeichen:

 !"#$%&'()*+,-./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~

Das Problem beim Hashen und Verschlüsseln ist nun, dass die Ausgabe im gesamten Zeichenbereich von #0 bis #255 verstreut ist. Computer können das in der Regel nicht ordentlich darstellen. Man erhält dann diese lustige Darstellung mit leeren Boxen und umgedrehten Fragezeichen.
Aus diesem Grund sorgt Base64 dafür, dass der nicht-druckbare Text in druckbaren Text umgewandelt wird. Genauer gesagt: Statt aller 256 Zeichen, die ein Byte darstellen könnte, werden nur 64 Zeichen verwendet. Damit wird das Ergebnis (um 33%) länger, aber dafür lesbar!

1
2
CHUNK encode_base64(CHUNK input);
CHUNK decode_base64(CHUNK input);

Die Anwendung ist relativ einfach. Mit encode_base64() enthält man den Base64-encodierten Text und mit decode_base64() erhält man wieder den Ursprungstext (hier gibt es die Headerdatei und die Sourcedatei).
Base64 wird übrigens zum Beispiel verwendet, um die Anhänge in E-Mails zu encodieren. Da IMAP, POP3 und SMTP (die Protokolle, mit denen E-Mails standardmäßig übertragen werden) Textprotokolle sind, kann man dort nicht einfach irgendwelche Binärdaten hineinkippen. Aus diesem Grund enstand MIME, das u.a. Base64 als Datenencodierung vorsieht. 🙂

Gut, als nächstes brauchte ich einen Hashalgorithmus. Ich habe lange überlegt, welchen ich genau benutze, habe mich dann aber schlussendlich für SHA-1 entschieden (ja, es gibt mit der SHA-2 Familie inzwischen bessere Alternativen - diese benötigen jedoch auch wesentlich mehr Speicher).
Bei so einem Hashalgorithmus geht es schlussendlich darum, eine Eingabe mit belieber Länge zu nehmen und in eine Ausgabe mit fixer Länge zu überführen. Dabei legt man besonderen Wert darauf, dass diese Überführung bestimmte Kriterien erfüllt. Darunter zum Beispiel die Anforderung, dass man aus dem Ergebnis der Funktion keinen Rückschluss darauf ziehen kann, was denn die Eingabe (oder Teile davon) gewesen ist. Es soll zudem sehr schwer sein, zwei Eingaben zu finden, die zur gleichen Ausgabe führen (sogenannte Kollisionen) und bei der kleinsten Änderung der Eingabe soll sich dies sehr deutlich in der Ausgabe widerspiegeln (der sogenannte Avalance-Effekt).

1
2
CHUNK hash_sha1(CHUNK input);
CHUNK hmac_sha1(CHUNK input, CHUNK password);

Die Verwendung der eigentlichen Hashfunktion ist denkbar einfach. Man übergibt der Funktion hash_sha1() seinen Input und erhält als Output den Fingerprint (der bei SHA-1 immer genau 20 Zeichen lang ist). Darüber hinaus habe ich noch eine andere nützliche Funktion implementiert: hmac_sha1() (hier findet ihr die Headerdatei und die Sourcedatei).
Bei einem MAC handelt es sich um eine Möglichkeit, die Korrektheit einer Nachricht zu überprüfen. Ein HMAC in unserem speziellen Fall macht dies, indem die Nachricht und ein geheimer Schlüssel genommen und beides zusammen gehasht wird. Jemand, der die Nachricht erhält und den geheimen Schlüssel kennt, kann überprüfen, ob der HMAC zur erhaltenen Nachricht passt.

Auf Basis von HMACs werden zum Beispiel sehr gerne Challenge-Response-Verfahren realisiert. Dabei wird bei der Passwortabfrage nicht einfach das Passwort an den Server geschickt, sondern der Server schickt eine Challenge (eine zufällige Zahl). Derjenige, der sich einloggen will, erzeugt nun einen HMAC aus dieser zufälligen Zahl und seinem Passwort und schickt dem Server das Ergebnis zu. Da auch der Server das Passwort kennt, kann er aus der Zufallszahl und dem Passwort ebenfalls den HMAC bilden. Stimmen sein Ergebnis und das zugesandte Ergebnis überein, ist sichergestellt, dass der Nutzer das richtige Passwort kennt.

Bleibt noch das Thema Verschlüsselung übrig. Hier habe ich mich nach langem hin und her für Arc4 entschieden. Dabei handelt es sich um einen eigentlich proprietären Algorithmus, dessen Struktur jedoch Mitte der 90er im Usenet veröffentlicht wurde und seitdem unter dem Namen "Arc4" oder "Arcfour" weite Verbreitung gefunden hat. Dieser Algorithmus hat einen Nachteil, den ich gleich näher erläutere.

1
2
CHUNK encrypt_arc4(CHUNK input, CHUNK password);
CHUNK decrypt_arc4(CHUNK input, CHUNK password);

Auch hier sollte die Verwendung einleuchtend sein. encrypt_arc4() übergibt man seine Nachricht und sein Passwort und erhält anschließend seine verschlüsselte Nachricht. decrypt_arc4() überreicht man die verschlüsselte Nachricht und das gleiche Passwort und erhält wieder den Klartext. Soweit so einfach (hier ist die Headerdatei und hier die Sourcedatei).
Wie jedoch schon gesagt, hat Arc4 ein Problem, das durch seine einfache Struktur zu erklären ist. Im Grunde ist Arc4 nichts weiter als ein großer Pseudo-Zufallsgenerator. Das heißt, dass anhand des Passwortes ganz viele "zufällige" Bytes erzeugt werden und die Bytes der Nachricht mit diesen "zufälligen" Bytes geXORt werden. Das Verfahren selbst ist nicht unsicher, weist jedoch eine Besonderheit auf: Verschlüsselt man zwei Nachrichten mit dem gleichen Passwort und XORt die beiden verschlüsselten Nachrichten, so erhält man als Ergebnis die unverschlüsselten Nachrichten geXORt. Um das mal zu verdeutlichen: Der Zufallsgenerator von Arc4 erzeugt ganz viele Schlüsselbytes k_i (Schlüsselbyte k an Position i). Für jedes Byte der unverschlüsselten Nachricht n_i (Nachrichtenbyte n an Position i) wird ein Byte der verschlüsselten Nachricht c_i (verschlüsseltes Nachrichtenbyte c an Position i) erzeugt. Nämlich durch c_i = n_i XOR k_i

Wenn man nun also eine verschlüsselte Nachricht c_i = n_i XOR k_i und eine verschlüsselte Nachricht d_i = m_i XOR k_i abgefangen hat und diese beiden XORt, dann folgt daraus z_i = c_i XOR d_i = m_i XOR k_i XOR n_i XOR k_i = m_i XOR n_i

Der Schlüsselstrom k_i kürzt sich also einfach raus und übrig bleiben die beiden Ursprungsnachrichten. Das ist erstmal eine unerfreuliche Information. Das positive ist, dass man dieses Problem relativ einfach umgehen kann, nämlich, indem man dafür sorgt, dass die verwendeten Passwörter nie identisch sind. Das geht zum Beispiel über einen sogenannten Nonce (= "number used once"). Das ist eine zufällige Zahl, die nur ein einziges Mal verwendet werden darf. Wenn ihr nun Arc4 nicht direkt mit eurem Passwort verwendet, sondern erst per hmac_sha1(Nonce, Passwort) das eigentliche Passwort für Arc4 ermittelt, seid ihr auf der sicheren Seite.

cryptu.ino in Aktion cryptu.ino in Aktion

cryptu.ino in Aktion

Um abschließend einmal zu zeigen, wie das ganze nun in Aktion aussehen könnte, habe ich mit cryptu.ino ein kleines Beispielprojekt implementiert. Es bietet euch die Möglichkeit, zwischen verschiedenen Modus hin- und herzuschalten. Mit "!help" seht ihr, was ihr alles auswählen könnt.

Ich hoffe, euch hat der kleine Ausflug in die Welt der Kryptographie gefallen. Für Fragen, Ideen, Anregungen und Kritik bin ich wie immer jederzeit zu haben. 🙂
Kryptographische Grüße, Kenny

P.S.: Für den Fall, dass Arc4 nicht das Mittel der Wahl ist, gucke ich mir derzeit nebenbei noch IDEA an - das jedoch nur mit einer geringeren Priorität. 😉

4 Kommentare » Schreibe einen Kommentar

  1. Vorschlag:
    -hänge an beide(!) Arduinos eine RTC.
    -nimm als PW dann z.B. "aktuelle Stunde+Wochentag+Monat+Minute+TagDerWoche+Text"
    -wenn Du dann pro Minute nur eine Übertragung fährst, ist das PW immer ein anderes.
    (Sekunde geht natürlich auch, dann müssen die RTCs aber wirklich die gleiche Uhrzeit haben.)

    Bei der Übertragung der Wetterdaten vie DCF77-Funkuhrsignal wird ganz ähnlich verfahren ....

    • Ich muss gestehen, dass ich nicht so wirklich verstehe, worauf sich dieser Vorschlag bezieht? Im oben stehenden Artikel geht es um kryptographische Algorithmen, nicht um das Auswählen von Passwörtern.

    • Oh, das ist offenbar nicht so gut heraus gekommen. Der Typ gehört zum Speichermanager.

      Die neuste Version von allem kriegt man übrigens hier.

      Eine Kopie kann man sich z.B. mit Mercurial ziehen, indem man folgenden Befehl ausführt:

      1
      hg clone http://hg.nhg.name/arduino/cryptuino/

Schreibe einen Kommentar

Um Ihnen beim weiteren Kommentieren auf dieser Webseite die erneute Eingabe Ihrer Daten zu ersparen, wird beim Absenden Ihres Kommentars ein Cookie an Ihren Browser gesendet und von diesem gespeichert. Mit dem Absenden eines Kommentars auf dieser Webseite stimmen Sie der Speicherung und Übertragung dieses Cookies explizit zu.

Pflichtfelder sind mit * markiert.