Most phone repair stores offer SIM unlocking, it's not illegal at all. In fact, a SIM lock is just a precaution used by carriers to ensure that you will not "stop" using their services all of a sudden, but nowadays it's obselete. In the past, you could have a phone for years without any upgrades and the assumption was that since it was locked, you will likely just continue the contract rather then buy a new expensive phone with the exact same features. Nowadays users think the other way around - as soon as the contract ends, I can get a new, snazzy phone cheap.
SIM locks are a thing of the past, and carriers need to start realizing that.