README
¶
fisheryates
Pure-Go Fisher–Yates shuffle, derived from the Java F5 reference with an unbiased index-reduction fix. It produces the password-driven coefficient permutation that F5 uses.
Install
go get github.com/0verkilll/fisheryates
Sponsor
If this project is useful to you, please consider supporting its development:
License
Documentation
¶
Index ¶
- Constants
- Variables
- func GetLogger() logger.Logger
- func GetSupportedLocales() []string
- func RecoverDigits(sigma []int) ([]int, error)
- func SetLogger(l logger.Logger)
- func SetTranslator(translator TranslatorProvider)
- func TailOf(sigma []int, k int) []int
- type EarlyRejectResult
- type FisherYates
- func (fy *FisherYates) CompleteFromKnownHead(size int, random f5prng.RandomSource, knownHead []int) (*PermPair, error)
- func (fy *FisherYates) Generate(size int, random f5prng.RandomSource) ([]int, error)
- func (fy *FisherYates) GenerateInto(buf []int, size int, random f5prng.RandomSource) ([]int, error)
- func (fy *FisherYates) GenerateWithInverse(size int, random f5prng.RandomSource) (*PermPair, error)
- type JavaCompatdeprecated
- type PermPair
- type Permutator
- type ScanResult
- type TranslatorProvider
- type Unbiased
Constants ¶
const ( // MaxPermutationSize is the maximum allowed size for a permutation. // This prevents memory exhaustion attacks. At 100M elements with 8 bytes per int, // this allows up to ~800MB for a single permutation on 64-bit systems. // // Rationale: // - 100M * 8 bytes = 800MB (reasonable for modern systems) // - Prevents OOM attacks from malicious size values // - Users requiring larger permutations should process in chunks // // If a size exceeds this limit, Generate() and GenerateInto() return an error. MaxPermutationSize = 100_000_000 // 100 million elements )
Security limits to prevent resource exhaustion attacks. These constants define hard limits on input parameters to protect against malicious or accidental resource exhaustion when processing untrusted input.
Variables ¶
var ( // ErrSizeNegative is returned when size is negative. ErrSizeNegative = errors.New("fisheryates: size must be non-negative") // ErrSizeExceedsMax is returned when size exceeds MaxPermutationSize. ErrSizeExceedsMax = errors.New("fisheryates: size exceeds MaxPermutationSize") )
Sentinel errors for validation failures. Use errors.Is() to check error types.
var ErrKnownHeadTooLong = errors.New("fisheryates: knownHead length exceeds size")
ErrKnownHeadTooLong is returned when knownHead is longer than size.
Functions ¶
func GetSupportedLocales ¶
func GetSupportedLocales() []string
GetSupportedLocales returns the list of locales supported by this package.
It reads the list of embedded locale files and returns their locale codes. The returned array is sorted alphabetically for consistency.
If the embedded filesystem cannot be read (which should never happen in normal operation), this function returns a fallback array containing only "en-US" to ensure graceful degradation.
func RecoverDigits ¶
RecoverDigits recovers the complete Fisher-Yates digit sequence from a permutation σ that was produced by FisherYates.Generate (or the Forward field of a PermPair).
digit[i] is the pool index selected at FY step i — the value that would be computed as:
int(PRNG.NextInt()) % (N - i) (with Java signed-mod fixup)
This is the full "walk": the concrete sequence of N choices that drove the shuffle. Knowing the walk lets you:
- Reconstruct the exact PRNG outputs at each step (PRNG_int32[i] ≡ digit[i] (mod N−i); the residue narrows the int32 domain ~N−i-fold per step).
- Verify that two separately-seeded PRNG streams produced the same shuffle.
- Implement custom embedding / extraction schemes indexed by step index rather than permutation position.
To recover the walk from partial knowledge (only σ[0..K-1] known): you need the seed first, because the last K digits depend on the pool arrangement at step N−K, which itself depends on the first N−K digits. Use FisherYates.CompleteFromKnownHead to verify a candidate seed with your known head, then call RecoverDigits on the resulting Forward slice.
Time: O(N). Space: O(N).
func SetLogger ¶
SetLogger sets the logger for the fisheryates package. Pass nil to disable logging and reset to the default NopLogger. The logger is shared across all goroutines and is thread-safe.
func SetTranslator ¶
func SetTranslator(translator TranslatorProvider)
SetTranslator sets the global translator for this package. Pass nil to disable translations and use default English messages. The translator is shared across all goroutines and is thread-safe.
func TailOf ¶
TailOf returns the last k elements of sigma — a convenience for extracting the sigmaTail argument to EarlyRejectFromTail once you have a known-good permutation from a prior CompleteFromKnownHead call.
Types ¶
type EarlyRejectResult ¶
type EarlyRejectResult struct {
// Rejected is true if the candidate PRNG stream cannot have produced
// the expected tail positions. A rejected candidate can be discarded
// immediately — the rest of the permutation is guaranteed wrong.
Rejected bool
// StepsConsumed is the number of PRNG calls that were read.
// On rejection this is the step where the mismatch occurred (1-based).
// On acceptance it equals len(sigmaTail).
StepsConsumed int
}
EarlyRejectResult is returned by EarlyRejectFromTail.
func EarlyRejectFromTail ¶
func EarlyRejectFromTail(sigmaTail []int, size int, random f5prng.RandomSource) EarlyRejectResult
EarlyRejectFromTail is the fast-rejection oracle for seed brute-forcing.
Background ¶
The Fisher-Yates shuffle settles positions from RIGHT to LEFT:
PRNG call 0 → digit[0] → settles σ[N-1] (1 call to check) PRNG call 1 → digit[1] → settles σ[N-2] (2 calls to check) … PRNG call K → digit[K] → settles σ[N-1-K] PRNG call N → digit[N] → settles σ[0] (ALL N calls to check)
If you know the TAIL of σ (σ[N-K..N-1]), you can verify or reject a candidate PRNG stream after just K calls — ~N/K times faster than a full run. For N=240 000 and K=32, that is a 7 500× speed-up for rejected candidates. Since the probability that a wrong candidate passes K independent checks is ≈ 1/N^K ≈ 0, the survivors are almost certainly correct.
Contrast with CompleteFromKnownHead ¶
CompleteFromKnownHead checks σ[0..K-1] (the HEAD). The head is settled LAST, so all N PRNG calls must be read first. Use it when you need the full permutation or when the head is all you have.
EarlyRejectFromTail checks σ[N-K..N-1] (the TAIL). The tail is settled FIRST; each mismatch aborts after i+1 calls. Use it as a cheap pre-filter before the full CompleteFromKnownHead.
Parameters ¶
- sigmaTail: the last len(sigmaTail) elements of σ in order, i.e. sigmaTail[0]=σ[N-K], …, sigmaTail[K-1]=σ[N-1]. Typically K=1 is enough for a 240 000-element shuffle (false-positive rate ≈ 1/240 000 per candidate). K=8 gives ≈ 1/240 000^8.
- size: the total permutation length N.
- random: a freshly seeded PRNG for the candidate password. On rejection random has been read StepsConsumed times. On acceptance random has been read len(sigmaTail) times and is positioned for a subsequent CompleteFromKnownHead call (re-seed first) or further PRNG reads.
EarlyRejectFromTail does not validate that sigmaTail is a valid subset of [0,N); the caller is responsible for that.
type FisherYates ¶
type FisherYates struct{}
FisherYates implements the Fisher-Yates shuffle using the Java reference algorithm — the same biased-modulo reduction used by the F5.jar / Android PixelKnot embed pipeline.
Default semantics (since fisheryates v2) ¶
This permutator is byte-compatible with the reference Java F5 implementation: the embed and extract sides agree on the shuffle order on every artifact produced by F5.jar, the original Java F5 standalone, and the Android PixelKnot app (e.g. sample.jpg). If you are decoding any of those, the default constructor NewFisherYates is what you want.
Algorithm ¶
Initialize perm = [0, 1, 2, ..., size-1]
For maxRandom = size; maxRandom > 0; maxRandom-- :
var2 = int(NextInt()) // 4 PRNG bytes, sign-extended
idx = var2 % maxRandom
if idx < 0 { idx += maxRandom } // Java's signed-mod fixup
Swap perm[idx] with perm[maxRandom-1]
The plain `int(NextInt()) % maxRandom` reduction carries a small modulo bias toward low indices — about maxRandom / 2^31, which is statistical noise for typical F5 sizes (< 0.005% at maxRandom = 1e5). For new code that wants strictly-uniform draws, use NewUnbiased instead.
Determinism and concurrency ¶
The struct is stateless. Generate / GenerateInto calls on the same instance are safe to run concurrently as long as each call uses its own f5prng.RandomSource (sources are documented as not thread-safe).
Same seed ⇒ same permutation, always.
Migration from earlier versions ¶
In versions prior to v2, NewFisherYates returned a strictly-uniform (rejection-sampled) shuffle. Code that relied on that behaviour should switch to NewUnbiased:
// before v2: p := fisheryates.NewFisherYates() // v2+ (preserve unbiased behaviour): p := fisheryates.NewUnbiased()
Code that decodes PixelKnot / F5.jar artifacts should use the default (it now works out of the box; previously it required the now-deprecated NewJavaCompat).
func (*FisherYates) CompleteFromKnownHead ¶
func (fy *FisherYates) CompleteFromKnownHead(size int, random f5prng.RandomSource, knownHead []int) (*PermPair, error)
CompleteFromKnownHead generates the full σ and σ⁻¹ and optionally validates a known prefix of σ.
Parameters:
- size: total permutation length N (>= 0, <= MaxPermutationSize)
- random: PRNG source pre-seeded by the caller
- knownHead: the caller's known values of σ[0..len(knownHead)-1]; pass nil (or an empty slice) to skip validation
Typical F5 usage: the caller knows the first K shuffled coefficient positions from a partially decoded stego image, passes them as knownHead, and uses PermPair.HeadMatch to confirm the candidate PRNG seed before trusting the rest of the permutation. On a match, PermPair.Forward completes the full sequence and PermPair.Inverse provides the extraction map.
The reverse-digit theorem guarantees correctness of Inverse:
FY = T_{N-1} ∘ ⋯ ∘ T_0 (each T_i is a transposition, self-inverse)
FY⁻¹ = T_0 ∘ ⋯ ∘ T_{N-1} (same swaps, reversed order)
Memory cost: 3 × size × 8 bytes (digits buffer + Forward + Inverse).
func (*FisherYates) Generate ¶
func (fy *FisherYates) Generate(size int, random f5prng.RandomSource) ([]int, error)
Generate produces a Java-bias-compatible permutation of [0, size). Returns an empty slice for size == 0; an error for size < 0 or size > MaxPermutationSize.
func (*FisherYates) GenerateInto ¶
func (fy *FisherYates) GenerateInto(buf []int, size int, random f5prng.RandomSource) ([]int, error)
GenerateInto produces a Java-bias-compatible permutation of [0, size) into the supplied buffer. The buffer is grown if it cannot hold size elements; the returned slice may share storage with buf or be a fresh allocation.
This is the zero-allocation variant for hot paths (e.g. password brute-force) where the caller pools permutation buffers across calls.
func (*FisherYates) GenerateWithInverse ¶
func (fy *FisherYates) GenerateWithInverse(size int, random f5prng.RandomSource) (*PermPair, error)
GenerateWithInverse produces the complete σ and σ⁻¹ in a single PRNG pass.
Compared to FisherYates.Generate followed by a separate O(N) inversion loop, this eliminates one allocation and one full scan when both directions are needed (e.g. an F5 embed pass followed by an extract pass over the same permutation).
The PRNG is consumed byte-for-byte identically to FisherYates.Generate, so the returned Forward slice is always equal to what Generate would return for the same seed and size.
type JavaCompat
deprecated
type JavaCompat = FisherYates
JavaCompat is a deprecated alias for FisherYates, retained for source compatibility with v1.x code that explicitly opted into Java-biased shuffling via NewJavaCompat when the default was rejection-sampled.
As of v2, FisherYates is itself the Java-biased default, so JavaCompat is now redundant. New code should use FisherYates / NewFisherYates directly.
Deprecated: use FisherYates (the package default since v2).
type PermPair ¶
type PermPair struct {
// Forward is σ: the shuffled permutation.
// Forward[i] is the original index of the element placed at shuffled position i.
// Apply it to map original-order data into shuffled order:
// shuffled[i] = original[Forward[i]]
Forward []int
// Inverse is σ⁻¹: the extraction map.
// Inverse[i] is the shuffled position of original element i.
// Apply it to recover original order from shuffled data:
// original[i] = shuffled[Inverse[i]]
Inverse []int
// HeadMatch reports whether every element of the knownHead argument to
// [FisherYates.CompleteFromKnownHead] matched the corresponding element
// of Forward. Always true when knownHead was nil or empty.
HeadMatch bool
// MatchCount is the number of knownHead positions that matched Forward.
// Equals len(knownHead) when HeadMatch is true.
MatchCount int
}
PermPair holds both σ and σ⁻¹ of a Fisher-Yates shuffle produced in a single PRNG pass via the reverse-digit theorem. Obtain one from FisherYates.GenerateWithInverse or FisherYates.CompleteFromKnownHead.
func CompleteFromKnownHead ¶
func CompleteFromKnownHead(size int, random f5prng.RandomSource, knownHead []int) (*PermPair, error)
CompleteFromKnownHead is a package-level shorthand that avoids a type assertion when callers only need PermPair and do not hold a FisherYates instance. Semantics are identical to FisherYates.CompleteFromKnownHead.
func GenerateWithInverse ¶
func GenerateWithInverse(size int, random f5prng.RandomSource) (*PermPair, error)
GenerateWithInverse is a package-level shorthand for FisherYates.GenerateWithInverse.
type Permutator ¶
type Permutator interface {
// Generate creates and returns a permutation of integers from 0 to size-1.
// The permutation is determined by the provided RandomSource, which must
// be properly seeded before calling this method.
//
// The returned slice contains each integer from 0 to size-1 exactly once,
// arranged in a pseudo-random order determined by the RandomSource.
// The same RandomSource state must always produce the same permutation.
//
// Parameters:
// size - The number of elements in the permutation (must be >= 0)
// random - The RandomSource used to generate the permutation order
//
// Returns:
// A slice of size integers containing a permutation of [0, size-1]
// An error if size is negative or exceeds MaxPermutationSize
//
// Example:
// Generate(5, seededRandom) might return [2, 4, 0, 3, 1], nil
Generate(size int, random f5prng.RandomSource) ([]int, error)
// GenerateInto generates a permutation into the provided buffer.
// This is a zero-allocation variant that reuses an existing buffer.
// The buffer will be resized if needed to fit 'size' elements.
//
// Parameters:
// buf - Reusable buffer (will be resized if needed)
// size - The number of elements in the permutation (must be >= 0)
// random - The RandomSource used to generate the permutation order
//
// Returns:
// The buffer containing the permutation (may be reallocated if too small)
// An error if size is negative or exceeds MaxPermutationSize
GenerateInto(buf []int, size int, random f5prng.RandomSource) ([]int, error)
}
Permutator defines the interface for generating permutations of integers. This abstraction follows the Single Responsibility Principle by focusing solely on permutation generation, and the Dependency Inversion Principle by depending on the RandomSource abstraction rather than concrete implementations.
The interface supports both allocating and zero-allocation variants to enable performance optimization in hot paths.
func NewFisherYates ¶
func NewFisherYates() Permutator
NewFisherYates returns a Permutator that reproduces Java's reference biased Fisher-Yates shuffle (the F5/PixelKnot wire format).
See FisherYates for the algorithm, determinism guarantees, and the migration note for callers upgrading from versions where this constructor returned the rejection-sampled variant.
func NewJavaCompat
deprecated
func NewJavaCompat() Permutator
NewJavaCompat returns a Java-bias-compatible permutator. It is identical to NewFisherYates in v2 and later.
Deprecated: use NewFisherYates. JavaCompat is retained only so existing call sites continue to compile.
func NewUnbiased ¶
func NewUnbiased() Permutator
NewUnbiased returns a Permutator that uses rejection sampling for strictly uniform shuffles. See Unbiased for trade-offs vs. the default FisherYates.
type ScanResult ¶
type ScanResult struct {
// Index is the position of the matching candidate in the input slice.
Index int
// Pair holds the complete σ (Forward) and σ⁻¹ (Inverse) for the
// matching candidate, produced in a single PRNG pass via the
// Reverse-Digit Inverse Theorem.
//
// Pair.Forward[i] = original coefficient index at embed position i
// Pair.Inverse[i] = embed position of original coefficient i
//
// These are all N elements — the complete walk.
Pair *PermPair
}
ScanResult is returned by ScanCandidates when a match is found.
func ScanCandidates ¶
func ScanCandidates( ctx context.Context, size int, knownHead []int, candidates []f5prng.RandomSource, workers int, ) (ScanResult, bool)
ScanCandidates runs CompleteFromKnownHead against each candidate PRNG in parallel and returns the first (and in practice only) candidate whose first len(knownHead) positions of σ match knownHead exactly.
Typical F5 usage ¶
You have N = number of non-zero AC DCT coefficients, knownHead = the first K embed positions of σ (σ[0..K-1]) observed from the stego image, and a list of candidate PRNG sources — one per candidate password, each freshly seeded.
ScanCandidates tries all candidates concurrently. The match is cryptographically certain: for K=32 and N=240 000, the probability that a wrong candidate passes is ≈ (1/N)^32 ≈ 0. The matching ScanResult gives you the complete walk (Pair.Forward, all N elements) and the extraction map (Pair.Inverse) without any further PRNG work.
Parameters ¶
- ctx: cancellation; cancelled after the first match to stop remaining workers.
- size: total permutation length N.
- knownHead: σ[0..len(knownHead)-1] that the correct candidate must reproduce.
- candidates: one RandomSource per candidate, freshly seeded. Each source is consumed and cleared by this call; do not reuse them.
- workers: goroutine concurrency (0 = len(candidates), i.e. all at once). For 1340 candidates on a modern CPU, workers=8 is a good default.
Returns (result, true) on match, (zero, false) if no candidate matches.
type TranslatorProvider ¶
type TranslatorProvider interface {
// Translate returns the translated string for the given key.
Translate(key string) string
// TranslateWithArgs returns the translated string with format arguments.
TranslateWithArgs(key string, args ...interface{}) string
// HasKey returns true if the translation key exists.
HasKey(key string) bool
// SetLocale changes the current locale.
SetLocale(locale string)
// GetLocale returns the current locale.
GetLocale() string
}
TranslatorProvider defines the interface for translation providers. This allows loose coupling - the package works with or without i18n. The interface matches github.com/0verkilll/i18n.Translator.
func GetTranslator ¶
func GetTranslator() TranslatorProvider
GetTranslator returns the global translator, or nil if not set.
func NewTranslator ¶
func NewTranslator(locale string) (TranslatorProvider, error)
NewTranslator creates a new translator configured for the fisheryates package. If locale is empty, it will auto-detect from environment variables. The translator uses embedded locale files and the i18n package for translation.
type Unbiased ¶
type Unbiased struct {
// contains filtered or unexported fields
}
Unbiased implements the Fisher-Yates shuffle with strictly uniform draws via rejection sampling over the 31-bit positive int32 range.
When to use ¶
You are creating new artifacts and want statistically unbiased permutations. The default FisherYates (which matches Java's biased reference) carries a tiny modulo bias toward low indices — about maxRandom / 2^31 (≈0.005% at size 1e5, ≈4.7% at size 1e8). Bias is irrelevant for steganographic shuffling, but real for cryptographic or simulation use.
You need the Unbiased.Rejections counter for diagnostics.
For decoding any artifact embedded by the reference Java F5 implementation (F5.jar, PixelKnot, Android port), use the default FisherYates which reproduces Java's biased modulo byte-for-byte.
Algorithm ¶
Initialize perm = [0, 1, 2, ..., size-1]
For maxRandom = size; maxRandom > 0; maxRandom-- :
Repeat: u = uint32(NextInt()) & 0x7FFFFFFF
until u < (2^31 - 2^31 % maxRandom)
idx = u % maxRandom
Swap perm[idx] with perm[maxRandom-1]
Determinism per seed is preserved (same seed ⇒ same permutation). Rejected draws are counted in Unbiased.Rejections.
func (*Unbiased) Generate ¶
Generate produces a strictly-uniform permutation of [0, size) using rejection sampling. See Unbiased for the algorithm and trade-offs vs. the Java-biased default.
func (*Unbiased) GenerateInto ¶
GenerateInto is the buffer-reusing variant of Unbiased.Generate.
func (*Unbiased) Rejections ¶
Rejections returns the cumulative number of uniform-rejection retries performed by this permutator across all Generate/GenerateInto calls.
This is intended for diagnostics: if the value grows faster than roughly size * (maxRandom / 2^31) per call, something is likely wrong with the RandomSource. In typical F5 usage (maxRandom <= MaxPermutationSize, i.e. <= 1e8) the expected rate is well under 5% of draws.
Source Files
Directories