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.

I'd like to create a database of questions and answers so that an attacker with access to the database can't obtain either the questions or the answers.

If H0 and H1 are secure hashes, looking up the answer to a question might proceed as follows:

lookup(H0(question)) -> value
H1(question) XOR value -> answer

Can this be done securely with a hash function such as SHA1?

I've looked at HMAC, which could be used to combine the message with additional strings. The additional strings wouldn't be secret. Would access to one MAC weaken the other?

Btw.: The answer would be the same size as the hash.

EDIT

To answer a question that was asked -- the application is unique. The database would be publicly accessible, and anyone could store a question, answer pair. The encryption would be done client-side, so the server would never see plaintext. You shouldn't be able to get any useful information from seeing the database itself.

share|improve this question
1  
I think brute-forcing questions is a real concern; as a first pass I'd recommend using a strong, slow KDF like scrypt instead of a hash function. I haven't given significant thought to the security of the scheme, so this is not an endorsement of it, but that's my most immediate reaction. –  Reid Oct 25 '13 at 5:00
    
I think we really need to know the context of this problem. Who is creating these questions, are they confidential (I assume so since you're trying to hide them), and what attack model are you trying to defend against? Are you just trying to secure your DB in the case of a breach, or are you going to do something crazy like make this DB freely available to download? It looks like the user only needs to know the question to get the answer... is that right? Can you prearrange anything else with the user, like a key or something? –  Reid Oct 25 '13 at 16:29
add comment

2 Answers

I'd need to know precisely what the "lookup" operation does but I'm pretty worried already by that XOR. Let's remove the lookup operation for now and see what happens.

Suppose we have two hashes that hash to the same length ($L$) and we XOR their outputs. You've now got a much weaker hash that either of them.

Here's how to find a collision. Hash a message $m$ using $H_0(m) \oplus H_1(m)$ to produce an output $h$. We now wish to find a collision on $m$, such that $h=H_0(m') \oplus H_1(m')$

We now create a series of messages $m_i$ that are slightly different to $m$. The goal here is to find a message which has a xor of $H_0(m_i)$ and $H_1(m_i)$ equal to that of $H_0(m)$ and $H_1(m)$.

Let's assume that $H_0$ and $H_1$ behave like random oracles. In that case, the probability of this happening is approximately $2^{L\over2}$. Each oracle will take the message $m_i$ and produce a random bit string of length $L$. The probability that they collide will be $2^{L\over2}$ by the birthday paradox.

There's a slight difference here in that we're not after a precise collision but for them to have a fixed XOR. Even so, this event will happen with the same probability. We're just changing the meaning of the equality.

Note that this attack is not the typical birthday attack against a hash. The typical birthday attack finds a pair of message $m'$ and $m$ that hash to the same value. Here, I'm taking a known fixed hash value for one message and finding collision for it. That should normally take $2^{L-1}$ time but this attack demonstrates it in $2^{L/2}$ time. Thus, this scheme is completely unsafe.

share|improve this answer
    
Having fixed $m$, you can not find a colliding counterpart with $2^{n/2}$ complexity here. The reason is that $H_0(m_i)$ is not independent of $H_1(m_i)$. However, the collision search in this case is still $2^{n/2}$ as you can define $G = H_0\oplus H_1$ and find collisions for $G$. XOR does not reduce the security here. –  Dmitry Khovratovich Oct 30 '13 at 12:01
    
@Dmitry - Under the assumption that $H_0$ and $H_1$ behave as random oracles, then the inputs being independent or not is irrelevant, as far as I can tell. The hash values, however, will (by virtue of them being output from random oracles) will be independent and thus should collide with the birthday frequency? What have I missed? –  Simon Johnson Oct 30 '13 at 13:20
1  
Maybe I did not understand your algorithm, but if it is 1. Fix $m$, compute $T = H_0(m)\oplus H_1(m)$ 2. Try $2^{n/2}$ different $m_i$, for each check if $T = H_0(m_i)\oplus H_1(m_i)$. then it is incorrect, because for each $m_i$ the probability is $2^{-n}$. –  Dmitry Khovratovich Oct 30 '13 at 13:53
    
@SimonJohnson: Dmitry is correct. The odds of some two messages colliding is the birthday frequency. The odds of some single message having a specific XOR of $H_0$ and $H_1$ is $2^{-n}$. –  Nemo Oct 31 '13 at 14:59
add comment

Without reading through your protocol, yes there is a method of generating two hashes from a single message: just include a counter or any other additional information.

So H = Hash(C1 | M) and H' = Hash(C2 | M) would mean H != H' if C1 != C2.

C1 and C2 can be public, but brute force attacks would of course apply. You can find M using H or H' if M can be guessed. If you want to avoid this you need a MAC and a secret key instead.

The above method is used for instance in key derivation functions, most of the time with a fixed (32 bit) counter value per key to be derived.

With regard to your protocol, trying to keep something secret without using any key is probably not going to end well.

share|improve this answer
add comment

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.