swineone's Journal

A cryptographic data escrow protocol
So here's what I've been working on:

For a P2P protocol that I'm trying to design, I needed a secure way of `selling' a piece of data to an untrusted person (the lack of trust is symmetrical, in fact: the buyer doesn't trust the seller either). Immediately one might suggest the introduction of a third party that's trusted by both of them, to perform an escrow service. OK, that's fine, except that this is going to be used in a P2P protocol, so you can't shift back the load to a central server. It occurred to me that the seller might send an encrypted version of the data, then use the escrow authority to perform an escrow of the key only. While not completely decentralized, this seems suitable.

There are two problems with the naive protocol as stated:

Why should the buyer trust that the seller will not simply send random data instead of what was promised?

Why should the seller trust that the buyer is not going to lie about receiving correctly the data and kill the transaction?

Note that this isn't about being sure that the encrypted data was correctly transmitted; that's easy to do. The point is whether the seller even bothered to encrypt the correct data at all, and if they didn't, it's obvious that no amount of error correction is going to change that.

Now let's suppose we had a hash function h() with an interesting property: given a message m, an encryption function E_k() where k is the key, and the hash h(m), then h(E_k(m)) can be efficiently deduced from k and h(m) (besides being directly computable given just E_k(m)). Obviously h() should be a strong hash function otherwise: hard to find collisions and preimages, etc. In that scenario, assuming the escrow authority knows h(m), the escrow protocol could proceed like this:

Escrow authority generates a key k and sends it to the seller, and computes h(E_k(m)), given that it knows k and h(m);

Seller encrypts m with k: c = E_k(m), and sends it to the buyer;

Buyer computes h(c) = h(E_k(m)) and checks with the escrow authority whether it matches the expected value;

If affirmative, buyer is sure that seller was honest and completes the transaction.

Initially it occurred to me that one could seek a linear hash: one for which h(m XOR s) = h(m) XOR h(s). This, combined with a strong stream cipher (or a block cipher in a mode of operation that emulates a stream cipher, say CTR mode) would do the job. My advisor did have one at a hand (a MAC, rather): the Galois/Counter Mode (GCM) of operation for a block cipher. If the message m could be written as the concatenation of block m₀, m₁, m₂, ..., then GCM computes something like m₀ H + m₁ H² + m₂ H³ + ..., where H is a polynomial in GF(2¹²⁸), and the entire computation is performed in GF(2¹²⁸) -- that is, modulo an irreducible binary polynomial of degree < 128. The polynomial H is the encryption of a string of zeros under some key (recall that this is a MAC, not an ordinary hash). The problem is, once this key (and hence H) is revealed, it becomes easy to forge a hash: just equate the expression above (m₀ H + m₁ H² + m₂ H³ + ...) with the desired hash value, then fix all coefficients (the m_i's) save for one, then solve the corresponding polynomial equation.

As a sidenote, I have an argument that the inherent idea of a linear hash is flawed (but not a MAC: rest assured that GCM is still unbroken), which I'm sure has been published already, but here goes: if your hash has b bits, consider the vector space GF(2)^b (note: this isn't the same as GF(2^b)). Generate a few random random bitstrings (all of the same length) and map them to GF(2)^b using your hash, and take note of these preimages. Now, one expects that b+1 or b+2 bitstrings should be necessary until you have a set of b linearly independent vectors in GF(2)^b. Now, take these as a basis of your vector space, and perform a change of base to the canonical basis, applying the same operations to the preimages that were stored before. Now you will have a bitstring which hashes to 100..000, another which hashes to 010...000, and so on. It's easy to XOR these together to obtain any desired hash value. (Note that the change of basis is not strictly necessary, but it's certainly easier than solving a linear system each time a preimage is desired; either way the hash is broken.)

But I digress. So it seems that the whole idea has to be scrapped? I believe not. To fake a hash in GCM, one must solve polynomial equations in GF(2¹²⁸), which is easy. In fact, it can be as simple as solving a linear equation of the form ax = b for x, which requires computing an inverse of a. To prevent inverse computation, I thought of hiding the group/ring/field order away. The only algebraic structure I'm aware of where this would work is the multiplicative group (Z/nZ)* for n = pq a product of two large primes -- the same setting as RSA. The group order is phi(n) = (p-1)(q-1), so anyone who doesn't know the factors of n can't compute phi(n) either (or so it is hoped). In fact, the whole premise behind RSA is that, given the public exponent e, one can't compute the private exponent d which is the inverse of e modulo phi(n).

Initially I thought of computing something similar to a GCM hash, say h(m) = h(m₀ || m₁ || m₂ || ...) = b^{m₀ H + m₁ H² + m₂ H³ + ...} mod n for some integers b and H. Now, if one replaces the XOR operation is a stream cipher by integer addition, then h(m + s) = b^{(m₀ + s₀) H + (m₁ + s₁) H² + (m₂ + s₂) H³ + ...} mod n = h(m) h(s). In fact one doesn't need to break up the message at all: just interpret it as an integer in binary (in fact that's a special case of this definition, for a choice of H as a certain power of two.) Then h(m) is simply b^m mod n.

The only problem with this scheme is efficiency: for each bit of the message, the buyer needs to compute a big modular multiplication (512-bit at the very least). The throughput for such a calculation should be less than a megabyte per second, I believe. The escrow authority is privileged in that it knows phi(n) and can reduce the message modulo phi(n) to gain a lot of time, and the seller doesn't need to compute this hash at all. The buyer though doesn't have a choice. Well, at least it's a start, and I'm thinking of ways to improve this without losing security.

Current Music: Stand Away (Angra)

Advertisement