# Solution

Like in part 1, we have to reconstruct the commit from the commit log. Part 1 is a prerequisite, as we must be able to generate the last commit in part 1 to reconstruct this commit.

```
commit f1543b8d6792da44c7fcf5634c6115c8c8c1a98f
Author: CTF Organizer <[email protected]>
Date: Wed Nov 1 12:32:27 2023 -0700

Somehow people are guessing the password! Add some random letters and numbers at the end to make it really secure.
```

The message mentions adding random letters and numbers at the end of the password. We can brute-force the password assuming it is not too long.

A first try might be to modify the file on disk and then invoke `git commit` and `git reset` for each attempted password. On my machine, that benchmarks at about 9 values/sec. If we assume "random letters and numbers" means random lower- and upper-case English letters and all ten digits, then we have `26*2+10 = 62` possible characters. At the rate of 9 values/sec, brute-forcing only 2 characters will take `62^2/9/60 ~= 7` minutes. Similarly, for 3 characters it will be about 7 hours.

Instead of modifying files on disk and invoking actual git commands, what if we could compute the commit sha ourselves? That would involve figuring out how git internally computes commit shas. Searching on Stack Overflow reveals that it's not actually too complicatedhttps://stackoverflow.com/a/68806436.

The solution script invokes a Go program that brute-forces the password by computing each potential commit sha. It does all the computations in-memory, with minimal copying, and uses goroutines to achieve better performance through parallelization. On my machine, this benchmarks at around 10,000,000 values/sec. It takes a little over 1 minute to find the password.

### Solution Script

```go
package main

import (
"bytes"
"crypto/sha1"
"encoding/hex"
"fmt"
"math"
"os"
"os/exec"
"path/filepath"
"runtime"
"sync/atomic"
"time"

"github.com/briandowns/spinner"
)

const (
// The desired secret length.
secretLen = 5
// The first part of the password (the solution to part 1).
passwordPrefix = "41156adeacb68c10705f9a6f50c8e9ef92de4e58"
// The desired commit sha.
wantSha = "f1543b8d6792da44c7fcf5634c6115c8c8c1a98f"
// The desired parent sha.
parentSha = "958290ed4c52c380e0ebd0797a298119bcb3ba5d"
// The desired git author.
gitName = "CTF Organizer"
// The desired git email.
gitEmail = "[email protected]"
// The desired git date.
gitDate = "1698867147 -0700"
// The desired git message.
gitMessage = "Somehow people are guessing the password! Add some random letters and numbers at the end to make it really secure."
)

// mainFile is the path to main.go provided as a program argument.
var mainFile string

// charSet is the set of possible characters that can be used to construct the
// secret value.
var charSet = []byte("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")

// numPartitions is the number of ways to partition the set of possible secret
// values. Set this to 1 to disable parallelism.
var numPartitions = runtime.NumCPU() * 3 / 4

// partitionSize is the size of each partition.
var partitionSize = int(math.Round(float64(len(charSet)) / float64(numPartitions)))

func check(e error) {
if e != nil {
panic(e)
}
}

func forEachPossibleSecret(part int, callback func([]byte)) {
startIndex := part * partitionSize
endIndex := startIndex + partitionSize
if part == numPartitions-1 {
endIndex = len(charSet)
}

s := make([]byte, secretLen)
for i0 := startIndex; i0 < endIndex; i0++ {
s[0] = charSet[i0]
for i1 := 0; i1 < len(charSet); i1++ {
s[1] = charSet[i1]
for i2 := 0; i2 < len(charSet); i2++ {
s[2] = charSet[i2]
for i3 := 0; i3 < len(charSet); i3++ {
s[3] = charSet[i3]
for i4 := 0; i4 < len(charSet); i4++ {
s[4] = charSet[i4]
callback(s)
}
}
}
}
}
}

func forEachPossibleObjectHash(part int, callback func(secret, hash []byte)) {
mainFileBytes, err := os.ReadFile(mainFile)
check(err)

object := []byte(fmt.Sprintf("blob %d\x00", len(mainFileBytes)+secretLen))
object = append(object, mainFileBytes...)

prefixBytes := []byte(passwordPrefix)

index := bytes.Index(object, prefixBytes)
if index == -1 {
panic("password prefix not found")
}
index += len(prefixBytes)

// make room for copying in the secret
object = append(object[:index+secretLen], object[index:]...)

forEachPossibleSecret(part, func(secret []byte) {
copy(object[index:], secret)
hash := sha1.Sum(object)
callback(secret, hash[:])
})
}

func forEachPossibleTreeHash(part int, callback func(secret, hash []byte)) {
cmd := exec.Command("git", "cat-file", "tree", "HEAD")
cmd.Dir = filepath.Dir(mainFile)
stdout, err := cmd.Output()
check(err)

treeObject := []byte(fmt.Sprintf("tree %d\x00", len(stdout)))
treeObject = append(treeObject, stdout...)

mainObjectName := []byte(filepath.Base(mainFile))

objectNameIndex := bytes.Index(treeObject, mainObjectName)
if objectNameIndex == -1 {
panic("object name index not found")
}

objectHashIndex := objectNameIndex + len(mainObjectName) + 1

forEachPossibleObjectHash(part, func(secret, objHash []byte) {
copy(treeObject[objectHashIndex:], objHash)
treeHash := sha1.Sum(treeObject)
callback(secret, treeHash[:])
})
}

func forEachPossibleCommitHash(part int, callback func(secret, hash []byte)) {
commitObjectData := []byte(fmt.Sprintf(`tree aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
parent %s
author %[2]s <%[3]s> %[4]s
committer %[2]s <%[3]s> %[4]s

