Graphical_Passwords_Based_on_Robust_Discretization.pdf

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

395

we will nd a lower bound on the second sum. To do so, we rst derive

an upper bound on c l for l satisfying l<( ? )n . We start with

[4] J. Fridrich, M. Goljan, and D. Soukal, “Wet paper codes with improved

embedding ef_ciency,” IEEE Trans. Inf. Forensics Security , vol. 1, no.

1, pp. 102–110, Mar. 2006.

[5] F. Galand and G. Kabatiansky, “Information hiding by coverings,” in

Proc. ITW , Paris, France, 2003, pp. 151–154.

[6] M. Goljan, J. Fridrich, and T. Holotyak, “New blind steganalysis and its

implications,” in Proc. SPIE, Electronic Imaging, Security, Steganog-

raphy, and Watermarking of Multimedia Contents VIII , E. Delp, III and

P. W. Wong, Eds., San Jose, CA, Jan. 16–19, 2006, vol. 6072, pp. 1–13.

[7] A. D. Ker, “Steganalysis of LSB matching in grayscale images,” IEEE

Signal Process. Lett. , vol. 12, no. 6, pp. 441–444, Jun. 2005.

[8] M. van Dijk and F. Willems, “Embedding information in grayscale im-

ages,” in Proc. 22nd Symp. Information and Communication Theory

Benelux , Enschede, The Netherlands, May 15–16, 2001, pp. 147–154.

[9] A. Westfeld, “High capacity despite better steganalysis (F5—a stegano-

graphic algorithm),” Information Hiding, 4th International Workshop

I. S. Moskowitz, Ed. New York, Springer-Verlag, 2001, vol. 2137,

Lecture Notes Comput. Sci., pp. 289–302.

[10] F. J. M. Williams and N. J. Sloane , The Theory of Error-Correcting

Codes . Amsterdam, The Netherlands: North-Holland, 1977.

c l n

l 2 nH(l=n) : (14)

The second inequality follows from Lemma 2.4.2 in [2] and holds for

any l<n=2 for sufciently large n (e.g., n>n 1 ). Using the fact that

H(x) is increasing on [0,1/2], from Taylor expansion of H(x) at ?

2 nH(l=n) 2 nH() =2 n ( H() ) (15)

where ? << ? . Finally, because H 0 is decreasing on the same

interval

c l 2 n 2 nH() <2 n 2 nH()

(16)

for any l<( ? )n .

We now obtain a lower bound for R a . Writing l 0 =b( ? )nc ,

from (13)

Graphical Passwords Based on Robust Discretization

Jean-Camille Birget, Dawei Hong, and Nasir Memon

lc l

c l

2 n

R a

2 n ( ? )n

l=l+1

Abstract— This paper generalizes Blonder’s graphical passwords to ar-

bitrary images and solves a robustness problem that this generalization

entails. The password consists of user-chosen click points in a displayed

image. In order to store passwords in cryptographically hashed form, we

need to prevent small uncertainties in the click points from having any ef-

fect on the password. We achieve this by introducing a robust discretization,

based on multigrid discretization.

Index Terms— Images, passwords, robust discretization.

c l

2 n

=( ? )n1

(17)

l=0

because R l=0 c l =2 n . Using (16)

R a ( ? )n1( ? )n2 nH()

=( ? )n(1(n)) (18)

I. I NTRODUCTION

where (n)!0 exponentially fast with n!1 . Combining this

result with a ? + , we obtain the following bounds for the

average distance to code in terms of the relative quantities (for n>

max(n 0 ;n 1 ) ):

Graphical passwords were rst proposed by Blonder [1]. In his

scheme, a password uses an image in which many small regions have

been delineated. The user has to choose some of these regions as a

password and in order to log in later, the user must click in each of the

chosen regions (with a mouse or a stylus). The user must remember the

chosen click regions and keep them secret. Several implementations of

this idea were given by [9]. Another version of click regions, this time

with movement, was carried out in [4]. Somewhat different graphical

password schemes (based on drawings in a grid) were introduced and

( ? )(1(n)) a ? + (19)

which proves the claim because >0 was arbitrary and (n)!0 for

n!1 .

A CKNOWLEDGMENT

The authors would like to thank J. Bierbrauer, P. Lisonvek, and M.

Goljan for many useful discussions.

Manuscript received September 14, 2005; revised May 29, 2006. The work

of J.-C. Birget was supported by the National Science Foundation (NSF) under

Grant DMS-9970471, in part by the National Science Foundation (NSF) under

Grant CCR-0310793, and in part by a Rutgers University ISATC Pilot Grant.

The work of D. Hong was supported in part by the National Science Foundation

(NSF) under Grant CCR-0310793 and in part by a Rutgers University ISATC

Pilot Grant. The work of N. Memon was supported by National Science Foun-

dation under grants. An earlier version of this paper appears in the Cryptology

ePrint Archive , report 2003/168 (Aug. 2003). Preliminary work also appeared

in [11]. The associate editor coordinating the review of this manuscript and ap-

proving it for publication was Prof. Roy A. Maxion.

J.-C. Birget and D. Hong are with the Department of Computer Science, Rut-

gers University, Camden, NJ 08102 USA (e-mail: birget@camden.rutgers.edu;

dhong@camden.rutgers.edu).

N. Memon is with the Department of Computer and Information Science,

Polytechnic University, Brooklyn, NY 11201 USA (e-mail: memon@poly.edu).

Digital Object Identier 10.1109/TIFS.2006.879305

R EFERENCES

[1] J. Bierbrauer , On Crandall’s Problem. 1998 [Online]. Available:

http://www.ws.binghamton.edu/fridrich/covcodes.pdf, Personal Com-

munication.

[2] G. D. Cohen, I. Honkala, S. Litsyn, and A. Lobstein , Covering

Codes . : Elsevier, North-Holland Mathematical Library, 1997, vol.

54.

[3] R. Crandall, “Some notes on steganography,” Steganography Mailing

List [Online]. Available: http://os.inf.tu-dresden.de/westfeld/crandall.

pdf, 1998.

396

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

analyzed in [5]. Yet, other graphical password schemes have been

invented, based on image recognition [2], [8], [10].

The click region passwords of Blonder have a limitation in that the

set of possible click regions must be predened; they are part of the

design of the image. This implies that the users cannot provide images

of their own for making passwords, and that users cannot choose click

places that are not among the preselected ones. Moreover, a complex

“natural” image (landscape, cityscape, art, photo of individual people

or groups, etc.) is not easy to subdivide into xed and recognizable

click regions.

On the other hand, allowing arbitrary click points leads to a robust-

ness problem: Usually a person will not be able to click repeatedly on

exactly the same places, which means that the password clicked on by

the user is “a little” different from the password that was originally

chosen. Allowing approximately correct passwords, however, prevents

the use of cryptographic password hashing (also known as “password

encryption”) since passwords that are approximately (but not exactly)

the same will usually have very different hash values. Cryptographic

password hashing is important because it enables secure storage of

passwords in an insecure storage (and backup) environment.

Thus, our passwords need to be discretized. But this is not good

enough by itself because of the edge problem of discretization: If the

place pointed to in the image is near a grid line, then slight perturba-

tions in the pointing can lead to signicant changes in the output of the

discretization. In Blonder-type graphical passwords, this would often

prevent a legitimate user from logging in. So, we need robust discretiza-

tion in which outputs are not inuenced by small uncertainties in the

input. We will achieve such a discretization by using a small number

of discretization grids simultaneously.

Our graphical password scheme, described in detail in Section III,

allows arbitrary images and has three components: image handling

(which allows a user to choose an image from a data base, or update

the image data base); password selection (during which a user chooses

click points in a chosen image); and login (during which a user clicks

close to the previously chosen click points in the previously chosen

image).

Overview : A robust discretization method is described in Section II.

The main motivation of the paper is the application of robust discretiza-

tion to graphical passwords, as described in Section III. Security is

briey discussed in Section IV.

This subdivides R 2 into grid squares of side-length q ; near the borders

