Skip to content

Instantly share code, notes, and snippets.

@markblundeberg

markblundeberg/pgp-checkdatasig.md

Created August 31, 2018 01:23
Show Gist options
  • Save markblundeberg/af59d7cd234cbdb14dcf9e00f0ea2c17 to your computer and use it in GitHub Desktop.
Save markblundeberg/af59d7cd234cbdb14dcf9e00f0ea2c17 to your computer and use it in GitHub Desktop.
Download ZIP
Using PGP signatures with bitcoin script OP_CHECKDATASIG
Raw
pgp-checkdatasig.md

Using PGP signatures with bitcoin script OP_CHECKDATASIG

Dr. Mark B. Lundeberg, 2018 August 30 bitcoincash:qqy9myvyt7qffgye5a2mn2vn8ry95qm6asy40ptgx2

Since version 2.1, GnuPG is able to use the very same secp256k1 elliptic curve signature algorithm (ECDSA) as used in bitcoin. Quite soon Bitcoin Cash will add a new script opcode OP_CHECKDATASIG that is able to check signatures not just on the containing transaction, but also on arbitrary data. For fun, let's try to intersect the two signature systems and see what can be done!

Background

OP_CHECKDATASIG signatures

This new opcode will allow scripts to fail/succeed on the basis of whether a given message is signed with a given key. When a script invokes this opcode, it pops three items (byte arrays) off the stack: sig, msg, pubkey. It checks the result of Verify_ECDSA_secp256k1(pubkey, digest, sig), where digest=SHA256(msg). This is similar to the transaction signature system, except note that:

  • sig stores the signature (r,s) values in the regular ~70 byte DER format used for the OP_CHECKSIG signatures. A hashtype byte suffix is however not added.
  • Unlike with transaction signing, msg is not altered in any way before inputting into the hash, and msg is hashed once with SHA256, not twice.
  • pubkey is a standard bitcoin public key, uncompressed or compressed.

PGP elliptic curve signatures

This document only focusses on the "version 4" PGP signature system. See the RFC4880 section on computing signatures. The specification for ECDSA encoding in PGP is RFC6637.

When you run a command like gpg --detached-sign stuff.dat, a number of things happen behind the scenes in accordance with the OpenPGP standard. Focussing on the case of an ECDSA key,

  1. Construct a partial 'signature packet' that includes: a version number (0x04 currently), the type of signed data (0x00 for binary document), the public key algorithm type (0x13 for ECDSA), the hash type (0x08 for SHA256), and various subpackets of metadata including the signature creation time.
  2. Read in the file "stuff.dat", for example this byte string of ASCII characters: data = b'Hello world!\n'.
  3. Appends the partial signature packet to the message data, plus an extra 6 bytes encoding the length of the partial signature packet. In hex: msg = 48656c6c6f20776f726c64210a04001308000605025e0c518004ff0000000c where the bolded part is the original data.
  4. Compute the digest according to the selected hash type, e.g.: digest = SHA256(msg)
  5. Run r, s = Sign_ECDSA(secret_key, digest).
  6. Take the partial signature packet from step 1, and complete it by appending: various other subpackets of metadata (like the key ID used for the signature), the leftmost 2 bytes of digest, and finally the integers (r,s) stored in PGP's multiprecision integer format.
  7. This yields the completed signature data, which for ECDSA is typically 96 bytes. It may at this point be converted to ascii armor "-----BEGIN PGP SIGNATURE----- ...".

To verify, GnuPG extracts out the partial signature packet, appends it to the data as above to get msg, then computes digest. It checks that it matches the 2 bytes and tries to find the public key matching this key ID. Finally it checks Verify_ECDSA(pubkey, digest, sig).

Key-signing signatures

For key certifications / self-signatures, the msg passed into the hash is a bit more complicated. It is a concatenation of the following byte strings:

  • A 3-byte key header.
  • The key packet being signed (using 'old style' header).
  • A 5-byte user ID header.
  • The user ID packet being signed.
  • The partial signature packet plus extra 6 bytes, as above.

Compatibility? Interconversion?

