I want to be able to detect tampering in a log file that is under the control of an untrusted party. I am not interested in secrecy, only the integrity of the contents in the file - so I want to detect if entries have been removed/changed. The solution that I seem to have found from a short google search is to use hash chains linking the current log entry to all other previous entries. The untrusted party publishes the hashes with some acceptable frequency such that any tampering after the time of publishing can be detected. Is there any technique that will accomplish something similar without the need for publishing the hashes frequently?
1 Answer
The verifier and logger start with a seed for a forward-secure pseudo-random number generator.
To denote a valid ending of a log, append the string of the next $b$ bits of the PRNG's output
to the end of the log. $\;\;$ To add a log entry, get the next $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits of the PRNG's output,
use the last $k$ of those bits to mac the new content, append the concatenation of the new
content with its mac to the log, and then erase those $\:b\hspace{-0.03 in}+\hspace{-0.03 in}k\:$ bits and the previous PRNG state.
This allows you to replace "The untrusted party publishes the hashes"
with "The untrusted party erases the old PRNG state".