Nalini K. Ratha IBM T. J. Watson Research 30 Saw Mill River Road, Hawthorne, NY 10532 ratha@us.ibm.com |
Jonathan H. Connell IBM T. J. Watson Research 30 Saw Mill River Road, Hawthorne, NY 10532 jconnell@us.ibm.com |
Ruud M. Bolle IBM T. J. Watson Research 30 Saw Mill River Road, Hawthorne, NY 10532 bolle@us.ibm.com |
With the rapid growth of the Internet, electronic commerce revenue now amounts to several billion US dollars. To avoid fraud and misuse, buyers and sellers desire more secure methods of authentication than today's userid and password combinations. Automated biometrics technology in general, and fingerprints in particular, provide an accurate and reliable authentication method. However, fingerprint-based authentication requires accessing fingerprint images scanned remotely at the user's workstation, a potentially weak point in the security system. Stored or synthetic fingerprint images might be fraudulently transmitted, even if the communication channel itself is encrypted. In this paper we describe an algorithm for secure data hiding in wavelet compressed fingerprint images to alleviate this problem. Assuming the image capture device is secure, then only the decompressor on the server can locate the embedded message and thereby validate the submitted image.
Keywords Authentication, biometrics, fingerprints, WSQ compression, watermarking, data hidingThe past few years have seen an explosive growth of B2C (business-to-customer) activities over the Internet. The total dollar value of these web-based transactions is now over several billion US dollars. At present, the buyers are authenticated by service providers using only a combination of userid and password (at most). The critical information about the transaction, such as the credit card number and the amount, are sent over the web using secure encryption methods. However, current systems are not capable of assuring that the transaction was initiated by the rightful owner of the credit card. As Internet revenues grow, credit card owners and credit card issuers are likely to be increasingly concerned with the reliability and security of transactions.
One way this can be enhanced is with the help of automated biometric authentication. Biometrics is a rapidly expanding area and focuses on identifying people based on innate physiological or behavioral characteristics. Examples of biometrics include fingerprint, face, iris and voice. All automated biometrics-based person authentication systems operate by first acquiring a biometrics signal from the user, either locally or remotely. The signal is then analyzed to extract invariant features, and finally matched against a previously registered template.
Fingerprint-based authentication systems are the most advanced and accepted of the biometrics technologies. They have been used for more than a century in law-enforcement agencies and have been progressively automated over last three decades. Recent developments in fingerprint sensing technology that allow a fingerprint to be acquired without using the traditional ink and paper method have enabled the use of fingerprints in many non-criminal applications. As these sensors become cheaper, fingerprints will be an obvious choice for authentication in wide ranging applications because of its mature technology and its legal standing.
However, in both Web-based or other on-line transaction processing systems, it is undesirable to send uncompressed fingerprint images to the server. A typical fingerprint image is in the order of 512 × 512 pixels with 256 gray levels, resulting in an image size of 256 Kbytes. Unfortunately, many standard image compression methods have a tendency to distort the high-frequency spatial structural ridge features of a fingerprint image. This has lead to several research proposals regarding domain-specific compression methods. As a result, an open wavelet-based image compression scheme (WSQ) proposed by the FBI [1] has become the de facto standard in the industry because of its low distortion even at very high compression ratios.
Typically, the compressed image is transmitted over a standard encrypted channel as a replacement for (or in addition to) the user's PIN. Yet because of the open compression standard, transmitting a WSQ compressed image over the Internet is not particularly secure. If a compressed fingerprint image bit-stream can be freely intercepted (and decrypted), it can be decompressed using readily available software. This potentially allows the signal to be saved and fraudulently reused.
One way to enhance security is to use data-hiding techniques to embed additional information directly in compressed fingerprint images. For instance, assuming that the embedding algorithm remains inviolate, the service provider can look for the appropriate watermark to check that the submitted image was indeed generated by a trusted machine. Several techniques have been proposed in the literature for hiding digital watermarks in images. Bender et al. [4] and Swanson et al. [7] have presented excellent surveys of data-hiding techniques. Petitcolas et al. [8] provide a nice survey and taxonomy of information hiding techniques. Hsu and Wu [3] describe a method for hiding watermarks in JPEG compressed images. Most of the research, however, addresses issues involved in resolving piracy or copyright issues, not authentication.
Our approach is motivated by the desire to create on-line fingerprint authentication systems for commercial transactions that are secure against replay attacks in particular. To achieve this, the service provider would issue a different verification string for each transaction. The string would be mixed in with the fingerprint image before transmission. When the provider receives the image back he can then decompress and check for the presence of the correct verification string. This guards against resubmission of stored images. The method proposed here hides such messages with minimal impact on the decompressed appearance of the image. Moreover, the message is not hidden in a fixed location (which would make it more vulnerable to discovery) but is, instead, deposited in different places based on the structure of the image itself. Although our approach is presented in the framework of fingerprint image compression, it can be easily extended to other biometrics.
The following sections detail the original WSQ compression scheme and our message embedding extensions. We describe the FBI standard WSQ fingerprint compression algorithm in Section 2. Our data-hiding algorithm is presented in Section 3. Section 4 gives results of our algorithm. Conclusions and future work are presented in Section 5.
Here we give a short review of the FBI standard WSQ
fingerprint compression. More details are available in
[1]. Block diagrams of the WSQ encoder and decoder
are shown in Fig. 1(a).
An interesting aspect of the WSQ algorithm is the way
it handles the image at the boundary. Instead of simply
periodizing the image at the boundaries in both the dimensions,
the standard specifies symmetric extension transforms (SET)
which essentially mirror the image across the boundaries. By
extrapolating the signal in this way, the discrete wavelet
transform results in the same number of coefficients as there
were pixels in the original image. The details of the SET are
available in [1] and also in [2].
There are two more stages to WSQ encoding. The second
stage is a quantization process where the discrete wavelet
transform (DWT) coefficients are transformed to integers with a
small number of discrete values. This is accomplished by
uniform scalar quantization for each sub-band. There are two
characteristics for each band: zero of the band (Zk) and width
of the bins (Qk). These parameters must be chosen carefully
to achieve a good compression ratio without introducing
significant information loss. The Zk and Qk for each band
are transmitted directly to the decoder. The final stage
is Huffman coding of the integer indices for the DWT
coefficients. For this purpose the bands are grouped into
three blocks. In each block, the integer coefficients are
remapped to numbers between 0-255 as per a translation
table described in the standard. This translation table
encodes run lengths of zeros and large values. Negative
coefficients are also translated in a similar way by this
table.
Our data-hiding algorithm works on the quantized indices
before this final translation (i.e. between stages 2 and 3). Note
that we assume the message size is very small compared to the
image size (or, equivalently, the number of DWT coefficients).
The Huffman coding characteristics and tables are not changed;
the tables are computed as for the original coefficients,
not after the coefficient altering steps described in next
section.
Our method is intended for messages which are very
small (in terms of bits) compared to the number of pixels
in the image. To hide such a message during the image
encoding process, there are three basic steps as described
below.
For the decoder, there are also three steps. The first two
steps are the same as the first two steps described in the
encoder: constructing the set S and selecting the seed for
the random number generator. The third step is run the
pseudo-random number generator to select specific sites in a
particular order. The least significant bits of the values at
these sites are then concatenated to recover the original
message.
If a restoration appendix is included, the decoder can
optionally restore the original low order bits as it goes.
This allows perfect reconstruction of the image (up to
the original compression) despite the embedded message.
Because we were careful in selecting modification sites, the
restored decompressed image will be nearly the same as the
decompressed image with the message still embedded. In
practice, the error due to the embedded message is not
perceptually significant, and does not affect subsequent
processing and authentication.
Using this process only the right decoder can locate and
extract the message from the compressed image during the
decoding process. This message might be a fixed authentication
stamp, or personal ID information which must match some
other part of the record (which might have been sent in the
clear). Thus, if an uncoded or improperly coded bit stream is
given to the special decoder, it will fail to extract the expected
message and hence can reject the image.
A grayscale fingerprint image and its 64 bands are shown in
Fig. 2. The input image shown in 2(a) was acquired using
a live-scan optical fingerprint scanner. It was then been
compressed to 0.75 bits per pixel (10.7 : 1 compression)
to yield a representation consisting of the quantized and
translated bands comprising 13490 bytes. In this representation
our algorithm found 1287 sites where message bits can be
hidden. We randomly modified all of these sites. After
decompression (but not restoration) we obtain the image shown
in Fig. 2(c). Note that any standard decoder would yield
this image; it just could not extract the encoded message.
As can be seen, we can hide a message of considerable
length in the image, probably sufficient for e-commerce
transactions, without substantially affecting the image
quality.
In this paper, we have described a robust data-hiding
algorithm in the wavelet-compressed domain for fingerprint
images. The proposed algorithm is simple and can be easily
implemented in hardware. We have tested the system on
fingerprint images using the FBI-standard WSQ compression
scheme.
The basic algorithm can be easily extended to other
compressed image domains such as medical images, satellite
images, and other classes of biometrics images such as faces.
The key is to select sites for value-modification that have low
visual impact, and guarantee that some sites are left unmodified
for pseudo-random number seed generation.
Furthermore, many versions of the same algorithm are
possible by using different random number generators or partial
seeds. This means it is possible to make every implementation
unique without much effort; the output of one encoder need not
be compatible with another version of the decoder. This has the
advantage that cracking one version will not necessarily
compromise another version.
Currently, we are examining the possibility of recovering the
original data bits at the message sites without using an
appendix in order to get back the fully correct decompressed
image without any loss due to data hiding.
WSQ FINGERPRINT COMPRESSION
In the first step, the input image is decomposed into 64
spatial frequency subbands using perfect reconstruction
multirate filter banks. The filters are implemented as a
pair of separable 1D filters. The two filters specified for
Encoder 1 of the FBI standard are plotted in Fig. 1(b) and
(c). The sub-bands are the filter outputs obtained after a
desired level of cascading of the filters as described in the
standard (see Fig. 2(b)). For example, sub-band 25 corresponds
to the cascading path of `00,10,00,11' through the filter
bank. The first digit in each binary pair represents the row
operation index. A zero specifies lowpass filtering on the row
(column) while a one specifies highpass filtering on the row
(column).
DATA-HIDING ALGORITHM
RESULTS
CONCLUSIONS
REFERENCES