?

Log in

No account? Create an account
Passwords - Arvind Narayanan's journal [entries|archive|friends|userinfo]

Passwords [Aug. 29th, 2006|06:53 am]
Arvind Narayanan
[Tags|, ]

I changed my work password a while back because of the stupid policy, and promptly forgot it. I was on the line with the help desk last evening for several minutes, listening to music, and hung up because I had a damn presentation to complete (still do) and didn't have the patience. I knew that my new password was at a Hamming distance 1 from my old one, so I brute forced it!

Assuming I'm not alone in the way I pick passwords, there are two interesting questions: 1) what percentage of people change their passwords in a way that's easy to guess given the knowledge of their old password 2) if you have an existing large password database, can you crack significantly more passwords from a new server than if you didn't? There are so many nice experiments I can think of running if I had access to a password database. Oh well.

Anyway, the paper "A Method for Making Password-Based Key Exchange Resilient to Server Compromise" at this year's Crypto by Craig Gentry, Philip MacKenzie, and Zulfikar Ramzan* describes how to do remote authentication using low-entropy passwords. Unless a serious bug is found (this paper itself fixes a bug in a 2002 version) this should be the only way that anyone that cares about security should do password authentication over the Internet. I believe the protocol is already an RFC. How long before we start seeing adoption? My guess is that no one's going to change unless they get attacked.

*None of the three authors is in academia, which kind of explains why the paper is not online :(
LinkReply

Comments:
[User Picture]From: sdevarajan
2006-08-29 03:00 pm (UTC)

Crack that!

1) what percentage of people change their passwords in a way that's easy to guess given the knowledge of their old password

I'll assume that this is a pseudo-poll and answer that with "I do" - but then there are multiple websites that one visits each with a different account...rotation of passwords is another possibility...what goes around, comes around!:P
(Reply) (Thread)
[User Picture]From: kadambarid
2006-08-29 03:30 pm (UTC)

Re: Crack that!

That was by me, actually- a bit of troubleshooting for dad (who'd just started blogging).
Would've let sleeping words lie- but for the fact that they aren't true in his case :P
(Reply) (Parent) (Thread)
[User Picture]From: ephermata
2006-08-29 06:50 pm (UTC)
Craig is actually a grad student at Stanford right now.

From what I understand, one of the reasons this approach hasn't caught on has been due to patent issues. One of the nice things about the GMR work is that it is different enough from existing work that it may not fall under those patents. Unfortunately, you still have to rewrite all the existing software...

There's another protocol, SRP, which has had a library out for a while. I don't think it's seen that much uptake, unfortunately. (The protocol has also been revised several times and has no proof of security.)
(Reply) (Thread)
[User Picture]From: arvindn
2006-08-29 11:22 pm (UTC)
"Craig is actually a grad student at Stanford right now."

<slaps forehead> Of course. Sorry.

"Unfortunately, you still have to rewrite all the existing software".

Right. As I understand it, this may or may not involve client (human) participation. Ironically, if the server currently stores the password in the clear, then the upgrade probably does not impact the client. Weird.
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-02-20 01:02 am (UTC)

agree

I skimmed through that paper too, it's a very good paper!

-- your officemate summer 2007
(Reply) (Thread)
[User Picture]From: arvindn
2008-02-20 01:46 am (UTC)

Re: agree

oh hi elaine :)
(Reply) (Parent) (Thread)