| |||||||||||||
Forward secure sealingForward secure sealingPosted Aug 25, 2012 0:51 UTC (Sat) by nybble41 (subscriber, #55106)In reply to: Forward secure sealing by dlang Parent article: Forward secure sealing
I don't know about that. If you ignore the "none of the lines are missing" part, which I never saw claimed anywhere, it seems like a fairly simple problem to me. For random verification key V, signing keys K[n], messages M[m], and signatures S[m], with n, m >= 0 and "+" signifying concatenation:
K[0] = HASH(V)
From V you can get any K[n], and from any K[n] you can get K[i] where i >= n, but not V or K[j] where j < n. From K[n] and M[m] you can get S[m], and with K[n], M[m], and S[m] you can verify that M[m] was logged while K[n] was known. Periodically you would calculate and store a new K[n] and securely wipe K[n-1].
Once an intruder is on the system they could wipe the logs (in full or selectively), and fake any _future_ messages signed, but not _past_ entries requiring signing keys which have already been wiped from the system.
(Log in to post comments)
Forward secure sealing Posted Aug 25, 2012 0:55 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
If an attacker can delete individual log entries, the sealing or hashing of the logs is worthless
If an attacker can delete all log entires newer than X and put whatever they want after that point, the logs are again worthless.
These are the sorts of things that the initial hashing implementation from systemd was broken on, and why I am skeptical of further security claims from the same product.
Forward secure sealing Posted Aug 25, 2012 1:10 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
> If an attacker can delete individual log entries, the sealing or hashing of the logs is worthless
There is some value in ensuring that an attacker can't fabricate log entries from before the break-in. If you want to prevent any individual log entries from being deleted, or (more likely) detect any such deletions, you have no choice but to send _some_ data (the log entries or an updated hash) to an external, uncompromised system.
> If an attacker can delete all log entires newer than X and put whatever they want after that point, the logs are again worthless.
That the attacker will be able to fabricate new log entries after the break-in is inevitable, even if you log to an external system. This scheme does prevent the scenario you describe for new log entries between time X (assuming X is before the attack starts) and the generation of the signing key in effect at the time of the actual compromise.
This could be combined with hash chaining to make it harder to get away with erasing individual log entries while keeping other, later, entries. For example, each message M[m] could include the signature of the previous message (S[m-1]). That would make any gaps rather obvious, without requiring you to have all previous log entries on hand to verify the hashes.
Forward secure sealing Posted Aug 25, 2012 1:24 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
> you have no choice but to send _some_ data (the log entries or an updated hash) to an external, uncompromised system.
This is part of my point
If you are required to send _some_ data, then simple hashing is enough (as implemented by logtools for example)
The claim here is that by sending the verification key off of the system at key creation time, there is no need to ever send any other data off of the system for you to know that your logs haven't been tampered with.
If you can truncate the file (either partially or create the entire logfile) and write bogus stuff after the breakin, you can truncate the part of the file that shows the breakin and re-create everything after that point, making the logs look like they had been created before the breakin.
Forward secure sealing Posted Aug 25, 2012 1:49 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
> you can truncate the part of the file that shows the breakin and re-create everything after that point, making the logs look like they had been created before the breakin.
Assuming the messages are chained as I described, that's only true if you're willing to accept a gap in the logs from the first deleted entry to the beginning of the valid interval for the K[n] in effect at the time you compromised the system.
> If you are required to send _some_ data, then simple hashing is enough
The "simple hashing" requires you to send data _continuously_ as the logs are updated. That's a more difficult problem than making a record of a single verification key once at the beginning of the log.
Forward secure sealing Posted Aug 25, 2012 1:59 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
> hat's only true if you're willing to accept a gap in the logs from the first deleted entry to the beginning of the valid interval
so you delete everything and there's no 'valid' entry to compare anything to that will let you detect the gap.
I understand that they are claiming that this verification key eliminates the need to send any data off the box ever again, I'm just not believing it. If someone can point me to the peer reviewed papers that describe how the technology can work, I'll believe it.
Forward secure sealing Posted Aug 25, 2012 2:12 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
> so you delete everything and there's no 'valid' entry to compare anything to that will let you detect the gap.
If you deleted everything then I wouldn't need a "valid" entry to compare against; the simple lack of previous logs would be plenty suspicious by itself.
Forward secure sealing Posted Aug 25, 2012 0:59 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
> but not _past_ entries requiring signing keys which have already been wiped from the system.
only if the person doing the verification can know that those log entries needed to be signed by an old key.
If the signing doesn't create gaps, what stops someone from creating new log entries that look like old ones, but are signed by the newer key?
remember that everything that systemd relies on as part of it's validation can be forged by a root user (including the SCM_CREDENTIALS, which even systemd forges when sending the logs on to syslog)
Forward secure sealing Posted Aug 25, 2012 1:12 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
Presumably the key rotation is on a well-defined schedule, so a given key is only used for a given interval. "Old" entries with a new key would be suspicious.
Forward secure sealing Posted Aug 25, 2012 1:16 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
The question is how the verification can tell that there weren't gaps in the process.
how can it tell key 20 from key 2000? or more precisely, how can it tell that something was signed by key 20 instead of being signed by key 2000.
Forward secure sealing Posted Aug 25, 2012 1:33 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
> how can it tell key 20 from key 2000? or more precisely, how can it tell that something was signed by key 20 instead of being signed by key 2000.
The keys follow a very specific pseudo-random sequence. K[2000] = HASH^2000(K[0]) is an entirely different value from K[20] = HASH^20(K[0]). Using a different key value will result in a different message signature S[m] = HASH(M[m] + K[n]). Assuming the message includes a timestamp t[m], keys are rotated every ten seconds, and you have the verification key V and the initial time t0, then n = floor((t[m] - t0) / (10 seconds)) and you would expect message M[m] to have S[m] = HASH(M[m] + K[n]).
Forward secure sealing Posted Aug 25, 2012 1:37 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
please point me at the technology that lets you tell which key a message is signed with given only the signature and the verification key?
Even if you can do this, you still have the question of how do you know that message should have been signed by key 20 instead of key 2000, or better still, how it should have been signed by key 934503459 instead of 934505459.
Forward secure sealing Posted Aug 25, 2012 1:43 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
> please point me at the technology that lets you tell which key a message is signed with given only the signature and the verification key?
This is an honest question. this seems like it would be a breakthrough in non-reputiation if you can sign one message with a key and send it to person A, a second with the next key and send it to person B and a third with the next key and send it to person C and therefor prove that message B was send between message A and message C
As far as I know, all signing services currently boil down to "we include the timestamp in what we sign, and since you trust our signature, you trust the timestamp", with the trust in the signature being that you trust that nobody else is able to sign anything that can be verified with the verification key you have.
It's very possible that I am ignorant of some digital signing technology here, but this seems like such a useful combination of features that I would have expected to have heard that such things are at least possible, even without knowing the details.
Forward secure sealing Posted Aug 25, 2012 2:05 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
> please point me at the technology that lets you tell which key a message is signed with given only the signature and the verification key?
In this scheme you already know which key the message should have been signed with, so you only need to check that one key. However, if all else fails you could generate every signing key from the verification key up to the present and calculate the message hash for each key, checking it against the provided signature.
> Even if you can do this, you still have the question of how do you know that message should have been signed by key 20 instead of key 2000, or better still, how it should have been signed by key 934503459 instead of 934505459.
I already answered this at least twice. The initial time t0 and key change interval are known. The message includes a timestamp t[m]. If it was really logged at that time, the signing key will be K[floor((t[m]-t0)/interval)].
Since the question has come up, the logging system knows t0 and n in addition to K[n], and rotates keys however many times are necessary after downtime until n is correct for the timestamp of the next log entry.
Forward secure sealing Posted Aug 25, 2012 2:11 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
I'm still trying to find out how you can know which key was used to sign this. remember that you are using the same validation key to check every signature.
You seem to know about this technology, can you point me at a paper on it?
Forward secure sealing Posted Aug 25, 2012 2:14 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link]
You simply take the initial key and do N key derivations, where N is the number of key regeneration intervals since the initial generation and the desired timestamp.
Forward secure sealing Posted Aug 25, 2012 2:19 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
I give you a precise formula for calculating the expected signing key from the validation key, initial time and message timestamp, and you reply that you still can't tell which key was used to sign which message. Clearly we have a communication problem, but I don't have any idea how to bridge the gap.
As for "knowing this technology", I have no idea how systemd actually implements this. I only presented one possible implementation based on the design requirements. Obviously, since I made the implementation up on the spot, I can't point you to any papers; everything there is to know is in this thread.
Forward secure sealing Posted Aug 25, 2012 3:27 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
Ok, the formula you provided will work to generate a symmetric key, Simply using the "verification key" as a seed for a PRNG will do that much (and since the sequence will be unique, walking through the sequence until you find something that matches will work)
However, I was assuming that this was some form of asymmetric key, since that's the norm for signing something. The problem with using a symmetric key is that the person trying to validate the signature is also in a position to forge the signature.
Forward secure sealing Posted Aug 25, 2012 3:41 UTC (Sat) by dlang (✭ supporter ✭, #313) [Link]
by the way, this approach would result in pretty unusable validations for a system that's been running a long time.
if you are on key 9834750927 and need to iterate through that key generation routing that many times to get you from the starting validation key to the key needed to validate the file, it's going to take a long time.
Forward secure sealing Posted Aug 25, 2012 4:54 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link]
You can adapt this for public/private keys as well.
And you can easily walk through the keys. If you do log sealing every minute then key 9834750927 would be some time after 20711.
Given that AES on modern CPU works can produce about 1Gb of data per second, it'll take only a few minutes to walk to that point.
Forward secure sealing Posted Aug 25, 2012 19:00 UTC (Sat) by nybble41 (subscriber, #55106) [Link]
> The problem with using a symmetric key is that the person trying to validate the signature is also in a position to forge the signature.
Yes, but that doesn't matter here, since the person doing the validation is also the person who administers the server; they're _already_ in a position to forge log messages, if they cared to do so.
You are correct that the signing key is basically just the output from a PRNG, but the PRNG does need to have a special property that some PRNGs lack: the computation must only work in the forward direction. Given the internal state of the PRNG, it must not be possible to go back to a previous state and generate a past signing key.
For example, both the following functions will produce a stream of pseudo-random numbers:
F[0] = HASH(seed)
G[n] = HASH(seed + n)
However, only the former PRNG would be suitable, because computing G[n] requires the original seed value, and given the seed you can compute any G[n], past or future.
Forward secure sealing Posted Aug 25, 2012 20:22 UTC (Sat) by ikm (subscriber, #493) [Link]
> S[m] = HASH(K[n] + M[m])
May I suggest S[m] = HMAC(K[n], M[m])?
Also, calculating K[n] from V is O(n). If we use the systemd default of 15 minutes per key, we would have 35,040 iterations per year, which doesn't seem bad. If we, however, decide to narrow it down to 10 seconds, as the article suggested we could, we would get a much worse looking number of 3,153,600 iterations per year, which might get a little expensive, especially if the verification is done on an Android device. Other than that, the scheme you've proposed seems fit and may even be the actual scheme systemd uses.
Forward secure sealing Posted Aug 25, 2012 20:38 UTC (Sat) by ikm (subscriber, #493) [Link]
P.S. I would also propose having a single sealing hash for all messages which have accumulated during a single key validity period. That is, assuming the period of 15 minutes, one accumulates all messages during the [0,15m) period and seals them all in one piece with K[0], then all messages within [15m, 30m) with K[1], and so on. This way you end up saving space as you only store a single hash for each 15 minutes, you prohibit deleting, duplicating or rearranging the individual messages within the sealed block, and the result is not less secure, as even though we don't have the latest unfinished block of messages sealed, it doesn't matter anyway, as the sealing key would be known to the attacker. The idea is to seal the block just before calculating the next successive key and forgetting the previous one, which seems most logical.
Forward secure sealing Posted Aug 25, 2012 21:13 UTC (Sat) by ikm (subscriber, #493) [Link]
Another thought: periods during which no messages were received should still be recorded, with an empty message block body. As long as this is done, any tampering with the historic data, including the deletion of the entire periods can be detected, since there would be a single record required for each period of time. One could define a log rotation policy which always keeps at least N last periods recorded (e.g., given the period of 15 minutes, require at least 1344 records to account for at least 14 last days from now). Any record missing would indicate a tempering attempt.
The only missing piece is what to do in case the system goes down. All log data before the system came up can then be erased with a plausible explanation that the system was down at that time. If an attacker gains entry, he can erase all traces of his activity and hard-reboot the machine once he's done, making everything look like it was a hardware failure. I wonder if journald accounts for that.
Forward secure sealing Posted Aug 28, 2012 14:48 UTC (Tue) by mathstuf (subscriber, #69389) [Link]
> The only missing piece is what to do in case the system goes down. All log data before the system came up can then be erased with a plausible explanation that the system was down at that time. If an attacker gains entry, he can erase all traces of his activity and hard-reboot the machine once he's done, making everything look like it was a hardware failure. I wonder if journald accounts for that.
Well, systemd is the first thing running in these situations. Conceptually, it could do the sealing before starting anything else. The only leak I can think of there is if systemd itself is compromised in which case you're SOL anyways. In the general case, it might be an issue.
|
|||||||||||||