91–100 of 100 posts
Earlier quoted context omitted.
Financial market prediction is where my mind went too.
Good luck with that. Financial markets are not pRNG's -- they are more like an adversary you are playing poker with. Think game theory, rather than pattern matching.
I'd like to see a neural net have a go at a DRBG, such as one using an HMAC/SHA256 and PBDKF2, a cryptographically strong pseudo-random bit generator. Is it possible there's something that analytic methods of this RFC didn't catch that a neural net could?
There's been over a decade of research into machine learning cryptanalysis. It's not a new idea.
Earlier quoted context omitted.
There's been over a decade of research into machine learning cryptanalysis. It's not a new idea.
If we knew everything we wouldn't be reading this website. Or do you already know everything and just like being dismissive?
Earlier quoted context omitted.
It would also work for PCG. You're simply modeling the PRNG and learning the internal state from outputs. It's even easier using Z3 or your own SAT solver. I've broken pretty much all non-crypto PRNGS using Z3, and it's trivial to do so. You simply model the PRNG in Z3, with unknown constants, plug in a few values from the output (or even parts of output, or even non-consecutives ones, anything you derive from them,…
I don't think this will work on PCG. "pcg32, which has state-space size of 2^127 (2^64 period × 2^63 streams) and produces 32-bit outputs." https://www.pcg-random.org/predictability.html That said, The PCG author does not recommend to use it for cryptography. "Although it is less trivial to predict than many mainstream generators, that does not mean it should be considered crypographically secure. Exactly how hard it…
Earlier quoted context omitted.
If I recall, something like 7 hand shuffles becomes indistinguishable from random. I'd guess a pro could get this level of mixing in a few shuffles
Yeah, but that's 7 shuffles of a single deck. Most casinos use 6 or 8 decks. They are certainly not shuffling 42+ times.
Earlier quoted context omitted.
Good luck with that. Financial markets are not pRNG's -- they are more like an adversary you are playing poker with. Think game theory, rather than pattern matching.
I was actually considering something known to be a relatively weak pRNG....card shuffling in a casino setting.
Earlier quoted context omitted.
Do you have a worked example of finding a PRNG's internal state that you could share? (Most people are unfamiliar with Z3 and other SMT solvers. Seeing a relevant worked example would be very illustrative.)
Yeah, I was considering posting one. I've lately switched to Z3 under C# since it's so easy to do things... If I get around to it tonight I'll make a post.
// Code to demonstrate finding the hidden seed of a PRNG with Z3
// Chris Lomont Oct 2021
// Answering this comment on Hacker News https://news.ycombinator.com/item?id=28886698
// Start by getting Z3, a theorem prover from Microsoft, via nuget. See https://github.com/Z3Prover/z3
using Microsoft.Z3;
using System;
// get a solution
ulong Solution(Context ctx, BoolExpr f, BitVecExpr seed)
{
Solver s = ctx.MkSolver();
s.Assert(f); // assert constraint into solver
if (s.Check() == Status.SATISFIABLE)
{
var m = s.Model;
Expr e = m.Evaluate(seed);
return ulong.Parse(e.ToString());
}
else
throw new Exception("Fatal error");
}
// simple PRNG, used in many old C libs
UInt32 next = 0x1234;
UInt32 rand()
{
next = next \* 214013 + 2531011;
return (next / 65536) % 32768;
}
void Test()
{
var R = new Random();
next = (uint)R.Next();
var start = next;
Console.WriteLine($"Starting seed {next:X8}");
using (var ctx = new Context())
{
// 32 bit vector type
Sort bv_type = ctx.MkBitVecSort(32);
// unknown seed - we will solve for this
BitVecExpr seed = ctx.MkBVConst("seed", 32);
// constants used in the PRNG
BitVecExpr c214 = (BitVecNum)ctx.MkNumeral("214013", bv_type);
BitVecExpr c253 = (BitVecNum)ctx.MkNumeral("2531011", bv_type);
BitVecExpr c65536 = (BitVecNum)ctx.MkNumeral("65536", bv_type);
BitVecExpr c32768 = (BitVecNum)ctx.MkNumeral("32768", bv_type);
// track the boolean to satisfy
BoolExpr be = ctx.MkTrue();
var next = seed; // start here
int pass = 0;
while(true)
{
++pass;
if (pass > 10) break;
// the sampled random
var r = rand();
BitVecExpr rndBV = (BitVecNum)ctx.MkNumeral(r, bv_type);
// make this code using Z3 variables
//next = next * 214013 + 2531011;
//return (next / 65536) % 32768;
next = ctx.MkBVAdd(ctx.MkBVMul(next, c214), c253);
var ret = ctx.MkBVURem(ctx.MkBVUDiv(next, c65536), c32768);
// add a constraint boolean for this "Z3 ret = returned value"
be = ctx.MkAnd(be, ctx.MkEq(ret, rndBV));
// get solution
var val = Solution(ctx, be, seed);
// todo - can check unique by adding "seed != soln" to the boolean and checking
Console.WriteLine($"{pass} : 0x{val:X8}");
if (val == start)
break; // done - can also break when shown unique
}
}
}
Test();Earlier quoted context omitted.
Yeah, I was considering posting one. I've lately switched to Z3 under C# since it's so easy to do things... If I get around to it tonight I'll make a post.
Here's a simple example finding a hidden seed. It takes around 1, 2, or 3 values in a row and finds the seed. You can adapt this to all sorts of breaking problems, but for some you'll have to learn more about SATs and be careful how you code things. Note the simple PRNG I chose doesn't reveal all the state, yet over time you can deduce all of it. // Code to demonstrate finding the hidden seed of a PRNG with Z3 // Chr…
Earlier quoted context omitted.
Is it potentially useful for something outside of cryptography? I was watching a video on speedrunning where they were gaming the RNG somehow to improve their times
Predictable bit streams that look random are useful for communications. Satellite navigation systems like GPS for instance use such streams where the whole idea is for a receiver to sync up on on the bitstream. An example where no one even cares exactly what the bitsream is can be found on motherboards where a bitstream is used to jitter the system clock to spread out any radio interference caused by the motherboard.
Earlier quoted context omitted.
I was actually considering something known to be a relatively weak pRNG....card shuffling in a casino setting.
Manual or modern automated shuffles in a casino are NOT weak. Casino owners and employees aren’t dumb. They actually understand the math involved quite well.
Having met a few casino owners, and many more game supervisors actually charged with understanding the math of the games to avoid exploitation, I can tell you this is patently false.