coercion proof timestamping services

Just some thoughts about creating more robust time-stamping services.

Current time stamping services just generate a PGP key, and sign any
messages you send them.  PGP signatures already include a time stamp.

Problem: if we find some interesting uses for time-stamps where it
becomes important that no one can coerce the timestamping service into
back-signing timestamps in the past, the current timestampers will be
able to comply, or as they are automated services, simply confiscating
the machine will likely give the attacker all information required to
back date any number of time-stamps.

One solution to this is for the time-stamper to publish all
time-stamps (they are quite small being detached signatures), and
publish a siganature on all the time-stamps stored in one file each
day.  Perhaps even publish the signature in a newspaper.  Anyone with
that newspaper, or an archive of the master signature only, will be
able to verify any claimed time-stamps -- the publically published
hash (in the signature) must match the time-stamps archived for that
day.

Another way is perhaps to have a sequence of keys for signing
time-stamps on each day, and to discard the private key after that
day.  Authenticate the use-for-one-day-only keys by signing with a
long term key.  If people archive daily keys, the coercion of
timestamping service will be detected if it attempts to publish a
daily key for some date in the past, and the timestamping service
can't sign with old keys as it has purposely discarded the private
halves.

Adam
-- 
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

-----BEGIN PGP SIGNED MESSAGE-----

In <199708202137.WAA00738@server.test.net>, on 08/20/97 
   at 10:37 PM, Adam Back <aba@dcs.ex.ac.uk> said:

>One solution to this is for the time-stamper to publish all
>time-stamps (they are quite small being detached signatures), and publish
>a siganature on all the time-stamps stored in one file each day.  Perhaps
>even publish the signature in a newspaper.  Anyone with that newspaper,
>or an archive of the master signature only, will be able to verify any
>claimed time-stamps -- the publically published hash (in the signature)
>must match the time-stamps archived for that day.

This is how Stamper works. The time stampes are published to various NG's
& mailling lists once a week.

- -- 
- ---------------------------------------------------------------
William H. Geiger III  http://www.amaranth.com/~whgiii
Geiger Consulting    Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 2.6.3a at: http://www.amaranth.com/~whgiii/pgpmr2.html                        
- ---------------------------------------------------------------

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3a
Charset: cp850
Comment: Registered_User_E-Secure_v1.1b1_ES000000

iQCVAwUBM/t2jY9Co1n+aLhhAQHUgwQAnTprQx1BDbWaj5gDeOn+6MMNQE9AW/N6
3CDvw+iYokUBxYkdqpR+K2b9xCCO2Lu/L9xcnIEb0Wehe5YG8usm6tmwaVVd9G7c
pnI4XlYxrNjaZROAWiAYPdBq+hE/HMNUo9B3mmeAeXftoIj3VJ5JvBkzWNdUB/Lj
qrc5dslsXTw=
=Q2QL
-----END PGP SIGNATURE-----

On Wed, 20 Aug 1997, Adam Back wrote:

> Just some thoughts about creating more robust time-stamping services.
> 
> Current time stamping services just generate a PGP key, and sign any
> messages you send them.  PGP signatures already include a time stamp.
> 
> Problem: if we find some interesting uses for time-stamps where it
> becomes important that no one can coerce the timestamping service into
> back-signing timestamps in the past, the current timestampers will be
> able to comply, or as they are automated services, simply confiscating
> the machine will likely give the attacker all information required to
> back date any number of time-stamps.
> 
> One solution to this is for the time-stamper to publish all
> time-stamps (they are quite small being detached signatures), and
> publish a siganature on all the time-stamps stored in one file each
> day.  Perhaps even publish the signature in a newspaper.  Anyone with
> that newspaper, or an archive of the master signature only, will be
> able to verify any claimed time-stamps -- the publically published
> hash (in the signature) must match the time-stamps archived for that
> day.

Or post to a news group.  (Some form of transport that can be automated
and widely distributed without having to create new protocols.)

> Another way is perhaps to have a sequence of keys for signing
> time-stamps on each day, and to discard the private key after that
> day.  Authenticate the use-for-one-day-only keys by signing with a
> long term key.  If people archive daily keys, the coercion of
> timestamping service will be detected if it attempts to publish a
> daily key for some date in the past, and the timestamping service
> can't sign with old keys as it has purposely discarded the private
> halves.

Also maintaining the temporary keys on some sort of volitile storage media
that does not leave traces for later when erased.  (RAM disk or the like.)
Keep the private key on the card and erase the old key as part of the
private key generation process.

The only weakness I see here (there may be others) is keeping the long
term key secure.  (Keeping the bad guys from generating their own bogus
keys for later timestamps and the like.)

alan@ctrl-alt-del.com | Note to AOL users: for a quick shortcut to reply
Alan Olsen            | to my mail, just hit the ctrl, alt and del keys.

At 2:37 PM -0700 8/20/97, Adam Back wrote:
>Just some thoughts about creating more robust time-stamping services.
>
>Current time stamping services just generate a PGP key, and sign any
>messages you send them.  PGP signatures already include a time stamp.
>
>Problem: if we find some interesting uses for time-stamps where it
>becomes important that no one can coerce the timestamping service into
>back-signing timestamps in the past, the current timestampers will be
>able to comply, or as they are automated services, simply confiscating
>the machine will likely give the attacker all information required to
>back date any number of time-stamps.

The Surety folks do (or did, as I don't know their current market status) a
lot more than this, and the published hash makes "back-signing"
problematic! Their URL is www.surety.com, and my own Cyphernomicon has a
description.

--Tim May


There's something wrong when I'm a felon under an increasing number of laws.
Only one response to the key grabbers is warranted: "Death to Tyrants!"
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^1398269     | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."