Protecting against dictionary attacks

| Comments (6) | TrackBacks (76) |
The reason that the Secret Service's DNA key-cracking network works is that people are encrypting their files under keys generated from their passwords. People choose easily guessable passwords, which makes them easy to attack.

There are a number of countermeasures to this kind of attack:

  1. Use a non-guessable password or passphrase. There are algorithms for generating memorable and high-entropy passwords. See, for instance FIPS 181. Unfortunately, retraining users is very hard.
  2. Slow down the password->key transformation. There are a large number of techniques available to make the process of computing the encryption key from the password slower. The general idea here is that users will accept a small delay (order 1 second) in the first decryption in order to have advanced security. If you imagine that the attacker has to try a million keys--this is a very small number--even at 1 second a key we're up to about 300 CPU hours of computer time.
  3. Make it more difficult for attackers to detect whether a given key is correct. For instance, some compression schemes would require you to decrypt the entire file, thus slowing down trial decryption somewhat.

The second strategy is probably the most attractive. It can be implemented by the software vendors and doesn't require new user behavior. If I were a criminal who expected my communications to be tapped by the FBI, I would definitely want my vendor to implement something like this.

UPDATE: Replaced FBI with Secret Service (see the original post).

76 TrackBacks

Listed below are links to blogs that reference this entry: Protecting against dictionary attacks.

TrackBack URL for this entry: http://www.educatedguesswork.org/cgi-bin/mt/mt-tb.cgi/193

womens health from womens health on August 26, 2005 11:42 AM

womens health Read More

ringtones for nokia from ringtones for nokia on August 27, 2005 11:09 PM

ringtones for nokia Read More

Protecting against dic... Read More

LOOK AT THIS LINK from Monika Rothenwchier on November 30, 2005 3:29 PM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

ass from Johnathan Javinen on December 11, 2005 5:07 PM

Protecting against dic... Read More

ass-like-that from Schmidt Eckhart on December 12, 2005 4:21 AM

Protecting against dic... Read More

bare-ass-women from Leitsch Richard on December 12, 2005 5:37 AM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

booty-babes-ass from Pekka Jauhiainen on December 13, 2005 4:14 AM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

tit-and-ass from Martina Weser on December 13, 2005 10:37 PM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

closeup-ass from Maguus Lisbjerg on December 14, 2005 6:05 AM

Protecting against dic... Read More

Butts from Sarah Schmidt on December 15, 2005 2:07 AM

Protecting against dic... Read More

yana-round-ass from Isabel Schacider on December 15, 2005 2:08 AM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Naked prison uncensored from Indian nude video clippings on December 17, 2005 12:41 AM

Mom and son free pics galleries Adult cartoonsfree thumbnails Free japan school girls South india movie... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

boobs-boat from Christing Bremes on December 25, 2005 4:47 PM

Protecting against dic... Read More

black-tits-milfs from Margamlu Rovwssonwall on December 26, 2005 4:31 PM

Protecting against dic... Read More

Protecting against dic... Read More

tiny-teen-tits from Rummel Alexanda on December 26, 2005 4:52 PM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

hot-women-boobs from Anni Ca Soderovist on December 28, 2005 1:09 AM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

jean grae from Jeaneas Fluns on December 29, 2005 10:31 AM

Protecting against dic... Read More

anime-boobs from Manpeb Spiess on December 29, 2005 9:39 PM

Protecting against dic... Read More

boobs-smoking from Louise Forsmark on December 30, 2005 4:44 AM

Protecting against dic... Read More

cream-tits from Petrica Haggblom on December 30, 2005 5:00 PM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

tits-lactating from Raffaela Marafante on January 1, 2006 6:47 AM

Protecting against dic... Read More

Payday Loans from Payday Loans on January 18, 2006 2:15 PM

Payday Loans is a niceblog. Read More

Free Ringtones from Free Ringtones on January 23, 2006 10:29 AM

Free Ringtones Read More

drug-virility-ex from Mariche Van Dyk on February 9, 2006 4:59 PM

Protecting against dic... Read More

sexual-enhancement from Jonathan Liedholm on February 10, 2006 5:12 AM

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

Protecting against dic... Read More

genes-sense-of-smell from Kristina Serebrink on February 17, 2006 8:42 AM

Protecting against dic... Read More

sexy-perfume from Sulnierd Dieetf on February 19, 2006 2:12 AM

Protecting against dic... Read More

sexy-perfume from Sulnierd Dieetf on February 19, 2006 2:12 AM

Protecting against dic... Read More

6 Comments

PKCS #5, described in RFC 2898, has a widely used method for turning pass phrases into keys that includes an iteration count (section 5.1 and 5.2 of the RFC). It amounts to repeatedly iterating a hash or MAC function, feeding the output of one pass into the input of the next.

This approach is widely used, but typically there is no control by the end user over the number of iterations used. Some users wouldn't mind waiting 1 second or even longer; others would demand that it be perceptually instantaneous, say a tenth of a second. It will depend on how often you have to enter your pass phrase vs how much security you want.

GPG uses a slightly different system with a fixed count of 65536, but that is characters, not iterations. It alternately hashes the pass phrase and a salt until it has hashed this many characters. While this does slow things down relative to a straight hash, it is still fast and will be well under a millisecond, so you're not getting nearly as much protection as you might want.

Unfortunately this kind of option is complicated and hard to explain to an end user so there is not much motivation to include it as an adjustable parameter. GPG users are stuck with that value unless they patch their source.

Yes, I should have mentioned PKCS#5. Thanks for the reminder.

Another option is to have a random, secret, salt. This is generated when the key is first used and then discarded. Each time the user enters their password, the program then has to exhaustively search that salt until it gets the right key. (This is usually done by having some check that lets you instantly know if you've hit the right key.)

One problem with the salt is that you might get unlucky and choose a low one. 1% of people will have salts in the low 1% of the range. These people get less protection if they are unlucky enough to be targeted. This situation is different from keys, where you might think the same thing applies, because the range of these salts is intentionally small enough to allow brute forcing.

I don't think this is correct. Recall that the attacker doesn't know the salt and so has to try every candidate salt for each candidate password. So, if you imagine that the passwords are ranked in order from 1 to P and the salts are chosen from 1 to S, if you have password i and you happen to chose 1 as your salt, the attacker still has to do (i-1)S + 1 operations... as opposed to iS if you choose S as your salt. Assuming that i is even modestly large, these (i-1)S + 1 ~= iS.

Now, obviously, an attacker could try every candidate password with salt 1, then every candidate password with salt 2, etc. In this case you clearly would suffer from having a weak salt. On the other hand, this doesn't seem like a very good attack strategy, since it nullifies any benefit you might have from predicting which candidate passwords are more frequent, while optimizing for breaking passwords with small salts, even though salts are likely to be uniformly distributed, whereas passwords are not.

Ah, yes, that makes sense. So that would be another way to do it.

Now though it would mean that people would hope to be one of the "lucky" ones who gets a low salt! They get the benefit of fast access to their keys while protected by the attacker's forced assumption that the salt might be anything in a large range. I wonder if this would make people do something to improve their odds of getting lucky... which would then suggest that attackers might in fact bias their searches towards low salts, to some degree.

Interesting point. I think the Nash Equilibrium is probably random selection slightly biased towards small salts, but I can't prove it....

Leave a comment