OTP Generierung

L

lone.wolf

0
Guten Tag,
Ich bin gerade auf eine neue Methode für One-Time-Pad Generierung gestoßen.
Ich werde es kurz erläutern und im Anschluss ein paar Fragen in den Raum werfen.

********************************

Key#1 - 110 (Länge 3)
Key#2 - 0101 (Länge 4)

Key#1 unendlich oft aneinandergereiht XOR
Key#2 unendlich oft aneinandergereiht
=
1101 1011 0110 1101 1011 0110 (..) XOR
0101 0101 0101 0101 0101 0101 (..)
-------------------------------
1000 1110 0011 1000 1110 0011 (..) = Key#3

Man merkt, das Key#3 ab der 12. Stelle sich wiederholt, dh.
Key#3 = 1000 1110 0011

Wir haben nun aus zwei kurzen Keys einen längeren generiert.
In der Quelle heißt es, dass der GGT beider Keys 1 sein soll, damit die Länge des generierten Schlüssels maximal wird.
Wenn GGT(Länge(Key#1), Länge(Key#2)) = 1 gilt, dann ist Länge(Key#3) = Länge(Key#1) * Länge(Key#2)

Ich habe mir Gedanken darüber gemacht, was passieren würde, wenn der GGT nicht 1 ist; auf folgendes bin ich gekommen:
Länge(Key#3) = Länge(Key#1) * Länge(Key#2) / GGT(Länge(Key#1),Länge(Key#2))

Bei unserem Beispiel kommen wir auf folgendes:
GGT(3, 4) = 1
Länge des gen. Keys = 3*4 = 12

Andere Beispiele:
GGT(2, 4) = 2
Länge = 4 * 2 / 2
= 4

GGT(768, 2048 ) = 256
Länge = 2048 * 768 / 256
= 2048 * 3
= 6144

Interessanteres Beispiel:
Länge(Key#1) ~ 32kb
Länge(Key#2) ~ 32kb
GGT = 1
Länge des gen. Schlüssels = 32kb * 32kb ~ 1gb

Key#1 und Key#2 können z.B. zwei verschiedene "Bilder" (jpg, bmp..) sein.

********************************

Soweit alles klar. Nun habe ich diesbezüglich zwei Fragen:
1. Inwiefern ist diese Methode der Schlüsselgenerierung besser/sinnvoller als z.B. die Generierung über einen Random Number Generator?
2. Welche Attribute hat der generierte Schlüssel? Ist er wirklich genauso sicher wie ein (pseudo~)zufällig generierter Schlüssel?

Quelle:
Inception E-Zine #1, 10.Power in simplicity
 
Zuletzt bearbeitet:
das one time pad ist die nachweisbar einzige informatonstechnisch sichere (selbst mit unbegrenzten mitteln nicht zu knackende) Chiffre


diese Sicherheit hat einen preis:


der Schlüssel MUSS 100% zufällig sein
der Schlüssel MUSS mindestens genauso lang sein wie die zu verschlüsselnde Information
der Schlüssel MUSS nach der Verwendung irreversibel vernichtet werden
der Schlüssel MUSS absolut geheim gehalten werden
der Schlüssel MUSS dem Empfänger auf sicherem Wege zugestellt werden


eine Verletzung dieser regeln und der Keks ist gegessen, sprich die Sicherheit ist dahin.


die von dir beschriebene Methode zur schlüsselerzeugung liefert keinen garantie dafür dass der schlüssel keine vorhersagbarkeit besitzt, und ist daher für OTP nicht zu gebrauchen... sichere wege zur schlüsselerzeugung wären unter kontrollierten umweltbedinungen z.b. thermisches rauschen, eine geiger-müller-röhre, oder eine kompanie affen die münzen werfen




was du beschreibst ist eine trivial form eines LFSR (linear feedback shift register) oder genauer gesagt, das XOR Produkt von zweier trivialer LFSRs


die Idee ist nett, aber ihre kryptografische stärke ist eher nicht so groß
 
Hey,
also erstmal gebe ich Graf Zahl recht, dass es wie ein LFSR aussieht. Allerdings hat es mich mehr an den shrinking Generator erinnert (vom Ansatz her). Dieser nimmt einfach zwei Streams an bits (Stream A und B) und generiert einen Stream C daraus, wobei nur die bits aus A genommen werden, bei denen in Stream B eine 1 steht.

Also so:

A 010101110
B 101110110

C 0 0 10 11

Diese Art von Generation wird übrigens noch als sicher angesehen und ist somit auf einem ähnlichen Level wie RC4 zu betrachten.

Aber zu deiner ersten Frage: Ich denke die Schlüsselgenerierung ist nicht sehr gut, da die Periode sehr klein ist. Bei LFSR beträgt die Periode bspw. 2^n -1, d.h. die relation zwischen Eingabe und Periodenlänge ist sehr gut, da exponentiell.

Zur zweiten Frage: Die Attribute und die Sicherheit sind (wie in der Kryptographie ja so üblich) sehr schwer einzuschätzen. Was man sagen kann ist, ist dass die Periodenlänge einen sehr starken Einfluss auf die Sicherheit hat, womit die von dir aufgezeigte Methode schlechter wäre als bspw. ein LFSR. Über alles weitere muss ich noch genauer nachdenken ;)

Random Number Generatoren haben generell das Problem, dass es schwer zu definieren ist was random ist. Ich glaube ich selbst habe mittlerweile 4 oder 5 definitionen von "randomness" gelernt und man muss immer wissen, von was für einer Art von "randomness" gesprochen wird. Aber vielleicht haben dir schon ein paar Stichworte hier geholfen, damit du weiterdenken / recherchieren kannst.
 
Das sind aufklärende Antworten, danke!

Ich selbst kenne mich kryptographisch eigentlich oberflächliche super aus. Wenns dann aber tief in die Mathematik geht, habe ich kA. mehr. Nicht dass mir Mathe nicht stehen würde. Es ist nur - ich habe mich mit der Materie noch nicht so genau befasst..

Aufjedenfall danke für die bisherigen Antworten.
Fraglich ist, warum so ein Algorithmus dann in einem angesehen Hacker-Magazin landet, wenns eh nicht allzu toll ist!?
 
lone.wolf hat gesagt.:
Fraglich ist, warum so ein Algorithmus dann in einem angesehen Hacker-Magazin landet, wenns eh nicht allzu toll ist!?
Zum Vergrößern anklicken....

Es gibt angesehene Hacker-Magazine? Das ist mir neu :)

Jeder kann einen kryptographisches Verfahren bauen, dass er selber nicht knacken kann. Viele denken dann leider, dass es dann auch sicher sein muss. Man schaut sich Magenta an, ein von der Telekom generierter Algorithmus. Bereits während der Präsentation des Algorithmus beim AES-Wettbewerb wurde dieser geknackt.

Selber was was auzuprobieren ist schön. Für echte Anwendungen dann aber bitte bewährte Algorithmen nutzen.
 
Ich bin auch kein Kryptographieexperte, deswegen sind meine Ausführungen auch immer mit vorsicht zu genießen und sollten selber nochmal nachvollzogen werden (wie immer bei Postings im Internet ;)).

Kryptographie ist ein sehr schwieriger Zweig und hat sehr viel mit Mathematik zu tun. Zwar ist es eigentlich nie möglich (Ausnahme: One-Time Pad) matehematisch zu beweisen ,dass ein Algorithmus/Verschlüsslung sicher ist, aber doch benötigt man sehr viele Grundlagen aus der Zahlentheorie. Besonders modulo Rechnung, Körper, Gruppen, Eulersche Funktion usw. sollte man sich anschauen, wenn man sich ein wenig weiter mit Kryptographie beschäftigen möchte. Denn ein oberflächliches Verständnis (d.h. ohne die mathematischen Grunlagen zu kennen) reicht oft nicht aus um z.B. "neuere" Methoden bewerten zu können.


Ich selber kenne dieses Magazin nicht und kann nicht sagen warum dieser Algorithmus dort veröffentlich wurde. Was ich mir vorstellen könnte wäre folgendes (das habe ich aber nicht geprüft, die Zeit dazu fehlt einfach, deswegen ist das nur eine Vermutung!): LFSR haben gewisse Probleme, d.h. sie sind kryptographisch alleine absolut als nicht sicher anzusehen. D.h. LFSR benutzt niemand mehr alleine sondern nur in Kombination, wie in der von mir beschriebenen Methode (shrinking Generator). Beim Shrinking Generator ist es aber so, dass wir den Keystream von Stream A (wenn wir beim obigen Beispiel bleiben) kürzen, womit wir im Endeffekt !VIELLEICHT! bei gleich langen Keys im Vergleich mit der hier vorgestellten Methode einen Key bekommen der kleiner ist, als Länge(Key1)*Länge(Key2). Womit diese Methode die hier vorgestellt wurde einen Vorteil hätte (nämlich einen größeren Key zu erzeugen, als andere Generatoren).

Also: Länge(Generierter Key Shrinking) < Länge(Key1) * Länge(Key2)

Allerdings bleibt mein Argument bezüglich der Periode der vorgestellten Methode und die damit verbunden sicherheitstechnischen relevanten Dinge bestehen.

Ich würde mich auch (vor allem bei Kryptographischen Sachen) eher auf wissenschaftliche Veröffentlichungen verlassen (d.h. wissenscahftliche Paper). Es ist allerdings sehr schwer an die dran zu kommen, wenn man nicht in der Uni ist (hier noch ein Tipp für die Grunlagen, falls dich das interessiert: http://www.sagemath.org/files/kohel-book-2008.pdf ) :)
 
Hmm ok.
Zum Hacker-Magazin - also ich hätte den Eindruck, dass es angesehen ist.. oder brüchtigt xD

Und zu wissenschaftliche Papers - hast Recht, sollte man vorziehen. Es war mir aber zu aufwendig, jetzt nach Papers zu suchen.
Wenn ich mir aber die Zeit nehme, mich über meine UNI in gewisse Bibliotheken einlogge, merke ich, dass es im Grunde unheimlich viele und vorallem verschiedene Papers zu LSFR gibt. Anstatt mich durch alle durchzuackern geh ich da lieber auf youtube und dröhn mich mit 0815 dingern zu xD
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben