Über Hash und Datenlänge Dateien bilden...

Bashar

Dann gäbe es immer noch je Hash 256 verschiedene Dateien, die diesen Hashwert haben.

RobthaR

Das versteh ich jetzt net

Michael E.

Dein Hash kann (216 = 2^128 verschiedene Werte annehmen. Die 17 Originalbyte können (217 = 2^136 verschiedene Werte annehmen. Nun willst du diese 2^136 Möglichkeiten auf nur 2^128 Möglichkeiten abbilden, d. h. du musst 2^136 / 2^128 = 2^8 = 256 verschiedene Möglichkeiten auf einer einzigen abbilden 256-fache Mehrdeutigkeit.

RobthaR

Zum austesten, wie viele Hashs mit einem Hash übereinstimmen, hab ich ein Programm geschreiben

delegate void GotHash(array<Byte>^);
delegate void LoopNum(Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,Byte,__int64);

void Hashing17Ex16(array<Byte>^	in,GotHash^	gh,LoopNum^	l){
	MD5 ^ Md = MD5::Create();
	array<Byte> ^ b;
	__int64	agi = 0;

	for(Byte a0	= 0; a0 < 256 ; )	{
	for(Byte a1	= 0; a1 < 256 ; )	{
	for(Byte a2	= 0; a2 < 256 ; )	{
	for(Byte a3	= 0; a3 < 256 ; )	{
	for(Byte a4	= 0; a4 < 256 ; )	{
	for(Byte a5	= 0; a5 < 256 ; )	{
	for(Byte a6	= 0; a6 < 256 ; )	{
	for(Byte a7	= 0; a7 < 256 ; )	{
	for(Byte a8	= 0; a8 < 256 ; )	{
	for(Byte a9	= 0; a9 < 256 ; )	{
	for(Byte a10= 0; a10< 256 ; )	{
	for(Byte a11= 0; a11< 256 ; )	{
	for(Byte a12= 0; a12< 256 ; )	{
	for(Byte a13= 0; a13< 256 ; )	{
	for(Byte a14= 0; a14< 256 ; )	{
	for(Byte a15= 0; a15< 256 ; )	{
	for(Byte a16= 0; a16< 256 ; )	{
		agi = agi + 1;
		l(a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,agi);
		b = Md->ComputeHash(gcnew array<Byte>{a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16});
		if(BACompare(b,in))gh(gcnew array<Byte>{a0,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16});
	a16+=1;}
	a15+=1;}
	a14+=1;}
	a13+=1;}
	a12+=1;}
	a11+=1;}
	a10+=1;}
	a9+=1;}
	a8+=1;}
	a7+=1;}
	a6+=1;}
	a5+=1;}
	a4+=1;}
	a3+=1;}
	a2+=1;}
	a1+=1;}
	a0+=1;}
}

Aber irgendwas stimmt mit den for loops nicht...
Siehe http://lhtech.lh.funpic.de/downloads/hasharraygeterror.gif
Die größeren A's bleiben 0 und das andere ist bei 400irgendwas ( bei einem Byte!!! )

hustbaer

@RobthaR: Wen willst du hier eigentlich verarschen?
1-2-viele oder wie, hm?

RobthaR

hustbaer schrieb:

@RobthaR: Wen willst du hier eigentlich verarschen?
1-2-viele oder wie, hm?

Spast!! Wenn du nur rumflamen willst, geh wo anders hin :p

TomasRiker

Tipp:
Deine for-Schleifen sind Endlosschleifen.
Die Laufvariable ist immer < 256, da Bytes nur max. den Wert 255 annehmen können. Danach gibt's einen Überlauf, und es fängt wieder bei 0 an.

Aber das bringt doch eh nix.
Denk lieber mal in Ruhe drüber nach, dann kannst du dir das Programm sparen.

RobthaR

Das Problem ist, das ich nur weiss was Hashes bringen, aber nicht genau und sonst hab ich auch keine Ahnung.

Aber ich wollte mal austesten, ob das geht, wie das halt mit so Ideeen ist
Ich müsste also ans Ende aller Schleifen

if(aIrgendwas==255)break;

machen

RobthaR

Hat aber keinen sinn, es dauert viel zu lange, jedenfalls wie ichs mache, vllt probier ichs später nochma, war trotzdem sehr lehrreich

Ausser hustebaer, der war einfach nur am unproduktiv rumflamen

Gerard

ich hatte mal vor einer weile so eine idee

man nähme 4 bytes hashe sie,
dann probiert man per bruteforce aus wie viele koliesionen man überspringen muss um zu orginal wert zu kommen
abspeichern tut man dann den hash und die anzahl der kolisionen

das problem dabei ist wenn der hash 1 byte groß ist, gibt es 0xFFF mögliche kolisonen d.h. man spart damit kein speicher platz ein

die idee ist "verlustbehafte text komprimierung", man speicher nur den hash und der algo am ende findet von alleine heraus welcher text es sein sollte, anhand rechtschreibung und gramatik, wenn dabei was schief wirds unterm tisch fallen gelassen

der komprimierer kann aber auch schon mal ein dekomprimieren durchspielen und dann extra informationen einbauen wo er merkt das es beim dekomprimieren unsicherheiten geben wird

thordk

ich behaupte mal ganz dreist, dass jedes andere "echte" kompressionsverfahren besser sein wird

Michael E.

Vor allem schneller beim Dekomprimieren

Nachtwind

und weniger fehleranfaellig.

Aber ganz uninteressant ist die idee ja nicht.. fuer kleine Datenmengen waere es durchaus lustig sowas zu basteln..
Man ueberlege sich einfach, dass man eine Datei hat, die aus 1ern und nullen besteht, was dann also 2^(laenge der 1/0er Kette) waere. Haette man jetzt also den Hash der Kette sowie die Laenge der Kette koennte man im BF verfahren wahrscheinlihc die originaldaten wiederhestellen koennen, da man ja bei ketten bis 2^80 laenge theoretisch nur eine uebereinstimmung finden duerfte..
Keine ahnung ob das geht oder in irgendeiner Form perfomant ist - interessant waere es auf jeden fall.. denke aber, dass Aufwand > Nutzen ist.

Bashar

Nachtwind schrieb:

Man ueberlege sich einfach, dass man eine Datei hat, die aus 1ern und nullen besteht, was dann also 2^(laenge der 1/0er Kette) waere. Haette man jetzt also den Hash der Kette sowie die Laenge der Kette koennte man im BF verfahren wahrscheinlihc die originaldaten wiederhestellen koennen, da man ja bei ketten bis 2^80 laenge theoretisch nur eine uebereinstimmung finden duerfte..

Wie kommst du auf diese Zahl, 2^80?

Nachtwind

Hatte noch von irgendwann im schaedel, dass es eine chance von 1 zu 2^80 gibt einen 'Treffer' zu landen, wenn man randomisierte strings hasht

*edit* Falls falsch lasse ich mich gerne aufklaeren ;0) Komme absolut nicht mehr drauf wann ich das aufgeschnappt hab - die Informatik lingt zu lange zurueck *G*

hustbaer

@RobthaR:
ich will nicht rumflamen, aber dein Posting grenzt an ... naja, lassen wir das. Daher die Vermutung dass DU hier nur blöd rumspammen/-trollen willst.

Dass dein Programm zu lange läuft ist klar, es will ja auch 2^136 Durchläufe machen (wenn du die Schleifenbedingung korrigierst bzw. einfach ints statt bytes verwendest). Und selbst mit Rechnern die eine Million mal schneller wären als das schnellste was uns heute an Computern zur Verfügung steht (Cluster, Supercomputer - was du willst) würde das immer noch milliarden Jahre dauern (was noch eine gewaltige Untertreibung ist).

Und um rauszubekommen wieviele mögliche Kollisionen eine Abbildung Daten -> Hash im Schnitt hat musst du auch nicht so eine Schleife laufen lassen, du musst nur die Länge des Hash mit der Länge der Daten vergleichen.
z.B. 800 Bit Daten (100 Byte) und 128 Bit Hash (16 Byte, z.B. MD5) ergibt im Schnitt 2^(800-128) also 2^672, also VIELE.

Das ist auch keine höhere Mathematik, das sind grundlegendste Grundlagen.

hustbaer

Nachtwind schrieb:

und weniger fehleranfaellig.

Aber ganz uninteressant ist die idee ja nicht.. fuer kleine Datenmengen waere es durchaus lustig sowas zu basteln..
Man ueberlege sich einfach, dass man eine Datei hat, die aus 1ern und nullen besteht, was dann also 2^(laenge der 1/0er Kette) waere. Haette man jetzt also den Hash der Kette sowie die Laenge der Kette koennte man im BF verfahren wahrscheinlihc die originaldaten wiederhestellen koennen, da man ja bei ketten bis 2^80 laenge theoretisch nur eine uebereinstimmung finden duerfte..
Keine ahnung ob das geht oder in irgendeiner Form perfomant ist - interessant waere es auf jeden fall.. denke aber, dass Aufwand > Nutzen ist.

Nein es geht nicht, und nein es wäre nicht performant.
BTW: wäre die Chance immer 1 zu 2^80 eine Kollision zu bekommen, dann könnte man auch maximal 80 Bit lange Daten nehmen, nicht 2^80. Grosser unterschied.
Und bei 80 Bit aka 10 Byte ... naja, jeder normale Hashcode ist länger.
Und Hashcodes wo die Chance eine Kollision zu bekommen 1 zu 2^80 ist sind normalerweise auch 80 Bit lange. Sowas, hm?

RobthaR

@hustbaer

Ich weiss net was du willst, es war eine berechtigte Frage, und nur weil dus besser weisst, sagst du ich würd Spannen oder Trollen, is ja wohl net der Sinn eines Formums, denk ma drüber nach
Begründe erst mal deine Behauptung, ich würd Spammen/Trollen

hustbaer

RobthaR schrieb:

...
Begründe erst mal deine Behauptung, ich würd Spammen/Trollen

Begründung: So blöd kann man garnicht sein.
Sorry, du hast danach gefragt.