One of the ways to hide data in steganographic communication is to create messages that look random. To achieve this goal, an encryption function could be applied, but in covert communication, exchanging keys may be impossible or can expose secret data transmission. However, in the steganograpic scenario, information concealment is the primary goal and is valued much more than providing confidentiality, so encryption can support information hiding purposes in a way where confidentiality is not a priority. Moreover, a question arises of whether alternative cryptographic solutions, i.e., less costly than encryption, can achieve the same level of randomness. Considering the above, in this paper we propose an approach inspired by proof-of-work principles to transmit the cryptographic key along with the encrypted message, eliminating the need for the prior key exchange. In more detail, we explore a scenario where both the covert sender and receiver perform proof-of-work (called double proof-of-work). We implement the proposed solution and experimentally assess its security and key performance metrics, i.e., bandwidth, stealthiness, and robustness. The results obtained demonstrate the feasibility and effectiveness of such a scheme.