2

Carl asks Alice and Bob if they have a file f such that for a secure cryptographic
hash function h, h(f) = K. Both claim to have f, but they can't show the file.

Carl doesn't believe them. He can ask further questions to Alice and Bob, although
they can secretly talk to each other (note that even if Alice or Bob have f, they
can't show f to each other). Could Carl discover whether both have f?
Could Carl discover whether some of them has f?

user70561
  • 21
  • 2
  • 1
    Sounds like a homework question. What work have you done to try to answer this question yourself? – schroeder Mar 17 '15 at 21:42
  • 1
    pssst: the hint is for each to sign the file with their own private keys .... what they do next I leave to your work ... – schroeder Mar 17 '15 at 21:45
  • the concept you are learning is called non-repudiation – schroeder Mar 17 '15 at 21:54
  • @schroeder I couldn't find the solution. I guess I'm too slow for that hint. Note that Carl doesn't know the content of `f`. My assumption was that Carl can't know anything, but I don't know about cryptography. (Btw I'd read the crypt related pages from the wikipedia. Yes, it's not the best. It's not a homework). – user70561 Mar 17 '15 at 23:28
  • read about how you achieve non-repudiation and signing – schroeder Mar 18 '15 at 03:10
  • ... I also don't see any way for signing to help here. –  Mar 18 '15 at 04:40
  • "although they can secretly talk to each other (note that even if Alice or Bob have f, they can't show f to each other)" doesn't really make sense. If they can communicate and choose to collude they effectively become one entity. And it doesn't make sense to figure out if one of both have the file. – CodesInChaos Mar 18 '15 at 11:23
  • Search for proof-of-knowledge, proof-of-possession, proof-of-retrievability for related literature. – CodesInChaos Mar 18 '15 at 11:27
  • Does Carl know `f`, or only `K`? Note that it's not possible to distinguish the case where both Alice and Bob have the file and the case where exactly one of them does, because they can collude to function identically. (The only restriction on Alice-Bob communication is they can't share `f`, but they're also prohibited from sharing `f` with Carl, so Carl can never exploit the one limitation in Alice-Bob communication.) – apsillers Mar 18 '15 at 13:24
  • @aspillers Carl doesn't know about `f`. @CodeInChaos it's an imaginary situation. (It could be that showing `f` is too expensive, or A and B want to deceive C, only A has `f`, but A doesn't want to reveal the secret to B) – user70561 Mar 18 '15 at 14:04

3 Answers3

2

Carl can ask Alice and Bob (independently) to calculate hashes of specific fileparts and compare the results. For example C asks A to calc h(f[0-100]) and receives h' then C asks B to do the same and B returns h''. If h' == h'' they both have the same knowledge about this part of f. You can repeat this for different sections of the file.

Notice: If A and B cooperate (and want to trick C) and only one of them has the file there is no way for C to tell if they both have f or of they're just cooperating.

wischi
  • 121
  • 4
  • with the element that A and B can communicate secretly, I think this approach is defeated – schroeder Mar 18 '15 at 04:24
  • 1
    As I mentioned in the last paragraph. If A and B cooperate against C there is NO way for C to tell! It depends on the problem user70561 is trying to solve if this does or doesn't matter! – wischi Mar 18 '15 at 04:36
  • @wischi the problem is the worst case scenario. If A and B cooperate, or C has `f` it's easy to resolve. What I'm not sure if there is some hash function `f` with some property that could led C to know something. (When you say that is A and B cooperates, is it necessary that one of them have the file `f`?) – user70561 Mar 18 '15 at 08:35
  • Note that there might be a MITM: Alice+Bob try to prove it to Carl, but Carl with Diana try to prove it simultaneously to Elizabeth. To mitigate such issue, A+B would have to add an identification of Carl as a "salt". But chosing a proper identifier might be tricky. Moreover you should be aware of Length Extension Attack, but this is rather a technical detail. – v6ak Mar 18 '15 at 10:23
0

If Alice and Bob can talk to each other secretly, and are willing to collude, there is no way.

Assuming we know that at least one of them has the file (lets say Alice), then any question that Bob could answer if he had the file, he could forward to Alice to answer - Bob would be a "man in the middle".

In any case, if they were willing to collude, they could share the file. Or, since there is nothing identifiable about the file, they could agree that the file is 0 bytes long, thereby instantly "having the same file" which they could answer any question about - any checksum, any computation.

It seems pointless to find out if they "have the same file", unless there is something specific about that file, that differentiates it from any other file.

AMADANON Inc.
  • 1,481
  • 9
  • 9
0

A knows Sa

B knows Sb

Goal: Prove Sa == Sb

Given a one-way function H with the following properties:

H(x, y) = H(y, x) (Commutative)

H(H(x, y), z) = H(x, H(y, z)) (Associative)

C generates random k, l, m, n

C shares k to A only and l to B only, then:

A computes Saₖ = H(Sa, k)

B computes Sbₗ = H(Sb, l)

A shares Saₖ publicly

B shares Sbₗ publicly

A now knows Sa, k, Saₖ, Sbₗ

B now knows Sb, l, Saₖ, Sbₗ

C computes Saₖₘ = H(Saₖ, m)

C computes Sbₗₙ = H(Sbₗ, n)

C shares Saₖₘ and Sbₗₙ publicly

A now knows Sa, k, Saₖ, Sbₗ, Saₖₘ, Sbₗₙ

B now knows Sb, l, Saₖ, Sbₗ, Saₖₘ, Sbₗₙ

A computes Sbₗₙₖ = H(Sbₗₙ, k)

B computes Saₖₘₗ = H(Saₖₘ, l)

A shares Sbₗₙₖ publicly

B shares Saₖₘₗ publicly

A now knows Sa, k, Saₖ, Sbₗ, Saₖₘ, Sbₗₙ, Saₖₘₗ, Sbₗₙₖ

B now knows Sb, l, Saₖ, Sbₗ, Saₖₘ, Sbₗₙ, Saₖₘₗ, Sbₗₙₖ

C computes Saₖₘₗₙ = H(Saₖₘₗ, n)

C computes Sbₗₙₖₘ = H(Sbₗₙₖ, m)

C compares Saₖₘₗₙ and Sbₗₙₖₘ must be equal.

Due to commutativity and associativity, we know that Saₖₘₗₙ == Sbₗₙₖₘ if Sa and Sb are equal.

This is inspired by n-ways Diffie-Hellman-Mekrle Key Exchange, but how the things are put together is of my own invention just a few hours ago without doing mathematical proofs or proper analysis, there is probably a glaringly obvious hole there that I didn't just thunk about.

The H function in Diffie-Hellman would probably be usable here, with a little bit of modification.

Assumptions:

  • A and B cannot share Sa and Sb with each other
  • A and B cannot share k and l with each other
  • C has a way to verify that A and B are doing their calculations using the correct file (they can't collude to both use another file instead of Sa and Sb to fool C)
  • C has a way to make it impossible for A and B to leak k, l to each other. For example, k, l may be stored in a hardware token that can be be unlocked by a password known only to C.
  • A, B, and C does not all have to be at the same place at the same time

Disclaimer: I'm not a mathematician or cryptographer, and I don't play as one on TV. Inventing your own cryptography scheme may be harmful to your security. You agree to assume all risk from the use of this material, and release me from any responsibility for any harm caused, real or imagined. No representation or warranty, express or implied, with respect to the completeness, accuracy, fitness for a particular purpose, or utility of these materials or any information or opinion contained herein.

Lie Ryan
  • 31,089
  • 6
  • 68
  • 93