2020 Projekt-Update

Scallion war ein Hobbyprojekt, um OpenCL und RSA zu lernen. Wir warten Scallion derzeit nicht. Es hat auf zwei wichtige Arten gelitten:

1. Tor ist zu v3 Onion-Adressen übergegangen, die Scallion nicht unterstützt. Alte v2-Adressen werden im Oktober 2021 nicht mehr funktionieren. Der neue Standard verwendet andere kryptografische Primitive und ist insgesamt komplizierter. Der Trick, den wir verwenden, um Chargen von RSA-Schlüsseln auf der GPU zu erzeugen, funktioniert nicht auf dieselbe Weise für die erforderlichen neuen ECDSA-Schlüssel. Es ist möglich, ähnliche (aber nicht kompatible) ECDSA-Schlüssel auf der GPU für die Bitcoin-Adressgenerierung zu erzeugen. Siehe vanitygen-plus oder das ältere oclvanitygen. Eine Liste (CPU-basierter) Vanity-Gen-Tools, die für Tor v3 Hidden Services funktionieren, finden Sie in diesem Blogbeitrag.
2. Die Version von OpenSSL, auf die wir angewiesen sind, ist veraltet und in den meisten modernen Betriebssystemen nicht verfügbar. Es ist nicht einfach, ein Upgrade durchzuführen, da wir einige Low-Level-Mathefunktionen in OpenSSL verwenden, die in den C#-Bindungen für die neueren Versionen nicht verfügbar sind. Ich persönlich betreibe Scallion mit dem Nvidia-Dockerfile, das auf Ubuntu 16.04 Xenial basiert, das noch die veraltete OpenSSL enthält. Dies ist jedoch nur eine Option für Nvidia-GPU-Benutzer. Sie könnten auch versuchen, die veraltete OpenSSL-Bibliothek zu erstellen und direkt dagegen zu linken, oder eine ältere Version Ihres Betriebssystems von einem Live-USB oder einer VM (mit PCI-e-Durchleitung) ausführen.

Mit genügend Aufmerksamkeit und Mühe wäre es möglich, beide oben genannten Herausforderungen zu bewältigen. Wir könnten die GPU-ECDSA-Schlüsselgenerierung implementieren, um Tor v3 zu unterstützen. Wir könnten OpenSSL aktualisieren und die Mathefunktionen durch eine andere Bibliothek ersetzen oder einen eigenen verwalteten Code-Wrapper für die OpenSSL-Bibliothek erstellen. Es wäre jedoch wahrscheinlich besser, die Unterstützung für v3-Onion-Adressen zu einem gepflegten Projekt wie vanitygen-plus hinzuzufügen.

Scallion

