Zukunftsträchtige Algorithmen...

[enkore]

Hi Leute,
für mein Projekt CEXP würde ich gerne ein oder zwei SHA-3 Kandidaten implementieren. Ich denke mal, dass da eh nur die akpzeptabel sind, die es in Runde 2 geschafft haben, und bei denen keine Schwächen bis jetzt bekannt sind.
Nur welche sollte ich da am besten nehmen?
Ich fände Skein ganz interessant, allein schon wegen der Geschwindigkeit ("The authors claim 6.1 cycles per byte for any output size on an Intel Core 2 Duo in 64-bit mode.") Keccak wäre vielleicht auch noch was.
Was meint ihr?

 

[Elderan]

Hallo,
also im produktivem Einsatz sollte man noch keinen SHA-3 Kandidaten nehmen, da man nicht vorhersehen kann, was sich noch alles so ergeben wird. Ebenso sind die Chancen, dass der implementierte Algorithmus wirklich zum SHA3 Standard wird eher gering, zusätzlich da auch eine Reihe von Algorithmen Verbesserungen (Tweaks) für den Algorithmus angemeldet haben, die noch bis (ich mein) mitte September eingereicht werden können.

Es ist auch noch gar keinen Grund, bereits auf einen der SHA-3 aufspringen zu wollen. SHA-2 tut weiterhin gut seine Dienste und wenn einem Kollisions-Resistenz egal sein kann (z.B. PW Hashing), ist auch weiterhin SHA-1 oder gar MD5 verwendbar.


Ansonsten, wenn man es rein aus Interesse implementieren möchte:
Skein ist sehr schön in der Implementierung. Threefish zu implementieren ist sehr einfach, bischen unbequemer wird es dann bei UBI und dem Konfigurationsblock, da man da sehr genau auf die Vorgaben achten muss, an welcher Bitposition welche Information steht.
Ansonsten halte ich die Aussichten von Skein für doch recht gut. Aber ob Skein es wird, und ja in welcher Form, kann jetzt keiner sagen. Da muss man einfach abwarten.

Keccak ist vom Konzept und vom Paper her sehr Lustig. Es macht einfach Spaß etwas über kryptograpische Schwämme und den Operationen Squeeze und Absorb zu lesen
Wie der zu implementieren ist kann ich leider nichts sagen. Wenn man aber Lust hat kann man es einfach ausprobieren


Sicher werden die Kandidaten in Runde 2 eigentlich alle sein für viele Anwendungsszenarien. Glaube kaum, dass ein Kandidat realistische Schwächen bzgl. Preimage-Attacken aufweisen wird.
Ob aber die Kollisionsresistenz gewährleistet ist, ist eine ganz andere Frage.


Eine Notwendig SHA3-Kandidaten zu nutzen besteht nicht, da sollte man lieber auf SHA-2 o.ä. zurückgreifen, wenn man das ernsthaft verwenden will. Spaß den ein oder anderen Kandidaten mal zu implementieren macht es aber.

Persönlich finde ich auch Edon-R vom Paper her sehr spannend. Es ist einfach mal etwas ganz anderes, nicht eine stupide Blockchiffre als Kernfunktion. Ist aber zugegeben sehr schwere Mathematik, aber wenn man das nötige Hintergrundwissen hat (und Mathe affin ist), doch mal interessant zu lesen.

 

[enkore]

Ich denke mal das bspw. CubeHash auf keinen Fall SHA-3 sein wird, weil CubeHash für heutige Verhältnisse viel zu langsam ist (über 30 Cycles/Byte)...

Auf jeden Fall danke für deinen ausführlichen Post, ich werde mich erstmal mit Skein beschäftigen.

 

[Elderan]

Hallo,
naja wenn CubeHash es auf keinen Fall werden könnte, wäre dieser nicht in die zweite Runde gekommen. NIST war schon relativ streng bei der Wahl der Kandidaten für die zweite Runde und es wurden viele Kandidaten nicht ausgewählt, aufgrund deren Performance (z.B. MD6).

Und so schlecht ist CubeHash gar nicht. Laut deren Website:
"20r/b cycles/byte on a Core 2 Duo in 64-bit mode"

D.h., CubeHash4/8 hat mit 10 Cycles/Byte doch noch eine ordentliche Performance.



Dennoch bin ich persönlich von CubeHash nicht so überzeugt. Nicht unbedingt wegen der Performance, sondern eher wegen der Sicherheit.

Aber wie gesagt: Noch ist alles offen. Es kann sein, dass morgen ein desaströse Attack auf Threefish gefunden wird und Skein somit als gebrochen gilt. Man wird es sehen

 

[enkore]

Seh' ich auch so
Perfomancemäßig schlägt allerdings Skein mit 6,1 Cycles/Byte egal in welchen Modus alles andere zu Brei. Das finde ich schon beachtlich...

Allerdings werde ich nicht (wie ich es sonst gemacht habe) Skein in Freebasic implementieren. Ich werd einfach die Referenzimplementation um die CEXP Pluginschnittstelle ergänzen und beim Release als Plugin beilegen^^ Schließlich sind das ja an die 2000 Zeilen

 

[lightsaver]

