Summary: Information hiding techniques allow a player to hide secret information in some innocent-looking document. In this paper we present a novel approach to information hiding. We investigate the possibility of embedding information using the intrinsic entropy of some classes of cover-documents. In particular we provide algorithms for embedding any binary string in an image mosaic (i.e. an image consisting of a mosaic of smaller images). The algorithms presented allow different levels of security for the information hidden in the cover-document. We also show some techniques to reduce the amount of information the users have to secretly store.