Wie zufällige Hashes erzeugen?

[Y0Gi]

Ich suche einen Weg, eindeutige Zufallshashes zu erzeugen, die ich z.B. in Webanwendungen anstelle von numerischen, fortlaufenden IDs nutzen kann.

Mit den bekannten und weniger bekannten Hash-Algorithmen benötige ich ja einen Ausgangswert, der gehasht wird - auf den möchte ich aber verzichten können.

Gibt es eine Methode, die Zufallsnamen (nicht Dateinamen) erzeugt?

[lutz.horn]

Du kannts z. B. mit http://pypi.python.org/pypi/uuid/ UUIDs erzeugen und diese dann nach Wunsch verwenden.

[jens]

MD5 oder SHA1 berechnen lassen, z.B. so:
http://code.djangoproject.com/browser/d ... els.py#L21

[Leonidas]

Was spricht dagegen, als Seed für die Hashfunktion `time.time()` zu verwenden? Ist zwar nicht kryptografisch sicher aber ich glaube das willst du auch nicht, oder?

[rafael]

Wie wäre es mit sowas wie hier?

[Y0Gi]

Du kannts z. B. mit http://pypi.python.org/pypi/uuid/ UUIDs erzeugen und diese dann nach Wunsch verwenden.

Danke, `uuid` hatte ich vergessen. Das sieht soweit (s.u.) gut aus.

Was spricht dagegen, als Seed für die Hashfunktion `time.time()` zu verwenden? Ist zwar nicht kryptografisch sicher aber ich glaube das willst du auch nicht, oder?

Es geht mir dabei nicht um Kryptografie, sondern darum, (weitgehend) eindeutige Ergebnisse zu erhalten. Wenn ich den Timestamp verwende, so dachte ich, erhalte ich bei theoretisch möglichen mehreren parallelen Zugriffen ja identische Hashes (da ich ja sonst keinen Wert habe, den ich in den Hash mit einbeziehen kann). Jedoch habe ich außer acht gelassen, dass `time.time()` eine Fließkommazahl liefert, bei der Kollisionen durch parallele Aufrufe (die entsprechend so einen eindeutigen Hash erfordern) in einer Webanwendung praktisch fast auszuschließen sind.

So gesehen ist dieser Ansatz möglich, entsprechend sind auch die beiden von jens und rafael genannten Lösungen denkbar.

Zwar kommen nun doch mehrere Wege, eindeutige Hashes (nicht zwangsweise Hashes, aber ich bleibe mal bei dieser Bezeichnung) zu erzeugen, in Frage. Jedoch scheint auch keiner davon die Einschränkung der Ergebnislänge zu erlauben...

...denn es gibt eine weitere Einschränkung, die ich... ääh... erst jetzt nenne, damit es spannend bleibt : Ich möchte vorzugsweise relativ kurze eindeutige Werte erhalten, wie ich sie etwa von Blogger für hochgeladene Bilder und von Jottit (cool!) für Wikiseiten ohne zugewiesene Subdomain kenne. Diese haben teilweise schätzungsweise um die 6-9 Zeichen Länge und verwenden nicht nur hexadezimale Zeichen, sondern bedienen sich Zahlen und unseres Alphabets sowie auch der Unterscheidung von Groß-/Kleinbuchstaben. Letzteres ist mir nicht unbedingt wichtig, aber die erhöhte Zahl von möglichen Zeichen erlaubt es natürlich, in geringerer Stringlänge mehr Variationen zuzulassen. Einen Algorithmus, der mir dieses bietet, suche ich. Muss da wohl doch was eigenes her?

[BlackJack]

Wenn es möglichst kurz und eindeutig sein soll, würde sich dann nicht ein fortlaufender Zähler zur Basis 46 anbieten? Also Buchstaben und Dezimaliffern als "Ziffern"? Vielleicht auch Gross- und Kleinschreibung. Und für die "user friendliness" sollte man einige Zeichen rausnehmen bzw. synonym verwenden können, also 0 und O oder 1 und l zum Beispiel. Der Nutzer sollte beides eingeben dürfen, damit man auch URLs eingeben kann, die mal jemand auf ein Blatt Papier gekritzelt hat und man nicht mehr so recht weiss ob das nun eine Null oder ein grosses O war.

[Leonidas]

Ich habe einfach einen simplen Passwort-Generator für Short-URLs verwendet. Zugegeben, sind nicht allzu schön.

[Y0Gi]

Wenn es möglichst kurz und eindeutig sein soll, würde sich dann nicht ein fortlaufender Zähler zur Basis 46 anbieten? Also Buchstaben und Dezimaliffern als "Ziffern"? Vielleicht auch Gross- und Kleinschreibung.

