Yeah, broaching is the way to go if doing a number of them. You start by boring a round hole and then a broaching machine pulls a broach through the hole. The broach is sort of a shaft with teeth. The broach teeth are in the shape of a square, but tapper ever bigger as you pull the broach through the hole. Each time a tooth passes through the hole it cuts the square bigger They make sockets that way (for the wratchet drive). It's how you get splines inside a gear or other part. I assume it's how you rifle a gun barrel too.

Someone I'm sure already has a square broach that will work. Have the blanks machined and then send them out for the broaching. Too bad it's such low quantities...costs more. It's a matter of finding one that will do a small job. There are plenty of shops listed on the web, but I'd look locally first to try and save the shipping.