Symmetric Key Announcements and Claiming

[aszepieniec]

This is a response to Dan's writeup regarding UTXO notifications, symmetric key announcements, and UTXO claiming. (I am not sure how to leave a response there.)

When a UTXO is created by a sender it is necessary to somehow transmit certain secrets to the recipient, so that the recipient can claim the UTXO.

Correct. Specifically, these secrets are:

• sender randomness (a Digest), needed to operate the mutator set;
• utxo (a Utxo) consisting of a lock script hash (a Digest) and a coins dictionary containing (type script hash, state) pairs of type (Digest, Vec<BFieldElement>). In the common case, this dictionary contains only one pair, (NativeCurrency::hash(), amount) where amount deserializes to a NeptuneCoins object, which is a wrapper around a u128.

This information highlights that the payload can have variable length.

A quick internet search did not turn up meaningful results. I did find a statement indicating that:

• Symmetric-key ciphertext length is the same or smaller than the original plaintext.
• Asymmetric-key ciphertext length is the same or larger than the original plaintext. Other sources indicate that symmetric key ciphertext length is normally the same or a tiny bit larger than the plaintext, due to padding.

This is mostly incorrect. The ciphertext can only be smaller if you drop information, in which case it cannot be decrypted again. The ciphertext can only be the same length if you pre-share the key (which is the case in our setting) and have no key-independent randomization (which we do want to have because otherwise encrypting the same plaintext twice gives the same ciphertext). The word "padding" could mean randomization, in which case that statement is correct; but it could also mean coercing the plaintext into the right format before encrypting, in which case that statement is incorrect. Asymmetric ciphertext lengths are virtually always larger than the corresponding plaintext.

I would summarize the situation as follows.

• Symmetric ciphertexts are a small constant number of bits larger than their corresponding plaintexts due to randomization and MACs. A "small constant number" is something on the order of the security level, say 256. We want to use an AEAD mode which implies both.
• Asymmetric ciphertexts are a larger constant number of bits larger than their corresponding plaintexts. Typically the KEM/DEM framework in used, wherein the asymmetric crypto is used to securely transmit a shared symmetric key (that's the Key Encapsulation Mechanism), which is then used to symmetrically encrypt the plaintext (that's the Data Encapsulation Mechanism and one might as well use an AEAD mode here). The phrase "larger constant" means something in the ballpark of 5x the security level.
• Post-quantum asymmetric ciphertexts are a large constant number of bits larger than their corresponding plaintexts. The same KEM/DEM framework applies except you need to use a different scheme for the KEM part. Using lattice-based KEMs, the ciphertext (for just the KEM part) is typically on the order of 1-4 kB. Quantum computers are rarely capable of speeding up attacks on symmetric key primitives, so there's no need to worry about the DEM part being vulnerable.

Neptune currently supports lattice-based KEM for its GenerationAddress format. That's the addresses that start with nolga. You should be able to use this scheme to generate post-quantum ciphertexts and observe their sizes. Furthermore, since it uses the KEM/DEM framework, with a little digging work you should be able to extract the symmetric part and use that for statistics on symmetric ciphertext sizes.

We already have PublicAnnouncements and ExpectedUtxos. It seems clearer to call these OnChain and OffChain notifications, respectively.

I'm not sure this renaming is a good idea. Since public announcements live on transactions and can make transactions valid or invalid, they are subject to consensus logic. However, ExpectedUtxos lives entirely on the client side and different clients might have different implementations regarding how they become aware of UTXOs intended for them.

pub enum UtxoOnChainNotifyMethod {
    PubKey(PublicAnnouncement),
    SymmetricKey(PublicAnnouncement),
}

Note that the announcement itself already possesses the information about whether it is a public key or symmetric key ciphertext. In light of that, I'm not sure how or when this struct would be used.

Symmetric Key Cipher Selection TODO: More work/research needed here. Some possible candidates: AES, RC6, Twofish, SPECK128, LEA, ChaCha20-Poly1305