of R 2 , the grid squares are truncated. The discretization yields a grid

map, which tells us which points of the rectangle R 2 are mapped to

which grid vertices

g:(x;y)2[0;a][0;b]7! x’

;

The set of points of R 2 that are mapped to a given grid point (m;n) is

1 (m;n)=f(x;y)2R 2 :qm+’x<q(m+1)+’;

qn+ y<q(n+1)+ g:

1 (m;n) is called a grid square; the grid map g maps this

entire grid square, namely [qm;q(m+1)i[qn;q(n+1)i , to the

grid point (m;n) .

Notation for intervals: In order to avoid confusion with the point

(a;b) , the open interval fx:a<x<bg is denoted by ha;bi . The

closed interval is denoted by [a;b] , and the half-open intervals are de-

noted by [a;bi and ha;b] .

Usually, the goal in the design of a good discretization is to min-

imize the loss of precision, or “quantization error” (i.e., the distance

between data points (x;y) and their discretizations). Our goal is quite

different: We want the discretization to keep outputs unchanged when

inputs are slightly perturbed, and we are not so much concerned with

the loss of precision. Indeed, in our applications, one of the main prob-

lems with discretization is the edge problem, mentioned in the Intro-

duction: Important features of an image could be near grid lines V m

or H n , and slight perturbations of a chosen location could then lead to

signicant changes in the output of the discretization. By denition, a

discretization is robust if and only if it has two properties which are: 1)

if a location pointed to is close to an originally chosen location (within

a specied tolerance distance < r 1 ), then the output is the same as

for the originally chosen location and 2) if a location pointed to is at

distance greater than r 2 from the originally chosen location (for some

specied tolerance distance r 2 with r 2 >r 1 ), the output is guaranteed

to be different than for the originally chosen location. (Here, “pointing

to” a location means, for example, pointing with a stylus, or clicking

with a mouse.) In our application to graphical passwords, condition

1) guarantees the acceptance of approximately correct passwords, and

condition 2) guarantees the rejection of signicantly wrong passwords.

In order to make sure that all features of an image are at a safe dis-

tance from grid edges, we use several grids at the same time. It is fairly

intuitive that in 2-D images, three grids are necessary and sufcient;

then we can lay out the grids so that every point in the image is at a

safe distance from the edges in at least one of the three grids (Fig. 1).

In a d -dimensional “image,” we will show that d+1 grids with appro-

priate offsets are necessary and sufcient.

The “safe distance from the edges” is a parameter r>0 . The

open r -disk around a point (x 1 ;...;x d ) is D r (x 1 ;...;x d )=

f(z 1 ;...;z d ):k(x 1 ;...;x d )(z 1 ;...;z d )k<rg , where kk

denotes the Euclidean norm in d -dimensional space. The following

denition makes the phrase “a point is at a safe distance from the

edges” precise.

Denition 2.1: Let r be any positive real number. A point

(x 1 ;...;x d ) is r -safe in a d -dimensional square grid G if the open

d -dimensional r -disk around this point (x 1 ;...;x d ) is entirely con-

tained in one grid hypercube of G .

Just as for the integers, we dene the mod operation for reals t and

q (with q 6=0 )by tmodq= def tbt=qcq .

Lemma 2.2: A point (x 1 ;...;x d ) is r -safe in a d -dimensional grid

G with quantum q and offset ( 1 ;...; d ) if for all i=1;...;d

II. R OBUST D ISCRETIZATION

We will start with a discussion of discretization, and then develop

a discretization which is robust. We dene the concepts of robustness

and of safety within a discretization grid, and give a rigorous proof of

robustness for our method.

Discretization (also called quantization) of data consists of approx-

imating a continuum, or a very large discrete set, by a discrete set of

limited size. To x the terminology, we describe a discretization of a

two-dimensional (2-D) rectangular gray picture. The picture is given

by a function [0;a][0;b]![0;1] , where [0;a];[0;b] are intervals

in the reals , or in the integers . In this paper, we are only interested

in the discretization of the domain of the picture (i.e., the rectangle

R 2 =[0;a][0;b] ). To discretize R 2 , we choose a positive number

