Go program to reverse Minecraft seed based on Village locations.

reseed.go

// Copyright Dexter3000 (aka SMemsky) 2018-2019.
// Find me at: github.com/SMemsky

// DONATE ETHEREUM: 0x5Cc0DC5A8E38BaCDB2c316d8B6A052BCB087C8F4
// Thank you :3

// Implementation Note:
// This implementation depends alot on signed integer magic and stuff. Original
// LCG implementation is done in Java and so sign is kept for unexpected bugs I
// didn't think of. Be aware that signed integer bit operations are undefined in
// C++ and C and many other languages.

// Side note:
// Linear Congruential Generators are not cryptographically safe. Keep that in
// mind!

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
package main

import (
    "fmt"
    "log"
    "os"
    // "strconv"
    // "sync"
    "time"
)

const (
    loggerFilename = "reseed.log"

    bitMask48Bit = 0xFFFFFFFFFFFF

    randMultiplier = 0x5DEECE66D
    randIncrement = 0xB
    randReverseMultiplier = 0xDFE05BCB1365 // Don't tell anyone!

    mcMagic1 = 341873128712
    mcMagic2 = 132897987541
    mcMagic3 = 10387312
)

var (
    targets = []Village {
        Village {119, -87},
        Village {146, -123},
        Village {162, -114},
        Village {194, -112},
        Village {224, -96},
        Village {209, -79},
        Village {204, -60},
        Village {265, -124},
        Village {302, -112},
        Village {291, -93},
        Village {341, -81},
        Village {352, -57},
        Village {310, 23},
        Village{-53, -17},
    }

    candidates = []int64 {
        0x1E44260DF6BD,
        0x359C260DF6BD,
        0x4CF4260DF6BD,
        0x644C260DF6BD,
        0x7BA4260DF6BD,
        0x92FC260DF6BD,
        0xAA54260DF6BD,
        0xC1AC260DF6BD,
    }

    start time.Time
)

// Simplified implementation of Java util.Random
// see: https://docs.oracle.com/javase/8/docs/api/java/util/Random.html
type Seed int64

func (s *Seed) setSeed(seed int64) {
    *s = Seed((seed ^ randMultiplier) & bitMask48Bit)
}

func (s *Seed) nextIntMod24() int32 {
    var bits, val int32
    // Roll rounds and check for overflow. Which rarely happens with low modulo.
    // For 2**31+1 overflow happens 1/2 of time! Or was it 2**30+1?
    for ok := true; ok; ok = (bits - val + 23 < 0) {
        *s = Seed((int64(*s) * randMultiplier + randIncrement) & bitMask48Bit)
        // Note that we're using different data type after cutting 17 bits.
        bits = int32(int64(*s) >> 17)
        val = bits % 24
    }
    return val
}

type Village struct {
    ChunkX int32
    ChunkZ int32
}

func (v *Village) canSpawn(worldSeed int64) bool {
    x, z := v.ChunkX, v.ChunkZ
    // Adjust negative values to make sure chunks map smoothly to regions.
    if x < 0 {
        x -= 31;
    }
    if z < 0 {
        z -= 31;
    }

    // Region (k, l)
    k := x / 32;
    l := z / 32;

    // Watch the Bits, Not the Cards!
    seed := worldSeed
    seed += int64(k) * int64(mcMagic1)
    seed += int64(l) * int64(mcMagic2)
    seed += int64(mcMagic3)

    var random Seed
    random.setSeed(seed)

    // Fact: Since seed is the same for 32x32 chunk area, we can only have one
    // village max. But there might be up to 4 villages nearby due to four 32x32
    // chunks bordering each other. But this is quite rare :(

    // (k, l) has lost precision due to integer rounding during division.
    // If random values will exactly match those lost values, then this chunk
    // is suitable for spawning. Though also specific biomes are checked, so
    // this won't guarantee anything :P
    k *= 32
    l *= 32
    k += random.nextIntMod24()
    l += random.nextIntMod24()

    return v.ChunkX == k && v.ChunkZ == l
}

func (v *Village) precalculateMagic() (int32, int32, int64){
    x, z := v.ChunkX, v.ChunkZ
    if x < 0 {
        x -= 31;
    }
    if z < 0 {
        z -= 31;
    }

    k := x / 32;
    l := z / 32;

    preSeed := int64(k) * int64(mcMagic1)
    preSeed += int64(l) * int64(mcMagic2)
    preSeed += int64(mcMagic3)

    k *= 32
    l *= 32

    return v.ChunkX-k, v.ChunkZ-l, preSeed
}

// Algorithm depends on the best-case situation and /might/ fail in some
// rare circumstances
func mine(villages []Village, baseStepTimeout time.Duration) []int64 {
    // We choose a single starting village for which we will evaluate all
    // possible seeds. For each valid seed we reconstruct 48-bit of original
    // world seed candidate.
    // Each candidate is checked against every village (including the starting
    // one, because we might hit special case).

    // Set of resulted seeds (little 48 bits)
    seeds := make(map[int64]struct{})

    // Choose which village will be the starting one
    for _, village := range villages {
        tried := make(map[int64]struct{})

        firstInt, secondInt, preSeed := village.precalculateMagic()
        // val = bits % 24
        // Iterate over all possible keys for first village magic until we hit a
        // special case :)
        // We can just hope than at least one of the villages is not a special
        // case.
        // Max target here is 2147483639 (2**31-9).
        for firstBits := int64(firstInt); firstBits < 2147483640; firstBits += 24 {
            // Iterate on all possible values for hidden 17-bit part.
hiddenBitsLoop:
            for hiddenBits := int64(0); hiddenBits < 131072; hiddenBits++ {
                firstSeed := (firstBits << 17) + hiddenBits
                secondSeed := (firstSeed * randMultiplier + randIncrement) & bitMask48Bit
                secondValue := int32((secondSeed >> 17) % 24)
                if secondValue != secondInt {
                    continue
                }

                // Restore the actual world seed.
                startingSeed := ((firstSeed - randIncrement) * randReverseMultiplier) & bitMask48Bit
                worldSeed := (startingSeed ^ randMultiplier) - preSeed

                var tries uint
                for _, otherVillage := range villages {
                    if otherVillage.ChunkX == village.ChunkX &&
                        otherVillage.ChunkZ == village.ChunkZ {
                        continue
                    }

                    if !otherVillage.canSpawn(worldSeed) {
                        continue hiddenBitsLoop
                    }
                    tries++
                    if tries >= 3 {
                        break
                    }
                }

                // At least this seed is enough to generate the first village :)
                if _, present := tried[hiddenBits]; present {
                    // Theese hidden bits are already checked.
                    continue
                }
                tried[hiddenBits] = struct{}{}

                printf("Hidden bits %05X are chosen for next evaluation. Total: %d values.\n",
                    hiddenBits, len(tried))

likelyBitsLoop:
                for k := firstBits; k < 2147483640; k += 24 {
                    // Restore the actual world seed.
                    firstSeed = (k << 17) + hiddenBits
                    startingSeed := ((firstSeed - randIncrement) * randReverseMultiplier) & bitMask48Bit
                    passedSeed := startingSeed ^ randMultiplier
                    worldSeed := passedSeed - preSeed

                    for _, village := range villages {
                        if !village.canSpawn(worldSeed) {
                            continue likelyBitsLoop
                        }
                    }

                    printf("Seed %012X has passed all checks! There are %d other final candidates.\n",
                        worldSeed, len(seeds))
                    seeds[worldSeed] = struct{}{}
                }
            }
        }
    }

    return nil
}

func printf(format string, v ...interface{}) {
    log.Printf(format, v...)
    fmt.Printf(format, v...)
}

func main() {
    file, err := os.OpenFile(loggerFilename, os.O_WRONLY|os.O_CREATE|os.O_APPEND, 0666)
    if err != nil {
        fmt.Printf("Unable to open/create logs")
        return
    }
    defer file.Close()
    log.SetOutput(file)

    // Bonus part: Find possible villages to check for
    for x := int32(-65); x <= int32(65); x++ {
        for z := int32(-65); z <= int32(65); z++ {
            var value bool
            var found bool
            village := &Village{x, z}
            for _, candidate := range candidates {
                if !found {
                    value = village.canSpawn(candidate)
                    found = true
                } else {
                    if village.canSpawn(candidate) != value {
                        printf("Try searching (%d, %d)\n", x*32, z*32)
                        break
                    }
                }
            }
        }
    }

    // Main part: Mining
    start = time.Now()

    mine(targets, 5 * time.Minute)

    elapsed := time.Since(start)
    printf("Execution took %s\n", elapsed)
}

Note that this program will only help you find last 48 bits of your world seed. Have fun 😃