Right now GenerationAddress uses AES-256 in GCM mode for the DEM part. If this choice turns out to be inadequate for whatever reason, I would suggest as follows.

cipher	advice
AES	yes but you still need an AEAD mode
RC6	no
TwoFish	no
SPECK128	f** no
LEA	no
ChaCha20-Poly1305	yes

In my opinion, there is no good reason not to use AES in our case. AES has received by far the most scrutiny and is by far the most widely deployed. Reasons not to use AES could be:

• You need a cipher that is native to a different field, for instance the Oxfoi field, because it works in the context of some overlay protocol like a proof system or multi-party computation that fixes the field to something different from $\mathbb{F}_{2^8}$ (over which AES is defined).
• The cipher needs to consume the lowest possible amount of energy. Actually, I am not sure this is an argument against using AES but it's certainly an argument researchers use to motivate studying other ciphers. The energy consumption is an issue for instance in pace makers, where yes you need to communicate with the outside world to receive updated programming, and yes this communication must be authenticated because you don't want to receive reprogramming from just anyone, and the cipher eats away in the pace maker's limited battery life, and you can't replace the battery or the entire pace maker every year. Energy consumption of cryptographic algorithms is not an issue for computers that are plugged into the grid or computers that are recharged often, like smart phones.
• Cache timing attacks are an issue. If you can make the victim encrypt a lot of data and if you have fine-grained insight to the victim's response times, then you can extract the key based on whether there was a cache miss or not. If cache timing attacks are an issue, then ChaCha20-Poly1305 is an excellent choice. Note that:
  • cache-independent implementations of AES do exist, but these are not widespread and generally slower
  • modern CPUs come with native AES support which voids this entire class of attacks
  • the ciphertexts are relatively short (kilobytes at most) whereas you need the victim to encrypt a lot of data to deploy the attack
  • the victim is generally behind an internet connection, which adds a lot of noise to the timing info, making the attack that much harder to deploy.

We have a choice whether to use a single symmetric key that all SymmetricKey notifications would be encrypted to, or to derive a new symmetric key for each UTXO. Using a single key has the drawback that if the key is ever stolen or published, then all UTXO notifications encrypted to it can be decrypted revealing the inner UTXO of each. Moreover, we require a mechanism such as the PublicAnnouncement receiver_id in order to match transaction outputs with our key. For a single key, the derived and publicly visible receiver_id would always be the same, which links these UTXOs together -- making this option unviable. Using derived keys, each key only unlocks a single UTXO, so loss of a single key does not enable UTXO linking. As such, key derivation seems the path we should take, ceteris paribus. A consequence of using key derivation is that we may incur additional cost when scanning for utxos that our wallet can claim. It is important to find an efficient construction.

This concern is mirrored closely by the fixed counter value in the spending key generation. In both cases I think it is prudent to fix the counter value for the time being, and roll out support for automatically incrementing it when more of the transaction infrastructure is in place. That said, we can brainstorm about the right way to go about claiming UTXOs when there are multiple potential keys.

And to minimize the possibility that we forget to roll out support for automatically incrementing the counter, let's open an issue on it.

2^16 limitation

It is worth discussing the counter: u16. Presently the code has a comment:

// We keep n between 0 and 2^16 as this makes it possible to scan all possible // addresses in case you don't know with what counter you made the address

This limits the number of derived keys to 65536, which is not really that much, especially if one considers:

• high volume merchants
• exchanges
• high frequency traders
• wallet consolidation transactions
• not all generated keys actually receive funds

Further, it seems a hidden privacy bug as the counter will simply wrap around to 0,which means that keys can/will be re-used, perhaps over and over.

I think we should re-consider this (mis?)-feature. If we do decide to keep it, then at minimum we should carefully document it for end-users, as I would consider it "surprising behavior" that I'm unaware of in other cryptocurrencies.

There is an argument for keeping the number of possible keys associated with one seed phrase low: it is the factor $n$ in the $O(mn)$ cost of claiming UTXOs.

