leijurv
commented
5 years ago After some more analysis, I have found that the above is wrong, and that the C code from slime-seed is wrong half the time.
The issue is in Java itself:
public long nextLong() {
// it's okay that the bottom word remains signed.
return ((long)(next(32)) << 32) + next(32);
}It's NOT okay that the bottom word remains signed. I found that when the second call to next(32); provides a negative integer, then the 48 to 64 expander in slime-seed is incorrect.
Here is the current code that only succeeds if second >= 0
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
long seed = System.nanoTime();
long scrambled = (seed ^ 0x5DEECE66DL) & MASK_LOWER_48_BITS;
scrambled = (scrambled * 0x5DEECE66DL + 11) & MASK_LOWER_48_BITS;
int first = (int) (scrambled >>> 16);
scrambled = (scrambled * 0x5DEECE66DL + 11) & MASK_LOWER_48_BITS;
int second = (int) (scrambled >>> 16);
long prediction = ((long) (first) << 32) + second;
long rand = (new Random(seed).nextLong());
System.out.println(rand + " " + prediction + " " + (rand == prediction));
System.out.println(first + " " + second);
if (second < 0) {
continue;
}
long partial = rand & MASK_LOWER_48_BITS;
System.out.println((rand >> 48) & MASK_LOWER_16_BITS);
List<Long> reversed = reverse(partial);
System.out.println(rand + " " + reversed);
if (!reversed.contains(rand)) {
throw new IllegalStateException("Unable to invert " + rand);
}
}
}
public static final long MASK_LOWER_48_BITS = (1L << 48) - 1;
public static final long MASK_LOWER_32_BITS = (1L << 32) - 1;
public static final long MASK_LOWER_16_BITS = (1L << 16) - 1;
public static List<Long> reverse(long partial) {
List<Long> found = new ArrayList<>();
long low = (partial >> 32) & MASK_LOWER_16_BITS;
long high = partial & MASK_LOWER_32_BITS;
for (int i = 0; i < (1 << 16); i++) {
long prev = invert((high << 16) | i);
long lastOutput = prev >> 16;
if (low == (lastOutput & MASK_LOWER_16_BITS)) {
System.out.println(i);
found.add(((long) lastOutput << 32) | (high));
}
}
return found;
}
public static long invert(long l) {
return ((l - 11) * 246154705703781L) & MASK_LOWER_48_BITS;
}
Badel2
Here https://www.reddit.com/r/technicalminecraft/comments/7idgzx/seed_reverse_engineering_survey_of_approaches_and/dqzczmc/ you stated
The problem is that the higher bits (48...29) need even more slime chunks, so we need to combine this strategy with structure finding, biomes, or other stuff, like the color of the sheep wool (not seriously, but that's a funny bug)..This is true, you can't figure out the upper 16 bits if the seed is a random 64-bit number. For this to happen, you'd need to generate a truly random 64-bit number and set it as the seed. In that scenario, you would need to check all 65,536 possible seeds against the world as you see it, potentially just by generating that number of chunks and comparing them, it would be reasonably fast, but it can be faster!
If the seed itself was generated normally, by Minecraft itself, the generation of the seed (including the ignored upper 16 bits) was also done by util.Random, which also ignores the upper 16 bits of its input.
It's generated by
(new Random()).nextLong(). Internally, this is two successive calls tonext(32), returning an int, combined into a long. That function simply returns the middle 32 bits of the seed (as in, a call to next(32) doesseed=seed*multiplier +addend; seed = seed & mask; return seed >>> 16). We know the lower 48 bits of the result of two successive calls to this. As in, we know the lower 16 bits ofseed0 >>> 16and we know all 32 bits of((seed0 * multiplier + addend) & mask) >>> 16. Therefore, we can take the lower 32 bits of our partial seed, shift it left by 16 bits, and try all possibilities for those lowest 16 bits. For each one, we can check if it's plausible by inverting the random seed step function, taking us from(seed0 * multiplier + addend) & mask(not shifted right by 16!!) back toseed0(or the lower 48 bits of it). Then, we need to take the middle 16 bits of the 48 bitseed0. Why? Becauseseed0 >>> 16has the same lower 16 bits as the uppermost known 16 bits of our partial seed! As above, we know that our 48-bit partial seed's uppermost 16 bits are the lower 16 bits masked out of our first call tonext(32). And if they are truly equal, we've found a candidate for the correct upper 16 bits (there's some randomness, but we are guaranteed to find at least one if this seed was truly generated byRandom.nextLong).You can invert
(seed0 * multiplier + addend) & mask(more or less) like so:((seed - 11) * 246154705703781L) & MASK_LOWER_48_BITSsource (information is lost in this multiplication but since the lower 48 bits are masked both ways, this does actually invert it properly)Tying it all together, if
(partialSeed >> 32) & MASK_LOWER_16_BITS == (((((((partialSeed & MASK_LOWER_32_BITS) << 16) | candidateHighestSixteenBits) - 11) * 246154705703781L) & MASK_LOWER_48_BITS) >> 16) & MASK_LOWER_16_BITS, thencandidateHighestSixteenBits << 48 | partialSeedis a possible seed.On average it will find just one, and it's guaranteed to find at least one if the seed was generated normally randomly, but it could find more, those will need to be checked manually.
The method is here https://github.com/pruby/slime-seed/blob/master/expand48to64random.c