Cool Hashing mit FPGAs - TU Dresden...Long M., Implementing Skein Hash Function on Xilinx Virtex-5 FPGA Platform,Intel Corporation, 2009 Damiani E., Tettamanzi A. G. B., Liberali V.,

COOL HASHING MIT FPGAS

Robert Bachran

Dresden, 16.1.2012

Einführung

GrundlagenKriterien für gute HashverfahrenGrundlagen FPGAs

Hashverfahren auf FPGAsSkein auf FPGAEvolutionäre Hashverfahren

Energiesparendes Rechnen

ZusammenfassungTU Dresden, 16.1.2012 Cool Hashing Folie 2 von 18

02 Kriterien für gute Hashverfahren

Allgemeine Forderungen:

• Datenreduktion• Zufälligkeit• Eindeutigkeit• Effizienz

zusätzliche Forderungen:

• Kollisionsfreiheit• Unumkehrbarkeit

TU Dresden, 16.1.2012 Cool Hashing Folie 2 von 18

02 Was sind FPGAs?

• bestehen aus vielenLogikelementen (ConfigurableLogic Block)

• CLBs können jede beliebigeFunktion darstellen

• realisiert durch SRAM-Zellenoder Antifuse-Technik

• SRAM beliebig oftrekonfigurierbar

• vor Start jedoch neukonfigurieren


02 Beschaltung von FPGAs

• meist in Hardwarebeschrei-bungssprachen wieVHDL

• Programm wird über serielleSchnittstelle in Flashgespeichert

• bei Neustart Beschaltung ausFlash laden


03 Grundlagen Skein und verwendeter FPGA

Skein:

• basiert auf der Threefish Blockverschlüsselung• 72 Runden bei einer Blockgröße von 256 oder 512• 80 Runden bei 1024

verwendeter FPGA:

• Xilinx Virtex-5 LX50T• 550Mhz


03 technische Realisierung

• 1:1 Übernahme desAlgorithmus

• key scheduling block erstelltrundenweise neuen Schlüssel

• Round Block stellt dieThreefish Verschlüsselungdar.

• eine Runde pro Takt• Ausgang wird mit Eingang

XOR verknüpft


03 Ergebnis

FPGALeistung

Skein 256 Skein 512 Skein 1024

LUTs 3723 7029 14237

MinimaleTakt Periode

(ns)

8,7 8,7 11,79

Durchsatz(Gbps)

0,409 0,817 1,1


03 Evolutionäre Hashverfahren

• Algorithmen, die sich an die Evolutionstheorie anlehnen

• Verbesserung durch Mutation, Kreuzung und Selektion

• viele Algorithmen bekannt

• schwer für Hardware umzusetzen

• Flexibilität der FPGAs sehr nützlich


03 Prinzipielle Technik

Verwendete Techniken

• Beschaltung nach der GammaCircuit Topology

• sehr einfacher evolutionärerAlgorithmus

• Jede Zelle wird durch 5Zahlen je 16Bit dargestellt


03 Material & Ergebnisse

Material:

• Xilinx XC3020• basiert auf SRAM• 8x8 CLBs

Ergebnisse:

• Bester Schaltkreis wurde nach 13911 Generationen erstellt• Evolution bestand meistens aus 3 Phasen:

– beste Kombinationen für Funktionsblöcke– jeder Input baute sich einen Weg– erhöht die Verbindungen zwischen den Zellen


04 Energieverhältnisse eines FPGA

• Energieverbrauch steigt mitTaktfrequenz

• Taktverringerung jedoch nichtwünschenswert

• Verdrahtung verbraucht denmeisten Strom

• Verbesserung auf Architektur-und Schaltkreisebene


04 Reduktion auf Schaltkreisebene

• Verbindungskosten hoch beidirekter Übertragung

• geringere Stromübertragung= weniger Energieverbrauch

• realisiert durchTransformation

• Senkung der Kosten umFaktor 2


04 Reduktion auf Architekturebene

• 3 Ebenen der Architektur– Direkte

Nachbarumgebung– Maschenarchitektur– Hierarchische

Verbindungen

• Direkte Nachbarumgebung:– CLBs in direkter

Umgebung– je mehr Nachbarn,

desto höher derVerbrauch

– Verbindung zu 8 istenergiesparend


04 Verbindungen auf höheren Ebenen

• Maschenarchitekur:– Verbindungen über längere Distanzen– keine Änderungen nötig

• Hierarchsische Verbindungen:– Verzögerungen vergrößern sich mit Anzahl der langen Verbindungen– Hierarchieebenen nötig– Inverse Clustering ist vorteilhaft


04 Sparen durch Rekonfiguration

• ungenutzte Hardware in Standby

• ungenutze Hardware austauschen!!!

• bei Funkübertragung nur benötigtes Modul laden

• im energiesparsamen Modus nur Kern nötig


04 Funktionsweise Partielle Rekonfiguration

• jede benötigte Hardwarevorher synthetisiert

• FPGA einmal vollständigbeschreiben

• fester Kern bleibt immer• verschiedene

Hardwarevarianten imSpeicher


05 Zusammenfassung

• Hashverfahren schnell aufexternem FPGA

• Optimierung mit FPGAmöglich

• FPGAs könnenenergieeffizient beschriebenwerden

• können sich speziellenAufgaben anpassen


05 Fragen


05 Quellen

Literaturquellen:

• Long M., Implementing Skein Hash Function on Xilinx Virtex-5 FPGAPlatform,Intel Corporation, 2009

• Damiani E., Tettamanzi A. G. B., Liberali V., On-line Evolution ofFPGA-based Circuits: A Case Study on Hash Functions

• Weicker K., Evolutionäre Algorithmen• Opitz F., Partielle Rekonfiguration von FPGA basierten SoCs:

Seitenblicke

• George V., Zhang H., Rabaey J., The Design of a Low Energy FPGA• Altera, FPGA Run-Time Reconfiguration: Two Approaches• Porrmann M., Griessl R., Herbrechtsmeier S., Rueckert U., A

LOW-POWER VISION PROCESSING PLATFORM FOR MOBILEROBOTS


05 Quellen

Internetquellen:

• http://www.uni-protokolle.de/Lexikon/Hash-Funktion.html• http://www.schneier.com/skein.html, Niels Ferguson

Zusätzliche Bildquellen:

• http://www.fpga-talk.de/forum/public images/cyclone3 devkit.jpg,14.01.2012

• http://cdn.head-fi.org/9/9d/9dc48f9f XilinxSpartanXC2S150.jpeg,14.01.2012

• http://www.varbak.com/bilder/fragezeichen-auf-der-tastatur-nb10411.jpg,15.01.2012


EinführungGrundlagenKriterien für gute HashverfahrenGrundlagen FPGAs

Hashverfahren auf FPGAsSkein auf FPGAEvolutionäre Hashverfahren

Energiesparendes RechnenZusammenfassungAnhang

Documents

Cool Hashing mit FPGAs - TU Dresden...Long M., Implementing Skein Hash Function on Xilinx Virtex-5 FPGA Platform,Intel Corporation, 2009 Damiani E., Tettamanzi A. G. B., Liberali V.,