Not logged in
Log in now
Create an account
Subscribe to LWN
LWN.net Weekly Edition for May 23, 2013
An "enum" for Python 3
An unexpected perf feature
LWN.net Weekly Edition for May 16, 2013
A look at the PyPy 2.0 release
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)
Posted Aug 25, 2012 1:16 UTC (Sat) by dlang (✭ supporter ✭, #313)
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.
Posted Aug 25, 2012 1:33 UTC (Sat) by nybble41 (subscriber, #55106)
The keys follow a very specific pseudo-random sequence. K = HASH^2000(K) is an entirely different value from K = HASH^20(K). 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]).
Posted Aug 25, 2012 1:37 UTC (Sat) by dlang (✭ supporter ✭, #313)
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.
Posted Aug 25, 2012 1:43 UTC (Sat) by dlang (✭ supporter ✭, #313)
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.
Posted Aug 25, 2012 2:05 UTC (Sat) by nybble41 (subscriber, #55106)
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.
Posted Aug 25, 2012 2:11 UTC (Sat) by dlang (✭ supporter ✭, #313)
You seem to know about this technology, can you point me at a paper on it?
Posted Aug 25, 2012 2:14 UTC (Sat) by Cyberax (✭ supporter ✭, #52523)
Posted Aug 25, 2012 2:19 UTC (Sat) by nybble41 (subscriber, #55106)
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.
Posted Aug 25, 2012 3:27 UTC (Sat) by dlang (✭ supporter ✭, #313)
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.
Posted Aug 25, 2012 3:41 UTC (Sat) by dlang (✭ supporter ✭, #313)
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.
Posted Aug 25, 2012 4:54 UTC (Sat) by Cyberax (✭ supporter ✭, #52523)
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.
Posted Aug 25, 2012 19:00 UTC (Sat) by nybble41 (subscriber, #55106)
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 = 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.
Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds