We develop a novel technique for authenticating physical documents by using random, naturally occurring imperfections in paper texture. To this end, we devised a new method for measuring the three-dimensional surface of a paper without modifying the document in any way, using only a commodity scanner. From this physical feature, we generate a concise fingerprint that uniquely identifies the document. Our method is secure against counterfeiting, robust to harsh handling, and applicable even before any content is printed on a page. It has a wide range of applications, including detecting forged currency and tickets, authenticating passports, and halting counterfeit goods. On a more sinister note, document identification could be used to de-anonymize printed surveys and to compromise the secrecy of paper ballots.