Gerade etwas fortlaufendes möchte ich nicht. Denn genau dann ist es ja wieder möglich, weitere IDs zu erraten, das soll vermieden werden. Auch soll kein z.B. chronologischer Zusammenhang durch in-Reihenfolge-setzen ermittelbar sein.
Oder verstehe ich deinen Ansatz da vielleicht nicht richtig?

Und für die "user friendliness" sollte man einige Zeichen rausnehmen bzw. synonym verwenden können, also 0 und O oder 1 und l zum Beispiel. Der Nutzer sollte beides eingeben dürfen, damit man auch URLs eingeben kann, die mal jemand auf ein Blatt Papier gekritzelt hat und man nicht mehr so recht weiss ob das nun eine Null oder ein grosses O war.

User-friendly muss es nicht sein, der Benutzer soll die Namen nicht von Hand eingeben oder dergleichen.

Ich habe einfach einen simplen Passwort-Generator für Short-URLs verwendet. Zugegeben, sind nicht allzu schön.

Doch, ziemlich genau sowas schwebt mir vor!

Wie erstellst du diese? Es ist ja schön und gut, wenn man Hashes über MD5, SHA* und Konsorten erstellen kann, aber wenn man davon nur die ersten z.B. acht Zeichen verwendet, ist es mit der Eindeutigkeit relativ schnell geschehen.

[Leonidas]

Ich habe einfach einen simplen Passwort-Generator für Short-URLs verwendet. Zugegeben, sind nicht allzu schön.

Doch, ziemlich genau sowas schwebt mir vor!

Wie erstellst du diese? Es ist ja schön und gut, wenn man Hashes über MD5, SHA* und Konsorten erstellen kann, aber wenn man davon nur die ersten z.B. acht Zeichen verwendet, ist es mit der Eindeutigkeit relativ schnell geschehen.

Habe mich mal auf den alten Server verbunden (Last login: Fri Jun 1 18:14:00 2007 ), und nachgeschaut:

Code: Alles auswählen

import string
def gen_short(length=8, chars=string.letters + string.digits):
    """Generator for random, short sequences.
    Modified from a password generator in the Python Cookbook
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/59873"""
    return ''.join(random.choice(chars) for i in range(length))

Wobei du die von BlackJack vorgeschlagenen Änderungen, wie etwa das Entfernen von 0, O, l, 1, I ganz einfach dort implementieren kannst.

[jens]

Wenn es eh eine fortlaufende Nummer gibt, warum dann nicht die mit time.time() kombinieren und daraus eine MD5 oder SHA1 bilden? Die dürfte auch dann eindeutig sein, wenn zwei User gleichzeitig eine ID bekommen

[Y0Gi]

Leonidas: OK, das ist jetzt wirklich ein simpler Ansatz Der beinhaltet ja leider nicht die von Hashverfahren annehmbaren großen Unwahrscheinlichkeiten von Kollisionen, aber selbst da wäre eine Prüfung auf einen bereits vorhandenen Wert keine schlechte Idee. Dann werde ich es wohl so lösen und habe da den Baum vor lauter Wäldern nicht gesehen.

Wenn es eh eine fortlaufende Nummer gibt, warum dann nicht die mit time.time() kombinieren und daraus eine MD5 oder SHA1 bilden? Die dürfte auch dann eindeutig sein, wenn zwei User gleichzeitig eine ID bekommen

Wer sagt, dass es eine fortlaufende Nummer gibt? Ich habe doch mindestens einmal geschrieben, dass dem nicht so ist/sein sollte?

[gerold]

Hallo YOgi!

lutz.horn hat es in diesem Beitrag http://www.python-forum.de/post-81208.html#81208 schon geschrieben. UUIDs oder GUIDs sind genau für deinen Zweck gemacht. Nur musst du dafür auch die volle Länge des erzeugten GUIDs verwenden. GUIDs sind eindeutig und die Wahrscheinlichkeit, dass jemand den gleichen GUID erzeugt, ist unendlich gering.

Mit dem Python-Modul ``uuid.py`` kannst du solche global eindeutige IDs erstellen. Unter Windows könntest du über pywin32 direkt auf ``CreateGuid`` zugreifen. Aber besser du verwendest ``uuid.py`` dafür.

Code: Alles auswählen

>>> import pythoncom
>>> pythoncom.CreateGuid()
IID('{973778F6-CB65-421F-B5E6-96D95677657C}')
>>> 

Diese so erstellten UUIDs brauchst du nicht mehr auf Eindeutigkeit prüfen. So können z.B. Daten von vielen Computern in einer Datenbank gesammelt werden, ohne dass es ID-Kollissionen gibt.

Aber wie schon geschrieben. Du musst dafür die gesamte erzeugte UUID verwenden. --> "973778F6-CB65-421F-B5E6-96D95677657C"

mfg
Gerold


EDIT:

Wie ich soeben sehe, ist das Modul ``uuid`` seit Python 2.5 sogar ein mit Python ausgeliefertes Standardmodul.

