kleine theorie: komprimierung durch MD5 möglich?

[the_alien]

loki1985 schrieb:

mensch, es geht dabei doch einzig und alleine um die theorie, ob es möglich wäre etc.....

Hmmm, wenns normale Ascii Zeichen sind würde es gehen, sobald du Unicode hast müssen rein rechnerisch doch gleiche Hashes für unterschiedliche Strings rauskommen. Ganz davon ab, dass so eine Lookup Tabelle unmöglich wäre

[loki1985]

the_alien schrieb:

davon ab, dass so eine Lookup Tabelle unmöglich wäre

... du hast es nur nicht richtig verstanden

[junix]

Ich glaube eher DU hast nicht verstanden.... Siehe Bashars posting...

[loki1985]

ich kann nur sagen dass ich mich bereits mit der theorie von huffman und dem Lempel-Ziv-Algorythmus beschäftigt habe....

und dann soll er mir einfach begründen, weshalb ein derartiger lookup-table unmöglich wäre. er wäre zwar lahm, aber schneller als das on-the-fly-berechnen via MD5.

[Bashar]

loki1985 schrieb:

ich kann nur sagen dass ich mich bereits mit der theorie von huffman und dem Lempel-Ziv-Algorythmus beschäftigt habe....

Aber nicht mit der Theorie hinter dem Packen allgemein. Warum man überhaupt aus einer Bitsequenz eine kürzere machen kann, ohne Informationen zu verlieren. Welche Voraussetzungen dafür gegeben sind usw. Mach mal folgendes Gedankenexperiment: Du nimmst deinen Packer und wendest ihn iterativ auf sein eigenes Ergebnis an. Wenn er jedesmal die Daten auf die Hälfte komprimiert, hast du irgendwann nur noch 1 Bit. Dass man das nicht wieder entpacken kann liegt auf der Hand. Folgerung: Kein Packer kann beliebige Daten komprimieren.

[loki1985]