q (called the quantum) and an offset (’; ) (where j’j;j j<q ), and

we superimpose a square grid on the rectangle. The grid has ba=qc+1

vertical lines

(V m )x=qm+’; where m=0;...;ba=qc

and bb=qc+1 horizontal lines

(H n )y=qn+ ; where n=0;...;bb=qc:

r<(x i i )modq<qr:

The set g

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

397

0;1;...;d) , we simply map the point into one of the grids in which

it is r -safe. We have to make a choice here, since there often will be

more than one grid in which (x 1 ;...;x d ) is r -safe. A safe grid choice

map : d 7!f0;1;...;dg from points to grids, is any map such

that (x 1 ;...;x d ) is r -safe in grid G (x;...;x) , for all (x 1 ;...;x d ) .

For example, (x 1 ;...;x d ) could be dened to be the smallest k such

that (x 1 ;...;x d ) is r -safe in grid G k ;or (x 1 ;...;x d ) could be a k

for which the distance of (x 1 ;...;x d ) to the grid hyperplanes of G k

is maximized; or (x 1 ;...;x d ) could be chosen randomly, always

subject to the r -safety condition (but kept xed once chosen). The

robust grid map is then dened by

g:(x 1 ;...;x d )2R d 7!((x 1 ;...;x d );

g (x;...;x) (x 1 ;...;x d )):

Fig. 1. Three grids G;G , and G (A is safe in G;B is safe in G and in

G ).

So the grid map provides a grid identier k=(x 1 ;...;x d )2

f0;1;...;dg and a grid-point g (x;...;x) (x 1 ;...;x d )2 d of the

corresponding grid G k .

The denition of r -safe says that if a chosen point p is r -safe in the

grid G k , and if a point x is at Euclidean distance <r from p , then x is

in the same grid square as p . In other words, once the system has chosen

a grid G k in which the click point p is r -safe (i.e., k=(p) ), then any

click within distance <r from p will be in the same grid square as p

and, hence, will be recognized by the system as the same as p . So the

user has a guaranteed tolerance r for click errors.

On the ot he r hand, if the user clicks on a point x at a distance >

m be the grid hyperplanes

that border the grid hypercube containing the point (x 1 ;...;x d ) . The

point is r -safe if it is at distance >r from each of these hyperplanes

