Pseudo-Signatures as a Biometric

Pseudo-Signatures as a Biometric Jin Chen, Daniel Lopresti, Lucas Ballard, and Fabian Monrose

Abstract— Recent work has shown that biometric key generation using handwriting as input is susceptible to attacks based on generative models and population statistics. In this paper, we examine a new scheme we have proposed that attempts to address this issue. Pseudo-signatures are intended to be easy for users to create and reproduce while being more resilient to forgery attempts. We consider some basic quality and performance measures to try to determine whether a user’s pseudo-signatures are sufficiently idiosyncratic. Our preliminary results indicate the approach shows promise and is deserving of further study.

I. INTRODUCTION It is widely accepted that reliance on user-generated textual passwords is problematic because passwords that are easy to remember are also relatively easy to guess [1], [7]. To address this issue, the community has devoted significant effort to finding input that has sufficient unpredictability to be used in cryptographic applications, but is still easy for humans to reliably regenerate. Biometrics, which are measurements of human physiology or behavior, are potentially useful for generating cryptographic keys because they are believed to exhibit high entropy across a population, while remaining easy for legitimate users to reproduce. A. Handwritten Biometrics Handwritten signatures have received widespread acceptance for legal purposes and are a familiar mechanism for establishing one’s identity. There are two fundamentally different ways of using handwriting for security purposes. Authentication, sometimes referred as verification, is the problem of using a biometric sample as proof of claimed identity. The other approach is to use handwriting as a basis for cryptographic key generation. Feature extraction and mapping to the key space are constructed in a way to preserve as much entropy as possible in the input without revealing anything useful to an attacker who may capture the biometric and reverse-engineer the host system. There are some important differences between the two usages of handwriting in a biometric setting. An authentication system can protect itself from a sustained attack by limiting each user a small number of attempts to login. Schemes that This work is supported by the National Science Foundation under grants CNS-0430178 (Lehigh) and CNS-0430338 (Johns Hopkins). J. Chen is with the Department of Computer Science & Engineering, Lehigh University, Bethlehem, PA 18015, USA [email protected] D. Lopresti is with the Department of Computer Science & Engineering, Lehigh University, Bethlehem, PA 18015, USA [email protected] L. Ballard is with the Department of Computer Science, John Hopkins University, Baltimore, MD 21218, USA [email protected] F. Monrose is with the Department of Computer Science, John Hopkins University, Baltimore, MD 21218, USA [email protected]

use handwriting for biometric key generation do not have this option since it is assumed that a potential adversary can obtain complete control over the system and reconstruct the biometric key at her leisure, without any time constraints. From a security perspective, this means that to be rigorous an evaluation must test not only the ability of talented human forgers trying to defeat the system, it must also consider whether algorithmic techniques place it at risk. Ballard et al. addressed precisely this question in their work, showing that attacks based on generative models for handwriting or that exploit general population statistics can be a serious threat [4], [5], [6]. B. Biometric Key Generation Techniques for cryptographic key generation have been proposed for numerous biometric modalities, including iris codes, keystroke latencies, speech, and, of course, handwritten signatures [9], [12], [13]. However, generating keys from signatures has several obvious benefits. First, compared with other biometric modalities, the capture of signatures is minimally intrusive. Secondly, the daily use of signatures results in a biometric modality that is highly repeatable. Third, users often embellish their signatures with decorative flourishes, which increases variation across the population. We note, however, that signatures have one drawback that makes them unappealing for key generation: each user only has one true signature. Since cryptographic keys can become compromised for any number of reasons, we seek a biometric modality that allows a user to create completely new keys whenever they are needed. A variant of this, which shares some of the benefits of signatures, is to generate cryptographic keys from handwritten passphrases. Handwritten passphrases address the onesignature/one-key limitation: if a user wishes to generate a new key, she can write a new passphrase. There have been studies showing that handwriting varies across the population [11], and researchers have proposed generating keys from this modality [12], [13]. This is the system that was broken by Ballard, et al. [5]. Veilhauer, et al., present a biometric hash based on 24 features extracted from an online handwriting signal [13]. They report achieving a False Accept Rate (FAR) of 0% at a False Reject Rate (FRR) of 7%. In a later paper they discuss feature correlation and stability for a larger set of features [12]. In this paper, we propose an approach for overcoming the vulnerabilities we previously identified through the use of idiosyncratic “pseudo-signatures.” We summarize the past work that led us to this notion and describe a novel graphical

