Scientists Develop New Method To Improve Passwords

An anonymous reader writes "Scientists at Max-Planck-Institute for Physics of Complex Systems in Dresden, Germany have developed a novel method to improve password security. A strong long password is split in two parts. The first part is memorized by a human. The second part is stored as a CAPTCHA-like image of a chaotic lattice system."

Comments

RTA?

[del_diablo]

Well, It indeed silly. What is stopping us from just doing normal bruteforce?

Re:RTA?

[pushing-robot]

That's the one with the $5 wrench, right?

Re:RTA?

[del_diablo]

No, from the article i got the idea was:
1. Split password into 2 pieces, a normal password and a captcha part
2. Now if you bruteforce, you could miss on the second part, meaning bruteforcing will just take a bit more time
Meaning that "standard bruteforce" is still valid.

Re:RTA?

[Haedrian]

Standard bruteforce was valid?

There are [Dictionary]^[PasswordLength] possible combinations.

If I write an 8 character password with the keys I can see on my keyboard at the moment, you get - 6,095,689,385,410,816 permutations.

Using my 'very quick' calculations which are more than probably not very accurate- if using a 3.5 GHz processor which can hash and check each password in a single cycle (which is a very funny proposition indeed) - it'll take you 20 days. If the system upgrades to a 9 character password, that increases the choices and time by a factor of the Dictionary size, which is a bit less than 100.

Re:RTA?

[AC-x]

Captcha image is encoded using the user's password. To brute force you'd either need to check the captcha images for each password combination or brute force the whole string (password+captcha) which is twice as long so will take an order of magnitude longer.

There are plenty of other key stretching techniques so not sure why this is any better tho.

Re:RTA?

[Sky Cry]

A bot can't keep a list of checked passwords, because it's impossible to tell whether the password failed because of the static part or the part which is changing with every attempt (the captcha). Therefore there's no guarantee that your bruteforce will succeed in a certain time, that is after a certain number of attempts.

Re:RTA?

[nanospook]

If your password is to a system that is worth the effort, then it's likely going to lock out after 3 tries.. I realize you are speaking generically, but unless you can subvert that feature, you can't try more than N times without invalidating the account..

Re:RTA?

[zippthorne]

So.. they've invented.. password salting?

Re:RTA?

[Haedrian]

I am assuming the worst case scenario, in which an attacker has copied the passwords and usernames from the database server, and is trying to break the hash.

if there are 3 tries, then there's absolutely no point in putting the CAPTCHA thing suggested by the article, since it'll be a human trying them out.

Re:RTA?

[Anonymous Coward]

Not to mention such systems have problems of their own. They tend to make DOS attacks trivial. Try enough times on everyone's account and now everyone is locked out. If it is something like " lockout limited to per IP address" Things get a bit better, for both sides, with DDNS attacks.

Re:RTA?

[the_other_chewey]

...or brute force the whole string (password+captcha) which is twice as long so will take an order of magnitude longer.

So 1,000,000 is an order of magnitude more than 1,000? Is has twice as many zeros...
You have a weird definition for "order of magnitude".

Re:RTA?

[hweimer]

There are plenty of other key stretching techniques so not sure why this is any better tho.

You can only see the CAPTCHA text when you enter the correct password, a wrong password will just lead to random noise. Their claim is now that the presence of the CAPTCHA text cannot be detected by algorithms because to an algorithm, the picture will basically look the same in both cases.

I don't buy this. They study a system close to a continuous phase transition, meaning that it is self-similar, and there is no singular length-scale that shows up in any correlation function. By introducing the CAPTCHA text, however, they explicitly introduce such a scale, namely the size of the letters. This scale will result in a detectable feature in correlation functions, and of course only appears when the correct password has been entered. So, contrary to the authors' claim, it should be rather easy to spot when the correct password has been guessed.

Re:RTA?

[Anonymous Coward]

No, everyone here is saying that but it is completely off base. Salting only protects against a time-memory trade off, each individual password is still just as easily brute forced. In this case, it actually becomes significantly harder (potentially impossible with current techniques) to even check if the password you guess via brute force is correct, since the only way you know it is right is if you can break the CAPTCHA.

Re:RTA?

[Martin Blank]

Standard bruteforce has always been generally valid, though there are cases where it doesn't work as well such as account lockout and those places where logs are watched carefully.

If the password database can be retrieved, it generally works better, though a bit of salting helps to address that. Distributed computing solutions for rainbow tables help cut down the time needed to break these, and I imagine that places like the NSA devote both dedicated and spare cycles to building up their own rainbow tables (or more elegant but less well-known mechanisms).

Re:RTA?

[Threni]

How do you unlock it? Second password, probably. Also, many, many secure systems don't lock you out because it's a pain in the ass to get it unlocked. If you want to mess someone up and can't guess their password then lock their account up.

Re:RTA?

[Anonymous Coward]

Hi HWeimer,

If you read our paper you will see that for an incorrect password you will still be in a vicinity of the correct initial condition. The Lyapunov exponents will get this difference multiplied, but the picture for the final evolution will still be very similar nomatter whether the password is correct or not correct.

K Kladko

Re:RTA?

[johnsnails]

Im assuming its 3 orders of magnitude since its 10^3 times greater? correct me if im wrong... oh wait you will http://xkcd.com/386/

Re:RTA?

[mjwx]

That's the one with the $5 wrench, right?

