Indeed, not only does (pre-Omarian Nebula, pre-Detapa Council coup, pre-Dukat coup, pre-Dominion War) the average Cardassian citizen know that the Obsidian Order exists, but the Cardassian elites want the average Cardassian to know the Obsidian Order exists. They want normal people on Cardassia living in constant fear of the Obsidian Order, believing that they're being watched at all times -- that way the people will be less likely to rebel against the corrupt oligarchy that ruled the Union.
Re: Star Trek Into Darkness. Nothing about that film contradicts Section 31's status as an illegal conspiracy within the Federation. Yes, Admiral Marcus implies to Kirk that it's legit -- but in the course of the film, we find out that they're secretly building a starship staffed by mercenaries who are not Starfleet officers, as part of an illegal plot by Marcus to provoke a war with the Klingons that will allow him to take over the Federation. So, no, I don't buy that Section 31 is a legitimate agency in the Kelvin Timeline either.
I'm not convinced the depiction of S31 in DIS constitutes a real retcon. I mean, the entire plot of the season revolves around an omniscient artificial intelligence feeding Starfleet officers falsified information to manipulate them. There's no reason not to imagine that Control was tricking Admiral Cornwall and the others into thinking S31 was legit so that it would be able to operate its own private army out in the open without Starfleet hunting them down.
Everything contradicts Sloan's claim that they're authorized. He cites a legally inactive document (again, citing the United Earth Starfleet Charter for the Federation Starfleet is like citing the February 1776 Massachusetts law authorizing the Massachusetts Naval Militia to justify the existence of a division of the United States Navy -- it's legal nonsense), whose relevant passage does not establish a military division with carte blanche (it only allows for leeway on officers' actions in times of crisis), and it is explicitly depicted as operating without authorization from or accountability to the Federation government. They even spy on the head of government! None of that is what a legitimate government agency does.
You want special operations and espionage storylines to satisfy your boner for worshiping security services? That's cool -- the Federation already has an intelligence agency capable of satisfying those boners for you: Starfleet Intelligence.
Section 31 is not the Federation CIA. It's the Federation KKK.