Identification documents that cannot be counterfeited or falsified.
1993 International Carnahan Conference on Security Technology-P. 11-14.
Identification documents that cannot be counterfeited or falsified.
Identification documents (passports, ID cards, credit cards, etc.) that grant certain privileges to their owners are of particular interest to counterfeiters. By presenting a counterfeit ID card, one can receive cash on a check, a counterfeit passport allows illegal entry into another country, counterfeit medical cards allow free visits to medical institutions, etc. Significant progress in the development and production of desktop publishing systems and color copiers in recent years has contributed to the growing threat of counterfeiting and falsification of these documents.
Modern technology for protecting important and valuable documents uses special paper, paints and printing techniques (e.g. with holograms) to produce them. However, these measures have only limited success, since counterfeiters can often obtain paper, paints and even holographic installations from limited batches intended for printing special documents and reproduce documents that are indistinguishable from the originals. In addition, they take into account the limited ability of the human operator to visually distinguish between genuine and counterfeit documents; operator errors can make even very good security measures ineffective. The use of special materials and technological processes significantly increases the cost of producing documents.
The Communications Research Centre of Canada has developed a method for protecting identification documents (ID) from counterfeiting and falsification, AFID (Anti-Forgery Identification Document). A document produced using this method, in addition to the security features usually included in an ID, has a so-called «security seal». This seal, the size of a postage stamp, is placed on the front side of the ID next to the photograph of its owner and contains encrypted information identifying the photograph and alphanumeric information typical of IDs. All security information is recorded as a two-dimensional bar code. In fact, the security seal is a permanent ROM memory, into which the stored information is entered during the production of the ID. The seal may be in the form of a set of magnetic code strips or a memory block of a smart card. The information entered into the security seal is encrypted using the secret key of the two-key cryptographic system (see Appendix B). As a result, the information contained in the seal is protected in such a way that any alteration or forgery of it will be detected immediately. To identify the authenticity of a document, its image, including the photograph and the security seal, are entered into the computer via a scanner. The information contained in the seal is decrypted using the public key of the two-key cryptographic system. This information and the information obtained by scanning the photograph on the front side of the ID are compared. If they do not match, the fact of forgery is recorded. In this case, the identification process does not depend on the operator's attentiveness or fatigue.
The reliability of such protection depends on maintaining the secrecy of the private key of the two-key cryptosystem used to encrypt the information A FID. This key must be known only to the ID manufacturer. The identification equipment must not contain secret information, but must use an open decryption key corresponding to the secret encryption key used in the manufacture of the ID. This means that even the loss of the identification equipment cannot lead to a breach of the security of the protection system.
An ID card made using AFID technology is no different in appearance, shape and size from a regular ID card, and the presence of a security seal does not affect the process of checking its authenticity. The ID card contains a control point relative to which the position of the photograph and security seal is determined.
In the example ID, the rectangular mosaic of the security seal contains 80 bytes of data, arranged in a format of 32 bits across the width of the rectangle and 20 bits across its height. Of the 80 bytes of information, 6 bytes are unencrypted and 74 bytes are encrypted with a secret encryption key of 592 bits. If one bit of the encrypted information is changed, this will cause a change in the state of 50% of the bits, resulting in completely different decrypted data.
The information in the secure section of the seal contains a 12-dimensional vector called an «image descriptor», each element of which represents a three-digit number. The image descriptor is obtained by analyzing the ID holder's photograph using an algorithm that identifies the features of each face (see Appendix A). The descriptor also contains biographical information about the ID holder (surname, date of birth, etc.) and the ID validity period in secure form.
The unprotected part of the print includes the redundant CRC (Cyclic Redundancy Checking) code and bytes of scanning error flags caused by ID surface defects, as well as information about the ID manufacturer and the ID series number. The set of equipment used to produce the ID contains a camcorder or video camera connected to a personal computer controlled by a frame capture card. The final device that prints the ID is a color video printer.
The ID production process begins with the calculation of a pair of cryptographic keys used to generate the security seal information and input it into a personal computer application (Appendix B). The number of key pairs for each application may range from one to several hundred, and each organization may have its own set of keys and be responsible for maintaining the secrecy of its private encryption keys. The secret information, represented as a 592-bit binary number, is stored on a floppy disk that must be inserted into the personal computer during the ID production process. Non-secret information (ID holder's name, document expiration date, etc.) is entered from the keyboard and written to the database file card. A single frame of a video camera with an image of the ID holder is input into the computer for storage in its memory. The AFID software assembles the image, which is output to a video printer for printing on the text side of the ID. The ID is then scanned with a black-and-white scanner, the position of the checkpoint is determined, and the image descriptor is calculated. The program then encrypts the information to be protected on a secret encryption key, generates a security seal, and determines the ID format for printing it on a video printer.
To verify the authenticity of the ID, a scanner connected to a personal computer is used. The scanner transmits the converted ID image to the computer for analysis. The verification process is controlled by the identification part of the computer program, which issues a command to start scanning. The first step consists of determining the position of the checkpoint and orienting the photograph and the ID security seal relative to it. The computer calculates the descriptor of the scanned ID image. The information contained in the security seal is converted to binary form, and its integrity is checked using the CRC method. After this, the encrypted information is decrypted using the public key of the two-key cryptosystem.
The image descriptor contained in the security seal is compared with the descriptor obtained by scanning the ID after decryption. The comparison process consists of calculating the Euclidean distance between the two descriptor vectors. If this distance exceeds the established threshold value, the question of the ID authenticity arises. The threshold value of the Euclidean distance is established experimentally, taking into account that an overestimated value expands the tolerance for shutdowns during scanning and for damage to the ID, but at the same time can increase the number of errors in determining the authenticity of the ID. The biographical information of the ID owner contained in the security seal is reproduced on the computer monitor screen. The security seal may contain information that is not printed on the ID presented for verification. This information is also reproduced during verification and can be used to clarify some data about the ID owner.
Three possible methods have been identified by which a counterfeiter can forge an existing ID or make a new one.
1. A forger will attempt to replace the photograph in an existing ID with a different one. Since the image descriptor of the existing photograph in the ID differs from the descriptor of the new photograph, the forger must replace the forged photograph in a way that eliminates the difference in the descriptors before the replacement. Since there is no linear or approximate relationship between a photograph and its descriptor, the forger must resort to trial and error, making small modifications to the photograph to achieve a match in the descriptors. Each trial requires printing the modified photograph and scanning it to calculate the Euclidean distance. Printing and scanning the photograph takes about 1 minute and costs $1. Unless the Euclidean distance decreases monotonically as the forged photograph approaches the original, this method will fail. Furthermore, the modified photograph will not be an accurate image of the new ID owner.
2. A forger will attempt to change the biographical information of the ID owner printed on the text side of the document. During the ID authentication process, the calculator's display screen displays the decrypted biographical data contained in the security seal. If this data differs from that printed on the ID, it is considered counterfeit.
3. The forger will attempt to decipher the cryptographic key used to encrypt the information when making the security seal and make a new seal with new data. This operation requires factoring large binary numbers into prime factors. With large numbers used, this task is considered practically unsolvable.
A practical system for making IDs using AFID technology must be flexible enough to be reconfigured depending on the type of documents.
One ID verification station must be designed to identify documents of different types. Individual organizations using such a system may not agree with the general ID standard adopted for this system. For example, a driver's license in each state or region may have its own specific shape, size, and coloring. When verifying an ID, the operator must make appropriate changes to the settings and software depending on the ID presented, and select the necessary decryption key for the security seal information from the file.
The ID production can be carried out with remote control. The remote ID producer has the appropriate equipment and access to the central computer via a secret key. This producer forms the ID structure and transmits the information to be transferred to the ID in the form of a 592-bit number via the authentication line to the central computer. After this computer has performed the operations to process the incoming information, it is transmitted back to the remote location, where the prepared ID is printed. The transmission of 1200 bits of information for each ID allows IDs to be issued to customers almost in real time. The secret key is stored in a separate location with the necessary protection, so that there is no confidential information directly at the ID production location. Theft or loss of equipment from such a location will not lead to a breach of security of the entire ID production and authentication control system.
At the Communications Research Centre of Canada, experiments were conducted to generate image descriptors using a photograph database during the development of the AFID method. The files in this database contained approximately 4,000 photographs of men and women of different nationalities. The Euclidean distance was calculated for 300 randomly selected photographs, which made it possible to conduct 44,850 comparisons. Euclidean distance calculations were performed to determine the similarity of all photographs. The average value of this distance was 5507.2, and the standard deviation was 4104.5. The minimum Euclidean distance for any two photographs was 107, and the maximum was 51270. If the threshold value of this distance is taken to be 106, then none of the values obtained in the experiment will be below this threshold. If we increase the threshold to 263, then for 50 photographs the Euclidean distance will be below this threshold and they will be recognized as identical. If this higher threshold is adopted in the ID authentication system and a forger replaces a photograph on a document, then the probability that this replacement will not be detected by the threshold control is 50/44850 = 1.1 — 10E — 3. This means that 99.9% of IDs with replaced photographs will be recognized as counterfeit. With a threshold of Euclidean distance equal to 263, no genuine document will be recognized as counterfeit. It is advisable to choose a higher threshold, since a high probability of detecting counterfeits will create significant difficulties for forgers, and a low probability of recognizing valid documents as counterfeit will increase the degree of trust in the system.
Tests conducted with the presentation of a photograph of the same person at intervals of 30 seconds yielded a Euclidean distance value of 5000. The probability of recognizing a valid document as counterfeit depends on the accepted tolerance for the control equipment and the aging characteristics of the ID. It is planned to conduct a test of the AFID system under real operating conditions with the participation of 1000 students to evaluate its actual performance.
The size of the encryption key of a two-key cryptosystem determines the achievable level of security. To determine the secret encryption key from a known public decryption key, it is necessary to factorize a large number that is the product of two prime numbers. With a large key length, this process is very labor-intensive. It is estimated that the time required to factorize a 596-bit number exceeds 7-10E5 years, provided that modern mainframe computers are used to solve this problem.
In conclusion, based on the results of comprehensive tests and evaluations of the AFID system, it is stated that this system, based on the use of cryptography and image compression techniques, makes it possible to create IDs with increased security without additional costs for their production. If necessary, special inks and printing processes can be used to increase security in the production of IDs. Traditionally, the security of documents depends on the use of a limited supply of materials, but this does not apply to documents produced by the AFID system. The organization issuing the ID has a secret key, with which it manages the security of the ID. A prototype of the system with a full set of functional capabilities was tested with various software. The tolerance for improper handling of the ID by its owner was assessed.
Appendix A
Black and white photographs are scanned at a resolution of 160 pixels per cm. The first step in image compression is to reduce the resolution to 80 pixels per cm based on averaging. Each element of the image matrix represents a certain gray level. A histogram of gray levels is constructed, making it possible to define two thresholds for dividing image elements into classes with equal numbers. All elements with a gray level below the first threshold are classified as «white». Elements with a gray level above the second threshold belong to the «black» class, and all other elements to the «gray» class.
Thus, each element of the scanned image belongs to one of three classes, and the entire image matrix is divided into three separate matrices. A weighting function is applied to the image quantized in this way, which allows one to determine the center of the image, where the information is concentrated. Then the centroid is determined and the variations are calculated for the three matrices. 12 numbers (four for each matrix) form the «image descriptor». This descriptor has tolerances for changes in scanner parameters and adjustment inaccuracies during scanning.
Appendix B
The encryption operations in the AFID system are based on the well-known public-key cryptographic algorithm RSA. This algorithm uses two prime numbers p and q, which when multiplied together give 71 = pq. Then two other numbers d and e are generated; d is chosen randomly, but it must be relatively prime to (p — l)(q — 1). The number e is calculated as the multiplicative inverse of dmod(p- l)(q- 1). The pair of numbers e and n is kept secret, and the second pair — d and n — is published openly.
The encryption process is represented as follows:
encrypted message = (clear message)E e mod n.
The clear message is restored by performing the following operation:
plaintext=(encrypted message)^ mod n.
The time required to factor a k-bit number that is the product of two primes is
a constant x (5 — 10 E(9+(k/50))).
This time increases by an order of magnitude for every 50 bits (15 decimal places) of length. Factoring a 664-bit number (200 decimal places) requires (2-10)E28 operations. Using this computer, which performs one operation per 1 μs, factoring this number would take 36 million years.
The fastest computers in 1992 performed about 10E10 operations per second and cost $10 million or more. Even if the performance of future computers increases by two orders of magnitude, it will take about 1,000 years to factor a 664-bit number into prime factors. The cost of such a computer would be approximately $1 billion, making this approach practically unfeasible.