2020 Project Update

Scallion était un projet de loisir pour apprendre OpenCL et RSA. Nous ne maintenons actuellement pas Scallion. Il a vieilli de deux manières importantes :

1. Tor est passé aux adresses Onion v3, que Scallion ne supporte pas. Les anciennes adresses v2 cesseront de fonctionner en octobre 2021. La nouvelle spécification utilise des primitives cryptographiques différentes et est globalement plus complexe. L'astuce que nous utilisons pour générer des lots de clés RSA sur le GPU ne fonctionne pas de la même manière pour les nouvelles clés ECDSA requises. Il est possible de générer des clés ECDSA similaires (mais pas compatibles) sur le GPU, pour la génération d'adresses Bitcoin. Voir vanitygen-plus ou l'ancien oclvanitygen. Pour une liste d'outils de génération de vanity (sur CPU) fonctionnant pour les services cachés Tor v3, voir ce billet de blog.
2. La version d'OpenSSL sur laquelle nous nous appuyons a été dépréciée et est indisponible dans la plupart des OS modernes. Il n'est pas simple de mettre à jour, car nous utilisons certaines fonctions mathématiques de bas niveau dans OpenSSL qui ne sont pas disponibles dans les liaisons C# pour les versions plus récentes. Personnellement, j'exécute Scallion en utilisant le Dockerfile nvidia, basé sur Ubuntu 16.04 Xenial, qui livre encore l'ancien OpenSSL. Cependant, cela n'est une option que pour les utilisateurs de GPU Nvidia. Vous pouvez également essayer de construire l'ancienne bibliothèque OpenSSL et la lier directement, ou exécuter une version plus ancienne de votre OS depuis une clé USB live ou une VM (avec passthrough PCI-e).

Avec suffisamment d'attention et d'effort, il serait possible de surmonter les deux défis mentionnés ci-dessus. Nous pourrions implémenter le support de l'algorithme de génération de clés ECDSA sur GPU pour obtenir le support Tor v3. Nous pourrions mettre à jour OpenSSL et remplacer les fonctions mathématiques par une autre bibliothèque, ou créer notre propre wrapper de code managé pour la bibliothèque OpenSSL. Cependant, il serait probablement préférable d'ajouter le support des adresses onion v3 à un projet maintenu comme vanitygen-plus.

Scallion

Scallion vous permet de créer des clés GPG de vanity et des adresses .onion (pour les services cachés de Tor) en utilisant OpenCL.

Scallion fonctionne sous Mono (testé sur Arch Linux) et .NET 3.5+ (testé sur Windows 7 et Server 2008).

Scallion est actuellement en version bêta et en développement actif. Néanmoins, nous estimons qu'il est prêt à être utilisé. Les améliorations sont attendues principalement au niveau des performances, de l'interface utilisateur et de la facilité d'installation, pas dans l'algorithme global utilisé pour générer les clés.

Scallion est disponible sous licence MIT. Si vous utilisez du code de ce projet dans vos propres projets, nous apprécierions d'en être informés à [email protected].

FAQ

Voici quelques questions fréquemment posées et leurs réponses :

• Pourquoi générer des clés GPG ?

  Scallion a été utilisé pour trouver des collisions pour chaque identifiant de clé 32 bits dans l'ensemble fort du Web of Trust, démontrant à quel point les identifiants de clé 32 bits sont peu sécurisés. Il y a/avait une conférence au DEFCON (vidéo) et des informations supplémentaires peuvent être trouvées sur https://evil32.com/.

• Quels sont les caractères valides ?

  Les adresses .onion Tor utilisent Base32, composé de toutes les lettres et des chiffres 2 à 7 inclus. Elles sont insensibles à la casse.

  Les empreintes GPG utilisent l'hexadécimal, composé des chiffres 0-9 et des lettres A-F.

• Peut-on utiliser des ASIC Bitcoin (par ex. Jalapeno, KnC) pour accélérer ce processus ?

  Malheureusement, non. Bien que le processus utilisé par Scallion soit conceptuellement similaire (incrémenter un nonce et vérifier le hachage), les détails sont différents (SHA-1 vs double SHA-256 pour Bitcoin). De plus, les ASIC Bitcoin sont aussi rapides car ils sont extrêmement adaptés aux applications de minage Bitcoin. Par exemple, voici la fiche technique du CoinCraft A-1, un ASIC qui n'est jamais sorti, mais qui est probablement représentatif de l'approche générale. Le microcontrôleur envoie le travail sous la forme des 128 derniers bits d'un bloc Bitcoin, l'état intermédiaire du hachage des bits précédents, une difficulté cible et le nonce maximum à essayer. L'ASIC choisit l'emplacement pour insérer le nonce, et il choisit quels blocs satisfont au hachage. Scallion doit insérer le nonce à un emplacement différent, et il vérifie une correspondance de motif plutôt qu'un simple « inférieur à XXXX ».

• Comment utiliser plusieurs appareils ?

  Exécutez plusieurs instances de Scallion. 😄 Les recherches de Scallion sont probabilistes, donc vous ne répéterez pas le travail avec le deuxième appareil. Un vrai support multi-périphériques ne serait pas trop difficile, mais il n'apporterait pas grand-chose non plus. J'ai exécuté plusieurs instances de Scallion dans tmux ou screen avec un grand succès. Vous devrez simplement arrêter manuellement toutes les tâches lorsqu'une trouve un motif (ou écrire un script shell pour surveiller le fichier de sortie et les tuer toutes lorsqu'il voit des résultats).

Dépendances

