scallion: GPU-based Onion Hash generator
Scallion runs on Mono (tested in Arch Linux) and .NET 3.5+ (tested on Windows 7 and Server 2008).
How does Scallion work?
At a high-level Scallion works as follows:
- Generate RSA key using OpenSSL on the CPU
- Send the key to the GPU
- Increase the key’s public exponent
- Hash the key
- If the hashed key is not a partial collision go to step 3
- If the key does not pass the sanity checks recommended by PKCS #1 v2.1 (checked on the CPU) go to step 3
- Brand new key with partial collision!
The basic algorithm is described above. Speed/performance is the result of massive parallelization, both on the GPU and the CPU.
- Why generate GPG keys?Scallion was used to find collisions for every 32bit key id in the Web of Trust’s strong set demonstrating how insecure 32bit key ids are. There was/is a talk at DEFCON (video) and additional info can be found at https://evil32.com/.
- What are valid characters?Tor .onion addresses use Base32, consisting of all letters and the digits 2 through 7, inclusive. They are case-insensitive.
GPG fingerprints use hexadecimal, consisting of the digits 0-9 and the letters A-F.
- Can you use Bitcoin ASICs (e.g. Jalapeno, KnC) to accelerate this process?Sadly, no. While the process Scallion uses is conceptually similar (increment a nonce and check the hash), the details are different (SHA-1 vs double SHA-256 for Bitcoin). Furthermore, Bitcoin ASICs are as fast as they are because they are extremely tailored to Bitcoin mining applications. For example, here’s the datasheet for the CoinCraft A-1, an ASIC that never came out, but is probably indicative of the general approach. The microcontroller sends work in the form of the final 128-bits of a Bitcoin block, the hash midstate of the previous bits, a target difficulty, and the maximum nonce to try. The ASIC chooses the location to insert the nonce, and it chooses what blocks meet the hash. Scallion has to insert the nonce in a different location, and it checks for a pattern match rather than just “lower than XXXX”.
- How can you use multiple devices?Run multiple Scallion instances. 😄 Scallion searches are probabilistic, so you won’t be repeating work with the second device. True multi-device support wouldn’t be too difficult, but it also wouldn’t add much. I’ve run several scallion instances in tmux or screen with great success. You’ll just need to manually abort all the jobs when one finds a pattern (or write a shell script to monitor the output file and kill them all when it sees results).
Copyright 2012 Richard Klafter (www.jollybit.com) and
Eric Swanson <email@example.com>