« first day (4913 days earlier)      last day (28 days later) » 

12:24 PM
Do PRNG algorithms have pre-image resistance?
 
12:39 PM
That is, do they guarantee it is impossible to reverse-engineer the seed used to generate their output?
 
what is the best way to convert 1 into string "true" & 0 into string "false" ?
 
perehaps var_export((bool)$a, true)
but is there really a "best" way ?
 
https://3v4l.org/WjTZ6
not working
 
($a ? "true" : "false") is also simple
 
1:01 PM
o/
 
 
2 hours later…
3:00 PM
@QuolonelQuestions Best answer here probably is: Depends.
As an example, for Mt19937, Xoshiro256** and PcgOneseq128XslRr64 it's impossible to reverse the state (you probably mean state instead of seed) from a single output, as the state is larger than the output.
For consecutive outputs it's often possible to reverse the state.
 
We would just be doing single outputs
What's the distinction between state and seed?
 
For very simple LCGs a single output is sufficient to know the state, because they often directly return the inner state as their output.
 
@QuolonelQuestions Seed is effectively just the initial state.
A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation. The generator is defined by the recurrence relation: Xn+1=(aXn+c)modm{\displaystyle X_{n+1}=\left(aX_{n}+c\right){\bmod {m}}}where X{\displaystyle...
 
Right, so for my purposes, it's the same thing
I was just wondering whether it's "safe" to derive a (single) PRNG value from a secret that must not be revealed by the generated value
 
3:07 PM
@QuolonelQuestions What's your real-world use case there?
 
A voucher code, similar to an identifier, (that is private) and can be used to redeem the money associated with the voucher, and a public identifier that refers to the same voucher, but cannot be used to redeem it (shared with customer support personnel). We could either generate the public identifier independently, or just derive the public identifier from the private one, provided the algorithm guarantees pre-image resistance
From what you've said, it would seem we can generate the public ID from the private one, at least in terms of pre-image resistance. There is a secondary concern that the IDs could still collide
i.e. it's not known whether a given PRNG algorithm provides any guarantees that distinct seeds will always generate distinct (initial) output
 
You likely want a hash function then?
 
No, because converting a binary hash to a human-readable identifier is both non-trivial and unclear whether the various methods for doing so would violates their important properties, such as pre-image and collision resistance
For example, if our readable identifier has to be numeric (0-9), converting most hashes results in a LOT of digits, unless the hash is truncated. But if it's truncated, it may no longer guarantee collision resistance, and even if it isn't truncated, there's still no guarantee that mapping 0-255 onto 0-9 wouldn't result in a ton of new collisions anyway (I guess it almost certainly would)
 
> there's still no guarantee that mapping 0-255 onto 0-9 wouldn't result in a ton of new collisions anyway (I guess it almost certainly would)

It would not, if you implement it as a reversible transformation.
Because then it's just a different representation of the same thing.
 
It's going to involve some degree of truncation
Whether chopping off the end, or even dropping some bits per byte so converted
 
3:15 PM
No. base64 does exactly that: It encodes 3 bytes as 4 characters.
 
The identifier so converted from the average hash is just too long to be practical otherwise
 
And base16 (a.k.a. hex) encodes 1 byte as 2 characters.
 
Yes I am aware, but my point is that base64 encoding any hash (even md5) would be too long
And base64 is a luxury we most likely do not have
The dictionary is typically going to be numeric in the worst case, or alphanumeric (with one case only) at best, which is neither a very long dictionary to work with, nor is it divisible by a power of 2, so truncation is going to happen to (a) keep the code from being too long and/or (b) as part of the (irreversible) conversation algorithm
We're generally looking at base10 or base29. 29 comes from the removal of vowels and 0/1 from the set, to avoid generating (rude) words. i.e. BCDFGHJKLMNPQRSTVWXYZ23456789
Anyway, this is why I avoided getting into specifics, because they are just distractions
 
 
3 hours later…
5:52 PM
truncation would keep the relative properties of the hash (of course you'd loose entropy, but it's a linear reduction). So truncating a secure 256 bit hash down to say 16 bits would keep collision resistance within the 2^16 space.

This is in effect how bitcoin algorithm works. There's a target number of leading 0's in the hash that you have to "proof of work" to generate a hash. This is the same problem as truncating the hash to be the length of the target.

With what you showed as a problem set, you could treat a 512 bit hash function as a base 256 number 512 digits long, then converting
 
6:11 PM
(note: this only applies to strong hash functions, hash functions that have "near collisions" known and computable (such as sha0, md5, etc) would be drastically weakened)
 
 
2 hours later…
8:08 PM
And you could really aggressively truncate a "strong" hash without compromising its collision resistance?
Doesn't seem to make much sense to me
 
 
3 hours later…
11:04 PM
Also, how does this work? github.com/php/php-src/commit/…
I presume understanding this code is key to figuring out how one might conceivably convert a hash to an arbitrary character dictionary
If I'm reading it right, any leftover bits that do not fit into the source_length (because the source length is less than or equal to 8 bits) are just discarded in each iteration?
 
11:19 PM
@QuolonelQuestions you absolutely compromise it's collision resistance. Take a degenerate case. Let's say you truncate a 512 bit hash function to 8 bits. The original hash function should expect a 50% chance of 2 colliding values within about 2^256 unique inputs (birthday paradox). But an 8 bit truncation would only have 18 values to have the same 50% chance of a collision.
 
Right, that's what I thought....
 
yeah, you don't get entropy for nothing. However, it's worth noting that's not unique to the truncation. any 8 bit hash function would only require 18 values to have the same chance of collision
@QuolonelQuestions exactly
 

« first day (4913 days earlier)      last day (28 days later) »