interface to test the theory. We then outline the experimental setup and finally conclude with our experimental results and a discussion of ongoing research. II. P SEUDO -S IGNATURES AS A B IOMETRIC A. Motivation Ballard, et al. show how to exploit certain characteristics of biometrics and template structures which include, but are not restricted to, population statistics and the fact that many features are not statistically independent [3]. Their experiment results show a generative algorithm has a 50% chance of guessing a user’s key in no more than 222 attempts, and 15.5% chance guessing a key in a single attempt. In an attempt to address this problem, we exploit a kind of input the user does not normally write in the course of daily life. We base our approach on pseudo-signatures which are designed to provide distinguishability and a very large sample space. Our pseudo-signatures are created with the help of visual cues, common shapes (e.g., circles, squares, and triangles) which can be composed by the user in various ways, along with hints about how to trace the stylus over top of the shapes. In this way, we provide users with a tool allowing them to produce a form of handwritten (or handdrawn) input that will hopefully prove secure. Our idea for pseudo-signatures is outwardly similar to the “Draw-a-Secret” (DAS) graphical passwords proposed by Jermyn, et al. [8]. In that work, the authors present users with a 5 × 5 grid of blocks, and ask the users to create a drawing. The authors derive a password from the squares that the user’s stylus visits, as well as the order in which the squares are visited. The authors argue that the theoretical password space for “DAS” is much larger than the password space for standard text-based passwords. In an experiment involving 16 test subjects [10], however, Nali and Thorpe find that approximately 45% of the users choose symmetric passwords, two-thirds of which are mirror-symmetric. What is more, approximately 80% of the users choose passwords composed of 1-3 strokes, 10% use 4-6 strokes, and 10% employee six or more strokes. Finally, 56% of the passwords are centered, and an additional 30% are nearly centered. Clearly, when left to their own devices, users do not choose particularly good graphical passwords. B. Pseudo-Signatures Pseudo-signatures are a sequence of simple sketches that a user writes only for security purposes and hence may be able to help thwart generative attacks. Two aspects are important to accomplish this goal. First, we add online features, such as velocity of the pen tip and the lengths of pauses, over the relatively simple features used in the original “DAS” scheme. Secondly, we provide users with randomly generated visual cues to help them construct better passwords. This second point deserves more explanation. In order to encourage users to create pseudo-signatures with sufficient entropy, we propose to show each user a different set of visual cues generated through a random process. The user can use the cues as hints for creating more distinctive

passwords. The entropy of a pseudo-signature will not be computed from the cues, but rather how the user chooses to combine the cues and then draw her password based on them. These templates include, but are not limited to, different shapes to trace, colors to indicate pen velocity, arrows to indicate directions of strokes, and locations and lengths of suggested pen-tip pauses. Figure 1 is an example of two cues that might be presented to a user. The user might then draw the four edges of a square in the indicated order, with the red stroke (1) drawn slowly, the yellow stroke (2) somewhat faster and dashed, and the green strokes (3, 4) drawn quickly. She would also dwell the pen tip for a short time period in the lower left corner of the square, and for a longer time in the upper left corner. After finishing this, she could draw a circle at moderate speed, pausing at roughly the three o’clock position for a short period of time.

Fig. 1.

An example of two pseudo-signature cues.

It is important to note that the user is free to ignore the hints provided by the user interface. We also leave it to user’s interpretation as to what constitutes “medium” velocity, or a “long” pause. We hope that by only vaguely specifying the meanings of the visual cues, user are able to create their own keys with sufficient entropy. These visual cues serve as a mnemonic device to help users remember what they have previously written. Moreover, because the the users have the freedom of where to place the cues on the drawing surface, entropy is further enhanced. While the cue pallet is generated randomly, the system should be able to supply a particular user with the same set of cues she saw during her enrollment, of course. Our recent paper describes this part of the system in more detail [2]. When a user finishes placement of the visual cues, she then can draw her pseudo-signature. While one strategy here is to trace over the cues, it is important to note that the user is not limited to tracing – she can create a completely new pseudo-signature that bears little resemblance to the cues, making use of the space between the cues in creative ways. The final cryptographic key is a string of hashed values of the indices of bins over the range of each feature that contain the user’s samples. Since each user will be shown a different set of graphical cues, and since these cues can be combined in arbitrary ways, the maximum theoretical entropy available from pseudo-signatures is hopefully much

