Atualização do Projeto 2020

Scallion foi um projeto hobby para aprender OpenCL e RSA. Não estamos mantendo o Scallion atualmente. Ele se degradou de duas maneiras importantes:

1. Tor passou para endereços Onion v3, que o Scallion não suporta. Endereços v2 antigos deixarão de funcionar em outubro de 2021. O novo padrão usa primitivas criptográficas diferentes e é, no geral, mais complicado. O truque que usamos para gerar lotes de chaves RSA na GPU não funciona da mesma forma para as novas chaves ECDSA necessárias. É possível gerar chaves ECDSA semelhantes (mas não compatíveis) na GPU, para geração de endereços Bitcoin. Veja vanitygen-plus ou o antigo oclvanitygen. Para uma lista de ferramentas de geração de endereços personalizados (baseadas em CPU) que funcionam para serviços ocultos Tor v3, veja este post no blog.
2. A versão do OpenSSL da qual dependemos foi descontinuada e não está disponível na maioria dos SOs modernos. Não é simples atualizá-la, pois usamos algumas funções matemáticas de baixo nível no OpenSSL que não estão disponíveis nas ligações C# para as versões mais recentes. Eu pessoalmente executo o Scallion usando o dockerfile nvidia, que é baseado no Ubuntu 16.04 Xenial, que ainda vem com o OpenSSL desatualizado. No entanto, essa opção é apenas para usuários de GPU Nvidia. Você também pode tentar compilar a biblioteca OpenSSL desatualizada e ligá-la diretamente, ou executar uma versão mais antiga do seu SO a partir de um Live USB ou VM (com passagem PCI-e).

Com atenção e esforço suficientes, seria possível superar ambos os desafios acima. Poderíamos implementar suporte para o algoritmo de geração de chaves ECDSA na GPU para obter suporte a Tor v3. Poderíamos atualizar o OpenSSL e substituir as funções matemáticas por uma biblioteca diferente, ou criar nosso próprio wrapper de código gerenciado para a biblioteca OpenSSL. No entanto, provavelmente seria melhor adicionar suporte a endereços onion v3 a um projeto mantido como vanitygen-plus.

Scallion

Scallion permite criar chaves GPG e endereços .onion personalizados (para serviços ocultos do Tor) usando OpenCL.

O Scallion roda no Mono (testado no Arch Linux) e .NET 3.5+ (testado no Windows 7 e Server 2008).

O Scallion está atualmente em fase beta e em desenvolvimento ativo. No entanto, acreditamos que está pronto para uso. Melhorias são esperadas principalmente em desempenho, interface do usuário e facilidade de instalação, não no algoritmo geral usado para gerar chaves.

O Scallion está disponível sob a licença MIT. Se você usar código deste projeto em seus próprios projetos, agradeceríamos se nos avisasse em [email protected].

Perguntas Frequentes

Aqui estão algumas perguntas frequentes e suas respostas:

• Por que gerar chaves GPG?

  O Scallion foi usado para encontrar colisões para cada ID de chave de 32 bits no conjunto forte da Web of Trust, demonstrando o quão inseguros são os IDs de chave de 32 bits. Houve/há uma palestra no DEFCON (vídeo) e informações adicionais podem ser encontradas em https://evil32.com/.

• Quais são os caracteres válidos?

  Endereços .onion do Tor usam Base32, consistindo de todas as letras e os dígitos de 2 a 7, inclusive. Eles não diferenciam maiúsculas de minúsculas.

  Impressões digitais GPG usam hexadecimal, consistindo dos dígitos 0-9 e das letras A-F.

• É possível usar ASICs de Bitcoin (ex.: Jalapeno, KnC) para acelerar esse processo?

  Infelizmente, não. Embora o processo que o Scallion usa seja conceitualmente semelhante (incrementar um nonce e verificar o hash), os detalhes são diferentes (SHA-1 vs. SHA-256 duplo para Bitcoin). Além disso, os ASICs de Bitcoin são tão rápidos porque são extremamente adaptados para aplicações de mineração de Bitcoin. Por exemplo, aqui está a folha de dados do CoinCraft A-1, um ASIC que nunca foi lançado, mas provavelmente é indicativo da abordagem geral. O microcontrolador envia trabalho na forma dos últimos 128 bits de um bloco Bitcoin, o estado intermediário do hash dos bits anteriores, uma dificuldade alvo e o nonce máximo a tentar. O ASIC escolhe o local para inserir o nonce e decide quais blocos atendem ao hash. O Scallion precisa inserir o nonce em um local diferente e verifica uma correspondência de padrão em vez de apenas "menor que XXXX".

• Como usar vários dispositivos?

  Execute várias instâncias do Scallion. 😄 As buscas do Scallion são probabilísticas, então você não estará repetindo trabalho com o segundo dispositivo. O suporte a vários dispositivos verdadeiro não seria muito difícil, mas também não acrescentaria muito. Já executei várias instâncias do Scallion no tmux ou screen com grande sucesso. Você só precisará abortar manualmente todos os jobs quando um encontrar um padrão (ou escrever um script de shell para monitorar o arquivo de saída e matar todos quando encontrar resultados).

Dependências

• OpenCL e drivers relevantes instalados e configurados. Consulte a documentação da sua distribuição.
• OpenSSL. Para Windows, as DLLs x86 pré-compiladas estão incluídas.
• No Windows apenas, VC++ Redistributable 2008

Download Binário

Quer apenas a versão binária mais recente? Pegue-a aqui.

Compilar no Linux

Pré-requisitos

• Obtenha o mono mais recente para sua distribuição Linux:

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

• Instale dependências comuns:

  root@kitploit:~

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

