Towards reliable storage
of 56-bit secrets
in human memory

Southern Methodist University

March 25, 2015

Usenix Security Symposium 2014

Stuart Schechter

Microsoft Research

Joseph Bonneau

Princeton University

Motivation: password leaks

Motivation: really weak passwords

Digression: passwords shouldn’t leak

user: jcb

pass: 12345

user | pass

-------------

jcb H(12345)

user | pass

-------------

jcb H(12345)

user | pass

-------------

jcb indexjcb

verify(indexjcb, 12345)?

user | pass

-------------

jcb MACk(12345)

Solution 1: secure storage

Solution 2: secure computation

k

MACk(12345)?

Sometimes, a really strong secret is actually worth some effort

Public domain image: http://www.bing.com/images/search?&q=eggs+in+one+basket&qft=+filterui:license-L1&FORM=R5IR37#view=detail&id=F4CB4E9B5972A91AB870ED870BDDE7E4F3268805&selectedIndex=0

How to store secrets in humans?

How to store secrets in humans?

Platters

Read/Write Head

The standard computer science approach would be to look at the problem this way

Modeling human memory as a disk

Time

write

read

FAIL

Kaufman, Perlman and Speciner
Network Security: Private Communication in a Public World

2002

Humans are incapable of securely storing high-quality cryptographic keys… they are also large, expensive to maintain, difficult to manage, and they pollute the environment. It is astonishing that these devices continue to be manufactured and deployed. But they are sufficiently pervasive that we must design our protocols around their limitations.

A more accurate model for human memory

http://en.wikipedia.org/wiki/File:Wavecut_platform_southerndown_pano.jpg

Learning through spaced repetition

Time

write

read

SUCCESS!

Hermann Ebbinghaus

1850-1909

The Forgetting Curve

(1885)

“Learning”

SuperMemo: standing the test of time

Spaced repetition for passwords

Step 1: Type user-chosen password

User Name

stuart

Password

●●●●●●●

Spaced repetition for passwords

Step 2a: Type the random words as displayed

User Name

stuart

Password

verified

●●●●●●●●●

first nurse

Security code

Spaced repetition for passwords

Step 2b: Type the random characters as displayed

User Name

stuart

Password

verified

●●●●●●●●●

Security code

vnun

Spaced repetition for passwords

Step 3: Add increasing delays before showing the hint

User Name

stuart

Password

verified

●●●●●●●●●

Security code

Spaced repetition for passwords

Step 4: Wait until users can type without prompting

User Name

stuart

Password

verified

●●●●●●●●●

Security code

Look ma, no copying!

Spaced repetition for passwords

Step 5: add more codes and repeat

User Name

at least 4 characters

stuart

Password

verified

●●●●●●●●●

Security code

●●●●

●●●●

clxa

Spaced repetition for passwords

Step 5: add more codes and repeat

User Name

at least 4 characters

stuart

Password

verified

●●●●●●●●●

Security code

●●●●

●●●●

clxa

How big of a code do we need?

Digression: Estimating cost via Bitcoin

2013: 275 × SHA-256, US$250M rewards: US$8B/280 in 1 yr

2014: 280 × SHA-256, US$400M rewards: US$400M/280 in 6 mo.

256 + 214 stretching = 270 = million-dollar security (web)

256 + 224 stretching = 280 = billion-dollar security (encryption)

How to represent a 56-bit secret?

binary

2

56

11001111100111001010110100000100000101111101000110110000

decimal

10

17

27224896519905946

hexadecimal

16

14

55a108b f36380c

letters

26

12

rlhc zwps nffp

Base58Check

58

10

jTCaF fjqXq

short words

676

6

hem trial one by sky group

Diceware

7776

4.3

creek moo adams klaxon

poem?

Our word list: 3-5 letters, common, ☺