Where did you manage to find a wrench for $5?

Re:RTA?

[hweimer]

If you read our paper you will see that for an incorrect password you will still be in a vicinity of the correct initial condition. The Lyapunov exponents will get this difference multiplied, but the picture for the final evolution will still be very similar nomatter whether the password is correct or not correct.

Sorry, but I still don't understand why your approach is different from a key stretching function. I suppose the result of the time evolution should be quite different as one will reveal the CAPTCHA text and one will not. But as I said, there will be signatures of the presence of the text in the correlations functions, from which you can deduce that you guessed the correct password.

Re:RTA?

[zippthorne]

But captchas are already broken...

Re:RTA?

[Anonymous Coward]

HWeimer - thank you very much for your question !))) You are very bright )

Nonlinear chaotic lattices spontaneously develop have structures from complete disorder as a result of time evolution - this is called order-from-disorder transition )) It has been studied in academia for 20+ years just for the beauty of it )) The number of lattice Hamiltonians is so infinite and rich that one can fit the parameters in such a way that the spontaneously correlation functions and structures will resemble text with any required precision )
The hamiltonian we used in the paper is the first step - by introducing more sophisticated Hamiltonians we can match pretty much any correlation function ))

Konstantin

Re:RTA?

[Anonymous Coward]

I am assuming the worst case scenario, in which an attacker has copied the passwords and usernames from the database server, and is trying to break the hash.

What they seem to be saying is that you take a long password, hash the first half and store the hash in a database. Then take the second half, and turn it into a captcha image, and store that in another database. Now if you want to brute force the database, you have to use an OCR-based system to attack the captcha half of the password. Or if you are trying to brute force a login, you have to do both the password and the captcha.

The immediate problem I see with this idea is that captcha's only work because you don't know what the text represented in the image will be. If I was going to attack one of those databases, I'd start a brute force against the hashes. Any time I got a positive crack on a hash, I'd just take the 10 seconds to look up the corresponding captcha since we have it and it doesn't change.

Or to put it another way, how does this do anything more than an existing random-image captcha on a site? The 3-tries method works well for protecting a single login from being attacked, but it can be used as a DOS attack as well. The captcha prevents an automated source from rapidly scanning multiple logins, or automating account creation process; it does nothing to stop a human.

Re:RTA?

[Anonymous Coward]

That's the one with the $5 wrench, right?

Where did you manage to find a wrench for $5?

NASA was selling it. They said it was a steep discount.

Re:RTA?

[Anonymous Coward]

Maybe he's an alien who does math in base-1000 instead of base-10?

Belated April Fool Joke?

