Hashing-/Kryptografieproblem

Hi,

folgendes Problem: ich habe eine (eindeutige) 48-Bit-Zahl (um genauer zu sein eine MAC-Adresse), die ich gerne so hashen/verschlüsseln würde, dass sich aus dem Ergebnis dieser Operation nicht mehr auf die Ursprungs-MAC-Adresse schließen lässt, aber das Ergebnis immer noch eindeutig ist (d.h. es gibt keine zwei MAC-Adressen, die beide zu diesem Ergebnis gehören).

Die Datenmenge sollte sich dabei nicht sinnlos aufblähen (also 480 Bytes Ergebnis wären zu viel, 96 Bytes gerade noch so OK). Und der Hashing-/Verschlüsselungsalgorithmus sollte nicht geheim bleiben müssen.

Meine Frage: geht das überhaupt? Kann ich nicht immer irgendwie auf die Ursprungs-MAC zurückschließen, wenn diese eindeutig ist?

Und wenn ja: wie kann man sowas realisieren?

Danke

cooky451

Das Problem ist nicht einen Algorithmus zu finden der die Anforderungen erfuellt (siehe: SHA2/SHA3/...), sondern dass 48 bit einfach nicht genug sind um nicht einfach alle Kombinationen durch den Hash-Algorithmus zu ziehen und zu gucken ob das gleiche Ergebnis raus kommt. Gut, bei 48 bit waere das jetzt zumindest nicht voellig trivial, da muss man schon ein bisschen warten, aber das ist mit einem handelsueblichen PC trotzdem machbar. Und da das eine MAC-Adresse ist folgt die vermutlich auch noch irgendeinem bekannten Muster und ist nicht komplett zufaellig, was die Eingangsmenge noch mal deutlich verkleinert. Falls du noch andere, moeglichst zufaellige Daten hinten dran kleben koenntest (sollten dann mindestens 96, besser 128 bit sein die wirklich gleichverteilt zufaellig sind), sollte das aber kein Problem sein.

mgaeckler

Hi,

Diese Frage ist leicht zu beantworten. Das geht natürlich nicht, denn Deine Funktion mac -> hash ist umkehrbar.

Mfg Martin

krümelkacker

Ich habe möglicherweise das Problem nicht genau verstanden. Was willst Du damit gewährleisten? Was willst Du schützen? Und vor wem? Was weiß der Angreifer und was weiß er nicht?

Eine Idee wäre, die 48 Bit ggf. mit Nullen und/oder Zufall aufzufüllen und dann als Plaintext in eine Blockchiffre zu stecken. Das ist natürlich nur umkehrbar, wenn man den Schlüssel kennt oder in einer „praktischen Zeit“ ermitteln kann. Der Schlüsselraum sollte also viel größer als 48 Bit sein. Ich kenne sogar eine recht einfach zu implementierende Blockchiffre, die eine Blockgröße von 48 Bit unterstützt: Speck. Bei dieser Blockgröße sind die Schlüssel höchstens 96 Bit lang. 96 Bit ist jetzt aber auch gar nicht so wenig. Da beißt man sich schon die Zähne dran aus.

Ob das jetzt Dein konkretes Problem lösen kann, weiß ich nicht.

Zu Speck ist auch zu sagen, dass das Ding recht neu ist, von der NSA kommt und bisher kaum analysiert worden ist. Ich habe damit mal ein bisschen rumgespielt und es schien eine „gute Figur“ bzgl. Konfusion und Diffusion zu machen. Es sind jedenfalls keine offensichtlichen Schwächen vorhanden. Vielleicht reicht Dir das ja auch.

krümelkacker schrieb:

Ich habe möglicherweise das Problem nicht genau verstanden. Was willst Du damit gewährleisten? Was willst Du schützen? Und vor wem? Was weiß der Angreifer und was weiß er nicht?

Also entstanden ist die Frage aus dieser Diskussion heraus: https://bugzilla.mozilla.org/show_bug.cgi?id=949354