Furthermore, it is debatable whether using a single seed phrase is good practice for the listed use cases. I certainly want to avoid degrading the user experience of common users (and early adopters especially) in order to better serve high intensity users.

That said, right now the counter is fixed to zero. In the future we will roll out support for automatically incrementing it and when this happens (and even before), having a u32 or even u64 for this value is just as cheap. What is expensive is the range of counters searched through. As long as there is a configuration option or command-line argument that defaults to something small and that high-intensity users can manually set to something suitable for their needs, I think all concerns are addressed.

We will have a wallet method for generating a new symmetric key that increments this counter, eg:

fn next_symmetric_key(&mut self) -> SymmetricKey { let key = SymmetricKey::from_seed_and_index(self.seed, self.next_symmetric_key_index); self.next_symmetric_key_index += 1; key }

Don't forget a similar mechanism for public keys.

We do not necessarily have to optimize this operation for a first implementation, however it is clear that we will need to do so eventually if/when blocks begin to fill up and people are using wallets with many transactions.

It's certainly not a high priority. Right now the counters are fixed to zero. After rolling out the automatic increment, we may tolerate the $O(mn)$ cost for a while. But down the line we want a better solution, and we might as well brainstorm and architect in advance.

Adapting for symmetric keys It seems straight-forward to adapt this mechanism to symmetric keys.

Agreed, and your suggestions are sound.

Monero Sub-Addresses use pre-computed hash table.

Why no Bloom filter? The scenario where you have $n$ receiver identifiers and you want to find out which one of $m$ blocks lists one of them screams for solution based on Bloom filters. You populate a Bloom filter with your $n$ receiver identifiers, and then loop over all receiver identifiers announced in all blocks to see if there is a likely match. Note that every query to the Bloom filter involves $k$ hash functions and that $k$ is independent of $n$, so the total cost is $O(m)$.

Quote: Bob checks if an output pubkey P in a new transaction belongs to him or not by computing D' = P - Hs(a*R)*G and looking for D' in the hash table Thus, this is an $O(1)$ operation for a given UTXO, or $O(n)$ when checking $n$ UTXOs.

If I understand correctly, P, R, G and D' are elliptic curve points and * denotes elliptic curve multiplication. So you have to do elliptic curve operations in order to check whether you can claim 1 UTXO. This is expensive relative to the Bloom filter solution for the equivalent problem in Neptune, but in exchange you have an extremely low likelihood of recipient identifiers or recipient-identifying data being reused. In particular, in Neptune you can generate multiple addresses (or you will be able to in the future) but you cannot prevent users from donating to the same address twice -- and these transactions will be linkable as benefiting the same user.

[dan-da]

I would summarize the situation as follows.

thanks, that's exactly the kind of analysis/perspective I was hoping for with regards to ciphertext lengths, etc. I will incorporate into the document.

Right now GenerationAddress uses AES-256 in GCM mode for the DEM part. If this choice turns out to be inadequate for whatever reason,

I was already leaning towards AES, so yeah let's go with that.

I'm not sure this renaming is a good idea. Since public announcements live on transactions and can make transactions valid or invalid, they are subject to consensus logic. However, ExpectedUtxos lives entirely on the client side and different clients might have different implementations regarding how they become aware of UTXOs intended for them.

I'm not sure I follow your logic here. Well, anyway let me explain where I'm coming from.

When I was first working with the codebase, the terms PublicAnnouncement and ExpectedUtxo did not convey much meaning to me. In particular, I did not get the notion that the latter are local-only data. Nor that they both do same/similar thing, namely transmitting secrets to the recipient. For a new enum, I carefully chose the name UtxoNotifyMethod with variants OnChain and OffChain to convey these ideas. Then I was thinking that it would be more consistent if we renamed PublicAnnouncement and ExpectedUtxo to match, ie:

// PublicAnnouncement --> UtxoOnChainNotification
// ExpectedUtxo      --> UtxoOffChainNotification

As a relative newcomer to the codebase I feel these names are a lot more self-describing.