• OpenCL et les pilotes correspondants installés et configurés. Référez-vous à la documentation de votre distribution.
• OpenSSL. Pour Windows, les DLL x86 pré-compilées sont incluses.
• Sous Windows uniquement, VC++ Redistributable 2008

Téléchargement binaire

Vous voulez simplement la dernière version binaire ? Récupérez-la ici.

Compiler sous Linux

Prérequis

• Obtenez le dernier mono pour votre distribution Linux :

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

• Installez les dépendances communes :

  root@kitploit:~

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

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

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

• Enfin msbuild scallion.sln

Docker Linux (GPUs nvidia uniquement)

1. Ayez le runtime conteneur nvidia-docker

2. Construisez le conteneur :

   root@kitploit:~

   docker build -t scallion -f Dockerfile.nvidia .
   

3. Exécutez :

   root@kitploit:~

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

   capture d'écran de la sortie attendue

Compiler sous Windows

1. Ouvrez 'scallion.sln' dans VS Express pour Desktop 2012
2. Compilez la solution, j'ai tout fait en mode debug.

Utilisation

Redémarrer Scallion pendant une recherche ne perdra pas la « progression ». C'est une recherche probabiliste et Scallion ne fait pas de « progression »

Lister les périphériques

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

Générer un hachage

$ 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...

Hachage multi-motifs

Scallion supporte la recherche d'un ou plusieurs des multiples motifs grâce à une syntaxe regex primitive. Seules les classes de caractères (ex. [abcd]) sont supportées. Le caractère . représente n'importe quel caractère. Les adresses Onion font toujours 16 caractères et les empreintes GPG toujours 40 caractères. Vous pouvez trouver un suffixe en mettant $ à la fin de la correspondance (ex. DEAD$). Enfin, la syntaxe pipe (ex. pattern1|pattern2) peut être utilisée pour trouver plusieurs motifs. Rechercher plusieurs motifs (dans la mesure du raisonnable) NE produira PAS une diminution significative de la vitesse. De nombreuses regexps produiront un motif unique sur le GPU et n'entraîneront aucune réduction de vitesse.

Quelques cas d'utilisation avec exemples :

• Générer un préfixe suivi d'un nombre pour une meilleure lisibilité :

  root@kitploit:~

    mono scallion.exe prefix[234567]
  

• Rechercher plusieurs motifs à la fois (n.b. -c fait que scallion continue à générer même après avoir trouvé une correspondance)

  root@kitploit:~

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

• Rechercher le suffixe "badbeef"

  root@kitploit:~

    mono scallion.exe .........badbeef
    mono scallion.exe --gpg badbeef$ # Générer une clé GPG
  

• Exemple compliqué explicite :

  root@kitploit:~

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

Comment fonctionne Scallion ?

À un niveau élevé, Scallion fonctionne comme suit :

1. Générer une clé RSA en utilisant OpenSSL sur le CPU
2. Envoyer la clé au GPU
3. Augmenter l'exposant public de la clé
4. Hacher la clé
5. Si la clé hachée n'est pas une collision partielle, aller à l'étape 3
6. Si la clé ne passe pas les vérifications de validité recommandées par PKCS #1 v2.1 (vérifiées sur le CPU), aller à l'étape 3
7. Nouvelle clé avec collision partielle !

L'algorithme de base est décrit ci-dessus. La vitesse / performance est le résultat d'une parallélisation massive, à la fois sur le GPU et le CPU.

Vitesse / Performances

Il est important de réaliser que Scallion effectue une recherche probabiliste. Les temps réels peuvent varier considérablement par rapport aux prévisions

La génération initiale de la clé RSA se fait sur le CPU. Un i7 Ivy Bridge peut générer 51 clés par seconde en utilisant un seul cœur. Chaque clé peut fournir 1 gigahach d'exposants à exploiter et un CPU décent peut suivre plusieurs GPU dans l'implémentation actuelle.

Le hachage SHA1 est effectué sur le GPU. Les taux de hachage pour plusieurs GPU que nous avons testés sont ci-dessous (regroupés par fabricant et triés par puissance) :

MH/s = millions de hachages par seconde

Il convient de noter qu'Intel a publié des pilotes OpenCL pour ses processeurs et que des collisions courtes peuvent être trouvées sur le CPU.

Pour calculer le nombre de secondes nécessaires pour une collision partielle donnée (en moyenne), utilisez la formule :

Par exemple, sur mon nVidia Quadro K2000M, j'obtiens environ 90 MH/s. Avec cette vitesse, je peux générer un préfixe .onion de huit caractères en environ 1h 41m, 2^(5*8-1)/90 millions = 101 minutes.

Taille du groupe de travail

Par défaut, Scallion utilisera la taille de groupe de travail préférée déclarée par vos périphériques. C'est une valeur par défaut raisonnable, mais expérimenter avec le groupe de travail peut augmenter les performances.

Sécurité

Les clés générées par Scallion sont assez similaires à celles générées par shallot. Elles ont des exposants publics inhabituellement grands, mais elles sont soumises à l'ensemble complet des vérifications de validité recommandées par PKCS #1 v2.1 via la fonction RSA_check_key d'openssl. Scallion supporte plusieurs tailles de clés RSA, avec des noyaux optimisés pour 1024b, 2048b et 4096b. D'autres tailles de clés peuvent fonctionner, mais n'ont pas été testées.

Remerciements / Références

• Scallion est basé en partie sur shallot et inspiré par vanitygen
• L'implémentation OpenCL de SHA-1 a été adaptée de NearSHA
• Inclut des composants d'OpenTK et d'OpenSSL-net

Dons

N'hésitez pas à diriger les dons vers l'adresse Bitcoin : 1FxQcu6vhpwsqcTjPsjK43CZ9vjnuk4Hmo