• Compilação AMD/OpenSource sudo apt-get install ocl-icd-opencl-dev

• Compilação Nvidia sudo apt-get install nvidia-opencl-dev nvidia-opencl-icd

• Finalmente msbuild scallion.sln

Docker Linux (apenas GPUs nvidia)

1. Tenha o runtime do contêiner nvidia-docker

2. Compile o contêiner:

   root@kitploit:~

   docker build -t scallion -f Dockerfile.nvidia .
   

3. Execute:

   root@kitploit:~

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

   captura de tela da saída esperada

Compilar no Windows

1. Abra 'scallion.sln' no VS Express for Desktop 2012
2. Compile a solução. Eu fiz tudo em modo debug.

Uso

Reiniciar o Scallion durante uma busca não fará você perder "progresso". É uma busca probabilística e o Scallion não faz "progresso"

Listar dispositivos

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

Gerar um hash

$ mono scallion/bin/Debug/scallion.exe -d 0 prefixo
Cozinhando algumas scallions deliciosas...
Usando kernel otimizado do arquivo kernel.cl (Optimized4)
Usando tamanho de grupo de trabalho 128
Compilando kernel... pronto.
Testando hash SHA1...
CPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
GPU SHA-1: d3486ae9136e7856bc42212385ea797094475802
Parece bom!
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>prefixo64kxpwmzdz.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 milhões de hashes por segundo

Parando a GPU e desligando...

Hashing de Múltiplos Padrões

O Scallion suporta encontrar um ou mais de múltiplos padrões através de uma sintaxe de regex primitiva. Apenas classes de caracteres (ex. [abcd]) são suportadas. O caractere . representa qualquer caractere. Endereços onion têm sempre 16 caracteres e impressões digitais GPG têm sempre 40 caracteres. Você pode encontrar um sufixo colocando $ no final da correspondência (ex. DEAD$). Finalmente, a sintaxe de pipe (ex. pattern1|pattern2) pode ser usada para encontrar múltiplos padrões. Buscar por múltiplos padrões (dentro do razoável) NÃO produzirá uma diminuição significativa na velocidade. Muitas expressões regulares produzirão um único padrão na GPU e resultarão em nenhuma redução de velocidade.

Alguns casos de uso com exemplos:

• Gerar um prefixo seguido por um número para melhor legibilidade:

  root@kitploit:~

    mono scallion.exe prefixo[234567]
  

• Buscar por vários padrões de uma vez (n.b. -c faz com que o scallion continue gerando mesmo depois de encontrar uma correspondência)

  root@kitploit:~

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

• Buscar pelo sufixo "badbeef"

  root@kitploit:~

    mono scallion.exe .........badbeef
    mono scallion.exe --gpg badbeef$ # Gerar chave GPG
  

• Exemplo complicado auto-explicativo:

  root@kitploit:~

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

Como o Scallion funciona?

Em alto nível, o Scallion funciona da seguinte forma:

1. Gera chave RSA usando OpenSSL na CPU
2. Envia a chave para a GPU
3. Aumenta o expoente público da chave
4. Faz o hash da chave
5. Se a chave hasheada não for uma colisão parcial, vá para o passo 3
6. Se a chave não passar nas verificações de sanidade recomendadas pelo PKCS #1 v2.1 (verificadas na CPU), vá para o passo 3
7. Nova chave com colisão parcial!

O algoritmo básico está descrito acima. Velocidade / desempenho é resultado da massiva paralelização, tanto na GPU quanto na CPU.

Velocidade / Desempenho

É importante perceber que o Scallion realiza uma busca probabilística. Os tempos reais podem variar significativamente do previsto

A geração inicial da chave RSA é feita na CPU. Um i7 Ivy Bridge pode gerar 51 chaves por segundo usando um único núcleo. Cada chave pode fornecer 1 gigahash de expoentes para minerar e uma CPU decente pode acompanhar várias GPUs como está implementado atualmente.

O hashing SHA1 é feito na GPU. As taxas de hash para várias GPUs que testamos estão abaixo (agrupadas por fabricante e ordenadas por potência):

MH/s = milhões de hashes por segundo

Vale notar que a Intel lançou drivers OpenCL para seus processadores e colisões curtas podem ser encontradas na CPU.

Para calcular o número de segundos necessários para uma dada colisão parcial (em média), use a fórmula:

Por exemplo, na minha nVidia Quadro K2000M, vejo cerca de 90 MH/s. Com essa velocidade, posso gerar um prefixo .onion de oito caracteres em cerca de 1h 41m, 2^(5*8-1)/90 milhões = 101 minutos.

Tamanho do Grupo de Trabalho

Por padrão, o Scallion usará o tamanho de grupo de trabalho preferido reportado pelos seus dispositivos. Este é um padrão razoável, mas experimentar com o grupo de trabalho pode aumentar o desempenho.

Segurança

As chaves geradas pelo Scallion são bastante semelhantes às geradas pelo shallot. Elas têm expoentes públicos excepcionalmente grandes, mas passam por todo o conjunto de verificações de sanidade recomendadas pelo PKCS #1 v2.1 através da função RSA_check_key do openssl. O Scallion suporta vários tamanhos de chave RSA, com kernels otimizados para 1024b, 2048b e 4096b. Outros tamanhos de chave podem funcionar, mas não foram testados.

Agradecimentos / Referências

• O Scallion é baseado em parte no shallot e inspirado pelo vanitygen
• A implementação OpenCL SHA-1 foi adaptada do NearSHA
• Inclui componentes do OpenTK e OpenSSL-net

Doações

Sinta-se à vontade para direcionar doações para o endereço Bitcoin: 1FxQcu6vhpwsqcTjPsjK43CZ9vjnuk4Hmo