Proposal: Minisign FIDO2 extension to sign files using Ed25519 on SoloKey

[stevenwdv]

Note: part of the info below is outdated, in the end we settled on using a CTAP vendor command instead, see the rest of the issue comments.

---

I created a FIDO2 Minisign extension for the SoloKey 1. It uses a simple method to sign a file + comment using Ed25519, possibly using pre-hashing with Blake2b-512.

This extension would be a cheap and simple way to generate signatures using a modern algorithm on a hardware token, such that the actual private key does not have to be stored on a hard drive, for example. It could be used for authenticating documents, signing code/binaries, etc. Of course we can already create signatures directly with FIDO2, but if we sign a document this way (e.g. via ssh-keygen), then we also have to include some extra metadata like the authenticator data, so the verifier has to be changed as well. With this extension, an unchanged Minisign verifier can be used.

Minisign details

Minisign is a simple tool to sign files, which is already used to sign releases of various software packages. It is an extension of signify, both create signatures of a file using Ed25519 without appending any metadata to the document to be signed. However, Minisign also adds a (single-line) trusted comment, which is signed together with the file signature to obtain a second 'global' signature. This comment can contain metadata about the filename, date, purpose of signing etc. Minisign also supports Ed25519 with pre-hashing using Blake2b-512, contrary to signify, which only supports pure signatures. See below for more. I only implemented the pre-hashed variant of Minisign.

The concept is simple: you call authenticatorGetAssertion with the Minisign extension with the Blake2b-512 hash of the document you want to sign and a trusted comment to be signed, and you get the document signature and global signature (including comment) back!

The code can be found in stevenwdv/solo:minisign (diff).

This code can already be flashed onto existing non-locked Solo Hacker keys, but I think it would be nice to have it available in the official firmware as well, because then it can also be used with regular SoloKeys and locked Hacker keys. If it would be part of the official firmware, it will be easier for people to use. I can imagine it being useful to sign software packages, for example.

That's why I think it would be awesome if this were part of the official Solo firmware. However, before creating a PR I would like to know if you're interested in this or not. I also imagine that before this code would be merged, some tests verifying that the extension works correctly would be in order. In that case I could look into adding these to solokeys/fido2-tests.

Usage

I also updated solo-python to add a the solo key minisign command and add some switches to solo key make-credential, see stevenwdv/solo-python:minisign (diff).

(If you want to test this on a simulator over UDP, you can do this using the old v0.0.27 branch stevenwdv/solo-python:minisign-v0.0.27 (diff).)

To try it out, clone my forks:

git clone --recurse-submodules --branch minisign https://github.com/stevenwdv/solo.git solo-minisign
git clone --recurse-submodules --branch minisign https://github.com/stevenwdv/solo-python.git solo-python-minisign

Then follow the regular installation steps. (If you want to use it on an actual Solo Hacker hardware token, do not use the v0.0.27 version, as that will soft-brick your device until you hold the button while plugging it in.)

Options added to solo key make-credential

  --no-pubkey               Do not display public key
  --minisign                Display public key in Minisign-compatible format
  --key-file TEXT           File to store public key (use with --minisign)
  --key-id TEXT             Key ID to write to key file (8 bytes as HEX) (use
                            with --key-file) [default: <hash of credential ID>]
  --untrusted-comment TEXT  Untrusted comment to write to public key file (use
                            with --key-file) [default: <key ID>]

Previously, the make-credential command did not display the public key, but now it does, unless you specify --no-pubkey.
By default, the key ID is derived from the credential ID, such that it does not have to be entered separately when signing.

Added command solo key minisign

Usage: solo key minisign [OPTIONS] CREDENTIAL_ID FILENAME

  Sign file using Minisign-compatible pre-hashed Ed25519 signature

Options:
  [...omitted common options...]
  --sig-file TEXT           Destination file for Minisign-compatible
                            signature (<filename>.minisig if empty)
  --trusted-comment TEXT    Trusted comment included in global signature
                            [default: <time and file name>]
  --untrusted-comment TEXT  Untrusted comment not included in global signature
                            (combine with --sig-file)  [default: signature
                            created on solokey]
  --key-id TEXT             Key ID to write to signature file (8 bytes as HEX)
                            (combine with --sig-file) [default: <hash of
                            credential ID>]

