Ilya Maximets <[email protected]> writes:
> 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?
This is a subtle thing - any hash we choose becomes the attack point.
Actually, the ipv4 tuple space is quite small, and it is possible to
just brute force it. This doesn't solve the problem of port selection
via the hash - that is a separate problem to solve (I dunno what the
alternative sould be - maybe SipHash, but I don't know about the
properties it needs and whether it could be acceptable with truncation
due to the way NAT addresses are pulled, etc).
But it becomes a more difficult problem. The thing this patch does is
at least make it so that the rng being used for the hash basis can't
impact other parts of the system. I can rephrase the commit message to
describe that better.
> ---
>
>> +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.
This is a good difference to spot. I'll update the nat_random_uint32 to
a non-zero value. It shouldn't happen often.
> 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?
Sure.
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
