So to forbid washing fish at a faucet in a national park... you literally do have to make a federal law (or a regulation with the force of federal law).
This is also why they have their own law-enforcement agency (the United States Park Police): Congress was, for a very long time, reluctant to authorize a general federal police force, so many agencies have their own specific police force operating solely within that agency's jurisdiction. It also creates fun inter-jurisdictional issues since the U.S Capitol building has its own separate police force, but the Capitol building is on the National Mall, which is Park Police territory.
The issue here is that the statute authorizing criminal penalties covers a whole range of national park regulations, some of which clearly merit stiff penalties, and some of which are just about washing fish safely.