Fingerprints are characteristics of an object that tend to distinguish it from other similar objects. They have various applications, but in this chapter, we will show how they can be used for copyright protection of data. The techniques we are interested in do not rely on tamper-resistance and hence do not prevent users from making copies of the data, but they enable the owner to trace authorized users distributing them illegally. In the case of encrypted satellite television broadcasting, for instance, users could be issued a set of keys to decrypt the video streams and the television station could insert fingerprint bits into each packet of the traffic to detect unauthorized uses. If a group of users give their subset of keys to unauthorized people—so that they can also decrypt the traffic—at least one of the key donors can be traced when the unauthorized decoder is captured. In this respect, fingerprinting is usually discussed in the context of the traitor tracing problem. Fingerprints have another application: they can also be used as a means of high-speed searching. For example, the Cambridge University Library uses a fingerprint code with six characters to search periodicals. If the title consists of one word, one just needs to keep the first six characters. Otherwise, the first three characters of the first word of the periodical title and three initial characters of the following words in the title are used. For instance, “Computer & Communications Security Reviews,” can be found simply using “comcsr.” Similar ideas but more complicated techniques involving hashes are also used in database searching. Usually, cryptographic techniques are not used for such purposes. In both cases, the underlying concept is similar but the aspects and detailed techniques are different. Fingerprinting refers to the process of adding fingerprints to an object or of identifying fingerprints that are alread intrinsic to an object. The next sections present examples of fingerprints, the terminology and requirements for fingerprinting, a classification of fingerprints, research history, and a brief survey of important fingerprinting schemes.
Examples of Fingerprinting
Fingerprinting has been used for centuries and we may find several classical examples of it. We list typical examples of fingerprinting before the computer era. These examples will provide inspiration about what fingerprinting is and why it is needed.
Human fingerprints: It is known that each fingerprint has a different pattern that distinguishes it from others. For investigation purpose, human fingerprints are collected from prisoners and criminals. Since it is an easy means of identification, some countries adopt it in the citizen’s identification card (e.g., Korea and France). The Korean resident identification card contains a human fingerprint, and French citizens must give their fingerprints when requesting a new national identification. Human fingerprints are also used for access control as shown in several spy movies. During World War II, the American Office of Strategic Services (OSS) used the fist of their agents to identify them. Similar biometrics means such as human iris patterns and voiceprints are used for the same purpose. A British building society has been operating a large number of human iris scanning test systems on automated teller machines and will adopt this technology for customer identification on their automated teller machines rather than a typed password.
Fired bullet: Each weapon has its own type of fired bullet depending on both the manufacturer and the type of weapon. Typewriters are similar; each typewriter has its own typesets.
Serial number: Serial numbers on manufactured products are unique for each product and can be used to distinguish between them.
Coded particles of explosives: Some explosives are manufactured with tiny coded particles that can be found after an explosion. By examining the particles, the manufacturer, type, and manufactured time can be identified.
Maps: Sometimes maps have been drawn with slight deliberate variations from reality to identify copies. Since fingerprints on digital data are easy and inexpensive means of copyright protection, the demand on fingerprinting in computers and communication is getting stronger. We can find several examples of fingerprints in the computer era.
Prefix of email address: On mailing systems supporting IETF RFC 754, it is possible to add a prefix to usual email addresses. This can be useful when registering with an on-line service. For example, Bob (Bob@foo.org) can register Mallory+Bob@foo.org at Mallory’s site. Then if he receives an unsolicited message to this address, he can infer that Mallory passed the address to some bulk mailer.
PGP public keys: PGP (Pretty Good Privacy) is one of the most widely used public key packages and fingerprints for PGP public keys are used as one of the most important methods of identification. In PGP, the fingerprint is the MD5 [7, pp. 436–441] hash of public key bits including the public modulus and encryption exponent . This fingerprint is almost unique, and can be used as an identifier in directories of keys such as the Global Internet Trust Register. This register includes PGP fingerprints and key length as identifiers for public keys.
Digital audio/video: It has been suggested to use fingerprints to check out piracy of video data. In a pay-TV broadcast system, fingerprinting is applied to trace illegal subscribers.
Documents: As copyright protection means, fingerprinting is used in documents to discourage copying. Fingerprints are also embedded in computer programs, multimedia data, data streams, etc.
Terminology and Requirements
A mark is a portion of an object and has a set of several possible states; a fingerprint is a collection of marks; a distributor is an authorized provider of fingerprinted objects to users; an authorized user is an individual who is authorized to gain access to a fingerprinted object; an attacker is an individual who gains unauthorized access to fingerprinted objects; and a traitor is an authorized user who distributes fingerprinted objects illegally. To help understand this terminology, let us think about a case of image distribution; the image producer deliberately puts tiny errors into each distributed copy. These errors are the marks and the collection of all these errors is the fingerprint. The producer of the image is the distributor, and the buyer the user. A group of users may compare their images and find deliberate errors, then they may give or sell this information to others so that they can make illegal copies (such an attack is called a collusion attack). In this example, a group of users who give the information of errors are the traitors and the people who make illegal copies are the attackers. The general threat model in fingerprinting is as follows: the distributor’s goal is to identify the users whom the attacker has compromised and the attacker’s goal is to prevent his identification by the distributor.
While fingerprinting in itself provides only detection and not prevention, the ability to detect illegal use may help deter individuals from committing these acts. Requirements of fingerprinting for copy tracing and copy reduction include collusion tolerance as well as all requirements of watermarking:
• Collusion tolerance: even if attackers have access to a certain number of copies (objects), they should not be able
to find, generate, or delete the fingerprint by comparing the copies. In particular, the fingerprints must have a
• Object quality tolerance: the marks must not significantly decrease the usefulness or quality of the object.
• Object manipulation tolerance: if an attacker tampers the object, the fingerprint should still be negotiable, unless
there is so much noise that makes the object useless. In particular, the fingerprint should tolerate lossy data
Information Hiding Techniques for Steganography and Digital Watermarking
by Stefan Katzenbeisser and Fabien A. P. Petitcolas.