Format for full file signatures

[bit22gen]

There does not seem to exist a format for full file bitcoin signatures, at least have I not found any.

It is a bit surprising that bitcoin uses signatures at the core of its functionality,
but bitcoin developers seem to use PGP signatures for distributed software instead of bitcoin signatures.

There are a couple of message formats for bitcoin signatures, but they seem to be mostly used for
signatures of short messages where the result of the signature operation is a new file where the message is included.

However, it would be very useful to be able to sign an existing file which might be very large,
for example en exe-file or a source code archive.
This would provide PGP-like signature functionality using the bitcoin elliptic curve.

I have therefore created and implemented such a signature format which is included in the bitgen software package:

http://bitcoin-gen.org/

A signature might look like this:
------ BEGIN BITCOIN SEPC256K1 SIGNATURE ------
feu
14F0668D7FE8938F6A23F8FE1A4FB906C558A3FBDB967222B929158487F34183
6C50D34A304A3227035CEE1ADE006B5502CC41BF639609201F75919F1B3F560E
------ END BITCOIN SEPC256K1 SIGNATURE ------


The signature includes the r and s values of the signature as well as three boolean values.

The public key x and y values are not included since the sepc256k1 curve allows public key recovery
from the r and s values and the hash sum.

The three letters in the first line give information about which public address should be choosen since there are
eight possible public addresses when (r, s, hash) are given.

The first letter can be "f" or "s", which stands for "first" and "second".
With "f", the first value should be choosen, with "s" the second value is the correct one.

The second letter is "e" or "o" for "odd" or "even", and will together with the first boolean value give the correct public key.

The public address can be derived from a compressed or uncompressed public key.
The third character specifies "u" for uncompressed or "c" for compressed.

The second and third lines are the r and s values as hex encoded values.

The double sha256 hash of the file is performed using the string "Bitcoin Signed File " followed by the
byte length of the file contents in decimal ascii, followed by " bytes:" and finally the file contents:

"Bitcoin Signed File " + ascii(length) + " bytes:" + file_content

The file format uses unix style newline with a single linefeed character.


Building the project will give two executable files, one which is bitsig

In order to create and store a new private key, use for example:
$ bitsig random

When this is done, the signature of any file can be created:
$ echo "bitgen test" > btest.txt
$ bitsig sign btest.txt

This will give output similar to the following:
========================
Signing message file: btest.txt
No key specified, using default key: 17RjaCGZQbe2Cw984YdWcMcWDgM86kM7EN
Generating 32 random bytes.
Press random keys or move the mouse if needed
32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Signing in progress...
Trying even...
Parity is even

Result written to: btest.txt.bitsig
========================

In order to verify the signature of the file, give the following command:

$ bitsig verify btest.txt btest.txt.bitsig

This will give:
========================
The signed file      : btest.txt
The signature file   : btest.txt.bitsig
Calculated address   : 17RjaCGZQbe2Cw984YdWcMcWDgM86kM7EN
No public address given, looking in keychain
This is our own address
Found the address in the keychain
Verifying signature....
Verify OK for address: 17RjaCGZQbe2Cw984YdWcMcWDgM86kM7EN
Address alias: MY KEY
========================

[gmaxwell]

Yes. Bitcoin uses digital signatures. It also uses addition. And linked lists.  Yet you don't see people going around replacing other things that use addition or linked lists with parts of bitcoin.

Providing a useful, secure, and usable system for authenticating files is vastly more than just having a digital signature, in the same way that creating a cryptocurrency is vastly more than just having software that can perform addition.

Getting it right involves satisfying numerous cryptographic, procedural, and user interface goals which are completely unrelated to Bitcoin.

A digital signature by itself is meaningless. Anyone can create one. Look at the signatures on your site... it's served over HTTP and you have these .bitsig files. Anyone who could tamper with the download in the first place could simply replace the signatures: so at least as it's being used there the signatures provide virtually no security.

Having evidence that the pubkey key being used is an authentic one is the hard part-- but this system seems to do nothing for that; and Bitcoin provides no answers for that--  in the design of Bitcoin keys are the exact opposite of persistent identity-- anonymous, ephemeral, and hopefully single use.

PGP, on the other hand, has extensive infrastructure for the verification of keys.

So that is the primary reason we use it rather than something homebrew.

Some other things to think about for anyone working on this...

Bitcoin works with transactions, which are necessarily small... but a good file signature system should have a structure that makes it possible to work with files much larger than memory.

As an aside-- looking at your codebase, I see that it contains a completely naive and quite slow implementation of ECC. This approach will bleed out information about the users' private key via timing, cache, and electro-magnetic sidechannels.  Mature cryptographic software (like GPG) avoids these sorts of vulnerabilities. I also see that it doesn't use derandomized signing. I'm glad to see there are some tests, but you should be careful-- a number of people have suffered serious losses of funds due to incorrect pubkey/address generation in rare cases that a few fixed tests vectors are unlikely to catch (e.g. rare corner case bugs in bignum libraries). Doing a real review of the cryptography in the project would be a ton of work... and I think it's unlikely anyone will do so, because there doesn't appear to have been a reason to reinvent the wheel in the first place (beyond your own education, which is super valuable, but not a great reason to create software for other people to use).

