_______ __ _______
| | |.---.-..----.| |--..-----..----. | | |.-----..--.--.--..-----.
| || _ || __|| < | -__|| _| | || -__|| | | ||__ --|
|___|___||___._||____||__|__||_____||__| |__|____||_____||________||_____|
on Gopher (inofficial)
URI Visit Hacker News on the Web
COMMENT PAGE FOR:
URI Randar: A Minecraft exploit that uses LLL lattice reduction to crack server RNG
skitter wrote 2 days ago:
Impressively, there's Mess Detector, a machine built in Minecraft
itself that predicts the internal state of the rng, using the position
a lit tnt (instead of a block drop):
URI [1]: https://www.youtube.com/watch?v=FPmQ0rnJjNc
smithcoin wrote 2 days ago:
Leijurv, did you do any collaboration with Matt Bolan or did you guys
independently discover this? I can only imagine the power of your two
minds combined. Loved the video. Also laughed when I found out you
named baritone for fitâs voice.
leijurv wrote 1 day ago:
It was a one-way collaboration, in that we referenced their
discoveries and code such as LattiCG [1] , but they were unaware of
anything we were doing until now. [2] Naming Baritone after Fit is
actually a coincidence / joke, the repo github.com/cabaletta/baritone
was the result of random brainstorming for something untaken. We only
later realized it described Fit and thus added that to the readme :)
URI [1]: https://github.com/mjtb49/LattiCG
URI [2]: https://twitter.com/admiral_stapler/status/17806748612594609...
moritonal wrote 2 days ago:
Love how it's basically the Dark Forest logic at play. The only true
way to live is to hide your location and not give off signals.
lawrenceyan wrote 2 days ago:
What level of compute would you need realistically to start doing
things like this irl instead of in Minecraft I wonder?
sdwvit wrote 2 days ago:
Some extra piece of background: 2b2t is a famous server for people
trying to build great structures and then for other people to snipe
their locations and grief said great structures. So this exploit makes
a lot of sense.
danielwmayer wrote 2 days ago:
Yo Leijurv this is so sick! As a fellow game hacker this sort of stuff
is super inspiring.
My girlfriend and I watch all the fitmc videos even though neither of
us play minecraft, and love the ones detailing your insane tooling the
most.
Ever since we watched the nocom one Iâve wondered what you do
professionally - are you in the infosec space?
With the amount of math and computer science knowledge you put into
your work I would guess more in algorithmic trading or something like
that. No worries if you donât want to answer, just curious!
leijurv wrote 2 days ago:
I'm just a regular SWE! Infosec or algorithmic trading - maybe
someday.
tptacek wrote 2 days ago:
This is you? You're fully qualified.
niederman wrote 2 days ago:
Even better, this style of RNG cracking has even been done in-game:
URI [1]: https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A
er4hn wrote 2 days ago:
This appears to be a State Compromise Extension Attack ( [1] ) which is
something that PRNGs that are not CSPRNGs can be subject to.
At this point it feels like having PRNGs be defaults is just not that
safe of a thing to offer in libraries. Like defaulting to allow TLSv1.0
or blowfish in 2024.
URI [1]: https://en.wikipedia.org/wiki/Random_number_generator_attack
lxe wrote 2 days ago:
The video on this is amazing: [1] . I had no idea how sophisticated the
community was.
URI [1]: https://www.youtube.com/watch?v=maMpMOnIJDE
ben_bai wrote 2 days ago:
Yeah the Minecraft and MC anarchy community is insane.
If you found this amazing, take a look at this, it'll blow your mind.
[1] and
URI [1]: https://www.youtube.com/watch?v=ea6py9q46QU
URI [2]: https://www.youtube.com/watch?v=GaRurhiK-Lk
ajcp wrote 2 days ago:
The narration in this video is so over-the-top you'd think they were
talking about Stuxnet or something. I love it.
leijurv wrote 2 days ago:
Yes, absolutely :) that's why we went to FitMC to make the video,
he always delivers.
ro_bit wrote 2 days ago:
Between nocom and this I'm sure at least a dozen people who had
no idea about reverse engineering are going to eventually have a
career in it thanks to his videos, even if I find them incredibly
cheesy. His videos have a habit of reaching and engrossing all
sorts of people who otherwise wouldn't really care about
minecraft server exploits, and maybe that will inspire some of
them to learn more
Thanks for the writeup!
CERNoholic wrote 2 days ago:
The video looks very much like a particle colliderâs detector output.
dzogchen wrote 2 days ago:
I loved playing on 2b2t, until it got too popular all of the sudden
when a YouTuber did a video on it.
2b2t (an anarchy servers in genral) are Minecraft the way it is meant
to be played.
immibis wrote 2 days ago:
I assure you Notch did not mean to make a game of RNG reverse
engineering.
cedws wrote 2 days ago:
I haven't played Minecraft for many years but I'd argue the way it's
supposed to be play is an old version from like 10 years ago with a
tech modpack like Tekkit. Back then, there were open servers where
communities built cities with no grief prevention because people
trusted each other.
permo-w wrote 2 days ago:
if so, you'd be making a poor argument
hot_gril wrote 2 days ago:
When I was a kid, I ran a public server with Logblock and anticheat
but no other plugins, so it was basically vanilla for anyone who
wanted to play nice. People loved it.
lupusreal wrote 2 days ago:
Public servers with e.g. coreprotect for rollbacks are still
around. Most people play nice, but when somebody doesn't their
acts can be reverted without impacting anybody else. It's a lot
of fun if you can get the right team of admins/janitors to keep
it running.
hot_gril wrote 1 day ago:
Maybe, but back in high school, it was very hard to find those.
Especially with things advertised as "vanilla" or
"semi-vanilla" actually having tons of crap installed.
OsrsNeedsf2P wrote 2 days ago:
To be fair, there are still servers like that. Last week I was on
the largest ReIndev mod server, beautiful architecture for as long
as you walked, none protected by any means
nottorp wrote 2 days ago:
Fully unprotected is a lot of work for the mods when the
occasional griefer does find the server.
Easier to have some form of land ownership/permission system for
builds.
chc4 wrote 2 days ago:
LLL lattice reduction is the same algorithm that can be used for
cracking PuTTY keys from biased nonces from the CVE a few days ago.
'tptacek explained a bit about the attack (and links to a cryptopals
problem for it, which I can almost pretend to understand if I squint)
[1] In a similar vein, the SciCraft minecraft server had a creeper farm
which used some sort of black magic setup in order to deterministically
manipulate an RNG state to trigger a "random" lightning strike at a
specific block every frame in order to get better creeper drops.
URI [1]: https://news.ycombinator.com/item?id=40045377
URI [2]: https://youtu.be/TM7SutJyDCk
lyu07282 wrote 2 days ago:
There is also some Rng manipulation to make blocks always drop the
maximum, explained here:
URI [1]: https://youtu.be/ZcdN1wCJPqM?t=390
tptacek wrote 2 days ago:
Sean and Kelby do a much better job of describing what LLL is, but
this is maybe the best explanation of why LLL is that I've ever read.
In all three cases, you only need basic linear algebra, if that
(Kelby wants you to grok Gram-Schmidt, which is like just before the
midterm of an undergrad linear algebra 101).
I really don't have words for how great this post is. It made my
week.
Later
A really concise explanation of the same process you can step through
in Python:
URI [1]: https://crypto.stackexchange.com/questions/37836/problem-wit...
pbsd wrote 1 day ago:
Personally I think [1] is a better answer. It turns the LCG state
recovery into a hidden number-like problem, and works out the
solution that way. It is easy to go from there to (EC)DSA key
recovery.
URI [1]: https://crypto.stackexchange.com/a/86548
squigz wrote 2 days ago:
> some sort of black magic
> which I can almost pretend to understand if I squint
This is me and all cryptography :D
bingaling wrote 2 days ago:
reminds me of phase space plots of weak tcp isn rng [1]
URI [1]: https://lcamtuf.coredump.cx/oldtcp/tcpseq.html
URI [2]: https://lcamtuf.coredump.cx/newtcp/
leijurv wrote 2 days ago:
I believe that may be the spectral test [1] which I mentioned in the
explanation when showing the lattices visually
URI [1]: https://en.wikipedia.org/wiki/Spectral_test
dzdt wrote 2 days ago:
Back in 1999-2000 there was an "International RoShamBo Programming
Competition" [1] where computer bots competed in the game of
rock-paper-scissors. The baseline bot participant just selected its
play randomly, which is a theoretically unbeatable strategy. One joke
entry to the competition was carefully designed to beat the random
baseline ... by reversing the state of the random number generator and
then predicting with 100% accuracy what the random player would play.
Edit: the random-reversing bot was "Nostradamus" by Tim Dierks, which
was declared the winner of the "supermodified" class of programs in the
First International RoShamBo Programming Competition. [2] [1]
URI [1]: https://web.archive.org/web/20180719050311/http://webdocs.cs.u...
URI [2]: https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc
bagels wrote 2 days ago:
So, it was using a pseudorandom generator?
eru wrote 2 days ago:
I remember someone doing the same to an online poker site that had
helpfully documented its PRNG in a laudable attempt at transparency.
(And the transparency got them an improvement in their security in
the end.)
alickz wrote 2 days ago:
I'm surprised they don't use some form of hardware based RNG. I
assume there's many good reasons
URI [1]: https://en.wikipedia.org/wiki/Hardware_random_number_gener...
Elucalidavah wrote 1 day ago:
> don't use some form of hardware based RNG
I've always wondered: why aren't ADCs (e.g. mic input) and
temperature sensors considered a good source of entropy,
particularly if the lower bits are taken?
logtempo wrote 2 days ago:
URI [1]: https://www.random.org/
mikegreenberg wrote 1 day ago:
Or, if you don't want to trust the source,
URI [1]: https://drand.love/
eru wrote 2 days ago:
They wanted to show that they didn't cheat.
In general, you can pick a random seed at the start of the day,
commit to it somewhere (eg publish a hash of it on the bitcoin
blockchain, or just on your website), then use that seed in a
cryptographically secure PRNG on your website all day, and at the
end of the day you publish the seed you already committed to.
This way people can check that you didn't cheat, but can't guess
their opponents cards either.
thenewnewguy wrote 1 day ago:
Wouldn't the most obvious method of cheating be the site owner
peeking at other player's hands and/or the deck? Which this
doesn't (and cannot) prevent?
I guess I'm not sure what publicizing their PRNG is meant to
prove. It shows they didn't cheat via a very specific type of
cheating but there are several other potential cheating
vectors.
eru wrote 9 hours 30 min ago:
> It shows they didn't cheat via a very specific type of
cheating but there are several other potential cheating
vectors.
Yes, and this is not the only anti-cheat method they had.
eru wrote 2 days ago:
(The above was simplified. In a game of poker, you also want
to make sure that when hands get folded, that no one learns
what the cards were.)
joshu wrote 2 days ago:
I submitted the optimally bad entrant the first year, cheesebot.
URI [1]: https://web.archive.org/web/20180719050236/http://webdocs.cs...
rhaps0dy wrote 2 days ago:
Nice! How does Cheesebot work and why did it lose?
BarryMilo wrote 2 days ago:
I can't believe they didn't say anything about your solution! How
did it work?
timdierks wrote 2 days ago:
That's me! Thanks for pulling up the quote from long ago:
> "With his obvious technical skill, and his "cheat early and often"
attitude, Tim could have a promising career as an AI programmer
in the computer games industry. :)"
Instead took a path of security, authoring the TLS RFC and principal
engineer in Google security. Thanks for the flashback.
spacebacon wrote 2 days ago:
I had to checkout your Git after this awesome reply. Gotta love
Hacker News.
I had a cool vision for âtag playâ ⦠I visualize mini RFID
records on a turn table that tell Roku what to play.
romanows wrote 1 day ago:
DJs have timecoded vinyl records that do something like this,
even allowing the DJ to scratch the mp3 that is being played.
teekert wrote 2 days ago:
You pulled a Kobayashi Maru when you got the chance. I bow to thee.
shthed wrote 2 days ago:
Can you share the source to Nostradamus?
le-mark wrote 2 days ago:
Or a write up on the algorithm used? How did knowledge of the
prngs of the impact the impl?
sleepingreset wrote 2 days ago:
you're a wizard bro. hell yea
tomrod wrote 2 days ago:
This makes me happy to see.
reactordev wrote 2 days ago:
So what youâre saying is, if you canât beat em, join em? /s
Iâm actually a bit relieved they have you on the team.
Considering what they (Google) know about us all.
timvdalen wrote 2 days ago:
Only on Hacker News!
dzdt wrote 2 days ago:
The whole commentary about the "supermodified" class of competition
entrants is making my laugh:
> Nostradamus was written by Tim Dierks, a VP of Engineering at
Certicom,
who has a lot of expertise in cryptography. The program defeats the
optimal player by reverse-engineering the internal state of the
random()
generator, which he states "was both easier and harder than I thought
it
would be". To be sporting, it then plays optimally against all other
opponents.
> Fork Bot was based on an idea that Dan Egnor came up with a few
minutes
after hearing about the contest. Since "library routines are
allowed",
his elegant solution was to spawn three processes with fork(), have
each
one make a different move, and then kill off the two that did not
win.
This was implemented by Andreas Junghanns in about 10 lines of code.
Unfortunately, since all three moves lost to the Psychic Friends
Network
after the first turn, the program exited and the remainder of that
match
was declared forfeited.
> The Psychic Friends Network is a truly hilarious piece of
obfuscated C,
written by Michael Schatz and company at RST Corporation. Among other
things, it uses an auxiliary function to find good karma, consults
horoscopes, cooks spaghetti and (mystic) pizza to go with various
kinds
of fruit, #defines democrats as communists, and undefines god. We're
still trying to figure out exactly what it is doing with the stack
frame, but we do know that it never scores less than +998 in a match,
unless it is playing against a meta-meta-cheater.
> The Matrix was written by Darse Billings, who holds the prestigious
title of "Student for Life", and recently started the PhD programme
at
the University of Alberta. The RoShamBo program defeated every
opponent
with a perfect score, based on the simple principle "There is no
spoon".
> Since The Matrix is also the tournament program, it has complete
access
to all other algorithms, data structures, and output routines, and is
therefore unlikely to ever be overtaken. As a result, this category
is
hereby declared to be solved, and thus retired from future
competitions.
handojin wrote 1 day ago:
The whole is better than the sum of the parts. You have nostradamus
which predicts the future, fork bot which plays all playable
presents, and the psychic friends network which rewrites the past.
All under the watchful eye of the matrix.
There's something beautiful here and you honestly couldn't make it
up.
rhaps0dy wrote 2 days ago:
I was very curious about the Psychic Friends Network. One can find
the code here ( [1] ), and it's easy to deobfuscate substantially
by running it through the C preprocessor.
I believe it works as follows:
- It plays randomly for the first 998 turns ( [1] ): this line is
"if (*turn < trials - 2) return libra ? callback() : random() %
3;", and "libra" is initalized to (int) NULL, i.e. zero, on every
invocation.
- In the last 2 turns, it uses `find_goodkarma` to comb through the
stack to find where the variables that match its history and the
opponents' history are stored. These the stack arrays p1hist and
p2hist ( [1] )
They're easy to find because they contain 998 known values each in
a ~random sequence of (0, 1, 2), and they're just upwards of the
stack from the current invocation of the Psychic Friends Network.
`find_goodkarma` simply increments a pointer until the whole
sequence of 998 values matches the known history.
- Then, it rewrites the history to make itself win. These lines (
[1] ) never get executed, then these lines ( [1] ) tally up draws
so far (libra), wins (cancer) and losses (scorpio).
This line makes sure its move is the opponents' move +1 mod 3,
which is the winning move: [1] Then, these lines repeat the same
trick for the number of wins and losses. It checks whether it's p1
or p2 by comparing the addresses of the win/loss arrays, and then
overwrites the wins/losses appropriately using `pizza` [1] in the
end it returns an arbitrary value (the address of `good_hand` mod
3).
It was fun to follow but the result is kind of boring :)
URI [1]: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocai...
URI [2]: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocai...
URI [3]: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocai...
URI [4]: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocai...
URI [5]: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocai...
URI [6]: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocai...
URI [7]: https://github.com/MrValdez/Roshambo/blob/master/rsb-iocai...
konstantinua00 wrote 2 days ago:
so parallel universes lost to rewriting history
amazing
dzdt wrote 2 days ago:
Thanks for the deep dive. Yes fun to follow.
bee_rider wrote 2 days ago:
Pretty cool exploit.
The idea of a free for all bug abusing server is pretty neat, a whole
ânother level of the game.
I guess this is what âactually fightingâ (rather than just using
in-game battling mechanics) would look like if the metaverse really
happened ever.
dontupvoteme wrote 2 days ago:
>The idea of a free for all bug abusing server is pretty neat, a
whole ânother level of the game.
Isn't this basically any non-VAC CS 1.6 server?
hot_gril wrote 2 days ago:
An in-between is Super Smash Bros Melee, where a lot of
tournament-legal ingame tactics rely on bugs. But only ones you can
exploit manually with a regular controller, not actual hacking, and
also one exploit called Wobbling got banned in 2019 (note that this
is a 2001 game).
vitiral wrote 2 days ago:
In those cases the bugs are more like advanced fighting moves. I
don't think item dup or insta-kill bugs would be allowed, even if
they did exist.
hot_gril wrote 2 days ago:
Surprisingly none of those bugs have been found, but yeah they'd
be banned. The weirdest thing people actually use is the yoyo
glitch, which allows Ness to hit a player with a powerful move
from anywhere on the map, but it's hard enough to execute that
it's not OP.
orbital-decay wrote 2 days ago:
> The idea of a free for all bug abusing server is pretty neat, a
whole ânother level of the game.
Balance converging around bugs and exploits is pretty typical for all
PvP sandbox games with cutthroat gameplay, even if not allowed by the
server. ARK: Survival Evolved and Eve Online are infamous for having
huge clans (thousands of players) willing to go extreme lengths at
metagaming and bug exploitation. It isn't always that rosy, ARK had
certain mechanisms to dox players and their multiple Steam accounts,
which I believe led to a few spillovers of the ingame relations to
the real life during the Great War. Sometimes it's very basic stuff
though, like building a huge tower and breaking it upon being raided,
DoSing the server and crashing it, after which it rolls back to a
previous backup made 10-20 min ago, making your base very hard to
raid if you have active players. (an ancient thing that was fixed
many years ago)
Rust (the PvP game, not the language) also had the policy of
encouraging players to spread and publish bugs and exploits on
YouTube, but with the different aim - so that the devs would notice
and patch those faster. This resulted in a pretty robust game that is
extremely hard to exploit without resorting to actual external hacks.
dontupvoteme wrote 2 days ago:
This happened in PvE situations too -- Everquest always had
people, especially guilds, running ShowEQ/MacroEQ to read mob
locations off of the wire/from memory. Often could be used in
non-unethical ways[1]
Sometimes you got funny situations like top guilds cheesing new
raid content in their race to finish it first, leading the devs to
go "cmon bro, you only played yourself" and then patching it
immediately after, but almost never taking any loot away or banning
anyone.
Also funny is the common situation where you don't want to _admit_
to everyone in your guild that you have at least one person running
it, but you can kind of figure it out and it becomes an open
secret.
1 - These are the days where you might have to clear down a dungeon
4 hours to see if a mob is up, or, even worse, to see if it's
camped or not. Alternatively (or as a cover) people just parked
alts but you get the idea.
Also, come to think of it, Diablo had this too with maphacks and
grabit and such
hot_gril wrote 2 days ago:
The problem is, the optimal hacks usually don't make the game fun.
It becomes a war of attrition.
chii wrote 2 days ago:
> don't make the game fun
the fun is no longer the game in an anarchy server. It's in
beating other play's strategies - which actually makes it quite
close to a real war in the physical world.
For example, the 2b2t minecraft wars between factions involve
logistics, misinformation and intelligence (such as spies, fakes
etc). It's no longer just minecraft. But that's what makes it fun
and interesting.
hot_gril wrote 1 day ago:
Yeah but that's not fun, that's tedious work 99% of the time
that culminates in some rare fun.
orbital-decay wrote 1 day ago:
> tedious work 99% of the time that culminates in some rare
fun
Welcome to the multiplayer gaming, especially games like
Minecraft or ARK.
hot_gril wrote 1 day ago:
Online games without hacks are usually fun the whole time,
even Minecraft SMP. Lots of people play those casually.
hatsunearu wrote 2 days ago:
the combat in 2b2t does not look like regular minecraft either.
because of a long history of duped high value items, PvP is just
simply spamming ender crystals which deals massive damage when
broken, and the defense is just how many "totems of undying" you have
which absorbs lethal damage.
of course all the hacked clients automate placing ender crystals,
reloading totems and identifying weak/strong locations so you're
following those guidance to spam damage.
a little before that there were hacked +32,767 damage swords that
will insta kill you that was patched out by the server.
bee_rider wrote 2 days ago:
Thatâs what I think is interesting about it, it looks like (from
the outside at least; for all I know it could be super boring to
play) a new system on top of the old one that obviates some of the
old mechanics by ramming them to infinity/zero, but other mechanics
emerge as a result.
Whatâs the difference between a weak and strong location?
I could imagine funny evolutions over time, just a random thought,
if everyone is running a âglass cannon with lots of 1-hit
protectionâ build, then I guess if players had to pick between
fast/little attacks and big/slow ones, theyâd favor the former.
If everyone is walking around with little attacks just intended to
trigger the 1-hit protections on their fellow glass cannons, then
actually using the in-game armor system might turn those one hits
into two-hits, making it relevant again. If the systems were
properly tuned, (it could be exponentially difficult to gather
1-hit protections and extra lives, so turning those 1-hits into
2-hits could be really valuable), mechanics could be saved from
obsolescence in interesting ways.
Iâm not describing Minecraft at this point, just spitballing. It
would be interesting to see a game designed with this evolution of
âthings being brokenâ taken into account, though. I guess
thatâs what Magic the Gathering is, hahaha.
hatsunearu wrote 2 days ago:
> Whatâs the difference between a weak and strong location?
IIRC ender crystals can only be placed on bedrock, and a lot of
PVP happens on the bombed-out terrain that goes all the way to
bedrock.
The weak terrain in the bedrock are locations where it requires
multiple jumps to get out of, iirc
gu5 wrote 2 days ago:
Adding on to this, explosions deal significantly more damage if
your whole player is exposed - so one block holes where the
bottom half of the player hitbox is covered by bedrock on all
sides are usually marked by hacked clients
asddubs wrote 2 days ago:
I also quite liked the idea of a true anarchy server (from a gameplay
perspective), but on 2b2t in practice this looked like a lot of the
n-word being said in chat, so I stopped playing.
zzzzzzzzzz10 wrote 2 days ago:
You can avoid this using chatfilters.
Players who spam slurs are not worth talking to anyway.
But I agree that there are far better anarchy servers than 2b
around.
bee_rider wrote 1 day ago:
Hypothetically if lots of players ran those kind of filters, a
team could gain a benefit by including slurs in all their
communications I guess, which would be an odd result.
asddubs wrote 1 day ago:
or just use discord
asddubs wrote 2 days ago:
Yeah, I'm good just not hanging out in the same place as people
like that
NoMoreNicksLeft wrote 2 days ago:
Oh god. You just wake up one morning, to see blocks in the sky that
weren't there the night before, ghostly and foglike, until a moment
later they're visible as redstone and observer and slime, and you can
see the dropping infinite TNT. All because the server gave away your
position. You can still escape it, there might even be a few seconds to
grab what you can out of the chest and run, or to build an obsidian
shelter, but that's about it. Not enough time to build a precisely
aimed cannon and you couldn't get the elevation right anyway. Maybe if
you had an elytra and some rockets you could go sabotage, even then
there's this big worldeater hole just 16 chunks away. Have they lava
trapped all the nearby nether portals?
pclmulqdq wrote 2 days ago:
I have seen a lot of interesting and funny RNG issues, but this is one
of the most sophisticated exploits for the least payout. A wonderful
work of art.
ryanisnan wrote 2 days ago:
Indeed! I love seeing how the seemingly innocuous decisions by Mojang
devs are being abused here, so freaking cool.
sebzim4500 wrote 2 days ago:
If they had sold the items they could have probably made some money
(maybe $1000s?). Still a small payout considering the amount of work,
of course.
zzzzzzzzzz10 wrote 2 days ago:
You can make much more by selling items on 2b.
This is not little payout, it sounds to me like one of the most
significant exploits in anarchy minecraft history, possibly even
more than nocom.
pclmulqdq wrote 2 days ago:
RNG vulnerabilities are usually really bad in terms of the
systems they compromise. It often means exposure of keys, huge
numbers of jailbroken devices, or something similar. Making at
most tens of thousands of dollars in Minecraft with one is sort
of cute and fun in comparison.
Of course, I could be underestimating this by a lot.
saagarjha wrote 2 days ago:
This is a bug in how Minecraft does things, not a bug in the
generator itself (which has long been known to be vulnerable to
such things).
marshray wrote 2 days ago:
If "random" implies "contains no information", then it is
indeed a bug in anything calling itself a "random number
generator".
But that's just my opinion. The world is free to use the word
however it wants.
Filligree wrote 2 days ago:
âRandomâ means something closer to âcontains maximal
informationââ¦
armb wrote 2 days ago:
One way of thinking about it is that each bit has maximal
information because knowing the entire previous history
should give you no information about what the next bit
will be ahead of it being revealed.
pclmulqdq wrote 2 days ago:
Yeah, there is a big class of "RNG bugs" where someone uses a
non-cryptographic RNG for secure things, not realizing that
those things are supposed to be secure.
The classic example of these is a password manager that gave
out recovery codes using a PRNG. This is in that class.
kbolino wrote 2 days ago:
While a CSPRNG would have solved this problem, it also
would've created a new one: much slower chunk loading and
random item placement, which would have greatly slowed down
the game simulation, and thus tanked framerate and
playability. As it turns out, the right solution is to use
multiple, isolated non-cryptographic random number
generators with distinct state. That way, even though you
can guess the state of one of them, it doesn't give you any
insight into the others.
pclmulqdq wrote 2 days ago:
The problem of dealing with randomness is about figuring
out how to use CSPRNGs (and TRNGs) as little as possible,
but not too little. CSPRNGs can get to a couple of
GB/sec on a core, so they're not all that bad, but
non-secure PRNGs are over an order of magnitude faster.
I would assume that most of those things (eg chunk
generation/loading) don't need secure RNG at all.
Sharding your RNGs by player is also an option for some
games, and can be easier.
Retr0id wrote 2 days ago:
Modern CSPRNGs can generate numbers at GB/s, I find it
hard to believe it would slow the game down in a
measurable way.
The "right" solution you describe sounds overcomplicated
and error-prone (now you need to think carefully about
which domains are separated) compared to just using a
CSPRNG.
kbolino wrote 2 days ago:
We may be at the point where CSPRNGs are viable for
video game randomness, but that wasn't the case 10+
years ago especially when factoring in compatibility
with 20-year-old hardware (high-end PCs from ca 2004
could play Minecraft).
Even so, a non-crypto PRNG can generally compute a new
random number in 2-4 ALU ops. With SIMD optimization,
that can amortize to under 1 cycle per byte, which
means it takes under a nanosecond to generate a new
32-bit number. I'm not sure even the best
hardware-accelerated CSPRNG on modern hardware can
quite say the same just yet.
Retr0id wrote 2 days ago:
chacha12, a construction that's been around in one
form or another since the '00s, runs at well under 1
cycle per byte on good hardware and still plenty fast
on "bad" hardware [1] (iiuc just using SIMD, no
special acceleration)
But it doesn't really matter what things were like
when the code was first written, it's about how it
could be fixed in the present.
URI [1]: https://bench.cr.yp.to/results-stream.html
kbolino wrote 1 day ago:
Video games do not generate large streams of data,
they generate individual values on demand. Your
link says, to generate 8 bytes, chacha12 on modern
hardware needs 24-45 cpb. That's 192-360 cycles to
generate enough bits for a pseudorandom
double-precision floating-point number. Xoshiro256+
[1], a relatively high-quality generator for this
purpose, can do it with 11 single-cycle ALU ops. So
unoptimized xoshiro256+ should be 17 times faster
than optimized chacha12 on the best hardware. This
is a classic latency vs. throughput issue.
Now, maybe you could optimize the use of a CSPRNG
here by filling large buffer(s) and sampling values
from them. Some warm-up time could go a long way.
However, I fear that you would run into one or more
of the following problems:
- stop-the-world pause to refill the buffer (e.g.
single buffer, no threading)
- synchronization delays from mutex locks (e.g.
ring buffer refilled from a background thread)
- high memory usage (e.g. rotating pool of buffers,
atomically swapped)
Needless to say, none of these solutions is
anywhere near as simple to implement as a
non-cryptographic PRNG.
Now let's consider determinism. Video games
generally use a lot of differently seeded instances
of the same PRNG algorithm to provide random
numbers in different parts of the simulation. Since
each part may demand random numbers at different
rates, it's hard to replace several independent
PRNGs with a single PRNG without compromising
determinism. In the 4096 bytes necessary to run one
instance of chacha12 at its maximum efficiency, you
can fit 128 instances of xoshiro256+ or 512
instances of splitmix64 [2]. [1] = [1] [2] =
URI [1]: https://prng.di.unimi.it/xoshiro256plus.c
URI [2]: https://github.com/svaarala/duktape/blob/m...
Retr0id wrote 1 day ago:
Generating random numbers into a refillable
buffer is the standard for high-performance RNG,
whether you're doing CSPRNG or not (it's how V8
uses xorshift, for example). "stop the world" is
not a problem when the time to refill the buffer
is still measured in nanoseconds.
There's nothing stopping you from having multiple
CSPRNG instances, with deterministic seeds, if
that's a design requirement.
kbolino wrote 1 day ago:
I ran a microbenchmark with Go 1.22, which
ships with both ChaCha8 (a little faster than
ChaCha12) and PCG (a little slower than
xoshiro256+). On my M1 Mac, I'm seeing 2.3
ns/uint64 for PCG and 4.5 ns/uint64 for
ChaCha8. Assuming 3.2 GHz clock speed, that
puts them at about 1 and 2 cpb respectively.
With a floating-point conversion in the mix,
they ran at 4.0 and 4.5 (!) ns/float64
respectively. That's far better than I would
have thought.
So yes, a good, slightly buffered (internal
state seems to be 300 bytes) implementation of
a (quasi-?)CSPRNG is pretty damn close to a
decent quality non-cryptographic PRNG and
likely fast enough for most video games on most
hardware. Though, very few people write games
in Go.
pclmulqdq wrote 1 day ago:
That's not quite a correct benchmark if I'm
understanding what you benchmarked. Xoshiro
and PCG need a chain of serial ops to
generate a number, but not a lot of
parallelism, letting the core do other stuff
while it is working. ChaCha needs a lot of
parallelism, and you are essentially
saturating that core running it.
kbolino wrote 1 day ago:
The builtin benchmarking tool in Go runs
with parallelism set to 2x the number of
cores. That should make evident any code
that scales poorly. It is a tunable
parameter though; I can try 4x cores etc.
I also ran it on x86 (AMD Ryzen 5600X) and
got similar results; everything ran faster
on a 4.6 GHz chip, but ChaCha8 stayed
around 2 cpb while PCG improved a little to
about 0.7 cpb.
I do have a ~10-year-old Celeron NUC laying
around that I could use to test
older/lower-end hardware. I can also
publish the (admittedly very simple)
program I'm using.
It's also worth noting that cpb is still a
measure of average throughput not variance
or latency and while Go's buffered ChaCha8
implementation amortizes to 2 cpb, when the
32-element buffer exhausts, generating a
new number is much more expensive than the
previous 31 numbers. I wouldn't say the
performance is good enough for every use
case.
kbolino wrote 1 day ago:
Ok, I was able to figure out a few more
things. First of all, the benchmark
runner does not necessarily exploit the
parallelism of GOMAXPROCS out of the box.
Second, GOMAXPROCS seems to default to 1x
logical cores; I last ran it on a machine
where logical cores = 2x physical cores.
I adjusted the benchmark code to use
RunParallel and adjusted the parallelism
of each run.
Testing on Celeron J3455 @ 1.5 GHz (4
physical and logical cores) gave me PCG
at 1.2 cpb and ChaCha8 at 2.6 cpb with
cpu=1, but PCG stayed relatively constant
across cpu=1,2,4,8 (worst was 1.8 cpb)
while ChaCha8 slowed to 6.5 cpb at cpu=2
and 7.5 cpb at cpu=4 and cpu=8.
Back on my M1 Mac (8 logical and
physical? cores), both ChaCha8 and PCG
generally got better with more cores.
ChaCha8 got down to 0.76 cpb at cpu=4
(then regressed a bit at cpu=8) while PCG
got down to 0.26 cpb at cpu=8.
I don't think any of these results rule
ChaCha8 out completely, though again I'm
looking from the perspective of video
games, which generally monopolize a
machine while running.
pclmulqdq wrote 17 hours 21 min ago:
The important question to benchmark for
small buffer sizes isn't actually
cycles per byte, it's micro-ops per
byte. You are sort of getting there by
adding threads, but if you want to
measure micro-ops per byte by measuring
cycles per byte, your benchmarking code
should run a number of parallel
implementations of the generator on
each thread (and stick to 1 thread per
physical core, too). Each generator
will have a "roof" where more
generators per thread doesn't cost any
more in terms of cycles/byte. I am
assuming that for PCG, that roof is
around 4-ish on an old CPU, and may be
as high as 6 or 8 on your macbook,
while the roof for ChaCha will be close
to 1.
ChaCha exploits instruction-level
parallelism to get speed. PCG doesn't
- it has a chain of instructions that
must be executed sequentially. That
means that when the PCG generator
executes, it leaves gaps in the
instruction stream that can be filled
with other instructions for the game.
That means a slowdown in the game that
is more significant than what your
benchmark suggests.
I'm going to do this and write blog
about it (although I don't have a
macbook), so we may be able to compare
results.
kbolino wrote 16 hours 29 min ago:
Ok this makes sense. There are only 4
FP/SIMD units in the M1 and I'm
guessing just one in the Celeron.
I look forward to reading your blog
about this.
pclmulqdq wrote 1 day ago:
There are CSPRNG constructions based on AES that
would probably be appropriate, but they are still
a huge performance hit. PCG, Xorshift, Xoshiro,
and the like are all about 50x faster than the
fastest CSPRNGs in sustained throughput, and also
have smaller state and much less spinup time.
kibwen wrote 2 days ago:
> The "right" solution you describe sounds
overcomplicated and error-prone
It's not particularly. At program start-up, you seed
the original PRNG. Then, you generate N numbers from
the original PRNG and use those to seed N other PRNGs,
then throw away the original PRNG. You don't need to
think carefully about domains, you just create a new
PRNG for everything you need a random number for. This
makes your game easier to debug in a deterministic way,
because now reproducing the behavior of one specific
action that involves randomness no longer depends on
every other action that involves randomness.
ZeWaka wrote 2 days ago:
Just watched the video on this! It's definitely a cautionary tale of
having your random sources interact - applicable to so many important
systems.
I often find myself sharing the rng in my code for performance reasons,
but stories like this definitely make me pause.
iforgotpassword wrote 2 days ago:
I think I never used PRNG in any serious software, but it surprised
me as intuitively I would've assumed that using the same RNG in as
many places as possible would make it harder to perform such an
attack, because it would make it less likely you can observe enough
places at which it is updated, but this was a pretty impressive and
fun demonstration that this is false.
adra wrote 2 days ago:
Hi about pulling a sample of good random every N invocations to
still allow for fast PRNG but to ideally defeat these schemes.
Maybe use the real signals RNL value to seed the PRNG. Just a
thought.
IshKebab wrote 2 days ago:
Pretty much all serious software uses PRNG at some point. Unless
you mean you use CSPRNG, which is the easy fix.
iforgotpassword wrote 2 days ago:
Yeah it's obviously biased to the field you work in. And I'm
aware that libs im using use some form of randomness, be it for
uuid-gen, entropy for SSL or whatnot, but I seriously can't
remember the last time I called rand() and friends directly for
anything.
DIR <- back to front page