AbstractThe paper presents StegBlocks, which defines a new concept for performing undetectable hidden communication. StegBlocks is a general approach for constructing methods of network steganography. In StegBlocks, one has to determine objects with defined properties, which will be used to transfer hidden messages. The objects are dependent on a specific network protocol (or application) used as a carrier for a given network steganography method. Moreover, the paper presents the approach to perfect undetectability of network steganography, which was developed based on the rules of undetectability for general steganography. The approach to undetectability of network steganography was used to show the possibility of developing perfectly undetectable network steganography methods using the StegBlocks concept. Copyright © 2016 John Wiley & Sons, Ltd.