2
$\begingroup$

I have a project where a user needs to store a U32 encrypted on a blockchain such that they can recover it themselves: the user will always have their key available but may "forget" the U32 value. No other party needs to decode the information, but the plaintext will eventually also be public on the chain.

The user has an entropy seed from which an infinite number of keys of any size can be deterministically derived. I was looking to using a single block of AES but it occurred to me that a simple XOR would also suffice. Assuming the user derives a unique "key" every time they perform this type of operation, is there any reason to do anything more complicated than that?

$\endgroup$
13
  • 2
    $\begingroup$ Standard cryptographic practice (12B nonce + 16B authentication tag) would require 32B of storage for a 4B value. Given that your storage is a blockchain and assuming you always find the correct value, you might be able to get away without further authentication getting down to 12B of nonce overhead. If you can walk the blockchain state and count the number of transactions you have done overall you could use that number as the nonce and get to 0B overhead. It depends on whether the previous two assumptions are sensible. $\endgroup$
    – SEJPM
    Nov 19, 2020 at 14:18
  • 1
    $\begingroup$ Actually, the entire message is also signed (it is a blockchain transaction) so I don't think the auth tag is really necessary. The user knows for certain this is their encrypted blob and they can generate the decryption key from their seed. $\endgroup$
    – pinhead
    Nov 19, 2020 at 14:45
  • 1
    $\begingroup$ That is not the point! The point is that since nobody has the knowledge of either the message or the OTP key, then you can reveal the message as any message you want. Then the poor people will find a key that is not the original key. And people like me will smile at you. The Accepted answer is therefore wrong. The SEJPMs solution is what you want, not OTP! $\endgroup$
    – kelalaka
    Nov 19, 2020 at 20:37
  • 1
    $\begingroup$ ` but the plaintext will eventually also be public on the chain.` What is the aim then? $\endgroup$
    – kelalaka
    Nov 19, 2020 at 21:38
  • 1
    $\begingroup$ @kelalaka I want to encrypt a U32 in a public place, then decrypt later in case I forget the U32 value. The bigger picutre, what the cryptocurrency uses the U32 for, is irrelevant, it gets processed by the forgetful user in a different scheme later on $\endgroup$
    – pinhead
    Nov 19, 2020 at 21:48

2 Answers 2

3
$\begingroup$

The obvious answer is to use a one time pad. If you are truly using a unique random 4 byte key for each 4 byte block then it is provably secure.

The user has an entropy seed from which an infinite number of keys of any size can be deterministically derived.

The real problem is this "derived" randomness and how random it truly is. I'm not aware of any infinite source of it.

With Salsa/ChaCha you could generate up 2^64 512 bit keys, each key being able to encrypt 16 different 4-byte blocks. So I suppose infinite enough.

Users would need to seed it with a 320 bit key. They need to change their their key after 2^68 (if my maths isn't wrong) encryptions. Using a setup similar to XChaCha allows you to extend this to 2^132.

In summary, if you have a cryptographically secure source of randomness you can just XOR.

$\endgroup$
4
  • 1
    $\begingroup$ In bitcoin and related systems we have a standard called BIP32 github.com/bitcoin/bips/blob/master/bip-0032.mediawiki which can generate ECDSA keys based on a series of integers called a path. The idea would be to use data from the chain to derive a single-use 32 byte key (maybe hash it a few times for security) and then use that as the OTP $\endgroup$
    – pinhead
    Nov 19, 2020 at 16:19
  • $\begingroup$ I would rather memory the 4-byes instead of memorizing the OTP key. Chihcken-egg problem. Also, OTP is the wrong solution since the OP can reveal whatever they want. $\endgroup$
    – kelalaka
    Nov 19, 2020 at 20:08
  • $\begingroup$ @kelalaka: "Reveal whatever they want" -> OP wants a backup/restore mechanism, not a delayed revelation mechanism. $\endgroup$ Nov 19, 2020 at 22:48
  • 2
    $\begingroup$ @MooingDuck but the plaintext will eventually also be public on the chain. $\endgroup$
    – kelalaka
    Nov 19, 2020 at 22:49
2
$\begingroup$

So, the standard solution of a cryptographer with these constraints would be to use AES-128-GCM with a 12 byte nonce and a 16 byte authentication tag using a fixed secret key.

However, the fact that this value is stored on the blockchain allows some unqiue size reductions:

  1. The nonce can be dropped and instead re-derived from the number of values written to the blockchain - which is retrievable by inspecting the past state of the chain. This assumes that the key is only used for this application and not other usage of the key can accidentally use the same key / nonce pair as any transaction.
  2. The authentication tag can be dropped because you always know what the ciphertext is and it can't be changed after submission thanks to the signature on the transaction and the immutable nature of a blockchain. Note that this assumes that upon retrieval of the value you either trust the blockchain client not to deliver a wrong value or that you can somehow also retrieve the relevant signed transaction and verify it.

Now if you remove both of these you are essentially left with AES-128-CTR which computes $\operatorname{AES}_K(C)\oplus M$ for a fixed key $K$ and your counter value $C$ and a message $M$. Note that this doesn't incur any message expansion because you can just rederive the same part of the AES output for decryption.

$\endgroup$
2
  • $\begingroup$ If I understand correctly, we use a counter and a key as inputs to AES to generate a value that we then XOR with the message. Do we need the AES function at all then? If the key is secure and single-use can I not use it as a OTP as suggested by the other answer? $\endgroup$
    – pinhead
    Nov 19, 2020 at 16:23
  • $\begingroup$ @pinhead AES in the middle here ensures that you don't have to remember all the fresh keys. If I understand correctly however, you can derive a key per-message securely. In that case you might as well use that for direct OTP-like encryption because AES in this case is just a method to derive a fresh random-looking key for each message. If you already do that, you can indeed skip AES (assuming the derived key looks cryptographically random). $\endgroup$
    – SEJPM
    Nov 19, 2020 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.