greater than what is offered by other systems that use handwriting as a biometric. III. E XPERIMENTAL D ESIGN Our data collection activities take place using NEC Versa LitePad tablet computers; this is the same system we used in our previous studies on handwriting biometrics. For now, there are six basic shapes built in the experiment system, four of which are symmetric, (e.g., triangle, square, cross, and circle). Along with these shapes, we have added arrows, colors, dashed lines, and gray circles to enrich the variety of the basic shapes. In this way, although most shapes are symmetric, the cues generated by the system will combine the hints and the basic shapes in a way to ensure greater variety. The experiment consists of three sessions, each of which requires a test subject to produce 10 pseudo-signatures. A 3 × 5 matrix of cues is shown on the upper half of the palette. Each subject is required to read an instruction sheet before providing her samples. In addition, one of the authors is available in case a user has questions during the course of the data collection. The total input time for a session falls between 30 and 45 minutes. Between each session, the system pauses to give the user a break and then resumes when she clicks the “next” button on the screen. There are a number of questions that need to be answered before pseudo-signatures can be considered an effective biometric. First, they must be memorable and repeatable by ordinary users, a question we consider in our first series of tests, Session I. It is also important from a security standpoint that different users select different cues when presented with the same palette, and that they tend to place their cues on the drawing surface differently, otherwise an attacker may have an easier time guessing a targeted user’s cue selection and placement. We deal with these questions in Session II. Finally, we wish to develop some intuition concerning the resistance of pseudo-signatures to forgery attempts. In Session III, we allow users to work from exactly the same cue placements, simulating a form of “shouldersurfing” attack, to see whether they sketch out their pseudosignatures differently even when the spatial arrangement of cues is identical. A. Session I In Session I, test subjects are required to select a numeric seed to protect the cue palette which they will use in creating their pseudo-signatures. When a subject selects a seed, the system generate a 3 × 5 matrix of cues which differ from one another in basic shape and/or other characteristics. The subject then drags down cues from the upper palette into

the lower drawing area. Cues are movable by the user and multiple copies of a given cue are permitted. Once a subject finishes the placement of her cues, she inputs her handwriting which serves as the biometric. She can trace the cues taking her own interpretation of the visual suggestions concerning pen speed and direction and dwelling time, or she can ignore the cues completely and draw whatever she likes. The cues are only intended to serve as a helpful mnemonic. In this session, subjects repeat the procedure 10 times trying to be as consistent as possible. This includes the set of cues they select, the way they place them, and the way they form their handwritten input. A practice session is recommended so that subjects can get used to the data collection tool and its user interface. B. Session II In this session, all test subjects work from the same set of 10 distinct seeds which are generated randomly. Subjects still perform the cue selection and placement phase of the data collection experiment, followed by entering their handwritten input. Once again, they have the freedom to sketch out a pseudo-signature however they like. Our goal here is to measure whether disclosure of a user’s initial seed value constitutes a primary threat to the security of the scheme. C. Session III In the third and final session, we study whether users tend to create similar pseudo-signatures when working from the same cue placement. Each test subject is presented with a set of cues in the lower drawing surface which are fixed and cannot be moved; the only step they perform is entering their handwritten input. The same settings are repeated 10 times. Figure 2 shows a screen snapshot from this part of the experiment. We note here that the cues and the placements we used in this session were results from real users collected in previous sessions. Hence, this can be regarded as a human-generated forgery attempt where the attacker has the benefit of knowing the targeted user’s cue layout but not her particular writing style. We use this data to measure the False Accept Rates (FAR) based on a particular feature extraction strategy to be described shortly. IV. E XPERIMENTAL R ESULTS To date, we have collected data from 29 test subjects totaling 960 samples using a custom GUI interface we developed in the Tcl/Tk scripting language. We begin by noting that seven of the subjects chose only one-digit seeds to protect their cue palette, further emphasizing the need

Percentages of Symmetric Pseudo-Signatures

90.00% 80.00% 70.00% 60.00% 50.00% 40.00% 30.00%

Experiment Session 1 Experiment Session 2

20.00% 10.00% 0.00% 0.00%

20.00%

40.00%

60.00%

80.00%

100.00%

120.00%

Tolerance Rates

Fig. 3. Percentages of symmetric pseudo-signatures observed in Session I and in Session II.

Fig. 2.

Screen snapshot of a user’s pseudo-signature from Session III.

both for good strategies for selecting and placing cues and for extracting significant entropy from a subject’s writing.

a tolerance threshold to decide when two quadrants contain roughly equal numbers of points. Examining two quadrant pairings (NW vs. NE and SW vs. SE), we classify a sample as symmetric if the two pairings possess an equivalent number of points. Figure 3 plots the percentage of symmetric pseudosignatures for various threshold levels. Assuming a threshold of 20%, the percentage of symmetric signatures in Session I is 13.8% and in Session II it is 14.1%. These results suggest that pseudo-signatures are not likely to suffer from symmetry problems to the same degree as the “DAS”scheme, as was shown by Nali and Thorpe [10].

