# Ed25519 keys

TODOS:

- [ ] Another research item. Reportedly Apple's CryptoKit supports 25519, and also has a KeyAgreement in https://developer.apple.com/documentation/cryptokit/sharedsecret that may use X25519. Are we able to use/convert any of their public keys and do meaningful operation with CryptoKit's private keys in 25519?

## Abstract

WIP

This document summarizes some general information about using and managing of `Ed25519` keys in popular applications
such as Minisign, Tor Onion service, Signal, Cryptocurrencies.

## Introduction

`Ed25519` keypair consists of a `secret key` (a random 32 byte number, sometimes called `seed` or `private key`) and a `public key`. When signing a message though,
the `secret key` is expanded (involves hashing and bit clamping) into an `expanded secret key` which consists of a `secret scalar` and a `nonce`. The `secret scalar` is in turn what is actually used to sign messages.

### Storage

Applications normally store its `Ed25519` secret key and public key (e.g. [Minisign](https://jedisct1.github.io/minisign/)). However, some applications (e.g. a Tor onion service) store the secret key in its expanded format (i.e. `expanded secret key`) to improve the signing performance. Since expanding a secret key involves [hashing](https://github.com/dalek-cryptography/ed25519-dalek/blob/925eb9ea56192053c9eb93b9d30d1b9419eee128/src/secret.rs#L266), the `expanded secret key` is no longer convertible back to its `secret key`. For this reason one can convert a Minisign secret key to Tor onion keys, but not the private key of onion service to minisign keys.

### Tor

An onion v3 address is essentially an Ed25519 public key:

 onion_address = base32(PUBKEY | CHECKSUM | VERSION) + ".onion"
 CHECKSUM = H(".onion checksum" | PUBKEY | VERSION)[:2]

This fact allows to conveniently build new applications on top of Tor onion services, e.g. [DIDs](https://github.com/BlockchainCommons/torgap-sig-cli-rust).

### Hierarchical Deterministic Keys

Bitcoin HD Wallets are known for deriving and managing keys according to [BIP32](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki).
[SLIP010](https://github.com/satoshilabs/slips/blob/master/slip-0010.md) tries to extend this concept to Ed25519 keys. Due to `bit clamping` (necessary to avoid a class of timing attacks) in Ed25519 key generation, SLIP010 managed to implement only the hardened derivation paths but not the soft (normal) dervation paths.

Another [paper BIP32-Ed25519](https://raw.githubusercontent.com/input-output-hk/adrestia/master/user-guide/static/Ed25519_BIP.pdf) emerged which suggests there
is possible to have normal derivations. The paper was implemented and is used in cryptocurrency [Cardano](https://docs.cardano.org/projects/adrestia/en/latest/key-concepts/hierarchical-deterministic-wallets.html#hierarchical-deterministic-wallets) for child derivation. Still, there are many reservations about this approach ([1](https://forum.w3f.community/t/key-recovery-attack-on-bip32-ed25519/44), [2](https://github.com/w3f/hd-ed25519/)).

Note, that only the child key derivations are unified across Cardano wallets [[1](https://github.com/satoshilabs/slips/issues/827#issuecomment-627573766)], whereas a master node derivation differs from wallet to wallet. For example, Trezor derives a master node according to [SLIP023](https://github.com/satoshilabs/slips/blob/andrewkozlik/slip-0023/slip-0023.md) and from *any* 32-byte master seed whereas `BIP32-Ed25519` paper and some Cardano wallets discard a master seed that does not map to a valid `expanded key` (every one in two is discarded). Also note, that child keys exist only in the expanded format, they don't have a (`RFC8032` compatible) private key. This means we cannot export child keys into `Minisign` key format, but we can use them for `Tor onion services`.

With regards to `Monero`, `Trezor` uses `SLIP010` to generate a master node and children, whereas Ledger does [bip32 derivations on secp256k1](https://github.com/monero-project/monero/issues/5744) and converts the keys to `Ed25519` keys through hashing. This makes `Trezor` and `Ledger` incompatible when deriving keys for `Monero`.

Due to problems with building complex protocols on top of `Ed25519` keys (e.g. HD key derivations), `Polkadot` implements [Ristretto point compression for the Ed25519 curve](https://w3f-research.readthedocs.io/en/latest/polkadot/keys/1-accounts.html). [The library](https://github.com/w3f/schnorrkel) implements `Schnorr signature`, `HD key derivations` and `MuSig`.
The library does seem to support exporting the `Ristretto Schnorr secret key` to `Ed25519 expanded secret key` and vice versa ([1](https://github.com/w3f/schnorrkel/blob/8fa2ad3e9fbf0b652c724df6a87a4b3c5500f759/src/keys.rs#L468), [2](https://github.com/w3f/schnorrkel/blob/8fa2ad3e9fbf0b652c724df6a87a4b3c5500f759/src/keys.rs#L83)).

## Signatures

Ed25519 signatures (`EdDSA`) may have [different validation criteria](https://hdevalence.ca/blog/2020-10-04-its-25519am) accross different implementations, so it's important to validate signatures within the same ecosystem that signatures are issued in.

The points of contention are:
* `canonical s`: honestly-generated signatures will have `0≤s<q0` and implementations can choose to reject `s≥q`.
* `canonical A`: Implementations can choose to reject non-canonically encoded curve points
* `verification equation`: batched vs individual verification of signatures can give different results
* (In addition there are some ad-hoc checks added by a particular implementation)

This problem originates from `RFC8032` which initially did not (sufficiently) specify validation criteria. It added them several years later and many implementations didn't (couldn't) follow. However, there still appears to be one point of contention left in the `RFC8032` ([1](https://hdevalence.ca/blog/2020-10-04-its-25519am)), that is allowing for batched and unbatched verification of signatures. This means conforming to `RFC8032` still gives no guarentee of compatibility behavior.

*Note:* in contrast to `ECDSA` signatures, public keys cannot be extracted from `EdDSA` signatures. They have to be communicated explicitly.

### Multi party signature scheme

[Multi party EdDSA](https://github.com/ZenGo-X/multi-party-eddsa) supports aggregated signatures, (accountable subgroup) multisig and threshold signatures ([1](https://tools.ietf.org/id/draft-hallambaker-threshold-sigs-00.html), [2](https://medium.com/blockchain-at-berkeley/alternative-signatures-schemes-14a563d9d562)). Wrt threshold signatures:

> Users generate their own keys and then have an aggregation step to create a single public key and transaction signing has a three round interactive protocol.

`Tezos` has a PoC for Ed25519 threshold signatures ([1](https://zengo.com/adding-threshold-signature-scheme-tss-to-tezos/), [2](https://ee-paper.com/how-to-use-threshold-signature-scheme-tss-to-control-tezos-address/)) but there appears to be no cryptocurrencies using threshold signatures in production.

## Signal

[Signal](https://signal.org/docs/) uses `X3DH` key agreement protocol to establish a shared secret between two parties based on a set of X25519 keys. Since the protocol requires publishing the set of keys to a server, a party has to provide a certain signature to ensure a strong `forward secrecy` once communication is established. To produce (verify) the signature, a party maps ([birational map](https://blog.filippo.io/using-ed25519-keys-for-encryption/)) its `X25519` identitity key into an `Ed25519` key which in turn does the signing (verification). This algorithm is called `XEdDSA` to distinguish the signing and validation criteria from those of `EdDSA`.

After the shared secret key is established Signal uses it to initialize the `Double ratchet protocol` to send and receive encrypted messages. The parties attach new Diffie-Helman public values to their messages to effectively rotate the shared secret key which is mixed into a key derivation (KDF) chain which produces a new message key. Message key is in turn used to encrypt/decrypt a new message.

### Database

`Signal` keeps data in `sqlite` database encrypted with [sqlcipher](https://github.com/sqlcipher/sqlcipher) [[1](https://www.yoranbrondsema.com/post/the-guide-to-extracting-statistics-from-your-signal-conversations/), [2](https://github.com/Magpol/HowTo-decrypt-Signal.sqlite-for-IOS)]. The key to decrypt the database is located in `config.json` in plaintext. Inspecting the database shows not only the conversations but also `X25519` keys (`Identity keys`, `signed prekeys`, `prekeys`) used to derive the (initial) `shared secret`. Device owner's `identity key`, `signed prekey`, password etc. are stored in table `items`.

gorazd@gorazd-MS-7C37:~/.config/Signal/sql$ sqlcipher db.sqlite
SQLite version 3.33.0 2020-08-14 13:23:32 (SQLCipher 4.4.2 community)
Enter ".help" for usage hints.
sqlite> PRAGMA key="x'3d3987230cd441ffda6e26750da978943d3987230cd441ffda6e26750da97894'";
ok
sqlite> .tables
attachment_downloads  messages_fts_config   signedPreKeys       
conversations         messages_fts_content  sticker_packs       
emojis                messages_fts_data     sticker_references  
identityKeys          messages_fts_docsize  stickers            
items                 messages_fts_idx      unprocessed         
messages              preKeys             
messages_fts          sessions            
sqlite>

## Encryption

### miniLock

miniLock uses a brainwallet style of ed25519 creation, which we don't want to support. However, there are some very interesting features of how it does what it does to encrypt for multiple people that we want to learn from to do a CBOR version of encryption that leverages sskr seeds or key, or derived keys, to encrypt metadata to package along with sskr root to be able to do social metadata recovery.

My miniLock public key (an EdDSA key using the 25519 curve):

`7rXYBKi1Xf9g9nupb9f8u6MHbobEJCMK3r3sChjN5RmGN`

[As published on [Twitter 1:47 PM - 20 Aug 2015](https://twitter.com/ChristopherA/status/634466769311105024)]

The minilock website has expired or has been pouched: [ARCHIVE.ORG 2018-09-15 https://minilock.io/ ](https://web.archive.org/web/20180915100358/https://minilock.io/) as has the Minilock Chrome extension, but the GitHub source is still available [github:@kaepora](https://github.com/kaepora/miniLock) though hasn't been updated since 2015. There is a compatible command-line implementation [MikroLock](http://www.andre-simon.de/doku/mlock/en/mlock.php) with code at [gitlab@saalen](https://gitlab.com/saalen/mikrolock) as well as some useful utilities and visual overview of the [MiniLock file format](https://45678.github.io/miniLock-file-format/2.html) at [github@45678](https://github.com/45678?tab=repositories).

The essence of the best ideas here are in what they call the manifest in the [MiniLock file format](https://45678.github.io/miniLock-file-format/2.html).

## Conclusion

Due to bit clamping in `Ed25519` keys it is incredibly difficult to build complex applications (e.g. hierarchical determnistic key derivation - `HDKD`) on top of them.
There are implementations of `Ed25519` `HDKD` with limitations and with only a few real-world applications. Therefore, new projects rather choose `Ristretto` encodings over `RFC8032` because it easily supports `HDKD`, `MuSig` etc.
It would be interesting to know when doing `HDKDs` with `Ristretto`, if children can be mapped to 'normal' `Ed25519` keys.
Mapping of private keys is possible, but can public keys also be mapped directly back and forth (without knowing a private key)? If yes, managing keys between different 25519 protocols could be managed through `Ristretto`.

## Q&A

* Q: I know that old like to know more about if and how other platforms are deriving 25519 form Ledger Trezor. I’d like to understand what kinds of 25519 keys are available under Android & iOS hardware supported APIs and compatibility issues.
* A: There is no compatibility issues between Ed25519 keys. Any 32 byte number is a valid Ed25519 private key (Yes, even zero is valid). TRNG is the only thing that matters accross different platforms. Expanding a private key is always the same: first apply hashing then apply bit clamping. Compatibility issues arise if you generate Ed25519 keys from X25519 keys (the otehr way around is fine [1](https://docs.rs/curve25519-dalek/2.0.0/curve25519_dalek/edwards/struct.EdwardsPoint.html#method.to_montgomery)), so to not have problems you stick with what Signal specified. Compatibility issues are also in the realm of HD keys as explained above (which are platform independent issues).
Wrt to signature compatibility between Android and iOS it's best to stick to RFC8032 implementations with individual verification equation only.

* Q: I’d like to know more about different signature formats.
* A: (plain EdDSA and hashed EdDSA with arbitrary hash functions (sha512, blake2b-512, etc.), what else?)

* Q: And understand more weaknesses revealed by https://hdevalence.ca/blog/2020-10-04-its-25519am
* A: (I'll see what i can do here)

* Q: I’d like to know more about where various apps store and/or backup their keys
* A: I noted about Signal's storage, whereas for Tor onion services and Minisign it is well known where and how they are stored

* Q: Most 25519 does Schnorr signatures natively, but only naively - key aggregation can only support M of M, but is anyone leveraging even that
* A: Answered above in 'Multi party signature scheme'

* Notes:
* https://blog.elcomsoft.com/2019/08/how-to-extract-and-decrypt-signal-conversation-history-from-the-iphone/
* https://www.yoranbrondsema.com/post/the-guide-to-extracting-statistics-from-your-signal-conversations/#1-get-the-sqlite-database
* https://searchsecurity.techtarget.com/answer/How-did-Signal-Desktop-expose-plaintext-passwords
* https://github.com/Magpol/HowTo-decrypt-Signal.sqlite-for-IOS
* https://www.redshiftzero.com/signal-protocol/
* https://github.com/monero-project/monero/issues/5744
* https://github.com/satoshilabs/slips/issues/827
* https://ledger.readthedocs.io/en/latest/background/hd_keys.html

* https://github.com/google/tink/issues/99
* https://www.reddit.com/r/Monero/comments/64cmbc/schnorr_signature_and_monero/
* https://crypto.stackexchange.com/questions/75981/does-eddsa-share-schnorr-signature-secure-linearity-property
* https://github.com/ZenGo-X/multi-party-eddsa
* https://wiki.polkadot.network/docs/en/learn-keys#why-was-ed25519-selected-over-secp256k1

## References

* https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/
* https://medium.com/@justinomora/demystifying-the-signal-protocol-for-end-to-end-encryption-e2ee-ad6a567e6cb4
* https://crypto.stackexchange.com/questions/84118/is-it-possible-to-safely-implement-the-signal-protocol-x3dh-without-using-xedd
* https://signal.org/docs/
* https://github.com/solana-labs/solana/issues/6301
* https://blog.filippo.io/using-ed25519-keys-for-encryption/
* https://github.com/dalek-cryptography/x25519-dalek/issues/53
* Academic paper "IACR: The Provable Security of Ed25519: Theory & Practice" https://eprint.iacr.org/2020/823.pdf

More references (2022-05)

* [It’s 255:19AM. Do you know what your validation criteria are?][https://hdevalence.ca/blog/2020-10-04-its-25519am]
*