Original von Elderan
NIST war schon relativ streng bei der Wahl der Kandidaten für die zweite Runde und es wurden viele Kandidaten nicht ausgewählt, aufgrund deren Performance (z.B. MD6).

Wobei MD6 nicht rausgewählt sondern zurückgezogen wurde, da für eine performantere Variante mit weniger Cycles, welche es wohl in die 2. Runde geschafft hätte, wohl kein Sicherheitsbeweis möglich war, was wohl aber angeblich bei anderen (noch im Rennen befindlichen) Kandidaten wohl ebenfalls der Fall ist.

 

[Elderan]

Hallo,

Original von lightsaver

Original von Elderan
NIST war schon relativ streng bei der Wahl der Kandidaten für die zweite Runde und es wurden viele Kandidaten nicht ausgewählt, aufgrund deren Performance (z.B. MD6).

Wobei MD6 nicht rausgewählt sondern zurückgezogen wurde, da für eine performantere Variante mit weniger Cycles, welche es wohl in die 2. Runde geschafft hätte, wohl kein Sicherheitsbeweis möglich war, was wohl aber angeblich bei anderen (noch im Rennen befindlichen) Kandidaten wohl ebenfalls der Fall ist.

Also das MD6 Team (Rivest & Co.) haben dem NIST nur empfohlen, MD6 nicht in die nächste Runde weiterkommen zu lassen, da man MD6 wohl nicht so schnell machen kann, dass es verwendbar wäre und dennoch noch seine Sicherheitseigenschaften behält.

We are not withdrawing our submission; NIST is free to select MD6 for further consideration in the next round if it wishes. But at this point MD6 doesn't meet our own standards for what we believe should be required of a SHA-3 candidate, and we suggest that NIST might do better looking elsewhere
http://groups.csail.mit.edu/cis/md6/

Wodrauf ich aber hinaus wollte:

Einen interessanten Kommentar dazu gibt es auf dem Blog von Bruce Schneier:
http://www.schneier.com/blog/archives/2009/07/md6.html

"Do similar proofs of resistance to differential attacks available for competing hashfunctions such as skein?"

Not really, and that's what's puzzling about this whole thing.

I'm not impressed by these sorts of proofs. It's not hard to prove specific security properties about block ciphers, including resistance to differential attacks. The problem is with the model. What ends up happening is that an algorithm has a proof of security with respect to a class of attacks, and then the attacker responds with an attack that's not in that class. So any proof against differential attacks may not include everything that cryptanalysts call "differential" and certainly will not include other attacks.

Proofs of security are overrated.

Posted by: Bruce Schneier at July 1, 2009 3:01 PM

Perfomancemäßig schlägt allerdings Skein mit 6,1 Cycles/Byte egal in welchen Modus alles andere zu Brei. Das finde ich schon beachtlich...

BMW (Blue Midnight Wish) ist noch schneller


Und Skein zu implementieren ist gar nicht so aufwendig. Die Referenzimpl. ist bischen grausam und viele Zeilen Code entstehen, wenn man Threefish-256/512/1024 voll entrollt. 80 Runden und je 16 Wörter machen bei Threefish-1024 eben viele Zeilen Code aus.
Enrollt man aber nur 8 Runden, hat man einen angenehmen, schlanken Code.

 

[enkore]

Naja ich nehme für meine Zwecke einfach die Referenzimpl. und haue da meinen Plugincode dran - Reicht für mich vollkommen...
Der Vorteil ist auch, dass ich bei Tweaks dann nur ein paar Dateien ersetzen muss, ohne irgendetwas anzupassen, da ich sowieso die SHA-3 Candidate API nutze...


@Blue Midnight Wish:
Oha habs bei den Kommentaren gelesen^^ 3.63 Cycles per byte... heftig^^

Aber:

Dear all,
Blue Midnight Wish (BMW) allows pseudo-attacks---collisions and (2nd)
preimages---below the expected security levels. These are attacks where
the attacker is free to choose the IV. With respect to pseudo-attacks,
the security level of BMW-256 is reduced by roughly 64 bits, and the
security level of BMW-512 is reduced by roughly 128 bits. Memory
requirements to obtain this security reduction are negligible.
For details, see http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf.
Best regards,
/S?ren

Okay man muss den IV wählen, aber wenn man es schafft das Abfrageprogramm des Clienten zu manipulieren... ?

 

[Elderan]

Hallo,

Original von csde_rats
Okay man muss den IV wählen, aber wenn man es schafft das Abfrageprogramm des Clienten zu manipulieren... ?

dann wird die BMW-Implementierung mit keiner anderen (nicht manipulierten) BMW-Implementierung mehr kompatibel sein.

Wenn man bei AES lineare S-Boxen wählt, dann lässt sich AES auch recht trivial brechen. Aber da fragt auch keiner: Was ist, wenn man das Programm des Client manipuliert?
Oder: Was ist, wenn man die Skein Implementierung so abändert, dass Threefish nur mit 4 statt mit 72 Runden betrieben wird?


Dieses Ergebnis ist also bisher ohne irgendwelche Relevanz. Könnte nur interessant sein für mögliche weitere Attacken

 

[enkore]

Danke das du es nochmal so erklärt hast Elderan, ich habe wohl sinngemäß etwas anderes geschrieben als gedacht.