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 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?

share|improve this question
    
Where do the logs come from in the first place? Are you are sending them to an untrusted server from a trusted one, or do they originate in an untrusted location? –  figlesquidge Nov 26 '13 at 16:16

1 Answer 1

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".

share|improve this answer

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.