(i.e., (x 1 ;...;x d ) is r -safe if for some integers m 1 ;...;m d we have

(for i=1;...;d ): i +qm i <x i < i +q(m i +1) . By the denition

of “mod,” this is equivalent to the statement of the Lemma.

In two dimensions, we now introduce three grids G 0 ;G 1 ;G 2 . All

three have quantum q=6r , and they are “staggered”: G k has offset

(2rk;2rk) , for k=0;1;2 . We will see (as a consequence of the

Theorem below), that every point is r -safe in at least one of these three

grids.

More generally, in a d -dimensional space, we consider a rectangle

R d =[0;a 1 ][0;a d ] , and we generalize all of the denitions

above in an obvious way. We introduce d+1 grids G k (with k=

0;1;...;d ), all with quantum q=2r(d+1) , that are staggered: G k

has offset (2rk;...;2rk) .

Lemma 2.3: A point (x 1 ;...;x d ) is r -safe in grid G k (k=

0;1;...;d) if for all i=1;...;d

r(2d+1) p d from the chosen point p , then the click is guaranteed

to be treated as incorrect. Indeed, each grid square has side-length q=

2r(d+1) , and a safe point is at distance >r from the edges; therefore,

if x is in the same grid square as p , then jp i x i j2r(d+1)r=

r(2d+1) for all of the coordinates (x 1 ;...;x d )=x;(p 1 ;...;p d )=

p . In other words, the max-distance between p and x is r(2d+1) ;

hence, the Euclidea n distance (in d -dimensional space) between p and

x is r (2d+1) p d . In 2-D space, this means that a click at distance

>r5 p 2(7:07r) is guaranteed to be treated as incorrect.

If a point x is at a distance between r and r(2d+1) p d from a

chosen point p , x may be in the same grid square as p , and they may be

in different grid squares (depending on the exact locations of x and p ).

In any case, for each grid, the number of grid squares in an a 1 ...a d

hyper-rectangle is at least ba 1 =qc...ba d =qc , and all of these grid

squares will be treated differently by the system.

Remark on connections with error-correcting codes: The midpoints

of the grid (hyper-)squares of a grid are an example of an error-cor-

recting code (with the decoding map being the mapping of a point to

the midpoint of the square that contains the point). All error-correcting

codes have an “edge problem” of a similar nature as grids do; if users

choose messages that are about equally close to two (or possibly more)

code words, the result of decoding becomes “unrobust.”

Previous work on robust discretization: Ideas similar to our robust

discretization appear in Wu’s work [15], where the edge problem is

discussed as well as the need for d+1 grids in d -dimensional space.

However, the properties of robust discretization (namely, the denition

of r -safety and our Theorem 2.4) are not explicitly stated in [15], and

the sufciency of d+1 is not proved (which we prove here for our

Theorem 2.4).

r<(x i +2rk)mod(2r(d+1))<r(2d+1):

Proof: In Lemma 2.2, just plug in 6r for the quantum q , and plug

in 2rk for each offset i

The following theorem shows that robust discretization is possible.

When the dimension d is 1 or 2, the proof is intuitive from the picture

of the grids.

Theorem 2.4: Let r be any positive real number. For every point

(x 1 ;...;x d ) in d -dimensional space, there is at least one grid G k (k=

0;1;...;d ) such that (x 1 ;...;x d ) is r -safe in that grid.

The proof is given in the Appendix.

The number d+1 is the minimum number of grids that gives us

r -safety. Indeed, for d grids G k (k=1;...;d) , let x i =c i;k be a grid

hyperplane of G k perpendicular to coordinate axis x i . Then, the point

(x i =c i;i ) i=1;...;d belongs to a grid hyperplane for each grid. Hence,

this point cannot be r -safe, no matter how small a positive number r is.

So d grids will not be sufcient, no matter what the quantum and the

offsets may be.

Robust discretization: Since we now know that every point

(x 1 ;...;x d ) is r -safe in at least one of the d+1 grids G k (k=

III. G RAPHICAL P ASSWORD S CHEME

We now give a detailed description of our graphical password

scheme, that was outlined in the Introduction. Our graphical password

scheme has three components: image handling, password selection,

and login.

1) The image-handling component enables users to choose images

or to introduce their own; the images are stored together with a

m ;...;H (d)

Proof: Suppose that the grid spacing (i.e., the discretization

quantum) is q , and the offset of the grid hyperplanes in dimension i

is i (for i=1;...;d ). Let H (1)

398

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

collection of images provided by the system. For this password

system to work well, it is important that the images be fairly

intricate, with hundreds of interesting details that could be chosen

as click regions (e.g., topographic maps, architectural images,

cityscapes, certain landscapes, and renaissance paintings).

2) The password selection component allows the user to select a new

password. Assuming the user has already logged in (by using ei-

ther a graphical or a conventional password), the user enters the

“password” command. The system then prompts the user for a

user name and current password. If the system accepts the current

password, it lets the user specify a new image (or keep the current

image), and set the safety parameter r for robust discretization (or

keep a default value).

Next, the image is displayed, and the user has to click on a

few places (of the user’s choice); for security’s sake, at least

ve places should be clicked. Let c be the number of clicks,

and let (x 1 ;y 1 );...;(x c ;y c ) be the sequence of click places.

The system takes the pixel coordinates of the click places,

and for each click place (x i ;y i ) , it computes a grid identier

k i =(x i ;y i )2f0;1;2g such that (x i ;y i ) is r -safe in grid

G k (for i=1;...;c ). For each (x i ;y i ) , the system remembers

the grid identier k i ; in our scheme, k i is stored in the clear (not

cryptographically hashed).

The system also computes the grid point g k (x i ;y i ) of the click

place (x i ;y i ) with respect to the grid G k , and it remembers

