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 have a program (whereby people can download and run on their own computers) that will calculate a couple of unknown values each day. For simplicity sake, let's assume that the calculation is simply Rand(0, 1). The program will run and the user will get a value e.g. 0.230957203975.

He will then broadcast this value to anyone interested. He will say "my number today is 0.230957203975!". The problem is that the user can simply lie about the number.

How can we make it such that the user cannot lie? Or rather, how we can detect it if he lies?

I've came up with a solution, but it's sub-par and will be easily defeated. My solution is to broadcast the value 0.230957203975 along with a verification-value calculated as such:

verification_value = SHA2(MD5(RIPEMD(SHA2(HAVAL(GOST(MD5(0.230957203975)))))))

The problem is that the user can examine the machine code, and know the obscure mixture of hash functions used, enabling him to calculate the verification-value himself and lie about the number he had gotten.

I've browsed through Applied Cryptography, but none of the protocols mentioned there seems to have a solution. Is cryptography able to solve this problem?

share|improve this question
    
Is verification-value known beforehand? If so, you can sign it with your private key. (Then everyone who has your public key can verify its correctness.) –  Reid Jan 18 at 3:17
    
@Reid,We can set the program up such that verification-value is known beforehand, However each user will be calculating many values and all of them needs to be verified. How could the verification-values be known beforehand when the value is still not known? –  Pacerier Jan 18 at 7:02
1  
In 2, there is the problem that anyone (with your public key) can compute the verification_value accrediting a fake, and even you can not detect that. –  fgrieu Jan 18 at 9:23
    
Can you assume that a key embedded in the software remains secret? If yes, the simplest solution to your problem seems to be a MAC, such HMAC with SHA-256, used to generate verification_value as HMAC(key,0.230957203975), and re-generated from the alleged 0.230957203975for verification purposes. –  fgrieu Jan 18 at 9:57
    
@fgrieu, Since people can download and run the software, the key could definitely be extracted and leaked. Especially so since everyone's copy of the software is going to be using the same key for hashing/verifying right? –  Pacerier Jan 18 at 15:27

2 Answers 2

From my point of view, multi-hashing will slow down things, but it won't add the security you are looking for in this case.

Is cryptography able to solve this problem?

Yes. What you need is a message authentication code (MAC), which is a short piece of information used to authenticate a message and to provide integrity and authenticity assurances on the message. Integrity assurances detect accidental and intentional message changes, while authenticity assurances affirm the message's origin.

For your further research endeavours, "MAC" and "HMAC" are the relevant keywords.

Nota Bene: In bis comment, @fgrieu hints at practically using a HMAC with SHA256... which indeed seems to be the most logic choice (because it's pretty minimal while currently offering expected security).

share|improve this answer
    
But the program is downloaded and run on the user's own computer, thus isn't there no way to hide the key from the user? As such, isn't using a MAC simply another form of obfuscation that can be easily defeated by a determined user? –  Pacerier Jan 19 at 2:46
1  
@Pacerier Seems you're facing more than one crypto-problem. At first glimpse, Zero-Knowledge Proof comes to mind as a potential solution. There are a few Zero-Knowledge Proof Q&As around here (which are more enlightening than Wikipedia). E.g.: this one talks about password verification protocols - which could be a usable piece to your puzzle (just think "password = your key", so you don't have to store it as-is on the client-side). –  e-sushi Jan 19 at 14:16
    
@Pacerier Looking at your problem again, it's less of a "ensure that a “received value” is not altered" thing, but more of a "is user authorized to send a message" and "is message transmitted without interaction/modification by user" problem. In that case, you'll have to look at protocols related to authorization and co. instead of (H)MACs - as they will most probably be part of the individual protocols anyway. –  e-sushi Jan 19 at 14:24
1  
@Pacerier There's one thing you won't be able to work around though: you can't verify the random number itself because (true) randomness can't be predicted and therefore not cross-checked. If you receive the number 0.230957203975 (by whatever means and protection), you will not be able to learn if I injected that number into your software or if it's the result of your software's random function. Simpler said: client-side software can always lie. Unless you control the security of that function (eg: server-sided), your client-sided idea will keep leaning towards the software-obfuscation area. –  e-sushi Jan 19 at 14:40

If you want to be sure the value is not altered in transit by an active attacker that is occupying the wire then what you need is an integrity mechanism that will guarantee that nobody has tampered with the message. Such mechanisms are instantiated with the employment of a message authenticated code (MAC) which are build on top of secure crypto primitives such as block ciphers and hash functions.

Also what do you mean by lying? Is it that on input $a$, $f(a)=b$ and the user submits $c$ instead. Then you just publish the function.On the other hand if you want to convince the other parties that the values you sign and you send is a truly and reliable evaluation of a function then you need a zero knowledge proof of knowledge of the output of the function if you want to keep the value secret

share|improve this answer
    
MAC considers a symmetric setting in which two clients have agreed on a secret key –  curious Jan 18 at 17:16
1  
Yes, upon f(a) = b, the user submits c instead. I'm not sure what you meant when you say publishing the function can solve the problem. Publishing the function wouldn't help, since the function is Rand(0, 1) (for the actual function see the comment I wrote to DrLecter) –  Pacerier Jan 19 at 3:05

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.