Threefish

Threefish
Struktur einer Runde von Threefish
Entwickler	Bruce Schneier, Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
Veröffentlicht	2008
Schlüssellänge	256, 512 oder 1024 Bits (Die Schlüssellänge ist immer gleich der Blockgröße)
Blockgröße	256, 512 oder 1024 Bits
Runden	72 für 256-Bit Blockgröße 72 für 512-Bit Blockgröße 80 für 1024-Bit Blockgröße

Threefish ist eine Blockverschlüsselung, entwickelt als Teil der kryptographischen Hashfunktion Skein, welche am NIST-Auswahlverfahren zu SHA-3 teilnahm. Um zeitliche Seitenkanalattacken (Rechenzeitangriffe) zu erschweren, verwendet Threefish keine S-Boxen oder andere Lookup-Tabellen. Die notwendige Nichtlinearität wird nur durch die Addition realisiert.^[1]

Ein Teil des Entwicklungsteams arbeitete bereits beim Entwurf der Blockverschlüsselungen Twofish und Blowfish zusammen, die allerdings eine andere Struktur aufweisen.

Threefisch ist eine sogenannte ARX-Chiffre, da sie nur Additionen, Rotationen mit konstanter Weite und XOR-Verknüpfungen als kryptografische Primitive verwendet.

Threefish ist eine sogenannte tweakable Blockverschlüsselung, was bedeutet, dass über einen zusätzlichen Steuereingang die Art der Permutationen in gewissem Umfang verändert werden kann. Der Tweak hat dabei eine ähnliche Funktion wie ein Initialisierungsvektor oder ein Nonce, kann öffentlich sein und schneller gewechselt werden als der Schlüssel. Dies erlaubt bei zeitkritischen Anwendungen wie Festplattenverschlüsselungen, jeden Datenblock unterschiedlich zu verschlüsseln, ohne dass dies zu Lasten des Datendurchsatzes geht, während bei vielen Blockchiffren die Änderung des Primärschlüssels vergleichsweise zeitaufwändig ist.

Ein Datenblock besteht aus 4, 8 oder 16 Wörtern von je 64 Bit. In jeder Runde werden Paare von zwei Wörtern aus je einer von zwei Blockhälften durch die MIX-Funktion modifiziert, und anschließend werden die Wörter innerhalb jeder Blockhälfte permutiert, so dass jedes Wort in der nächsten Runde für die MIX-Operation mit einem anderen gepaart wird. Die MIX-Funktion besteht aus den elementaren Operationen Addition modulo 2 64 {\displaystyle 2^{64}} , Bitrotation und XOR-Verknüpfung:

B ← B + A ; A ← A ⋘ R i , j ; A ← A ⊕ B {\displaystyle B\leftarrow B+A;\;\;A\leftarrow A\lll R_{i,j};\;\;A\leftarrow A\oplus B}

Die Rotationsweite R i , j {\displaystyle R_{i,j}} hängt von der Runde und vom Wortpaar ab und folgt einem Muster, das sich alle acht Runden wiederholt. Die Wortpermutation ist in jeder Runde gleich. Nach immer vier Runden, und auch vor der ersten Runde, wird zu jedem Blockwort ein Rundenschlüssel-Wort addiert.

Die Schlüsselgröße ist gleich der Blockgröße, und der Tweak besteht unabhängig davon aus zwei Wörtern. Zur Schlüsseleinteilung wird zuerst ein zusätzliches Schlüsselwort berechnet, indem alle Schlüsselwörter und eine Konstante miteinander XOR-verknüpft werden, und ein drittes Tweak-Wort wird durch XOR der beiden gegebenen gebildet. Jeder Rundenschlüssel besteht aus 4, 8 bzw. 16 der Schlüsselwörter, die von einem zum nächsten Rundenschlüssel durchrotiert werden, d. h. für jeden Rundenschlüssel wird ein anderes Wort weggelassen. Zum letzten Wort des Rundenschlüssels wird die Rundennummer addiert. Zum zweit- und drittletzten Rundenschlüsselwort wird je ein Tweak-Wort addiert; die drei Tweak-Wörter werden ebenfalls durchrotiert, so dass jedes Mal zwei andere angewandt werden.

Im Zuge des SHA-3-Wettbewerbs wurden von den Entwicklern zwei Änderungen vorgenommen. Für Skein Version 1.2 wurden die Rotationsweiten der MIX-Funktion geändert, um die Diffusionseigenschaften zu verbessern. Für Version 1.3 wurde die Konstante geändert, die bei der Schlüsseleinteilung mit den Schlüsselwörtern XOR-verknüpft wird, um eine bestimmte Angriffsmethode gegen ARX-Chiffren (englisch rotational cryptanalysis) zu erschweren.

Implementierung von Threefish (neueste Version) mit 256 Bit Blockgröße in C++:

#include <stdint.h>
typedef uint64_t U64;

static inline void mix(U64 &a, U64 &b, int r) {
	b += a; a = a << r | a >> (64-r); a ^= b;
}

void tf_256(U64 b[4], const U64 key[4], const U64 tw[2], unsigned c = 9) {
   U64 t[3] = { tw[0], tw[1], tw[0] ^ tw[1] };
   U64 k[5]; k[4] = 0x1BD11BDAA9FC1A22;
   for (int i=0 ; i<4 ; ++i) k[4] ^= k[i] = key[i];
   const unsigned g = 2*c; // Zahl der Runden = 8*c
   for (unsigned s=0 ;;) {
     // Addiere Schlüssel, Tweak und Rundennummer:
      b[0] += k[0]; b[1] += k[1] + t[0];
      b[2] += k[2] + t[1]; b[3] += k[3] + s++;
      if (s > g) break;
     // vier Runden:
      mix(b[1], b[0], 14); mix(b[3], b[2], 16);
      mix(b[3], b[0], 52); mix(b[1], b[2], 57);
      mix(b[1], b[0], 23); mix(b[3], b[2], 40);
      mix(b[3], b[0],  5); mix(b[1], b[2], 37);
     // Addiere Schlüssel und Tweak um 1 Wort rotiert und Rundennummer:
      b[0] += k[1]; b[1] += k[2] + t[1];
      b[2] += k[3] + t[2]; b[3] += k[4] + s++;
     // Rotiere Schlüssel und Tweak je um 2 Wörter:
      U64 h = k[0]; k[0] = k[2]; k[2] = k[4];
      k[4] = k[1]; k[1] = k[3]; k[3] = h;
      h = t[2]; t[2] = t[1]; t[1] = t[0]; t[0] = h;
     // vier Runden:
      mix(b[1], b[0], 25); mix(b[3], b[2], 33);
      mix(b[3], b[0], 46); mix(b[1], b[2], 12);
      mix(b[1], b[0], 58); mix(b[3], b[2], 22);
      mix(b[3], b[0], 32); mix(b[1], b[2], 32);
	}
}

1. ↑ Ferguson et al: The Skein Hash Function Family. (PDF; 479 kB) 1. Oktober 2010, archiviert vom Original (nicht mehr online verfügbar) am 24. August 2014; abgerufen am 28. März 2013.