But they can instead make it illegal to use such software, which would not be an ex post facto law (it would only apply to uses of said software after the law was enacted).

IANAL though, so I digress.