Attachments are a type of post, and a post can only have a single parent, that’s why it’s not natively possible to have an attachment associated with multiple posts- there is no mechanism for many-to-many associations. There are several ways to solve this, but how simple it is depends on your skill level or willingness to depend on plugins.
For plugins, there’s File Gallery, and Advanced Custom Fields, probably others. Otherwise a couple of custom solutions would be to use post meta data to store references to attachments for a post, and/or a taxonomy to “tag” images for each unique gallery you want them associated with along with some meta data for ordering them.
Here is a thread on WordPress Hackers with an explanation from the lead developer and some possible solutions.