Abstract: Bit-plane complexity segmentation (BPCS) steganography replaces bit-plane blocks of high complexity with secret data, providing large embedding capacity and good imperceptibility. By constructing a histogram of bit-plane block complexity, however, a security flaw in the BPCS method is revealed. Two striking discontinuities in the complexity histogram unambiguously announce the presence of BPCS-based hidden information. Furthermore, the complexity criterion used in data embedding can be estimated quite accurately, leading to a good estimation of the embedding capacity. The steganalytic technique proposed in this paper is equally effective against BPCS steganogrphy both in the spatial (temporal) domain and in the transform domain.