Forward secure sealing

By Jake Edge
August 22, 2012

When a system is compromised, the attackers may try to cover their tracks so that the administrator is not alerted to the attack. One way for an attacker to hide is by removing log file entries that might lead an administrator (or a log file analyzer) to notice. A new feature in the systemd journal, "forward secure sealing" (FSS) is meant to detect log file tampering.

Traditionally, administrators have written log files to external systems across the network or to a local printer—though paper is notoriously hard to grep—to defeat log file tampering. As long as the other system is not compromised, and log file lines are written immediately, an attacker can't help but leave their "fingerprints" behind. But FSS provides a way to at least detect tampering using only a single system, though it won't provide all of the assurances that external logging can.

Systemd developer Lennart Poettering announced FSS on August 20. The basic idea is that the binary logs handled by the systemd journal can be "sealed" at regular time intervals. That seal is a cryptographic operation on the log data such that any tampering prior to the seal can be detected. So long as a sealing operation happens before the attacker gets a chance to tamper with the logs, their fingerprints will be sealed with the rest of the log data. They can still delete the log files entirely, but that is likely to be noticed as well.

The algorithm for FSS is based on "Forward Secure Pseudo Random Generators" (FSPRG), which comes from some post-doctoral research by Poettering's brother Bertram. The paper on FSPRG has not been published but will be soon, according to (Lennart) Poettering.

The announcement on Google+ and its long comment thread do give some details, however. FSS is based on two keys that are generated using:

    journalctl --setup-keys

One key is the "sealing key" which is kept on the system, and the other is the "verification key" which should be securely stored elsewhere. Using the FSPRG mechanism, a new sealing key is generated periodically using a non-reversible process. The old key is then securely deleted from the system after the change.

The verification key can be used to calculate the sealing key for any given time range. That means that the attacker can only access the current sealing key (which will presumably be used for the next sealing operation), while the administrator can reliably generate any sealing key to verify previous log file seals. Changing log file entries prior to the last seal will result in a verification failure.

As a bell—or perhaps a whistle—the key generator can create a QR code of the verification key, which can be scanned so that the key doesn't have to be typed in.

Anything that happens after the system is compromised is under control of the attacker, as was pointed out multiple times in the comments. That means that local logs cannot be relied on after that point, but it also applies to remotely stored—or even printed—log files. The latter two methods do protect against an attacker simply deleting the local log files, though.

By default, FSS will seal the logs every 15 minutes, but that can be changed at key generation time with a flag: "--interval=10s" for example. The system clock time is used in the generation of each new sealing key, which is why the interval must be specified when the keys are generated. The default value surprisingly leaves a rather large window for an attacker who immediately turns to altering the log file, though. One also wonders if subtle (or not so subtle) manipulations of the system clock might be a way to subvert or otherwise interfere with the key generation.

Securely deleting the old sealing key is handled by setting the FS_SECRM_FL and FS_NOCOW_FL file attributes, which may or may not be implemented by the underlying filesystem. That could potentially lead to leaks of previous sealing keys, which would allow an attacker to make changes to earlier entries. Obviously, losing control of the verification key means that all bets are off as well.

The code is available already in the systemd Git repository. Poettering notes that it will also be available in Fedora 18.

FSS is an interesting feature that will likely prove useful for some administrators. It certainly doesn't solve all of the problems with detecting attackers or compromised systems, but it could definitely help by raising red flags. There is more to do, of course, starting with a security audit of the code—more eyes can only be helpful in ferreting out any holes in the algorithm or implementation. Once that's done, administrators can feel more confident that their log files aren't undetectably changing out from under them—at least if they are using the systemd journal.

Index entries for this article
Security	Cryptography
Security	Tools/Attack detection

to post comments

Forward secure sealing