the secure hash value of the sequence of grid points of the click

places. In summary, the user provides a sequence of click places

((x 1 ;y 1 );...;(x c ;y c )) , terminated by a “return.” The system re-

members

stored in the system les. On the other hand, for a 2c -dimensional point,

there are 2c+1 grids. One grid out of 2c+1 possible grids is stored.

Of course, a source of information in which each event has probability

(1=2c+1) has much less entropy than a source in which each event

has probability (1=3 c ) (when c>1 ). For example, for c=5 , the grid

information is log 2 (2c+1)=log 2 113:5 for the improved method.

For the rst implementation, the grid information is log 2 3 c 7:9 . The

advantage of the improved implementation is thus that it represents the

chosen grids slightly more compactly.

Zoom: Zooming in magnies the area of the screen close to the

cursor. The magnication allows the user to choose ner features of the

image as click places. This may be a convenience for the user; it also

increases the password space signicantly by, in effect, decreasing the

parameter r .

One can imagine several options, which are: 1) the user could click

with the second mouse button to activate or deactivate the zoom-in; 2)

there is automatic zoom in in the vicinity of the cursor; and 3) The au-

tomatic zoom in around the cursor depends on the speed of movement

of the cursor; as the cursor slows down (near a possible click target),

the magnication increases.

IV. S ECURITY

The security of a password scheme depends, roughly, on the size of

the password space (i.e., the total number of possible passwords for any

given setting of the password parameters), and also on the way humans

tend to use the password scheme. We are not able to give a serious

security analysis of our graphical password scheme, for lack of data

on human behavior. We limit ourselves to a brief discussion based on

plausibility.

The size of the password space of our graphical passwords is parame-

terized by the safety parameter r (or, equivalently, the quantum q=6r )

and the number of click points c . Moreover, the image size ab (or

the screen size), and the resolution (number of pixels per square cen-

timeter) are parameters, but we usually have little control over them.

In general, the number of possible passwords is (ba=qcbb=qc) c .For

example, for an image of size 330 260 mm 2 , with safety parameter

r=1 mm (so, q=6r=6 mm), each grid has at least 2365(

330=6260=6) grid points. For graphical passwords with c=5 clicks,

the number of possible passwords is therefore 2365 5 710 16 . With

six clicks, the number of possible passwords is 2365 6 1:710 20 ,

and with seven clicks, it is 2365 7 410 23 .

For the value r=1 mm, the grid squares have side-length q= 6 mm;

this could be inconveniently small for many users, and for present-day

computer screens (due to poor resolution). However, when the zoom

feature is used, r=1 mm will not be small. When r= 2 mm, there

will be about 560 grid points; with six clicks, the number of possible

passwords is then 560 6 310 16 .

The human use of a password scheme determines the effective pass-

word space which, intuitively, consists of the passwords that users are

likely to use. Although it is difcult to dene the effective password

space rigorously in general, for our graphical password system, we can

nd an operational denition as follows: The chosen image itself is an

additional parameter now, and instead of the whole image size ab ,we

now count the area of the image that is occupied by “memorable” fea-

tures. We cannot dene rigorously what a memorable feature is, but

by human experiments, we can nd out which grid squares contain

features that humans will accept as being possible to remember; we

can also double-check by determining the nonmemorable regions–in-

tuitively, those are large “empty” areas that do not contain edges or con-

trasts. Thus, for our graphical password system to be effective, we have

to use images that are intricate enough to offer hundreds of attractive

click places (e.g., maps, architectural graphics, renaissance paintings,

city scapes, and complicated landscapes).

((x 1 ;y 1 );...;(x c ;y c )) and

HASH(g (x;y) (x 1 ;y 1 );...;g (x;y) (x c ;y c ))

in the user’s password record. The secret consists of the sequence

of grid points.

As usual for password systems, before putting the new password

in operation, the system should ask the user to conrm the pass-

word (by repeating the choice of clicks, but this time, it tolerates

errors within the safety parameter r ).

3) The login component presents the user with a window into which

the user types the user name. The system then retrieves the user’s

