How do RFC3161 timestamps work?

RFC3161 exists to demonstrate that a particular piece of information existed at a certain time, by relying on a timestamp attestation from a trusted 3rd party. It's the cryptographic analog of relying on the date found on a postmark or a notary public's stamp.

How does it work? Let's timestamp some data and rip things apart as we go.

First, we'll create a document and have a brief look at it. The document will be one million bytes of random data:

 $ dd if=/dev/urandom of=data bs=1000000 count=1  
 1+0 records in  
 1+0 records out  
 1000000 bytes transferred in 0.039391 secs (25386637 bytes/sec)  
 $ ls -l data  
 -rw-r--r-- 1 chris staff 1000000 Dec 21 14:10 data  
 $ shasum data  
 3de9de784b327c5ecec656bfbdcfc726d0f62137 data  
 $   

Next, we'll create a timestamp request based on that data. The -cert option asks the timestamp authority (TSA) to include their identity (certificate chain) in their reply and -no_nonce omits anti-replay protection from the request. Without specifying that option we'd include a large random number in the request.

 $ openssl ts -query -cert -no_nonce < data | hexdump -C  
 Using configuration from /opt/local/etc/openssl/openssl.cnf  
 00000000 30 29 02 01 01 30 21 30 09 06 05 2b 0e 03 02 1a |0)...0!0...+....|  
 00000010 05 00 04 14 3d e9 de 78 4b 32 7c 5e ce c6 56 bf |....=..xK2|^..V.|  
 00000020 bd cf c7 26 d0 f6 21 37 01 01 ff                |...&..!7...|  
 0000002b  
 $   

The timestamp request is only 43 bytes, so we're definitely not sending the actual document (one million bytes) to the TSA. So what's in the request?

Perusing the data, a couple of things (the two mandatory items, in fact) stand out. First, the SHA1 hash of the data that we captured earlier appears here in the timestamp request. Second the OID specifying SHA1 is included here. The OID (1.3.14.3.2.26) is a little less recognizable because of the insane way OIDs are encoded in ASN.1 (section 8.19), but there it is. The only other information included in the request is result of the -cert flag, which is a boolean (true) in the last 3 bytes. I found that the TSA refused to respond if I failed to request the signer include its certificate chain.

Okay, lets re-generate that request and send it to a real TSA:

 $ openssl ts -query -cert -no_nonce < data | curl --data-binary @- http://timestamp.entrust.net/TSS/RFC3161sha2TS | hexdump -C  
 Using configuration from /opt/local/etc/openssl/openssl.cnf  
  % Total  % Received % Xferd Average Speed  Time  Time   Time Current  
                  Dload Upload  Total  Spent  Left Speed  
 100 3773 100 3730 100  43 24064  277 --:--:-- --:--:-- --:--:-- 24500  
 00000000 30 82 0e 8e 30 03 02 01 00 30 82 0e 85 06 09 2a |0...0....0.....*|  
 00000010 86 48 86 f7 0d 01 07 02 a0 82 0e 76 30 82 0e 72 |.H.........v0..r|  
 00000020 02 01 03 31 0b 30 09 06 05 2b 0e 03 02 1a 05 00 |...1.0...+......|  
 00000030 30 81 e2 06 0b 2a 86 48 86 f7 0d 01 09 10 01 04 |0....*.H........|  
 00000040 a0 81 d2 04 81 cf 30 81 cc 02 01 01 06 09 60 86 |......0.......`.|  
 00000050 48 86 fa 6c 0a 03 05 30 21 30 09 06 05 2b 0e 03 |H..l...0!0...+..|  
 00000060 02 1a 05 00 04 14 3d e9 de 78 4b 32 7c 5e ce c6 |......=..xK2|^..|  
 00000070 56 bf bd cf c7 26 d0 f6 21 37 02 06 5d eb 11 2b |V....&..!7..]..+|  
 00000080 86 c9 18 13 32 30 31 39 31 32 32 31 32 30 30 38 |....201912212008|  
 00000090 30 36 2e 30 30 34 5a 30 04 80 02 01 f4 a0 76 a4 |06.004Z0......v.|  
 000000a0 74 30 72 31 0b 30 09 06 03 55 04 06 13 02 43 41 |t0r1.0...U....CA|  
 000000b0 31 10 30 0e 06 03 55 04 08 13 07 4f 6e 74 61 72 |1.0...U....Ontar|  
 000000c0 69 6f 31 0f 30 0d 06 03 55 04 07 13 06 4f 74 74 |io1.0...U....Ott|  
 000000d0 61 77 61 31 16 30 14 06 03 55 04 0a 13 0d 45 6e |awa1.0...U....En|  
 000000e0 74 72 75 73 74 2c 20 49 6e 63 2e 31 28 30 26 06 |trust, Inc.1(0&.|  
 000000f0 03 55 04 03 13 1f 45 6e 74 72 75 73 74 20 54 69 |.U....Entrust Ti|  
 00000100 6d 65 20 53 74 61 6d 70 69 6e 67 20 41 75 74 68 |me Stamping Auth|  
 00000110 6f 72 69 74 79 a0 82 0a 23 30 82 05 08 30 82 03 |ority...#0...0..|  
 <...4KB Later...>
 00000e80 7a 1b a2 95 ec cc 1e d5 33 06 c3 69 61 6a a5 15 |z.......3..iaj..|  
 00000e90 53 0a                                           |S.|  
 00000e92  
 $   

Holy cow! Our 43 byte request provoked a ~4KB response! What is this thing?

Naturally, it's an ASN.1 document, just like everything else involving cryptography. OID 1.2.840.113549.1.7.2 indicates that it is PKCS#7 signed data (that crazy OID formatting again). The signed data includes:

• The OID indicating a SHA1 hash and the hash result from our request both appear.
• OID 2.16.840.114028.10.3.5 indicates the Entrust (their ORG ID is 114028) timestamp policy under which this result was issued. See RFC3161(2.1.5). It seems like there should be a document describing their practices somewhere, but I can't find it.
• Next, we find that the signed document indicates that it was created at 2019-12-21 20:08:06.004 UTC (this is the whole point)
• The value 01F4 indicates timestamp accuracy of 500ms. This optional field has the ability to represent seconds, milliseconds and microseconds, but this response only includes milliseconds.
• The readable strings following the accuracy field are optional timestamp GeneralName data identifying the TSA.
• The rest of the response (most of it, really) is PKCS#7 (signed data) overhead including the signer's signature and certificate chain.

So... Neat! We submitted a hash of some data to the TSA, and it replied with our hash, the time it saw it, and a verifiable signature. This definitely beats dropping hashes on twitter to prove you had some data at a particular time.

One of the places that timestamps of this sort come up is with code signing: Unlike a live transaction (say, TLS handshake), it is possible for a code signing entity to back-date a software release. Because we generally want software builds to work forever once they're created/signed, how do you stop a signer from creating a back-dated, but apparently valid release after their signing certificate has expired or been compromised? The best answer we've got is to include a 3rd party who can be trusted to not fake the date, so software signatures might include one of these timestamps.