Hi zusammen, hoffe ich bin hier an der richtigen Stelle im Forum gelandet :) Und zwar bin ich auf der Suche nach einer (kryptographischen) Hashfunktion, deren Design den Effizienzvorteil einer Implementation in Hardware (insbesondere auf FPGAs) schmälert (ja, richtig gelesen ;)). Der Algorithmus sollte also z.B. einen möglichst hohen Platzbedarf haben und die nutzbare Taktfrequenz verringern (bspw. Pipelining erschweren), also eine geringe Optimierbarkeit aufweisen. Gibt es bestimmte "Strukturen" die dazu führen könnten? Ziel ist es, den Laufzeitunterschied zwischen Hardware-Implementierung und Software-Implementierung möglichst klein zu halten. Soweit das halt möglich ist. Schön wäre es, wenn es eine Java-Implementierung gäbe.
>> Ziel ist es, den Laufzeitunterschied zwischen Hardware-Implementierung >> und Software-Implementierung möglichst klein zu halten pll -> genutzte Taktfrequenz verringern. Das dürfte der effektivste Weg zur Leistungsverringerung sein. Sehe nicht warum man absichtlich eine lahme Funktion bauen will. Willst du damit beweisen das java schneller sein kann als eine direkte Hardwareimplementierung ?
Die Suche kannst Du Dir sparen. a.) Bekannte Algorithmen werden prkatisch immer auf Speed optimiert b.) Alles was Du in Software in mehreren Schritten berechnest, kannst Du in Hardware in einer Pipeline implementieren.
B. G. schrieb: > Hi zusammen, > hoffe ich bin hier an der richtigen Stelle im Forum gelandet :) > Und zwar bin ich auf der Suche nach einer (kryptographischen) > Hashfunktion, deren Design den Effizienzvorteil einer Implementation in > Hardware (insbesondere auf FPGAs) schmälert (ja, richtig gelesen ;)). > Der Algorithmus sollte also z.B. einen möglichst hohen Platzbedarf haben > und die nutzbare Taktfrequenz verringern (bspw. Pipelining erschweren), > also eine geringe Optimierbarkeit aufweisen. Gibt es bestimmte > "Strukturen" die dazu führen könnten? > > Ziel ist es, den Laufzeitunterschied zwischen Hardware-Implementierung > und Software-Implementierung möglichst klein zu halten. Soweit das halt > möglich ist. > > Schön wäre es, wenn es eine Java-Implementierung gäbe. Bestimmender faktor für den Platzbedarf eines dersigns ist meist die Anzahl der FlipFlops. Rechenvorschriften mit sehr vielen gleichzeitig benutzten Zwischenvariablen z.B skalarprodukt sind da ein problem für lowCost fpga's. Viele parallel Multiplikationen sprengen auch schnell kleiner FPGA's, je breiter die Faktoren (<24 bit ?) desto eher ist schluss. Bit-Shiftoperationen sind ein Klacks für FPGA's, die solltest du also vermeiden. Der onboard memory von FPGA's ist begrenzt, und sobald du einen externen Speicher anschlisst, wird der Durchsatz etwas geringer. Interleaving größerer Blöcke könnte also einen FPGA "verlangsamen". Insgesamt bin ich allerdings skeptisch, das eine Verschlüsselung gibt, die nicht durch heutige FPGA's flott ausgeführt wird. Eine CPU besteht wie ein FPGA aus den selben digitalen Baugruppen. Der FPGA mag langsammer sein (<500 MHz), kann aber "mehrere" CPUS gleichzeitig realisieren. MfG
Für den Einstieg in das Thema "FPGA-Implementierung von Hash-Funktionen: http://www.east.isi.edu/~bschott/pubs/grembowski02comparative.pdf
> Insgesamt bin ich allerdings skeptisch, das eine Verschlüsselung > gibt, die nicht durch heutige FPGA's flott ausgeführt wird. Ja, in der Tat. Kürzlich bin ich über eine skalierbare Plattform gestolpert die von einer Uni hergestellt wurde und genau dafür eingesetzt wurde. Es gibt sogar einer offizielle Webseite für das Gerät. finde es aber im Moment nicht :-(
Gestolpert oder gefallen ? Bei dem teilweise schon zwanghaft anmutendem Marketing (insbesondere durch Okkupierung fast sämtlicher PLD-relavanter Artikel in Wikipedia) ist es ein Wunder das man nicht sofort drauf kommt. Mittlerweile scheint es sich dabei jedoch um ein kommerzielles Produkt zu handeln, deswegen werde ich den Namen nicht hier auch noch nennen.
Ich würde mal sagen, alles was gleitkommalastig ist. Aktuelle Prozessoren mit SSE sind genau dafür optimiert, das nachzubauen kann im FPGA nur langsamer werden. Falls GPUs auch noch zu "Software" zählen gilt das umso mehr.
> Bei dem teilweise schon zwanghaft anmutendem Marketing (insbesondere > durch Okkupierung fast sämtlicher PLD-relavanter Artikel in Wikipedia) Was ist damit gemeint?
Benutze einen Algorithmus der aus einem Blockcipher als Hashalgorithmus verwendet und Blowfish als Blockcipher. Blowfish ist hat einen sehr langsamen Keyschedule und brauch dazu noch etwas über 4 KiB RAM. Beides erschwert einen Angriff einen linearen Vorfaktor gegenüber anderen Ciphern.
@ Brathänchen : http://www.google.de/search?hl=de&lr=&safe=off&q=copacobana++site:wikipedia.org&start=0&sa=N Versuch mal einen Artikel zu finden der über FPGA, allgemein rekonfigurierbare Systeme oder Parallelrechner handelt und nicht Lobpreisungen über C. enthält. Mittlerweile wurde ja sogar die englische Wikipedia schon infiltriert. Wenn ein Neuling in dieses Gebiet reinschneit muss er ja schon fast das Gefühl bekommen C. sei praktisch das einzige, große Projekt das für FPGAs überhaupt existiert.
Danke erst mal für die vielen Antworten. Ziel war es eigentlich eine KDF (Key derivation function) zu erstellen, welche nicht so effizient wie üblich in Hardware ausgeführt werden kann, um wiederum BruteForce-Angriffe zu erschweren. Die eigentliche Sicherheit der KDF sollte dann z.B. durch eine Hashfunktion aus der SHA-2-Familie kommen. Ich merke aber schon, dass es da nichts erprobtes gibt und ich somit die Finger davon lasse werde ;)
Man merkt deutch deutlich, dass Du a) aus der Informatikecke kommst b) jung bist Die Haltung eines echten Ingenieurs vom alten Schlag wäre nun, den Ehrgeiz zu entwickeln, in diese Lücke zu stossen und etwas zu erdenken und zu entwickeln. Aber so sind sie, unsere Nachfolger
> Die Haltung eines echten Ingenieurs vom alten Schlag wäre nun, den > Ehrgeiz zu entwickeln, in diese Lücke zu stossen und etwas zu erdenken > und zu entwickeln. Ja, die Sorte kenne ich. Ein paar davon merken dann auch zum Glück, dass Kryptographie kein Gebiet ist, in dem man sich selbst was zusammenfrickelt. Die anderen sind dann für die riesigen Sicherheitslücken verantwortlich, die man in vielen aktuell verwendeten Systemen findet. > Aber so sind sie, unsere Nachfolger Die meisten leider nicht.
>Ziel war es eigentlich eine KDF (Key derivation function) zu erstellen, >welche nicht so effizient wie üblich in Hardware ausgeführt werden kann, Dann ist dein Ansatz komplett falsch gedacht. Selbst wenn du diese KDF in Femtosekunden pro Schlüssel ausführen könntest so machst du exakt das was jeder Kryptologe und damit Mathematiker macht, inkrementiere exponentiell die Komplexität des Verfahrens indem du einfach die Schlüsselgröße in Bits inkrementierst. Also: eine KDF über 64Bit Schlüssel ist ungleich einfacher zu knacken wie eine KDF über 256Bit Schlüssel. Im Allgemeinen geht man davon aus das mit heute praktikabler Hardware 128 Bit Zufallschlüssel nicht in vertretbarem Aufwand zu knacken sind per Brute Force. Es geht also nicht darum das du nun einen hoch komplizierten Algortihmus benutzt sondern die mathematische Komplexität durch die benutzte Schlüsselänge erhöhst. Letzters geht mit den einfachsten Algorithmen. Du denkst also eher wie ein Hacker statt wie ein Kryptologe. Statt also die Motorleistung deines Autos zu erhöhen baust du nur größere Reifen dran. Gruß Hagen
Desweiteren gilt: benutze in deiner KDF einen gleichlangen Zufallssalt wie das Passwort lang ist. Denn wenn du dies nicht machst dann gilt i.A. die Brute Force Attacke nicht mehr als die effizienteste durchführbare Attacke. Über Rainbow Tabellen zb. kann man dann effizienter und damit schneller deine KDF knacken. Entscheidend ist also nicht wie möglichst ineffizient dein Algorithmus umsetzbar ist sondern wie hoch die Komplexität und damit die Datengrößen deiner Algorithmen sind. Also nciht die Technologie ist federführend sodnern die mathematische Basis die du benutzt. Falls du denoch diesen Weg gehen möchtest dann schau dir Polymorphe Kryptographie an. Bei diesen Verfahren besteht der Algorithmus quasi aus einem Compiler der abhängig von deinen Schlüsseln den eigentlichen kryptographisch relevanten Algorithmus erst zur Laufzeit erzeugen muß. Es gibt dann Konstante X * Anzahl an Kombinationen von Schlüsseln verschiedene kryptographische KDFs die als Algorithmus erst zur Laufzeit erzeugt werden. Nur mit dem korrekten Schlüssel erzeugt man den korrekten kryptographischen Algortihmus. Generell halte ich aber nicht viel davon da diese Verfahren aus mathematischer Sicht zur Berechnung ihrer Komplexität sehr wohl gemappt werden können in die derzeitig anerkannten Standard Algorithmen die nicht polymorph sind. Gruß Hagen
Sorry, warum muß ein Schlüssel immer zu 100% aus dem Schlüssel bestehen? Wenn z.B. ausreichend Mist aus dem letzten ostfriesischen Telefonbuch hinzugemischt wird, kann das die mathematische Vielfalt auch verbessern, da länger gesucht werden muß.
Zur Verdeutlichung des Sachverhaltes: Eine polymoprhe KDF könnte basierend auf 2 Hash Verfahren und dem Schlüssel eine Pseudozufakllstrom erzeugen. Dieser wird zur laufzeit erzeugt und dazu benutzt zwischen den beiden Hashfunktionen umzuschalten, für jedes Bit das die KDF erzeugt. Das wäre unsere polymorphe KDF. Deren Komplexität berechnet sich aus der Komplexität eines Angriffes auf die einzelnen beiden Hashfunktionen und der benutzten Schlüsselgröße (so Pi* Daumen abstrakiert). Wenn also die beiden Hashfunktion 128 Bit Hashs sind und der Schlüssel ebenfals 128 Bit dann hätte ein Angreifer 2*128Bit ergo eine 129 Bit Komplexität durch diesen Trick erreicht. Würdest du aber statt zwei unterschiedlicher Hashfunktionen eine einzige mit 256 Bit benutzen dann hättest du die Komplexität einer Brute Force Attacke um ein enorm größeres Vielfaches inkrementiert. Dir wird nun sicherlich bewusst wo der Fehler in deinem Ansatz liegt. Übrigens zweigt auch obiges vereinfachtes Beispiel noch andere Nachteile: 1.) überproportional mehr Hardwareresourcen werdden verbraucht in relation zum Nutzen 2.) das Ratio zwischen Effizienz der ersten Methode zur zweiten bei authorisierten Operationen wird wesentlich schlechter. Der Ansatz die Effizienz des Algortihmus zu reduzieren trifft also nicht nur den Angreifer sondern auch den regulären Nutzer ohne das sich kryptrographisch wirklich was verbessert hat. Gruß Hagen
>Sorry, warum muß ein Schlüssel immer zu 100% aus dem Schlüssel bestehen? >Wenn z.B. ausreichend Mist aus dem letzten ostfriesischen Telefonbuch >hinzugemischt wird, kann das die mathematische Vielfalt auch verbessern, >da länger gesucht werden muß. Jo und diesen hinzugemischten Mist musst du dir auch noch merken da es schlüsselrelevante Informationen sind und ergo wird dieser Mist plus deinem Schlüssel zum wahren benutzten Schlüssel. Damit erreicht man garnichts ausser Probleme ohne zielführenden Nutzen. Gruß Hagen
Potentiell ist jedes Schlüsselbit das nicht zufällig gewählt wurde eine Unsicherheit die später zum Knacken des Schlüssels herangezogen werden könnte. Es gibt also wesentlich weniger Kombination aus zb. allen Telefonbüchern weltweit als Schlüsselkombinationen die der Algortihmus nutzen könnte. Damit sind solche Tricks in jedem Falle eine reduktion der Sicherheit des benuztzen Verfahrens. Also: 128 Bit Hashfunktion und 128 Bit Schlüssel. Wählen wir diese Schlüssel per Zufall aus so gibt es 2^128 gleichverteilt sichere Schlüssel. Würden wir aber diese Schlüssel aus den Telefonbüchern erzeugen dann gibt es weit weniger als 2^128 verschiedene Schlüsselkombinationen. Man unterschätzt leicht was 2^128 bedeutet ! Wenn unser Universum immer weiter expandiert dann werden in 2^213 Jahren alle Schwarze Löcher verdampft und damit nicht mehr existent sein. Die Erde besteht aus geschätzten 2^170 Atomen die zu diesem Zeitpunkt fast gleichverteilt vereinzelt im Universum rumschwirren. Gruß Hagen
Dein Ziel müsste also exakt andersrum lauten: Gibt es ein Verfahren das enorm schnell in HW abläuft dessen mathematisch kryptographische Komplexität aber um ein Vielfaches höher ist als die bisherigen Verfahren. Nur so inkrementierst du das Ratio des Aufwandes für den Angreifer und dem berechtigten Nutzer. Und nur das ist das Ziel der Kryptographie. Die einfachste Methode ist dabei die Vergrößerung der Anzahl an Schlüsselbits im Zusammenhang mit der Inkrementation der Komplexität des benutzten Algorithmus. Es geht also nicht um Kompliziertheit sondern Komplexität als Formel zur Bewertung des beweisbaren Aufwandes einer im besten Fall durchführbaren Brute Force Attacke. Gruß Hagen
Hm, vielleicht nochmal einfacher: 1.) Eine FPGA Implementierung eines Verfahren beschleunigt einen Angriff nur proportional linear. 2.) Die Inkrementation der Kompelxität und damit die Anzahl an Schlüsselbits inkrementiert dagegen den Aufand exponentiell. Es ist also unklug, ja mathematisch beweisbar dumm, nun zu versuchen über den Weg 1.) die Sicherheit des Verfahrens inkrementieren zu wollen. Übrigens ist dies auch eine Erklärung warum Quantencomputer mathematisch rein garnichts grundsätzlich verändern, es sei denn nur Wenige besitzen Quantencomputer und alle Anderen benutzen die heutige Technologie. Gruß Hagen
Hallo Hagen, danke erstmal für deine hilfreichen und ausführlichen Beiträge. Ich muss jedoch eingestehen, dass ich ein wichtiges Detail in meinen Beiträgen vergessen habe zu erwähnen. Und zwar handelt es sich um eine spezielle KDF, nämlich eine PBKDF (Password-based key derivation function). Da "normale" Passwörter sich wenn überhaupt im Komplexitätsbereich von 2⁶⁵ bewegen, ist dann über die Komplexität moderner kryptographischer Hashfunktionen keine Erschwerung möglich. Wohingegen bspw. "Memory-Hard Functions" einen konstanten Faktor "rausholen" können. Habe nach längerer Suche ein Paper von der letzten BSDCan'09 gefunden, welches sich vermutlich (hab es selber NOCH nicht gelesen ;)) mit diesem Thema beschäftigt: http://www.tarsnap.com/scrypt/scrypt.pdf
> PBKDF (Password-based key derivation function)
Und wo ist der Unterschied deiner Meinung nach ?
Jede KDF ist wie es der Name schon sagt eine Key Derivation Function,
eine Schlüsselableitungsfunktion. Es gibt noch MGFs also Mask Generation
Functions die im Aufbau identisch zu KDFs sind. Per Definition besteht
der Unterschied zwischen beiden Verfahren in der Benutzung eines
Schlüssels als Datenausgangsbasis bei den KDFs. Eine PB-KDF ist also
auch eine KDF und nichts anderes. Nur das in diesem Spezialfall der
abzuleitende Schlüssel aus mehreren Bestandteilen besteht, zb. eben aus
einem Nutzerschlüssel und einem Hardwareschlüssel den der Nutzer nicht
beeinflussen noch sehen kann. Dazu nimmt man eine normale KDF und die
beiden Schlüssel werden einfach zusammengefügt bevor sie in der KDF
gelangen, fertig ist deine PB-KDF.
Sogesehen: es gelten für deine PB-KDF die exakt gleichen Regeln wie für
jede andere KDF auch und meine obige Argumentation ist direkt
übertragbar auf deine PB-KDF.
Wichtig sind nur zwei Punkte bei den KDFs.
1.) die Hashfunktion sollte eine Komplexität besitzen die größer oder
besser gleich der der Schlüssel ist. Heist: ist der Schlüssel als
Eingangsdaten zb. 128 Bit groß dann sollte die Hashfunktion ebenfalls
128 Bit betragen. Ist es weniger reduziert sich die machbare Sicherheit
auf Grund des benutzten Schlüsselmateriales, man verschenkt also
Sicherheit. Ist sie größer so verschenkt man Resourcen und Rechenpower
ohne einen Sicherheitsgewinn. Ergo: am besten ist es die Komplexität der
Schlüssel ist identisch zur hashfunktion da das der Breakeven ist.
2.) die KDF sollte unbedingt einen Zufallssalt benutzen. Bei 128 Bit
Schlüssel und 128 Bit Hashfunktion also noch 128 Bit Zufallsalt mit in
die Berechnung einbeziehen. Dieser Salt wird extern und sichtbar
gespeichert, verhindert aber effektiv andere Angriffe die schneller als
Brute Force gehen, zb. eben offline vorausberechnete Rainbow Tabelle.
Ohne den Salt benötigt man für diese Angriffe maximal eine Datenbasis
von zb. 2^128 Datensätzen bei 128 Bit Schlüsseln. Mit 128 Bit Salt
benötigt man 2^128 solcher Datenbanken zu jeweils 2^128 Schlüsseln. Der
Trick der Rainbow Tabellen besteht nun darin das diese Datenbasis für
die 2^128 Schlüssel um einen gewaltigen Faktor reduziert werden kann, so
das am Ende oft eine DVD als Datenspeicher ausreichend ist.
Gruß Hagen
Hallo Hagen, > Und wo ist der Unterschied deiner Meinung nach ? Strukturell gibt es dort keinen Unterschied, jedoch ist es meiner Meinung nach für das Verständnis essentiell. (siehe unten!) > 1.) die Hashfunktion sollte eine Komplexität besitzen die größer oder > besser gleich der der Schlüssel ist. Heist: ist der Schlüssel als > Eingangsdaten zb. 128 Bit groß dann sollte die Hashfunktion ebenfalls > 128 Bit betragen. Ist es weniger reduziert sich die machbare Sicherheit > auf Grund des benutzten Schlüsselmateriales, man verschenkt also > Sicherheit. Ist sie größer so verschenkt man Resourcen und Rechenpower > ohne einen Sicherheitsgewinn. Ergo: am besten ist es die Komplexität der > Schlüssel ist identisch zur hashfunktion da das der Breakeven ist. Das ist ja auch in der Theorie richtig was du schreibst. In der Praxis wird es jedoch die Regel sein, dass kein Schlüssel/Passwort verwendet wird welches der Komplexität eines z.B. 128Bit Schlüssels (2¹²⁸ Möglichkeiten) auch nur im geringsten nahe kommt. Unter der Annahme (die in der Praxis eher die Ausnahme als die Regel ist), dass bspw. ein Passwort bestehend aus 10 druckbaren ASCII-Zeichen verwendet wird, kommen wir gerade einmal auf ~2⁶⁵ Möglichkeiten. Die restlichen Eingabedaten kommen durch den bekannten Salt konstanter Länge. Einem BruteForce-Angreifer (der z.B. entweder x=PBKDF(Password, Salt, Iterations) kennt, oder ein bzw. mehrere Klartext/Chiffretext-Paar(e) einer nachgeschalteten Blockchiffre kennt) ist es also relative egal, ob in der PBKDF ein SHA-1 oder ein SHA-512 iterativ verwendet wird. Das eine wesentlich sicherere kryptographische Hashfunktion (hier SHA-512) nämlich NICHT auch gleichzeitig eine wesentlich schlechtere Performance aufweist (zumindest in die eine Richtung ;)) ist http://www.east.isi.edu/~bschott/pubs/grembowski02comparative.pdf zu entnehmen. In beiden Fällen muss der Angreifer "lediglich" ~2⁶⁵ PBKDF-Berechnungen und Vergleiche (mit z.B. entweder dem x, oder dem Klartext/Chiffretext-Paar) durchführen. Um dem BruteForce-Angreifer die Attacke möglichst schwer zu machen, ist es also sinnvoll das "Key strengthening/Key stretching" durchzuführen.
Werden zu kurze Schlüssel benutzt hilft dagegen garnichts, da kannst du noch soviel tricksen. Die gesammte Sicherheit basiert auf dem Schlüsselmaterial, ist dieses schlecht so kann man es nur virtuell aufbessern aber nicht physikalisch.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.