password record (which contains the sequence of grids to be used),

and displays the user’s password image. (If the user is not valid,

the system will display a default image, and will eventually reject

the user.)

The user then makes a sequence of clicks in the image. For the

i th click, the system uses the i th grid (1ic) in the stored

sequence of grid identiers, and computes the grid point of that

click place. (The system will not check whether the clicked point

is r -safe in this grid, because we want to tolerate errors up to r .)

When the user types “return,” the system computes the secure hash

value of the sequence of grid points and compares this with the

hash value stored in the user’s password record. If the two are

identical, the user is accepted; otherwise, the user is rejected.

Improved Implementation: In the graphical password scheme de-

scribed above, the c clicks were implemented as c 2-D points. Instead,

we could represent the click points (x 1 ;y 1 );...;(x c ;y c ) as one 2c -di-

mensional point (x 1 ;y 1 ;...;x c ;y c ) . This does not change anything

from the user’s point of view, but it decreases the amount of information

contained in the chosen grids. Indeed, when the c clicks are viewed as

c 2-D points, a sequence of c grids is stored in the system (in the clear).

At each click, there are three grids that are possible, so for c clicks, 3 c

grid sequences are possible. One out of 3 c possible grid sequences is

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

399

Some human aspects of graphical passwords are analyzed in [5] and in

[8], but the graphical passwords considered in those papers are very dif-

ferent from ours. Our graphical password system has been implemented

and some human factors experiments have been carried out on it, mainly

from the point of view of ease of use; we refer to [12]–[14] for details.

Extensive human factors experiments will be needed to explore the

size of the effective password space as well as possible unsafe usage

practices by human users which could then be exploited by attacks.

Moreover, in order to obtain a more general assessment of the human

security of our graphical passwords, real-world experience will be

needed, since in an experimental settings, it is difcult to replicate

the habits and practices that users develop as a result of long-term

everyday experience. Such experiments and experience are beyond the

scope of this paper, and will be addressed in future research.

hence, since r<2r(dh o ) when h o d1

r<x j +2rk<2rd+r:

So, for all x j with ji o , the condition of Lemma 2.3 is satised. For

all x j with ji o +1 ,wehave

2r(h o +1)+r<x i x j <2r(d+1)

hence, by adding 2r(dh o )(=2rk) and then subtracting 2r(d+1)

r<(x j +2rk)mod(2r(d+1))<2r(dh o )(<2rd+r)

hence, the condition of Lemma 2.3 is satised for all x j with ji o +1 .

Case B

[2rd+r;2r(d+1)i[[0;rihx d ;2r(d+1)i[[0;x 1 i:

V. C ONCLUSION

We generalized Blonder’s graphical passwords to arbitrary images,

which makes this type of password more usable. We introduced a ro-

bust discretization of images, based on a multigrid discretization; this

enables us to produce a unique output of the password, despite the fact

that users are not able to input exactly the same graphical password at

each login. This enables the system to store our graphical passwords in

cryptographically hashed form.

We claim that in this case, the point (x 1 ;...;x d ) is r -safe in grid

G 0 . Indeed, in this case, x d <2r(d+1) and r<x 1 ; hence, r<

x 1 ...x j ...x d <2r(d+1) . So the condition of Lemma

2.3 is satised (with k=0 ) for all x j

A CKNOWLEDGMENT

The rst author would like to thank students B. Isaacson and L. So-

brado, whose work beneted this paper. The authors thank the referees

for their recommendations which improved this paper.

A PPENDIX

P ROOF OF T HEOREM 2.4

Consider any point (x 1 ;...;x d ) . Since r -safety only depends on the

value of the coordinates mod (2r(d+1)) , we can assume 0x i <

2r(d+1) for each i=1;...;d . Also, by renaming the coordinates if

necessary, we can assume that 0x 1 x 2 ...x d <2r(d+1) .

Claim.: For some i o 2f1;...;dg and some h o 2f0;1;...;dg

R EFERENCES

[1] G. Blonder, “Graphical Password,” U.S. Patent 5 559 961, 1996.

[2] R. Dhamija and A. Perrig, “Déjà Vu–A user study using images for

authentication,” in Proc. 9th Usenix Security Symp. , Denver, CO, 2000,

pp. 45–58.

[3] D. C. Feldmeier and P. R. Karn, “UNIX Password security–ten years

later,” in Lecture Notes Comput. Sci. 435: Advances Cryptology Conf. ,

1990, pp. 44–63.

[4] B. Isaacson, “The password problem,” Hons. thesis, Rutgers Univ.,

Camden, NJ, Jun. 2001.

[5] I. Jermyn, A. Mayer, F. Monrose, M. Reiter, and A. Rubin, “The de-

sign and analysis of graphical passwords,” in Proc. 8th Usenix Security

Symp. , Washington, D.C., 1999, pp. 1–14.

[6] D. Klein, “A survey of, and improvements to, password security,”

in Proc. UNIX Security Workshop II , Portland, OR, 1990, pp. 5–14,

Usenix Assoc.

[7] R. Morris and K. Thompson, “Password security: A case history,”

Commun. ACM , vol. 22, pp. 594–597, 1979.

[8] “The science behind Passfaces,” Real User Corporation , Sep. 2001

[Online]. Available: http://www.realuser.com.

[9] M. Boroditsky, Passlogix Password Schemes, 2001/2002 [Online].

Available: http://www.passlogix.com.

[10] A. Perrig and D. Song, “Hash visualization: A new technique to

improve real-world security,” in Proc. Workshop Cryptographic

Techniques and E-Commerce , Hong Kong, 1999, pp. 131–138.

[11] L. Sobrado and J. C. Birget, “Graphical passwords,” Rutgers

Scholar , vol. 4, 2002 [Online]. Available: http://RutgersScholar.rut-

gers.edu/volume04/contents.htm.

[12] S. Wiedenbeck, J. Waters, J. C. Birget, A. Brodskiy, and N. Memon,

“PassPoints: Design and longitudinal evaluation of a graphical pass-

word system,” Int. J. Human-Comput. Studies , vol. 63, pp. 102–127,

2005.

[13] S. Wiedenbeck, J. Waters, J. C. Birget, A. Brodskiy, and N. Memon,

“Authentication using graphical passwords: Effects of tolerance and

image choice,” presented at the Symp. Usable Privacy and Security,

Carnegie-Mellon Univ., Pittsburgh, PA, Jul. 6–8, 2005.

[14] S. Wiedenbeck, J. Waters, J. C. Birget, A. Brodskiy, and N.

Memon, “Authentication using graphical passwords: Basic results,”

presented at the Human–Comput. Interaction Int., Las Vegas, NV,

Jul. 25–27, 2005.

[15] C.-W. Wu, “On the design of content-based multimedia authentication

systems,” IEEE Trans. Multimedia , vol. 4, no. 3, pp. 385–393, Sep.

2002.

[2rh o +r;2r(h o +1)+ri

hx i ;x i+1 i; with i o <d;h o <d; or

[2rd+r;2r(d+1)i[[0;ri

hx d ;2r(d+1)i[[0;x 1 i; when i o =h o =d:

Proof of the Claim: There are d numbers x j (for j=1;...;d ),

and there are d+1 disjoint sets

S h =[2rh+r;2r(h+1)+ri; for h=0;1;...;d1

and

S d =[2rd+r;2r(d+1)i[[0;ri:

Hence, by the pigeonhole principle, at least one of these sets, say S h ,

does not contain any x j . We take x i to be the largest x j that is less

than all of the elements of the set S h . This proves the claim.

Proof of the Theorem: With the claim, we only need to consider

the two cases A and B below. Case A

[2rh o +r;2r(h o +1)+ri

hx i ;x i+1 i; with h o <d;i o <d:

We claim that in this case, the point (x 1 ;...;x d ) is r -safe in grid

G k with k=dh o (>0) . Indeed, for all x j with ji o ,wehave

0x j x i <2rh o +r:

Hence, by adding 2r(dh o )(=2rk)

2r(dh o )x j +2rk<2rd+r

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: