2
$\begingroup$

I have recently read a bit about Lamport signatures (especially the approach using hash ladders to save disk space) and I found it very interesting that it entirely depends on a hash function.

So I asked myself the following question:

When you have a plaintext $p$ and hash it and concatenate it with its hash again and so on: plain -> $H(p) + H(H(p)) + H(H(H(p))) + ...$ ($n$-times)

  1. is this a good source for randomness? Why not?

  2. Does the attacker having a look at this output have any advantages in guessing the plaintext for large $n$?

You have some file you want to encrypt. Hash the file with a good hash function (e.g. Keccak). Then concatenate this hash with a password you choose. From this you derive a hash concatenation like above until it is as long as the file you want to encrypt; lets call it "hashchain". Then XOR your file with the hashchain and when you are finished you write the hash of the original file to the beginning of your encrypted file. Destroy original file and hashchain.

When you want to decrypt, take your password and the hash of the original file (which we have written to the beginning of the encrypted file), concatenate and hash this until you have a file which has the size of the original file. XOR both again and you get back your file from the beginning.

Note: Using password and hash of the original file as the beginning for the hash chain makes us able to use the same password for encryption of different files.

  1. Is there a reason why this is not secure?

I have no only superficial knowledge about cryptography, please keep this in mind when answering.

$\endgroup$

2 Answers 2

6
$\begingroup$

1) is this a good source for randomness? Why not?

It is certainly not a cryptographically secure PRNG. In order to be a cryptographically secure PRNG, it must not be possible to predict the next output based on the current output. With your algorithm, the next output is predictable, since it's just H(previous_output) and, according to Kerckhoff's principle, you should assume the attacker knows the hashing algorithm.

2) Does the attacker having a look at this output have any advantages in guessing the plaintext for large n?

The attacker only has to guess or know the first block of plaintext. Once the attacker knows this, decrypting the rest of the plaintext is easy: for the first block, the ciphertext C is H(password) ^ M, so H(password) = C ^ M. So once the first block of plaintext is known, the attacker knows H(password), and can calculate H(H(password)), H(H(H(password))) etc.

3) Why is the following encryption a bad idea? You have some file you want to enrcrypt. Hash the file with a good hash function (e.g. Keccak). Then concatenate this hash with a password you choose. From this you derive a hashconcatenation like above until it is as long as the file you want to encrypt lets call it (hashchain). Then XOR your file with the hashchain and when you are finished you write the hash of the original file to the beginning of your encrypted file. Destroy original file and hashchain.

Password have the habit of having low entropy, which makes them excellent targets to brute-force. If the first block of the file's plaintext reveals any information about whether the file is successfully decrypted, the attacker only has to calculate H(plaintext_hash || password) and xor the first block to see if the attack is successful. Most hash functions are fast, and attackers can easily try millions of passwords per second.

Even if the first block does not reveal any information, if you reuse the same password, an encryption oracle attack with a chosen plaintext can choose an all-zero plaintext. Then the first block simply becomes C = H(plaintext_hash || password) ^ 0 = H(plaintext_hash || password). Since the attacker knows the plaintext hash, the password can still be brute-forced in the same way.

Given my experience with cryptography, that's probably just the tip of the iceberg.

$\endgroup$
5
  • $\begingroup$ i understand the point your making when talking about file headers of plaintext... you could then map the hashchain onto the original file beginning from the end of the file $\endgroup$ Feb 8, 2017 at 21:28
  • $\begingroup$ or even better you create two hashchains, one starting at the beginning of the file, the other starting at the end of the file. then hash the meeting hashes to retrieve the final block hash. $\endgroup$ Feb 8, 2017 at 21:52
  • $\begingroup$ @user7431243 In that case you'd have matching pairs of hashes (i.e. the first and last) that are xor'ed with the plaintext. By xor'ing the blocks which use the same hash, say C1 and C2, you can use C1 ^ C2 = M1 ^ hash ^ hash ^ M2 = M1 ^ 0 ^ M2 = M1 ^ M2, i.e. given two cipherblocks using the same hash, you can retrieve the xor of the two plaintexts. With some knowledge of the text's domain (i.e. is it a HTML page) and some analysis it is then quite easy to get (parts of) the original plaintext. Also, unless the file is huge, brute-forcing the password is slower, but still quite feasible. $\endgroup$
    – knbk
    Feb 8, 2017 at 22:15
  • $\begingroup$ btw. thanks a lot for the detailed answers it really helps me. what if the second hashchain is not the same as the first one. I somehow think that with a bit of variation one could arrive at adecent encryption. $\endgroup$ Feb 8, 2017 at 22:23
  • $\begingroup$ so to answer question 1) im preparing a hashchain based on sha256 and wil run the dieharder tests on it $\endgroup$ Feb 9, 2017 at 0:01
0
$\begingroup$

IT is a bad idea because hash function does not have a trapdoor, meaning during decryption you have to spend the same amount of time to decrypt as an attacker trying to break your scheme. Encryption algorithms are implemented with trapdoor one way functions: The owner of the trapdoor can decrypt very efficiently

$\endgroup$
2
  • $\begingroup$ i dont agree with you. the attacker would have to create a file first by hashing which has the original file size of my file and then he can try to decrypt but only has one try and then has to repeat the whole procedure $\endgroup$ Feb 8, 2017 at 21:14
  • 3
    $\begingroup$ This is not the correct definition of a trapdoor function (see this answer for why trapdoor functions are generally only applicable to asymmetric crypto), nor does it accurately explain why the proposed scheme is a bad idea (see knbk's excellent answer). $\endgroup$ Feb 8, 2017 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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