Although OP_CHECKDATASIG and PGP store the signatures in different format, and appear to compute the digest differently, they are not entirely incompatible. We must create secp256k1 keys (currently requires gpg --full-gen-key --expert) and when we sign documents we should make sure we use SHA256 (gpg --digest-algo SHA256 -b stuff.dat).

Let's say we have such a PGP signature and want to convert it to be verifiable by OP_CHECKDATASIG. We can do the following:

  1. Extract the partial signature packet and append it to our data, to obtain msg.
  2. Extract the signature data -- the (r,s) multiprecision integers -- and convert it to the bitcoin DER representation. Ensure that s is 'low S' by possibly subtracting it from the group order.
  3. Get the public key file and extract they key data (PGP stores this in uncompressed 04... format), in order to get pubkey.

One major limitation is the following point: In the bitcoin script interpreter, a single stack element cannot in any circumstances exceed 520 bytes in size. This means that the entirety of msg must fit within 520 bytes. Practically, this means:

  • Signed documents need to be limited to <~ 500 bytes, to leave enough room for the appended metadata. If you need a signature on a large file, you will need to instead create a small document including the hash of the large file. This is perhaps not so inconvenient -- it is quite common in software distributions to sign a 'SHA256SUMS' file, for which ~4 to 6 files can be included within 500 bytes.
  • Key certifications on large keys can easily exceed 500 bytes. The following keys are small enough to sign while keeping msg under 520 bytes:
    • All ECDSA/Ed25519 keys.
    • DSA up to 1024 bits.
    • RSA up to ~3500 bits.

Use cases

Oracle wants to use PGP

The classic use envisioned for OP_CHECKDATASIG is that a trusted Oracle would sign some message using bitcoin's signmessage or some variant, and this information could be more-or-less directly included and processed in script. It is now clear that Oracles also have the option to use PGP.

The fact that msg includes a mandatory appendix (partial signature packet) does add a wrinkle. In particular the appendix includes a creation time (unix seconds since epoch) and may or may not include other metadata subpackets.

The redeem script can be constructed so that the appendix is omitted. For example msg = (data + appendix) may be split into: data = b'Broncos win!\n' and appendix = 04001308000605025e0c518004ff0000000c. Then the following redeem script would reconstruct them, given the signature and appendix as an input:

[sig and appendix get pushed from scriptSig]
...            (..., sig, appendix)
<data>         (..., sig, appendix, data)
SWAP           (..., sig, data, appendix)
CAT            (..., sig, msg)
<pubkey>       (..., sig, msg, pubkey)
CHECKDATASIG   (..., 0 / 1)
...
[do stuff based on CHECKDATASIG result]

(items in parentheses show the stack state after performing the operation)

Note however this means a PGP signature from the oracle on any message starting with "Broncos win!\n" would work, even if this message came from a previous year or if the signed message was "Broncos win!\nJust kidding!".

If the appendix is not truncated, then a timestamp is automatically included. However, the exact appendix contents (including timestamp set with 1-ssecond accuracy) must be known ahead of time. If this is done, the Oracle should use the gpg --faked-system-time flag and other options to make sure that the appendix has precisely the pre-announced binary form.

Atomic swap of BCH for a PGP key certification

Alice wants to pay Bob some bitcoin in exchange for a PGP certification but doesn't quite trust that he won't run off with her money. What a bizarre situation. But don't fret, now there is a way for them to do a trustless swap!

Bob performs the certification but keeps it secret, only sharing msg. Alice parses the msg to make sure it would be satisfactory and computes digest=SHA256(msg). She then funds a P2SH address with the following 151-byte redeem script:

IF
  <alice_bitcoin_pubkey>
  CHECKSIGVERIFY
  <alice_recovery_time>
  CHECKLOCKTIMEVERIFY
ELSE
  <bob_bitcoin_pubkey>
  CHECKSIGVERIFY
  DUP
  HASH256
  <digest>
  EQUALVERIFY
  <bob_pgp_pubkey>
  CHECKDATASIG
ENDIF

