Another and seemingly older interpretation of the name:
Oaks of a great size, firm and sound, have been taken out of a large moss on Bewick-Moor, called King‘s Moss, by the road from Chillingham to Alnwick, near a noted aperture in a freestone-rock, called Catherine‘s cave.
From ‘The Natural History and Antiquities of Northumberland‘, v1, by John Wallis (1769).
And for another version of the story about bold adventurers exploring the tunnel, it’s rather fun to see George Tate himself do the retelling, in The Border Magazine, November 1863.