Posted Aug 23, 2012 3:25 UTC (Thu) by dlang (guest, #313) [Link] (49 responses)

people interested in this sort of thing may be interested in looking at the logstore utilities that the rsyslog author wrote

http://www.rsyslog.com/logtools-0-1-0-released/

work is underway to add digital signatures to this

http://www.logtools.org/logstore-digital-signatures/

This has the advantage that it can work with any logfile and isn't tied to any particular log format.

Forward secure sealing

Posted Aug 23, 2012 11:04 UTC (Thu) by mezcalero (subscriber, #45103) [Link] (48 responses)

Judging by the description of logtools on that web site, it also has the big disadvantage of requiring the admin to copy the topmost SHA1 hash off the machine all the time, which requires infrastructure, adds fragility and is much less straightforward to use.

And I don't understand the point of the signing logtools is supposed to do: if the signing key stays around locally, and is not changed regularly an attacker can sign anything he wants with it, including messages from the past.

In summary: what systemd's journal does here, and what logtools does is very different. And um, I think FSS is much more useful for admins.

Forward secure sealing

Posted Aug 23, 2012 19:39 UTC (Thu) by dlang (guest, #313) [Link] (47 responses)

logtools doesn't sign things currently, but it's planned for the near future.

All your objections to the signing key apply equally to the systemd signing key. In all cases the key needs to be around locally so that it can be used to sign new logs, and if the attacker can get access to it, they can delete the existing log and fabricate a new one.

Yes, the hash needs to be sent off the machine, but it's a lot less data to send than sending every log.

logtools was created as a response to systemd claiming that it's hash chains made their logging tamperproof. Unlike the systemd announcements, logtools calls out the weakness in this (that the entire logfile can be recreated unless the hash is sent off the machine)

Forward secure sealing

Posted Aug 24, 2012 0:49 UTC (Fri) by mezcalero (subscriber, #45103) [Link] (46 responses)

No, we do not sign anything. We do not do what cryptography understands under the terminology "signing". We also don't do "hash chains". And no, none of my objections to logtools apply to the journal, that's why I pointed them out.

And no, with the systemd journal the sealing key (that remains on the system) cannot be used to "change history". The old sealing key is forgotten and erased when a new sealing key is calculated and you cannot get back from the new one to the old one.

Next time, please read what I wrote, before commenting about the technical background of it, please.

Again: the FSS stuff is very different from what logtools does. Please read up. The journal's FSS stuff is much more useful than hash chains/signatures are. We do not require sending the topmost hash away.

Forward secure sealing

Posted Aug 24, 2012 0:55 UTC (Fri) by dlang (guest, #313) [Link] (45 responses)

what is to stop someone from completely erasing everything and creating a new logfile, complete with new sealing keys from scratch?

If they did that, then the new logs that systemd tried to write to the files would look like the fake ones.

unless you are relying on systemd to know the current sealing key (and that won't work across a reboot, unless systemd stores the sealing key somewhere on the system, at which point it's vulnerable to being replaced, unless it's sent off the box, just like the hash that logtools has)

Forward secure sealing

Posted Aug 24, 2012 11:44 UTC (Fri) by DavidS (guest, #84675) [Link] (44 responses)

Each sealing key S_j is used to seal the log messages in the time period T_j and to create the sealing key S_{j+1} which in turn will be used to seal messages in T_{j+1} and create S_{j+2} and so on. As soon as S_j is securely erased -- an assumption that the article calls out as a weakness -- you cannot recreate S_j from S_{j+i} (i > 0), therefore you cannot recreate the sealed log for T_j or earlier.

For verification a off-system key is needed which is never stored on the system, but only displayed at key-generation time.

Does it keep an intruder from rm -Rf / ? No.

Does it reliably raise a red flag in a system audit? Yes.

Could an android app be written that could tell me every timerange where a downloaded FSS log is trustworthy without a third system? Yes.

Is that an improvement over having no verification (in security) and needing special logging equipment (in cost)? Yes.

Therefore I believe that FSS is a pareto optimal solution (http://en.wikipedia.org/wiki/Pareto_efficiency). There may be systems that are more secure and systems that are cheaper (intellectually, monetary and otherwise). There may be even systems that have similar security at similar costs.

Forward secure sealing

Posted Aug 24, 2012 23:20 UTC (Fri) by dlang (guest, #313) [Link] (43 responses)

so where is the latest key stored so that after a system has rebooted you can validate that the entire file hasn't been replaced by one from another system?

If it's not stored somewhere off the system, then it can be replaced along with the file and you are no better off than the simple hashing that logtools does. If you can send the key off the system, you can send the logtools hash off the system.

If it's stored on the same filesystem as the 'sealed' file, then it can be replaced, along with the file it's protecting.

The only case I am seeing where this helps you is if the system has not been restarted and so you can query systemd to find out what it thinks the current key is to validate that it matches the file.

If you don't send the key off the box, I don't see why this is any better than the initial systemd hashing. both will detect if a file has been edited after the fact, but neither will detect if a file has been forged in it's entirety.

Forward secure sealing

Posted Aug 24, 2012 23:42 UTC (Fri) by jake (editor, #205) [Link] (42 responses)

> so where is the latest key stored so that after a system has
> rebooted you can validate that the entire file hasn't been
> replaced by one from another system?

aiui, the verification key can calculate the keys at any given point in time. so the old key isn't needed, just the log and the verification key (which is kept elsewhere).

because the attacker can't calculate the keys from the past, they can't forge a validating log file that covers the past. they can delete it, or forge messages after the compromise, but can't go back in time.

jake

Forward secure sealing

Posted Aug 25, 2012 0:03 UTC (Sat) by dlang (guest, #313) [Link] (41 responses)

Since there are no pointers to how this is actually working, I'm having to ask the questions here

so you are saying that if the verification key is stored off the box, it can tell that not only is every line 'sealed' but that none of the lines are missing?

This sounds like it is relying on some signing technology that's beyond what I'm aware of as the state of the art. This is possible, but I would have expected to hear about such a new technology through the security side of things rather than as something implemented in any FOSS project as the first word.

I am skeptical about this, because very similar claims were made about the hashing that systemd implemented

The ability to generate a key for signing documents where you can use a key for signing once, use it to generate a new one and forget the old one, and people verifying the signature can not only validate it no matter which key you use, but verify the order that you signed the documents and validate that there are no gaps in the order is something that seems like it would be a revolution in digital signatures.

If it's something less than this, the limitations are likely to greatly weaken it's value for logs as well.

If, for example, you have to have every document that was ever signed by the sender, then it's going to be much less useful. You don't keep all logs that a system has ever generated, you roll them and delete the old logs

Forward secure sealing

Posted Aug 25, 2012 0:31 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (15 responses)

Simple, you just need to calculate the hash of the log messages and use the secret encryption key to seal this hash.

That's how it works, I expect.

Forward secure sealing

Posted Aug 25, 2012 0:50 UTC (Sat) by dlang (guest, #313) [Link] (14 responses)

I don't understand what you are saying.

are you saying that this uses the hash chaining (similar to what logtools does) and then 'seals' the hash, and it's the fact that the hash chaining detects gaps that makes this work, not the sealing?

Forward secure sealing

Posted Aug 25, 2012 0:53 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (13 responses)

It does not use hash _chaining_, i.e. making a hash dependent on all the previous hashes.

Each log block is hashed and sealed separately. Using hashes, of course, but each such block is independent from all the previous blocks.

Forward secure sealing

Posted Aug 25, 2012 1:00 UTC (Sat) by dlang (guest, #313) [Link] (12 responses)

> Each log block is hashed and sealed separately. Using hashes, of course, but each such block is independent from all the previous blocks.

so what stops someone from deleting an entire block?

Forward secure sealing

Posted Aug 25, 2012 1:03 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (11 responses)

You can store information about the number of previous blocks and/or date of the last sealed block in the current block (in clear text).

Forward secure sealing

Posted Aug 25, 2012 1:10 UTC (Sat) by dlang (guest, #313) [Link] (10 responses)

but you can fake that information in a replacement sealed block as well, can't you?

Forward secure sealing

Posted Aug 25, 2012 1:15 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (9 responses)

It's actually even more simpler. The sealing key itself depends on the block number.

I.e. if you delete a block then the administrator would be able to see that your current key can't be generated without skipping a block.

Forward secure sealing

Posted Aug 25, 2012 1:26 UTC (Sat) by dlang (guest, #313) [Link] (8 responses)

so you just delete the entire file and recreate the entire file, there's no prior block to compare to and notice a missing block.

Forward secure sealing

Posted Aug 25, 2012 1:30 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (7 responses)

Nope. Suppose that you hack into a system and delete block 3 (while block 4 is the current one). Admin will see the following:
<block_1> - key_1
<block_2> - key_2
<block_3> - key_4

You can't recreate key_3 from key_4 (which you know) and you can't modify the sealed block.

Forward secure sealing

Posted Aug 25, 2012 1:33 UTC (Sat) by dlang (guest, #313) [Link] (6 responses)

right, so you delete everything, not just one bock, and the admin sees

<block> key_4
<block> key_5
<block> key_6

how is the admin supposed to know that this log file was supposed to start with key_1? remember that logs rotate and so you cannot count on having logs since the beginning of time, so make the nubmers 748934 and up instead of 1 and up.

Forward secure sealing

Posted Aug 25, 2012 1:40 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (5 responses)

That's the point - you have to delete EVERYTHING. Also, keys can be made time-dependent if they are regenerated at predictable intervals. "Gaps" due to system downtime can be bridged by special log entries.

I have not yet checked how log sealing actually works, so I'm making it up as I go along. But it certainly seems doable.

Forward secure sealing

Posted Aug 25, 2012 1:47 UTC (Sat) by dlang (guest, #313) [Link] (4 responses)

I guess the thing is that deleting everything and recreating it doesn't seem like a problem to me. you can create the new logs containing everything that was in the old logs, except what you don't want to be there. you don't even have to have an algorithm to make up log entries.

I don't see how keys can be time dependent. As you note there will be downtime when keys don't get rotated, and any records of what those downtimes were are subject to being tampered with.

Forward secure sealing

Posted Aug 25, 2012 1:48 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (3 responses)

You can't recreate everything, as your key is time-dependent. It'll be obvious that timestamps inside the faked blocks and the key-derived timestamps are different.

Forward secure sealing

Posted Aug 25, 2012 2:01 UTC (Sat) by dlang (guest, #313) [Link] (2 responses)

only if you have a way of knowing

A) which of the keys was used to sign this block

and

B) which key should have been in use at that time

If such technology exists, I'm very interested in learning about it. But I would have expected that technology like this would be in use for things much more significant than just logs.

Forward secure sealing

Posted Aug 25, 2012 2:12 UTC (Sat) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

>A) which of the keys was used to sign this block
? You know this, otherwise signature can not be validated.

> B) which key should have been in use at that time
That's true because of the key's construction.

Suppose that you have the initial key (key_0) constructed on 24 Aug 2012, 00:00 UTC. You encode the key update interval (say, 10 minutes) in this key and start using it. Every 10 minutes you then generate the next key and use it for signing.

Each signed block is numbered, without gaps.

If it turns out that your current system time is ahead of the key's time (because you've resumed your computer from a long sleep) then you insert a special "skip-time" block, signed by your existing (and now obsolete) key and the time-derived key. I.e. that block in essence authenticates a legitimate gap in the log history.

Again, I'm making it up as I go along :) So I might be incorrect.

Forward secure sealing

Posted Aug 25, 2012 3:22 UTC (Sat) by dlang (guest, #313) [Link]

are you sure? it could be that you know that it's signed by A valid key, but not know which one. I really don't know how this sort of "many signing keys, one verification key" setup works. I'm interested to learn.

I am assuming that this is an asymmetric key, and so knowing the validation key does not let you know the signing key. If that's not the case, all you would need to do is to seed a PRNG and use the output as your symmetric key along with a generation number. That wouldn't be nearly as good as as if this is an asymmetric key.

your 'skip time' log entry does you no good if you don't have logs from all time (what happens when you delete the 'skip time' log entry), you would have to chrun thorugh however many key generation cycles you need to get you to the valid key (and hope that time never goes backwards on your box) as was noted by someone else on this thread.

we can speculate and design what we think is a valid algorithm here, but we don't know if that's what's being implemented in this case.

Forward secure sealing

Posted Aug 25, 2012 0:51 UTC (Sat) by nybble41 (subscriber, #55106) [Link] (24 responses)

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)
K[n] = HASH(K[n-1])
S[m] = HASH(K[n] + M[m])

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.

Forward secure sealing

Posted Aug 25, 2012 0:55 UTC (Sat) by dlang (guest, #313) [Link] (5 responses)

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] (4 responses)

> 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 (guest, #313) [Link] (3 responses)

> 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] (2 responses)

> 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 (guest, #313) [Link] (1 responses)

> 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 (guest, #313) [Link] (13 responses)

> 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] (12 responses)

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 (guest, #313) [Link] (11 responses)

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] (10 responses)

> 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 (guest, #313) [Link] (9 responses)

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 (guest, #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] (7 responses)

> 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 (guest, #313) [Link] (6 responses)

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] (4 responses)

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 (guest, #313) [Link] (3 responses)

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 (guest, #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)
F[n] = HASH(F[n-1])

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] (2 responses)

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] (1 responses)

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.

Forward secure sealing

Posted Aug 23, 2012 11:48 UTC (Thu) by richmoore (guest, #53133) [Link] (3 responses)

I wonder what the effect of the system clock going backwards (eg. because of updates from ntp, or a negative leap second) would be on the key generation. These are rare, but 'expected' events.

Forward secure sealing

Posted Aug 24, 2012 0:50 UTC (Fri) by mezcalero (subscriber, #45103) [Link] (2 responses)

This will be noticed during verification and reported. It's then up to the admin to either consider that OK, or not.

Forward secure sealing

Posted Aug 26, 2012 5:09 UTC (Sun) by ikm (subscriber, #493) [Link] (1 responses)

What about the sealing key? Wouldn't journald fast-forward it when it boots into the distant future, and then would have no way to revert it back once ntp returns the box back into the present time?

Forward secure sealing

Posted Aug 26, 2012 5:22 UTC (Sun) by Cyberax (✭ supporter ✭, #52523) [Link]

Yup. That's a problem, but that doesn't happen that often in practice (and journald would be able tolerate small jumps just fine). In case a big jump happens, journald can insert authenticated record about it.

Forward secure sealing

Posted Aug 23, 2012 14:47 UTC (Thu) by dps (guest, #5725) [Link] (2 responses)

A *long* time ago some people implemented well protected centralised log servers and drop safe logging boxes. The latter were basic non-networked boxes recording logs sent via a serial line. Even the best remote attackers can't hack a non-networked box.

An open source drop safe logging box would be really nice. Erasing your tracks by flooding the box would be impossible in these days of multiple Tb discs. Seals are great but if somebody has adjusted your logs then a copy which has not been edited might be really useful.

Of course FSS might be handy to detect that the logs are unreliable and you should check the emergency ones.

Forward secure sealing

Posted Aug 23, 2012 19:49 UTC (Thu) by dlang (guest, #313) [Link]

doing this with a serial line doesn't work nowdays because the serial line isn't fast enough.

I've created such systems, both with serial lines and with static arp entries and modified 100Mb ethernet cables that only allow traffic to go one way through the wire.

I've also created similar systems that have the logs sent out over the wire to a static arp entry and then use a Gig-E network tap to pull traffic going in one direction and send it to a machine (the tap makes the connection one-directional)

This is pretty trivial to do with opensource on commodity (or at least very readily available) hardware.

In practice, very few people want to go to this much effort, even if pretty high security situations.

it's also worth noting that if you start filtering logs, you need to hash/seal/sign each output stream separately, and such logs don't work well when you then start sending the logs to a remote system.

Forward secure sealing

Posted Aug 24, 2012 0:52 UTC (Fri) by mezcalero (subscriber, #45103) [Link]

serial lines are neither fast enough nor do they really scale that well to large numbers of hosts.

Forward secure sealing

Posted Aug 23, 2012 16:37 UTC (Thu) by cdmiller (guest, #2813) [Link] (2 responses)

How inaccessible does this system makes the logs for day to day troubleshooting?

Forward secure sealing

Posted Aug 23, 2012 16:48 UTC (Thu) by josh (subscriber, #17465) [Link] (1 responses)

This doesn't encrypt the logs; it just signs them. You can still get at the logs just as easily.

Forward secure sealing

Posted Aug 23, 2012 19:42 UTC (Thu) by dlang (guest, #313) [Link]

you just have to use the systemd tools to deal with all of your logs.

or you can have systemd forward the logs to a standard syslog server, at which point I don't see much value in having systemd process the logs in the first place (rsyslog and syslog-ng both have the ability to gather the 'trusted properties' such as pid, etc nowdays, you don't need systemd for that)

A bit concerned about relying on claims made in unpublished crypto papers

Posted Aug 25, 2012 10:10 UTC (Sat) by paulj (subscriber, #341) [Link] (3 responses)

To echo points made by dlang elsewhere in this thread...

Does anyone else find it a bit disconcerting that a security feature is being pushed based on unpublished crypto? New cryptographic protocols often will have subtle features to them, if not flaws, that have significant implications for operators/implementors, but which take time for researchers to discover.

Very strong security claims are being made for this new technology, based on a worryingly early stage of the academic peer review process (it apparently hasn't even gotten past the first stage of that yet). This is unsettling...

A bit concerned about relying on claims made in unpublished crypto papers

Posted Aug 25, 2012 13:51 UTC (Sat) by Fowl (subscriber, #65667) [Link] (2 responses)

It doesn't seem to me to be very novel, just a rearrangement of well-known, understood and time-tested primitives.

The implementation will almost certainly have bugs of course, but all software does. If your security depends on this feature you must evaluate it yourself.

A bit concerned about relying on claims made in unpublished crypto papers

Posted Sep 7, 2012 9:55 UTC (Fri) by paulj (subscriber, #341) [Link] (1 responses)

just a rearrangement of well-known, understood and time-tested primitives.

Agreed, hence why I wrote "new cryptographic protocols". I meant that this is a new protocol using cryptography, not new cryptographic protocols. Sorry. Although, exactly what the protocol is is unclear. It seems you need to read the code to figure that out (?).

A bit concerned about relying on claims made in unpublished crypto papers

Posted Sep 7, 2012 10:29 UTC (Fri) by paulj (subscriber, #341) [Link]

Gah... s/\(not new cryptographic\) protocols/\1 primitives/

Forward secure sealing

Posted Aug 27, 2012 10:33 UTC (Mon) by weinholt (subscriber, #18819) [Link]

Linux does not seem to have any filesystems that support FS_SECRM_FL. Is such support in the works?

Forward secure sealing

Posted Aug 31, 2012 20:22 UTC (Fri) by gem (guest, #86510) [Link]

Interval 15 mins? Maybe 10 sec? Whenever I have caught a hacker cleaning the logs it has taken them about 1 second after the initial root access. No point trying to outrace a hacker using a good script.

Forward secure sealing

Posted Nov 16, 2012 5:24 UTC (Fri) by zooko (guest, #2589) [Link]

I'm interested in such topics. I work on the Tahoe-LAFS secure distributed filesystem, and we have some ideas about how to implement similar-sounding semantics:

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/795

So, I'd like to read up on "forward secure sealing" or "Forward Secure Pseudo Random Generators". Maybe the way it is done would shed light on the security or efficiency properties of the way we are designing Tahoe-LAFS.

But unfortunately, I can't seem to find a peer-reviewed article, or even non-peer-reviewed documentation about how "Forward Secure Pseudo Random Generators" actually work.

I've read this article and the discussion threads, searched with Google Scholar, Google Search, and http://eprint.iacr.org. With the latter I find five publications by Bertram Poettering, but none of them seem to be about this.

Can someone hook me up with a paper or doc about it?