[Tigger's Pet]

Not only does this not look to me like a particularly professional reporting site, if you follow the link on the page 'Which authors of this paper are endorsers?' you get the following;-

"No authors of 1103.6219 can endorse.
The weak password problem: chaos, criticality, and encrypted p-CAPTCHAs
Tetyana Laptyeva V.: Is registered as an author of this paper.
Not currently an endorser.
S. Flach and K. Kladko are not registered as owners of this paper"

If nobody is willing to endorse the paper then surely it's not been peer-reviewed and is, consequently at this time, worthless. It's no different to if I put a paper out there stating that I was going to produce safe passwords by generating random characters from snail-trails.

Re:Belated April Fool Joke?

[kestasjk]

That lists which authors of that paper endorse other papers.

Perhaps analyze this idea for its own worth rather than look for silly reasons to discard it? How about that it relies on generating a secure password already, which would be hard for people to memorize, how the blind couldn't use it, or how it's really just the combination of two already common ideas?

Re:Belated April Fool Joke?

[Uranium-238]

You're an idiot, that's what e-journal sites look like and I'm pretty TFA is an abstract of a new paper.

Re:Belated April Fool Joke?

[pushing-robot]

I think the concept is fairly straightforward, though: If you make it hard for a computer to determine the difference between the plaintext and garbage, it will be hard to brute-force decrypt. In theory, by making the plaintext into a captcha the computer will no longer be able to tell when it has successfully decrypted the image, so (again in theory) after every password attempt a human will have to read the "decrypted" image to see if it is correct or not, so a brute force attack would (in theory) take an incredibly long period of time.

I see a few problems, though, in that (a) even if a computer can't read a captcha, it could probably tell the difference between it and random noise, (b) the computer could take "likely candidates" and farm them out to Mechanical Turk et al., and (c) it's not practical for anything but short text messages, since the message is no longer readable by a computer.

I could see it used for encrypting other passwords, though: Encrypt your files using a long random password, then encrypt that password using this captcha system and a password you can actually remember.

Re:Belated April Fool Joke?

[Anonymous Coward]

you ARE pretty

Re:Belated April Fool Joke?

[Anonymous Coward]

It looks like you don't know a lot about arxiv. In arxiv papers are not endorsed, but authors. So ""No authors of 1103.6219 can endorse." means, that the authors cannot invite other authors to publish on arxiv. Laptyeva on the other hand was invited by someone who published several papers before on arxiv, so he may well have some credit.

How many times we need to explain thid

[skyriide]

Its not the difficulty (that is length, various enforcements against common dictionary words, mandated password change every few months or so) of password that matters. Its the users that do. Users will always find a way to use a variation of 'password', like password1, or pass-word-1 or something like that. The problem is that users just don't want/can't remember compex things. Thus the real solution is to store full blown AES key in a disk and educate users to keep it safe. Or even write a real random password on a piece of paper, but keep it not under the keyboard, but in their wallet If you want some laughs, just look at this blog post that describes the various ways user create insecure passwords.

Re:How many times we need to explain thid

[Anonymous Coward]

Or have a simple password which you keep for ever and use a RSA key.

Re:How many times we need to explain thid

[Anonymous Coward]

mod down, goatse link, sage sage sage.

Re:How many times we need to explain thid

[Anonymous Coward]

Well, if you actually read the paper, you'd have answers to those questions.

What they are proposing is a method that uses CAPTCHA-like systems to make the automating brute-forcing of the password much more difficult (but, since it's a CAPTCHA, it's still easy for a human to handle). The idea is that then you don't need the human to memorize as strong of a password: you can get the same level of security with weaker passwords. This won't let people use trivial passwords, but would allow you to greatly decrease the crazy/silly password requirements, because the decryption side becomes so difficult to automate. (You could always brute-force using a mechanical Turk setup, so you would need the user to pick a decent password, but as long as the search space is at least a few hundred thousand or million passwords, it's going to be impractical to hire CAPTCHA-readers to break it...)

The details of how they split a single strong password into two halves (a short bit that the human can memorize and a longer more secure bit that the user releases using CAPTCHA, and thus doesn't have to memorize) is quite interesting. Worth a read. This implementation might have mistakes that make it less secure than it seems at first, but the overall idea is really quite amazing.

Re:How many times we need to explain thid

[jhigh]

The real solution is to let the user have their dumb password that is easy to remember, but require them to also scan some biometric like their fingerprint or iris. This way, the only way that they can be compromised is by an attacker having access to both some physical characteristic in combination with their easy-to-guess password.

Re:How many times we need to explain thid

[Alex Belits]

That will work really well for remote access.

Idiots.

Re:How many times we need to explain thid

[subanark]

There are 3 basic ways a person can identify themselves:

1. What you know - like a password
2. What you have - like a keycard, or a one time password generator
3. What you are - biometrics

The advantage of 1 is that it can only be stolen when being used.
The advantage of 2 is that it can't be easily copied without removing it from the person.
The advantage of 3 is that it can't be stolen, but can be copied without being used.

I've seen places like air ports that use all 3. Swipe your card, punch in the pin, and scan your fingerprint. However, it is often not practical to require users to use all 3. A password is easy to give out, but can be easily forgotten. A keycard or password generator is a physical device that has to be issued to the individual. Biometrics requires special hardware that many users don't have, or you can afford to install on your building doors. Having fingerprint readers on your computer won't really help too much against if your computer gets compromised, while #2 can help deter this. On the other hand, if fingerprint readers become standard issue on computers, then many web sites can add it to their log in requirements (your computer would send a hash of your fingerprint based on the certificate of the requesting web site to avoid it being used for another site).

Re:How many times we need to explain thid

[Firehed]

Of course, that whole massive procedure around three-factor authentication goes to hell when the first guy holds the door open for the two people standing behind him. The biggest issue always has and will likely always be social - the person walking around in a jumpsuit with a toolbelt will, in almost all locations, be assumed to be on the maintenance staff and will go completely unquestioned as he attaches mystery devices to the network wiring. Basically, the sooner that we're taken over by the machines, the sooner we can finally have effective security.

Re:How many times we need to explain thid

[Anonymous Coward]

> There are 3 basic ways a person can identify themselves:

Actually 2. and 3. are pretty much the same. "what you have" includes finger prints and such. And you can lose your finger prints if you work with chemicals, so they are very much like a keycard.

There is also alternative of having a combination of 1. and 2. E.g. my local bank uses that. I have a password and a card with keys. Only the combination of those will grant me access.

Less used, but also existing peer identification also exists. It means that someone who is identified can identify others. E.g. to became a Debian developer, someone who is already a Debian developer needs to identify you. Gmail granted access during beta only to those who were recommended by existing users. Those examples are not really used to identify individual, but could be, in theory.

There could be other alternatives also.

> The advantage of 1 is that it can only be stolen when being used.

No, it can be "stolen" by simply asking it e.g. via phone or chat. I would guess that 90% will give their password this way, given that it is asked by someone who masters human hacking. E.g. I once received a phone call where there was an emergency (money was lost every minute) and I almost panicked and was ready to give the password, but luckily it was not asked and the problem was solved via another way. And I'm paranoid about security and I know a lot about hacking and security. That is why even 90% sounds a bit too small.

> The advantage of 2 is that it can't be easily copied without removing it from the person.

No, e.g. at one work place there are key cards which could be copied unnoticed remotely with hardware that is sell openly with a cost of less than hundred dollars.

> The advantage of 3 is that it can't be stolen, but can be copied without being used.

No. One guy lost his fingers because his car used biometric identification. And his car was also stolen. Also if you just drink something your fingerprints can be stolen and copied. I also think that it would not be impossible just to take a picture of someone and use that picture to create copy that can be used.

Re:How many times we need to explain thid

[Anonymous Coward]

or, use a crypto card for stuff that needs to be secured. I still maintain that using chip& pin cards is the best approach to internet security. It lets you pick your security token vendor (which bank you want), puts it under an existing, fairly robustly (outside of the US) enforeced set of laws, and ties the security system to the people who have the most to lose when it's compromised ... the banks. The banks in every wesetern country are already required to verify in some way who their customers are. This lets people trust crypto cards that aren't directly issued by a government (theirs or others), lets you have as many online ID's as you want, protects to a great extent (not perfectly) against almost every password attack, and ties the password to a financial transaction when auditing is necessary .... those places with a financial transaction. However, website operators are still capable of trusting the certificates without sending information back to the banks.

Epc fail

[Hognoxious]

Two days late, guys. HIYGCOTWO.

A key is just a lengthy password!

[Anonymous Coward]

If a typical user can't keep a short word or phrase safe, why the fuck do you think they'll be able to keep any sort of a cryptographic key safe?

Seriously, you key advocates are fools. You'll correctly identify passwords as being a weak point in many security implementations, but then your "solution" will be to suggest the use of a private key, which is nothing more than a lengthy password that's often stored in a file that can be easily stolen.

Yeah, that'll work great, replacing one password with another. Way to go.

Re:A key is just a lengthy password!

[Qzukk]

then your "solution" will be to suggest the use of a private key, which is nothing more than a lengthy password that's often stored in a file that can be easily stolen.

Except that if someone steals the USB dongle on my keychain, I'm likely to notice.

Sure, it's possible that there's malware on the computer copying all of my keys as I speak, but the same could be said for the keylogger copying all my passwords, so its pretty easy to establish that public/private keypairs are more secure than just plain passwords, given that they are significantly harder to brute force, for any reasonable protocol the key is never sent over the wire (the server asks the client to encrypt something in order to prove that it possesses the private key matching the public key), and they can provide for positive identification of both sides of the connection (given that the server has its own private key).

Maybe I should patent

[rossdee]

Heres an extra layer of security for your password.
You take another post it note and stick it to your monitor over the top of the one with your password on. To access your password just lift up the top sticky note.

Re:Maybe I should patent

[Haedrian]

"The use of opaqueness of tree-derived substances in 3 dimensional space in order to secure against password disclosure through movement of waverforms through translucent media".

There, picked out a name for you.

Re:Maybe I should patent

[Anonymous Coward]

"You take another post it note and stick it to your monitor over the top of the one with your password on. To access your password just lift up the top sticky note."

From your description, it sounds like I'd have to lift a whole monitor to get to the password on the monitor underneath.

Re:Maybe I should patent

[jpellino]

I was going to go with self-destructing sticky notes, disappearing-ink sticky notes, but yours is elegant in its simplicity.

Right so...

[Haedrian]

So if someone steals the password list off a server and wants to steal the admin passwords, all he has to do is to read the captcha himself, work it out (being a human and all that), then try to break the hash by adding the 'captcha answer' to the end of the string.

Sure it might make it harder for someone to try to steal passwords from a large list, but if you're only targetting admin (or specific ones) it'll actually make things less secure. You tell people they only need to remember half the password and the rest is "uberencrypted" and their half will be easy to remember stuff you can dictionary attack.

Re:Right so...

[Anonymous Coward]

No, the CAPTCHA is encrypted with the "weak" password.
You need to brute force the weak password before you get a readable CAPTCHA. Automatically determining whether a CAPTCHA is readable should hopefully be computationally intensive and error prone, frustrating a brute force search.

Something is wrong with that PDF

[Lord Lode]

It causes "ePDFViewer" (the random PDF viewer firefox and/or linux decided to bring as default option when opening such link in firefox) to hang for a minute and use 100% CPU whenever scrolling or zooming.

Re:Something is wrong with that PDF

[Anonymous Coward]

Same with Chrome default viewer on OS X.

Re:Something is wrong with that PDF

[Anonymous Coward]

Foxit Reader on Windows too. I think it's the gradients in the graphics.

More on topic: This is what is known as "polishing a turd". The Mythbusters showed that it can be done, but that doesn't mean it should be done.

Maybe the image changes.

[Anonymous Coward]

Maybe they mean that the CAPTCHA image is not static? I.E. you're picking two points in the lattice but the lattice moves around every time the image is generated, so the coordinates are not very brute-forceable since they are actually different on each password submission?

Seeding...

[Manip]

So let's just be clear, they've re-invented seeding a password?

Re:Seeding...

[Anonymous Coward]

So let's just be clear, they've re-invented seeding a password?

And this surprises you?

This is IT were the new is old and the old becomes new again!

I'm still looking at 1970s mainframe technology to see what I can port to the internet, give it a catchy buzz-wordy name, and then get my VC funding!

Right now, I'm looking CICS. I'm thinking of taking it, adding in some syntax of the language du jour, calling it Distributed Internet Control Knowledge - Just so I can hear PHBs say, "I want DICK!"

Wasn't April Fools a couple of days back?

[beaverdownunder]

Seriously... how does this help? Sure, it might give brute-force a harder time, but wouldn't people just brute-force the captcha? Hm.

Re:Wasn't April Fools a couple of days back?

[Anonymous Coward]

not if the captcha changes.

brute force doesn't really work on a constantly changing password because well, you tied abc123 and it didnt work, being that my password at the time was f00b4r. now my password it abc123 but you'r not gonna try it cause well, you already have.

This will not work

[houghi]

as long as I am not able to select my own login AND password.
I have a multitude of different logins that were given to me and that I can not change. I have been given a multitude of passwords that I am unable to change, because I am not the only one to use that specific login.

Also have more then one security key.

Oh and I need to change some of them each month. I could easily remember a 32 character password. But not if I need to change it every month AND if I need to remember anywhere between 10-30 AND need to know what login it belongs to AND some can't be that long.

So sure, you can blame the human. However that IS a factor that will not go away. And as long as logins and password are basically a "Hey, I tried to protect the data, so I am safe"-thing for IT people, nothing will change.

To often I see people that are resposible for the security try to find a technological solution for the social problem. Security is not a technical issue. It is a social process.

Re:This will not work

[stonewallred]

I read a lot about password security here, and I fail to grasp one basic thing.

How many passwords are "necessary"? In the sense lives or large amounts of money would be lost if they were breached?

How many passwords are more of dutiful "security"?

In a sense, how many passwords do you have, that someone would be willing, capable and likely; to bust your head open and steal the password from your pocket?

I have one important password, to my WoW account (yeah I know...). The rest are unimportant in the grand scheme of life, forums, email, FB, etc.

I don't bank online, or that would be an important one also.

I don't access any of these places other than on my personal computer, or work computer. Both which are located in my home, one in my study and the other in my office.

Re:This will not work

[Anonymous Coward]

The best password to take for the web based world be your email account.
Reset the rest from there.

Re:This will not work

[stonewallred]

Got a different password for each of my email accounts, which are different from my social networking sites, which are different from my WoW account.

Plus all my sites are under different email accounts, a separate email account for each site.

Only place I got a concern is fucktarded blizzard which requires you to use your email address as an account name, and the same email address and password on the game, the battlenet account management and on the forums.

Guess a better way to rephrase my question is, how many folks could just carry their passwords written down in their pocket and still be safe?

Re:This will not work

[prograde]

...because I am not the only one to use that specific login.

I cannot think of a single circumstance where this is necessary or a good idea.

Excuses for why is it the way it is don't count.

I think the key with this idea is

[fragfoo]

to improve password security and not to make a fail safe method. In a way that users can still create passwords like "123456" (they allways will, if they are allowed to), but by adding the captcha they will be harder to crack.

waste of verbage

[danwesnor]

The second component is transformed into a CAPTCHA image and then protected using evolution of a two-dimensional dynamical system close to a phase transition, in such a way that standard brute-force attacks become ineffective.

You don't need a bunch of mumbo jumbo to make a brute force attack ineffective, all you need to do is lock the account after x failed login attempts.

Re:waste of verbage

[whrde]

And now you've just opened up a new way do a denial of service!

Re:waste of verbage

[ftobin]

If brute-force attacks are inefficient, compromised password files are less dangerous.

Re:waste of verbage

[zome]

I found the method used by an old phone (don't remember brand and model) effective. If you enter incorrect password for the first time, it make you wait 10 seconds before you can try again. A second time, wait 20 seconds, third time, 40 seconds, 4th time, that 80 seconds for you, and it keeps going like that. It gives the real owner of the phone a chance to get it right, but if you brute force, the wait time goes up quickly

Re:waste of verbage

[Anonymous Coward]

I think you need to read the parent again.

This is about compromised password hash databases, not about attacks coming in via the UI.

Think Gawker:
http://yro.slashdot.org/story/10/12/12/2234252/Gawker-Source-Code-and-Databases-Compromised

That was a great example of a case where a weak hash made brute-forcing the passwords out of the hashes too easy.

Wrong.

[Anonymous Coward]

You have no idea what you are talking about. Key authentication sends a single use secret over the wire. The server does not have your password, and you are never giving your password to the server. This is far more secure. Learn first, then talk.

Re:Wrong.

[Anonymous Coward]

> The server does not have your password, and you are never giving your password to the server.

Neither does the server check, if your private key even has a password set on it. Or whether it's unique to the server in question (as opposed to one key for all logins). In most cases you'll end up with:

1. the mentioned 1 key for all logins
2. a weak or even no password 'protecting' it

Which leads to having pretty much all of your (SSH) logins compromised if your silly key gets stolen and the now lovely feature of password-less login becomes the dream of whoever stole it (and a 'stolen' key may simply be a drive-by grab from your browser, not Mr. TLA doing some cloak-and-dagger routine).

Yes, keys can be convenient and more secure (2-factor) compared to just passwords, but reality will fail those high goals 9 out of 10, IMHO.

Re:Wrong.

[Anonymous Coward]

reality will fail those high goals 9 out of 10, IMHO.

As opposed to just using plain passwords that fail 10 out of 10, since the malware installed by the browser hack to read your keys is also logging your passwords?

Re:Wrong.

[Anonymous Coward]

> plain passwords that fail 10 out of 10, since the malware installed
> by the browser hack to read your keys is also logging your
> passwords?

Not saying passwords alone are better. But neither are public keys in most cases. In fact, public keys CAN be just as insecure (see original post) as passwords...perhaps even less secure.
Assuming my keys got stolen by malware and every passwords gets logged by it as well, then every system I do not log in using passwords is still safe (assuming unique passwords), whereas if I use the same key on several systems, they can all be compromised even if I haven't logged in there since the malware was installed.

Only way to make public keys more secure:

1. Use unique keys per unique system
2. Passphrase-protect each key.

For maximum safety, 2 should be a unique passphrase per system-key. Of course, that gives you the exact same management headache passwords alone do. The same factor, that increases your security, namely having to *have* the physical key in addition to the passphrase is also increasing the PITA-factor. If you forgot your USB-stick with the keys at home, you can't log in, even if you remember the passphrase. So it's all a trade-off...and most if not all of them suck donkey balls.

Good Article

[Anonymous Coward]

I especially like Figure #2. Kind of looks like boobies.

Re:Finally, some real innovation.

[icebraining]

But they fail to realize that the private key is nothing more than a lengthy password

You don't quite understand how PKI works, do you?

and is in fact more susceptible to being stolen than a human-entered password is.

Uh, no, it's not, because a private key stays in one place - you computer - while the password is sent to each server, and you have to trust them to secure it properly. Which, as we have seen with Gawker, won't happen.

So when can I scan my eye to sign in to web..

[Anonymous Coward]

sites. Is that day coming? Even if it's not secure, it is though, right?, it would be fancy.

Thank you!

[Anonymous Coward]

The "3 strikes you're out" feature has been a feature of intelligent OSes (like VMS) for decades.

I suspect the reason it is not more widely implemented is ... wait for it ... MONEY. Someone can't login and gets locked out but needs in? Well, you have
to CALL A HUMAN to restore access. Humans cost MONEY. And no one wants to spend REAL MONEY for security. It's cheaper to take the economic
hits that bad security brings with it than pay the money to implement intelligent security up front. But this isn't really news, is it?

Re:Finally, some real innovation.

[Anonymous Coward]

the key itself can be password protected.

Please develop improved end user

[kdsible]

to use the new password. "now where did my sticky note go" -the religious capitalist "send me $50 to be saved"

Just my own problem with password systems

[bryan1945]

Different systems have different parameters. One required 5-8 characters, including 1 number and 1 capital letter. I ran into one that had to be exactly 6 characters, but no other restrictions. One had a requirement of a 'special' character, i.e. $ * # ! ) etc. I understand the restrictions, somewhat, but my passwords tend to be 10-15 characters long with numbers but no special characters. Sometimes a capital letter or 2.

Instead of creating new schemes, just let me use this-
"ijustgotanewpuppyandinamedhimbippyandhesverycute"

Brute force that for my Amazon account. It's a whole lot better than "borked" for that 6 character password scheme I mentioned above.

In plain terms

[Anonymous Coward]

This could be used with any existing password system. The changes required are only on the client side.

When the user chooses a password, he breaks it into two parts. One part is memorized and the other is turned into a CAPTCHA, evolved using some math, and encrypted. The encrypted image is stored to disk.

When the user wants to log in, he enters the memorized password. The client software decrypts the image from disk, derives the CAPTCHA with math and displays it. The user enters the CAPTCHA text. The client software can then send both parts of the password concatenated. So the server just gets one long password.

Assuming that no perfect AI exists for this, if someone compromises the client computer, then the password has a few more bits of strength than just the memorized password against brute force. If the server is compromised, then the password is hugely stronger than normal. Compare that to the case where if someone compromises the client computer without this system, then no hint to the password exists and it is impossible to guess the password. So while this system makes the server-side security stronger it greatly weakens the client-side.

Also note that it only works if the client system contains the encrypted CAPTCHA file. If you're trying to log into Faceville with this scheme from your sister's PC in another state then you don't want to leave hints of your password on her harddrive, and you don't want to be burdened by copying the file from your home computer. So it doesn't really work for a lot of common uses of passwords...

Another problem with this system is that it is too complicated: it would be very difficult to prove p-CAPTCHA is secure. I don't like relying on "round-off" approximations. This seems unnecessary for security, so an integer-based system would be preferred. I think all the weird chaos math is just to make the images look texty to make it harder to use an AI on. So instead of pretending it is adding security it would be better to pick a good bubbly procedural texture generator...

Another user mentioned that this is similar to password seeding. What he means is that your password can be used as a seed for a pseudo-random number generator, and before you send the password to the server your client PC will extend the password. As long as the attacker doesn't know what algorithm you chose, your account will be more secure than other users. You could also just hash your password and truncate the hash to the desired expanded password length. Password seeding is great because you don't need to drag a CAPTCHA file around with you. This would be a great browser plugin, hmmmm... So long as only a small percentage of users are using extended passwords, attackers probably won't take the time to break them.

Re:In plain terms

[Anonymous Coward]

In fact I have a better scheme than the paper that is a lot easier to prove security for, and doesn't weaken the password:

Have the client program accept a password from the user and internally generate a long random number. Encrypt the long random number with the memorized password and store it to disk.

When the user logs in, he will enter the memorized password into the program. The program loads and decrypts the long random number, concatenates it with the memorized password and sends it to the server.

This is better than the scheme in the paper because the encrypted file on disk doesn't give any hints about the password (it would just decrypt to a different random number if you guess the password wrong). It has the same disadvantage of needing to carry around a file.

I am not sure why they don't just write a short whitepaper on this better method if that is really what they wanted to achieve. Maybe I am misunderstanding their approach. I hope not. If they are storing the CAPTCHA on the server and sending it to the client then at best the scheme is no better than just adding a normal CAPTCHA to the login, and at worst is providing basically a password hash to anyone who enters your name they can brute-force offline.

Re:Finally, some real innovation.

[EdIII]

because a private key stays in one place - you computer

I think that is what he is pointing out. A regular password is stored in your brain. A private key is stored someplace on your computer and the computer itself could be stolen, or the data could be copied (border security Gestapo is an example). I also remember some articles about freezing active memory to retrieve stored keys in memory on systems that are secured (locked) but still running.

Of course it is not as simple as that and there is more to consider. Just pointing out that is what I think he meant by more easily stolen. He certainly does not compare the two methods fairly or thoroughly.

As for the article I am not really sure how innovative this is. CAPTCHA is a dying technology in its current implementation. It is purely based upon the premise the a human brain is a much better pattern recognition device then any artificial device we can currently come up with. This is inevitably being proven false. I give it two decades max. After which Turing tests are going to have to evolve to physically inspect the devices themselves similar to Blade Runner. They did not ask the "device" to recognize a pattern, only how it felt about a turtle on its back. Ohhh, and the testing was a little more dangerous to the tester.

Bruteforcing of interfaces is the simplest thing to defend against. My preferred method is using geometric progression to add a delay for every failed attempt. Lockout after three tries is a bit simplistic and user unfriendly. Brute forcing is going to use a hell of a lot more than three. Geometric progression makes more sense to me and is more user friendly.

The key to understanding this system

[mr.newt]

...is that the whole password cannot be decrypted in an automated way, because even though a computer program would quickly guess the short password (SP), the fact that the strong key (SK) is stored as a CAPTCHA prevents the computer program from obtaining it, even with the correct SP.

The point is not (as some seem to believe) to help the user memorize a longer password by storing part of it for him. This approach actually wouldn't introduce any added security, as you still have a single point of failure (the memorized short password).

Re:The key to understanding this system

[Anonymous Coward]

The key to understanding this system is that there is a random file (Strong Key) which is encrypted with the SP (Simple Password). The Simple Password is used to decrypt the (encrypted) Strong Key, which is then used to encrypt/decrypt stuff. It looks like these fellows came up with a way for the user to verify that their Simple Password was right... (if they type in the wrong Simple Password, they are shown a mangled Strong Key Image). Think of this as something like VisualHostKey for ssh.

Re:The key to understanding this system

[mr.newt]

That's how it works, but not the key. The important thing is that the SK can't be understood by a computer program because it's a CAPTCHA, and therefore can't be brute forced.

Re:The key to understanding this system

[Anonymous Coward]

Hi Mr. Newt )

You are exactlly correct ) This is the most important part in the paper

K. Kladko, Axioma Research

Capcha is stupid

[Anonymous Coward]

We should make a virus that will infest all servers that use captcha to delete them all from the internet. Captchas are stupid, and pointless. They just make it hard for real people to login. I know so many people that can;t read them, or even when you click the sound version. That is hard to understand. I am sick and dying and my mind is struggling just to keep living every day. Some times when I get really bad, I have trouble with those damn things. It seems to me that with a visual recognition algorithm you could bypass the captcha very easily.

hunter2 tag

[fractalVisionz]

From http://www.bash.org/?244321:

<Cthon98> hey, if you type in your pw, it will show as stars
<Cthon98> ********* see!
<AzureDiamond> hunter2
<AzureDiamond> doesnt look like stars to me
<Cthon98> *******
<Cthon98> thats what I see
<AzureDiamond> oh, really?
<Cthon98> Absolutely
<AzureDiamond> you can go hunter2 my hunter2-ing hunter2
<AzureDiamond> haha, does that look funny to you?
<Cthon98> lol, yes. See, when YOU type hunter2, it shows to us as *******
<AzureDiamond> thats neat, I didnt know IRC did that
<Cthon98> yep, no matter how many times you type hunter2, it will show to us as *******
<AzureDiamond> awesome!
<AzureDiamond> wait, how do you know my pw?
<Cthon98> er, I just copy pasted YOUR ******'s and it appears to YOU as hunter2 cause its your pw
<AzureDiamond> oh, ok.

Important: From Paper Authors

[Anonymous Coward]

Folks - we would like to confirm that this is NOT an april fools joke

You can try a demo of our method to encrypt files at

http://www.axiomaresearch.com/pcaptcha/CryptApplet.html

Sincerely,
T. Lapteva, S. Flach, K. Kladko

Re:Important: From Paper Authors

[jthill]

That doesn't work for me on x86_64 wheezy with the Sun java plugin, under chrome or ff, and when I download the jar:

~$ cd down
/home/jthill/down
~/down$ java -jar pcaptcha.jar
Failed to load Main-Class manifest attribute from
pcaptcha.jar
~/down$ java main -jar pcaptcha.jar
Exception in thread "main" java.lang.NoClassDefFoundError: main
Caused by: java.lang.ClassNotFoundException: main
at java.net.URLClassLoader$1.run(URLClassLoader.java:217)
at java.security.AccessController.doPrivileged(Native Method)
at java.net.URLClassLoader.findClass(URLClassLoader.java:205)
at java.lang.ClassLoader.loadClass(ClassLoader.java:321)
at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:294)
at java.lang.ClassLoader.loadClass(ClassLoader.java:266)
Could not find the main class: main. Program will exit.
~/down$

Here's my try at a non-academic rendering:

Password cracking is generally "known ciphertext" -- they have /etc/shadow or whatever, probably because they just confiscated your filesystem, and can brute-force keys looking for one that produces the ciphertext they stole. Humans practically never memorize passwords long enough to defeat a brute-force search.

This makes that not work, because what's stored isn't the ciphertext. Instead, what's stored is combined with the password you supply to produce an image, which you then iteratively modify a few hundred times. Whether you've supplied the right password or not, all the modifications will look similar -- except that if you've supplied the right password, one of the iterations, while looking a lot like all the others, will also be a captcha. The authors implicitly claim that it's as hard to answer the "is-it-a-captcha-at-all" question as it is to to decipher one, leaving a would-be brute-forcer the task of solving hundreds of thousands of captchas to find even a criminally weak password like 'm0ney'. Solving the right captcha gets you the rest of the real password, which will be a strong one, long and random.

==

Somebody else already questioned that implicit claim, and I'll point out that the paper is written as if the number of iterations is secret ("The attacker attempting a brute-force attack has to visually analyze each image obtained by time-evolution of each incorrect state") -- as if the legitimate user is going to eyeball 350 images at every login, looking for the right one.

But the real question is whether or not it's really that hard to distinguish the payload iteration from the rest.

Re:Important: From Paper Authors

[Anonymous Coward]

Jthill - thank you - will will check )

