On 10/12/26 5:12 PM, Aaron Conole wrote:
> random_uint32() is a xorshift32 PRNG (see lib/random.c): it holds many
> properties including uniformity and reversibility, so recovering the
> internal state from any single observed output lets an attacker
> compute every other output of that (per-thread) stream, forward and
> backward. Using it for anything security-relevant is documented in
> random.c itself as inappropriate.
>
> Most NAT tuple selection does not call random_uint32() directly
> Instead, nat_get_unique_tuple() picks both the NAT address
> (get_addr_in_range()) and, in the common case, the NAT port
> (set_sport_range()/set_dport_range()) via nat_range_hash(), a
> deterministic hash of the flow tuple mixed with a single 32-bit value:
> ct->hash_basis. That basis was previously drawn once from
> random_uint32() at conntrack_init() time. Because it is a single,
> long-lived value on which every NAT address and default port choice
> depends, an attacker able to recover the xorshift state feeding that
> one random_uint32() call, e.g. by observing any other output drawn
> from the same per-thread PRNG stream elsewhere in the process, could
> predict every NAT tuple ovs-vswitchd will assign. In effect, it was
> derived from a shared, reversible state.
>
> Two narrower paths draw directly from random_uint32() per new
> connection rather than through the hash: the 'nat(...,random)' port
> path, and the retry offset used when the hash-selected port collides
> with an existing connection under range congestion. These are
> directly observable per-connection outputs.
>
> Fix this by drawing ct->hash_basis, and the two per-connection port
> paths above, from a cryptographic source: the recently added CSPRNG
> support in random.c which is a ChaCha20 based CSPRNG.
>
> Signed-off-by: Aaron Conole <[email protected]>
> ---
A different LLM had the following to say about this patch
(some parts seem reasonable to a human posting this, but not
fully validated):
────────────────────────────────────────
REVIEW: 22a8a9223 "conntrack: Use a cryptographic PRNG for NAT tuple selection."
────────────────────────────────────────
commit 22a8a92235271ab5ee7621c0f1b419bff54a9efb ("conntrack: Use a
cryptographic PRNG for NAT tuple selection.")
Author: Aaron Conole <[email protected]>
This patch adds a nat_random_uint32() helper backed by cs_random_uint32()
and uses it to seed ct->hash_basis in conntrack_init() and for the
NAT_RANGE_RANDOM port offset in nat_get_unique_tuple().
> - ct->hash_basis = random_uint32();
> + ct->hash_basis = nat_random_uint32();
The commit message says an attacker who recovers ct->hash_basis "could
predict every NAT tuple". Does changing where this 32-bit value comes
from actually stop that?
In the default path of nat_get_unique_tuple() (no NAT_RANGE_RANDOM, no
NAT_PERSISTENT), the hash output is used directly as the offset:
basis = (nat_info->nat_flags & NAT_PERSISTENT) ? 0 : ct->hash_basis;
hash = nat_range_hash(fwd_key, basis, nat_info);
[...]
} else if (basis) {
port_off = hash;
nat_range_hash() is a murmur-style hash_add()/hash_finish() over fields
the attacker already knows (both endpoints, the NAT min/max address and
port, dl_type, nw_proto, zone). Its only secret is the 32-bit basis.
A client that connects through SNAT to a server it controls sees the
translated address and port. With a full port range, each connection
leaks about 16 bits of nat_range_hash() output. Two or three of them
would be enough for an offline search over all 2^32 bases, and that
search never touches the PRNG.
After that, every hash-derived NAT tuple is predictable again, and so
are conn_key_hash() and the other users of the same basis. This
weakness predates the patch, but the commit message presents it as
fixed. Would a keyed PRF with a larger key, such as SipHash, or
per-connection randomness be needed to back up that claim? Otherwise,
could the commit message be narrowed to cover only the
NAT_RANGE_RANDOM path?
---
> +static uint32_t
> +nat_random_uint32(void)
> +{
> + return cs_random_uint32();
> +}
[...]
> - ct->hash_basis = random_uint32();
> + ct->hash_basis = nat_random_uint32();
random_uint32() could never return 0: random_init() keeps going until
it has a nonzero seed, and xorshift32 maps nonzero values to nonzero
values. cs_random_uint32() returns raw keystream bytes, so it can
return 0.
nat_get_unique_tuple() treats a basis of 0 as the NAT_PERSISTENT case,
and nat_range_hash() switches to its reduced input set on !basis:
if (!basis) {
hash = ct_addr_hash_add(hash, &key->src.addr);
If conntrack_init() draws 0, every non-persistent NAT flow would be
handled as persistent. Those flows would hash only the source address,
with no secret salt, for the life of the process. The chance is
2^-32 per start, but would it be worth redrawing when the value is 0?
---
> +/* NAT tuple selection (both the address/port hash basis and the
> + * fully-random port paths) must not be predictable from an observed
> + * random_uint32() output, so it must draw from a cryptographic
> + * source here instead of the general-purpose xorshift32 PRNG in
> + * random.c. */
> +static uint32_t
> +nat_random_uint32(void)
The name and comment describe ct->hash_basis as a NAT value only.
However, ct->hash_basis also salts conn_key_hash(), zone limit hashing,
the timeout policy hashing in conntrack-tp.c, and the ALG expectations.
Could the helper be renamed, or the comment updated, so it is clear
that this change affects every conntrack hash table and not just NAT?
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
