XTEA: patterns in plain text

Question

I'm using XTEA to encrypt passwords that I store in a database. (I need to be able to decrypt these passwords later to log in on another system.) But now I have noticed something: if I decrypt a password using a different key I can still see some of the patterns in the plain text. I am not worried about an attack against the XTEA encryption, I am worried about an attack against the other systems that use the encrypted passwords.

For example:

Password A = "111222111"
Password B = "222111222"

I encrypt these with some key, then decrypt them with another key. The output is something like:

A: qqqwwwqqq
B: wwwqqqwww

(Using q and w for readability, it's actually 2 illegible characters.) As you can see, for weak passwords this can reveal a lot of information that can make brute force or dictionary attacks against these passwords a lot easier:

1. The length of the password.
2. Patterns of the same character in a password.
3. Patterns in different passwords.

The assumptions here are:

1. The attacker has access to several encrypted passwords and salts.
2. The attacker has no access to the encryption key and this key is sufficiently strong.
3. The attacker is only interested in the plain-text. Getting the encryption key can be a means but is not an end.
4. The attacker has decompiled the code, obfuscation won't do any good.
5. The users are idiots and the passwords are as weak and similar as the above examples.

My questions are :

1. Can this be considered a weakness in my program? Or can I wash my hands by telling the users to use stronger passwords?
2. Is this normal behaviour for XTEA, or is there something wrong with the implementation I am using?
3. Are there other encryption methods that are better suited for this?

Answer 1

XTEA is a block cipher. It requires a block cipher mode of operation to work. Together with a block cipher mode of operation you can generate something that is secure. For this you require at least an IV, as you may otherwise encrypt identical passwords (for different users) to identical values. Or, if you encrypt each character separately, the same character value to the same ciphertext.

A block cipher itself is a PRP, a pseudo random permutation. Given a key, it will always transform one plaintext to the ciphertext associated with it. If you use XTEA in e.g. Block TEA this will not be different; you will always get the same ciphertext.

You can do the following things:

1. define a character set for your password and possible input values;
2. encode the password using the said character set
3. pad the password to a certain maximum length, say 64 bytes to allow for pass phrases (either store the length or use an invalid character such as 00 hex)
4. generate a 8 byte IV (for a 64 bit block cipher such as XTEA; IV requirements may depend on mode of operation and block size)
5. encrypt the encoded & padded password using the IV and key
6. store IV | ciphertext

This should be secure, as long as the mode of operation you choose is secure. You may want to use authenticated encryption (e.g. GCM) for this, but that's not really a requirement.

---

Usually it is better not to store passwords at all, but this seems a requirement in your case. You may want to check if there are secure password faults available from the runtime environment. If there is no pressing argument for using XTEA, you should be using AES.