It's actually easier than ever to ban encryption for messaging.
Would that stop determined people? No, but it's never been about that anyway. Just make the pool small enough and it becomes too difficult to use. (See PGP / email).
Also, if you genuinely legislate against encrypted messaging then it's easy to pick up on the relative handful of people who go outside the app stores to get encrypted messaging applications.
And it shouldn't come to technical solutions, we should have people challenge the notion that two people should never be allowed to share a private message, because that's why Rudd and the government is suggesting.