2

Update: Cloud Downloader 2.6

Cloud Downloader 2.6 - SearchingHeute gibt es mal wieder ein Update des Cloud Downloaders. Ab sofort steht der Cloud Downloader somit in Version 2.6 zur Verfügung. Neben einigen Bugfixes, wurden auch in dieser Version wieder Wünsche aus der Community umgesetzt. An dieser Stelle noch einmal vielen Dank an euch User für das tolle Feedback.

Nachfolgend einmal ein kurzer Überblick über die Neuerungen in Version 2.6:

  • [Feature] Such- und Downloadstatus werden nun auch in der Taskbar angezeigt. So kann man den Status verfolgen, auch wenn der Cloud Downloader minimiert ist.
  • [Feature] Coverbilder/Album-Art werden nun in höherer Auflösung (500×500 px) gespeichert.
  • [Feature] Auf Wunsch kann mit einem Klick jeder Song bzw. dessen Album/Künstler auf Amazon gesucht werden.
  • [Bugfix] Soundcloud-Suchanfragen (http://…search?q=) können nun auch wieder ausgelesen werden.
  • [Bugfix] Wenn die Suchergebnisse behalten werden sollen, wird die getroffene Auswahl bei der nächsten Suche nicht mehr zurückgesetzt. (Die Markierungen bleiben erhalten.)
  • [Refactoring] Die Abhängigkeit zum Windows MediaPlayer wurde entfernt. Stattdessen wir nun die NAudio-Bibliothek zum Streamen genutzt. Dies sollte Programmabstürze bei Nutzern vermeiden, die den Windows MediaPlayer nicht (oder nicht mehr) installiert haben.

 

Den Download der neuen Version gibt es wie bisher im Hauptartikel zum Cloud Downloader:

Download: Cloud Downloader 2.6

 

Cloud Downloader 2.6 - Searching  Cloud Downloader 2.6 - Shopping  Cloud Downloader 2.6 - Status in Taskbar

 

0

MAC OSX Mail – Dateien im Anhang statt Inline versenden

Apple Mail - Dateien als AnhangWer zum Senden seiner Mails die Apple OSX Standardsoftware “Mail” nutzt und schon mal versucht hat eine Mail mit Anhängen zu versenden, wird folgendes Problem sicherlich kennen.

Mail fügt Anhänge wie Bilder und PDF-Dokumente nicht, wie aus der Windows-Welt gewohnt, als reinen Anhang an, sondern bettet die Dateien (sogenanntes: Inlining) in die Mail ein.

Nutzt der Empfänger der E-Mail ebenfalls Apple Mail, so stellt dies kein größeres Problem dar. Setzt der Empfänger jedoch einen der vielen Windows-Mailclients oder einen Webmail-Client ein, so kann diese Art des Anhangversands zu Problemen führen.

Deshalb soll es im folgenden Artikel darum gehen, wie man mittels eines kleinen Tricks Anhänge mit Apple Mail auch wirklich “im Anhang” versendet.

Bild- und PDF-Dateien im Anhang versenden

Um Anhänge wie Bild- und PDF-Dateien in Apple OSX’ Mailprogramm “Mail” zu versenden, ohne diese in die Mail einzubetten, ist leider keine Einstellung im Standard-Menü vorhanden.

Stattdessen muss folgende Codezeile im Terminal ausgeführt werden. Der Terminal kann entweder über “Programme –> Dienstprogramme –> Terminal” oder über die Spotlight-Suche mit dem Begriff “Terminal” gestartet werden.

Innerhalb des Terminals muss folgender Befehl abgesetzt werden:

defaults write com.apple.mail DisableInlineAttachmentViewing -bool yes

Nachdem Ausführen des Befehls werden Dateianhänge nicht mehr als Vorschau, sondern als Anhang/Verknüpfung dargestellt. Die beiden nachfolgenden Screenshots zeigen ein und dieselbe Datei vor und nach Ausführung des Befehls.

Der Befehl überschreibt dabei den Default-Wert des DisableInlineAttachmentViewing-Parameters der Mail-Anwendung. Das heißt konkret: Die Änderung ist persistent und somit auch nach Schließen und erneutem Öffnen der Mail-App noch vorhanden.

Apple Mail - Dateien als Vorschau Apple Mail - Dateien als Anhang

Um die Einstellung wieder rückgängig zu machen, genügt es, die folgende Zeile Code im Terminal auszuführen.

defaults write com.apple.mail DisableInlineAttachmentViewing -bool no

Sollte es noch Probleme beim Empfang der Mails auf Windows-PCs geben, so kann dies an folgender Einstellung liegen.

MAC OSX Mail und die Windows-Kompatibilität

Der Apple Mail-Client verzichtet von sich aus teilweise die Dateiendung der Anhänge mitzuschicken. Dies kann auf Windows-Rechnern zu Problemen führen.

Apple Mail - Windows-kompatible DateianhängeAbhilfe schafft hierbei die Einstellung “Anhänge immer Windows-kompatibel senden“, welche sich im an folgender Stelle im Mail-Menü versteckt: “Bearbeiten –> Anhänge –> Anhänge immer Windows-kompatibel senden”.

Mit den beiden Tipps aus diesem Artikel sollte dann auch endlich ein sorgenfreier Mailversand inklusive Dateianhänge möglich sein.

Haben die Tipps bei euch geklappt und hat euch der Artikel weitergeholfen? Dann klickt auf den Teilen/Like-Button und helft auch anderen von dieser Information zu profitieren!

1

Spielkarten mit C# und AForge.NET analysieren

KartenDetektor - Spielkarten in C# erkennenWie im letzten Artikel schon angemerkt, soll es wieder ein wenig in Richtung der Wurzeln dieses Blogs gehen. Konkret heißt das mehr Code-Beispiele und Tutorials.

Dieser Artikel ist ein weiterer Schritt in diese Richtung. Nachdem wir im letzten Artikel ein C#-Tool geschrieben haben, mit dem man die Gewinnwahrscheinlichkeit einer Pokerhand ausrechnen kann, befassen wir uns in diesem Artikel mit den Themen Bildverarbeitung und maschinellem Sehen in C#.

Das Tool, welches wir heute entwickeln, analysiert Screenshots eines Pokerspiels und kann die Karten inklusive Kartenwert und Kartenfarbe automatisiert auslesen. Hierzu nutzen wir die ziemlich mächtige OpenSource-Bibliothek “AForge.NET”, welche etliche Klassen und Methoden für die Bereiche maschinelles Sehen und Künstliche Intelligenz bietet.

Vor dem Coding

Bevor es mit der Programmierung losgeht, müssen noch ein, zwei Dinge erledigt werden. Zum einen brauchen wir eine Palette an Screenshots mit Spielkarten, die wir analysieren können und zum anderen müssen wir uns die benötigten AForge-Dlls beschaffen.

Spieltisch-Screenshots zur VerarbeitungFür die Screenshots habe ich mir das erstbeste Online-Casino geschnappt, das mir zwischen die Finger kam. Im Prinzip ist es jedoch egal, aus welchem Casino die Screenshots stammen, solange die Karten komplett auf dem Screenshot sind und nicht durch andere Elemente verdeckt werden.

Bei der Wahl des Online Casinos hilft eine Google-Suche oder ein Blick in eine der Casino-Vergleichslisten. Die meisten Casinos bieten auch einen Spielgeld-Modus an, sodass für das Anlegen der Screenshots keine Kosten entstehen.

Ist der Anbieter gefunden, sollten zumindest so viele Screenshots gemacht werden, dass mindestens jede Kartenfarbe und jeder Kartenwert einmal vorkommt.

Die AForge-Bibliothek kann direkt von der AForge-Webseite geladen werden. Von den vier Download-Links sollte jener mit “Libraries only” im Titel gewählt werden. (Wer sich gerne alles installieren möchte, kann auch den Installer laden – nötig ist das jedoch nicht.)

Projekt anlegen – das GUI-Layout

Wenn die Vorbereitungen getroffen sind, kann es mit der Entwicklung losgehen. Entwickelt wird, wie fast immer hier im Blog, mit Microsofts Visual Studio.

Als erstes legen wir ein WinForms-Projekt an – ich habe es “KartenDetektor” genannt – und gestalten die Programmoberfläche.

Um sich einen besseren Überblick über die einzelnen Teilbilder der Bildanalyse machen zu können, habe ich für die verschiedenen Analyseschritte eigene PictureBoxen hinzugefügt, sodass die Ergebnisse der einzelnen Schritte separat betrachtet werden können.

KartenDetektor - GUI-LayoutIm Endeffekt würden auch weit weniger PictureBoxen reichen, zur (eventuellen) Fehlersuche und während der Entwicklung macht die große Anzahl aber in der Tat Sinn.

Das Layout, mit dem wir starten, kann dem links-stehenden Screenshot entnommen werden. Es besteht aus 3 GroupBoxen, die jeweils 5 PictureBoxen und 5 TextBoxen enthalten. Eine Gruppe dient für die Kartenfarben-Erkennung, eine für die Kartenwerte und eine für die Karten in der Gesamtansicht.

Weiter habe ich 2 Pictureboxen zur Ansicht des Screenshots (in der normalen und der bearbeiten Variante) hinzugefügt. Das letzte Nutzerelement ist ein Button, mit dem man die verschiedenen Screenshots durchschalten kann.

Nach dem die GUI-Elemente platziert sind, legen wir noch zwei Eventhandler an – einen für das FormLoad-Event und einen für das ButtonClick-Event.

Als letzten Schritt fügen wir über “Verweise->Verweis hinzufügen” die drei, für unser Projekt benötigten, AForge-Dlls “AForge.dll”, “AForge.Imaging.dll” und “AForge.Math.dll” hinzu.

Using-Direktiven, Hilfsklassen und Strukturen

Nachdem die Arbeiten im Form-Designer abgeschlossen sind, können wir uns an den Code wagen. Als erstes fügen wir die nötigen using-Direktiven hinzu.

using AForge;
using AForge.Imaging;
using AForge.Imaging.Filters;
using AForge.Math.Geometry;
using System.Drawing.Imaging;

Im Kopfbereich unserer Form-Klasse legen wir außerdem noch eine Liste an, in der wir später die Dateinamen der Screenshots ablegen wollen.

//Liste für die Eingabe-Screenshots
List<string> files = new List<string>();

Damit wir im Logikteil nachher etwas geschickter arbeiten können, brauchen wir noch ein paar Hilfsstrukturen/-Klassen. Zum einen eine Klasse, die eine Spielkarte samt Eigenschaften und Grafiken abbildet und zum anderen eine Struktur, die Kartenfarben und -werte abbilden kann.

//Spielkarten Klasse - enthält alle Informationen zu einer Karte
private class Card
{
    //Bild der Karte
    public Bitmap cardImg { get; set; }

    //Bildausschnitt mit der Kartenfarbe
    public Bitmap identifierSuitImg { get; set; }

    //Bildausschnitt mit dem Wert
    public Bitmap identifierValueImg { get; set; }

    //Analysierte Kartenfarbe
    public string suit { get; set; }

    //Analysierter Wert
    public string value { get; set; }
}

//Identitätsstruktur
private struct Identifier
{
    //Name des Samples (z.B. Karo, Ass, ...)
    public string name { get; set; }

    //Sample-Grafik
    public Bitmap sample { get; set; }
}

Folgende, weitere Methode wird im späteren Verlauf des Artikels benötigt und dort dann auch weiter erklärt.

public static Bitmap normalizeForEqualityCheck(Bitmap source)
{
    //Den ersten schwarzen Pixel von rechts erkennen (=linke Schnittkante)
    int left = -1, right = -1, up = -1, down = -1;
    int clip = 255;
    for (int x = 0; x < source.Width; x++)
    {
        for (int y = 0; y < source.Height; y++)
        {
            var col = source.GetPixel(x, y);
            if ((col.R + col.B + col.B) / 3f < clip)
            {
                left = x;
                break;
            }
        }
        if (left != -1)
            break;
    }

    //Den ersten schwarzen Pixel von rechts erkennen (=rechte Schnittkante)
    for (int x = source.Width-1; x > 0; x--)
    {
        for (int y = 0; y < source.Height; y++)
        {
            var col = source.GetPixel(x, y);
            if ((col.R + col.B + col.B) / 3f < clip)
            {
                right = x;
                break;
            }
        }
        if (right != -1)
            break;
    }

    //Den ersten schwarzen Pixel von oben erkennen (=obere Schnittkante)
    for (int y = 0; y < source.Height; y++)
    {
        for (int x = 0; x < source.Width; x++)
        {
            var col = source.GetPixel(x, y);
            if ((col.R + col.B + col.B) / 3f < clip)
            {
                up = y;
                break;
            }
        }
        if (up != -1)
            break;
    }

    //Den ersten schwarzen Pixel von unten erkennen (=unten Schnittkante)
    for (int y = source.Height-1; y > 0; y--)
    {
        for (int x = 0; x < source.Width; x++)
        {
            var col = source.GetPixel(x, y);
            if ((col.R + col.B + col.B) / 3f < clip)
            {
                down = y;
                break;
            }
        }
        if (down != -1)
            break;
    }

    //Grafik an den Schnittkanten zuschneiden
    Crop cropSuit = new Crop(new Rectangle(left, up, right-left, down-up));
    var output = cropSuit.Apply(source);
    //Grafik auf Norm-Maße strecken
    ResizeBilinear resizer = new ResizeBilinear(60, 60);
    return resizer.Apply(output);
}

Nun kann es mit der Programmierung der Logik losgehen. Wir beginnen analog zur Programmablauflogik mit FormLoad-Event.

Der Programmstart

Beim Programmstart werden alle Screenshots aus dem Verzeichnis “\samples\n” (relativ zum Ausführungsordner) des KartenDetektors in eine Liste geladen.

private void Form1_Load(object sender, EventArgs e)
{
    //Dateinamen der Screenshots in die Liste laden
    files = System.IO.Directory.GetFiles(Application.StartupPath + "\\samples\\n").ToList();

    //Ersten Screenshot in Bitmap-Objekt laden
    Bitmap inputBmp = (Bitmap)Bitmap.FromFile(files[0]);
    //Analyse durchführen
    analyzeCards(inputBmp);
    //Screenshot aus Liste entfernen
    files.RemoveAt(0);
}

Nach dem Laden der Screenshots wird die erste Datei geöffnet, in eine Bitmap geladen und an die Analysemethode übergeben.

Der Kartenzuschnitt

Kommen wir nun zum Herzstück des Programms. Der Methode zur Kartenanalyse. Da in der Methode relativ viel passiert, werden wir sie Stück für Stück aufbauen. Solltet ihr dabei einmal den Überblick verlieren, könnt ihr euch das komplette, lauffähige Demoprojekt am Ende dieses Artikels herunterladen.

Die Methode nimmt als einziges Argument eine Bitmap an, welche den Screenshot vom Spieltisch enthalten sollte.

Danach wird der Screenshot auf zuvor definierter Maß (1364×726 px) gestreckt. Dies geschieht, da im weitere Verlauf Bildausschnitte verwendet werden, die relativ zu den Screenshot-Abmessungen stehen. Von daher bringen wir alle Screenshots erst einmal auf dieselbe Größe.

Ist die einheitliche Größe gegeben, legen wir eine Arbeitskopie (processedBmp) an.

public void analyzeCards(Bitmap inputBmp)
{
    //Liste für Spielkarten-Objekte anlegen
    List<Card> cards = new List<Card>();

    //Screenshot auf Standardformat ziehen, damit unabhängig von der Auflösung
    //die nachfolgenden Koordinaten stimmen
    ResizeBilinear filterRes = new ResizeBilinear(1364, 726);
    inputBmp = filterRes.Apply(inputBmp);

    //Arbeitskopie des Screenshots anlegen
    Bitmap processedBmp = inputBmp.Clone() as Bitmap;

Nun wird die Arbeitskopie erst mit einem Farbfilter, dann mit einem Graustufenfilter und schlussendlich mit einem Schwarz-Weiß-Filter bearbeitet. Dies ist nötig, da wir im Anschluss einen sogenannten Blobcounter anwendenden wollen und dieser Grafiken in s/w bevorzugt verarbeitet.

//Farbfilter für die Arbeitskopie anlegen und anwenden, um
//bessere Ergebnisse bei der S/W-Konvertierung zu erhalten
ColorFiltering filter = new ColorFiltering();
filter.Red = new AForge.IntRange(250, 255);
filter.Green = new AForge.IntRange(250, 255);
filter.Blue = new AForge.IntRange(250, 255);
filter.ApplyInPlace(processedBmp);

//Arbeitskopie über Graustaufen nach S/W konvertieren
FiltersSequence seq = new FiltersSequence();
seq.Add(Grayscale.CommonAlgorithms.BT709);
seq.Add(new IterativeThreshold());
processedBmp = seq.Apply(processedBmp);

Der Blobcounter kann Objekte innerhalb einer Bitmap erkennen. Wir wollen ihn Nutzen, um die Spielkarten bzw. dessen Positionen innerhalb des Screenshots zu erkennen.

Screenshot des Spieltischs - vor und nach der Bearbeitung für den BlobcounterUm bessere Ergebnisse zu erhalten, konfigurieren wir den Blobcounter vorab über die Parameter “MinHeight”, “MaxHeight”, “MinWidth”, “MaxWidth” und FilterBlobs.

Die Min-Max-Parameter geben an, wie groß bzw. klein ein gefundener Blob maximal bzw. minimal sein darf. Hierdurch erreichen wir, dass möglichst nur die Spielkarten auf dem Screenshot als Blob gefunden werden und nicht etwa andere, kleinere oder größere Gegenstände auf dem Screenshot.

Der Parameter “FilterBlobs” wiederum beschreibt nur, um die in den Min-Max-Filtern gesetzten Maße angewendet werden sollen.

Abschließend entfernen wir die ersten beiden Ergebnisse aus der Blob-Liste, da es sich hierbei um die zwei verdeckten Karten auf dem Screenshot handelt. (Dies kann jedoch von Poker-Applikation zu Poker-Applikation abweichen. Da ist ausprobieren angesagt.)

//Spielkarten per Blobcounter finden. Durch MinHeight und MaxHeight wird die
//Größe der gefunden Blobs so eingeschränkt, dass nur Karten gefunden werden
BlobCounter extractor = new BlobCounter();
extractor.FilterBlobs = true;
extractor.MinWidth = extractor.MinHeight = 40;
extractor.MaxWidth = extractor.MaxHeight = 70;
extractor.ProcessImage(processedBmp);
var blobs = extractor.GetObjectsInformation().ToList();

//Die ersten beiden Blobs entfernen (da dies die zwei verdeckten Karten
//auf dem Screenshot sind.
blobs.RemoveRange(0, 2);

Nun haben wir also den gestreckten Original-Screenshot (inputBmp), das S/W-Abbild davon (processedBmp) und eine Liste mit den Koordinaten der Spielkarten auf dem Screenshot (blobs).

Im nächsten Schritt durchlaufen wir alle gefunden Blobs/alle Spielkarten, um diese zu analysieren.

Zuschnitt der SpielkarteFür jeden Blob/jede Spielkarte ermitteln wir die Punkte, die die Kontur der Spielkarte bilden (edgePoints) sowie die 4 Eckpunkte der Spielkarte (corners). Mit dem Wissen über die Eckpunkte können wir nun den Ausschnitt aus dem Screenshot erzeugen, der die Spielkarte darstellt und diesen mittels QuadrilateralTransformation in ein rechteckiges Format entzerren.

Im Anschluss prüfen wir, ob die Spielkarten-Grafik auf der Seite liegt, und stellen sie ggf. per Drehung (Rotate270FlipNone) auf.

Abschließend strecken wir die Karte per (ResizeBilinear) auf eine definierte Größe, sodass alle Spielkarten/Blobs gleich groß sein werden.

Die bearbeitete Spielkarten-Grafik legen wir in einer neuen Instanz der Card-Klasse ab.

//Graphics-Object vom Screenshot (nicht der S/W-Arbeitskopie) anlegen,
//um die gefunden Blobs (=Spielkarten) einzeichnen zu können
Graphics gfx = Graphics.FromImage(inputBmp);

//Durch alle Blobs (=gefunden Kartenpositionen) iterieren
foreach (Blob blob in blobs)
{
    //Eckpunkte des Spielkarten-Blobs in Liste schreiben
    List<IntPoint> edgePoints = extractor.GetBlobsEdgePoints(blob);
    //Spielkarten-Ecken finden
    List<IntPoint> corners = PointsCloud.FindQuadrilateralCorners(edgePoints);

    //Spielkarte in Rechteck tranformieren/entzerren
    QuadrilateralTransformation quadTransformer = new QuadrilateralTransformation();
    quadTransformer.SourceQuadrilateral = corners;
    quadTransformer.AutomaticSizeCalculaton = true;
    Bitmap tempImg = quadTransformer.Apply(inputBmp); 

    //Wenn die Spielkarte auf der Seite liegt, Karte drehen/aufrichten
    if (tempImg.Width > tempImg.Height)
        tempImg.RotateFlip(RotateFlipType.Rotate270FlipNone); 

    //Spielkarte auf Standardmaße strecken, damit die nachfolgenden
    //Koordinaten auf alle Spielkarten-Grafiken anwendbar sind
    ResizeBilinear resizer = new ResizeBilinear(200, 300);
    tempImg = resizer.Apply(tempImg); 

    //Neue Spielkarten-Objekt anlegen und die Spielkarten-Grafik hinzufügen
    var card = new Card() { cardImg = tempImg };

Nun haben wir den ersten Zuschnitt einer Spielkarte, den wir jetzt tiefer analysieren können. Im ersten Schritt wollen wir den Wert der Spielkarte (z.B. 2, 6 ,J ,K , Ass) ermitteln. Hierzu fertigen wir wieder einen kleineren Zuschnitt der Karte an, in dem sich der Wert befindet.

Zuschnitt des KartenwertsDanach vergleichen wir den Zuschnitt per ExhaustiveTemplateMatching mit allen möglichen Kartenwerten. Dies Samples zum Vergleich haben ich zuvor aus den Screenshots extrahiert und als Ressource im Programm hinterlegt.

Bei jedem Abgleich überprüfen wir, ob der Ähnlichkeitsfaktor größer als der bisher größte Treffer ist. Wenn dem so ist, nehmen wir den Wert als vermutlichen Treffer an.

//Bildauschnitt mit dem Kartenwert erzeugen
Crop cropValue = new Crop(new Rectangle(0, 0, 70, 60));
Bitmap tempValueImg = cropValue.Apply(tempImg);
//Wert-Ausschnitt nach S/W konvertieren
tempValueImg = seq.Apply(tempValueImg);
//Wert-Ausschnitt im Karten-Objekt ablegen
card.identifierValueImg = tempValueImg;

//Liste mit Wert-Samples erstellen
List<Identifier> valueSamples = new List<Identifier>()
{
    new Identifier(){ name = "2", sample = KartenDetektor.Properties.Resources._2 },
    new Identifier(){ name = "3", sample = KartenDetektor.Properties.Resources._3 },
    new Identifier(){ name = "4", sample = KartenDetektor.Properties.Resources._4 },
    new Identifier(){ name = "5", sample = KartenDetektor.Properties.Resources._5 },
    new Identifier(){ name = "6", sample = KartenDetektor.Properties.Resources._6 },
    new Identifier(){ name = "7", sample = KartenDetektor.Properties.Resources._7 },
    new Identifier(){ name = "8", sample = KartenDetektor.Properties.Resources._8 },
    new Identifier(){ name = "9", sample = KartenDetektor.Properties.Resources._9 },
    new Identifier(){ name = "10", sample = KartenDetektor.Properties.Resources._10 },
    new Identifier(){ name = "Bube", sample = KartenDetektor.Properties.Resources.j },
    new Identifier(){ name = "Dame", sample = KartenDetektor.Properties.Resources.q },
    new Identifier(){ name = "König", sample = KartenDetektor.Properties.Resources.k },
    new Identifier(){ name = "Ass", sample = KartenDetektor.Properties.Resources._as }
};

//Alle Samples auf den Wert-Ausschnitt anwenden
float maxSimilar = 0f;
foreach (var valueSample in valueSamples)
{
    //Ähnlichkeit zwischen Sample und Wert-Ausschnitt ermitteln
    ExhaustiveTemplateMatching tm = new ExhaustiveTemplateMatching(0);
    TemplateMatch[] matchings = tm.ProcessImage(card.identifierValueImg, valueSample.sample);

    //Wenn das aktuell getestete Sample besser passt, als das bisher beste,
    //setze den Wert als identifizierten Kartenwert
    if (matchings.Length > 0 && matchings[0].Similarity > maxSimilar)
    {
        maxSimilar = matchings[0].Similarity;
        card.value = valueSample.name;
    }
}

Nun haben wir den Spielkarten-Zuschnitt, den Wert-Zuschnitt und den ermittelten Wert in unserer card-Instanz gespeichert.

Zuschnitt der KartenfarbeIm nächsten Schritt geht es um die Ermittlung der Kartenfarbe (engl. “suit”). Theoretisch verläuft die Wertermittlung analog zur Analyse des Kartenwerts. Der einzige Unterschied ist, dass wir den Zuschnitt als auch das Sample mit der Funktion normalizeForEqualityCheck() zuvor noch exakter zuschneiden und auf eine Normgröße bringen, damit die Trefferquote beim Abgleich besser wird. (Der Code für die normalizeForEqualityCheck-Funktion befindet sich im Abschnitt “Hilfsklassen und Strukturen” dieses Artikels.)

Die “Normalisierung” ist bei den Kartenfarben nötig, da sich die Bilder im Gegenteil zu den Werten stark ähneln. Zudem ist die Auflösung der Flash-Applikation des Online Casino’s nicht allzu hoch, sodass die Ausschnitte nur eine sehr geringe Auflösung haben. Beide Faktoren erschweren den Vergleich per Sample, sodass die Samples möglichst genau zugeschnitten werden müssen.

//Bildauschnitt mit der Kartenfarbe erzeugen
Crop cropSuit = new Crop(new Rectangle(0, 60, 70, 65));
Bitmap tempSuitImg = cropSuit.Apply(tempImg);
//Kartenfarben-Ausschnitt nach S/W konvertieren
tempSuitImg = seq.Apply(tempSuitImg);
//Kartenfarben-Ausschnitt exakt zuschneiden und normalisieren
tempSuitImg = normalizeForEqualityCheck(tempSuitImg);
//Kartenfarben-Ausschnitt im Karten-Objekt ablegen
card.identifierSuitImg = tempSuitImg;

//Liste mit Kartenfarben-Samples erstellen
List<Identifier> suitSamples = new List<Identifier>()
    {
        new Identifier(){ name = "Karo", sample = KartenDetektor.Properties.Resources.diamonds },
        new Identifier(){ name = "Herz", sample = KartenDetektor.Properties.Resources.hearts },
        new Identifier(){ name = "Pik", sample = KartenDetektor.Properties.Resources.spades },
        new Identifier(){ name = "Kreuz", sample = KartenDetektor.Properties.Resources.clubs }
    };

//Alle Samples auf den Kartenfarben-Ausschnitt anwenden
maxSimilar = 0f;
foreach (var suitSample in suitSamples)
{
    //Ähnlichkeit zwischen Sample und Kartenfarben-Ausschnitt ermitteln
    ExhaustiveTemplateMatching tm = new ExhaustiveTemplateMatching(0);
    //Kartenfarben-Sample exakt zuschneiden, normalisieren und mit Ausschnitt abgleichen
    TemplateMatch[] matchings = tm.ProcessImage(card.identifierSuitImg, normalizeForEqualityCheck(suitSample.sample));

    //Wenn das aktuell getestete Sample besser passt, als das bisher beste,
    //setze die Farbe als identifizierte Kartenfarbe
    if (matchings.Length > 0 && matchings[0].Similarity > maxSimilar)
    {
        maxSimilar = matchings[0].Similarity;
        card.suit = suitSample.name;
    }
}

Nun haben wir unsere erste Karte analysiert. Wir haben sowohl den Grafikausschnitt, der die Karte darstellt als auch die Kartenfarbe sowie den Kartenwert im card-Objekt hinterlegt.

Nun fügen wir die fertig analysierte Karte der Kartenliste hinzu und zeichnen (nur der Übersicht halber) die Kartenkonturen im Ausgangs-Screenshot ein.

//Spielkarte der Spielkartenliste hinzufügen
    cards.Add(card);

    //Karte zur Visualisierung auf dem Screenshot markieren
    foreach (var c in edgePoints)
    {
        gfx.DrawRectangle(Pens.Red, new Rectangle(c.X, c.Y, 1, 1));
    }
}

Der Analyse-Teil ist hiermit abgeschlossen. Nach dem Einzeichen, wird der nächste Blob/die nächste Karte analysiert.

Sind alle Karten analysiert, werden die Ergebnisse in den Picture- als auch TextBoxen ausgegeben.

//Kartenfarben-Ausschnitte in PictureBoxen ausgeben
    //und ermittelte Farben in Textboxen anzeigen
    pictureBoxSuit1.BackgroundImage = cards[0].identifierSuitImg;
    textBoxSuit1.Text = cards[0].suit;
    pictureBoxSuit2.BackgroundImage = cards[1].identifierSuitImg;
    textBoxSuit2.Text = cards[1].suit;
    pictureBoxSuit3.BackgroundImage = cards[2].identifierSuitImg;
    textBoxSuit3.Text = cards[2].suit;
    pictureBoxSuit4.BackgroundImage = cards[3].identifierSuitImg;
    textBoxSuit4.Text = cards[3].suit;
    pictureBoxSuit5.BackgroundImage = cards[4].identifierSuitImg;
    textBoxSuit5.Text = cards[4].suit;

    //Kartenwerte-Ausschnitte in PictureBoxen ausgeben
    //und ermittelte Werte in Textboxen anzeigen
    pictureBoxValue1.BackgroundImage = cards[0].identifierValueImg;
    textBoxValue1.Text = cards[0].value;
    pictureBoxValue2.BackgroundImage = cards[1].identifierValueImg;
    textBoxValue2.Text = cards[1].value;
    pictureBoxValue3.BackgroundImage = cards[2].identifierValueImg;
    textBoxValue3.Text = cards[2].value;
    pictureBoxValue4.BackgroundImage = cards[3].identifierValueImg;
    textBoxValue4.Text = cards[3].value;
    pictureBoxValue5.BackgroundImage = cards[4].identifierValueImg;
    textBoxValue5.Text = cards[4].value;

    //Karten-Grafiken in PictureBoxen ausgeben
    //und ermittelte Farben & Werte in Textboxen anzeigen
    pictureBoxCard1.BackgroundImage = cards[0].cardImg;
    textBoxCard1.Text = cards[0].suit + "-" + cards[0].value;
    pictureBoxCard2.BackgroundImage = cards[1].cardImg;
    textBoxCard2.Text = cards[1].suit + "-" + cards[1].value;
    pictureBoxCard3.BackgroundImage = cards[2].cardImg;
    textBoxCard3.Text = cards[2].suit + "-" + cards[2].value;
    pictureBoxCard4.BackgroundImage = cards[3].cardImg;
    textBoxCard4.Text = cards[3].suit + "-" + cards[3].value;
    pictureBoxCard5.BackgroundImage = cards[4].cardImg;
    textBoxCard5.Text = cards[4].suit + "-" + cards[4].value;

    //Screenshot mit eingezeichneten Karten und Arbeitskopie anzeigen
    pictureBoxScreenshot.BackgroundImage = inputBmp;
    pictureBoxScreenshotProcessed.BackgroundImage = processedBmp;
}

Nun sind wir mit der Analysefunktion fertig. Das letzte Stückchen Code ist für den ClickEvent-Handler, der den nächsten Screenshot laden soll. Im Prinzip gleicht er dem Code aus dem FormLoad-Event.

private void button1_Click(object sender, EventArgs e)
{
    //Solange noch Screenshots vorhanden sind...
    if (files.Count() > 0)
    {
        //...lade Screenshot in Bitmap und starte Analyse
        Bitmap inputBmp = (Bitmap)Bitmap.FromFile(files[0]);
        analyzeCards(inputBmp);
        files.RemoveAt(0);
    }
    else
    {
        //Keine Screenshots mehr in der Liste
        MessageBox.Show("Alle Samples durch.");
    }
}

Allen, die sich bis hierhin erfolgreich durchgekämpft haben, wünsche ich schon mal herzlichen Glückwünsch und sage: “Hut ab!”.

Download: Karten Detektor Visual Studio Projekt

Wer zwischenzeitlich ausgestiegen ist, kann sich das komplette Projekt über oben-stehenden Link herunterladen und nachforschen, wo es klemmt.

Fazit und Ausblick

Wie schon im letzten Artikel gezeigt ist das Themenfeld der Kartenspiele wunderbar für diverse Programmierübungen geeignet.

Wer nach dem Artikel nun Lust auf mehr verspürt, dem seien folgende Anregungen zur Erweiterung des Programms gegeben.

  • Analysieren von mehr als 5 Karten
  • Kombinieren dieses Programms mit der Gewinnwahrscheinlichkeitsberechnung aus dem letzten Artikel hier im Blog
  • Verschönerung des GUIs

Wenn ihr weitere Ideen, Kritik oder (gerne auch) Lob habt, dann lasst es mich wissen und schreibt einen Kommentar. Ich freue mich auf euer Feedback!

0

Berechnung der Gewinnwahrscheinlichkeit beim Poker in C#

PokerChancenRechner - BerechnungHeute geht es wieder einmal um die Erstellung eines kleinen C#-Tools. Somit begeben wir uns thematisch wieder einmal in Richtung “Back to the roots” der Code-Bude.

Bei dem Tool handelt es sich um eine kleine Applikation, die Siegchancen einer Poker-Hand ermittelt. Das Tool erwartet als Eingabe die zwei Karten, die ein Spieler auf der Hand hat, sowie die drei initial ausgelegten Karten auf dem Deck (der sogenannte “Flop”) und berechnet daraus die Gewinnchancen für den Spieler.

Bevor nun die Ersten “Aber Poker ist doch ein Glücksspiel und Glücksspiele kann man nicht berechnen” schreien, wollen wir nachfolgend noch einmal kurz die Frage nach dem “Glücksspiel” stellen.

Ist Poker Glücks- oder Geschicklichkeitsspiel?

Zwar wird Poker in Deutschland rechtlich gesehen weit überwiegend zu den Glücksspielen gezählt, jedoch ist dies abseits der rein rechtlichen Regelung gar nicht so eindeutig.

Neben der wachsenden Popularität sowohl in Form von Online-Poker, TV-Duellen wie Stefan Raabs Pokernacht und Livestreams der großen Poker-Events gibt es auch noch weitere Gründe, warum Glücksspiel nicht gleich Glücksspiel ist.

Entgegen, zum Beispiel, dem Roulette-Spiel oder einem “Einarmigen Banditen”, kann der Spieler beim Poker aktiv Einfluss auf das Spiel nehmen. Neben der psychologischen Komponente lässt sich auch, unter Zuhilfenahme des Wissens der bereits ausgegebenen Karten, statistisch berechnen, wie hoch die Gewinnwahrscheinlichkeit einer Hand ist.

Forscher der Universität Hamburg sind im Rahmen einer Untersuchung sogar zu dem Entschluss gekommen, dass Poker eher als Geschicklichkeits- denn als Glücksspiel anzusehen ist. (Wobei sie das Pokerspiel dennoch nicht verharmlosen, sondern für eine Regulierung in Abhängigkeit der Sozialschädlichkeit eines Spiels anstelle der Regulierung in Abhängigkeit der Glücksspieldefinition plädieren.)

Fakt ist, dass die Wahrscheinlichkeit mit einer Pokerhand zu gewinnen, in Abhängigkeit zum Flop steht und sich dieser Wert berechnen lässt. Dies ist zwar kein Garant für einen Sieg, hilft jedoch beim Training, ein Gefühl für den Wert einer Hand zu erlangen. Und deshalb wollen wir nachfolgend ein kleines C#-Tool zur Berechnung eben dieser Wahrscheinlichkeit schreiben.

Poker-Gewinnchance mit C# berechnen

Für die Entwicklung des Tools nutzen wir das Visual Studio und legen eine WinForms-Anwendung an. Ich habe die Applikation “PokerChancenRechner” genannt.

Wie vielleicht schon aus anderen Artikeln hier auf code-bude.net bekannt, gestalten wir zuerst das GUI im Form-Designer, bevor es ans Coding geht. Für die Anwendung brauchen wir mindestens:

  • 5x ListBox (Kartenwerte, Kartenfarben, Zielstapel, Handstapel, Deck-/Tischstapel)
  • 3x Buttons (Karte auf einen Stapel legen, Stapel zurücksetzen, Wahrscheinlichkeit berechnen)
  • 1x Label (zur Anzeige der Gewinnwahrscheinlichkeit)

Ich habe zudem noch vier GroupBoxen platziert, um das Layout etwas zu strukturieren. Hier gilt aber: “Alles kann, nichts muss.”

PokerChancenRechner - StartDie Anordnung der Elemente könnt ihr nebenstehendem Screenshot entnehmen.

Wenn die Elemente platziert sind, benötigen wir noch Eventhandler – insgesamt 4 Stück. Einen Click-Handler pro Button und den FormLoad-Eventhandler. Diese können entweder über das Events-Eigenschaftsfenster des jeweiligen Controls oder direkt im Code-File angelegt werden.

Laden der GUI-Werte

Sind Controls und Eventhandler angelegt, kann es fast schon mit dem Coding losgehen. Zuvor binden wir jedoch noch die “HandEvaluator” Klassenbibliothek ein, die uns bei der Berechnung der gesuchten Wahrscheinlichkeit unterstützt. Die dazugehörige DLL-Datei kann kostenlos auf folgender codeproject.com-Projektseite heruntergeladen werden.

Nachdem Download fügen wir die DLL per “Rechtsklick->Verweis hinzufügen” auf “Verweise” hinzu. Danach schreiben wir noch folgende Using-Direktive in den Kopf unserer Form1.cs-Datei:

using HoldemHand;

Nun kann es mit dem Coding losgehen. Im ersten Schritt wollen wir die Initialwerte laden. Dies machen wir im FormLoad-Event unserer Applikation. Bei den Werten, die in die Listboxen geladen werden sollen, handelt es sich um die Kartenwerte, die Kartenfarben und die Zielstapel (Hand oder Deck). Nachfolgend der Code für das FormLoad-Event inklusive Kommentaren.

//Kartenwerte und dazugehörige Bezeichnungen für die Poker-Library
private Dictionary<string, string> cards = new Dictionary<string, string>()
{
    {"2", "2"}, {"3", "3"}, {"4", "4"}, {"5", "5"}, {"6", "6"}, {"7", "7"},
    {"8", "8"}, {"9", "9"}, {"10", "10"}, {"Bube", "J"}, {"Dame", "Q"},
    {"König", "K"}, { "Ass", "A" }
};

//Kartenfarben und dazugehörige Bezeichnungen für die Poker-Library
private Dictionary<string, string> colors = new Dictionary<string, string>()
{
    {"Pik", "s"}, {"Herz", "h"}, {"Karo", "d"}, {"Kreuz", "c"}
};

private void Form1_Load(object sender, EventArgs e)
{
    //Kartenbezeichnungen, -farben und Stapel in die Listboxen laden
    listBoxCard.Items.AddRange(cards.Select(x => x.Key).ToArray());
    listBoxColor.Items.AddRange(colors.Select(x => x.Key).ToArray());
    listBoxStack.Items.AddRange(new string[]{"Hand", "Deck"});
}

Die Lösung mittels Dictionary hat folgenden Grund: Die HandEvaluator-Library nimmt die Spielhände (also die Karten in der Hand des Spielers) nur in einem bestimmten Format an, welches aus Abkürzungen der englischen Kartennamen besteht. Da dies für den Nutzer jedoch relativ unverständlich sein kann, speichern wir die Kurzbezeichnungen für die Library inklusive sprechender Langbezeichnung auf Deutsch. So können wir in der Programmoberfläche sprechende Namen verwenden und diese später einfach durch die passenden Kurzbezeichnungen austauschen.

Karten auf einen Stapel hinzufügen

Sind die Initialwerte geladen, ist der Nutzer in der Lage Karten durch die Wahl des Wertes und der Farbe zu selektieren. Damit er diese auf einem Stapel (Hand oder Deck) platzieren kann, müssen wir nun die Button-Click-Methode für den “Hinzufügen”-Button ausprogrammieren.

private void buttonAddCard_Click(object sender, EventArgs e)
{
    //Überprüfe, ob Kartenwert, -farbe und der Zielstapel
    //ausgewählt wurden
    if (listBoxCard.SelectedItems.Count != 1 ||
        listBoxColor.SelectedItems.Count != 1 ||
        listBoxStack.SelectedItems.Count != 1)
    {
        MessageBox.Show("Bitte Karte, Farbe und Stack wählen.");
    }
    else
    {
        //Überprüfe ob der Zielstapel schon voll ist
        if ((listBoxDeck.Items.Count == 3 && listBoxStack.SelectedItem.ToString() == "Deck") ||
            (listBoxHand.Items.Count == 2 && listBoxStack.SelectedItem.ToString() == "Hand"))
        {
            MessageBox.Show("Maximale Kartenanzahl erreicht. Anderen Stack wählen oder zurücksetzen.");
        }
        else
        {
            //Füge die Karte dem Zielstapel hinzu
            if (listBoxStack.SelectedItem.ToString() == "Deck")
            {
                listBoxDeck.Items.Add(listBoxCard.SelectedItem.ToString() + "-" + listBoxColor.SelectedItem.ToString());
            }
            else
            {
                listBoxHand.Items.Add(listBoxCard.SelectedItem.ToString() + "-" + listBoxColor.SelectedItem.ToString());
            }
        }
    }
}

Zuerst wird geprüft, ob alle drei nötigen Angaben (Wert, Farbe und Zielstapel) gesetzt sind. Wenn dem so ist, wird der Zielstapel per if-Abfrage ermittelt und die Karte auf den Zielstapel übertragen.

Hat sich der Nutzer verklickt oder will seine Auswahl zurücksetzen, kann er dies über den “Zurücksetzen”-Button tun. Der Code für dessen Click-Event sieht wie folgt aus.

private void buttonReset_Click(object sender, EventArgs e)
{
    //Leere die Zielstapel um eine neue Berechnung zu ermöglichen
    listBoxHand.Items.Clear();
    listBoxDeck.Items.Clear();
}

Nun haben wir also die Initialwerte geladen und können Karten auf einen Stapel ablegen sowie die Stapel leeren. Im nächsten Schritt geht es um die Berechnung der Gewinnwahrscheinlichkeit.

Berechnen der Gewinnwahrscheinlichkeit

Die Berechnung der Siegchancen findet nach dem Klick auf den “Chancen berechnen”-Button statt. Der Code dafür liegt komplett im Click-Event dieses Buttons.

Die Funktionsweise des Codes sollte anhand der Kommentare im nachfolgende Sourcecode klar werden. (Wenn dennoch etwas unklar ist, dann schreibt einfach einen Kommentar unter diesen Artikel.)

private void buttonCalculate_Click(object sender, EventArgs e)
{
    //Überprüfe, ob beide Zielstapel ausreichend belegt sind
    if (listBoxHand.Items.Count != 2 ||
        listBoxDeck.Items.Count != 3)
    {
        MessageBox.Show("Bitte geben Sie erst die Hand und das Deck an.");
    }
    else
    {
        //Fasse alle Hand-Karten als string in der Poker-Library-Syntax zusammen
        string handCards = "";
        foreach (var item in listBoxHand.Items)
        {
            handCards += cards[item.ToString().Split('-')[0]]
                        + colors[item.ToString().Split('-')[1]]
                        + " ";
        }
        handCards = handCards.Trim();

        //Fasse alle Deck-Karten als string in der Poker-Library-Syntax zusammen
        string deckCards = "";
        foreach (var item in listBoxDeck.Items)
        {
            deckCards += cards[item.ToString().Split('-')[0]]
                        + colors[item.ToString().Split('-')[1]]
                        + " ";
        }
        deckCards = deckCards.Trim();

        //Initialisiere Hilfsvariablen für die Poker-Library
        double[] self = new double[9];
        double[] opponent = new double[9];
        double selfWin = 0.0;

        //Berechne Poker-Hände und Wahrscheinlichkeiten
        Hand.HandPlayerOpponentOdds(handCards, deckCards, ref self, ref opponent);

        //Berechne Sieg-/Split-Wahrscheinlichkeit
        for (int i = 0; i < 9; i++)
        {
            selfWin += self[i] * 100.0;
        }

        //Gebe Sieg-/Split-Wahrscheinlichkeit aus
        labelChance.Text = string.Format("{0:##0.0}%", selfWin);
    }
}

Nun ist die Applikation fürs Erste auch schon vollständig. Wir haben nun ein Tool, in das wir sowohl die Karten auf dem Tisch als auch unsere beiden Hand-Karten eingeben und uns mit einem Klick die Gewinnwahrscheinlichkeit anzeigen lassen können.

Fazit und Download

Wer nun “Blut geleckt hat”, kann das Programm noch um weitere Funktionen erweitern. Denkbar wäre eine Berechnung für vier Karten auf dem Tisch oder das dynamische Austauschen von Karten auf einem der beiden Stapel, ohne das beide Stapel komplett zurückgesetzt werden müssen.

Den Download des Visual Studio Projekts findet ihr unter folgendem Link:

Download: PokerChancenRechner – Visual Studio Projekt

Über Anregungen als auch (konstruktive) Kritik freue ich mich wie immer.

6

Grundlagen: Sicheres Passwort Hashing mit Salts

Passwörter in Plaintext speichernWer Software entwickelt und dies im Web-Umfeld tut, der hat sicherlich schon das ein oder andere Login-System geschrieben oder zumindest Berührungspunkte in diesem Bereich gehabt. Neben der Logik eines sicheren Login- bzw. User-Systems an und für sich, ist das sichere Speichern von Passwörtern einer der wichtigsten Punkte während der Implementierung.

Selbst wenn der eigentliche Code des Logins zu 100 Prozent fehlerfrei und sicher ist (wovon man in der Praxis nie ausgehen sollte), so kann es durch Sicherheitslücken in der Serversoftware immer noch zu Einbrüchen bzw. Hacks kommen. Es gibt immer eine Variable, auf die man keinen Einfluss hat und so werden tagtäglich Webseiten gehackt, kompromittiert und komplette Datenbanken mit Usernamen und Passwörtern ausgelesen.

Um die Nutzer im Falle eines solchen Hacks bestmöglich zu schützen, sollten die Passwörter durch Salts (=Salz; eine Methodik aus der Kryptologie) geschützt werden.

In der Praxis sieht es jedoch leider so aus, dass vielen Entwicklern zwar bewusst ist, dass sie Passwörter salten sollten, die Meinungen und Ansätze über das “Wie”, also die Umsetzung, jedoch stark voneinander abweichen und teilweise so falsch sind, dass sich der gut gemeinte “Schutz” eher ins Negative auswirkt.

Deshalb möchte ich nachfolgend einmal mit dem Thema Passwort Hashing und Salting aufräumen und vom “Was ist eigentlich Passwort Hashing” bis hin zu “Best Practices für Passwort Hashing” die gesamte Themenpalette abarbeiten.

Was ist Passwort Hashing?

Passwort Hashing bedeutet das Anwenden einer Hashfunktion auf ein Passwort. Eine Hashfunktion (“hash'” ist englisch und steht für zerhacken) ist eine sogenannte Streuwertfunktion, die es ermöglichst große Eingabemengen auf (meist kleinere) Zielmengen zu projizieren. Oftmals haben die Zielmengen auch festgelegte Länge.

Für den Secure Hash Algorithm (kurz SHA) beträgt die Länge der Zielmenge z.B. immer 160 Bit, die wiederum oftmals als 40-stellige Hexadezimalzahl notiert wird.

Hat man also das Passwort “Geheim” und wendet darauf SHA1 an, so ergibt sich folgende Ausgabe:

sha1('Geheim') => 4d376b70dad934828fb73fb4aab5d0217ff88d15

Lautet das Passwort hingegen “SuperLangesUndSehrSehrGeheimesPasswortMitVielenZahlen6489451456498489494894894″ ergibt sich folgender Hash (unter Anwendung von SHA):

sha1('SuperLangesUndSehrSehrGeheimesPasswortMitVielenZahlen6489451456498489494894894') => 43911599b264c56f819d8e93c6d7e9614689eabe

Trotz der viel längeren Eingabe hat die Zielmenge immer noch dieselbe Länge von 40 Zeichen. Hieraus ergibt sich ein Problem von Hashfunktionen. Da die Eingabemenge größer sein kann als die Zielmenge, kann es vorkommen, dass zwei unterschiedliche Eingaben den gleichen Hashwert erzeugen. Dies nennt man eine Kollisionen.

Wenn statt dem Passwort der Hash in der Datenbank gespeichert werden soll, so sind Kollisionen ein nicht erwünschter Seiteneffekt. Zudem ist nicht jede Hashfunktion zur Anwendung auf Passwörter geeignet. Aus diesem Grund gibt es eine Unterart der Hashfunktionen, die sogenannten kryptologischen Hashfunktionen.

MD5 ist unsicherDieser Typus von Hashfunktionen zeichnet sich durch eine Reihe von Merkmalen aus. So ist eine kryptologische Hashfunktion per Definition kollisionsresistent, wobei eine Kollisionen theoretisch immer noch möglich ist, jedoch mit einem unüberwindbar hohen Aufwand verbunden ist, sodass praktisch keine Kollision gefunden werden kann. Weiter sollen schon kleinste Änderungen an der Eingabemenge eine scheinbar willkürliche Änderung der Zielmenge bewirken. Zudem soll es nicht möglich sein, aus einem Hash einer kryptografischen Hashfunktion die Eingabe zu rekonstruieren.

Wenn für kryptologische Hashfunktionen dennoch Kollisionen gefunden werden, dann ist entweder eine Schwachstelle im Algorithmus entdeckt worden oder der Aufwand zum Finden einer Kollision ist im Verhältnis zum technischen Fortschritt nicht mehr groß genug um eine Kollisionsresistenz zu sichern. In diesem Falle spricht man davon, dass der jeweilige Algorithmus “broken” (=zerbrochen, kaputt) ist. Von der Nutzung solcher Algorithmen sollte abgesehen werden. (Dies gilt z.B. auch für die MD5-Funktion.)

Zum Passwort-Hashing sollten also ausschließlich kryptologische Hashfunktionen verwendet werden.

Der Standardablauf zur Verwaltung von Nutzerdaten und Passwörten unter Verwendung von Hashfunktionen sieht wie folgt aus:

  1. Der Nutzer registriert sich mit Nutzernamen und Passwort.
  2. Das Passwort wird vorm Speichern in der Datenbank gehasht und nur der Hash wird in der Datenbank abgelegt.
  3. Will sich der Nutzer nun einloggen, gibt er Nutzername und Passwort an. Sein Passwort wird wieder gehasht und mit dem Hash verglichen, der in der Datenbank für seinen Nutzernamen abgelegt ist.
  4. Stimmen die Hashes überein, wird der Nutzer eingeloggt, anderenfalls erhält er eine Fehlermeldung.

Die Fehlermeldung sollte hierbei immer nur sagen, dass die Zugangsdaten falsch sind. Wird angegeben, ob Passwort oder Nutzername falsch sind, kann der Angreifer daraus schon schließen, dass eines der beiden auf jeden Fall richtig ist. Deshalb sollten an dieser Stelle immer nur generische Fehlermeldungen ausgegeben werden.

Durch die obigen vier Schritte, sprich das Hashing der Passwörter, kann sichergestellt werden, dass beim Verlust der Datenbank bzw. einem Einbruch in die Datenbank nur die Hashes publik werden. Mittels der Hashes kann sich der Angreifer jedoch nicht einloggen, da diese in Schritt 3 ja erneut gehasht und somit nicht mehr mit dem Hash des eigentlichen Passworts übereinstimmen würden.

Warum sind Hashes nicht per se sicher?

Nachdem letzten Absatz könnte man meinen, (kryptografische) Hashes seien per se sicher. Man könnte fälschlicherweise annehmen, dass, unter Anwendung der vier Schritte aus vorherigem Absatz, die Passwörter ausreichend gesichert seien und man alles getan hätte, was zu ihrem Schutz nötig ist. Leider ist dem nicht so!

Was ist Brute Force?Zwar haben wir richtigerweise festgestellt, dass sich ein Hacker nicht (ohne Weiteres) mittels der Hashes einloggen kann, jedoch gibt es dennoch Möglichkeiten vom Hash wieder auf das Passwort zu schließen. Und da Nutzer (leider) meist dieselben Anmeldedaten für mehrere Portale/Webseiten nutzen, liegt die Wiederherstellung des Passworts im Interesse des Hackers. Deshalb betrachten wir nun, wie Hashes “entschlüsselt” (oder auch gecracked) werden können, um uns dann in einem späteren Absatz dann damit zu beschäftigen, wie wir eben dieses Risiko weiter eindämmen können.

Prinzipiell kann man zwischen zwei Methoden Hashes zu cracken unterscheiden:

  1. Brute Forcing; Beim Brute Forcing (brute force = rohe Gewalt) wird versucht, durch Ausprobieren aller möglichen Kombinationen, das gesuchte Ergebnis zu erhalten. Hat man also z.B. den Hash “e22a63fb76874c99488435f26b117e37″ so bildet man systematisch für alle Kombinationen eines Alphabets (z.B. A-Za-z0-9) den entsprechenden Hashwert und vergleicht diesen mit dem vorhandenen Hash. Sind die Hashes gleich, schaut man, welches die letzte Eingabekombination war und kennt somit das Passwort. Da das Durchprobieren aller Möglichkeiten einen hohen Rechen- und Zeitaufwand bedeutet, kann versucht werden zuerst mittels sogenannten “Dictionaries” zu arbeiten. Ein Dictionary (= Wörterbuch) ist eine Liste mit gängigen Passwörtern. Zu dieser Liste werden dann die Hashes erzeugt und mit dem gesuchten Hash verglichen. Je größer die gehackte Datenbank ist, umso wahrscheinlicher ist es, dass ein Nutzer eines der gängigen Passwörter aus dem Dictionary genutzt hat.
  2. Lookup Tables; Um das Performance-Problem von Brute Force Attacken zu umgehen werden Lookup Tables genutzt. Eine Lookup Table ist eine spezielle Datenstruktur, die vorberechnete Passwort-Hash-Pärchen enthält. Das Besondere an Lookup Tables ist, dass sie selbst bei Datenbeständen von mehreren Millionen Pärchen immer noch mehrere hundert Abfragen pro Sekunde verarbeiten können. Lookup Tables sind also schneller als reines Brute Force, dafür sind sie durch die vorberechneten Werte ebenso wie Dictionary-Attacken auf eine vorbestimmte Eingabemenge (an Passwörtern) begrenzt. Eine Sonderform sind die sogenannten “Rainbow Tables”. Sie stellen eine Mischform aus Lookup Table und Brute Force Attacke dar. So ist ein Teil der Hashes vorberechnet, um zu bestimmen, ob sich der Hash eines Passwortes in einer Submenge befindet. Ist dies der Fall, wird die Submenge per Brute Force gehasht um das passende Passwort zu finden. Auf diese Weise können auf geringerem Platz mehr Hashes gespeichert und somit die Trefferrate erhöht werden.

Kommen wir nun dazu, warum wir Passwörter vor dem Hashen zusätzlichen Salten (= mit einem Salt versehen) sollten.

Nutzen von Salts beim Passwort Hashing

Starke Passwort SaltsMittels eines Salts lässt sich das im vorherigen Abschnitt beschriebene Lookup-Table-Verfahren außer Kraft setzen. Dies funktioniert, weil Lookup Tables davon ausgehen, dass das gleiche Passwort immer den gleichen Hash ergibt. Nutzen zwei User also das gleiche Passwort haben Sie normalerweise (wenn nur gehasht wird) den gleichen Hash.

Versieht man die Passwörter der einzelnen Nutzer nun aber mit einem zufälligen Salt, so ergeben die beiden Passwörter unterschiedliche Hashes, sodass eine Lookup Table nicht funktionieren kann, da vor dem Hack die Salts nicht bekannt sind und somit auch keine Lookup Table vorberechnet werden kann.

Brute Force Attacken sind hiervor jedoch immun. Bei ausreichend langen Passwörtern ist der Aufwand des Brute Forcing jedoch so hoch, dass das Entschlüsseln aller erbeuteten Passwörter nicht in annehmbarer Zeit erfolgen kann. Zudem kann durch Key Stretching das Brute Forcen weiter erschwert werden. (Mehr zu Key Stretching im nächsten Abschnitt.)

Best Practice: Passwort Hashing mit Salt

Bei der Verwendung von Salts sollten folgende Dinge beachtet werden, um eine maximale Effektivität zu erreichen.

  • Der verwendete Salt sollte einzigartig pro Nutzer und Passwort sein. Das heißt, dass nicht nur bei der Registrierung eines Nutzers, sondern auch bei dem Wechsel seines Passworts ein neuer Salt generiert werden sollte.
  • Der Salt sollte aus einer zufälligen Zeichenfolge bestehen. Zur Generierung des Salts sollte ein kryptografisch sicherer Zufallszahlengenerator (bzw. englisch cryptographically secure pseudo-random number generator; kurz: CSPRNG) verwendet werden. Dies ist wichtig, da nicht jeder Zufallsgenerator wirklich zufällig ist. So lassen sich bei vielen Standard-Generatoren Muster erkennen, anhand derer, bei großen Mengen an Zufallszahlen (in diesem Falle Salts), auf andere mit dem Generator erstellte Zahlen (Salts) geschlossen werden kann. In nachfolgender Liste (zum Aufklappen den Titel anklicken), finden sich gängige CSPRNG-Implementierungen für verschiedene Programmiersprachen.
  • Liste mit CSPRNG-Algorithmen & Bibliotheken
    .NET (C#, VB, F#): System.Security.Cryptography.RNGCryptoServiceProvider
    C/C++ (Windows API): CryptGenRandom, ISAAC
    GNU/Linux/Unix-basierte Sprachen: /dev/random oder /dev/urandom als Stream-Source nehmen
    Java: java.security.SecureRandom, Java TRNG Client
    JavaScript: RandomSource.getRandomValues(), CryptoJS
    Lua: LuaCrypto, ISAAC
    NodeJS: crypto.randomBytes()
    Perl: Math::Random::Secure
    PHP: mcryptcreateiv, opensslrandompseudo_bytes, php-csprng
    Python: os.urandom, pyaes / Advanced Encryption Suite
    Ruby: SecureRandom, drbg-rb
    Visual Basic: ISAAC
  • Weiter sollte der Salt mindestens so lang sein wie das Ergebnis der verwendeten Hash-Funktion. Wenn der Salt zu kurz ist, ergeben sich zu wenig Variationen, sodass der Angreifer trotz Verwendung eines Salts seine Lookup-Tables für alle Salt-Variationen in annehmbarer Zeit vorberechnen könnte.
  • Das Hashing an sich sollte durch Erhöhung des Rechenaufwands künstlich verlangsamt werden. Mittels des Salts kann sichergestellt werden, dass Lookup Tables nutzlos werden. Gegen reine Brute Force Attacken helfen Salts jedoch nicht. Um auch Brute Forcing möglichst uneffektiv zu machen, sollte ein Hashing Algorithmus genutzt werden, der Key Stretching unterstützt. Key Stretching Algorithmen sind besonders rechenintensiv, sodass die Hashrate um einen frei definierten Faktor verlangsamt werden kann. (In der Regel erfolgt dies über die Angabe der Iterationen beim Aufruf der Hashing-Funktion.) Schafft eine Cracking Software bei einem normalen Verfahren z.B. 300.000 Hashs/Sekunde kann durch entsprechendes Key Stretching die Rate z.B. auf 5 Hashs/Sekunde verringert werden. Auf diese Art und Weise wird das Brute Forcen ineffektiv. Gängige Librarys zum Key Stretching sind zum Beispiel crypt(5), PBKDF2 oder bcrypt. Der Parameter beim Key Stretching sollte so gewählt werden, dass das Hashing möglichst langsam ist, schwache Geräte bzw. Webserver darunter aber nicht leiden. Wird mit zu vielen Iterationen gearbeitet, kann bei hohem Nutzeraufkommen zum Beispiel die Performance des Webservers leiden, auf dem die Hashing-Operationen ausgeführt werden.

Fassen wir also noch einmal kurz und knapp zusammen:

  1. Der Salt sollte einzigartig pro Nutzer und Passwort sein
  2. Der Salt sollte einem kryptografisch sicheren Zufallsgenerator entspringen
  3. Der Salt sollte mindestens solang wie der Hash sein
  4. Es sollte ein Key Stretching Verfahren angewendet werden

Unter Beachtung der obigen Regeln kann nicht mehr viel schief gehen. Dennoch schauen wir im nächsten Abschnitt noch einmal, was man beim Hashen und Salten definitiv nicht tun sollte.

Wie man Passwörter nicht hasht und saltet

Achtung – nachfolgende Dinge sollten beim Hashen und Salten von Passwörtern ausdrücklich nicht gemacht werden!

  • Salts mehrfach verwenden; Wenn der Salt nur einmalig generiert wird und/oder im Quellcode hart codiert ist, dann verliert er effektiv an Nutzen. Durch einen hart codierten Salt würde das gleiche Passwort zweier Nutzer ebenfalls den gleichen Hash ergeben. Somit müsste die Lookup Table nur einmalig für den definierten Salt neu berechnet werden und der Schutz durch den Salt wäre ausgehebelt. Deswegen sollte ein Salt immer einmalig pro User und Passwort generiert werden.
  • Nutzernamen als Salt verwenden; Das Verwenden des Nutzernamens als Salt ist eine ebenso schlechte Idee. Oftmals nutzen User denselben Nutzernamen für verschiedene Dienste. Würden nun alle Dienste den Nutzernamen als Salt verwenden, könnte ein gecracktes Passwort für sämtliche betroffene Dienste verwendet werden. Deshalb sollte ein kryptografisch sicherer, zufälliger Salt generiert werden.
  • Einen zu kurzen Salt verwenden; Ist der Salt zu kurz gewählt, können Angreifer Lookup Tables für alle möglichen Salt-Variationen vorberechnen. Besteht der Salt zum Beispiel nur aus 2 ASCII zeichen, ergeben sich gerade einmal 95*95=9025 mögliche Salts. Selbst wenn man von einer großen Passwortliste von 20MB für eine Dictionary-Attacke ausgeht, ergibt dies (bei Berechnung der Liste mit allen Salts) gerade einmal eine Datenmenge von 176GB, deren Verarbeitung und Speicherung bei heutigen Maßstäben keine Problem mehr darstellt.
  • Ausschließlich clientseitig hashen; Zwar scheint es auf den ersten Blick Sinn zu machen, das Passwort clientseitig, also zum Beispiel im Browser mittels Javascript, zu hashen, um das Passwort nicht im “Klartext” zum Server übertragen zu müssen, jedoch birgt dies bei genauerer Betrachtung mehrere Risiken. Zum einen kann nicht immer gewährleistet werden, dass der Browser des Nutzers JavaScript unterstützt und zum anderen hieße dies, dass nur noch der berechnete Hash an den Server geschickt und dort gegen den Hash in der Datenbank verglichen würde. Dies hieße auch, dass ein Angreifer beim Erbeuten des Hashs den Hash nicht mehr entschlüsseln müsste, sondern diesen direkt zum einloggen verwenden könnte, was eine große Schwachstelle darstellt. Das clientseitige Hashen und Salten kann also höchstens eine Zusatzleistung zum serverseitigen Hashen darstellen. Zudem sollte bedacht werden, dass clientseitiges Hashen kein Ersatz für eine sichere Verbindung (z.B. HTTPS TLS/SSL) zwischen Client und Server ist. Wer nur clientseitig hasht, aber keine sichere Transportstrecke nutzt, läuft Gefahr, dass der Hash mittels Man-in-the-Middle-Attacke abgegriffen und daraufhin missbraucht wird.
  • Unsichere oder selbst geschriebene Hashing-Algorithmen verwenden; Auf einigen Internetseiten/-foren wird vorgeschlagen, zur “Verbesserung der Sicherheit” mehrere Hash-Funktionen zu kombinieren oder ein und dieselbe Funktion verschachtelt aufzurufen. Solche Vorschläge können zum Beispiel wie folgt aussehen: sha1(sha1(passwort)) oder md5(sha1(passwort)). Was hierbei oft vergessen wird, ist die Abschätzung von Nutzen und Kosten. Auf der Nutzen-Seite steht im Idealfall der minimal höhere Rechenaufwand. Dieser Ansatz ist jedoch mit einem iterativen Algorithmus (Stichwort: Key Stretching) wesentlich effektiver umzusetzen. Auf der Kosten-Seite steht das Risiko die Sicherheit zu schwächen oder Inkompatibilitätsprobleme hervorzurufen, sodass von solchen Methoden abgesehen werden sollte. Ebenfalls ist es keine gute Idee, seinen eigenen Hash-Algorithmus entwerfen zu wollen. Oftmals passieren hierbei Fehler, die wiederum die komplette Sicherheit infrage stellen. Etablierte Algorithmen hingegen sind zigfach getestet und wesentlich stabiler, sodass auf einen bereits etablierten Algorithmus zurückgegriffen werden sollte.

Weitere Sicherheitsmaßnahmen

Unter Anwendung der bisher in diesem Artikel gelernten Methoden – Hashing, Salting und Key Stretching – lässt sich bereits ein gut gesichertes System aufsetzen. Dennoch gibt Hacker sind überalles noch weitere Möglichkeiten, den Schutz der Passwörter zu erhöhen. Eine dieser Möglichkeiten ist das Verschlüsseln der Hashes.

Verschlüsselung von Hashes

Durch die Verschlüsselung von Hashes kann sichergestellt werden, dass Brute Force Attacken nutzlos werden. Bei einem Hack erhält der Hacker die Hashes in verschlüsselter Form. Erzeugt er nun Hashes, um diese mit den erbeuteten (vermeintlichen) Hashes zu vergleichen, wird kein Match finden, da er die von ihm erzeugten Hashes noch unter Anwendung des gleichen Schlüssels wie die Applikation verschlüsseln müsste.

Zur Verschlüsselung von Hashes eignen sich Lösungen wie AES oder HMAC. Damit dieses System funktioniert, sollte der Schlüssel (engl. secret) jedoch auf einem dedizierten System liegen bzw. die komplette Verschlüsselung auf eben diesem passieren. Liegt der Schlüssel/die Verschlüsselungslogik auf dem gleichen Server wie die Datenbank, ist es wahrscheinlich, dass der Angreifer auch hierauf Zugriff hat, sodass die Verschlüsselung ausgehebelt werden kann. Sollte es nicht anders gehen oder keine geeignete Hardware vorhanden sein, ist es jedoch immer noch besser die Verschlüsselungslogik auf dem gleichen Webserver wie die Datenbank zu implementieren als gar nicht zu verschlüsseln. Nichtsdestotrotz sollte abgewägt werden, ob die Sicherheitsansprüche es nicht gebieten, in solch einem Fall zusätzliche, dedizierte Hardware anzuschaffen.

Weiter sollte der Schlüssel für die Hash-Verschlüsselung während der Installation einer Instanz dynamisch erzeugt werden. Ein, in der Software fest hinterlegter, Schlüssel steigert das Risiko eines erfolgreichen Angriffs. Hat der Angreifer einmal Zugriff zum Code, könnte er bei einem fest hinterlegten Schlüssel alle Instanzen dieser Software attackieren. Hingegen er bei einem dynamisch generierten Schlüssel Zugriff auf jedes System haben müsste, dass er angreifen will.

Zeit-konstanter Hash-Vergleich

Bei der Implementierung des Hash-Vergleichs, also bei der Validierung des Passworts, sollte darauf geachtet werden, dass der Vergleich immer gleich lang dauert. Das meint, dass sowohl die Validierung eines gültigen Passwort Hashes als auch die Validierung eines ungültigen Hashes die gleiche Zeit beanspruchen sollten.

Die am häufigsten verwendete Methode zum Vergleich zweier Hashes dürfte wohl wie folgt (oder ähnlich) aussehen:

string hash1 = "e22a63fb76874c99488435f26b117e37";
string hash2 = "0a4ff18a7d23f8b3ded5eaf93104ac88";

if (hash1 == hash2)
{
   return true;
}

Der “==”-Vergleichsoperator bewirkt jedoch, dass der Vergleich bei der ersten unterschiedlichen Stelle beendet und mit einem “false” quittiert wird. In obigem Beispiel wäre das direkt nach der ersten Stelle. Bei identischen Hashes hingegen würde der “==”-Operator alle Stellen der Hashes durchlaufen. Hieraus ergibt sich ein Zeitunterschied, den sich Angreifer zunutze machen können.

Attackiert der Angreifer einen Webservice und probiert alle Hashes für alle 256 Byte-Werte an der ersten Position des Hashes durch, kann er durch den Zeitunterschied feststellen, welches das richtige Byte an der ersten Position ist. Danach nimmt er sich die zweite Position vor und kann sich somit nach und nach an den richtigen Hash bzw. die richtige Eingabe herantasten.

Dieses Szenario mag auf den ersten Blick unwahrscheinlich klingen, ist jedoch technisch und praktisch umsetzbar, wie ein Paper der Universtität Stanford belegt.

Um diesen Angriffsvektor zu eliminieren, ist es nötig, eine Zeit-konstante Vergleichsroutine zu nutzen. Diese könnte wiederum wie folgt aussehen:

string hash1 = "e22a63fb76874c99488435f26b117e37";
string hash2 = "0a4ff18a7d23f8b3ded5eaf93104ac88";
bool valid = true;

if (hash1.Length == hash2.Length)
{
    for (int i = 0; i < hash1.Length; i++)
    {
        if (hash1[i] != hash2[i])
            valid = false;
    }
}
else
{
    valid = false;
}
return valid;

In obigem Code wird in jedem Fall jede Stelle durchlaufen, unabhängig davon, ob die beiden Hashes gleich oder ungleich sind. Somit kann der Angreifer keine Rückschlüsse aus der benötigten Zeit auf die Richtigkeit seines Hashes erhalten.

Fazit

Auch wenn der Artikel nun etwas ausführlicher geworden ist, lässt sich festhalten, dass das Passwort Hashing und Salting kein “Hexenwerk” ist. Wenn man sich auf die wesentlichen Punkte begrenzt, ist es ohne großen Aufwand möglich, ein sicheres System zu implementieren. Und gerade weil es eben kein unüberschaubarer Aufwand ist, sollte man bei der Implementierung eines Login-/Passwort-basierten Systems auch immer die oben genannten Techniken wie Hashing, Salting und Key-Stretching einsetzen.

Über Feedback und Erfahrungen würde ich mich (wie immer) freuen. Wie implementiert Ihr euer Hash-System? Habt ihr Erfahrung mit Key-Stretching, Salting und den oben genannten Vorgehensweisen? Ist euer oder ein von euch betreutes System bereits einmal von einem Hack betroffen gewesen?

Seite 1 von 58