Separately, looking at the instructions tools seem to frequently expect users to provide secret data on the command-line. This will result in it ending up in the shell history on many hosts, as well as being easily visible to other processes. It's usually better to avoid that.  Brainwallets are generally really inadvisable and we've seen over and over that most users are unable to use them safely and as a result there has been a lot of loss, but especially the kind of non-hardened (no KDF) brainwallets that this software implements is especially irresponsible.

[bit22gen]

Bitcoin signatures instead of PGP are not simply a replacement from one implementation to another
with the same use cases and characteristics.

The methods differ, and are therefore best used in different situations.

Bitsig does not (yet!) include any PKI infrastructure possibilities, and is therefore not the first option
for large corporations that would create a trusted root certificate that is used to sign other certificates.

However, for decentralized users such a trusted root might not be very useful anyway.
Open source software is one such area.

Signing a software package is very useful, and when a new version is released you want to
be sure that it is released by the same developer team as the previous one, which means that it is signed with the same key.

When you have used one version of an application and perhaps also studied the source code
you will  have some confidence in that software, and you will possess the public key even though
you may not know very much about the developers. A trusted root would not add much in that case.

When a new version is released and signed with the same key you will at least know that no one else
is trying to make you run their potentially malicious software.

Bitcoin uses shorter keys than PGP, which is an advantage over PGP.
RSA require longer keys than elliptic curves. RSA does the job,
but elliptic curves is a better algorithm when it comes to the key length.

Key distribution is hard. Downloading the public key is subject to the man-in-the-middle attack.
However, downloading from different sources over different channels will increase your trust in the public key.

Also, since a bitcoin address is short, it is easier to send with for example SMS.

If you will receive a file from someone you know it is possible to receive the public address
in a telephone call. A man-in-the-middle attack would be very hard if you know the person you are talking to.

The bitgen software is work in progress, there is plenty to improve including the test cases.

Bitgen is currently best used on a completely standalone machine with no internet connection,
and used for nothing else than key generation and signing. In that case the command line history will not matter so much.
But eliminating also that side channel is something to improve in future versions.

I fully agree regarding the brainwallet option, I consider removing that feature until salt and KDF has been implemented.

If anyone else finds bitcoin full file signatures useful my hope is that the specified file format will be used
when new bitsig-aware software is crated, possibly with another ECC implementation.

[gmaxwell]

Bitsig does not (yet!) include any PKI infrastructure possibilities, and is therefore not the first option
for large corporations that would create a trusted root certificate that is used to sign other certificates.

However, for decentralized users such a trusted root might not be very useful anyway.
Open source software is one such area.

PGP does not use a trusted root.

1Bitcoin uses shorter keys than PGP, which is an advantage over PGP.
RSA require longer keys than elliptic curves. RSA does the job,
but elliptic curves is a better algorithm when it comes to the key length.

PGP can use ECC too, for some time now.

Though for files the size of the pubkey keys and signatures is usually not very interesting.

However, downloading from different sources over different channels will increase your trust in the public key.

A cryptographic hash of the file works just as well for that purpose.  Though a network attacker near you can thwart any other unauthencated source you see.

Also, since a bitcoin address is short, it is easier to send with for example SMS.

A pgp fingerprint is short. Bitcoin addresses are very unfriendly to read over the phone due to mixed case.

If anyone else finds bitcoin full file signatures useful my hope is that the specified file format will be used
when new bitsig-aware software is crated, possibly with another ECC implementation.

Perhaps... but even ignoring the lack of PKI this design isn't good fit for files too big to fit in memory. Ideally you want a tree structured hashing scheme for that.

[fbueller]

I want to point out that openssl will give you a signature for a file produced using secp256k1 - you don't have to invent a new standard for it..

[tacotime]

^^^

[bit22gen]

Using low S values in signatures according to BIP-62 seems like a good idea
even if malleability for full file signatures is not a problem currently.

https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki

I have changed the implementation so low-s signatures are always generated. (Not yet released)

For full file signatures low-s is now a requirement, and the signature will not validate without beeing low-s.

In the other signature formats non-low-s is still accepted by bitgen.

Code for calculating and verifying low-s:

Sign:
======================
   //The computed (r,s) values is a valid signature.
   //However, we want to always use the "low-s" signature

   const BigInt<1024> nHalf = (ec.n >> 1);
   if(s > nHalf)
   {
      const BigInt<1024> s2 = ec.n - s;
      const ECPoint rs2(r, s2);
      return rs2;
   }   
   
   const ECPoint rs(r, s);
   return rs;
======================



Verify:
======================
   const BigInt<1024> nHalf = (ec.n >> 1);
   if(s > nHalf)
   {
      std::cout << "Does not use low-s value, incorrect signature" << std::endl;
      return false;
   }
======================