A. Session I B. Session II

25.00%

Percentages of unmoved cue pairs

A basic question is how quickly users adapt to such a system. Preliminary results reported in an earlier paper suggest that after an initial acclimation phase, users appear to settle down to more consistent timings [2]. Symmetry in cue placement is important for understanding the potential entropy provided by the system. Note that the original “Draw-a-Secret” scheme falls short in this regard. It is natural, however, to expect that users might employ symmetry as a technique to help create memorable pseudosignatures. To measure this effect, we apply a relatively simple measure which first determines a bounding box enclosing the handwriting comprising the pseudo-signature and then subdivides the box into four quadrants. By plotting the number of sample points that fall within a given quadrant, we can obtain an estimate of whether a pseudo-signature is symmetric or asymmetric. For data collected during Session I, we average the results over the 10 input samples on a per-subject basis since there is variability between samples. We then employ

20.90% 19.60%

20.00%

17.80% 15.10% 15.00%

13.70% 10.70%

10.60%10.60% 10.00%

8.60%

7.70%

5.00%

0.00% 1

2

3

4

5

6

7

8

9

10

Indices of Inputs

Fig. 4. Percentage of cues which are left in their initial positions by the test subjects in Session II.

Here we attempt to answer another set of key questions regarding the potential security of pseudo-signatures. Given the same cue palette (i.e., the same initial seed), will users select similar sets of cues and place them in the same way? For our 29 test subjects, each of whom created 10 pseudosignatures working from the same palette, there are 2,822 cue pairings, of which 379 involve cues that the subject left in their initial positions. Figure 4 plots the proportion of unmoved cues for each of the 10 test sets. The overall average in this case is 13.5%. Users who choose not to adjust the placement of their cues enjoy less security than those who take the time to move them around before starting to write. Cue placement is an important concern in our system. If users tend to place cues in similar positions, then it is more likely that guessing schemes or brute-force attacks will be successful. In Figure 5, we plot the average Euclidean distance between pairs of cues for the different sample sin our Session II dataset. The bars on the left plot distances for all cues, while those on the right plot distances for cues that the user moves beyond their initial placement. A key observation from this experiment is that moving cues before writing has the potential to enhance security; the increase in average distance between cues in 19.0%. We believe this is a behavior that can be encouraged as users acquire more experience with mechanisms like pseudosignatures.

Average distances of all subject pairs

250

Whole Set Moving Set

204.4 200

166.55 150

100

88.24 71.28 58.54 56.03 48.06 47.31

50

36.33 30.95

31.92 31.26 27.16 26.35

24.96 23.52 22.44 21.62 20.02 19.25

similarity? This might model a shoulder-surfing attack, where the adversary sees and remembers the targeted user’s cue placement, but has no special knowledge of the writing style she uses for her pseudo-signature. To measure performance in this case, we need a particular scheme for feature extraction and cryptographic key generation. As did Ballard, et al. [4], we employ the basic method described by Veilhauer, et al. [12], also assuming that it is possible to correct some number of decoding errors in selected hash positions. (It has been noted elsewhere that modern microprocessors are sufficiently fast to post-process such keys in a few seconds provided the number of errors is not too great.) We used pseudo-signatures from our Session I data collection to build the biometric template for each subject (i.e., the interval matrix described by Vielhauer, et al.). Then we employed samples from our Session III test set to compute the similarity between the pseudo-signatures for two different subjects. The results of this exercise yield a False Accept Rates (FAR) of approximately 20% when five errors are corrected in the biometric hash. While not a particularly impressive value, we believe it should be possible to improve on this level of performance through a better GUI interface combined with selective feedback provided when users are first learning the system, subjects for future research. More informally, it is interesting to note that the test subjects did in fact personalize their interpretations of the hints provided with the visual cues. For example, one subject used dashed and solid lines for a specific pair of cues as suggested, while another ignored this guidance to yield a different-looking pseudo-signature. While still quite preliminary, these results seem sufficiently encouraging that we believe the concept of pseudosignatures merits further study. With the potential to overcome limitations associated with traditional signatures, normal handwriting, and previous security schemes like “Drawa-Secret”, pseudo-signatures may provide a reliable basis for generating cryptographic keys from pen input. V. C ONCLUSIONS

0 1

2

3

4

