Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I'm toying around a distributed computing project. The client application asks for a problem to solve. The server returns a problem description from a "problems pool". When the client finishes, it sends back the solution.

I cannot trust my users, and so I cannot trust their solutions. I need somehow to validate their solutions are correct (for some definition of "correct"). Anyone could send a wrong solution to the problem they are assigned. I want to validate two things:

  1. No one can post a solution for a problem that I have not give them. I think this one is easy: I give a them an HMAC of the problem ID plus my secret, and check that they send the same tokens with the solution.
  2. I want to check that the user's solution is correct. I want to do this check without solving the problem by myself. And more important, I don't want the solution to be problem-specific, so I cannot use some property of the problems, which could work for NP-(Complete/Hard) problems, for instance.

Suppose, for the sake of the discussion, I want to compute the digits of PI. So how can I be sure that some user's response for the nth digit of PI is correct? Should I give the same problem to several users and cross validate? How is this problem handled in projects like SETI@home and others?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Distributed.net solved this by assigning the same search space to multiple users, and validated them that way. (They are probably still doing it.)

Depending on computation cost and participation levels, you might wish to double check only a fraction of packets. Comparing 5% should give you a statistically valid chance of catching a cheater. Be sure to randomly distribute the duplicate challenge blocks around, so that you don't only have User A validating User B's packets. Don't identify the test blocks in any way, such as sending a different size or range, or a cheater may tamper with them. And finally, know that one positive result does not indicate a malicious cheater. It could be a hardware or software problem. You need to see a pattern of abuse before you pull the plug on someone.

EDIT:

Here's a link to distributed.net's Operational Code Authentication document. It describes the security mechanisms by which they handle validating work work distributed to untrustable clients. Of particular interest are some of the other security problems they've identified, such as "solution stealing", where a malefactor distributes a modified client to someone else. The modified client suppresses the "winning results" signal, and instead sends the results to the attacker, who unfairly claims and collects the reward for the find.

share|improve this answer
    
Thanks, I like this approach. It is very close to what I have thought, but I like the idea of validating only a fraction of the packets. Can you provide some links? –  Alejandro Piad Nov 15 '13 at 20:33
    
I edited the question. Regarding statistical validation, you'll have to find a book on the topic yourself - I rely on an old copy of the Datamyte Handbook for Statistical Process Control methods for a lot of that kind of stuff. –  John Deters Nov 15 '13 at 21:34
    
Thanks, I'll look into it. –  Alejandro Piad Nov 15 '13 at 21:35

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.