--> http://docs.python.org/lib/module-uuid.html

[Leonidas]

Leonidas: OK, das ist jetzt wirklich ein simpler Ansatz Der beinhaltet ja leider nicht die von Hashverfahren annehmbaren großen Unwahrscheinlichkeiten von Kollisionen, aber selbst da wäre eine Prüfung auf einen bereits vorhandenen Wert keine schlechte Idee. Dann werde ich es wohl so lösen und habe da den Baum vor lauter Wäldern nicht gesehen.

Stimmt, ob das "Passwort" verwendet wird, musst du natürlich selbst prüfen. Jede Lösung hat ihre Vor und Nachteile, diese eben die relative "Lesbarkeit", und Einfachkeit aber auch ihre geringe Sicherheit.

[gerold]

Hallo!

Zu diesem Thema passend: PostgreSQL wird ab Version 8.3 den Datentyp UUID besitzen. Damit kann eine UUID endlich auch unter PostgreSQL platzsparend (16 Byte) und indiziiert gespeichert werden. Es soll auch eine Funktion zum automatischen Erstellen von UUIDs mit dazu kommen. So lässt sich eine UUID endlich auch unter PostgreSQL als Primärschlüssel einsetzen, ohne auf den TEXT-Datentyp ausweichen zu müssen.

lg
Gerold

[Y0Gi]

Gerold: Ja, UUIDs werden offenbar genau so hergestellt, wie ich mir das wünsche. Allerdings sind sie einfach zu lang. Sobald ich zwei oder drei davon kombiniere (angenommen, man will sie in einem Forum verwenden, das IDs für Kategorien, Themen und Beiträge verwendet), habe ich schon eine URL, die zweimal um die nördliche Hemisphäre reicht. Ohne RFCs bzgl. der zulässigen Maximallänge zu konsultieren, gefällt mir das verständlicherweise schon nicht.

Für komplett interne Bezeichner würde der Ansatz ansonsten in Frage kommen. Ich möchte diese Dinger aber eben gerne u.a. in URLs und als Dateinamen verwenden. Für letztere fällt auch die Unterscheidung von Groß-/Kleinbuchstaben weg, wenn man nicht möchte, dass einem der unter Unix entwickelte Kram unter Windows um die Ohren fliegt.

An Plattformen (win32) oder DMBS (PostgreSQL) möchte ich mich ungern binden, aber danke für die Hinweise - vielleicht sind sie mir ein andermal von Nutzen.

[Y0Gi]

Wenn ich den Timestamp verwende, so dachte ich, erhalte ich bei theoretisch möglichen mehreren parallelen Zugriffen ja identische Hashes (da ich ja sonst keinen Wert habe, den ich in den Hash mit einbeziehen kann). Jedoch habe ich außer acht gelassen, dass `time.time()` eine Fließkommazahl liefert, bei der Kollisionen durch parallele Aufrufe (die entsprechend so einen eindeutigen Hash erfordern) in einer Webanwendung praktisch fast auszuschließen sind.

Ein Blick in die Doku hat mich wieder an folgendes erinnert:

Note that even though the time is always returned as a floating point number, not all systems provide time with a better precision than 1 second.

Schade :/


Ich habe mich jetzt für ``uuid.uuid4().hex[:12]`` entschieden. Auf diesem Weg wird in einer Funktion, die als `default`-Argument über die Spaltendefinition in SA oder Elixir übergeben wird, ein Wert generiert und auf dessen Existenz in der Datenbank geprüft (bis zu X mal, damit im Falle eines Fehlers nicht die Applikation hängt).

[mitsuhiko]

Warum nicht einfach einen SHA Digest nehmen und dann auf Buchstaben von a-zA-Z0-9 umrechnen?

[Y0Gi]

Solange der Digest einigermaßen zufällig ist, ginge das, klar.

Von Großbuchstaben, falls ich das noch nicht erwähnt habe (edit: doch, habe ich schon), halte ich übrigens nicht so viel, weil die bei Verwendung in Dateinamen problematisch sind, da z.B. Windows Groß-/Kleinschreibung dabei ignoriert.

[mitsuhiko]

Code: Alles auswählen

try:
    from haslib import md5
except ImportError:
    from md5 import new as md5
from time import time
from random import random

base16 = '0123456789abcdef'
base62 = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'

def get_id():
    result = []
    x = reduce(lambda a, b: a * 16 + base16.index(b),
               md5('%s|%s' % (random(), time())).hexdigest(), 0)
    while x:
        result.append(base61[x % 62])
        x //= 62
    return ''.join(result)

Damit sind die Hashes nicht mehr so lange. Man könnte natürlich auch noch mehr Zeichen einbauen, aber ich finde die sind schon ziemlich kurz. Wie viele Kollisionen du rausbekommst musst du testen.