Next-Generation (Post-Quantum) Cryptography

[mDuo13]

Opening this discussion as a general gathering place for the discussion of new cryptography standards and how to keep XRP Ledger technology up-to-date with developments in cryptography and security.

Current State

Last updated: 2022-07-06

The XRP Ledger directly uses the following cryptographic hash algorithms:

• SHA-512Half. Used extensively, including in key derivation from seeds, transaction identifiers, ledger structure, identifying parent ledger blocks, etc. Believed to have comparable security to SHA-256.
• RIPEMD160. Used in account address derivation.
• SHA-256. Used in account address derivation.

The XRP Ledger uses the following digital signature algorithms:

• ECDSA using the secp256k1 curve. Allowed for all types of account keys for authorizing transactions (master key, regular key, signer list entry), payment channel claims, peer-to-peer communications, and validation messages.
  • To avoid transaction malleability, signatures must use the numerically smaller value out of the two possible signatures.
• Ed25519. Allowed for all types of account keys (master key, regular key, signer list entry), payment channel claims, and recommended validator lists.
  • Notably, Ed25119 currently cannot be used for peer-to-peer communications or validation votes. (Validators' ephemeral keys have to be secp256k1 even if their master keys are Ed25519.)

Furthermore, the MessageKey field of accounts is expected to take a valid 33-byte secp256k1 or Ed25519 key as a value. There is no cryptographic algorithm for encrypting messages implemented at a protocol level, but clients are expected to use ECIES to encrypt and decrypt messages.

Note, communications from clients to APIs are not covered here. Those are (generally) protected by Transport Layer Security and should be kept up to date with the latest HTTPS standards separately from these protocol-level concerns.

Known Weaknesses

• Multi-signed transactions can be malleable in the sense that parties can add or remove valid signatures while still meeting quorum requirements, resulting in different hashes for effectively the same transaction. This is an accepted risk that can be mitigated with proper operational security around quorum settings and collection of multi-signatures.
• Elliptic curve schemes including secp256k1 and Ed25519 are vulnerable to Shor's algorithm on theoretical quantum computers. Current quantum computers are not capable of performing Shor's algorithm with enough qubits to break elliptic curve keys of the size used by the XRP Ledger. Quantum computing technology continues to advance and it is unknown how soon it may become feasible to break these keys, but estimates of "within a decade" are plausible.

Post-Quantum Digital Signatures

RSA and Diffie-Hellman signatures have the same vulnerability to Shor's algorithm as elliptic curve signatures. (In RSA's case, it has other weaknesses, too.) The US National Institute of Standards and Technology (NIST) has been working on collecting and standardizing new algorithms that are resistant to quantum computing. NIST categorizes security of proposed algorithms at various key sizes into five "levels" as follows:

Level	At least as hard to break as...
1	AES128 (exhaustive key search)
2	SHA256 (collision search)
3	AES192 (exhaustive key search)
4	SHA384 (collision search)
5	AES256 (exhaustive key search)

Based on these benchmarks the XRP Ledger should aim to support at least one "post-quantum" digital signature algorithm with security in the level 1 to 3 range. As for when, it's not a bad idea to start planning how to support a post-quantum signature algorithm now with the goal of implementing one or more algorithms when NIST publishes its final standard (expected "by 2024").

As of the latest round the digital signature algorithms that will be standardized are:

• CRYSTALS-Dilithium (NIST recommends this as the primary choice)
• FALCON
• SPHINCS+

Here's how the public key sizes required to achieve level 1 / 3 / 5 security for post-quantum algorithms compare to legacy algorithms:

Scheme	Level 1	Level 3	Level 5
CRYSTALS-Dilithium	1312 (level 2)	1952	2592
FALCON	897	N/A	1793
SPHINCS+	32	48	64
Elliptic Curve	32	48	64
RSA / Diffie-Hellman equivalent	384	960	1920

(All key sizes in bytes; comparable levels of security are, of course, estimates since attacks on individual algorithms vary based on details. Also note these are the ideal difficulties not taking into account side-channel attacks.)

