I do not say "evidently" unadvisedly when I say that evidently the origin of 'let the cat out of the bag' considerably postdates 'the mists of time'. The date of the earliest recovered fossil of the latter phrase in OED is 1701:
And who see clearly thro' the Mists of Time, Those puzling Glooms where busy Mortals stray.
Ladies Defence, Mary Chudleigh, 1701. Emphasis mine; quote from OED collection.
However, a latter-day parting of those mists reveals an earlier fossil, dating from 1682:
And thus those Druides that formerly had dominion of the Britons Faith, become now to be helpers of their joy, and are become the leaders of the blind people in a better way, and unto a better hope; and held forth that Light which through Gods mercy hath continued in this Island ever since, through many Storms and dark Mists of time, until the present Noon-day.
An historical and political discourse of the laws & government of England, Nathaniel Bacon and John Selden, published 1682. Bolding mine.
Note that both authors of An historical and political discourse were dead by 1660, and thus that the "mists of time" must needs have preceded that date.
As mentioned, contemporary evidence dates 'let the cat out of the bag' to 1753, nearly a century after the mists of time parted for Bacon and Selden's "present Noon-day":
We hear from Rochester, a few Days past, there was held, at the Sign of the Drone in that City, a great Meeting of Pursers, Place Hunters, with Artificers of such Sort, to consider of inviting one or two Gentlemen to offer as Candidates to represent that City at the next General Election. It is thought in vain for any Gentleman to offer himself there until the Ad —— please to turn the Cat out of the Bag for them, which is not yet untied.
Caledonian Mercury, 27 December 1753 (paywalled).
The 1753 date is an earlier fossil than that unearthed from 1760 by Farmer and Henley, as referenced in 1890 in Slang and its analogues past and present:
- The Life and Adventures of a Cat, pr. 2s. 6d. Mynors. [We could have wished that the strange genius, author of this piece, had not let the cat out of the bag; for it is such a mad, ranting, swearing, caterwauling puss, that we fear no sober family will be troubled with her.]
The London magazine, or, Gentleman's monthly intelligencer, v 29, p 224, 1760.
Farmer and Henley remark the origin known to them, thus contributing what is the earliest evidence available concerning the origin of the 'let the cat out of the bag' phrase:
TO LET THE CAT OUT OF THE BAG, phr. (common). To reveal a secret; a variant with a slightly modified sense is TO PUT ONE'S FOOT IN IT. [This and the kindred phrase 'to buy a pig in a poke,' are said to have had their origin in the bumpkin's trick of substituting a cat for a young pig and bringing it to market in a bag. If the customer were wary THE CAT WAS LET OUT OF THE BAG, and there was no deal.]
Slang and its analogues past and present, John S. Farmer and W. E. Henley, 1890.
For my part, I uncovered no other origin story than that given by Farmer and Henley in 1890. Without evidence, the story that the origin of the phrase came from the practice of storing a cat-o-nine-tails in a bag is apocryphal and, because of its failure to evoke any other than unevidenced and fabulous sense consonant with the early meaning of 'let the cat out of the bag', barely credible.