Digital watermarking of multimedia (e.g., audio, images, video, etc.) can be viewed as a communications problem in which the watermark must be transmitted and received through a 'watermark channel.' The watermark channel includes distortions resulting from attacks and may include interference from the original digital data. Most current techniques for embedding digital watermarks in multimedia (e.g., audio, images, video, etc.) are based on spread spectrum (SS), although the connection is not always explicit. Current analyses of the watermarking channel are typically limited to the additive white Gaussian noise (AWGN) channel. However, new channel distortions not considered in classical SS are now possible. This paper describes several such manipulations and focuses on signal re-indexing (i.e., re- ordering of samples). The re-indexing channel is shown to behave like a linear filter on average, and the optimal detector, which has linear complexity, is derived. The channel is studied further for the case of spatial direct-sequence SS watermarks. For the conventional detector, it can yield a probability of bit error (PE) of 0.5, the worst possible case. A linear prefilter or the optimal (maximum-likelihood can be used for re-synchronization and reduction of PE. Both methods are analyzed and compared with experimental results. These results include both synthetic data and standard test images and video.