Advice from cryptographers and mathematicians

#1

Post by aruggirello » Sat, Sep 28, 2013, 9:36 AM UTC

I have a question regarding a simple hash-based encryption scheme I'm thinking of (forgive my ignorance if this already exists).

Let's suppose we have a function hash(T) that is cryptographically secure; a function combine(T,C) that simply concatenates token T with constant C; and a function xor(H1,H2) that performs bitwise exclusive or between H1 and H2 (of same length) and returns result. Is it safe to:

ask user for a token t and plaintext m;

let ha = hash(combine(t,"a")); let hb = hash(combine(t,"b")); let he = xor(hb,m);

then store ha,he on a database (assuming m and hb are of same length)?

to decrypt m, user has to provide token t only; we then:

let ha = hash(combine(t,"a")); let hb = hash(combine(t,"b"));

and select xor(he,:hb) where ha=:ha to retrieve plaintext m.

Is it really that simple, or am I missing something? Or, can an attacker brute-force hb out of ha knowing that inputs differ by "a" and "b" only (assuming hash is SHA-256 or similar)? Then, would it be any safer to use xor(t,X) instead of (or together with) simple string concatenation?

I will really appreciate any suggestions. Thank you!

Andrea

Re: Advice from cryptographers and mathematicians

#2

Post by nullmeme » Sun, Sep 29, 2013, 1:01 AM UTC

If I know the hash function, it would be relatively straight forward to deduce what state the hash function is in before processing the final "a" without knowing t.

With that state, it would then be a matter of computing the last character of the hash function with the "b" constant. Once I've got that, I can get m knowing only hash(combine(t,"a")), hash(combine(t,"b")), xor(hb,m) but not knowing t.

One way to strengthen your approach is the use an approach borrowed from HMAC, which is to compute hash(combine("a",t,"a")) and hash(combine("b",t,"b")) instead. Now it's a harder problem to figure out the state of the hash function, if you'll permit me to extend your combine function.

I hope this is clear.

Re: Advice from cryptographers and mathematicians

#3

Post by cdman » Sun, Sep 29, 2013, 4:52 PM UTC

nullmeme wrote: post #2

If I know the hash function, it would be relatively straight forward to deduce what state the hash function is in before processing the final "a" without knowing t. With that state, it would then be a matter of computing the last character of the hash function with the "b" constant. Once I've got that, I can get m knowing only hash(combine(t,"a")), hash(combine(t,"b")), xor(hb,m) but not knowing t. One way to strengt…

HMAC actually double-hashes the input, so something closer to HMAC would be hash(combine(hash("a", t), "a")). See http://en.wikipedia.org/wiki/Hash-based_message_authenticati...

Re: Advice from cryptographers and mathematicians

#4

Post by aruggirello » Sun, Sep 29, 2013, 5:06 PM UTC

Out of curiosity I looked up HMAC on Wikipedia; as it turns out, using H(key ∥ message ∥ key) as suggested by nullmeme is "better, however various security papers have suggested vulnerabilities with this approach, even when two different keys are used."

Now I'm thinking to use plain hmac("a",t) instead of hash(combine(t,"a")) - and simply hash(combine("b",t)) instead of hash(combine(t,"b")); after all, hmac shouldn't be required to protect hb since it's never stored as is.

hmac("a",t) would look like: hash(combine(xor("a",0x5c),hash(combine(xor("a",0x36),t))))

I could perhaps concat(m,hmac(t,m)) instead of leaving m alone when computing he.

Re: Advice from cryptographers and mathematicians

#5

Post by cdman » Sun, Sep 29, 2013, 6:20 PM UTC

The first question I would ask is: what attacks are you trying to defend against? Can the attacker eavesdrop on the initial communication?

If so, the attacker has all the needed information.

If the initial channel is assumed to be protected against eavesdropping, why can't the same channel be used on follow-up communications or perhaps the initial communication used to set up a shared secret and use it to encrypt later communications.

So the main question would be: what is your goal with this algorithm? Simply to construct encryption schemes using hash functions? (since the reverse has been done - given a block cypher like AES you can construct hash functions, just not very good ones).

Re: Advice from cryptographers and mathematicians

#6

Post by aruggirello » Mon, Sep 30, 2013, 9:23 PM UTC

cdman wrote: post #5

The first question I would ask is: what attacks are you trying to defend against? Can the attacker eavesdrop on the initial communication? If so, the attacker has all the needed information. If the initial channel is assumed to be protected against eavesdropping, why can't the same channel be used on follow-up communications or perhaps the initial communication used to set up a shared secret and use it to encrypt lat…

You are right: the goal of this algorithm is to construct an alternative encryption/decryption scheme using a cryptographically secure hash, and exclusive or.

So I'm trying to look for possible weaknesses in the scheme, e.g.: would it be safe to store (random-padded) plain text this way (vs. should it be compressed)? Since the encrypted messages are xor'ed with a (binary) hash, would they be exposed to attacks such as byte-by-byte crypto-analysis? And, how does simple xor compare against the classical power/modulus math in this respect - considering the random-like context and short length of a single, cryptographically secure hash?

Finally, should the algorithm be proven too weak, we might choose to substitute he = xor(hb,m) with e.g.: e = AES_encrypt(hb, m).