I created a separate command instead of merging the functionality into sign-file, because the method of signing is wildly different and it would make the sign-file command unnecessarily complex.

Demo:

$ . solo-python-minisign/venv/bin/activate
$ # Add --udp to all solo commands for use with simulator
$ # Create credential with public key:
$ solo key make-credential --minisign --key-file solosign.pub
PIN (leave empty for no PIN):
Touch your authenticator to generate a credential...
375eaec31f4155d3e02a8bd5e3d48f40137ceeb3438465a9449ab725a32a2799144c1ac491d9d3712c63f7b8d6cfadf86d057d099d382246dbe9c87f133ed167881b1b000000
Public key C9E4C68599B0462E (minisign Base64): RWQuRrCZhcbkyd4u0AMI1gELjmVuzpA8NKsERSlAN4EGbx/f/a1/LCcl
Minisign public key written to solosign.pub

$ cat solosign.pub
untrusted comment: minisign solokey public key C9E4C68599B0462E
RWQuRrCZhcbkyd4u0AMI1gELjmVuzpA8NKsERSlAN4EGbx/f/a1/LCcl

$ # File to be signed:
$ echo Hello! >file.txt

$ # Create signature:
$ # Use credential ID and key ID from above (key ID can be modified in the signature file later on)
$ solo key minisign 375eaec31f4155d3e02a8bd5e3d48f40137ceeb3438465a9449ab725a32a2799144c1ac491d9d3712c63f7b8d6cfadf86d057d099d382246dbe9c87f133ed167881b1b000000 file.txt --sig-file=""
PIN (leave empty for no PIN):
6aaa9efd0c10b06e6c746889e6d459816fbab315435336a303ef440866ef74d301cf1e73a21a1d60430a1f5cca9df476e0f8855ff512028e29f52e39a36c5c80  file.txt
Trusted comment: timestamp:1633611343 file:file.txt
Touch your authenticator to generate a reponse...
Signature (Base64): tTQUTspPst58Bp3h9UvnpX3jnH2Y+2bL8jzkKmyg1x7Xqi99Q7jK9GAIojU8DmDRarVen2phA/l5XmWkuyCXBA==
Global signature (Base64): HaNhjemTk1BPb0OAezYfVUQK3XS6NZ3xZ2Fvgp9YqcvjhqTJKCOTp1XSjzm2bMJ4Eg1XGdq8ZYlyDnzY6uFKAA==
Signature using key C9E4C68599B0462E written to file.txt.minisig

$ cat file.txt.minisig
untrusted comment: signature created on solokey
RUQuRrCZhcbkybU0FE7KT7LefAad4fVL56V945x9mPtmy/I85CpsoNce16ovfUO4yvRgCKI1PA5g0Wq1Xp9qYQP5eV5lpLsglwQ=
trusted comment: timestamp:1633611343 file:file.txt
HaNhjemTk1BPb0OAezYfVUQK3XS6NZ3xZ2Fvgp9YqcvjhqTJKCOTp1XSjzm2bMJ4Eg1XGdq8ZYlyDnzY6uFKAA==

$ # Now we use the regular Minisign tool to validate the signatures:
$ minisign -Vm file.txt -p solosign.pub
Signature and comment signature verified
Trusted comment: timestamp:1633611343 file:file.txt

$ # Or:
$ minisign -Vm file.txt -P RWSV7hx2VCoiL3NRapZA31wS2pY8fxgXGbQtR+xYLwIlmH8qJ/BiMQPO
Signature and comment signature verified
Trusted comment: timestamp:1633611343 file:file.txt

It might be nice to also create a more compact dedicated client using a compiled language instead.

Implementation

FIDO2 extension

I implemented the signature program as a FIDO2 extension. This might sound like a weird way to do this, and in fact I wanted to implement it directly on top of USB HID at first, but implementing it as a FIDO extension has as advantage that it is easy to reuse keys, key management code, user presence and verification logic, CBOR encoding, and USB/NFC abstraction layers.
However, you might say that it does not entirely fit in as it changes the existing authentication mechanism and does not actually authenticate individuals, but rather files.

I did not implement the extension for U2F/CTAP1, as its message structure is wildly different and it does not support extensions in the way that FIDO2 does. Moreover, it does not support EdDSA credentials.

Request format