However, there are other tradeoffs involved. SPHINCS+ for example generates very large signatures (7000–50000 bytes, compared to 600–1300 bytes for FALCON or 2400–4600 bytes for Dilithium). The amount of time it takes to generate keys or signatures is also variable between schemes and configurations, and the number of times you can safely reuse the same key varies as well. These details have implications for the transaction cost these transactions would have to burn to avoid overloading the XRP Ledger network's collective bandwidth, processing power, space in memory, and long-term storage. Other factors like complexity and vulnerability to side-channel attacks also matter for purposes of their use in a blockchain context.

Hypothetical Protocol Changes

Supporting Ed25519 signatures was easier than the migration to any post-quantum algorithm because an Ed25519 public key with a prefix (0xED) fits into the same byte space as a compressed secp256k1 public key without ambiguity. (secp256k1 compressed public keys have a 1-byte prefix that is either 0x02 or 0x03.) Furthermore, Ed25519 signatures are faster and easier to calculate than secp256k1 signatures, so there was no need to impose different transaction costs on transactions using these signatures.

Fortunately, both the SigningPubKey and Signature fields of transactions are variable-length encoded, with a theoretical maximum capacity of 918744 bytes, so they are capable of supporting a range of cryptographic systems' keys and signatures. The first byte of the SigningPubKey can, therefore, continue to act as a prefix indicating the signature system for which this key is valid; I propose the following prefixes:

Prefix	System	Notes
0x02, 0x03	secp256k1	In use since the inception of the XRP Ledger. 0x02 means the omitted Y coordinate is even; 0x03 means the omitted Y coordinate is odd. See secp256k1 key derivation for details.
0xED	Ed25519	In use since ~2014. ED short for the Edwards curve the Ed25519 is named after.
0x87	CRYSTALS-Dilithium	Suggested. The CRYSTALS-Dilithium and CRYSTALS-Kyber systems' names are Star Trek and Star Wars references, respectively. In the Star Trek setting, dilithium is element 87 (not just two lithium atoms).
0xFA	FALCON	Suggested. FA short for FALCON.
0x5F	SPHINCS+	Suggested. 5F because 5 resembles an "S" and "F" sounds like "PH" so 5F can be considered short for SPHINCS+.

(To reiterate: I don't think we should enable all 3 on the production XRPL, but we should consider them and maybe even put together test implementations for all three to compare on test networks. It may also be advisable to consider algorithms from other standards bodies given past concerns with the integrity of NIST's algorithms.)

The minimum transaction cost for transactions using these signature schemes should be scaled based on the size of the relevant fields and the performance of the implementation compared with signature verification on the existing schemes.

Post-SHA2 Hash Functions?

Arguably the XRP Ledger has a much deeper and more intractable dependence on the SHA2 family of hash algorithms (including SHA-256 and SHA-512). If efficient preimage collision attacks on these hash functions became feasible, the XRP Ledger could be at risk of attacks from many angles including modification or falsification of ledger state data and history. There is currently no sign that these functions will be broken anytime soon, but between the advancements of computing hardware power and cryptanalysis techniques, all prior hash functions have eventually become insecure, so we can expect that sooner or later these will too—probably on the order of decades, not hundreds of years in the future.

Moving to a new primary hash function would have many challenges involved, but one possible first step would be to adopt an encoding for transaction or ledger identifiers that encodes the hash function used. Perhaps a similar approach to IPFS's CID v1 would be appropriate. For a simpler approach, we could adapt existing API methods to support additional parameters for other hashes, such as ledger_sha3 instead of ledger_hash.

The entire underlying tree structure of the ledger data (the SHAMap) would have to be upgraded if it were to support a new hash function; we couldn't mix and match these like we do signatures. Due to the amount of calculations this would require to convert the entire ledger state to a new format, this seems likely to require collective downtime of the XRP Ledger (possibly multiple hours). While a brief downtime is preferable to the damage that a totally broken hash function could mean for the ledger, this type of change should not be made lightly, and can likely be postponed until the cryptographic community has demonstrated more serious weaknesses of/attacks on the SHA2 family.

That said, it would not be a terrible idea for a sidechain or private test network to experiment with an XRP-Ledger-like chain that use the SHA-3 family of hash functions.