I'm Sauvik.
I'm from Georgia Tech but this is work
that I did with collaborators at CMU.
Now I hate to be the bearer of bad news.
This talk has nothing to do with virtual reality
but right after this talk is over
I promise you'll go back to your regularly
scheduled programming.
I appreciate the creativity that the program chairs
had to put into putting my talk somewhere.
So anyway it's April 26, the UIST deadline has just passed.
You've been putting in long days.
All you want to do is Netflix and chill.
And yet you are presented with the dreaded login screen.
It's like it's been months since you last logged in.
What was your password again?
I'm pretty sure it started with password12345,
but that was the first one.
You've reset it several times since then.
It must be like qwerty or something.
So you try, you try, you try, and eventually
you just give up, fall asleep, and call it a day.
Anyone else relate to this problem?
So this scenario is one instantiation
of a broader class of problems that I
like to call infrequent authentication.
So this is when you need to login to accounts
with super long persisting sessions like Netflix,
Facebook, Twitter, what have you.
Or increasingly for the IoT devices
that this community and other communities
are developing where maybe you share
a physical device that you only access once in a while.
Like maybe a conference room or something
that you need to authenticate yourself
into but you do it maybe like once a week, twice a week.
For these situations you really need
secrets that are memorable so that you remember it
after a month, after a week, whatever, that are secure,
because otherwise there's no baseline value in having
the authentication at all, and that are deployable.
And this is an important one that's typically
forgotten in authentication work,
it needs to be something that is easy enough for users
to implement given the importance of the task.
So for example, I could just use a biometric reader
and put it on every single device
and give that information to every single account.
But I personally don't want to deliver my biometric data
and have it be secured by a bunch
of different third parties.
So in these situations what we really need
is some sort of combination of this usability, security,
and deployability.
I'm not going to go into each of these cells over here
but broadly speaking the existing solutions
to these sort of authentication techniques are
alphanumeric passwords, which we're all familiar with,
graphical passwords like Android's nine dot pattern
lock, and the Microsoft touchpoint password,
and of course biometrics that we all know about.
It turns out for infrequent authentication use cases,
graphical passwords provide a lot of great properties
in that they're very memorable, typically,
and that they require non-invasive
or no specialized hardware.
However, there is a problem, which
is that graphical passwords typically
have very weak security.
So there's a limited search space.
If you take Android nine dot as an example there's
a limited number of moves you can make.
And also it's easy to break usually
via common attacks like the dreaded shoulder surfing,
that everybody likes to talk about, where somebody is just
sort of looking over your shoulder
and trying to figure out what your password is.
Usually you can figure it out with one attempt.
And also, existing graphical passwords
are not built for this use case where you're only entering
your password in once a week.
They're typically built for the use case where
you're entering them like once, twice, four times,
ten times a day.
Like for your phone or for your computer or something
of that nature.
So what's really needed is this form
of graphical authentication that is quick to imprint,
so that you don't need to enter it ten times before you really
memorize it, that is long lasting,
so that you can go away for a week work on your UIST paper
and then come back and still remember it,
and that is resilient to common attacks,
like shoulder surfing, random guessing, brute forcing,
things of that nature.
So when we started thinking about the design space
for how can we approach this problem in a way that's
interesting, we were really inspired
by the ancient Greco Roman mnemonic technique
called the method of loci.
Many of you are probably familiar with this.
It traces its roots back millennia.
Actually ancient Greco Roman orders
used it to memorize speeches that they
used before there were lots of great external memory aids.
And it's still used by, quote unquote,
"memory athletes" today to memorize, for example,
arbitrarily long digits of pi.
The basic premise of this approach
is that all of us in our head have essentially
really strongly imprinted cognitive maps of places
that we know.
For example, your childhood home.
You can probably close your eyes right now
and imagine how to get exactly from your front door
to your living room to your kitchen to your bedroom
without batting an eye.
If you could bat your eye while your eyes were closed.
The key insight over here is that
the human visual-spatial memory system is clearly very strong
because it's been used for millennia and memory
athletes use it to this day and yet it
has not been thoroughly explored for the context
of authentication.
And so we thought maybe we should change that.
Maybe there's something to using this approach
for authentication.
So that led us to this research question which is,
are visual-spatial secrets, as opposed to just purely
graphical secrets, in a virtual memory palace
more memorable and secure than standard graphical passwords
like Android pattern lock?
In exploring that research question
we introduced this new form of authentication
called the Memory Palace in which secrets are encoded
as paths in a 3D virtual labyrinth
that the users can navigate using standard touch gestures.
So, how did we get there?
So broadly speaking we had these three steps.
We use an iterative design process
in order to get to the point where we could actually
evaluate and test this research question.
For time purposes I'm not really going
to go into this first step of our iterative design
process, which is perspective exploration,
but essentially we implemented a bunch of low fidelity
prototypes of encoding these visual-spatial secrets
as a two-dimensional path, or a three-dimensional path
navigated in third person or a three-dimensional path
navigated in first person.
And the upshot of all of that was palaces
should be three-dimensional and they
should be navigated in the first person perspective in order
to enhance memorability.
That makes sense, right?
That's how we navigate the real world
and that's how our visual-spatial memory has
been evolved to be taken advantage of.
So that's what we did.
So how did we design the system ultimately?
So at a high level view what we used
was procedural content generation techniques,
which has been talked about a little bit in the past
in this conference as well.
Essentially we implemented a proof
of concept version of the Memory Palace on Android using OpenGL
but I want to emphasize we don't really
see the Memory Palace as being useful as an everyday
authentication technique.
This was just a proof of concept to show that it could work.
So essentially we created a three-dimensional palace
that can be navigated in the first person perspective.
We employed procedural content generation techniques
to randomly construct visually distinctive rooms
and then we had users navigate the palace using standard touch
gestures.
So we started with this 21 by 21 grid but that's arbitrary.
In theory, the palace could be infinite.
As users get close to the edge we
can use procedural content generation techniques
to make the palace larger and larger and larger.
That gives us a nice property in that our search space is not
limited.
It's a theoretically infinite search space
which has some good security properties.
We used a genetic algorithm in order
to stochastically split this grid into Tetris room shapes,
you know the classic I, L, T, and block,
and then we placed doors between rooms along adjacent walls.
So if you start with this blank, simplified grid space
essentially what we did was we started
using this genetic algorithm to fill out
the grid space into these different Tetris shapes.
And then we placed doors randomly
along adjacent walls such that any two rooms that
are neighbors, there is a way for the user
to navigate to those different rooms.
But that wasn't enough.
So room shapes being distinctive is
good but you're still in this labyrinth
and labyrinths are tough to navigate through.
So we want each room to be visually distinctive,
so we added terms to the fitness functions
to not only generate the room divisions to be somewhat
distinctive but also so that each room looked
visually distinctive.
And the way we did that was essentially a coloring problem.
So we had a bunch of different floor and wall textures
and we ensured that adjacent rooms have different floor
and wall textures.
And we also wanted to make each door within each room
distinctive in some way.
And so each door was textured differently
and we also placed different artwork and decorations
around those doors such that each door could not
be confused for one another in theory at least.
And of course as you saw in the video,
users navigated the palace using touch gestures.
So in the Memory Palace authentication secrets
are specific paths through the space.
It's not just the start and the end point,
it's everything in between.
So if you double backed, that's part of your secret,
and that also makes the search space of the authentication
secret larger.
So of course to register a secret
you do the password, password confirmation approach.
So you start recording.
You're self-navigating through the palace.
And then you put it in again and then
that's a registered secret.
Of course, we gave users the ability
to freely explore the procedurally generated palace
first so that they could get familiar with the space.
And then to authenticate, a user simply
needs to recreate the preregistered path exactly
the way they put it in.
OK.
So that's the system.
So now let's talk a little bit about
if it actually works relatively better
than a standard graphical password.
So in general, we had these three hypotheses
going into the evaluation.
Controlling for secret complexity,
and this is important because we wanted an apples to apples
comparison, and relative Android nine
dot pattern lock, which we use because it's
a very popularly used graphical password out there
and we just wanted to compare it to something that people
are familiar with.
We had the following three hypotheses.
One, that visual-spatial secrets in the Memory Palace
should be more memorable after a period of extended disuse
than Android nine dot secrets.
Two, that visual-spatial secrets in the Memory Palace
should be more resilient to common attacks like shoulder
surfing.
I'm not going to argue for the other common attacks
like brute forcing because that just
follows from the theoretically infinite search space.
And three, that visual-spatial secrets in the Memory Palace
should be probably slower to enter because you're not just
drawing a shape on a screen.
But we wanted to quantify what that difference might be.
So broadly speaking we ran a counterbalance within subjects
experiment with two weeks separated by one--
with two sessions separated by one week.
In the first session, we essentially
showed participants a nine dot and complexity
controlled Memory Palace secret and counterbalanced order.
We had to give them a secret instead of having them generate
one so that we could ensure that the complexity of the secrets
was the same because if one was super simple
and the other was very difficult then that's not exactly
an apples to apples comparison.
And then we showed the participants the secret twice
and then we asked them to replicate the secret themselves
to show that they had learned it.
And if they didn't we would show it to them again
but in practice no participant needed more than two attempts
in order to show that they had learned it
in that particular session.
The second session was at least seven days later.
Some participants came in eight days later, but on median
seven days.
And essentially the first thing we asked them to do
is recreate their Memory Palace and/or nine dot secret
in counterbalanced order again.
We gave them three attempts to do so.
We give them no visual aids, no memory
aids at all, just recreate what you learned in the past.
And if they didn't do it in three attempts
we considered it a failed attempt
to remember their secret.
Otherwise, they would have remembered their secret.
And then, after that, in order to test the resilience of this
technique against a common attack-- shoulder surfing--
we essentially recorded one of us entering
the secret for a nine dot or memory palace
from an over-the-shoulder perspective
and showed it to participants twice.
And then we asked them to recreate
the secret they had just seen in the video
a few seconds earlier.
So our measures are basically one to one correspondence
with the hypotheses we had.
So for memorability we measure the accuracy of the user's
re-entering their secret in session two.
For shoulder surfing we measured the accuracy
of breaking the over-the-shoulder secret shown
in session two through that video.
And then finally for speed of course
we trivially measured the speed of the entry.
So we recruited 20 participants from the greater Pittsburgh
area.
10 male, 10 female, age range of 18 to 44, and here
are our results.
So our results are pretty good.
So memorability after one week, 70% of users
remembered their memory palace secret after one week
compared to just 30% of users who remembered their Android
nine dot complexity controlled secret, which is great.
It's a 2x improvement, more than 2x improvement.
The shoulder surfing results are even better.
Only 5% of users were able to recreate
the over-the-shoulder perspective
video for the Memory Palace versus 65% who
were able to recreate the over the shoulder
perspective of the Android nine dot secret,
again complexity controlled.
And then finally entry speed, well, the result
was not statistically significant.
We imagine it's just because we didn't
have enough participants for this particular result.
But the memory palace was a little bit slower.
About 4 seconds, which would be terrible
if you had to do this 10 times a day,
but if you have to do it once a week it might be tenable
given the significant improvements
to memorability and security over there.
Now before I conclude, I just want
to state that one of our co-authors, Taehoon Lee,
was an undergraduate who worked on this project.
He did a lot of work regarding the development
of this project.
He wanted to do a PhD but unfortunately
he passed away in 2017 and never was able to get there.
I have no doubt that he would have
been great at doing research.
And this paper, I hope, serves as a good tribute
to his memory.
So with that said, that was the Memory Palace,
I'm Sauvik, happy to take questions.
[APPLAUSE]
Wonderful, I see a question in the back there.
Hi, I'm Katharina Reinecke from the University of Washington.
This is great work.
I love the paper.
I am someone who is notoriously bad at navigating
environments and new houses, new buildings and so on.
So one thing that I was wondering
about is if you were able to personalize the environment
and let's say give me via Google Street View
my own neighborhood or something,
do you think this would increase quite a bit?
Have you been thinking about this?
Yeah, that's a great question.
People certainly have different perceptions
of their ability to wayfind in a 3D space, that's definitely
true.
Almost every human though is better at that
than remembering arbitrarily long strings
of alphanumeric characters though,
which is why we decided to pursue this approach.
I think the second part of your question
though which is, can we personalize this,
I think is really interesting.
We didn't actually explore it.
There's a trade off.
If I give you the street view of your neighborhood,
there's more information an attacker can exploit.
Because there might be more contextual
information of the Seattle area or something like that.
They can potentially look and then
they can use entropy based techniques to figure out,
OK you're more likely going to go left here than right,
or something like that.
But I do think that, relative to the usability gains,
that's an open question.
Is the usability gain so much better than the security loss?
I'm not sure but I think that would be
super interesting to explore.
Yeah.
How did you give the participants
what is the actual path to walk through?
Was it as a viewing of a walk or as a top down map?
Yeah.
So it was actually a viewing of the walk itself.
So when showing participants the path to follow we had them
look at one of the researchers who entered the path for them,
and they were asked to replicate that path.
That's exactly over the shoulder.
That is exactly over the shoulder, yeah.
But in this perspective it was interactive.
It was like, first you go up, them you go right,
then you go up.
It wasn't, just watch me do this thing.
Hi, I'm [INAUDIBLE] from Stanford University.
Great work, I really like it.
One thing I think about is for regular alphabet-based
passwords, we already build a lot of training
so that people can create a secure password for that.
Do you have any insight on how to make
user create a secure password for your kind of password?
Yeah, that's a great question.
I think with alphanumeric passwords
we benefit from decades of experience of it.
So in short I don't actually know what would be the best.