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 was torn between posting here or security.stackexchange.com. In the end, I felt that this was more of a design question, rather than an implementation question and so chose this forum.]

My question is: How do I assure myself that the results data submitted to me was generated by my official build of an open source program?

I'm developing an open source program. The program essentially collects data, performs some calculations, and sends back the data and results to me. The program is for all intents and purposes offline. More often than not, I'll get the results data back via a single HTTP post of XML data if I'm lucky, or more likely an emailed XML file, or a USB key with the XML for pure SneakerNet mode.

I will be releasing official builds of the program with the appropriate Authenticode signatures. (My target platform is Windows.) The Authenticode signing will prevent tampering of the program. Presumably, the program will be digitally signing the results data to prevent tampering of the data as well as establish the chain of evidence that the data was generated by this particular build. But how do I go from these "hand-waving" concept to actual implementation?

Since the program is open source, anybody else can also build the program, examine how it works, and potentially modify the program to perform some "cheating" or the results data that sent, as well as bypass any self-integrity checks I may embed in the code.

Here is what I've thought through so far:

Obviously, I'll be the only one holding on to the code signing keys. First layer of defense would be for the program to do a self-check for a valid Authenticode signature on all binaries. As as next layer, assuming it's doable, is verify that all binaries were signed using the same signing keys. I don't want to hardcode any attribute of the signing keys just in case somebody else wants to build their own official builds and verify that they are getting results from their official builds.

Although, the program integrity seems to be good, since it's open source somebody can always edit the code and make a build that doesn't do any self-integrity checks. :-(

The next bit of the puzzle is putting some characteristics of the running program binaries into the results XML. This could be simply a hash of all the running binaries. My server that accepts all the data can check the hash for a known good value. A malicious build can't bypass putting in a hash if the results data to be considered valid by the server, but it can just go ahead and compute the hash of all the official binaries and put it in the results XML. Essentially a replay attack. :-(

The next bit of the puzzle is how to digitally sign the results XML. This is a biggie. To do XML digital signatures, I'll need both the public and private keys. How do I embed these two keys into the program? Obviously checking them into source control is a really bad idea. :-(

I can hold the keys private the same way I held the code signing keys private and only at build time insert the keys as resources into the program. But I'm essentially publishing those keys once I release an official build. Anybody who looks at the source will discover that the keys are held in the resources and can get the keys themselves. :-(

Is there a public key system where I can generate my own private/public key pairs using characteristics of the official binaries? But this still suffers from the issue as above where a malicious build can just pick up those same characteristics from the official build. :-(

Any help or guidance on where to look for possible approaches to solve this problem would be most helpful.

Update: Think of this problem as building an open source voting machine. The Commission of Elections would like to build its own machines and distribute these for the elections, but it wants the source open to the world so that there are no rumors of impropriety. The commission doesn't care if the local Rotary club also makes their own voting machine for their board, but that machine should not be used to submit votes for the US Senate.

share|improve this question
add comment

3 Answers

I'm pretty sure it's impossible for software alone to do everything you suggested. Asymmetric encryption can solve part of the problem.

I suspect that, even though asymmetric encryption can't do everything you suggested, it can get close enough to solve your real problem. Perhaps you can give a high-level explanation of what you're really trying to do, and post that as a separate question. Perhaps there's some way of doing that, in a completely different approach that doesn't require most of the things you suggested.

Pretty much everything you suggested can be accomplished with a combination of special hardware and software called "Trusted Computing" by some, and "treacherous computing" by others.

Asymmetric encryption

Asymmetric encryption can solve part of the problem: You can safely publish your public key, posting it (among other places) into version control.

When a "good program on a good system", it can generate a fresh set of private keys, calculate the corresponding public key. Then it can save to disk/flash key the program's public key, the reported data, and MAC signatures of that data (either in separate files or all lumped together in one big file). Optionally, the program could encrypt that data with your public key. There are several open-source libraries for generating private keys, using them to sign data with MAC, etc. The articles Wikipedia: RSA, Wikipedia: GNU Privacy Guard, Wikipedia: elliptic curve cryptography etc. all have links to open-source libraries.

As long as the "good program on a good system" keeps the private keys in RAM, then after the private keys are lost (on power down), it's impossible for anyone else to successfully pretend to be that system -- even if the exact same hardware is later compromised. In particular, it's impossible to perform a replay attack.

Trusted Computing, aka treacherous computing

The "remote attestation" feature of "trusted computing", aka "treacherous computing", seems to do everything you want: It verifies that the software running is the official version of the program you wrote, and that no debuggers or other tools are interfering with its operation.

Most name-brand desktop and notebook computer manufacturers already include the "Trusted Platform Module" in at least some of their computers.

share|improve this answer
    
I must be missing it in MS's Base TPM Services API, but I don't see a way I can submit my program's running state to get "remote attestation". –  Ants Aug 30 '11 at 0:22
add comment

You need your official builds to create a signature with some kind of key,

  • without anyone being able to extract this key from the program, and
  • without anyone being able to use that part of the program to sign anything else than what you intended it to sign.

(Actually, private builds should be able to do the same thing, just with another key provided to the build script.)

The first point is what white-box cryptography is about. (Usually this is about encryption, but building a MAC or an (asymmetric) digital signature would be similar.)

Have a look at for some more discussion of this topic, and links to other resources.

Creating an open-source white-box implementation (e.g. an open-source program which at build-time creates the signing program part with a build-in hidden key) is of course even more difficult than the usual closed-source implementations.

Also, it is quite difficult (maybe even impossible) to make sure that the attacker can't simply extract and use this signing function to sign whatever she wants it to sign, instead of what you intend the program to sign. So it looks like you have to put your program integrity check inside the same function, and maybe use part of the result of this integrity check as some input to the signature function.

I don't know if there are already papers covering such signature techniques.

share|improve this answer
1  
I don't think this answer is correct. White-box cryptography (as currently considered in the literature) handles only the first of your criteria. It doesn't prevent others from using that part of the program to sign something other than what you intended. To the best of my knowledge, there is no good known solution to the latter problem. It is basically the copy protection problem, which is notoriously an arms race that the bad guys can always win if they put enough effort into it. –  D.W. Aug 28 '11 at 8:12
    
Thanks for your comment. I'm not that much of an expert in white-box cryptography, but I think the second point is in practice almost as important as the first one (but much more difficult to ensure, as I wrote at the end of the answer - even more in a open-source environment). I think I have read some mentioning of it in one of the papers I read, but you are right, the first part is the one traditionally meant by white-box cryptography. –  Paŭlo Ebermann Aug 28 '11 at 10:13
add comment

The best solution is to have one source file that you keep secret. Have a flag that marks whether it's the official build or the open build. The open build will not use that source file. Inside that source file, have an algorithm that is obfuscated that generates a checksum that you can verify. Keep the algorithm secret.

You can basically just make the algorithm random. To verify, simply use the exact same function to generate the exact same checksum on the received data and see if they match.

That leaves the only ugly part of someone excerpting the checksum function from your program and embedding it into their own.

I could probably give you a much better solution if I really understood your problem. Why do you care whether or not the results came from your official build?

Another little trick -- you can have some very subtle difference between the output of the open source version and the private, official version, such as a vertical tab in the output or a space before a newline. Check for that difference, and if you don't find what you expect (but do see a checksum), pretend to accept the results but secretly, you'll know they're bogus. Likely, nobody will even notice you are doing this.

You can implement this in code by having your checksum function call a function that modifies a global variable. That way, you don't have to modify any other code to get this difference. It takes some cleverness to hide it, but it's not that difficult.

For example, put this in the main code:

char *msg1="Your final results are:\n";
char *msg2="--End of results--\n";

And this in hidden file:

char *CalculateChecksum(struct results *res)
{
 msg1="Your final results are:\r\n";
 msg2="--End of results-- \n";
 // code to calculate a checksum
 ...

Note the two extra characters? This will allow your official builds to have a subtly altered results page that will look identical on casual inspection. Nobody looking at the public code would likely even suspect that some other code changes those to point to another string.

share|improve this answer
    
I care about the authenticity of the reports, because the data sent back is the result of a competition where prizes and money can be at stake. Imagine a bowling league scoring program, whoso results are combined for a nationwide postal match. Local clubs are free to use either the official build or their local build. If they want to participate in nationwide match, they have to use the official build. –  Ants Aug 26 '11 at 16:47
    
Tweaking a global variable is very likely a no-go because any code reviewer worth their salt will say msg1 and msg2 are constants, declare them as such. If I balk at accepting the change, then the game is up that voodoo happens with these. –  Ants Aug 26 '11 at 22:45
    
Subtly adjusting the output isn't going to stand up because if somebody writes a unit test to inspect the output, the unit test will fail. I can't waive my hand and just say "There are not the results you are looking for." –  Ants Aug 26 '11 at 22:47
    
If msg1 and msg2 are constants, how could you change the output language at run time? They can be part of a localization table, for example. You're going to have to be clever, there is no straightforward way to be obscure. –  David Schwartz Aug 26 '11 at 22:55
1  
LOL! I'll have to remember that quote "You're going to have to be clever, there is no straightforward way to be obscure." –  Ants Aug 26 '11 at 22:59
show 2 more comments

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.