ENTROPY: randomness metrics for byte samples

Data Structures
struct	N_ENTROPY_BIT
	per-bit statistics across a set of equal-length samples More...
struct	N_ENTROPY_POS
	per-position statistics across a set of equal-length samples More...

Functions
size_t	n_entropy_bits (const unsigned char *const *samples, size_t count, size_t sample_len, N_ENTROPY_BIT *out, size_t max_out)
	Per-BIT analysis of a set of equal-length samples.
double	n_entropy_chi_square (const unsigned char *data, size_t len)
	Chi-square statistic of the byte histogram against a uniform distribution over 256 values.
double	n_entropy_chi_square_p (double chi, size_t df)
	Upper-tail p-value of a chi-square statistic (Wilson-Hilferty).
size_t	n_entropy_longest_run (const unsigned char *data, size_t len)
	Length of the longest run of identical bits in the sample.
double	n_entropy_monobit (const unsigned char *data, size_t len)
	Fraction of set bits in the sample (0.0 .
size_t	n_entropy_positions (const unsigned char *const *samples, size_t count, size_t sample_len, N_ENTROPY_POS *out, size_t max_out)
	Per-POSITION analysis of a set of equal-length samples.
double	n_entropy_runs_p (const unsigned char *data, size_t len)
	Runs test over the sample's bit stream (NIST SP 800-22 style).
double	n_entropy_shannon (const unsigned char *data, size_t len)
	Shannon entropy of the byte sample, in bits per byte (0.0 .

Detailed Description

---

Data Structure Documentation

N_ENTROPY_BIT

struct N_ENTROPY_BIT

per-bit statistics across a set of equal-length samples

Examples

ex_entropy.c.

Definition at line 74 of file n_entropy.h.

Collaboration diagram for N_ENTROPY_BIT:

Data Fields
double	fraction	ones / sample count (0.5 is ideal)
size_t	ones	samples whose bit is set
double	p_value	two-sided p-value of z
double	z	z-score of the imbalance against a fair coin

N_ENTROPY_POS

struct N_ENTROPY_POS

per-position statistics across a set of equal-length samples

Examples

ex_entropy.c.

Definition at line 66 of file n_entropy.h.

Collaboration diagram for N_ENTROPY_POS:

Data Fields
double	chi_square	statistic against a uniform spread over the values seen
size_t	distinct	distinct byte values seen at this position
double	p_value	upper-tail p-value of chi_square
double	shannon	bits of entropy at this position (0 . . 8)

Function Documentation

n_entropy_bits()

size_t n_entropy_bits	(	const unsigned char *const *	samples,
		size_t	count,
		size_t	sample_len,
		N_ENTROPY_BIT *	out,
		size_t	max_out )

Per-BIT analysis of a set of equal-length samples.

The bit-level counterpart of n_entropy_positions: it finds a bit that is stuck, or biased, across the sample set, which is how a truncated counter or a fixed-prefix identifier shows up.

Parameters

samples	array of count pointers, each to sample_len bytes
count	number of samples
sample_len	length of every sample
out	array receiving one entry per bit (sample_len * 8 of them)
max_out	capacity of out

Returns

the number of bits written, or 0 on a bad argument

Definition at line 133 of file n_entropy.c.

References N_ENTROPY_BIT::fraction, N_ENTROPY_BIT::ones, N_ENTROPY_BIT::p_value, and N_ENTROPY_BIT::z.

Referenced by main().

Here is the caller graph for this function:

n_entropy_chi_square()

double n_entropy_chi_square	(	const unsigned char *	data,
		size_t	len )

Chi-square statistic of the byte histogram against a uniform distribution over 256 values.

Near 255 (the degrees of freedom) for random data; large for skewed data. Returns 0.0 for an empty/NULL sample.

Definition at line 64 of file n_entropy.c.

Referenced by main().

Here is the caller graph for this function:

n_entropy_chi_square_p()

double n_entropy_chi_square_p	(	double	chi,
		size_t	df )

Upper-tail p-value of a chi-square statistic (Wilson-Hilferty).

How surprising chi is for df degrees of freedom if the data really were uniform: near 1.0 means unremarkable, near 0.0 means the distribution is skewed far beyond chance. The Wilson-Hilferty cube-root transform is used rather than the exact incomplete gamma: it is accurate to a few thousandths for df >= 3, which is well inside what a verdict needs, and it is a dozen lines instead of a numerics library. Returns 1.0 for df == 0 or a non-positive statistic.

Definition at line 82 of file n_entropy.c.

Referenced by main(), and n_entropy_positions().

Here is the caller graph for this function:

n_entropy_longest_run()

size_t n_entropy_longest_run	(	const unsigned char *	data,
		size_t	len )

Length of the longest run of identical bits in the sample.

A long run in a token set is a stuck field; returns 0 for an empty sample.

Definition at line 183 of file n_entropy.c.

Referenced by main().

Here is the caller graph for this function:

n_entropy_monobit()

double n_entropy_monobit	(	const unsigned char *	data,
		size_t	len )

Fraction of set bits in the sample (0.0 .

. 1.0); 0.5 is the ideal for random data (the FIPS monobit idea). Returns 0.0 for an empty/NULL sample.

Definition at line 48 of file n_entropy.c.

Referenced by main(), and n_entropy_runs_p().

Here is the caller graph for this function:

n_entropy_positions()

size_t n_entropy_positions	(	const unsigned char *const *	samples,
		size_t	count,
		size_t	sample_len,
		N_ENTROPY_POS *	out,
		size_t	max_out )

Per-POSITION analysis of a set of equal-length samples.

An aggregate metric over concatenated tokens hides the finding that matters: a token can look random overall while its third character is always one of two values, or its counter half increments. This reports each byte position separately, so the caller can name WHICH position is predictable.

Parameters

samples	array of count pointers, each to sample_len bytes
count	number of samples (positions need several to mean anything)
sample_len	length of every sample
out	array receiving one entry per position
max_out	capacity of out

Returns

the number of positions written, or 0 on a bad argument

Definition at line 94 of file n_entropy.c.

References N_ENTROPY_POS::chi_square, N_ENTROPY_POS::distinct, n_entropy_chi_square_p(), N_ENTROPY_POS::p_value, and N_ENTROPY_POS::shannon.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

n_entropy_runs_p()

double n_entropy_runs_p	(	const unsigned char *	data,
		size_t	len )

Runs test over the sample's bit stream (NIST SP 800-22 style).

Counts the transitions between runs of equal bits and scores them against what a fair coin would produce. It catches what monobit cannot: a stream with exactly half its bits set but arranged as 0000...1111 passes monobit and fails this. Returns the two-sided p-value (near 1.0 is unremarkable), or 0.0 when the sample is empty or its monobit fraction is too skewed for the test to apply.

Definition at line 159 of file n_entropy.c.

References n_entropy_monobit().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

n_entropy_shannon()

double n_entropy_shannon	(	const unsigned char *	data,
		size_t	len )

Shannon entropy of the byte sample, in bits per byte (0.0 .

. 8.0). 0 means a single repeated value; 8 means a perfectly uniform byte histogram. Returns 0.0 for an empty/NULL sample.

Definition at line 29 of file n_entropy.c.

Referenced by main().

Here is the caller graph for this function: