Echo Back in Implementation of Passphrase Authentication
Kanta Matsuura(Institute of Industrial Science, University of Tokyo, JAPAN)

Abstract
In spite of well-known vulnerabilities, passwordbased authentication is still widely used. One possible
improvement is to use long passphrases. But unfortunately, the longer passphrases are, the more likely
users mis-stroke. To make matters worse, since userauthentication interfaces are usually implemented without echo-back of stroked characters, users do not notice
their mis-strokes before they nish the long inputs. In
order to solve this problem, this paper proposes an echoback scheme the monitor displays a chain of hashedvalues instead of asterisks. Its eect is studied in termsof expected number of total strokes. The study suggests
an optimal strategy for the chaining and echo-back. It
is also suggested that we can use the same strategy
without customizing it. As an extension, image-based
echoes are discussed as well.

Keywords: user authentication, password,
passphrase, hash function, echo-o problem.

1 Introduction
User authentication is a central security issue. A
taxonomy of user authentication tells us that we have(1) token-based systems, (2) systems based on biometrics, (3) knowledge-based systems, and (4) recognitionbased systems.

Token-based systems: The system regards theowner of a speci c device or token as a legitimate user. If a user carelessly leaves their token
at home, he could not use the system during thetrip. If someone else steals a token or luckily nds
a lost token on a public road, he may be able touse it. Thus the system is often combined withknowledge-based authentication ATM authenti-

 Correspondence to: Dr. K. Matsuura, Institute of Industrial
Science, University of Tokyo, Komaba 4-6-1, Meguro-ku, Tokyo
153-8505, Japan. E-Mail: kanta@iis.u-tokyo.ac.jp

cation requires a bank card and a PIN (Personal
Identi cation Number), for example.

Biometrics: The system veri es a speci c biomet-

rics property of a user ngerprint, for example.
Users may hate this due to privacy reasons. The
system equipment tends to be expensive. A moresigni cant problem is its unrevokability. If a PIN
is compromised, the user can update it into a newone. But he couldn't replace his ngerprint witha new one.

Knowledge-based systems: Users show someknowledge such as PINs or passwords to thesystem. Simple or meaningful passwords areeasier to remember but vulnerable to attacks
too short ones can be revealed by an exhaustivesearch attack while too meaningful ones by adictionary-search attack. Complex, arbitrary or
meaningless, and long passwords are more secure
themselves, but are dicult to remember. So
users tend to write them down. This in turn
reduces the system security in our real world. In
addition, the more severe the requirement for PIN
quality, the more likely they use similar or even
identical PINs in dierent systems. This meansthat all the systems are only as secure as the most
weakest one.

Recognition-based systems: Not a user but thesystem shows several items and the user makes appropriate response to them. This can be regarded
as a challenge-response extension of knowledgebased systems but, from the view point of humanfactors, more secure when we use images which aredicult to write down or tell to other guys images
generated by Random Art1], 2], for example.

Looking at current real systems, in spite of those wellknown vulnerabilities and proposals of other mechanisms, password- or PIN-based systems are still widelyused in user authentication either by themselves or in
combination with other schemes.

It is well known that there have been a lot of efforts to improve the security of password authentication 3]{6]. After all, even with those eorts, our passwords need entropy sucient for the required security
level 7], 8]. However, since people are not good atremembering a long meaningless chain of characters,
the entropy requirement might cause a compromise resulting from writing them down. One solution to thisproblem is the use of long meaningful passphrases 9],
10]. For instance, let us suppose a system in which a
passphrase is used to generate 64-bit encryption key.
In this case, according to the estimate of entropy inEnglish language11], 8], we need 49- or 50-character
passphrases. For example, the title of this paper itself
is composed of 50 characters. Typical users probably
accept and can remember passphrases of this length.
Thus passphrases may provide higher security but
unfortunately degrade usability the longer they are,the more likely users mis-stroke during authentication
procedure. To make matters worse, since it is a common practice to implement passphrase-authenticationinterface without echo-back of stroked characters12],
13], users do not notice their mis-strokes before theynish the long inputs and the log-in attempts are rejected. In order to solve this echo-o problem, thispaper proposes an echo-back scheme by the use of oneway hash function during passphrase-authentication
procedure, the monitor displays a chain of hashed values instead of echo-o asterisks. If the user remembers
part of the hashed values, he may notice his mis-strokes
before nishing all the typing-in.
The rest of this paper is organized as follows. First,
we describe how to echo back and how to remember theecho in Section 2. Next, in Section 3, the eect of thescheme is studied in terms of expected number of total
strokes required for one successful log-in. After discussion of the results and implementation in Section 4,
Section 5 concludes the paper with some remarks.

2 Echo-Back of Passphrase
We consider a passphrase composed of C charactersand divide it into L blocks. Each of the rst L;1 blocks
has C characters where L = dC=C e, and the last
block has C ; C (L ; 1) or (C mod C ) characters.
The j -th block will be denoted by pj , in the following.
In our echo-back scheme, the monitor displays a hashedvalue which is generated from a local secret, the userID, and blocks which are already typed. This display
is updated block by block, i.e., when the user nishes
typing a block. The user remembers part of the hashedvalues. If he nds a mismatch between the rememberedvalue and the displayed value, he restarts the log-in

procedure.
The details are as follows.
When a user X nishes typing the rst block, themonitor displays

h1 = h(h(ID X  K ) p1 ))(1)
where ID X is his user ID, K is a local secret of the machine for salting, and h() is a one-way hash function.

The salting prevents o-line exhaustive search attacks
after peeping. h1 appears on the screen in d-ary representation. We assume that the output of the hashfunction is too long for X to memorize all the digits.
So X remember not all but only m1 digits of h1 , andif he nds a mismatch in them, he clears the input andrestarts to type his passphrase from the rst character. If no mismatch is found, he goes on to the second block. On the assumption that the hash function
outputs random values, the probability of a mis-stroke
being noticed as a mismatch is

 

m1
:
1 ; d1(2)

When X nishes typing the second block, the monitor displays
h2 = h(h1  p2 ):(3)
Again, X remember not all but only m2 digits of h2 ,and if he nds a mismatch in them, he clears the input and restarts to type his passphrase from the rst
character. If no mismatch is found, he goes on to thenext block. The same procedure is operated until thesecond nal block, that is,

hj = h(hj;1  pj ) (j = 2 3     L ; 1):(4)
When X nishes typing the nal block, the monitor
does not need to echo it just tells X the authentication
result either by allowing the log-in or by rejection.
Thus, with a certain high probability, the user can
notice his mis-stroke before nishing all the input. Theeect of this \earlier notice and restart" will be studied
in the next section.

3 Evaluation
In this section, we evaluate the eect of the proposed
echo-back scheme in terms of expected number of total
strokes required for one successful log-in. This number
is denoted by S , in the following.
We assume that the memory capacity of the user islimited to a certain amountM = m1 + m2 +    + mL

(5)

where M is a constant integer. Since the hashed values
are random, it is easier for users to remember the same
number of digits per block. Therefore, we consider amemory strategy such thatand can be recursively derived from

m1 = m2 =    = mk = m (positive constant) (6)(j = 2 3     L)

mk+1 = M mod m
and

(7)

mk+2 = mk+3 =    = mL = 0:(8)
In general, users tend to type more carefully andslowly after an unsuccessful log-in attempt. For simplicity, we consider two types of users

Type 1 users become careful enough to type correctly in the second attempt.

Type 2 users make mis-strokes with the same probability in the second attempt as in the rst attempt
but become careful enough to type correctly in thethird attempt.

Both have their restart from the rst character of thepassphrases after noticing the mismatch of the echo.
We do not consider users who restart their typing fromthe previous block rather than the very rst character.
This is because long passphrases are dicult to restarton the way (e.g. it is dicult to remember what is the\26th" character of a long passphrase). Then, assuming that mis-stroke probability e (in the rst attempt
and in the second attempt of Type 2 users) is common
for every character, the expected number of strokes S
is given by

S = C (1 ; e)C +

LX
;1
j =1

j (j C + C ) + 2CL

(9)in the case of Type 1 users, andS = C (1 ; e)C + 2CL(1 ; e)CLX;1+ j (j C + C ) (1 ; e)C
j =1
LX
;1 LX
;1

i j ((i + j )C + C )i=1 j =1
LX
;1
+2 j L (j C + 2C ) + 3CL2
j =1
+

(10)

in the case of Type 2 users. j is the probability of\notice and restart" after the input of the j -th block,1 = 0(11)j ;2
j = (1 ; eblock)dmj;e1block + j;1

(12)


n
o
j = (1 ; eblock)j;1 eblock + j 1 ; dm1(13)j(j = 1 2     L ; 1)
L = (1 ; eblock)L;1 elast + L
(14)
where eblock=1 ; (1 ; e)C is the probability that misstrokes occur in a block of length C while

elast =



1 ; (1 ; e)C
(if C jC )1 ; (1 ; e)C mod C (otherwise)(15)

is that in the nal block.
Given the passphrase length C , the memory capacity M , and the mis-stroke probability e, the expected
number of total strokes S depends on the memory
strategy determined by C and m. We of course want
to use an optimum strategy to make best use of ourmemory capacity. Therefore, by exhaustive search, wend the optimum C and m which minimizes S fordierent values of user's mis-stroke probability.
Throughout the following study, we use a display
representation of d=10. This is because users are accustomed to memorizing a numerical character from 0
to 9 in the case of meaningless object1 .
Figure 1 shows the evaluation results when C =50
and M =10. As mentioned earlier, the passphrase
length C =50 corresponds to 64-bit key generation. The
additional memory burden of M =10 means that users
make an eort as heavy as remembering telephone
numbers. As for users with better or larger memory, we
also studied the case of C =50 and M =12. The resultis shown in Fig. 2. In those gures, the performance of
our echo-back scheme is plotted by marks (\o" in thecase of Type 1 users while \x" in the case of Type 2
users) and that of conventional echo-o implementation is plotted by lines (solid line in the case of Type 1
users while dotted line in the case of Type 2 users).
The dierence between the lines and the marks
shows how signi cantly the performance is improvedby the proposed scheme. This signi cance depends onthe mis-stroke probability e per character. In most
likely probability region between e=0.1% and 10%, thereduction in the expected number of total strokes islarger than 50%.

1 We say \meaningless" when the object has no understandable linguistic meaning for the user.

User of Type1 (o & solid); Type2 (x & dotted)
150
140

Expected Number of Strokes

130
120
110

Optimum Strategy:+ Hash per∆C=4 strokes+ Memorize m=1 digit
in each of the first
10 hashes

→
∆C<4

100
90
80
70
60
50
0.01

0.1
1
Mis-Stroke Probability [%]

10

100

Figure 1. Expected number of total strokes required for one successful log-in by the optimum strategy. Users are assumed to be able to memorize M =10 digits in echo. When the mis-stroke probability
is smaller than 32.5%, the optimum strategy is to update the hashed value every C =4 inputs andremember m=1 digit per hash. For reference, the solid line shows the expected number of strokes
in the case of Type 1 users with echo off. This is reduced to the circle marks (o) by the proposed
echo-back scheme. Likewise, the dotted line is in the case of Type 2 users with echo off. This is
reduced to the cross marks (x) by the proposed echo-back scheme.

Regarding users' burden, there is only a little dierence between the performances for M =10 and M =12.
So we can recommend users the more light one, i.e., toremember 10 digits in the echo.

4 Discussion
4.1 Implementation
Here we discuss the implementation of our scheme.
In the case of the recommended memory burden of
M =10 (Fig. 1), fortunately, we can see a very stable result in the region of e < 32:5%, the optimum
strategy is (C m)=(4, 1) for both Type 1 users andType 2 users. Since this range of mis-stroke probability
seems to cover carelessness of most real users, we canin practice use the same strategy where a hash chain ispresented every 4 characters typed in and users are recommended to remember one digit (probably the rst
or the last digit is the easiest for most users) of eachof the rst 10 hashed values. If users feel frustrated tosee a display of all the hashed values including digits
which are not remembered, an actual implementation
can display only one digit of each hashed value, or alternatively, display the sum of all the digits modulo 10.
This implementation is sketched in Fig. 3. For users
with better memory, the implementation continues toecho until the second last block.
The followings are extensions which would need user
studies with actual implementation although theoretically we can use Eqn.(9) and Eqn.(10). The need isdue to the cognitive issues, which are not trivial.
First, for security reasons against peeping, one
might be able to attach dummy echoes on the screen.
For example, 10 rows of numerical characters are displayed, among which only one row represents the actual
echo. When the user registrates himself, he determines
which row should play the role.
Second, practitioners can consider simple graphics
or images in place of numerical characters for the echo.
Let us suppose 10 simple but distinguishable images.
Instead of displaying the digits, the screen displays thecorresponding images. Random arts 1], 2] would beUser of Type1 (o & solid); Type2 (x & dotted)
150
140

Expected Number of Strokes

130
120
110

Optimum Strategy:+ Hash per∆C=4 strokes+ Memorize m=1 digit
in each of the first
12 hashes

→∆C<4

100
90
80
70
60
50
0.01

0.1
1
Mis-Stroke Probability [%]

10

100

Figure 2. Expected number of total strokes required for one successful log-in by the optimum strategy. Users are assumed to be able to memorize M =12 digits in echo. When the mis-stroke probability
is smaller than 18.5%, the optimum strategy is to update the hashed value every C =4 inputs andremember m=1 digit per hash. For reference, the solid line shows the expected number of strokes
in the case of Type 1 users with echo off. This is reduced to the circle marks (o) by the proposed
echo-back scheme. Likewise, the dotted line is in the case of Type 2 users with echo off. This is
reduced to the cross marks (x) by the proposed echo-back scheme.

worth a try. The next subsection will discuss this extension more in detail.

4.2 Graphic Echoes
When we want to display some graphics or images
as echoes, at least the following questions would occur:
 How many distinguishable images can be used?
That is, we want to know an appropriate assignment of the parameter d.
 How many images can be memorized? That is, wewant to know an appropriate assignment of theparameter M .
 Are the images easy to tell other guys? We preferdicult-to-tell images for security reasons.
The nal question recommends the use of Random
Arts. Random Art is a prototypical solution for hashvisualization1]:Denition 4.1 (HVA) A hash visualization algo-rithm (HVA) is a function hI which has, as a minimum, the following two properties:
1. Image-generation: hI maps an input x of arbitrary
nite length, to an output image hI (x) of xed size.
2. Ease of computation: Given hI and an input x,
hI (x) is easy to compute.

Denition 4.2 (Near Images) Two images I1 andI2 are said to be near, denoted as I1 ' I2 , if the two
images are perceptually indistinguishable.

Regarding the use of Random Arts for recognitionbased authentication, a user study2] suggests thatusers can tell M = 5 out of d = 25 distinguishable images with a burden and performance similar
to those for 4-digit PINs. Therefore, we studied theeect of our echo-back for the parameter assignmentof (M d) = (5 25). The situation is summarized asfollows:

s s s s s ss s s s

Passphrase divided into 4-character blocks
echo back inim plem enta tion ofpa ssph rase auth enti cati onID-? -? -? -? -? -?-? -? -? -?

??????????

2 7 1 5 3 7 2 6 0 4
display (echo)

'$
u&%
u
6
?

memory (10 digits)

Figure 3. An optimum implementation of echo-back for authentication by 50-character passphrase.
The sample passphrase is the title of this paper (without blanks).

 There are d = 25 distinguishable images or Random Arts I1 , I2 ,   , I25 .
 After the rst block input, the machine represents
h1 as a base-25 integer.

 Each base-25 digit is displayed as an image. For
example, if h1 = (2A3    6E )25 , then I14 , I6 ,   ,
I3 , I10 , and I2 are displayed.

 The rest of the blocks are processed in the sameway.
 The user remembers M = 5 displayed images intotal.
Figure 4 shows the evaluation results. As usual,the performance of our echo-back scheme is plottedby marks (\o" in the case of Type 1 users while \x"
in the case of Type 2 users) and that of conventional
echo-o implementation is plotted by lines (solid linein the case of Type 1 users while dotted line in the caseof Type 2 users). The improvement from the echo-o
scheme is similar to that in the case of numeral display.
By contrast, the optimum strategy is very dierent.
In most likely mis-stroke probability region between
e=0.1% and 10%, the echo increases every C = 9
or 8 inputs. This is less frequent than in the case ofnumeral display.

5 Concluding Remarks
User authentication is an important entrance to secure systems. Currently, despite well-known vulnerabilities, password- or PIN-based systems are widelyused either alone or in combination with other authentication methods. Long meaningful passphrases canimprove security but degrade usability due to its long
input with echo-o on the screen. In order to solve
this echo-o problem, this paper proposed an echo-backscheme with the help of one-way hash function.
Since users can notice their mis-strokes before theynish the long inputs, the proposed scheme can signi cantly reduce the expected number of total strokes
required for one successful log-in. This reduction ratedepends on the mis-stroke probability per character. In
most likely probability region between 0.1% and 10%,
the reduction is larger than 50%. If a user nds it difcult to accept the additional memory burden for theecho, he can just ignore the echo the resultant performance is as good as that in the conventional echo-o
implementation, anyway.
Fortunately, in a wider area including the mis-stroke
probability region, we can use the same strategy ofhashing every 4 characters and remembering one digit
per hash. This can simplify the implementation. In an

User of Type1 (o & solid); Type2 (x & dotted)
150
140

Expected Number of Strokes

130
120
110

Optimum Strategy:+ Hash per∆C=9 strokes+ Memorize m=1 imagein each of the first
5 hashes

∆C=8

→
∆C<8

100
90
80
70
60
50
0.01

0.1
1
Mis-Stroke Probability [%]

10

100

Figure 4. Expected number of total strokes required for one successful log-in by the optimum strategy. Users are assumed to be able to memorize M =5 images in echo. For reference, the solid line
shows the expected number of strokes in the case of Type 1 users with echo off. This is reduced
to the circle marks (o) by the proposed echo-back scheme. Likewise, the dotted line is in the caseof Type 2 users with echo off. This is reduced to the cross marks (x) by the proposed echo-backscheme.

extended discussion for the replacement of the numerical echoes with simple but distinguishable graphics, wefound that the optimal echoes would be updated lessfrequently.
As a further research, a user study is needed as well
as a real implementation. The experimental study shall
include performance analysis not only in the number ofstrokes but also in the net time per log-in. It could also
include extensions of the proposed scheme: (1) the useof graphics or images instead of numerical characters,and (2) the parallel display of dummy echoes.

Acknowledgment
This work is partly supported by Research Assistance Program 2000 of the Asahi Glass Foundation.

Workshop on Cryptographic Techniques and ECommerce (CryTEC'99), Hong Kong, 1999.

2] R. Dhamija and A. Perrig. \Dej!a Vu: A User
Study Using Images for Authentication". In Proceedings of 9th USENIX Security Symposium (toappear)3] A. Evans, W. Kantrowitz, and E. Weiss. \A User
Authentication Scheme Not Requiring Secrecy in
the Computer". Communications of the ACM,
Vol. 17, No. 8, pp. 437{442, August 1974.
4] G. P. Purdy. \A High Security Log-In Procedure". Communications of the ACM, Vol. 17,
No. 8, pp. 442{445, August 1974.

References

5] R. Morris and K. Thompson. \Password Security:
A Case History". Communications of the ACM,
Vol. 22, No. 11, pp. 594{597, November 1979.

1] A. Perrig and D. Song. \Hash Vsualization:
A New Technique to Improve Real-World Security". In Proceedings of the 1999 International

6] G. Brassard. Modern Cryptology: A Tutorial.
Springer-Verlag, 1988. Lecture Notes in Computer
Science 325.

7] D. C. Feldmeier and P. R. Karn. \UNIX Password Security | Ten Years Later". In Advancesin Cryptology | CRYPTO'89, pp. 44{63, 1990.
Springer-Verlag. Lecture Notes in Computer Science 435.
8] Bruce Schneier. Applied Cryptography Second Edition: Protocols, Algorithms, and Source Code in
C. John Wiley & Sons, 1996.
9] S. Porter. \A Password Extension for Improved
Human Factors". In Abstracts of CRYPTO'81,
p. 81, August 1981.

10] C. P. P$eeger. Security in Computing. Prentice
Hall, 1989.
11] C. Shannon. \Prediction and Entropy of Printed
English". Bell System Technical Journal, Vol. 30,
No. 1, pp. 50{64, January 1951.
12] P. R. Zimmermann. The Ocial PGP User's
Guide. MIT Press, 1995.
13] P. Loshin. Personal Encryption Clearly Explained.
Academic Press, 1998.