But it is not clear to me which app is.. Is the Play Store with gallery access privileges? Or is it a malware app installed by the user?
Discussion
It's the malware app. Typical Android malware like this asks for invasive permissions to then abuse them. Play Services doesn't provide apps permissions on their behalf.