Definition 1: Let $x_n := 2 + \sum_{i=0}^n [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$. Clearly, we can build a Turing machine which, given $n$, will compute $x_n$. Also the $x_n$ converge to $x := 2 + \sum_{i=0}^\infty [1/2^i \mbox{ if $i$ encodes a proof that $\bf{ZF}$ is inconsistent, and 0 otherwise}]$.

So $x$ is a gnostic real, which is equal to 2 if and only if $\bf{ZF}$ is consistent.

Definition 2: For any gnostic real $x > 1$, let $M'_x$ be a Turing machine which takes an index $n$ of a Turing machine $N$ and an input $s$, simulates $N$ on $s$ for $|s|^x/\log(|s|)$ steps (this function is time-constructible, because $x$ is gnostic), and inverts the result. By the Recursion Theorem, we may choose $M_x$ to be $M'_x$ with a fixed index of $M_x$ as its first input. Then a standard argument (the Time Hierarchy Theorem) shows that $M_x$ has runtime $\mathcal O(|s|^y)$ precisely when $y\ge x$, and that $M_x$ is efficient for its language.

Therefore, for $x$ as in Definition 1, $M_x$ will run in time $\mathcal O(|s|^2)$ precisely if $x = 2$, ie if $\bf{ZF}$ is consistent; moreover this fact will itself be provable in $\bf ZF$. So [if $\bf ZF$ is consistent], $M_x$ is a [strongly and canonically] cryptic machine, and this fact will be provable in $\bf ZF + Con(\bf ZF)$.

However, $\bf ZF + \not Con(\bf ZF)$ proves that all languages in $\bf P$ are gnostic, since it proves that $\bf ZF$ proves that every language has runtime $\mathcal O(|s|^z)$ for every $z$. So it is undecidable in $\bf ZF$ whether any cryptic language exists.

To answer your second and third questions, the definition I gave above for $M_x$ is quite concrete; I don't think a full Turing machine description would be very illuminating. I suppose I could give a pseudo-code description of the program, though.