We use Mac Os X - it works fine on Safari ))

There is no main class in the jar - one needs to speciy the main class explicitely - please try

java -cp pcaptcha.jar CryptApplet

Re:Important: From Paper Authors

[jthill]

The password for nvidia-latest.crpt is "foo". Please decipher the captcha. It turns out your demo, along with turning less than 1K of shell script into 400K of encrypted file, also wiped the original. I've tried q, w, u, n, j, jv for the last letter(s). I figure you need the annoyance a lot more than I do.

Re: Paper Authors:From Re:Belated April Fool Joke?

[Anonymous Coward]

Dear Slashdot Readers,

This is a message from the authors of the paper.

We are a little sorry about the April 1 confusion - it is not a joke. The paper was submitted the day before April 1.

Sergej Flach and Tetyana Lapteva are researchers from Max Planck Institute. Konstantin Kladko did his Ph.D. at the same institute and works at a cryptography lab in SF Bay Area.

The reason endorser is not required is because we have been publishing in the field of chaos for years, and the archive site does not require pre-endorsement for such users. We have presented the paper several times before publishing and received multiple endorsements from our colleagues.

T. Lapteva, S. Flach and K. Kladko

just use 2 passwords

[Anonymous Coward]

You could make a few long passwords with the combination of 2 shorter passwords. Most things require 8 chars and many people have a few password sets where they make small changes to each iteration. Just take 2 of those passwords and place them back to back for 16 chars. Or you could even repeat the password two or three times.

Something so trivial makes brute force near impossible. Each character you add more than doubles the computing power required to brute force and significantly reduces the ability for people to guess the password correctly.

How is this new?

[loosescrews]

Sorry, but I don't understand how this could possibly be any better than combining existing password and CAPTCHA systems, which I am fairly certain has been done before. If the CAPTCHA and password didn't have a link between them it would likely be more secure. Their system only provides some benefit until someone leaks the algorithm for generating the CAPTCHA.

Is there something that I am missing?

Re:How is this new?

[Anonymous Coward]

The algorithm for CAPTCHA generation can be made public.
What is important is that for an incorrect password a PCAPTCHA is still generated and needs to be analyzed by a human.

Re:How is this new?

[Anonymous Coward]

Seconded!

Re:How is this new?

[Anonymous Coward]

Sorry, but I don't understand how this could possibly be any better than combining existing password and CAPTCHA systems, which I am fairly certain has been done before.

People are definitely confused about what this is for. This is not for client-server authentication, where a CAPTCHA and simply locking out after three goes is trivial to implement.

This is for securing ciphertext, where the attacker can try any number of passwords. When securing ciphertext, the key is password complexity.

Their idea is that you're going to take the existing password and use it to perturb an image to generate a captcha image. For the owner, the captcha is relatively easy to break, and it then reveals the rest of the password.