Bob can spend from this address using the following scriptSig stack: (sig, msg, tx_sig, 0), where he constructed sig from the PGP signature's (r, s) parameters. He must also sign the transaction with his bitcoin key bob_bitcoin_pubkey, as this ensures that he is in control of where the funds go.

Once Bob has spent from this address, which requires him to reveal r, s, Alice now can take this signature together with msg, to reconstruct the valid key certification.

If Bob stops responding then Alice can recover her funds with just the stack (tx_sig, 1) -- i.e., the transaction is just signed by her key alice_bitcoin_pubkey. She must however wait until alice_recovery_time to do so.

Note 1: I used digest here in the redeemscript instead of including msg, since the entire redeem script must fit into 520 bytes. This lets us use a full 520 byte msg by having it pushed from the scriptsig.

Note 2: In practice, Alice might demand that Bob sign with a 'non-revocable' signature, which she can confirm by checking the metadata packets in msg. Quite a variety of customizations can be done with PGP signatures/certifications, and Alice must make sure to be aware of them.

Note 3: What if the participants don't want to publish this obvious exchange of a PGP certification on the blockchain? No problem -- like many other contracts, this one can be hidden inside of a regular payment channel.

Examples

Files available at github. Includes a python script that extracts PGP data and creates a bitcoin transaction.

Worked example of basic signature

A secp256k1 ECDSA PGP key was created using gpg --full-gen-key --expert:

984f045b745e9813052b8104000a020304a788d320086c086c71e15d34e6
2a2308240afccc2325bb34f07edf56706f62a60330ea3e1df9ee826afa2e
b4f382d681c99f27bccc486a9390d65b305215f978b40b4d792054657374
204b6579887904131308002105025b745e98021b03050b09080702061508
090a0b020416020301021e01021780000a09102d91cad9873ecc6a5e8c01
00c1c98722bb5ff8ecd80219b04e72134a604a4395f0eb387cfa86a2b909
4e73bd0100bf29cdacee283c3faaba9a480b0f0761a1d3377d8e0056a6e3
72977f1f068ba0

Three pieces of information are bolded above:

  • 0x13 indicates the public key is ECDSA.
  • 2b8104000a is an OID indicating the curve is secp256k1.
  • 04a78...978 is the public key in uncompressed format.

The rest of the info is the PGP key's user ID and self-signature (including various algorithm preference fields), which can be seen by pasting the above hex into cat | xxd -r -p | gpg --list-packets.

PGP's ECDSA doesn't use compressed keys, however it is easy to convert to compressed form: 02a788d320086c086c71e15d34e62a2308240afccc2325bb34f07edf56706f62a6. This compressed form will be used in the bitcoin script, for space savings.

A file containing binary hex 48656c6c6f20776f726c64210a, or, b"Hello world!\n", was then signed using gpg -b file.dat, yielding the following detached signature file:

885e04001308000605025e0c5180000a09102d91cad9873ecc6a4f3c00fe
2caa3f50ec00dcf2eff56bb9e14d4af2b54f0f7ecbdee576c8e5f128a503
82b400ff6eaa0117977269a2ba9eb5698861141681a81479e5f32e8f9bce
bacc07062616

Here I have highlighted four important parts:

  • The signature 'hashed part' which includes pubkey algorithm-id 0x13 (ECDSA), hash algorithm-id 0x08 (SHA256) and the signature creation time 0x5e0c5180,
  • the key ID 2D91CAD9873ECC6A (orange),
  • signature integer r = 0x2ca...2b4,
  • signature integer s = 0x6ea...616.

The 'hashed part' and then six more bytes get appended to the signed data: msg = 48656c6c6f20776f726c64210a04001308000605025e0c518004ff0000000c. The SHA256 digest of this msg is 4f3c2588e3a7c508fc16e71b418c20625fff5de633f61be116d94e1b86a5c449, and is used in signing but will not appear explicitly anywhere else. Note however that for pre-checking, PGP included the leftmost 16 bits 4f3c in the signature packet, just after the key ID.

