Researchers make weak passwords strong with CAPTCHAs plus an algorithm

Their encryption tool can foil brute-force attacks, they say

Researchers have found a way to get around the persistent problem of remembering strong passwords -- break them in two in such a way that one part is easy to remember and is used to encrypt and decrypt the other part that is long and complex.

The Java-based method employs CAPTCHAs as the vehicle to store the complex halves of passwords, says a team led by researchers at the Max Planck Institute for Physics in Dresden, Germany, in their paper "The weak password problem: chaos, criticality, and encrypted p-CAPTCHAs."

DEEP DIVE: 15 genius algorithms that aren't boring

These CAPTCHA images are encrypted using the simple half of the password in combination with a class of mathematical algorithm known as chaotic lattices, says Konstantin Kladko, one of the paper's authors, who works at Axioma Research in Palo Alto, Calif.

To retrieve the complex half of the password, users enter the easy-to-recall password fragment and the algorithm decrypts the CAPTCHA. Users copy the password from the CAPTCHA to decrypt protected files, Kladko says.

He says his team expects that within a month or so it will set up a Web page where users can download a Java applet that performs the encryption and decryption.

The team chose chaotic lattices to encrypt the CAPTCHAs as a way to get around brute-force attacks against the encrypted CAPTCHAs. Generally brute force would be effective because the password used to protect the CAPTCHA is weak, just the kind of thing brute-force attacks are designed to defeat.

But in this case, every password the brute force attack tries will generate a CAPTCHA that results in an image that the brute-forcing computer will interpret as decrypted. A human is required to determine for sure whether the image actually depicts something that might be a password.

Since every attempt will require human interpretation, the brute-force attack essentially becomes manual and therefore ineffective, Kladko says.

This is possible because the algorithm chosen takes seemingly random data -- the encrypted CAPTCHA -- and creates something structured out of it. Computer analysis of CAPTCHA images is such that it detects this structure, but still can't actually read it. So the brute-force application calls on a human to decide whether it has succeeded, Kladko says.

While the researchers used a particular algorithm called a non-linear Hamiltonian two-dimensional lattice system, there is a whole class of similar tools that Kladko describes as order-from-disorder algorithms.

In practice, if a user wanted to, say, encrypt a Word file, the person would do so using a commercial encryption application and jot down the password and split it into the two parts, easy and complex. The user would then go to the website Kladko and his colleagues plan to set up, create a CAPTCHA of the complex part and encrypt it with the easy part.

To decrypt, users enter the easy password to decrypt the complex part then enter that to decrypt the Word file. The website will have a tool that automatically applies the cleartext password to the encrypted file, Kladko says.

Learn more about this topic

Military wants full disk encryption for iPhone, Android smartphones 

20 hot IT security issues 

iPhone attack reveals passwords in six minutes

Insider Tip: 12 easy ways to tune your Wi-Fi network
Join the discussion
Be the first to comment on this article. Our Commenting Policies