Anyone ever heard of a little thing called the Berne Convention? It's basically a big international copyright law stating, if an artistic/literary work is copyrighted in one nation, it is protected by international copyright laws by any and every country that signed the convention. Naruto is licensed in Japan. So by the convention, it's copyrighted in every single country that's signed the treaty.
Yaaaay for international copyright laws. Everything you've ever heard about international licensing not having any effect has been false. Hooray!
And on that note, the whole "legal vs. illegal" debate can stop.