package main import ( "bytes" "crypto/sha1" "encoding/binary" "encoding/hex" "errors" "flag" "fmt" "html/template" "io" "io/ioutil" "log" "os" "os/exec" "path/filepath" "runtime" "strconv" "strings" "sync" "time" ) func progress(perc float64, size int) string { var ( s = "[" i int d = 100.0 / float64(size) ) for ; i < int(perc/d); i++ { s += "#" } for ; i < size; i++ { s += "-" } s += "]" return fmt.Sprintf("%s %5s%%", s, fmt.Sprintf("%.1f", perc)) } func readUint32(b []byte) uint32 { return uint32(b[0])<<24 | uint32(b[1])<<16 | uint32(b[2])<<8 | uint32(b[3]) } func humanScale(f float64) string { switch { case f > 1e15: return fmt.Sprintf("%.3fP", f/1e15+.0005) case f > 1e12: return fmt.Sprintf("%.3fT", f/1e12+.0005) case f > 1e9: return fmt.Sprintf("%.3fG", f/1e9+.0005) case f > 1e6: return fmt.Sprintf("%.3fM", f/1e6+.0005) case f > 1e3: return fmt.Sprintf("%.3fk", f/1e3+.0005) default: return fmt.Sprintf("%.f", f) } } func findSuffixWorker(suffix, b []byte, offset int, ts, min, step uint32, found chan []byte, wg *sync.WaitGroup, round *uint64) { var ( o = offset + 1 // Offset for the timestamp in the packet h = sha1.New() ) for ; ts > min; ts = ts - step { *round++ b[o+0] = byte(ts >> 24) b[o+1] = byte(ts >> 16) b[o+2] = byte(ts >> 8) b[o+3] = byte(ts) h.Reset() if bytes.HasSuffix(h.Sum(b), suffix) { found <- b return } } wg.Done() } func findSuffix(suffix, b []byte, offset int, min uint32, workers int) (bool, []byte) { ts := readUint32(b[4:]) wg := new(sync.WaitGroup) var ( round = make([]uint64, workers) found = make(chan []byte, 1) total = ts - min ) for i := 0; i < workers; i++ { wg.Add(1) // Make a copy of the slice, since all workers will manipulate wb := make([]byte, len(b)) copy(wb, b) go findSuffixWorker(suffix, wb, offset, ts-uint32(i), min, uint32(workers), found, wg, &round[i]) } abort := make(chan struct{}, 1) go func() { wg.Wait() abort <- struct{}{} }() timer := time.NewTicker(time.Second) start := time.Now() state := func() string { delta := time.Since(start) var rounds uint64 for _, r := range round { rounds += r } return fmt.Sprintf("%s %s, %sk/s [r=%d,t=%s]\r", time.Now().Format("2006/01/02 15:04:05"), progress((float64(rounds)/float64(total))*100+.05, 20), humanScale(float64(rounds)/(float64(delta)/float64(time.Second))), rounds, delta/time.Second*time.Second) } defer func() { timer.Stop() fmt.Println(state()) }() for { select { case key := <-found: return true, key case <-abort: return false, nil case <-timer.C: os.Stdout.Write([]byte(state())) } } } func readFull(r io.Reader, buf []byte) (n int, err error) { n, err = io.ReadFull(r, buf) if err == io.EOF { err = io.ErrUnexpectedEOF } return } func paddedHex(buf []byte) string { var ( tmp = buf pad string ) for i := 0; i < len(tmp); i += 2 { pad += strings.ToUpper(hex.EncodeToString(tmp[i:i+2])) + " " } return pad[:len(pad)-1] } func readableFingerprint(packet []byte) string { hash := sha1.Sum(packet) return paddedHex(hash[:]) } func readPublicKeyPacket(packet []byte, offset int) (err error) { //log.Printf("offset: %d\n", offset) //log.Printf("packet:\n%s\n", hex.Dump(packet[:16])) if version := packet[offset]; version != 4 { return fmt.Errorf("unsupported public key version %d", version) } switch keyType := packet[offset+5]; keyType { case 1: log.Println("public key type RSA") case 2: log.Println("public key type RSA (encrypt only)") case 3: log.Println("public key type RSA (sign only)") case 16: err = errors.New("unsupported ElGamal public key") return case 17: err = errors.New("unsupported DSA public key (you suck!)") return case 18: err = errors.New("unsupported ECDH public key") return case 19: err = errors.New("unsupported ECDSA public key") return default: err = fmt.Errorf("unknown public key %#02x", keyType) return } log.Printf("public key %s\n", readableFingerprint(packet)) return } func readPacket(r io.Reader) (packet []byte, tag byte, offset int, err error) { packet = make([]byte, 1, 4096) if _, err = readFull(r, packet); err != nil { return } if packet[0]&0x80 == 0 { err = errors.New("tag byte does not have MSB set") return } if packet[0]&0x40 == 0 { tag = (packet[0] & 0x3f) >> 2 lengthType := packet[0] & 3 if lengthType == 3 { err = errors.New("packet contains no data") return } lengthBytes := 1 << lengthType //log.Printf("got %d length bytes\n", lengthBytes) packet = append(packet, make([]byte, lengthBytes)...) _, err = readFull(r, packet[1:]) if err != nil { return } //log.Printf("packet: %q (%d)\n", packet, len(packet)) var length int for i := 0; i < lengthBytes; i++ { length <<= 8 length |= int(packet[1+i]) } offset = lengthBytes + 1 packet = append(packet, make([]byte, length)...) _, err = readFull(r, packet[lengthBytes+1:]) return } err = errors.New("new packet not supported") return } var ( keyRingTemplate, _ = template.New("keyring").Parse(`Key-Type: RSA Key-Length: 4096 Subkey-Type: RSA Subkey-Length: 1024 Name-Real: {{.Name}} Name-Email: {{.Email}} Expire-Date: 0 %pubring {{.PubRing}} %secring {{.SecRing}} %commit %echo done`) ) func populateStdin(str string) func(io.WriteCloser) { return func(stdin io.WriteCloser) { defer stdin.Close() io.Copy(stdin, bytes.NewBufferString(str)) } } func gpgVersion() (float64, error) { b, err := exec.Command("gpg", "--version").Output() if err != nil { return 0, err } const prefix = "gpg (GnuPG) " if !strings.HasPrefix(string(b), prefix) { return 0, nil } return strconv.ParseFloat(string(b[len(prefix):len(prefix)+3]), 32) } type keyRing struct { pub, sec []byte } func generateKeyRing(bits int, name, email string) (ring *keyRing, err error) { var secFile, pubFile *os.File if secFile, err = ioutil.TempFile("", "secring"); err != nil { return } secFile.Close() if pubFile, err = ioutil.TempFile("", "pubring"); err != nil { return } pubFile.Close() defer func() { os.Remove(secFile.Name()) os.Remove(pubFile.Name()) }() log.Printf("generating %d bits RSA key for %s <%s>\n", bits, name, email) cmd := exec.Command("gpg", "--no-tty", "--batch", "--gen-key") cmd.Stdout = ioutil.Discard cmd.Stderr = os.Stderr var stdin io.WriteCloser if stdin, err = cmd.StdinPipe(); err != nil { return } if err = cmd.Start(); err != nil { return } if err = keyRingTemplate.Execute(stdin, map[string]interface{}{ "Bits": bits, "Name": name, "Email": email, "PubRing": pubFile.Name(), "SecRing": secFile.Name(), }); err != nil { return } if err = stdin.Close(); err != nil { return } if err = cmd.Wait(); err != nil { log.Panic(err) } ring = new(keyRing) if ring.sec, err = ioutil.ReadFile(secFile.Name()); err != nil { return } if l := len(ring.sec); l < 1024 { err = fmt.Errorf("keypair generation failed: unlikely secring size %d", l) return } if ring.pub, err = ioutil.ReadFile(pubFile.Name()); err != nil { return } if l := len(ring.pub); l < 1024 { err = fmt.Errorf("keypair generation failed: unlikely secring size %d", l) return } return } func generateKeyRings(rings chan *keyRing, bits int, name, email string) { for { start := time.Now() ring, err := generateKeyRing(bits, name, email) if err != nil { log.Fatalln(err) } log.Printf("generated %d bits keyring in %s\n", bits, time.Since(start)) // This will block until there is a slot available on the channel rings <- ring } } func saveRing(name string, ring *keyRing, ts uint32, offset, length int) (err error) { log.Printf("saving dir %s/\n", name) if err = os.MkdirAll(name, 0700); err != nil { return } log.Printf("found match on %s\n", time.Unix(int64(ts), 0)) log.Printf("replace timestamp at +%d\n", offset) binary.BigEndian.PutUint32(ring.pub[offset+1:], ts) pubName := filepath.Join(name, "pubring.gpg") log.Printf("saving pubring to %s\n", pubName) if err = ioutil.WriteFile(pubName, ring.pub, 0644); err != nil { return } binary.BigEndian.PutUint32(ring.sec[offset+1:], ts) secName := filepath.Join(name, "secring.gpg") log.Printf("saving secring to %s\n", secName) if err = ioutil.WriteFile(secName, ring.sec, 0600); err != nil { return } return } func find(workers int, rings chan *keyRing, suffix []byte, min time.Duration) (found bool, err error) { // Pull a new keyring from the channel, this will block until there is one available ring := <-rings ringFile := bytes.NewBuffer(ring.pub) var ( packet []byte tag byte offset int ) if packet, tag, offset, err = readPacket(ringFile); err != nil { log.Fatalln(err) } log.Printf("read %d bytes %#02x (%#02x) packet, offset %d\n", len(packet), tag, packet[0], offset) if !(tag == 0x05 || tag == 0x06) { log.Fatalf("packet not a private key or public key, got %#02x\n", tag) } if err = readPublicKeyPacket(packet, offset); err != nil { log.Fatalln(err) } tsMin := time.Now().Add(-min) log.Printf("scanning for suffix %s up until %s\n", paddedHex(suffix), tsMin) var ( key []byte start = time.Now() ) if found, key = findSuffix(suffix, packet, offset, uint32(tsMin.Unix()), workers); found { delta := time.Since(start) fingerprint := readableFingerprint(key) log.Printf("public key %s found in %s\n", fingerprint, delta) err = saveRing(strings.Replace(fingerprint, " ", "", -1), ring, readUint32(key[4:]), offset, len(packet)) } return } func main() { suffixString := flag.String("suffix", "", "suffix to find") scanMin := flag.String("min", "43800h", "minimal valid timestamp") bits := flag.Int("bits", 4096, "RSA key size") name := flag.String("name", "John Doe", "name in uid") email := flag.String("email", "john.doe@example.org", "email in uid") workers := flag.Int("workers", (runtime.NumCPU()*3)/2, "number of workers") flag.Parse() if *suffixString == "" { log.Fatalln("supply a -suffix") } suffix, err := hex.DecodeString(*suffixString) if err != nil { log.Fatalf("invalid suffix %q: %v\n", *suffixString, err) } min, err := time.ParseDuration(*scanMin) if err != nil { log.Fatalf("invalid duration %q: %v\n", *scanMin, err) } tmp, err := ioutil.TempDir("", "pgp-suffix-finder") if err != nil { log.Fatalln("unable to create temporary folder: %v\n", err) } defer os.RemoveAll(tmp) if err = os.Mkdir(filepath.Join(tmp, ".gnupg"), 0700); err != nil { log.Fatalln("unable to create temporary folder: %v\n", err) } os.Setenv("GNUPGHOME", filepath.Join(tmp, ".gnupg")) ver, err := gpgVersion() if err != nil { log.Fatalf("failed to probe GnuPG version: %v\n", err) } if ver == 0.0 { log.Println("WARNING! unknown GnuPG version") } else if ver > 2.0 { log.Printf("WARNING! unsupported GnuPG version %.1f.x; tested up until 2.0.30\n", ver) } else { log.Printf("GnuPG version %.1f.x\n", ver) } for { var ( found bool rings = make(chan *keyRing, 1) ) go generateKeyRings(rings, *bits, *name, *email) if found, err = find(*workers, rings, suffix, min); err != nil { log.Fatalln(err) } if found { close(rings) break } log.Println("... not found, next round!") } }