Hi,

The following vulnerability was published for openvswitch.

CVE-2019-25076[0]:
| The TSS (Tuple Space Search) algorithm in Open vSwitch 2.x through
| 2.17.2 and 3.0.0 allows remote attackers to cause a denial of service
| (delays of legitimate traffic) via crafted packet data that requires
| excessive evaluation time within the packet classification algorithm
| for the MegaFlow cache, aka a Tuple Space Explosion (TSE) attack.

https://arxiv.org/abs/2011.09107
https://sites.google.com/view/tuple-space-explosion
https://dl.acm.org/doi/10.1145/3359989.3365431
https://www.youtube.com/watch?v=5cHpzVK0D28
https://www.youtube.com/watch?v=DSC3m-Bww64

If you fix the vulnerability please also make sure to include the
CVE (Common Vulnerabilities & Exposures) id in your changelog entry.

For further information see:

[0] https://security-tracker.debian.org/tracker/CVE-2019-25076
https://www.cve.org/CVERecord?id=CVE-2019-25076

Please adjust the affected versions in the BTS as needed.

There's nothing I can do about this bug, I don't think it is useful to
keep it open forever.

1. No upstream fix exists. Zero commits, issues, or PRs in
openvswitch/ovs referencing the TSE attack ("tuple space explosion",
"flow expansion", or the CVE id). The paper (Ghali et al., ACM CCS '19)
was disclosed to the OVS security process in 2019, and upstream never
merged a patch — the master classifier and docs have no mitigation
whatsoever.

2. It's a design-level DoS, not a patchable bug: crafted flow patterns
explode the megaflow classifier's Tuple Space Search subtables, delaying
legitimate traffic. Any "fix" is architectural (limiting megaflow
caching = permanent performance trade-off), which upstream declined to do.

3. Debian's security tracker agrees: every suite is vulnerable/unfixed,
buster/bullseye <no-dsa> "Minor issue", bookworm/trixie <postponed> —
"Minor issue, revisit when fixed upstream". Nothing moved in 7 years
across any distro (Red Hat, SUSE, Ubuntu same).

What we've done in production, is that we're just monitoring of there's
too many of these to-be-classified packets, to react to a DoS. OVS is
just vulnerable to traffic attack, just like so many components, and
that's the only way to "fix" this.

Cheers,

Thomas Goirand (zigo)