www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Kleiner XTEA in C (ohne 32 bit)?


Autor: Dietmar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hat jemand eine XTEA-Decipher-Funktion in C, die ohne 32bit-Int 
auskommt? Die drei Zeilen in der for-Schleife unten machen einen 
ATMega-Bootloader leider um 400 Bytes grösser.

// decode 64 bit of data (XTEA with 32 rounds)

#define XTEA_ROUNDS 32
#define XTEA_DELTA  0x9E3779B9

void
decipher(uint32_t v[2])
{
    // 128 bit XTEA key

    static const uint32_t k[4] =
    {
        0x00000000,
        0x00000000,
        0x00000000,
        0x00000000
    };

    uint32_t sum = (XTEA_DELTA * XTEA_ROUNDS);
    uint32_t v0  = v[0];
    uint32_t v1  = v[1];
    uint8_t  i;

    for (i = 0; i < XTEA_ROUNDS; i++)
    {
        v1  -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + k[(sum>>11) & 
3]);
        sum -= XTEA_DELTA;
        v0  -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + k[sum & 3]);
    }

    v[0] = v0; v[1] = v1;
}

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kann nur mit Assembler aushelfen. Dann benötigst du ca. 70 Opcodes = 140 
Bytes. Siehe hier Beitrag "Re: AVR-Bootloader mit Verschlüsselung"
Beachte auch das XTEA eine Blockverschlüsselung ist du benötigst also 
auch einen Ciphermode der über ein Feedback Register den vorherigen 
Block mit dem aktuellen XOR verknüpft. Ansonsten ist es nicht 
cryptographisch sicher. Mein Bootloader benutzt sogar einen 
Doppel-CBC-Feedback-Modus um eine CMAC und 
Alles-Oder-Nichts-Entschlüsselung hinzubekommen um die Authentizität und 
Integrität der entschlüsselten Daten überprüfen zu können.

Gruß Hagen

Autor: Jörg G. (joergderxte)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Welchen Compiler verwendest du? (Falls GCC: an "-Os" und "-lm" 
gedacht?).
Bringt es was, wenn du die k-Indexe mit 'passenderen' Datentypen 
berechnest:
//statt:
/*...*/ (sum + k[(sum>>11) & 3]);
//evtl.:
(sum + k[ ((uint16_t)sum>>11) & 3 ]);
// oder sogar ('sollte' aber nichts mehr bringen):
(sum + k[ (uint8_t)((uint16_t)sum>>11) & 3 ]);
Sonst poste eben den (erzeugten!) Assemblercode, vl. faellt da was ins 
Auge

hth, Jörg

Autor: Dietmar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Jörg: -lm und -Os werden benutzt. Die vorgeschlagenen Casts sind IMHO 
falsch (das sind 32 bit, die um 11 bit verschoben werden - danach sind 
es immer noch mehr als 16 bit).

@Hagen:
- Assemböer-Code verstehe ich leider nicht.
- Ist das XOR-Verknüpfen die Sahnehaube oder wird der Algorithmus ohne 
diesen Schritt nennswert unsicher?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
400 Bytes durch C erzeugten Code ist schon realistisch. Das wird man 
substantiell nur duch Verwendung von handmade Assembler verbessern 
können. Und selbst in Assembler wird man minimal 140 Bytes benötigen. 
Meine XTEA Assembler Routine habe ich schon optimiert und ich sehe keine 
essentiellen Verbesserungsmöglichkeiten mehr. Bei dieser Routine käme in 
einem C Code noch der Overhead hinzu die Register zu sichern und die 
Parameter zu laden.

Gruß Hagen