5

6

7

8

9

10

Indices of Inputs

Fig. 5. “Whole Set” datapoints take the average distances between all cue pairs into account, while “Moving Set” datapoints only reflect distances for cues that are moved by the user before writing.

C. Session III In our final experiment, we examine one particular forgery mode. Given a fixed cue placement, do different users sketch out different pseudo-signatures, or is there significant

In this paper, we have presented pseudo-signatures as a novel way of overcoming some of the limitations with previous schemes for generating secure cryptographic keys from handwritten input. Our preliminary experiments suggest that users are able to create and reproduce pseudo-signatures, and that they do not suffer from symmetry issues to the same degree as “Draw-a-Secret”. Encouraging good choices in cue selection and placement is clearly an important aspect of using our system effectively. A number of future investigations suggest themselves. We know from our previous studies on handwriting biometrics

that determined attackers can break such systems in several ways. Hence, we plan to explore the susceptibility of pseudo-signatures to several different forgery models. We can, for example, show potential attackers off-line or online playbacks of a targeted user’s writing to simulate more aggressive shoulder-surfing attacks. The impact of generative models for writing and drawing must also be studied before we can claim with confidence that pseudo-signatures are secure. Lastly, it is clear from this early work that users would benefit from assistance in the form of feedback when learning the system and designing good pseudo-signatures. Since such mechanisms can also be exploited by a potential adversary, however, care must be exercised at all times. VI. ACKNOWLEDGMENTS The authors gratefully acknowledge the anonymous subjects who participated in our data collection experiments. This work is supported by NSF under grants CNS-0430178 (Lehigh) and CNS-0430338 (Johns Hopkins). R EFERENCES [1] A. Alvare. How crackers crack passwords or what passwords to avoid. In Proceedings of the Second USENIX Security Workshop, pages 103– 112, 1990. [2] L. Ballard, J. Chen, D. Lopresti, and F. Monrose. Biometric key generation using pseudo-signatures. In Proceedings of The 11th International Conference on Frontiers in Handwriting Recognition, Montreal, Canada, August 2008. To appear. [3] L. Ballard, S. Kamara, F. Monrose, and M. Reiter. On the requirements of biometric key generator. Technical report, Whiting School of Engineering, John Hopkins University, Sep 7 2007. [4] L. Ballard, D. Lopresti, and F. Monrose. Evaluating the security of handwriting biometrics. In Proceedings of the 10th International Workshop on the Foundations of Handwriting Recognition, pages 461– 466, La Baule, France, October 2006. [5] L. Ballard, D. Lopresti, and F. Monrose. Forgery quality and its implications for biometric security. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Special Issue), 37(5):1107–1118, October 2007. [6] L. Ballard, F. Monrose, and D. Lopresti. Biometric authentication revisited: Understanding the impact of wolves in sheep’s clothing. In Proceedings of the 15th Annual USENIX Security Symposium, pages 29–41, Vancouver, BC, Canada, August 2006. [7] D. Feldmeier and P. Karn. Unix password security - ten years later. In Proceedings of Advances in Cryptology - CRYPTO, pages 44–63, 1990. [8] I. Jermyn, A. Mayer, F. Monrose, M. Reiter, and A. Rubin. The design and analysis of graphical passwords. In Proceedings of the Eighth USENIX Security Symposium, August 1999. [9] Y. Wai Kuan, A. Goh, D. Ngo, and A. Teoh. Cryptographic keys from dynamic hand-signatures with biometric security preservation and replaceability. In Proceedings of the Fourth IEEE Workshop on Automatic Identification Advanced Technologies, pages 27–32, Los Alamitos, CA, 2005. IEEE Computer Society. [10] D. Nali and J. Thorpe. Analyzing user choice in graphical passwords. Technical report, School of Information Technology and Engineering, University of Ottawa, May 27 2004.

[11] S. N. Srihari, S-H. Cha, H. Arora, and S. Lee. Individuality of handwriting: A validation study. In ICDAR ’01: Proceedings of the Sixth International Conference on Document Analysis and Recognition, page 106, Washington, DC, USA, 2001. IEEE Computer Society. [12] C. Vielhauer and R. Steinmetz. Handwriting: Feature correlation analysis for biometric hashes. EURASIP Journal on Applied Signal Processing, 4:542–558, 2004. [13] C. Vielhauer, R. Steinmetz, and A. Mayerhofer. Biometric hash based on statistical features of online signatures. In Proceedings of the Sixteenth International Conference on Pattern Recognition, volume 1, pages 123–126, 2002.