exakt. diese erkenntnis ist mir auch schon gekommen (wäre trotzdem cool, einen film auf 1,44"-diskette zu kriegen )

aber meine überlegung ist ja auch keine regulärer ansatz zum komprimieren.
zudem in heutiger zeit fernab von nützlich, da man so für ein paar hundert byte vermutlich tage zum dekomprimieren bräuchte.

die frage ob sich ein eindeutiges und einzig richtiges ergebnis "entpacken" lässt ist hier eben die frage und bin ich mir nicht im geringsten sicher...

daher die idee, für einen datenarray oder mehr technisch verschiedene hashs zu speichern....
lohnt sich nur wenn die daten grösser sind als alle hashs zusammen, aber je grösser die daten desto höher die gefahr, ein falsches ergebnis zu erhalten (glaube ich mal zumindest)...

/ADD: ich glaube absolut nicht dass meine überlegung tatsächlich funktioniert, denn sonst hätte sie schon irgendjemand präsentiert.

wie gesagt, ist nur so eine gedankliche spielerei.

[Bashar]

loki1985 schrieb:

aber meine überlegung ist ja auch keine regulärer ansatz zum komprimieren.

Doch, in der Beziehung schon. Der Ausgang des Gedankenexperiments hängt ja nicht davon ab, ob der Packer in irgendeiner Art und Weise regulär ist.

[ness]

Und mal ganz davon abgesehen, es sollte jedem mit gesundem Menschenverstand auffallen, dass kein Algorithmus aus allen 2³² Kombinationen verschiedene Werte errechnen soll, die er auf 2¹⁶ Möglichkeiten abbildet.

[loki1985]

ness schrieb:

Und mal ganz davon abgesehen, es sollte jedem mit gesundem Menschenverstand auffallen, dass kein Algorithmus aus allen 2³² Kombinationen verschiedene Werte errechnen soll, die er auf 2¹⁶ Möglichkeiten abbildet.

eben, daher auch die idee mit mindestens 2 "technisch" unterschiedlichen algorythmen, z.b. MD5 UND CRC32 (wobei ich mal denke dass CRC32 schon zu alt und "billig" ist)....

[net 0]

loki1985 schrieb:

eben, daher auch die idee mit mindestens 2 "technisch" unterschiedlichen algorythmen, z.b. MD5 UND CRC32 (wobei ich mal denke dass CRC32 schon zu alt und "billig" ist)....

crc ist nicht billig. das ist auf speed ausgelegt. anders als md5 wo's darum geht möglichst wenig mehrdeutigkeiten zu haben

[loki1985]

ok, ich habe da nicht so den durchblick. nur eben bräuchte mann für so einen test ein system welches auf möglichst wenige gleiche hashes ausgelegt ist....

[Bashar]

loki1985 schrieb:

ok, ich habe da nicht so den durchblick. nur eben bräuchte mann für so einen test ein system welches auf möglichst wenige gleiche hashes ausgelegt ist....

Das ist jeder vernünftige Hash-Algorithmus. Aber möglichst wenig heißt in deinem Fall immer noch 2^128 auf eins.

Ehrlich gesagt machst du ungefähr den Eindruck von einem, der ein Perpetuum Mobile bauen will.

[loki1985]

Bashar schrieb:

Ehrlich gesagt machst du ungefähr den Eindruck von einem, der ein Perpetuum Mobile bauen will.

ich weiss. aber manchmal gönne ich es mir einfach, etwas rumzuspinnen
nur bei dem PM bin ich schneller darauf gekommen, dass es nicht möglich ist (oder doch )

[Gerard]

wenn du weniger reden und mehr implementieren würdes, wärst du zu den gleichen schluss gekommen wie ich

man kann mit hashes schon komprimieren aber auch nicht mehr als man das mit normalen komprimierungs methoden kann

crc8 ist eine crc32 algo abgewandelt auf 8 bit und mit einer etwas anderen streung
next_pass und next_pass2 sind zwei funktion die ich mal benutz haben für brutforce verschlüsselung knacken

hier mein code (bevor er auf meiner hd versauert)

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <iterator>
#include <string>
#include <cstring>
#include <bitset>
using namespace std;

#include <boost\cstdint.hpp>
using namespace boost;

template<typename Iterator>
uint8_t crc8(Iterator begin, Iterator end)
{
    uint8_t res = 0;
    for(;begin != end; ++begin)
    {
        res = *begin + (res << 3) - res;
    }
    return res;
}

void next_pass(string & str, size_t current = 0)
{
    if(current == str.size())
        str.push_back('a');
    else if(str[current] == 'z')
    {
        str[current] = 'a';
        next_pass(str, current + 1);
    }
    else
        str[current]++;
}

void next_pass2(string & str, size_t current = 0)
{
    if(current == str.size())
        str.push_back(char(0));
    else if(str[current] == 0xFF)
    {
        str[current] = char(0);
        next_pass2(str, current + 1);
    }
    else
        str[current]++;
}

template<typename Iterator>
std::bitset<32> to5bin(Iterator begin, Iterator end)
{
    std::bitset<32> res;
    res &= *begin - 'a';
    for(;begin != end; ++begin)
    {
        res <<= 5;
        res |= *begin - 'a';
    }
    return res;
}

std::string from5bin(std::bitset<32> & r)
{
    string s = "";
    for(int k = 0; k < 6; ++k)
    {
        s.push_back(char((r & 31).to_ulong() + 'a'));
        r >>= 5;
    }
    reverse(s.begin(), s.end());
    return s;
}

int main()
{
    srand(42);

    string ein;
    int count = 0;
    cin >> ein;

    std::bitset<32> r = to5bin(ein.begin(), ein.end());

    char topress[5] = { 0 };
    *(int*)topress = r.to_ulong();

    uint8_t crc = crc8(topress, topress + 4);

    cout << hex << *(int*)topress << endl;
    cout << hex << (int)crc << endl;

    char gen[5] = { 0 };
    while(*(int*)topress != *(int*)gen)
    {
        if(crc == crc8(gen, gen+4))
        {
            count++;
        }
        (*(int*)gen)++;
    }

    cout << hex << count << endl;

    string pw;
    int t[256] = {0};
    for(int i = 0; i < 0xFFF; ++i)
    {
        t[crc8(pw.begin(), pw.end())]++;     
        next_pass2( pw );
    }

   // copy(t, t + 256, std::ostream_iterator<int>( cout, "\n"));
    cin.get();

    return 0;
}

[Jester]

Gerard schrieb:

man kann mit hashes schon komprimieren aber auch nicht mehr als man das mit normalen komprimierungs methoden kann

Wie das? Eine Hash-Funktion soll doch eine große Datenmenge möglichst gut streuend auf eine kleine Datenmenge abbilden. Dabei ist es natürlich unumgäglich,daß verschiedene Ausgangsn den selben Wert erhalten.

Ein Kompressionsalgo soll ebenfalls eine Datenmenge auf eine andere abbilden. Dabei soll die Darstellung nach der Abbildung möglichst oft kürzer sein als vorher. Aber es soll (bei verlustfreier Komprimierung) aus den komprimierten Daten die ursprünglichen zu rekonstruieren, das geht aber nur, wenn immer höchstens ein Datensatz auf jeden komprimierten Datensatz abgebildet wird. Das ist etwas was eine Hash-Funktion aber per Definition nicht leistet.

Für Mathematiker: Hash-Funktion sind nicht injektiv, verlustfrei Kompressionsfunktionen müssen das aber sein.

MfG Jester

[TomasRiker]

Wenn ich Loki richtig verstanden habe, dann meint er es wie folgt:
Klar ist, dass ein einziger Hash-Wert nichts bringt.
Wenn man aber noch einen Zweiten hinzufügt (und zwar einen, den man mit Hilfe eines anderen Algorithmus generiert hat), dann könnte es möglich sein, die Originaldaten sicher zu rekonstruieren.

Beispiel:
Der Text "HALLO, ICH BIN EIN TEXT!" würde vom Hash-Algorithmus 1 auf den Wert 66123178 abgebildet. Natürlich gibt es noch viele weitere Texte, die ebenfalls auf diesen Wert abgebildet würden.
Jetzt generiert man mit einem anderen Algorithmus noch einen Hash-Wert: 381941.
Dann speichert man die Werte 66123178 und 381941. Das könnte jetzt eindeutig sein, sodass nur der Text "HALLO, ICH BIN EIN TEXT!" die richtigen Hash-Werte bei beiden Algorithmen liefert.
Wenn das noch nicht reicht, könnte man einen dritten, vierten ... Hash-Wert hinzufügen, jeweils mit einem anderen Algorithmus generiert.

[net 0]

TomasRiker schrieb:

Der Text "HALLO, ICH BIN EIN TEXT!" würde vom Hash-Algorithmus 1 auf den Wert 66123178 abgebildet. Natürlich gibt es noch viele weitere Texte, die ebenfalls auf diesen Wert abgebildet würden.
Jetzt generiert man mit einem anderen Algorithmus noch einen Hash-Wert: 381941.
Dann speichert man die Werte 66123178 und 381941. Das könnte jetzt eindeutig sein, sodass nur der Text "HALLO, ICH BIN EIN TEXT!" die richtigen Hash-Werte bei beiden Algorithmen liefert.

kann ich mir auch vorstellen, dass dadurch die mehrdeutigkeit sinkt. das problem ist aber: wie kriege ich die originaldaten wieder. alle hashwerte liefern eine übelst grosse menge an ausgangswerten die passen. alle zu berechnen und zu vergleichen würde wohl jahre dauern

[Gerard]

Jester schrieb:

Gerard schrieb:

man kann mit hashes schon komprimieren aber auch nicht mehr als man das mit normalen komprimierungs methoden kann

Wie das? Eine Hash-Funktion soll doch eine große Datenmenge möglichst gut streuend auf eine kleine Datenmenge abbilden. Dabei ist es natürlich unumgäglich,daß verschiedene Ausgangsn den selben Wert erhalten.

ich habe mir noch mal überlegt wie ich das gemacht habe:

sagen wir mal du hast ein 4 byte string, du errechnest dazu eine 2 byte hash,
jetzt haben wir aus 4 byte 2 byte gemacht, aber wir haben noch das problem das die hash nicht eindeutig diesen 4 bytes zu geordnet werden kann
die lösung des problem ist, per bruteforce gehst alle möglichen 4 byte strings durch, errechnest die hash und jeder kolision zählst du mit (kolZ)
am ende hast du eine 2 byte hash und ein 2 byte grosse zahl (kolZ)

um zu dekomprimieren hast du die hash und kolZ, du gehst wieder alle möglichen 4 byte strings durch, jedes mal wenn der 4 byte string die hash ergibt die dir übergeben wurde zählst du mit, das tust du solange bis kolZ mal der übergebene hash errechnet wurde,

(bis jetzt wurde aus einen 4 byte string, eine 2 byte hash und 2 byte zahl, also noch nix wurde eigentlich komrimiert)

kann man mir bisher folgen?

der trick wie man damit komrimiert ist, wenn man weiss das es ein Text ist der aus a-z A-Z besteht, dann probiert man nicht alle 4 byte strings aus die möglich sind (beim komprimieren und dekomrimieren), sondern nur 4 byte strings die aus a-z A-Z bestehen dadurch sinkt die anzahl der möglichen kolisionen und wir kommen mit nur 1 byte zahl aus, tada
und das interesante ist sogar das die kolZ immer eine bestimmte max größe hat

@TomasRiker
ob du ein algo oder zwei algos benutzt ist im grunde genommen egal, probiere es doch mit etwas kleiner massstab aus es sollte ja kein unterschied machen ob du "HALLO, ICH BIN EIN TEXT!" oder eine 16 bit zahl mit zwei 4 bit hashes zu komprimieren, ich kann dir sagen das es minimum 256 * doppel kolisionen geben wird (d.h. beide hash werte werden sagen das es die zahl ist aber sie wirds nicht sein).
wir brauchen erstmal ein beweis das es überhaupt möglich ist, das wir die hardware noch nicht zu haben ist ein anderes problem

*(je nach qualität der hash algos wird die zahl näher an die 256 kommen)

[Bashar]

TomasRiker schrieb:

Beispiel:
Der Text "HALLO, ICH BIN EIN TEXT!" würde vom Hash-Algorithmus 1 auf den Wert 66123178 abgebildet. Natürlich gibt es noch viele weitere Texte, die ebenfalls auf diesen Wert abgebildet würden.
Jetzt generiert man mit einem anderen Algorithmus noch einen Hash-Wert: 381941.
Dann speichert man die Werte 66123178 und 381941.

Das heißt, die Kompression wird schlechter. Man könnte auch sagen, dass Hash-Algorithmus 3 den Wert 66123178381941 generiert, und damit sind wir in der gesamten Betrachtung back to square one.

Das könnte jetzt eindeutig sein, sodass nur der Text "HALLO, ICH BIN EIN TEXT!" die richtigen Hash-Werte bei beiden Algorithmen liefert.

"Könnte"? Es ist frühestens in dem Moment eindeutig, in dem nicht mehr komprimiert wird. Das sind absolute Grundlagen der Informationstheorie, was ist daran so schwierig?

[Sgt. Nukem]

TomasRiker schrieb:

Wenn ich Loki richtig verstanden habe, dann meint er es wie folgt:
Klar ist, dass ein einziger Hash-Wert nichts bringt.
Wenn man aber noch einen Zweiten hinzufügt (und zwar einen, den man mit Hilfe eines anderen Algorithmus generiert hat), dann könnte es möglich sein, die Originaldaten sicher zu rekonstruieren.

Das nennt man Double Hashing und ist doch gängige Methode bei Hashtabellen und Co.?!