To request a signature, call authenticatorGetAssertion with the "minisign" extension.
The CBOR structure of the request extension looks as follows:

• "minisign":
  • hash(0x01): Blake2b-512 hash of the document to be signed (byte string, 64 bytes)
  • trustedComment(0x02): trusted comment to be signed for global signature (byte string, ≤128 bytes)

Note how the document hash is not placed in the regular clientDataHash field. At first I coded it that way, with a parser accepting fields of both 32 bytes (SHA-256) and 64 bytes (Blake2b-512), but it as it turns out, the python-fido2 library unfortunately does not support setting the clientDataHash directly, but 'hardcodes' it to be a specific JSON structure hashed with SHA-256. This is contrary to libfido2, which does support setting an arbitrary-length hash directly. To make the scheme also easily usable with libraries such as python-fido2, without developers having to resort to manually constructing CTAP2 messages or using USB HID directly, I chose to put the hash inside the extension. This may also keep the Minisign code on the token a bit more separated from the FIDO2 base code, but it does require a bit more space in structures. The normal clientDataHash field is ignored and can have any value.
If you think that the hash should be put into the clientDataHash field anyway, I could change that.

For now, I set the maximum length of the trusted comment to 128 bytes as to not take up too much space as the CTAP_getAssertion structure is allocated on the stack, but if there is an easy way to support larger comments I'd like to hear that. The maximum size that Minisign accepts is 8173 bytes. Currently, I return CTAP2_ERR_LIMIT_EXCEEDED if the comment is too large. Truncating it instead would also be possible, but I do not think that is desirable.

I chose to use a byte string instead of a text string because text strings are supposed to be UTF-8 while Minisign will accept any byte sequence not containing newlines (\x0a/\x0d), for example also \x9f, which is 'é' in ISO-8859-1/Windows-1252 but an invalid sequence in UTF-8, where the encoding of 'é' is \xc3\xa9. Depending on the code page etc. you will actually get the \x9f encoding in the signature file when you specify -t é with the original minisign tool.

The parsing code I wrote does not reject newlines in the trusted comment, even though the trusted comment in a signature file can only be a single line. I think it is the task of the client to verify this.

Minisign signatures are also implemented for authenticatorGetNextAssertion, although I do not think this will be used often.

Response format

The response consists of the document signature and the global signature (which includes the trusted comment). These are both 64 bytes. I put the document signature in the regular signature field of the response structure, but put the global signature inside an extension with the following format:

• "minisign": global signature (byte string, 64 bytes)

If you think it would be better to put both signatures in the extension (or both concatenated in signature), then I could change this.

Signing process

If the Minisign extension is present, the code will only accept Ed25519 credentials and return CTAP2_ERR_UNSUPPORTED_ALGORITHM otherwise. The hash that is input is immediately signed, without any added metadata like RP ID, counter, etc. For the global signature, the hash signature concatenated with the trusted comment is signed. Because the global signature is placed in an extension, signing has to happen before extensions are built, so signing in ctap_end_get_assertion would be too late.
No significant code changes were made to ctap_make_credential, because that signature is created with the attestation key.

About domain separation between assertions and Minisign signatures

Currently, the Minisign extension can use any Ed25519 credentials, which can also be used for regular authenticating assertions. This might be a problem if a malicious RP could let a client sign a structure (authenticator data + clientDataHash) that could be confused with a Blake2b-512 hash, as then the assertion signature could be used as a signature on a file with that hash. Actually, because Minisign has no domain separation between pure and pre-hashed signatures, it can be used as a signature for a file with that content. (Technically, you could use this Minisign extension to create signatures without pre-hashing on a file of exactly 64 bytes, see below.)

Conversely, a Minisign signature created by the extension could be used as assertion if the inputs (Blake2b-512 hash and authenticator data + clientDataHash) were to be the same. However, this will not happen by accident, so it cannot be used to fool unknowing RPs that choose a random challenge. If an attacker could let a victim sign an arbitrary 64-byte input with the Minisign extension and they can predict the authenticator data (the latter should be doable), then they may be able to spoof assertions, but this basically assumes that the system is already compromised, because an attacker has to directly feed inputs to the device (or break Blake2b-512 pre-image resistance).