Mit Scallion können Sie Vanity-GPG-Schlüssel und .onion-Adressen (für Tor's Hidden Services) mit OpenCL erstellen.

Scallion läuft unter Mono (getestet in Arch Linux) und .NET 3.5+ (getestet auf Windows 7 und Server 2008).

Scallion befindet sich derzeit in der Beta-Phase und wird aktiv entwickelt. Dennoch sind wir der Meinung, dass es einsatzbereit ist. Verbesserungen werden hauptsächlich in Bezug auf Leistung, Benutzeroberfläche und Installationsfreundlichkeit erwartet, nicht im Gesamtalgorithmus zur Schlüsselgenerierung.

Scallion ist unter der MIT-Lizenz verfügbar. Wenn Sie Code aus diesem Projekt in Ihren eigenen Projekten verwenden, würden wir uns über eine Nachricht an [email protected] freuen.

FAQ

Hier sind einige häufig gestellte Fragen und ihre Antworten:

• Warum GPG-Schlüssel generieren?

  Scallion wurde verwendet, um Kollisionen für jede 32-Bit-Schlüssel-ID im starken Set des Web of Trust zu finden, was zeigt, wie unsicher 32-Bit-Schlüssel-IDs sind. Es gab/gibt einen Vortrag auf DEFCON (Video) und weitere Informationen finden Sie unter https://evil32.com/.

• Welche Zeichen sind gültig?

  Tor .onion-Adressen verwenden Base32, bestehend aus allen Buchstaben und den Ziffern 2 bis einschließlich 7. Sie sind Groß-/Kleinschreibung-unabhängig.

  GPG-Fingerabdrücke verwenden Hexadezimal, bestehend aus den Ziffern 0-9 und den Buchstaben A-F.

• Kann man Bitcoin-ASICs (z.B. Jalapeno, KnC) verwenden, um diesen Prozess zu beschleunigen?

  Leider nein. Obwohl der von Scallion verwendete Prozess konzeptionell ähnlich ist (einen Nonce erhöhen und den Hash prüfen), unterscheiden sich die Details (SHA-1 vs. doppeltes SHA-256 für Bitcoin). Darüber hinaus sind Bitcoin-ASICs so schnell, weil sie äußerst auf Bitcoin-Mining-Anwendungen zugeschnitten sind. Hier ist zum Beispiel das Datenblatt für den CoinCraft A-1, ein ASIC, der nie auf den Markt kam, aber wahrscheinlich repräsentativ für den allgemeinen Ansatz ist. Der Mikrocontroller sendet Arbeit in Form der letzten 128 Bits eines Bitcoin-Blocks, des Hash-Midstate der vorherigen Bits, einer Zielschwierigkeit und des maximalen Nonce zum Ausprobieren. Der ASIC wählt die Position zum Einfügen des Nonce und welche Blöcke den Hash erfüllen. Scallion muss den Nonce an einer anderen Position einfügen und sucht nach einem Mustervergleich, nicht nur nach 'niedriger als XXXX'.

• Wie kann man mehrere Geräte verwenden?

  Führen Sie mehrere Scallion-Instanzen aus. 😄 Scallion-Suchen sind probabilistisch, sodass Sie mit dem zweiten Gerät keine Arbeit wiederholen. Echte Multi-Device-Unterstützung wäre nicht allzu schwierig, würde aber auch nicht viel bringen. Ich habe mehrere Scallion-Instanzen in tmux oder screen mit großem Erfolg ausgeführt. Sie müssen lediglich alle Jobs manuell abbrechen, wenn eines ein Muster findet (oder ein Shell-Skript schreiben, das die Ausgabedatei überwacht und alle beendet, wenn Ergebnisse angezeigt werden).

Abhängigkeiten

• OpenCL und entsprechende Treiber installiert und konfiguriert. Schlagen Sie in der Dokumentation Ihrer Distribution nach.
• OpenSSL. Für Windows sind die vorgebauten x86-DLLs enthalten.
• Nur unter Windows, VC++ Redistributable 2008

Binär-Download

Möchten Sie nur die neueste Binärversion? Holen Sie sie sich hier.

Unter Linux bauen

Voraussetzungen

• Holen Sie sich das aktuellste Mono für Ihre Linux-Distribution:

  http://www.mono-project.com/download/

• Allgemeine Abhängigkeiten installieren:

  root@kitploit:~

  sudo apt-get update
  sudo apt-get install libssl-dev mono-devel
  

• AMD/OpenSource-Build sudo apt-get install ocl-icd-opencl-dev

• Nvidia-Build sudo apt-get install nvidia-opencl-dev nvidia-opencl-icd

• Schließlich msbuild scallion.sln

Docker Linux (nur Nvidia-GPUs)

1. Besitzen Sie die nvidia-docker-Container-Laufzeit

2. Bauen Sie den Container:

   root@kitploit:~

   docker build -t scallion -f Dockerfile.nvidia .
   

3. Ausführen:

   root@kitploit:~

   docker run --runtime=nvidia -ti --rm scallion -l
   

   Screenshot der erwarteten Ausgabe

Unter Windows bauen

1. Öffnen Sie 'scallion.sln' in VS Express für Desktop 2012
2. Bauen Sie die Projektmappe, ich habe alles im Debug-Modus gemacht.

Verwendung

Ein Neustart von Scallion während einer Suche führt nicht zu einem Verlust des 'Fortschritts'. Es handelt sich um eine probabilistische Suche und Scallion macht keinen 'Fortschritt'

Geräte auflisten

$ mono scallion/bin/Debug/scallion.exe -l

Einen Hash generieren

$ mono scallion/bin/Debug/scallion.exe -d 0 prefix
Cooking up some delicious scallions...
Using kernel optimized from file kernel.cl (Optimized4)
Using work group size 128
Compiling kernel... done.
Testing SHA1 hash...
CPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
GPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
Looks good!
LoopIteration:40  HashCount:671.09MH  Speed:9.5MH/s  Runtime:00:01:10  Predicted:00:00:56  Found new key! Found 1 unique keys.
<XmlMatchOutput>
  <GeneratedDate>2014-08-05T07:14:50.329955Z</GeneratedDate>
  <Hash>prefix64kxpwmzdz.onion</Hash>
  <PrivateKey>-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCmYmTnwGOCpsPOqvs5mZQbIM1TTqOHK1r6zGvpk61ZaT7z2BCE
FPvdTdkZ4tQ3/95ufjhPx7EVDjeJ/JUbT0QAW/YflzUfFJuBli0J2eUJzhhiHpC/
1d3rb6Uhnwvv3xSnfG8m7LeI/Ao3FLtyZFgGZPwsw3BZYyJn3sD1mJIJrQIEB/ZP
ZwKBgCTUQTR4zcz65zSOfo95l3YetVhfmApYcQQd8HTxgTqEsjr00XzW799ioIWt
vaKMCtJlkWLz4N1EqflOH3WnXsEkNA5AVFe1FTirijuaH7e46fuaPJWhaSq1qERT
eQT1jY2jytnsJT0VR7e2F83FKINjLeccnkkiVknsjrOPrzkXAkEA0Ky+vQdEj64e
iP4Rxc1NreB7oKor40+w7XSA0hyLA3JQjaHcseg/bqYxPZ5J4JkCNmjavGdM1v6E
OsVVaMWQ7QJBAMweWSWtLp6rVOvTcjZg+l5+D2NH+KbhHbNLBcSDIvHNmD9RzGM1
Xvt+rR0FA0wUDelcdJt0R29v2t19k2IBA8ECQFMDRoOQ+GBSoDUs7PUWdcXtM7Nt
QW350QEJ1hBJkG2SqyNJuepH4PIktjfytgcwQi9w7iFafyxcAAEYgj4HZw8CQAUI
3xXEA2yZf9/wYax6/Gm67cpKc3sgKVczFxsHhzEml6hi5u0FG7aNs7jQTRMW0aVF
P8Ecx3l7iZ6TeakqGhcCQGdhCaEb7bybAmwQ520omqfHWSte2Wyh+sWZXNy49EBg
d1mBig/w54sOBCUHjfkO9gyiANP/uBbR6k/bnmF4dMc=
-----END RSA PRIVATE KEY-----
</PrivateKey>
  <PublicModulusBytes>pmJk58BjgqbDzqr7OZmUGyDNU06jhyta+sxr6ZOtWWk+89gQhBT73U3ZGeLUN//ebn44T8exFQ43ifyVG09EAFv2H5c1HxSbgZYtCdnlCc4YYh6Qv9Xd62+lIZ8L798Up3xvJuy3iPwKNxS7cmRYBmT8LMNwWWMiZ97A9ZiSCa0=</PublicModulusBytes>
  <PublicExponentBytes>B/ZPZw==</PublicExponentBytes>
</XmlMatchOutput>
init: 491ms / 1 (491ms, 2.04/s)
generate key: 1193ms / 6 (198.83ms, 5.03/s)
cpu precompute: 10ms / 6 (1.67ms, 600/s)
total without init: 70640ms / 1 (70640ms, 0.01/s)
set buffers: 0ms / 40 (0ms, 0/s)
write buffers: 3ms / 40 (0.08ms, 13333.33/s)
read results: 67442ms / 40 (1686.05ms, 0.59/s)
check results: 185ms / 40 (4.63ms, 216.22/s)

9.50 million hashes per second

Stopping the GPU and shutting down...

Multimuster-Hashing

Scallion unterstützt das Finden eines oder mehrerer von mehreren Mustern durch eine primitive Regex-Syntax. Es werden nur Zeichenklassen (z.B. [abcd]) unterstützt. Das Zeichen . stellt ein beliebiges Zeichen dar. Onion-Adressen sind immer 16 Zeichen lang und GPG-Fingerabdrücke immer 40 Zeichen. Sie können ein Suffix finden, indem Sie $ am Ende des Musters setzen (z.B. DEAD$). Schließlich kann die Pipe-Syntax (z.B. pattern1|pattern2) verwendet werden, um mehrere Muster zu finden. Die Suche nach mehreren Mustern (im Rahmen des Zumutbaren) wird NICHT zu einer signifikanten Verringerung der Geschwindigkeit führen. Viele reguläre Ausdrücke erzeugen ein einzelnes Muster auf der GPU und führen zu keiner Geschwindigkeitsreduzierung.

Einige Anwendungsfälle mit Beispielen:

• Erzeugen eines Präfixes gefolgt von einer Zahl für bessere Lesbarkeit:

  root@kitploit:~

    mono scallion.exe prefix[234567]
  

• Suche nach mehreren Mustern gleichzeitig (Anm. -c bewirkt, dass Scallion auch nach einem Treffer weiter generiert)

  root@kitploit:~

    mono scallion.exe -c prefix scallion hashes
    mono scallion.exe -c "prefix|scallion|hashes"
  

• Suche nach dem Suffix "badbeef"

  root@kitploit:~

    mono scallion.exe .........badbeef
    mono scallion.exe --gpg badbeef$ # Generate GPG key
  

• Kompliziertes selbsterklärendes Beispiel:

  root@kitploit:~

    mono scallion.exe "suffixa$|suffixb$|prefixa|prefixb|a.suffix$|a.test.$"
  

Wie funktioniert Scallion?

Auf hoher Ebene funktioniert Scallion wie folgt:

1. RSA-Schlüssel mit OpenSSL auf der CPU generieren
2. Schlüssel an die GPU senden
3. Öffentlichen Exponenten des Schlüssels erhöhen
4. Schlüssel hashen
5. Wenn der gehashte Schlüssel keine partielle Kollision ist, gehe zu Schritt 3
6. Wenn der Schlüssel nicht die von PKCS #1 v2.1 empfohlenen Plausibilitätsprüfungen besteht (auf der CPU geprüft), gehe zu Schritt 3
7. Funkelnagelneuer Schlüssel mit partieller Kollision!

Der grundlegende Algorithmus ist oben beschrieben. Die Geschwindigkeit/Leistung ist das Ergebnis massiver Parallelisierung, sowohl auf der GPU als auch auf der CPU.

Geschwindigkeit / Leistung

Es ist wichtig zu verstehen, dass Scallion eine probabilistische Suche durchführt. Tatsächliche Zeiten können erheblich von den vorhergesagten abweichen.

Die anfängliche RSA-Schlüsselgenerierung erfolgt auf der CPU. Ein Ivybridge i7 kann mit einem einzelnen Kern 51 Schlüssel pro Sekunde generieren. Jeder Schlüssel kann 1 Gigahash an Exponenten zum Minen bereitstellen, und eine durchschnittliche CPU kann mit mehreren GPUs mithalten, wie es derzeit implementiert ist.

SHA1-Hashing erfolgt auf der GPU. Die Hashraten für mehrere von uns getestete GPUs sind unten aufgeführt (groupiert nach Hersteller und sortiert nach Leistung):

MH/s = Millionen Hashes pro Sekunde

Es ist erwähnenswert, dass Intel OpenCL-Treiber für seine Prozessoren veröffentlicht hat und kurze Kollisionen auf der CPU gefunden werden können.

Um die Anzahl der benötigten Sekunden für eine bestimmte partielle Kollision (im Durchschnitt) zu berechnen, verwenden Sie die Formel:

Zum Beispiel auf meiner nVidia Quadro K2000M sehe ich etwa 90 MH/s. Mit dieser Geschwindigkeit kann ich ein acht Zeichen langes .onion-Präfix in etwa 1h 41m generieren, 2^(5*8-1)/90 Millionen = 101 Minuten.

Arbeitsgruppengröße

Scallion verwendet standardmäßig die von Ihren Geräten gemeldete bevorzugte Arbeitsgruppengröße. Dies ist eine vernünftige Standardeinstellung, aber Experimente mit der Arbeitsgruppe können die Leistung steigern.

Sicherheit

Die von Scallion generierten Schlüssel sind denen von Shallot generierten sehr ähnlich. Sie haben ungewöhnlich große öffentliche Exponenten, werden aber über die RSA_check_key-Funktion von OpenSSL der vollständigen Reihe von Plausibilitätsprüfungen gemäß PKCS #1 v2.1 unterzogen. Scallion unterstützt mehrere RSA-Schlüsselgrößen mit optimierten Kernen für 1024b, 2048b und 4096b. Andere Schlüsselgrößen funktionieren möglicherweise, wurden aber nicht getestet.

Danksagungen / Referenzen

• Scallion basiert teilweise auf shallot und wurde von vanitygen inspiriert
• Die OpenCL SHA-1-Implementierung wurde von NearSHA adaptiert
• Enthält Komponenten von OpenTK und OpenSSL-net

Spenden

Sie können Spenden gerne an die Bitcoin-Adresse richten: 1FxQcu6vhpwsqcTjPsjK43CZ9vjnuk4Hmo