9
$\begingroup$

Here's the problem I'm trying to solve:

  • y is public, it's a timestamp
  • there is A who knows x - it's a file
  • A can send B some information about the file (a hash?), but not the full file (it's too big)
  • A then sends the file x to C

The role of B now, is to periodically verify that at given time y C still has the file x. C could send something like hash(x, y) to B, and B (who doesn't have the full x) needs a way to verify that C indeed has the full file x at time y.


Here's the original question I've asked (it includes the solution approach I've been trying to take):

Say I only know hash(x) and y.

I receive z that is supposed to be hash(x + y)? Is there any way I can verify that without knowing x?

I'm interested in any mechanism that could make such check possible rather than particular hash and + operations.

$\endgroup$
  • 3
    $\begingroup$ The edit helped clear up the question quite a bit, and I suggest actually changing the order: The actual question should be what you want to achieve - and the construction with hashes is just a possible solution - and it's fine to ask "does this work?". Atm, it seems to be a candidate for the XY problem. $\endgroup$ – tylo Mar 24 '17 at 10:51
  • $\begingroup$ Thanks tylo I wasn't aware of the XY problem. I've updated my question. $\endgroup$ – gysyky Mar 24 '17 at 11:33
  • $\begingroup$ Can B request information from A at any time after the file has been sent to C? If so, B could periodically generate a random seed and ask both A and C to send a hash generated with that seed. $\endgroup$ – Luca Citi Mar 25 '17 at 20:42
9
$\begingroup$

The technical term for what you're looking for is "publicly verifiable proof of retrievability". Here is a question on crypto.SE that discusses existing implementations of PoRs.

$\endgroup$
  • 1
    $\begingroup$ Could you elaborate a bit to make this a stand-alone answer? $\endgroup$ – Pål GD Mar 25 '17 at 9:15
6
$\begingroup$

After you described the actual problem, here's what you can do without breaking any security assumptions or putting restrictions on file $x$:

  1. Solution: Instead of having $C$ calculate $hash(x,y)$, it just $hash(x)$ to $B$. $B$ just needs to check that he got the same hash both from $A$ and $B$. $y$ is public anyway. Or $C$ could also send $y$ along with the hash.
  2. Solution: If $C$ can digitally sign messages and $B$ knows the verification key of $C$, then it would be enough if $C$ sends a message $Sign(hash(x) || y)$. B has $hash(x)$ (directly from $A$) and $y$, knows the verification key and can check the signature. $C$ obviously only can sign $hash(x)||y$ only if $C$ actually has either $x$ or $hash(x)$.

We got two more conditions from the comments:

  • $C$ has to prove to posess $x$ and not just $hash(x)$
  • $B$ wants to check periodically

I don't think that's possible at all, if you don't include Alice again in the periodic steps or the process becomes really large (scaling with size of $x$ instead of the hash). Here's the reason why:

  • A proof of knowledge of $x$ would be possible, and it would prove freshness because $B$ can always use different random coins. But that would probably scale with $x$.
  • In order to prove freshness you need to make the protocol dependent on random choices of $B$, otherwise it doesn't work because $C$ could just replay an old transcript.
  • Using hash function (or similar constructions) with length extension properties do not help at all: If $B$ can use the extension technique for checking, then $C$ can use the extension technique to create the new hash.
  • $B$ doesn't know $x$. Even if we consider arbitrary oneway functions (with or without trapdoor, keys, etc.) and $B$ only knowing $f(x)$, any homomorphic property (e.g. used in a proofs of knowledge) could be used by both $C$ and $B$.
$\endgroup$
  • $\begingroup$ "only if C actually has either x or hash(x)" I should probably have mentioned that in the question: what I want to verify in B, is that C actually has the whole file x at the time y, not just a hash of it $\endgroup$ – gysyky Mar 24 '17 at 11:13
  • $\begingroup$ More XY problems, it seems... Checking that $C$ has $x$ and not only $h(x)$ wasn't stated previously. Having $B$ check periodically and that it has to reflect the current state (and not just at one time) was also missing. $\endgroup$ – tylo Mar 24 '17 at 12:35
  • $\begingroup$ sorry, turns out it's not that easy to ask the question properly $\endgroup$ – gysyky Mar 24 '17 at 13:05
  • $\begingroup$ @gysyky No problem. I just don't think what you want is actually possible. $\endgroup$ – tylo Mar 24 '17 at 13:15
  • 1
    $\begingroup$ @fgrieu Yes, I think that would work. However, as you already pointed out: it does not work any more when $B$ just has public information. In the PDP scheme the verifier is required to hold some metadata - and that is effectively giving him some information about the file itself. $\endgroup$ – tylo Mar 27 '17 at 10:33
5
$\begingroup$

As to the first part of the current question: it was previously proposed that B receive $\operatorname{hash}(x)$ from A, then check $\operatorname{hash}(x+y)$ computed and sent periodically by C, comparing that against a recomputation made from $\operatorname{hash}(x)$ and $y$, using some property thought in the current question's title and second part.

That technique fails if C is dishonest. Problem is, C can compute $\operatorname{hash}(x)$ and discard $x$ (including while receiving and hashing $x$) and then use the very property used by B for verification. As a more easily solved aside, that technique also fails against an adversary having intercepted $\operatorname{hash}(x)$ sent to B, then impersonating C to B.

The problem is reminiscent of PDP: Provable (or proof of) Data Possession. Formalization of that problem is attributed to Giuseppe Ateniese, Randal Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary Peterson and Dawn Song with Provable data possession at untrusted stores (in proceedings of CCS 2007). A followup reference article by the same authors plus Osama Khan is Remote data checking using provable data possession, in ACM TISSec 2011.

Any PDP method can be used for the question's purpose by securely sending from A to B (with confidentiality and integrity) whatever the data originator of PDP is supposed to keep; but this does not match the requirement in this comment that B only holds public information.


As tho the original question (it's current second part): depending on the security properties thought for the hash, and the freedom we have about what $+$ is, what's asked is possible, or not.

For a hash with the security objective of being secure in the Random Oracle Model (informally: behaving like a random function), and all except very degenerate $+$, what's asked is clearly not possible, because it is a testable property that a random function would not have.

However, with common hashes like SHA-256, and $+$ taken as concatenation $\|$, something quite similar is possible: with $y$ starting with a certain prefix depending only on the length of $x$ (or $x$ ending with that), we can compute $\operatorname{SHA-256}(x\|y)$ from $\operatorname{SHA-256}(x)$ and $y$. That's the length-extension property (which breaks SHA-256 in the Random Oracle Model not adapted to allow the length-extension property, but is not against the originally stated security objectives of SHA-256).

Still with $+$ being concatenation, it seems possible to craft a hash without any restriction on the content of $x$ and $y$. However the solutions that I immediately see have some drawbacks, like a lesser security argument, constraints on the length of $x$, or/and reduced efficiency.

$\endgroup$
  • $\begingroup$ Nice, thanks @fgrieu. I'll definitely take a look at the length-extension property. $\endgroup$ – gysyky Mar 24 '17 at 10:48
3
$\begingroup$

If I understand correctly, you want C to be able to prove that they have $x$ at time $y$ (given that we know they had $x$ at some earlier time).

Your idea is that B wants to be able to verify that the value C provides is actually $\mathrm{hash}(x \| y)$. Further,the idea is that given $\mathrm{hash}(x)$ and $y$, B can calculate $\mathrm{hash}(x \| y)$ and compares with C's value; if they match, all is good.

The problem is that this doesn't provide you the guarantee you want. We know that at some point C had $x$, so C can easily remember $\mathrm{hash}(x)$ and repeat exactly the same calculation as B performs.

It feels like this is the sort of thing you ought to be able to do with some sort of asymmetric cryptography, but I don't know how.

Other concerns: This would be easier if $y$ was a random challenge provide by B. If that's not acceptable for some reason, C needs to derive $y$ by hashing a certificate returned by an time-stamping service. C will then need to send this certificate to B and B will need to verify it.

$\endgroup$
  • $\begingroup$ Thanks for your insights. Turns out there's one more thing I forgot to mention in the original question: everything that B knows is public, I'm not sure if random challenge would work in such case. $\endgroup$ – gysyky Mar 24 '17 at 13:04
  • $\begingroup$ They don't actually need to be random - just unpredictable. So C can't 1. work at what y will be in a year's time; 2. calculate the value; 3. remember it; 4. throw x away; 5. send out the saved value at the appropriate time $\endgroup$ – Martin Bonner supports Monica Mar 24 '17 at 13:50
  • $\begingroup$ A heartily welcome to crypto, Martin. Your reputation precedes you. I'll try and get back to you when I need a Greenland paddle (woodworking reference) ;) $\endgroup$ – Maarten - reinstate Monica Mar 25 '17 at 13:31
2
$\begingroup$

It really depends on your hash function and operator. For example, for Merkle-Dåmgard hash functions (MD5, SHA1, SHA2) and concatenation, it is easy. For SHA3, in general you cannot determine $\mathrm{hash}(x \| y)$ without knowing $x$.

$\endgroup$
  • 1
    $\begingroup$ "it is easy" is an oversimplification. We need additional constraints on either $x$ or $y$. See my answer. $\endgroup$ – fgrieu Mar 24 '17 at 10:35
  • $\begingroup$ Thanks for your answer Mark. As noted in my question, I'm really interested in mechanism how could I implement a system with such possibilities. To clear up a bit: - y is public, it's a timestamp - there is A who knows x - it's a file - A tells B hash(x) (or any other needed piece of information about x, but not the x itself - it's too big) - A sends x to C - C needs to send confirmation to B "I have x at the moment, as a proof here's hash(x, y) - B needs to verify that what it received is indeed a hash of a file and a timestamp $\endgroup$ – gysyky Mar 24 '17 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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