%[5]s
`, parentSha, gitName, gitEmail, gitDate, gitMessage))

commitObject := []byte(fmt.Sprintf("commit %d\x00", len(commitObjectData)))
commitObject = append(commitObject, commitObjectData...)

treeHashIndex := bytes.Index(commitObject, []byte("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"))
if treeHashIndex == -1 {
panic("tree hash index not found")
}

treeHashHex := make([]byte, 40)
forEachPossibleTreeHash(part, func(secret, treeHash []byte) {
hex.Encode(treeHashHex, treeHash)
copy(commitObject[treeHashIndex:], treeHashHex)
commitHash := sha1.Sum(commitObject)
callback(secret, commitHash[:])
})
}

func main() {
if len(os.Args) != 2 {
fmt.Printf("Usage: ./%s <path/to/main.go>\n", filepath.Base(os.Args[0]))
os.Exit(1)
}

mainFile = os.Args[1]

status := spinner.New(spinner.CharSets[14], 100*time.Millisecond)
status.Suffix = fmt.Sprintf(" Values/Second: %3.3f, Time Elapsed: %v", 0.0, 0)
status.Start()

wantBytes := make([]byte, 20)
hex.Decode(wantBytes, []byte(wantSha))

found := make(chan string)

start := time.Now()
checkpoint := start.UnixMilli()
var count atomic.Uint64
for part := 0; part < numPartitions; part++ {
go forEachPossibleCommitHash(part, func(secret, hash []byte) {
if bytes.Equal(hash, wantBytes) {
found <- string(secret)
}

newCount := count.Add(1)
if newCount%10000000 == 0 {
now := time.Now().UnixMilli()
diff := now - checkpoint
if diff == 0 {
diff = 1
}
vps := (10000000.0 * 1000.0) / float32(diff)
status.Suffix = fmt.Sprintf(" Values/Second: %3.3f, Time Elapsed: %v", vps, time.Since(start))
checkpoint = now
}
})
}

secret := <-found

status.Stop()
fmt.Printf("Found secret: %s\n", string(secret))
fmt.Printf("Elapsed time: %v\n", time.Since(start))
}
```