Autor: Maxxie (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es ist die Grundlage des Algorithmus (Wie eigentlich bei den meisten 
modernen symetrischen cyphern)
XOR verwendest du in deinem C Code doch auch: ^

Autor: Jörg G. (joergderxte)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>@Jörg: -lm und -Os werden benutzt. Die vorgeschlagenen Casts sind IMHO
>falsch (das sind 32 bit, die um 11 bit verschoben werden - danach sind
>es immer noch mehr als 16 bit).
Aber das ist der index für ein Array mit 4 Elementen , nach dem Shift 
sind auch von 16 Bits noch genug für den Index übrig

scnr, Jörg

Autor: Dietmar (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Es ist die Grundlage des Algorithmus

Es ging nicht um xor im XTEA, sondern um xor der verschlüsselten 64 
bit-Pakete. Ich nehme an, das soll Known-Plaintext-Atacken verhindern?

> Aber das ist der index für ein Array mit 4 Elementen , nach dem Shift
sind auch von 16 Bits noch genug für den Index übrig

Wenn das der Gedanke war, war IMHO die Klammerung falsch. Nicht 
((uint16_t)sum>>11), sondern: (uint16_t)(sum>>11).

Sicher bin ich mir aber nicht, da ich in solchen Fällen immer Klammern 
setze.

So der so, das bringt nichs. Der Code wird sogar länger - vmtl. weil 
irgendeine Optimierung verhindert wird.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>- Ist das XOR-Verknüpfen die Sahnehaube oder wird der Algorithmus ohne
>diesen Schritt nennswert unsicher?

Es ist ein Muß.
Angenommen du benutzt XTEA so wie er ist auf eine 256 Bytes Nachricht 
dann wird durch den XTEA diese 256 Bytes in Blöcke a 8 Bytes getrennt 
voneinander verschlüsselt. Nun gehen wir von folgendem Scenario aus:
Bootloader-Software mit immer gleichen Schlüssel verschlüsselt auf diese 
Weise 10 Programme a 256 Bytes. Ein Angreifer hat nur diese 
verschlüsselten Daten zu Hand aber das Wissen was du gemacht hast. Er 
weis auch das in den ersten 8 Bytes der Programm exakt die Elemente des 
Progammes drinnen stehen die er verändern möchte. Er kann nun ohne 
Probleme die Blöcke der 10 Programme untereinander austauschen und somit 
sein eigenes Program zusammenbauen.

Noch dramatischer wird es wenn wir davon ausgehen würde das es 
verschlüsselte Banküberweisungen sind. Im ersten 8 Bytes Block steht die 
Kontonummer des Empfängers einer Überweisung. Ein Angreifer veranlasst 
dich ihm auf sein Konto Geld zu überweisen und fängt ansonsten jede 
verschlüsselte Bankwüberweisung ab. Nun tauscht er eifach bei jeder 
dieser Überweisungen den ersten 8 Bytes verschlüsselten Datenblock aus 
schwups gehen alle Geldüberweisungen auf sein Konto. Er knackt also 
garnicht den XTEA Algorithmus noch den benutzten Schlüssel sondern 
einfach das benutzte Verfahren wie XTEA kryptographisch falsch benutzt 
wurde.

In meiner Bootloader-Verschlüsselung habe ich das so umgesetzt:
Doppel-CBC-Mode: Die verschlüsselten Daten des letzten Blockes werden 
mit den unverschüsselten Daten des aktuellen Blockes XOR verknüpft. Nun 
wird dieser Block mit XTEA verschlüsselt aber nur die halbe 
Rundenanzahl. Jetzt wird nochmals der aktuelle teilverschlüsselte XTEA 
Datenblock xor-verknüpft mit den verherigen Daten=8 Byte Feedback 
Register. Nun wird die restliche Hälte an Runden mit XTEA verschlüsselt. 
Im Abschlüss wird der verschlüsselte Datenblock in das Feedback Register 
per XOR-Verküpfung eingearbeitet, nicht durch eine einfache 
Kopieroperation. Somit haben wir eine mehrfache Verknüpfung, auch des 
internen Zwischenzustandes der XTEA Verschlüsselung mit einem 
Feedbackregister das über die Datenblöcke hinweg diese fest miteinander 
verbindet. Im Feedback Register entsteht also ein binärer Wert der 
abhängig ist von allen unverschlüsselten Datenblöcken, aller final 
verschlüsselten Datenblöcke und sogar den teilverschlüsselten 
Datenblöcken und damit direkt vom internen Zustandsregister des XTEAs. 
Das alles ist abhängig vom Passwort.

Würde man nun im Ciphertext das höchstwertigste Bit, also das 1. 
Datenbit umkippen und das dann entschlüsseln dann wäre die komplette 
entschlüsselte Nachricht über alle Datenblöcke hinweg zerstört. Also 
eine Alles-Oder-Nichts-Entschlüsselung.

Baut man vor die Daten nun noch 8-16 Bytes Zufall und verschlüsselt 
diese mit den Daten in einem Rutsch dann würde eine Randomisierung des 
Ciphertextes erfolgen. Das ist sowas wie ein externer 
IV=Initialisierungsvektor der aber verschlüsselt ist. Ein und die selbe 
Nachricht mit dem gleichen Passwort mehrfach verschlüsselt würde also 
immer einen komplett anderen Ciphertext ergeben. Logisch da alle 
nachfolgenden Datenblöcke auch vom Inhalt aller vorherigen Datenblöcke 
abhängig verschlüsselt wurden.

Hängt man nun hintendran an die Daten vor der Verschlüsselung eine 
geheime Signatur, zb. 4 Bytes des Passwortes dann hat man damit eine 
CMAC = Cipher Message Authentication. Durch die 
Alles-Oder-Nichts-Entschlüsselung, also die vollständige Propagation von 
Bitfehlern oder Manipulationen am Ciphertext, bzw. die vollständige 
Propagation aller Datenbits der vorherigen Datenblöcke in alle 
nachfolgenden Datenblöcke, wird also auch diese Signatur in einem 
solchen Fall komplett falsch entschlüsselt. Man hat also quasi eine 
kryptograhpisch geschützte Prüfsumme über alle Daten inklusive. 
Normalerweise mürde man mit einer sicheren Hashfunktion einen solche 
"Prüfsumme" erzeugen und diese dann mitliefern. Das kostet aber 
zusätzliche Resourcen im AVR und meine Veränderungen mit dem 
Doppel-CBC-Feedback-Modus ist dagegen fast geschenkt.

Alles in allem macht erst dies eine handvoll krypologischer Angriffe 
unmöglich, Choosen-Plain/Ciphertext Attacks, Reply-Attacks, 
Known-Plaintext-Attacks, Differientielle Kryptoanalyse usw. Gegen all 
diese Verfahren sind Blockverschlüssellungen im ECB Ciphermode (das was 
du vor hattest) nicht resistent.

Und wir haben mit einfachsten Mitteln auch noch eine CMAC. Wir können 
also feststellen ob was schief gegangen ist. Sowohl ob das Passwort das 
benutzt wurde korrekt ist (ohne es zusätzlich zu kompromittieren!), wie 
auch Bitfehler in der Datenübertragung und eben absichtliche 
Manipulationen. Dazu notwendig sind alle oben beschriebenen 
Bestandteile: also Zufallsseed von 8-16 Bytes am Anfang der Daten, der 
Doppel-CBC-Mode und die Teilsignatur bestehend aus dem geheimen Passwort 
am Ende der Daten die dann als eine Nachricht in einem Rutsch 
verschlüsselt werden.

Das alles inklusive ohne zusätzliche kryptographische Funktionen, die 
Resourcen verbrauchen, benutzen zu müssen.

Nicht umsonst habe ich in meinem Bootloader-Thread die Behauptung 
aufgestellt das man nach meinem Wissenstand diesen nur durch Reverse 
Engineering auf Chip Ebene knacken könnte :)

Gruß Hagen

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.