kleine theorie: komprimierung durch MD5 möglich?

[net 0]

loki1985 schrieb:

der lookuptable wird einfach gebaut indem man von (0) bis (maximum) hashes errechnet und eben abspeichert....

und wenn man, so wie er's vorschlägt, eine lookup table für alle kombinationen von 32bytes braucht, dann ist die mal eben 256^32 etwa 1.2*10^77 einträge gross

[the_alien]

Dann doch lieber ungepackt als so einen Packer

[loki1985]

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

[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