XOR Encryption with bcrypt password de-biasing

Question

Objective: To have a very simple to verify, but very secure small message encryption.

Idea: Message ⊕ bcrypt( Password). We remove password biases with bcrypt and then XOR resulting key with the Message.

Implementation.

Limitation: Only messages up to 320 characters long are supported.

10 bcrypt salt values are hard coded:

• Salt1 = $2a$12$geKv/Jdb2zSGEtnn3AuXXe
• Salt2 = $2a$12$h1V42zCLf/F5F7RbueVuZe
• Salt3 = $2a$12$UTX8OMvg1CI3/pnbT0F5Mu
• . . . . . . .
• Salt10 = $2a$12$Yq9Vo0yefk6zJlEvJmBf6O

Suppose we have

Message=My safe code is 29540323, my bank card pin is 6926

Password= 32GateKeepers

The message is 50 characters long. bcrypt produces keys 32 characters long. So we need 2 keys to match message length:

Key1 = bcrypt(Password, Salt1) = e8.4zyJT9m9R/KX./Kd2juSHn25IqGUO

Key2 = bcrypt(Password, Salt2) = emTDJsUVCLFE3Jm8Cjx2S2/WmXEVrrU.

Key (50 characters) = e8.4zyJT9m9R/KX./Kd2juSHn25IqGUOemTDJsUVCLFE3Jm8Cj

Code = Message ⊕ Key = 40,65,14,71,27,31,47,116,90,2,93,55,15,34,43,14,29,114,81,6,90,70,97,123,66,18,88,48,81,37,52,33,14,77,55,37,56,23,117,38,42,34,102,44,64,106,91,1,113,92

Question: Is bcrypt de-biasing good enough to use in XOR encryption?

Specific Problem: Attacker knows that the same password was hashed with ten known salts for longer messages.

Specific Question: If the attacker has 10 hashes of the same password with 10 known salts. Given the nature of hashes, does this weaken the password?

Answer 1

Any time you perform more than one evaluation of a password-hashing algorithm where it is a legitimate option to perform it only once you are doing something wrong. Here is why:

• If one hash evaluation costs $C$, then 10 hashes with with the same cost-parameter will costs $10 \times C$.
• Hashes can be evaluated by a cracker with a cost per candidate-password proportional to $C$. (Probably a lot less than C since they can build or buy systems optimized for and dedicated to password cracking.)
• Given $x = H(\text{salt}, \text{password})$, one can guess a candidate password $p$ and compare $x$ to $y = H(\text{salt}, p)$.
  • If $x \neq y$ then $\text{password}$ is not $p$.
  • If $\text{password}$ is not $p$ then $x = y$ with only $1 / N$ probability where $N$ is the size of a hash's image set. *
• Given knowledge of some $n$-bit long subset of one hash output's bits, a cracker can similarly evaluate the hash of one candidate password with a cost $\le C$ with a $2^{-n}$ false positive rate.
  • If the adversary knows one character of plaintext (8 bits), then out every 256 candidate passwords, 255 candidates can be eliminated with work proportional to $C$. Only 1 out of every 256 will need two or more hash function evaluations to check for false positives.
  • Because each 32 byte block can be tested independently, the password cracker will rarely have to do proportional to $10 \times C$ work but the legitimate password-holder will always do $10 \times C$ work,
  • The cracker has a significant advantage over the honest party compared to an alternate method: Use a single password hash evaluation (a password based key derivation function) to calculate one key and use that key with a typical symmetric key message encryption algorithm.

---

One can put key derivation functions (which you can think of as hash functions used to deterministically generate keys) into two categories: password-based KDFs and key-based KDFs.

"Password hashes" (or "slow hash algorithms" as non-experts sometimes say) are used to describe password-based functions that "stretch" passwords. Passwords are usually low entropy (that is they're relatively predictable) and so password hashes and PB-KDFs are designed to be artificially slow for both legitimate parties and password crackers to evaluate with the hope that it makes password cracking less "profitiable".

Standard or "fast" hash algorithms are not necessarily insecure just because they are fast. If passwords were as unpredictable as a 128 bit key then password bases could just store SHA-2 hashes of passwords (preferably still salted for off-topic reasons) with no loss to security.

The right way to do things is to increase your password hashing algorithm's cost parameter by a factor of ten. You're doing the same amount of work, $$1 \times (10 \times C) = 10 \times (1 \times C)$$ so your CPU-time budget doesn't increase. On the other hand, the adversary, with only one slower hash function to crack, now needs to always do proportional to $10 \times C$ work instead of just $C$ work.

If you need more key material than a PB-KDF can give you without multiplying the amount of work you need to do, then derive just one master key from the PB-KDF and feed the derived key to a KB-KDF. You can derive many keys from a key-based key derivation function much faster than the run time of a password hashing function.

If for some reason you must use only hash algorithms instead of a stream cipher, then do $$K_M = bcrypt_{10 \times C}^\text{**}(\text{salt}, \text{password})$$ $$K_i = \text{SHA-512}(K_M \| i \| \text{nonce})$$ $$\text{ciphertext}_i = \text{plaintext}_i \oplus K_{i + 1}$$

And send $$\text{ciphertext} \| \text{HMAC-SHA-512}(K_0, \text{ciphertext})$$ because you need message authentication in addition to message secrecy.

In my previous cost analysis I treated the key-stream computation as if it were zero. If you choose a large $C$ then this is a reasonable assumption. Otherwise assume little $c$ is the cost of a "fast" hash. You CPU cost is $10 \times C + 13 \times c$. (Since HMAC is 2 more hashes and you derive one more key for HMAC.) And the adversary's cost is $10 \times C + c$. But both are approxmately $10 \times C$.

---

For your specific proposal, assuming you're using ASCII encoding of plaintext, you can easily infer 32 bits of every full 32 byte block because no standard ASCII character has a byte value with the most significant bit set.

For other types of plaintext it won't necessarily be so trivial, but you should assume that there are some other ways to guess at plaintext. If there is uncertainty then the adversary could just compare more plaintext-guesses to the same hash evaluation. You get more false positives obviously, but this doesn't prevent cracking. False positives can be distinguished from true positives by evaluating a hash with each salt then looking at the decryption to see if it makes sense. (Check if it contains real dictionary words, or do statistical tests comparing it to reasonable plaintext.)

---

_{* Assuming the hash function is unbiased, which is reasonable for good password hash algorithms and many common not-good ones. (SHA-1 and MD5 included among other bad ones.) For the plain-old password hashing use case (not your use) false positives (which are so improbable that it's safe to say they won't happen) are just as good as true positives.}

_{** Use Argon2d if an optimized implementation is available instead of bcrypt. bcrypt is fine if it has an optimized implementation. Same for PB-KDF2 and balloon hashing. (Don't request PB-KDF2 output length that is too long.) You can use scrypt as well if there is an optimized implementation and if you can give it a large CPU and RAM allowance. ... I'm beginning to see that people hear the "Use ___ instead of ___ for password hashing" advice that's beginning to reach a larger audience now and are taking away the cargo-cult-like idea that it means "Always substitute [password hashing function] for [normal hash algorithm or encryption algorithm]". That's wrong. Only use password hashing functions for password storage and for derivation of a master key.}

_{Edit: Argon2d. not Argon2i.}

Answer 2

Bright side

As this is a one time encryption, you can use it for streaming between a server and a client. You can use an asymmetric encryption such as RSA to pass the symmetric encryption key that you call it Password.

The Vernam Cipher is an algorithm invented in 1917 to encrypt teletype (TTY) messages.

The salts do not need to be hardcoded. I would use 1, 2, 3, ... assuming the hashing algorithm is strong enough.

Dark side

However, the family of Vernam encryption aka one-time pad (OTP) have a very big disadvantage. You cannot use them more than once. You may ask what is the problem? If the key is generated by a random generator and passed to the client via secure method, you may not care. Because the next time you will generate another password.

But if you are using a human readable key such as password123 and encrypt file1 on your disk with it, you probably would like to encrypt file2, file3 and ... with the same password. That's where the problem comes from.

Even if I do not have your key and salts but I know file10 is empty and the encrypted file10.enc starts with ba61dc7bca877c3006663212fe, I know that if I XOR the same value with file2.enc, it will leak the content of file2 to me because it is the same binary string used for generation of file2.enc no matter what has been your password and your salt. In contrast, AES encryption does not have such vulnerability. Here is where the difference comes from.

Hope I have understood your point.

Answer 3

Is BCrypt de-biasing good enough to use in XOR encryption?

With extreme narrow mindedness, the technical answer is yes it is. It will produce a uniformly distributed random output can can be used in a short stream cipher. All decent password stretching /key derivation functions can as they use cryptographic primitives like HMACs or parts of them like Blowfish. So yes.

Rather than jump into a technical analysis of your scheme, I'd say that overall this is a very unorthodox method to secure short messages. You're taking on the role of Frankenstein creating a stream cipher monster out of parts that were never intended to be put together. Yes, it might be alive, but it's also horrible.

Consider that BCrypt output is alphanumeric rather than binary so you'll have to perform modular xorations(?). And longer messages require more keys. Kerckhoffs's principle warns tin foil wearing types that all the salts will be known, so they become irrelevant to the overall security context. And your final cipher text will be malleable as all un authenticated ciphers are. This might not be an issue in your case though.

There are common encryption methods based on stream ciphers than will automatically generate a pseudo random stream for subsequent xor. Or block ciphers. It doesn't really matter internally does it?

We remove Password biases with BCrypt and then XOR resulting Key with the Message.

You have to think very carefully. What are you creating? Password text biases are automatically resolved in standard symmetric key methods. There is even original Blowfish if you like, and that's with 400+ bit keys. Debiasing is definately not BCrypt's raison d'être. If anything, debiasing is straying into areas of entropy and it's extraction.

I'm a huge fan of rolling your own simple encyptions but I think that in this case you need to find some flaming torches, organise the villagers and kill this thing.

If the attacker has 10 hashes of the same password with 10 known salts. Given the nature of hashes, does this weaken the password?

This actually forms a good question, but might be better spun off as a separate one. This will encourage answers unbridled with the odd cryptographic monster baggage.