Field of Invention
The present invention relates to document security. In particular, it describes a method for using the characteristic grain structure of a paper and public/private key encryption to protect the integrity of machine-printed paper documents.
Prior Art
Given a printed paper document, it is often desirable or necessary to reliably ascertain one or more of the following facts regarding the document: (1) the physical device which printed the document contents onto the paper, (2) the individual(s) or organization which issued the document, and (3) whether the document is printed on the original paper used by the issuing entity. Since items (1) and (2) describe the document's source, we refer to them collectively as the document's “Source ID.” Ascertaining item (3) implies that a unique, identifying signature can be derived for the paper on which the document is originally printed. We refer to this identifying signature hereafter as the “paper signature.” We define “document certification” as the process of associating a Source ID and a paper signature with a printed paper document. We define “document authentication” as the process of extracting the Source ID and paper signature from a paper document, and verifying their validity. We define “document security” as the combined problems of document certification and document authentication.
The principle challenge for document security system is to prevent or detect counterfeiting attacks. We define a “counterfeiting attack” as any process having the following goal: to falsely attribute a specific paper document to a specific document source (i.e., person, organization, or printing device). Note that a paper document consists of two items: a specific piece of paper and specific information which is printed on that piece of paper. Therefore, a paper document is counterfeit if either the printed information or the paper on which the information is printed (or both) did not originate from the claimed document source. The document's Source ID and paper signature must be associated with the document in a way which protects the integrity of both pieces of information from counterfeiting attacks.
Before discussing prior art in the area of document security, it is instructive to classify the possible modes of counterfeiting attack in order to evaluate how well prior approaches protect against them. It is useful to classify counterfeiting attacks into two broad types: Copy Attack and Spoofing Attack. We define these terms as follows:    1. Copy Attack: In this form of attack, a counterfeiter obtains a document containing valid Source ID information and attempts to transfer the Source ID from the original paper to a new piece of paper. The new paper document may contain arbitrary printed content. It can be an exact reproduction of the original document, a modified reproduction, or a document with completely different content. The important point is that rather than attempting to directly generate a Source ID encoding for the counterfeit document, the counterfeiter transfers a valid Source ID encoding from an existing document. This form of counterfeiting attack therefore does not rely on an understanding of how the Source ID is encoded (the Source ID could even be encrypted and therefore unreadable to the counterfeiter)—it only requires a means of accurately reproducing the Source ID encoding in the counterfeit document.    2. Spoofing Attack: In this form of attack, the counterfeiter attempts to directly construct (rather than transfer) a Source ID encoding which falsely attributes a document to a third party (that is, without the third party's permission or cooperation). The counterfeiter might do this by using a legitimate apparatus for generating and printing the Source ID encoding, but with modifications which permit the counterfeiter to attribute the document to a third party.
The remainder of this section summarizes prior art in document security and evaluates the effectiveness of prior approaches in detecting various forms of Copy and Spoofing Attacks.
Digital Watermarking Approaches
A large body of prior art in document authentication focuses on “digital watermarking” of printed documents. A recent and representative example is U.S. Pat. No. 6,823,075 (Perry). This patent contains an extensive summary of prior art in digital watermarking.
A digital watermark is a signal which is added to the printed contents of the paper document. The watermark signal contains information testifying to the source and authenticity of the document. Document authentication consists of reading the watermark signal from a paper document and checking its content. If the watermark is not found or is not in the proper format, the document is rejected as counterfeit. The watermark therefore functions as the paper signature and as a carrier of the document's Source ID.
Digital watermarking attempts to prevent certain forms of counterfeiting by making it difficult to reproduce a valid watermark in counterfeit documents. Reproducing the watermark could involve explicitly reading the watermark from a document and then reprinting it in a counterfeit document. The watermark signal could be reproduced in a pixel-per-pixel fashion or it could be modified if the counterfeiter was capable of decoding the signal and generating a new signal. Digital watermarking techniques try to prevent this form of attack by making the watermark signal difficult to detect (e.g., using spread-spectrum techniques to distribute the signal energy in the frequency domain in some psuedo-random but reproducible fashion).
Assuming this deters a counterfeiter from explicitly reading the watermark signal, a counterfeiter could still try to reproduce the document while preserving the watermark. This would involve scanning the document using sufficient optical resolution to capture most of the energy in the watermark signal and then reprinting the scanned image at high resolution. Digital watermarking techniques try to prevent this form of attack by making the watermark signal “fragile” so that copy attempts degrade the watermark signal energy in some way that is detectable to an authentication device.
Clearly, digital watermarking is focused on deterring Copy. Attacks. The assumption is that the Source ID information contained in a correctly-formatted watermark is always valid and that the only security problem is to prevent the watermark from being illegally transferred from a valid original document to a counterfeit document. As noted above, this is not the only form of counterfeiting attack. Specifically, digital watermarking techniques do not address the threat of Spoofing Attacks in which a watermark is correctly generated and rendered but contains counterfeit Source ID information, falsely attributing the document to a third party source. A Spoofing Attack could be carried out using a valid watermarking apparatus to generate a watermark which contains information attributing the document to a third party without that party's permission or participation. The watermark signal itself does nothing to prevent this scenario since it is only the carrier of the falsified Source ID information. Additional system functionality beyond the watermarking technique is clearly required to prevent false Source ID information from being inserted into the watermark.
The ability of digital watermarking to deter Copy Attacks is also limited because it depends critically on preventing the watermark signal from being illegally transferred to another piece of paper. Preventing this form of transfer is necessary because the watermarking signal is not intrinsic to the paper on which it is printed—i.e., the same signal could be legitimately applied to any sheet of paper. If the signal encoded intrinsic properties of the paper instead, it would not be necessary to keep the watermarking signal hidden or fragile. The use of a non-intrinsic signal for the paper signature therefore introduces a potential security hole. The existence of a legitimate apparatus to read the watermark signal implies there is some finite optical resolution at which sufficient energy of the watermark signal can be captured by an imaging device. If the captured image can be printed at adequate resolution to preserve the watermark signal energy, then the watermark signal can indeed be transferred from one piece of paper to another, resulting in a successful Copy Attack.
Moiré Effect Approaches
Another set of document authentication techniques in the prior art focuses on using moiré effects to give a paper document a unique signature. A recent and representative example is U.S. Pat. No. 6,819,775 (Amidror, Hersch). This patent provides a detailed summary of prior art in moiré-effect-based approaches. Other related patents and published patent applications by Amidror and Hersch are: U.S. Pat. Nos. 6,249,588, 5,995,638, U.S. Pat. Application No. 20040001604, and U.S. Pat. Application No. 20020012447.
A moiré pattern is an interference pattern created when two grids are overlaid at an angle, or when they have slightly different mesh sizes. The use of moiré patterns for document authentication is similar to the use of digital watermarking. As in digital watermarking, a signal is added to the document contents which will produce a moiré pattern when superimposed in some manner with another signal. Authenticating a document consists of viewing it through an appropriate apparatus which will superimpose the two patterns and create a visible, specific moiré pattern if the document is valid. Absence of the moiré pattern or the presence of an unexpected moiré pattern indicates a counterfeit document. As indicated in U.S. Pat. No. 6,819,775 (Amidror, Hersch), the moiré pattern can contain document Source ID information. The embedded signal to produce the moiré pattern therefore functions as both the paper signature and a carrier for Source ID information. This is analogous to the role of the watermarking signal in digital watermarking approaches.
As with digital watermarking, a key goal in moiré pattern approaches is preventing the signal from being easily reproducible or transferable by a counterfeiter. Specifically, U.S. Pat. No. 6,819,775 (Amidror, Hersch) makes the following claim:
The fact that moiré effects generated between superposed dot-screens are very sensitive to any microscopic variations in the screened layers makes any document protected according to the present invention practically impossible to counterfeit, and serves as a means to distinguish easily between a real document and a counterfeited one.
Assuming this particular claim is true, moiré-effect-based approaches have the same fundamental limitation as digital watermarking approaches: they are designed to prevent Copy Attacks and do nothing to address Spoofing Attacks. The signal used to generate the moiré pattern is only a carrier of the Source ID information and cannot be used to detect whether that information is valid or falsified to begin with. There is nothing in the moiré technique itself which prevents false Source ID information from being added to a document using a valid moiré-capable printing apparatus.
As with digital watermarking, the moiré techniques form a paper signature by embedding a non-intrinsic signal in the paper document. They are therefore subject to the same limitations on Copy Attacks noted above for digital watermarking techniques. While both techniques make Copy Attacks difficult for technically unsophisticated counterfeiters using conventional reproduction devices, a Copy Attack could theoretically succeed if greater expertise and more sophisticated imaging and reproduction equipment are brought to bear to transfer the non-intrinsic signal from one piece of paper to another.
Digital Signature Approaches
A number of techniques in the prior art attempt to adapt well-known public-key encryption algorithms (such as the RSA algorithm) for document authentication. These approaches all exploit the fact that a sequence of digital bits can be “digitally signed” by encrypting it with the private key of an issuing party to produce a “digital signature.” The digital signature resulting from the encryption is appended to the original “clear-text” message to form a composite message. Authentication is accomplished by decrypting the digital signature with the public key of the party to whom the message is attributed. This public key can be included by the sender in the clear-text portion of the composite message. The decrypted message is then compared to the clear text message. If the two messages are identical, two conclusions can be drawn: (1) the party who digitally signed the message is indeed the individual to whom the public key belongs, and (2) neither the clear-text message nor the digital signature were modified after they were generated by the party who digitally signed the message. Practical digital signing algorithms commonly use a variation of the above technique in which the message to be digitally signed is first compressed using a hash function, but this is only done to improve algorithmic runtime and has no bearing on the analysis presented here.
A number of approaches in the prior art apply this digital signing technique to document security. Representative examples include: U.S. Pat. No. 5,912,974 (Holloway, Matyas), U.S. Pat. No. 5,157,726 (Merkle, Bloomberg, Brown), and U.S. Pat. No. 4,853,961 (Pastor). Despite some variations in method and intended application, these approaches use the same fundamental technique: they convert the printed contents of a paper document to some digital representation and then apply the digital signing technique to the digital representation of the printed document. The resulting digital signature is added to the paper document in some encoded, machine-readable form such as a barcode. Document authentication is accomplished by: (1) converting the printed document contents into the same digital representation originally used to generate the digital signature, (2) decrypting the digital signature included with the document using the public key of the alleged document source, and (3) comparing the decrypted digital signature with the digital representation of the document contents.
This technique indeed prevents certain forms of counterfeiting attack. For example, the printed content of a paper document cannot be falsely attributed by a counterfeiter to a third party (a Spoofing Attack) because the third party is identified by a public key and the document content must be digitally signed using the corresponding private key of the third party. As long as the counterfeiter cannot obtain the third party's private key, Spoofing Attacks of this sort are prevented. Additionally, a valid third-party digital signature cannot be transferred without detection from the document it was generated for to another paper document which has different printed content. This is because the third-party digital signature is formed using the original document content and will be inconsistent if transferred to a document with different content. This prevents a Copy Attack in which some of the printed document content is modified.
However, these approaches fail to protect against a Copy Attack which does not modify the printed document contents. In other words, if a counterfeiter transfers the exact printed contents of the document to another piece of paper (including the printed digital signature), the new paper document cannot be distinguished as a copy of the original. The reason is that only the printed information on the paper was digitally signed by the sender of the document. The digital signature contains no information that uniquely identifies the paper the original document was printed on. In other words, these approaches do not utilize a paper signature which can be used to distinguish different pieces of paper. Therefore, copies of identical documents on different paper cannot be distinguished. Copy Attacks which do not modify the document contents cannot be detected.
U.S. Pat. No. 6,611,598 (Hayosh) describes a modification to digital signing approaches that attempts to strengthen protection against Copy Attacks with no modification. When a document is created, this system generates a digital identifying tag (not the digital signature) for the paper and prints it on the paper using a special magnetic ink. This gives the paper a magnetic signature that can be detected during the authentication process. The magnetic signature printed on the paper is then encoded in some digital format and is concatenated with arbitrary user-defined data. The result of the concatenation is digitally signed with the private key of the issuing party. The digital signature is then printed on the document as a barcode. Authentication consists of using the public key of the issuing agent to decrypt the digital signature, retrieving the magnetic signature code from the decrypted data, re-reading the magnetic signature from the paper, and comparing the two signatures.
The approach is secure only if the magnetic signature applied to the paper cannot be transferred to another paper by a counterfeiter. If the magnetic signature can be transferred, the scheme is vulnerable to a Copy Attack with no modification—i.e., the magnetic signature provides no benefit. Like digital watermarks and moiré patterns, the magnetic signature is not derived from any intrinsic property of the paper. Therefore, it is vulnerable to being read and transferred from one paper to another by a counterfeiter. The existence of a legitimate apparatus for writing and reading a magnetic signature implies that a counterfeit apparatus for this purpose can also be produced with sufficient effort and ingenuity (perhaps by modifying the legitimate apparatus).
Paper-Grain/Light Scatter/Surface-Texture Based Approaches
The prior approaches described so far all suffer from a common limitation: the identifying signal applied to the document in question does not incorporate information intrinsic to the paper on which the document was printed. These systems are therefore vulnerable to various forms of Copy Attack in which the non-intrinsic nature of the signal allows it to be transferred from one paper to another, provided the signal can be reliably reproduced by a technically-sophisticated counterfeiter.
The final category of prior art we discuss avoids this limitation by deriving a paper signature directly from intrinsic properties of the paper itself. Specifically, these approaches use optical imaging of paper grains or surface texture to derive a unique signature for the paper a document is printed on.
U.S. Pat. No. 5,325,167 (Melen) describes a system which generates an identifying signature for a piece of paper using optical imaging of paper grain structure within a region of interest. Elementary image processing operations are performed on the paper grain image to remove high-frequency noise and DC offset. The resulting filtered pixel values collectively form a digital code for identifying the paper.
More recently, Cowburn has filed a patent with European Patent Office (GB2417707). In Cowburn's system, the surface of certain materials (such as paper and plastic) is illuminated with a laser and multiple detectors record an optical-scattering pattern which generates an image of surface texture. As with Melen's system, elementary image processing operations are performed on the recorded pixel values to filter high-frequency noise and remove the DC component and the filtered pixel values are collectively used to form an identifying digital code for the object.
Cowburn and Melen both propose using this signature to authenticate the source of various types of items, including paper documents. We focus here on the application to paper documents. In the approaches of both Cowburn and Melen, a reference signature is generated for a predetermined region-of-interest within the paper on which a document is printed. This reference signature can be printed on the document itself within a barcode-type region or it can be stored in a database at the site issuing the document. “Authentication” of a paper document is accomplished by re-deriving the paper signature from the predetermined region of interest and comparing this signature to the reference signature using cross-correlation of the two signatures. If the cross-correlation exceeds a threshold, the document is judged as authentic; otherwise, it is judge as counterfeit. If the reference signature resides in a database, then the re-derived paper signature must be cross-correlated against all entries in the database. If no match results, the paper document is classified as not having been issued by the site containing the database. We focus here on the case where the reference signature is included in the document itself.
In the system described by Melen, the reference signature is stored in unencrypted form in a barcode-type region of the document. Melen mentions that arbitrary user-defined data can also be co-located (in non-encrypted form) with the reference signature. This user-defined data could indicate the document source. Because the Source ID information is printed on the document in clear-text format and is not used to encrypt the reference signature, Melen's system provides little protection against counterfeiting attacks. A counterfeiter can selectively modify both the Source ID information and the reference signature when generating a new counterfeit document. For example, using Melen's proposed apparatus, a counterfeiter could generate a valid reference signature for a copy of the original document and then attribute the document to either the original third-party source or any other source.
In the system proposed by Cowburn, a coherent light source (laser) is used to shine light on a paper and several detectors are used to detect the light scattered from different parts of the paper. A digital signature is then generated from the pattern of scatter. Because the light scatter pattern is rather cumbersome to obtain and not robust at all, the system proposed by Cowburn is very complex and much less reliable.
Objects and Advantages
A Copy Attack on our system would involve transferring a valid signet from one piece of paper to another. This can be detected because the paper grain signature originally encoded in the signet will not match the grain signature of the new paper the signet is transferred to. A Copy Attack could only succeed if the transferred signet could somehow be modified to contain the signature of the new paper to which the signet is transferred. However, to construct a valid signet, the new paper signature must be encoded with the private key of the original Certifier, Augmented Printer, or both. It is assumed that the counterfeiter does not have access to the private keys of these entities. Therefore, the counterfeiter cannot selectively change the paper signature in the signet while simultaneously retaining the original Source ID. Therefore, a Source ID cannot be transferred to a new piece of paper.
A Spoofing Attack on our system requires a counterfeiter to construct a signet which references a third-party Certifier and/or Augmented Printer. A counterfeiter could certainly generate a signet and then modify its Certifier public key and/or Augmented printer public key to reference third-party sources. However, the counterfeiter would also need the private keys of the targeted third-party sources in order to encrypt the signet data (paper signature and user message). As long as these private keys are kept secure, they cannot be used by a counterfeiter. Any Spoofing Attack which false attributes the document to a third-party Certifier and/or Augmented Printer is therefore detectable by an Authentication Subsystem.
Comparison with Digital Watermarking/Moiré Effect Approaches
In contrast to Digital Watermarking/Moiré Effect Approaches, our system uses an intrinsic physical property of the paper to derive an identifying signature: the paper grain structure. This grain structure cannot be feasibly duplicated in another piece of paper. Therefore, there is no need to hide the data which encodes it. The signet in our system does not have to be hidden or degraded when copied. Its security rests in the fact that the paper grain signature of the paper has been entangled with the identities of the Certifier and Augmented Printer using public-key encryption. As demonstrated earlier, this prevents all forms of Copy and Spoofing Attack.
Comparison with Digital Signature Approaches
We should note here that the encryption our system performs using the Certifying Agent and Augmented Printer private keys is fundamentally the same form of encryption algorithm described above for generating the digital signature. The difference is that our system does not include any “clear-text” message—only the result of the encryption. We chose not to use the terms “digital signing” and “digital signature” in our system description in order to avoid confusion with our use of the term “signature” in describing the encoded paper grain structure within a region of interest. We use the terms “digital signing” and “digital signature” in the present discussion since they are standard terminology for this application of public-key encryption and are widely used in descriptions of prior art.
Our system exploits the digital signing algorithm described above, but it applies the algorithm to the grain signature of the original paper the document is printed on rather than the document contents. This allows our system to detect a Copy Attack which does not modify the printed document contents. Note that our system also detects Copy Attacks which do modify the document contents. This is because a Copy Attack always involves transferring some subset of the original document contents to a new piece of paper and our system detects when the paper is inconsistent with the signet printed on it.
Comparison with Paper-Grain/Light Scatter/Surface-Texture Based Approaches
Our system has advantages of both Melen's system and Cowburn's system, and more. For example, one difference between our system and the systems of Melen and Cowburn concerns how the paper signature is represented. Melen and Cowburn both use approaches that represent the paper signature as a group of filtered pixel intensity values and which use cross-correlation of these values when comparing two signatures. Cross-correlation is a general-purpose technique for template matching which does not attempt to exploit any structural information inherent in the signals it is processing. Paper grains, however, have a definite structure when imaged; algorithms which attempt to exploit this structure will perform better at discriminating/capturing the salient features of paper grains than cross-correlation approaches. Our system attempts to recognize pixel regions that strongly resemble a definite structural form typical of paper grains. This approach further distinguishes our system from the prior art discussed above.