able abuse acid acorn acre actor add adobe adult aft age agile agony air alarm album alert alive ally amber ample angle anvil apply apron arbor area army aroma arrow arson ask aspen asset atlas atom attic audit aunt aura auto aware awful axis baby back bad baker bare basis baton beam beer begin belly bench best bias big birth bison bite blame blind bloom blue board body bogus bolt bones book born bound bowl box brain break brief broth brute buddy buff bugle build bulk burst butt buy buzz cabin cadet call camp can cargo case cedar cello cent chair check child chose chute cider cigar city civil class clear climb clock club coal cobra code cog color comic copy cord cost court cover craft crew crime crown cruel cups curve cut cycle daily dance dark dash data death debt decoy delay depot desk diary diet dim ditto dizzy dose doubt downy dozen drawn dream drive drop drug dry due dust duty dwarf eager early easy eaten ebb echo edge edit egg elbow elder elite elm empty end enemy entry envy equal era error essay ether event exact exile extra eye fact faith false fancy far fatal fault favor feast feet fence ferry fetch feud fever fiber field fifty film find first fit flat flesh flint flow fluid fly focus foe folk foot form four foyer frame free front fruit full fume funny fused fuzzy gala gang gas gauge gaze gel ghost giant gift give glad gleam glory glut goat good gorge gourd grace great grid group grub guard guess guide gulf gym habit half hand happy harsh hasty haul haven hawk hazy head heel help hem here high hike hint hoax holy home honor hoop hot house huge human hurt husk hyper ice idea idle idol ill image inch index inner input iris iron issue item ivory ivy jade jazz jewel job join joke jolly judge juice junk jury karma keep key kid king kiss knee knife known labor lady laid lamb lane lapse large last laugh lava law layer leaf left legal lemon lens level lies life lily limit link lion lip liter loan lobby local lodge logic long loose loss loud love lowly luck lunch lynx lyric madam magic main major mango maple march mason may meat media melon memo menu mercy mess metal milk minor mixed model moist mole mom money moral motor mouth moved mud music mute myth nap navy neck need neon new nine noble nod noise nomad north note noun novel numb nurse nylon oak oats ocean offer oil old one open optic orbit order organ ounce outer oval owner pale panic paper part pass path pause pawn pearl pedal peg penny peril petty phase phone piano piece pipe pitch pivot place plea plot plug poet point polo pond poor poppy porch posse power press price proof pub pulse pump pupil pure quart queen quite radio ram range rapid rate razor real rebel red reef relic rents reply resin rhyme rib rich ridge right riot rise river road robot rock roll room rope rough row royal ruby rule rumor run rural rush saga salt same satin sauce scale scene scope scrap sedan sense serve set seven sewer share she ship show shrub sick side siege sign silly siren six skew skin skull sky slack sleep slice sloth slump small smear smile snake sneer snout snug soap soda solid sonic soon sort soul space speak spine split spoke spur squad state step stiff story straw study style sugar suit sum super surf sway sweet swift sword syrup taboo tail take talk taste tax teak tempo ten term text thank theft thing thorn three thumb tiara tidal tiger tilt time title toast today token tomb tons tooth top torso total touch town trade trend trial trout true tube tuft tug tulip tuna turn tutor twist two type ultra uncle union upper urban urge user usual value vapor vat vein verse veto video view vigor vinyl viper virus visit vital vivid vogue voice voter vowel wafer wagon wait waltz warm wasp

Putting it to the test

90 sessions

Congratulations! You have learned the first two words of your security code.

We have added another two words. Just like the first two words, once you have learned them, you can type them without waiting for the hint to appear.

Most users “got it”

Four failed to learn the 2nd code

p=.4

p=.2

p=.4

  • “imagine my disappointment when I was rewarded for memorizing the first code by having another one added. I envisioned having code after code added to the end until infinity but I discovered that if I refused to play the game at all then the length of the code never grew more.”

  • “it was kind of clear after learning the first pair that this would just result in a third pair and a fourth pair and ...
    I have to admit that I was kind of pleased that it worked and I wasn't forced to learn more and more ... Hooray!”

  • “I'd rather wait a few seconds and have a shorter code.”

  • “Your system should have recorded that I NEVER NOT ONCE typed it in at all before the ``hint'' appeared. I doubt my dog would feel like memorizing password just to be given more passwords to memorize. I mean are you serious? If there are people that fell for that please do not tell me as I would be very disappointed and fearful for the future of humanity. lol”

They were learning. But, damnit, they were not going to let us know they were learning!

Three days after participants completed the attention study…

Followup results

(after 3+ days)

(after 17+ days)

Most errors are “genuine” recall errors

(fixable)

(mostly not fixable)

(not fixable)

Modest delays to login

  • Median delay: 7.7 s
    • Faster by 2s for letters
    • No difference in typo rates
  • Median total delay: 11m 53s

Most people didn’t write codes down

(actually hurt recall)

Better than user-chosen passwords without repetition

Komanduri et al., USENIX Security 2014

    • Tested various password policies
    • One repetition (at end of single session)
    • Recall period 2-5 days after study (vs. 3-7)
    • Recall rates maxing out at ~74%

Published studies have never found random passwords are less memorable!

  • Zviran, Haga 1990
  • Bunnell et al. 1997
  • Yan et al. 2000
  • Stobert 2011

Some passwords are worth 5-10 aggregate minutes of training

Kaufman, Perlman and Speciner
Network Security: Private Communication in a Public World

2002

Humans are incapable of securely storing high-quality cryptographic keys… they are also large, expensive to maintain, difficult to manage, and they pollute the environment. It is astonishing that these devices continue to be manufactured and deployed. But they are sufficiently pervasive that we must design our protocols around their limitations.

Designing around human memory

  • Training period
    • Authenticate via your chosen password
    • Learn random assigned password during each login

  • High-security period
    • Authenticate via your assigned password

Next steps for spaced repetition

  • Optimize, optimize, optimize...

  • Extend to other authentication systems
    • Touchscreens?

  • Apply targeted rehearsals
    • Blocki & Blum, ASIACRYPT 2013

Many other memory training effects!

  • Generation effect
    • Make users fill in the blanks
  • Depth of processing effect
    • Make users convert the password
  • Dual coding effects
    • Show multiple versions

Acknowledgements

  • Ross Anderson (Cambridge)
  • Craig Agricola (IBM)
  • Cristian Bravo-Lillo (CMU)
  • Bill Bolosky (Microsoft Research)
  • Paul van Oorschot (Carleton University)
  • Cormac Herley (MSR)
  • Arvind Narayanan (Princeton)

Try it yourself!

experiment.research.microsoft.com

“It was surprising that you did this follow up, because I did not expect it. After having to enter the codes so many times,
the words are branded into my brain.”

Storing Keys In Humans SMU - Google Slides