Lack of entropy for encryption keys

[fedsten]

The specification defines K as 12 bytes random value, however 96 bits are not considered enough for today's security standards, so it is necessary to increase the entropy of the keys, but we still want to keep the 32 bytes limit to make the Color_Def undistinguishable form a SHA256. Unfortunately we cannot get to the raccomandable128 bits, since with such entropy the two keys would use the whole 32 bytes available making it impossible to put other data in the Color_Def, we would therefore recommend 120 bits, which represent a significant improvement and are an integer in bytes. To express all the other information in just two bytes is a bit challenging, but it is possible with acceptable trade-offs.

Currently the position of the two coloured inputs are expressed using two bytes, however if we make the protocol define that the coloured inputs always have to stay in first or second (when applicable) position, we can compress the input positions information in a single bit, which will simply specifies if there are either one or two coloured inputs (that will be found in the first or the first two positions).

We can similarly save space with the coloured vouts, if we enforce the coloured outputs to be always in the first positions, we just have to express how many coloured outputs there are in the transaction, knowing already they will be at the beginning of the output field. In this way, we can have up to 16 coloured outputs using only 4 bits.

Position	Size	Desciption
0-1	1 byte	RGB version
1-2	1 byte	Mask: 1 bit number of coloured inputs, 4 bits number of coloured outputs, 3 bits reserved
3-17	15 bytes	Tagging value of the previous output of the first coloured input
18-32	15 bytes	Tagging value of the previous output of the second coloured input , otherwise 0xffffffffffffffffffffffff

If we want to use XXTEA encryption algorithm to encrypt the Color_Def (not sure if we can consider it secure, please double check) needing an extra byte, we already have 3 reserved bits, and we can easily find other 5 bits reducing the version and the coloured outputs fields.

However even such solution is far from being optimal, 120 bits of entropy may be a security issue in the future and 32 bytes may not be enough to use a good symmetric encryption algorithm. Once we exceed the 32 bytes limit, for fungibility the second best number of bytes used is probably 80 bytes (you are just pushing as much data as you can in the OP_RETURN, multiple use cases). In this way, we can use 30 bytes for each key achieving a good level of entropy, 4 bytes to encode version and positions information, and 16 bytes used for encryption overheads (e.g. AES):

Position	Size	Desciption
0-1	1 byte	RGB version
1-2	1 byte	Mask: 1 bit number of coloured inputs, 4 bits number of coloured outputs, 3 bits reserved
3-32	30 bytes	Tagging value of the previous output of the first coloured input
33-64	30 bytes	Tagging value of the previous output of the second coloured input , otherwise 0xffffffffffffffffffffffff
65-80	16 bytes	Encryption overhead

In this case, if we find a symmetric encryption scheme which requires less than 16 bytes of overhead, we can even reach 32 bytes of entropy for each tagging value, which would be optimal.

[inaltoasinistra]

Currently the position of the two coloured inputs are expressed using two bytes, however if we make the protocol define that the coloured inputs always have to stay in first or second (when applicable) position,

This is not possible because positions of inputs depends by previous transactions, and they cannot be arbitrary chosen

[SimoneBronzini]

This is not possible because positions of inputs depends by previous transactions, and they cannot be arbitrary chosen

Well, I am not sure what you mean by this. In Bitcoin I can have an input (txid₁, n+1) in a position that appears before input (txid₂, n) (take this tx as an example). I don't see why one cannot do that in RGB transactions.

[inaltoasinistra]

I don't see why one cannot do that in RGB transactions.

Ops, I was wrong, I confused outputs of previous transaction with inputs.

I think that the motivation of specify input and output positions into Color_Def is guarantee privacy. If positions are fixed it is easy to follow the assets without decoding Color_Def

[RCasatta]

Enforcing input and output order to save space is not recommended for the following reasons:

• By forcing positions you are leaking privacy
• You cannot mix colored transaction in join market transactions (which can grant you more privacy)
• It's possible that one day will be encouraged/enforced a deterministic ordering of outputs which leaks less privacy, for example you can't do forensics based on tx building rules of some wallet (I haven't a reference but it was proposed by some core dev)

however 96 bits are not considered enough for today's security standards

Many still consider 80 bits enough for symmetric keys ... However I understand the worries and obviously I would like to have more entropy too. By using 6 bits to specify version and inputs/outputs position we can save 2 bytes and squeeze out 1 more entropy byte (reaching 104 bits). To be honest I consider this a much bigger problem...

Since we have versioning I would consider migrate to 80 bytes OP_RETURN an option for later upgrades.

If we consider to attack the derivation path instead of the encrypted Color_Def practically it takes about a day to iterate over one bip32 derivation. So it takes 2^64 days of a single computer to iterate over 96 bit. And this attack leaks privacy, do not steal bitcoins, so there aren't the same incentives.

[inaltoasinistra]

Many still consider 80 bits enough for symmetric keys ...

Since our data is public and stored into the blockchain we should be future proof.

The derivation path is it only another way to brute force the key. The attacker will use the cheaper way, so we must take care about both. Otherwise we could use a one-way function to hide keys from addresses derivations. For example K' = hash(K) Derivation path: xpub/K'1/K'2/K'3/K'4

[fedsten]

Since we have versioning I would consider migrate to 80 bytes OP_RETURN an option for later upgrades.

I believe that for improved fungibility it is better to have all the versions with the same number of bytes, making transaction clustering more difficult. At current rates, using 80 bytes instead of 32 will only cost 5000 extra satoshis

[RCasatta]

I don't consider reasoning about today rates a good judgment parameter, just some months ago was 30 times more expensive...

However it's probably a safest path to increase the cost of the tx and have more entropy for the privacy...

[SimoneBronzini]

The derivation path is it only another way to brute force the key. The attacker will use the cheaper way, so we must take care about both.

It is actually way easier to bruteforce two 12-byte keys than to bruteforce six levels of non-hardened HD keys. In fact: deriving a HD node is more computationally expensive than generating the next possible key to bruteforce. Furthermore, bruteforcing the HD tree has the same computational complexity of bruteforcing both K and J (i.e. you don't know that you have found the right K until you also find the right J), while bruteforcing K alone reveals J per the protocol specs.

Otherwise we could use a one-way function to hide keys from addresses derivations. For example K' = hash(K) Derivation path: xpub/K'1/K'2/K'3/K'4

Though this is a viable alternative, I dont't think this adds more security, assuming K and J are cryptographically-securely generated. Also, this would still need extra care, as in this case we'd need to split K in 8 chunks (assuming hash is a sha256 function) and still set the first bit to 0

[inaltoasinistra]

It is actually way easier to bruteforce two 12-byte keys than to bruteforce six levels of non-hardened HD keys.

This would change if a key derivation function is applied to the 12 bytes. Btw the one way function purpose is reduce the attack surface.

[SimoneBronzini]

This would change if a key derivation function is applied to the 12 bytes.

I am not sure what you mean by this.

Btw the one way function purpose is reduce the attack surface.

If the attack surface were the HD tree, a one-way function would help. But being the attack surface the key itself, a one-way function would not increase its entropy, apart from making the bruteforcing process a bit slower.

[afilini]

This issue refers to an old and obsolete version of RGB. See "old rgb" issue tag in our wiki.