What's more, this all assumes that both input types can have the same length, while in the current setting the two input types can never be confused, because authenticator data + clientDataHash together are at least 69 bytes while a Blake2b-512 hash is 64 bytes.
If it is desirable that more explicit domain separation is introduced anyway, maybe to make the system more future-proof, then I think that make_auth_tag would need to be changed to include a flag to indicate that a key can only be used for Minisign signatures. A special RP ID prefix (e.g. "minisign:"), might also be possible, but if a RP could freely choose its RP ID then the first attack would still be possible. However, WebAuthn clients can only choose parts of their domain name as RP ID.

Why Minisign

Minisign is nice because:

• It uses a modern signature scheme;
• For the main signature, it does not sign any metadata, so the full signed data can be freely chosen;
• It supports pre-hashing with a modern hashing function, so also large files can be signed fast and easily on a hardware token;
• It includes trusted comments, so more information can be included about what the signature author means with this signature;
• Its signatures can also be verified by signify, although this does not include the variant with pre-hashing that I used.

Minisign is less nice because:

• With pre-hashing, it does not follow Ed25519ph from RFC 8032 but rather directly signs a Blake2b-512 hash using plain Ed25519, so there is no domain separation between the pure and pre-hashed variant. Hence, it is trivial to forge one specific signature given a pre-hashed signature for file.txt: change the algorithm to Ed, and it will work as a signature for a file containing the Blake2b-512 hash of file.txt. This works because this metadata is not included in any of the two signatures. The other way around is also possible, but only if what is signed is already a file containing a (non-encoded) Blake2b-512 hash for which the pre-image is known. There are probably not that many cases where these attacks will necessarily pose a problem to security, but there might still be some, and it could possibly be used for DoS attacks if an automatic verifier accepts the signature and then the program crashes because of the invalid file format (e.g. it was expecting a JSON structure but got a binary hash instead). This can be countered by letting the verifier check the algorithm, if it is known ahead of time.
  UPDATE: Support for creating pure signatures was removed, see Domain separation between pre-hashed & pure version (forge signature for hash) jedisct1/minisign#104.
• Trusted comments are not optional, so even if the signing key is only used for a well-defined purpose and/or the content of the file describes enough about the file itself, you still have to add a trusted comment with extra signature.

I think it may be nice to implement signify as well, mostly because it is used more often. E.g. the minisign tool is currently not available as a package for Debian or Ubuntu, while signify is (as signify-openbsd). But it will require extra effort to support large files, as signify does not support pre-hashing.

Solo 2

As you can see, this does not contain a Rust implementation for the Solo 2 yet, mostly because the device is not available yet.

[nickray]

I think this would be very very awesome :) One of the many things I had on my perennial todo list...

[stevenwdv]

@nickray Nice! Should I already make a PR or are there still some things that have to happen / you want to look at / discuss first?

[stevenwdv]

Update: I now also implemented the extension in the latest version of the tool, see stevenwdv/solo-python:minisign (diff)

[nuno0529]

I think some points need to consider before adopting this change

1. Can the private keys be used for other cryptographic operations? w3c/webauthn#1595
2. Unknown extensions may not be bypass in client tools/browsers, at least chrome, Add instructions for passing unknown extensions to authenticators w3c/webauthn#789 (review)
3. Following Fido conformances tool may not allow unknown extension in metadata.

[nickray]

I'm not going to have time to review (I'm not very strong in C anyway). Some things that come to mind:

• what is the code size delta this introduces (it certainly looks small from the diff you linked)?
• it's probably annoying to "ifdef" this to be optional? Upholding conformance with the spec is a must, as the firmware is "FIDO L1 certified" (whatever that is worth - we'll have to go through re/delta certification since the CTAP 2.1 changes are considered substantial changes)
• on Windows or through browsers you'll have a hard time to no chance with unofficial extensions, so the potential users are Linux CLI people
• re. key sharing (spitballing), it might be sensible to enforce some magic byte sequence to distinguish minisign from FIDO keys

@conorpp thoughts?

[rgerganov]

FWIW, I have implemented file signing with ECDSA and SHA256 in PR #397 (at that time Ed25519 was not supported by Solo). My implementation is using custom CTAP command and it is clearly separated from the existing FIDO2 logic. I believe this is a better approach compared to changing core FIDO2 functionality. It is also supported by the official solo client with solo key sign-file <cred_id> <filename> added with this commit

