main.go
package main
import (
"bytes"
"crypto/sha1"
"encoding/hex"
"errors"
"flag"
"fmt"
"html/template"
"io"
"io/ioutil"
"log"
"os"
"os/exec"
"path/filepath"
"runtime"
"strings"
"sync"
"sync/atomic"
"time"
)
func hasSuffix(b, suffix []byte) bool {
h := sha1.Sum(b)
//log.Printf("%s =~ %s?\n", paddedHex(h[:]), paddedHex(suffix))
return bytes.HasSuffix(h[:], suffix)
}
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 findSuffixSingle(suffix, b []byte, min uint32) (bool, []byte) {
var (
ts = readUint32(b[4:])
round uint64
start = time.Now()
total = ts - min
)
for ; ts > min; ts-- {
b[4] = byte(ts >> 24)
b[5] = byte(ts >> 16)
b[6] = byte(ts >> 8)
b[7] = byte(ts)
if hasSuffix(b, suffix) {
return true, b
}
round++
if round%10000000 == 0 {
delta := float64(time.Since(start)) / float64(time.Second)
log.Printf("%s @ %.1f%%, %fk/s\n",
time.Unix(int64(ts), 0).Format("2006-01-02"),
(float64(round)/float64(total))*100, float64(round)/delta)
}
}
return false, nil
}
func findSuffixWorker(suffix, b []byte, ts, min, step uint32, found chan []byte, wg *sync.WaitGroup, round *uint64) {
//log.Printf("worker: scan %d down to %d, step %d\n", ts, min, step)
for ; ts > min; ts = ts - step {
atomic.AddUint64(round, 1)
b[4] = byte(ts >> 24)
b[5] = byte(ts >> 16)
b[6] = byte(ts >> 8)
b[7] = byte(ts)
if hasSuffix(b, suffix) {
found <- b
return
}
}
wg.Done()
}
func findSuffixParallel(suffix, b []byte, min uint32, workers int) (bool, []byte) {
ts := readUint32(b[4:])
wg := new(sync.WaitGroup)
var (
round uint64
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, ts-uint32(i), min, uint32(workers), found, wg, &round)
}
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)
return fmt.Sprintf("%s %s, %sk/s [r=%d,t=%s]\r",
time.Now().Format("2006/01/02 15:04:05"),
progress((float64(round)/float64(total))*100+.05, 20),
humanScale(float64(round)/(float64(delta)/float64(time.Second))),
round, 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 generateKeyRing(bits int, name, email string) (secRing, pubRing []byte, 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", "--batch", "--gen-key")
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)
}
if secRing, err = ioutil.ReadFile(secFile.Name()); err != nil {
return
}
if pubRing, err = ioutil.ReadFile(pubFile.Name()); err != nil {
return
}
return
}
func saveRing(name string, pubRing, secRing []byte, ts uint32, offset, length int, uidString string) (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)
pubRing[4] = byte(ts >> 24)
pubRing[5] = byte(ts >> 16)
pubRing[6] = byte(ts >> 8)
pubRing[7] = byte(ts)
pubName := filepath.Join(name, "pubring.gpg")
log.Printf("saving pubring to %s\n", pubName)
if err = ioutil.WriteFile(pubName, pubRing, 0644); err != nil {
return
}
secRing[4] = byte(ts >> 24)
secRing[5] = byte(ts >> 16)
secRing[6] = byte(ts >> 8)
secRing[7] = byte(ts)
secName := filepath.Join(name, "secring.gpg")
log.Printf("saving secring to %s\n", secName)
if err = ioutil.WriteFile(secName, secRing, 0600); err != nil {
return
}
return
}
func find(workers, bits int, name, email string, suffix []byte, min time.Duration) (found bool, err error) {
var secRing, pubRing []byte
if secRing, pubRing, err = generateKeyRing(bits, name, email); err != nil {
return
}
ringFile := bytes.NewBuffer(pubRing)
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 workers == 1 {
found, key = findSuffixSingle(suffix, packet, uint32(tsMin.Unix()))
} else {
found, key = findSuffixParallel(suffix, packet, uint32(tsMin.Unix()), workers)
}
if found {
delta := time.Since(start)
fingerprint := readableFingerprint(key)
log.Printf("public key %s found in %s\n", fingerprint, delta)
uid := fmt.Sprintf("%s <%s>", name, email)
err = saveRing(strings.Replace(fingerprint, " ", "", -1), pubRing, secRing, readUint32(key[4:]), offset, len(packet), uid)
}
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)
}
for {
var found bool
if found, err = find(*workers, *bits, *name, *email, suffix, min); err != nil {
log.Fatalln(err)
}
if found {
break
}
log.Println("... not found, next round!")
}
}