That said, this is my single attempt to argue for the rename. If you are not convinced, I will remove that from the document.

Note that the announcement itself already possesses the information about whether it is a public key or symmetric key ciphertext. In light of that, I'm not sure how or when this struct would be used.

hmm, that's interesting! Can you elaborate? I would have to say the information is not clear/obvious. PublicAnnouncement is defined as:

pub struct PublicAnnouncement {
    pub message: Vec<BFieldElement>,
}

It has a single method, new(). Here is usage within ReceivingAddress.

        let mut ciphertext = vec![GENERATION_FLAG, self.receiver_identifier];
        ciphertext.append(&mut self.encrypt(utxo, sender_randomness)?);

        Ok(PublicAnnouncement::new(ciphertext)

Digging deep into ReceivingAddress::encrypt(), it's still not clear to me.

I would say that if we could add a field or method to PublicAnnouncement that indicates PubKey or SymmetricKey encryption is used, then that would suffice.

This concern is mirrored closely by the fixed counter value in the spending key generation. In both cases I think it is prudent to fix the counter value for the time being, and roll out support for automatically incrementing it when more of the transaction infrastructure is in place.

I don't see anything blocking implementation of derived symmetric keys, and to me it seems faster and more cohesive overall to design and build it all at once with momentum, so that's my preference. Plus it could be used as a testbed before we derive spending-keys. As before, let me know if I haven't convinced you, and I will modify the document to reflect a multi-stage approach.

As long as there is a configuration option or command-line argument that defaults to something small and that high-intensity users can manually set to something suitable for their needs, I think all concerns are addressed.

I could possibly get behind this, though am still conflicted about it. I have written tools for deriving addresses for both bitcoin and monero, and another tool that extracts key params from 100+ cryptocurrencies. I've never heard of anyone using keys that wrap around in any circumstance. So I would suggest that adequate solutions exist for using non-wrapping keys, and that is what users are already familiar with. As always though, I am generally ok with giving user's a choice and providing clear documentation.

There is an argument for keeping the number of possible keys associated with one seed phrase low: it is the factor n in the O(mn) cost of claiming UTXOs.

yes. Normally the wallet keeps an index of the next address to give out. So the key-space to search when claiming would be 0..index. Only when importing a seed-phrase or running specialty wallet-recovery tools would we need to search higher, ie looking for a "gap". In other words, I don't think that is a strong argument for looping keys.

One other possibility exists that we could entertain. Suppose we keep the u16 counter and make it a hard error to exceed u16::MAX. Ie, no wrapping allowed. This would force users to create a new wallet at this point. That is kind of terrible user-experience, but it does keep the property that the entire key-space could be searched for wallet recovery purposes. I am definitely not advocating for this approach, just throwing it out for completeness.

Why no Bloom filter?

I can't speak to Monero's reasons. As for me, simply because I am not that familiar with Bloom Filters. I will look into it, thx for the suggestion. Indeed if we could avoid storing precomputed key IDs on disk, that would be a good thing.

If I understand correctly, P, R, G and D' are elliptic curve points

yeah, I don't think we need to worry about that. I will remove it. Initially while drafting the proposal I was thinking we might need to adapt some of Monero's math in order to determine if we have a key that can claim a given UTXO, but then I realized that PublicAnnouncement already includes a receiver_id that does this. So the document is suggesting that we borrow the pre-computed hash-table of recipient_id --> index. Although it sounds like with bloom filters we may not even need that.

[aszepieniec]

I'm not sure I follow your logic here. Well, anyway let me explain where I'm coming from.

When I was first working with the codebase, the terms PublicAnnouncement and ExpectedUtxo did not convey much meaning to me. In particular, I did not get the notion that the latter are local-only data. Nor that they both do same/similar thing, namely transmitting secrets to the recipient. For a new enum, I carefully chose the name UtxoNotifyMethod with variants OnChain and OffChain to convey these ideas. Then I was thinking that it would be more consistent if we renamed PublicAnnouncement and ExpectedUtxo to match, ie:

// PublicAnnouncement --> UtxoOnChainNotification // ExpectedUtxo --> UtxoOffChainNotification

As a relative newcomer to the codebase I feel these names are a lot more self-describing.

That said, this is my single attempt to argue for the rename. If you are not convinced, I will remove that from the document.

PublicAnnouncements can be used for other things than transmitting UTXO info to the recipient. For instance, the description of how lightning might work with PublicAnnouncements uses this field to broadcast the counterparty's signature on the balance that the channel is being closed to. I'm sure there are more use cases that I can't think of.

I would say that if we could add a field or method to PublicAnnouncement that indicates PubKey or SymmetricKey encryption is used, then that would suffice.

The genericity of PublicAnnouncement is a feature, and binding it down with an enum field describing its type undermines that. The possible uses of PublicAnnouncement should not be constrained to what we are capable of inventing.

I've never heard of anyone using keys that wrap around in any circumstance.

Let me clarify. I definitely want to avoid wrap-arounds. So let's update the counter to a suitable type and maybe even catch wrap-arounds in a safe way. As a second priority, I want to optimize the UX for the casual user who might have made 100 transactions tops. If the casual user boots and without overriding any config options starts scanning blocks for 10000 different receiver identifiers, that's a fail.

[dan-da]

The genericity of PublicAnnouncement is a feature, and binding it down with an enum field describing its type undermines that. The possible uses of PublicAnnouncement should not be constrained to what we are capable of inventing.

fair enough. I get that you intend it be generic over many possible uses.

I am still unclear about this statement however:

Note that the announcement itself already possesses the information about whether it is a public key or symmetric key ciphertext. In light of that, I'm not sure how or when this struct would be used.

Can you elaborate on how, given a public announcement, one can determine if the ciphertext is symmetric or asymmetric?

edit: on second thought, I think you must be alluding to the type field. eg type = GENERATION_FLAG or type = SYMMETRIC_FLAG. ok, that makes sense now.

[aszepieniec]

Can you elaborate on how, given a public announcement, one can determine if the ciphertext is symmetric or asymmetric?

The cryptosystem, whether symmetric or asymmetric, knows when it fails to decrypt a ciphertext. Furthermore, it guarantees with a high degree of certainty, that if decryption succeeds, it was not a fluke but really a message meant to be decrypted by that key. So using this property: try and decrypt it as a symmetric ciphertext and then try and decrypt it as a public key ciphertext. If either method succeeds, then it was a symmetric respectively public key ciphertext. If neither method succeeds, then the ciphertext is not meant for me and I don't even know if it is symmetric or asymmetric (but I can make an educated guess based on the length).

Have a look at scan_for_announced_utxos in the implementation for SpendingKey in generation_address.rs. It tries to decrypt the public announcement, and if decryption fails it ignores it.

[dan-da]

I just re-read your comment below. Before I was focusing mainly on the hash table lookup optimization.

If I understand correctly, P, R, G and D' are elliptic curve points and * denotes elliptic curve multiplication. So you have to do elliptic curve operations in order to check whether you can claim 1 UTXO. This is expensive relative to the Bloom filter solution for the equivalent problem in Neptune, but in exchange you have an extremely low likelihood of recipient identifiers or recipient-identifying data being reused. In particular, in Neptune you can generate multiple addresses (or you will be able to in the future) but you cannot prevent users from donating to the same address twice -- and these transactions will be linkable as benefiting the same user.

Yes I believe monero calls these "stealth addresses" and they involve a one-time key. We may want to investigate something similar, either now or in the future, since address re-use is fairly common. That's an area I would need design assistance with as I am not a mathemetician or cryptographer.

If we do it, I believe the same general approach could probably apply to both the asymmetric and symmetric keys, but would defer to your expertise on that.

For now, I am just making a note about it in the design doc, as something we might want to do eventually.

[dan-da]

@aszepieniec I've incorporated your feedback into the document. Please let me know if any concerns/suggestions.