Using the msg and pubkey from above, I created a custom redeem script PUSH<msg> PUSH<pubkey> OP_CHECKDATASIG. Note that it ends with opcode 0xba (OP_CHECKDATASIG):

1f48656c6c6f20776f726c64210a04001308000605025e0c518004ff0000
000c2102a788d320086c086c71e15d34e62a2308240afccc2325bb34f07e
df56706f62a6ba

I used Electron Cash in testnet mode to fund the P2SH address bchtest:pqgsc6ej2yqsrdlrlaqf3lphyznps50zgvwdaxc3e4 (corresponding to the redeem script hash) with 0.3 BCH. I set up a bitcoin-ABC with early activation for OP_CHECKDATASIG and an ElectrumX server. I then successfully spent the utxo using the following scriptSig that pushes the (r, s) signature and redeem script:

46304402202caa3f50ec00dcf2eff56bb9e14d4af2b54f0f7ecbdee576c8
e5f128a50382b402206eaa0117977269a2ba9eb5698861141681a81479e5
f32e8f9bcebacc07062616431f48656c6c6f20776f726c64210a04001308
000605025e0c518004ff0000000c2102a788d320086c086c71e15d34e62a
2308240afccc2325bb34f07edf56706f62a6ba

As can be seen, the bolded parts are directly the integers r, s that appeared in the PGP signature above.

Notes:

  • In general, it may be necessary to convert s to 'Low S' form but in this case PGP made it that way already.
  • This is a poor example of redeem script, since it requires no transaction signature and hence has no replay protection. Once the scriptsig is known, anyone can construct a new transaction that spends from this address, and send the funds to themselves. In fact, there is at least one bot on the bitcoin network that is designed to automatically respond in this way!

Mystery example

This hefty 679 byte single-P2SH-input transaction successfully confirmed on the testnet with OP_CHECKDATASIG enabled. It is left as an exercise to the reader to figure out what it is.

0100000001aec61bd1c2a6da1e61d957e4a36526f7652128c39c5337fef7
0cc85ae7b546a500000000fd5002473045022100f98cb8534576e1ce59f9
6257c4d8cb720efd3e1914ed9f4c9bc84fa1aa65de5802203fc114cd42da
1428070c9c3123bc3b4c8e7c589a01f2d265cadf934a014a78bc4d05024d
df019901a2044909faa7110400ca0d37199580d1b4fd50eff4a1bb3049cd
487d868555a30a207f65b4ed4e86f41a8a5b6e2ba623b162612b8cc15fbc
db68ccd93edf771dfecab7822d393b520c999ce0dab6c5e277b9b778a995
79cdbb3361fa3fba571c40d7a18f841469aef9e783cafd19800b2d4a68f5
7935eca138dbd618285815bed4cfb441949693b51300a0ec59967416d1a7
89a7e467f140d4f5873a7d5a0903ff7a59d1c0799b87a7cdfca53875e645
f24a04c174d990e7b18d46a9e1effcb8e4842bac4e9daacf8b612f271838
528698075da559ccb04fd36192e0a6cc63ac9b2b10f3527685e4dc88044a
da309978d37ebf7134eac1db4424d1938ed668a9396320b1ee0f988bb4d9
7db839aa56b7285d1ec5f7a012dcc037647bc68480087c03fb0794aedf2f
5062f2b173c7a85bfb6c88943fdf6b330155951ed2bdaea3b95da84cf9f8
67848811628277791c786a8c9c3cad42647de641a132989432a8ed70eb4d
1c5fcb336e6593f104b4e3fa4798f16818850e4c5ac482d8c5fb1591da25
d7586b4a73526159990874c9dba55544272cacd14ae9ec8c63a79b189605
9c1be9b4000000235361746f736869204e616b616d6f746f203c7361746f
7368696e40676d782e636f6d3e04101308000605025b83907404ff000000
0c2102a788d320086c086c71e15d34e62a2308240afccc2325bb34f07edf
56706f62a6baffffffff0198bfc901000000001976a9142b23deef077156
90e9c94c4bed6ce1601e15d43f88ac00000000
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment