How does one prevent users from tampering with the replay data?
Preventing the modification of data on a system is a difficult problem. Fundamentally a modern computer system (like a smart phone) is designed for the use of the owner. Like every program, application, or game, in almost every instance, the owner of the computer system is not the creater of the program. The program is a commodity that you distribute to many computer system owners. If you were the owner of every computer system your program was distributed to, you would have significant resources to protect your program: everything from legal restrictions to technical controls.
Since you do not own the computer system your program runs on, you must in some way get the owners agreement to protect your program. Even technical components like hardware protection are under the ownership and by extension control of the user. Computer systems are designed to provide the user the ability to efficiently and simply modify the data stored on them. There is an interesting component of this problem which attempts to differentiate programs (instructions) from data, but I won't get into that here.
There are several things a user could attempt to do to data. A user could attempt to corrupt, damage, or destroy the data. The intent may be to deny the data to someone else or to free up resources on their system. A user could attempt to overtly modify the data. An overt modification may be for personal reasons or to demonstrate skill or ability to someone else. Finally a user may attempt to covertly modify the data in an attempt to gain some type of advantage without being detected.
It seems like you are most interested in covert modification. A overt modification is by definition trivial to detect. I think you are concerned with a user modification to data that requires some effort to detect. Remote detection of data integrity is still a difficult problem. So, currently the best way to protect your data is to keep it on systems that you control. The way this is done for smart phone programs is to make your game a client program that communicates with a server.
The data you want to protect remains on the server. Typically you will send copies of some or all of the data to the clients. The client applications will present the data to the user (in the form of graphics on the display) and get responses from the user (in the form of button or key presses, touch screen movements, and tilting or rotating the device) and send the responses back to the server.
This is a heavy price to pay for control of the data. You will need to provide the resources (server, bandwidth, server maintenance, server update, etc) to accomidate all the users of your software. Compare the different attitudes of a user whose smartphone crashes where the fault is not your application, to the attitude of a user who can't play your game because your server is not available.
I suppose I could encrypt/checksum the data and such, but if they peek through the binary it might be possible to get the private key or whatever algo used.
This supposes that you are attempting to protect the game data on the user's smartphone. If you do go this route I would recomment against encrypting the data. It does not seem like your purpose is to prevent the users from seeing the data, you just want to prevent the user's from changing it without your detecting it.
The algorithm used shouldn't matter. The concensus in the security community is to focus your effort on protecting keys, and not on protecting the functioning of algorithms. Given a well designed publically known algorithm and a well protected key, it should be hard for an adversary to defeat your security.
Hash algorithms are used to provide integrity to data. Given some data m and a hash function H, x = H(m), where x is a hash value. So your game generates the data m and calculates x = H(m). The game sends m and x to you. You calculate H(m) and see if x is equal to H(m). If x is equal to H(m) the data has not been modified since the hash was calculated. But wait, what if the user gets ahold of m before your game sends it and changes it to n, amodified version of the original data m?
Then your game computers y = H(n) and sends n and y to you. You calculate H(n) and find it is equal to y. Your conclusion is that the data is unmodified! How could this happen? In the last paragraph I said calclating the same hash value proves that the data has not been modified since the hash was calculated. If a user can modify the game data before a hash is calculated then you will not be able to detect their modification. How can you detect a user modifying the data before calculating the hash? There are a few answers, but lets address the effort involved first.
I realise this is probably overkill for an iPhone game, but I suppose it's better to be safe than sorry?
It depends. You will need to expend resources to protect the dame data. How much protection your provide depends on the value of the game data to you. Economically, it does not make sense to spend more to protect the data than the data is worth. If you use the data to award prizes, then the data has the value of the prize or prizes it is capable of awarding, and your should spend as much as all the prizes are worth. All the prizes because the data is used to award all the prizes. If the data provides bragging rights, then it depends on how much the bragging rights are worth to you. Simply, the value put into protection should not exceed the value of the asset being protected, but that value may be hard to define.
How to prevent the user from modifying the data before the hash is calculated?
Use a protected key. Instead of using a simple hash algorithm, use a digital signature or HMAC (Hashed Message Authentication Code). The problem with both methods is they both require the use of a private key which must be protected. Protecting the key on a user's device is still a hard problem, so why might your do this? There may be hardware on the device that protects keys from the user. The key is much smaller than the data and it is easier to protect a small amount of data then a large one.
Make the data harder to access. Keep the key in memory and never write it to a file. Use operating system protected memory or file storage. Make the location of the data (in memory or in file) difficult to find by using non-deterministic (random) methods. Encrypt the data. All of these solutions have problems. Even if a key is never written to a file, sophisticated adversaries can copy it out of memory or modify it in memory. The Operating System, iOS in this case, can be hacked, or it's protection rendered innefective. Random use of memory can be easily found if the adversary traces the random data to the method that selects the address in memory or in the filesystem.
Distribute the data among users. If your copy the data of one user to a few others and then when a user send their data to you they also send the data of two (arbitrary) other users, then when a user modifies their data the two other copies will not match. The first problem with this method is it depends on two (or whatever number you pick) users being available to store the data. It also depends on the user not modifying their data before it gets copied and send to the two other users, which is similar to the original problem. It also depends on the two other users not collaberating with the first user to modify their copies the same way as the first user.
