In this paper, we present a data hiding algorithm for binary document images. This algorithm is based on the Distance-Reciprocal Distortion Measure that is used to evaluate the amount of distortion caused by flipping a particular pixel in binary document images. The pixels that will cause less distortion after flipping are preferred candidates for flipping. We do the embedding by enforcing the odd-even features of non-uniform blocks and employ a 2-D shifting to provide security for tamper proofing and authentication. Experiments show that the watermark-embedded document image has good quality and tampering of content can be detected successfully.