Dort schiebt die Datenkrake Mozilla rechliche Probleme vor, um damit zu begründen, warum Sie Ihre gesammelten Daten nicht veröffentlichen (warum Sie sie dann überhaupt sammeln und wieso das legal sein sollte, das Veröffentlichen aber nicht, begründen Sie spannenderweise nicht, aber das ist ein anderes Problem).

Also war meine Überlegung, dass man die MAC-Addressen (BSSIDs) verschlüsseln könnte um dann diese verschlüsselten Daten in der Datenbank abzulegen.

Wichtig wäre es nur, dass man von diesen verschlüsselten (aber immer noch eindeutigen!) Daten nicht auf die Ursprungs-MAC zurückschließen kann. Dann kann man immer noch die Geolokalisierung durchführen (empfangene BSSIDs verschlüsseln und Position mit der Datenbank abgleichen), aber wer die Datenbank hat, kann nicht ermitteln, welche MAC-Adressen sich an welchen Geopositionen befinden (weil ein Rückschluss eben nicht möglich ist).

SeppJ

Stamsund schrieb:

Wichtig wäre es nur, dass man von diesen verschlüsselten (aber immer noch eindeutigen!) Daten nicht auf die Ursprungs-MAC zurückschließen kann. Dann kann man immer noch die Geolokalisierung durchführen (empfangene BSSIDs verschlüsseln und Position mit der Datenbank abgleichen), aber wer die Datenbank hat, kann nicht ermitteln, welche MAC-Adressen sich an welchen Geopositionen befinden (weil ein Rückschluss eben nicht möglich ist).

Das wäre aus den von cooky451 genannten Gründen nicht möglich.

Zudem löst dies nicht in geringstem Maße das juristische Problem. Selbst wenn es nicht möglich wäre, von dem Hash auf die BSSID zu schließen: Nun könnte man nicht mehr von einer Geoposition auf eine BSSID schließen. Aber man könnte immer noch von jeder BSSID auf ihre Geoposition schließen. Und das wäre doch genau so problematisch wie umgekehrt.

rapso

was du brauchst ist also ein nicht symmetrisches verfahren das bei 48bit schon schwer zu knacken ist.

ein verfahren dass mehr bits fuer die verschluesselung braucht als deine zu verschluesselnde datenmenge (48bit) waere wohl nicht sinnvoll, da es einfacher waere die datenmenge durchzugehen. du musst also den aufwand die datenmenge durchzugehen hoch halten. aus der sicht wuerde es vielleicht sinn machen mehrere runden mit verschiedenen schluesseln durchzufuehren.

eliptic curve mit 128 oder 160 sollte ausreichen und mit 10 kaskaden waere es sowohl aufwendig 48bit zu testen, wie auch 10 schluessel von je 128/160 bit zu knacken. das resultat waere weiterhin klein genug (<96byte).

SeppJ schrieb:

Nun könnte man nicht mehr von einer Geoposition auf eine BSSID schließen.

Das soll man ja auch nicht - eben diese Richtung soll ja explizit ausgeschlossen werden.

SeppJ schrieb:

Aber man könnte immer noch von jeder BSSID auf ihre Geoposition schließen. Und das wäre doch genau so problematisch wie umgekehrt.

Das ist exakt das Prinzip JEDER Geolokalisierung per WLAN, egal ob die nun Google, Skyhook oder Mozilla macht. Dass das rechtlich problematisch ist, halte ich für ein vorgeschobenes Argument von Mozilla, um die Daten nicht herausgeben zu müssen. Das klingt für mich nach einem sehr einträglichen Geschäft, wenn man dann gleich noch haufenweise Leute hat, die die ganze Arbeit für lau machen und wie blöd WLANs scannen, ohne dass die Community davon was hat.

Aber das ist hier nicht das Problem!

rapso schrieb:

was du brauchst ist also ein nicht symmetrisches verfahren das bei 48bit schon schwer zu knacken ist.

Also wenn ich das richtig verstanden habe: Schlüsselpaar generieren, den privaten Schlüssel sofort löschen und dann alles mit dem öffentlichen Schlüssel verschlüsseln? Dann ist kein Rückschluss mehr auf die BSSID möglich, da der private Schlüssel ja nicht mehr existiert.

Klingt gut...aber gibt es ein asymmetrisches Verschlüsselungsverfahren, welches die sich ergebende Datenmenge klein hält?

krümelkacker

Stamsund schrieb:

Also war meine Überlegung, dass man die MAC-Addressen (BSSIDs) verschlüsseln könnte um dann diese verschlüsselten Daten in der Datenbank abzulegen.

Wichtig wäre es nur, dass man von diesen verschlüsselten (aber immer noch eindeutigen!) Daten nicht auf die Ursprungs-MAC zurückschließen kann. Dann kann man immer noch die Geolokalisierung durchführen (empfangene BSSIDs verschlüsseln und Position mit der Datenbank abgleichen), aber wer die Datenbank hat, kann nicht ermitteln, welche MAC-Adressen sich an welchen Geopositionen befinden (weil ein Rückschluss eben nicht möglich ist).

Natürlich kann man die BSSIDs „symmetrisch“ verschlüsseln. Aber dann ist die Datenbank wertlos für all die, die den Schlüssel nicht kennen. Sinn und Zweck der Übung soll doch sein, allen aufgrund der öffentlich zugänglich gemachten Daten eine Lokalisierung zu erlauben. Das heißt, jeder soll anhand einer BSSID, die er/sie aufgeschnappt hat, irgendwie in der Datenbank seine Position nachschlagen können. Und wenn alle dasselbe „Geheimnis“ kennen müssen, um das zu tun, ist es kein Geheimnis mehr. Es schließt also ein rein symmetrisches Verschlüsselungsverfahren aus. Die Abbildung von BSSID zu irgendeinem anderen Bitsalat muss also allen bekannt sein, nennen wir sie f. Mit „Eindeutigkeit“ meinst Du hier wahrscheinlich die Surjektivität von f – also: zwei unterschiedliche BSSIDs sollen nicht auf denselben Wert abgebildet werden. Das könnte man jetzt probabilistisch angehen (Hashfunktion mit genügend großen Hashwerten, dass die Kollisionen unwahrscheinlich werden) oder eben mit einer surjektiven Einwegfunktion (z.B. Potenzieren eines Generators einer genügend großen Gruppe, in der das diskrete Logarithmusproblem schwer ist).

Das Problem dabei liegt dann aber bei den 48 Bit. Folgender Angriff ist möglich:

Sortiere alle „verschleierten BSSIDs“ der Datenbank
Berechne y=f(x) für alle x in einer Schleife
Schaue für jedes dieser y-Werte per binäre Suche in der sortierten Liste der „verschleierten BSSIDs“ nach, ob der Wert vorhanden ist. Falls ja, kann man das dazugehörige x mit in der Datenbank ablegen

Und im Handumdrehen hast Du wieder eine Datenbank mit allen Klartext BSSIDs.

So, wie Du Dir das gedacht hast, ist es also nicht möglich.

Was man vielleicht machen kann, ist, mehrere Identifikationsmerkmale (nicht nur die BSSID) zu kombinieren. Also: Die 48 Bit der BSSID + die SSID + vielleicht noch was anderes, was man vom AP irgendwie mitbekommt und lange genug konstant bleibt und das dann zusammen durch einen aufwändig zu berechnenden Hash (so, wie man das auch bei Passwörtern macht, um eine Brute-Force Attacke zu erschweren) steckt. In der Datenbank würde nur noch der Hash und eine Geokoordinate stehen. Um das umzukehren, müsste man BSSID+SSID Kombinationen zusammen testen. Das ist schon schwieriger.