The attacker can try to decode the captcha or brute force every possible combination. (And the cpatcha doesn't have to be a dictionary word.)

If the CAPTCHA and password didn't have a link between them it would likely be more secure. Their system only provides some benefit until someone leaks the algorithm for generating the CAPTCHA.

My understanding is that the CAPTCHA is randomly generated and has no link to the password, so it's more bits of randomness.

i still prefer pixelock

[pyropunk51]

https://www.pixelock.com/

Easier passwords? That would be a god send!

[Anonymous Coward]

I hate long lines for confusing password's I would definitely like to see soon a better and more understandable password that I won't forget! But the CPU controlling what you say or type? Not sure If I would like to see something like that in the near future. they could perhaps use this new CLOUD based software that you see posted on the net Amazon.com has it. Sony has it. Microsoft has it as well so I'm wondering if they could use this in the future to be used for your passwords that would help a lot!

no joke - just quick science :-)

[Anonymous Coward]

arXiv, where the original article is stored, is a well-known and very respectable site, but it is specifically where researchers put their work *before* it has passed peer review. This allows their peers (i.e. other researchers in their field) to have a look at new work without time delay of review. If you want peer review, you'll have to wait for possible publication in some journal... or analyze the thing yourself ;-).

About endoring, read arXiv's FAQ: it seems to be not about judging the actual quality of a paper, only about keeping spam out.

Novel my ass

[Life2Death]

How is that novel when two of my banks not only do this already, but one-up it with a pin number along with a pictograph and password?