[stevenwdv]

@nuno0529: w3c/webauthn#1595
@nickray: re. key sharing (spitballing), it might be sensible to enforce some magic byte sequence to distinguish minisign from FIDO keys

Okay it's probably better to add some proper separation between auth & sign keys, what do you mean with "magic byte sequence"? I was thinking maybe add a flag to make_auth_tag?

@nuno0529: Unknown extensions may not be bypass in client tools/browsers, at least chrome, w3c/webauthn#789
@nickray: on Windows or through browsers you'll have a hard time to no chance with unofficial extensions, so the potential users are Linux CLI people

I wasn't really focused on browsers until now, I was mostly looking at a CLI interface, which you probably are familiar with if you sign software, but indeed it would be less suited for people signing regular documents, for example. I actually thought WebAuthn RPs couldn't specify extensions but apparently I was wrong about that. In that case one should choose the RP ID for local signing operations such that it cannot be a domain name of some site, to prevent accidental signing operations.

@nuno0529: Following Fido conformances tool may not allow unknown extension in metadata.
@nickray: it's probably annoying to "ifdef" this to be optional? Upholding conformance with the spec is a must, as the firmware is "FIDO L1 certified" (whatever that is worth - we'll have to go through re/delta certification since the CTAP 2.1 changes are considered substantial changes)

I wasn't aware unknown extensions are not allowed in FIDO-compliant devices; does that mean that it will never be possible to ship something like this in the official firmware? If so, would this be allowed if it were a custom CTAP command like @rgerganov proposed?

@nickray: what is the code size delta this introduces (it certainly looks small from the diff you linked)?

I haven't looked at the code size yet, but I will update you when I do.

@rgerganov
Oops, I noticed the sign-file command but sort-of assumed that it used plain WebAuthn with the hash as challenge, also because I didn't see any implementation on the device, but apparently that is not merged.. Should've looked more carefully. I also see that #395 already mentioned signify.
I largely agree that separating it better is a cleaner approach. As I mentioned, I did not go for implementing it directly on USB HID because it would require duplicating a lot of logic. I hadn't really thought of implementing it as a custom CTAP command, which indeed seems a lot more manageable, although some user & credential validation code etc. has to be duplicated. I also noticed that it doesn't support residential keys or lists of credentials, but that may be fine in most cases. Additionally, with a custom CTAP command there is a lower chance it will be available in browsers, but as was mentioned this is probably also tricky with a custom extension.

What do the rest of you think about this? Should I try to add Ed25519 signatures to #397?

[rgerganov]

@stevenwdv If you decide to go with a custom CTAP command, I can help with reviewing code and testing. In my opinion the best way to go for now is to extend the work I have done in #397 and add support for Ed25519. For the client part, I suggest to keep the solo key sign-file and add support for minisign with additional command line parameter or something like that.
Overall, I like your idea and I think this would be useful even if it is available only for Solo hackers.

[stevenwdv]

I implemented a first version as custom CTAP command:

• stevenwdv/solo:sign-hash
• stevenwdv/solo-python:sign-hash
• (stevenwdv/solo-python:sign-hash-v0.0.27; unfortunately this is necessary to be able to quickly test stuff)

The CTAP structure is backwards-compatible, but note that the command now respects the credential type so you will get an EdDSA signature if you invoke sign-file with an EdDSA credential. I also switched it to print the signature by default instead of writing it to a file, but this could be reverted if desired. Lastly, it now uses HEX credentials just like make-credential, but it might be nice to have support for both Base64 (shorter) and HEX if this is also enabled in make-credential.
Something else for later might be to add support for residential keys / discoverable credentials as the FIDO2 extension has, but that would incur quite some extra complexity.

I'm not sure yet if invoking verify_pin_auth_ex with a variable-length hash is safe, but I must admit I'm a bit confused by the whole FIDO2 PIN protocol and haven't used a PIN myself yet.

Let me know what you think when you have time and have a good weekend!

[rgerganov]

The CTAP structure is backwards-compatible, but note that the command now respects the credential type so you will get an EdDSA signature if you invoke sign-file with an EdDSA credential. I also switched it to print the signature by default instead of writing it to a file, but this could be reverted if desired. Lastly, it now used HEX credentials just like make-credential, but it might be nice to have support for both Base64 (shorter) and HEX if this is also enabled in make-credential. Something else for later might be to add support for residential keys / discoverable credentials as the FIDO2 extension has, but that would incur quite some extra complexity.

