It could be sent in the clear, although since the point was to apply it to every encrypted message, that would likely already have been redundant with having or

It could be sent in the clear, although since the point was to apply it to every encrypted message, that would likely already have been redundant with having originally been encrypted. Just consider it part of the decryption algorithm itself instead: step 1, attach warning text, step 2, initialize decryption state and decrypt.