Laur­en Ipsum and the Tim­ing At­tack

Laur­en Ipsum is try­ing to get past Jane Hecate, a lit­tle old lady who holds the Book of Passwords. Jane is older and can't see well, so she has to spell out Lauren's guess lett­er by lett­er to check wheth­er it's the right password. How can Laur­en use this to her ad­vantage?
A story about com­put­er sci­ence
and other im­prob­able th­ings.

Below is a lit­tle game that lets you try to beat Jane your­self. The sec­ret password is pic­ked at ran­dom from a list of 10,000 di­ctiona­ry words, and the box will show you valid words to make it a bit eas­i­er. No peek­ing at the sour­ce code. :)

(I'll give you a hint. Try ਲ.)

Spoil­ers below...

What you are doing is a tim­ing at­tack. If check­ing a com­plete­ly wrong password takes less time than a mostly-wrong password, you can use that in­for­ma­tion to guess the password, one lett­er at a time.

The at­tacker's strategy is pre­tty much the same as the one used in the children's game han­gman. It's stuff like this that makes build­ing secure sys­tems very hard. Make just one mis­take, and com­promis­ing your sys­tem be­comes lit­er­al child's play.

To fix this par­ticular in­for­ma­tion leak, Jane should take ex­act­ly the same amount of time to re­turn her yes/no an­sw­er, re­gardless of how close the guess is to the password. For ex­am­ple, she can simp­ly keep check­ing lett­ers even if they are in­cor­rect. Or she could use a stop­watch and al­ways wait to give her an­sw­er until 30 seconds have pas­sed. Check­ing passwords is one of the few cases where an al­gorithm must be made slow­er to work cor­rect­ly.

Like what you read? Laur­en Ipsum is a children's story about com­put­er sci­ence. Buy a copy and help us trans­late it into Spanish, Por­tuguese, and other lan­guages.