Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let's assume we have 2 phrases, one is the real password from a user, and the other is generated from the real password and almost impossible to guess. You would need both to authenticate a user. What would be the best theoretical way to store them, or how to encrypt them so that if attacker somehow gets encrypted pass phrase wouldn't be able to decrypt both phrases? I know with brute force, attacker can eventually break the encryption, but what would be best to do to not make it easier for attacker to break it?:)

If we encrypt (with symmetric algorithm) them separately and store them somewhere (doesn't really matter where), first phrase could be vulnerable to dictionary attack. We could combine them, for example p1f1p2f2… (phrase1=p1p2p3…, phrase2=f1f2f3…) and then encrypt them. That way the combined phrase shouldn't be vulnerable to dictionary attack, and attacker could only use brute force.

But I'm not sure how the way we combine them affects encryption algorithm. Is there any specific encryption algorithm that would be better than the other? Could there be vulnerabilities regarding how we combine them, because they could get discovered if we statistically analyse many examples of encrypted combined pass phrases (I'm guessing here)?

Or is there no way to know before actually analysing the algorithm, encryption algorithm and encrypted pass phrases?

share|improve this question

migrated from cstheory.stackexchange.com Feb 23 '12 at 22:55

This question came from our site for theoretical computer scientists and researchers in related fields.

    
Welcome to Cryptography Stack Exchange. Your question was migrated here because of being off-topic on CS Theory Stack Exchange, and being on-topic here. Please register your account here, too, to be able to comment and accept an answer. –  Paŭlo Ebermann Feb 24 '12 at 8:34
1  
If the second passphrase is (deterministically) »generated from the real password«, it is not harder to guess than the password itself. –  Paŭlo Ebermann Feb 24 '12 at 8:34
    
@PaŭloEbermann the second password could be harder to verify though (e.g. PBKDF2 is deterministic, and the salt is normally kept with the result of the PBKDF2 function). –  owlstead Feb 25 '12 at 13:53
    
What i meant by harder guessing is that usually attacker can guess user password, because many people use common words for it. Even if attacker guessed main pass phrase and knows how the other pass phrase is formed, it won't be that easy to guess the second phrase because there is human factor involved when generating (so it's more unique for every person). Ofc, that doesn't mean it can't be found by brute force, as every password can be cracked with it if you have enough time. –  Ronwe Feb 27 '12 at 8:08

2 Answers 2

"What would be the best theoretical way to store them, or how to encrypt them so that if attacker somehow gets encrypted pass phrase wouldn’t be able to decrypt both phrases?"

If you really want to encrypt them, I suppose I would
recommend http://sourceforge.net/projects/ntru/.


"I know with brute force, attacker can eventually break the encryption,
but what would be best to do to not make it easier for attacker to break it?"

The best thing to do would be to not use encryption at all, and instead use scrypt.



"If we encrypt (with symmetric algorithm) them separately and store them somewhere
(doesn’t really matter where), first phrase could be vulnerable to dictionary attack."

Um... not really, I haven't heard of any encryption algorithms
where there's a dictionary attack that is any faster than brute force.


"But I’m not sure how the way we combine them affects encryption algorithm."

The thing generated from the password might remove
the need for randomness in the encryption algorithm.


"Could there be vulnerabilities regarding how we combine them,
because they could get discovered if we statistically analyse many
examples of encrypted combined pass phrases (I’m guessing here)?"

There could be, one just hopes there isn't.


Or is there no way to know before actually analysing the algorithm,
encryption algorithm and encrypted pass phrases?

If the algorithm isn't contrived, then combining them
probably isn't any weaker than encrypting them separately.

share|improve this answer

If you are asking "how can the server verify that the password (or passwords in your case) that the user enters are valid", the standard answer to that is not to have the server encrypt the passwords at all. Instead, what we have the server do is store one hash of the two passwords. That way, if someone manages to break into the server and get the hashes, that doesn't tell him anything about what the passwords are.

One simple implementation would to be to take a standard hash function (SHA256, for example), and when registering the user, compute the hash of the user-selected password concatenated with the one generated from the real password; the server would store this hash in the database (or forget the actual passwords). Then, when authenticating a user, the user would supply the passwords, the server would concatinate them, hash them, and compare that hash to what's in the database (and, of course, allow the user only if the hashes are exactly the same).

One advantage of this over encrypting the passwords is that hashing is a one-way operation; no one can reverse the hash (this is actually one of the security properties of a cryptographical hash, that give a hash, no one can find that hashes to that value). In addition, if the user enters the wrong data, it well detect that as well (as that's another of the security properties, that no one can find two values that hash to the same).

Now, if your second password is as good as you expect, that it is "almost impossible to guess", well, that's actually good enough. Even if someone broke into the server and recovered the hash, well, all they could do is make guesses for both passwords, hash them, and seeing if both guesses were correct; if one of the passwords is unguessable, well, they can't do that.

However, I rather suspect that the password might be a bit more guessable than that (after all, if it were truly unguessable, why bother with the user-chosen password at all?). If that is likely to be the case, it might be wiser to do the same approach, but with a password derivation function (such as PBKDF2); it's pretty much like a hash, but it does these nice things:

  • It makes provision for a "salt" (which is an additional value that is hashed in); it won't make a brute force attack on a single hashed password any harder, but it does mean that the attacker cannot attack several hashed passwords at once (because each of them will have a different salt). The server would choose a random salt when registering the user, and include it along side the hash.

  • It's slower to evaluate than SHA256 (and in this context, that's not a bad thing; it means that an attacker will take longer to go through his dictionary).

  • It also provides a "key" that's needed to do the hash evaluation; if the server stores the key separately, well, the hash doesn't do the attacker any good unless he gets the key as well.

Oh, and one thing; about your specific question about how to combine the two passwords; well, hash functions and password derivation functions don't really care; they'll work with just about anything. The only thing you need to be careful is to make sure that you combine them in a way that doesn't lose information. For example, you wouldn't want to exclusive-or them together, otherwise (as a trivial example, the two passwords "A" and "1" would hash the same as the two passwords "B" and "2"). One easy and safe way to combine them is simply concatenate the two (of if the two passwords are "Alpha" and "Omega", you'd actually hash "AlphaOmega". (Note: if both passwords are variable length, you make also want to concatinate the length of one of them if you want to be pedantic; otherwise the two passwords "AB" and "C" would hash the same as the two passwords "A" and "BC").

share|improve this answer
    
I know how hash works (but not this password derivation function, which sounds very interesting, ty for that), and i would certainly use it if i would implement my solution, but i was asking just for a hypothetical situation where you can only encrypt your password, not hash it. And about generated phrase, it depends on first so that without original it is no good by itself :) –  Ronwe Feb 27 '12 at 8:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.