It is in fact close to impossible to sneak a sub into the black sea, although it can be done. The waterway into the black sea (The Bosporus) is an extremely narrow channel and kind of shallow for a sub to get through. Any ship has to get permission way in advance to get through. And going underwater at periscope depth I think is the deepest you can go, you must stay behind a rather large ship in order to keep your wake trail out of vision. Not only this, but you gotta have the latest charts and information available to avoid wrecks, rocks, etc to get through successfully, not to mention a pro commander
.
All of this was outlined in a great book about Naval Warfare and politics I read, its called Nimitz Class. (Its about a Russian Kilo that sneaked through the Bosporus and sunk most of a US carrier battle group with a nuclear torpedo.) Very cool book I thought.