It's great we can do both ECDSA and EdDSA with a single CTAP command and detect the key type in runtime. You may also consider using a separate command for EdDSA but then you will need the same boilerplate code for CBOR parsing. So I think it's better to implement both with a single command.

I have rebased #397 on top of the current master in case you want to base your work on it. In any case please open a PR so we can discuss the changes. The same applies for the changes in solo-python, you can open a PR and put the link here.

I'm not sure yet if invoking verify_pin_auth_ex with a variable-length hash is safe, but I must admit I'm a bit confused by the whole FIDO2 PIN protocol and haven't used a PIN myself yet.

The hash length should be either 32bytes (SHA256) or 64bytes (Blake2b). We should return an error if this is not the case.

Let me know what you think when you have time and have a good weekend!

Great stuff!

[stevenwdv]

The hash length should be either 32bytes (SHA256) or 64bytes (Blake2b). We should return an error if this is not the case.

I thought that to accept any hash function it may be nice to not enforce this, but on the other hand these options cover most cases. I added a check for this.

I have rebased #397 on top of the current master in case you want to base your work on it. In any case please open a PR so we can discuss the changes. The same applies for the changes in solo-python, you can open a PR and put the link here.

I cherry-picked my commits into your branch and opened two PRs: #583, solokeys/solo1-cli#137.

[stevenwdv]

I've started writing some tests and I just noticed that currently the credential is not validated in any way. Maybe it would be nice to do that (via ctap_authenticate_credential). For that we do need the RP ID. In my original post above I talked about domain separation, which is also not implemented here yet. Should we a) add a flag to the tag in the credential ID specifying if it is to be used with sign-hash (and only sign-hash), or b) introduce a special solo:sign-hash RP ID as this will not match regular domain names, for example:

struct rpId rp = {.id = "solo:sign-hash", .size = 14};
if (! ctap_authenticate_credential(&rp, &SH.cred))
{
    printf2(TAG_ERR, "Error: invalid credential\n");
    return CTAP2_ERR_INVALID_CREDENTIAL;
}

Edit: tests are here: stevenwdv/fido2-tests:sign-hash, these currently assume option (b). You need to replace solo-python v0.0.26 with stevenwdv/solo-python:sign-hash-v0.0.27 for this to work (run flit build and pip install the dist/*.whl file).

[rgerganov]

I've started writing some tests and I just noticed that currently the credential is not validated in any way. Maybe it would be nice to do that (via ctap_authenticate_credential). For that we do need the RP ID. In my original post above I talked about domain separation, which is also not implemented here yet. Should we a) add a flag to the tag in the credential ID specifying if it is to be used with sign-hash (and only sign-hash), or b) introduce a special solo:sign-hash RP ID as this will not match regular domain names, for example:

Adding flags to the CredentialId structure would most probably break existing credentials created by Solo. Using a fixed RP ID could work though. OpenSSH is already doing this by using the ID ssh: for its credentials. This has the advantage that we will be able to support resident keys for signing hashes by filtering by RP ID. This is the relevant code in OpenSSH: https://github.com/openssh/openssh-portable/blob/master/sk-usbhid.c#L1140

[stevenwdv]

I think it altering the credential ID could work if make_auth_tag would take a parameter indicating which verification method to use, but using a special RP ID would probably be better. I indeed know about the OpenSSH method. My main concern was if in some cases a malicious RP could specify that ID to get a signature, but this should probably be impossible because of the :? Also maybe a better ID would be solo-sign-hash:[optional string chosen by user] similar to what OpenSSH does. In this case the RP would need to be passed along. In any case, old credentials used for sign-hash will be rejected because they do not have the correct RP ID. Also, actually it would probably be best to reject credentials with the solo-sign-hash: prefix in FIDO2 methods, right?

[stevenwdv]

I implemented & merged the prefixed solo-sign-hash: variant, but you can still use these credentials with authentication methods as well

[stevenwdv]

but you can still use these credentials with authentication methods as well

I forgot to add that now I implemented a check for this a couple of days ago, so it should be all functional now.
PRs: #583, solokeys/solo1-cli#137