2

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?

pinhead
  • 245
  • 1
  • 7
  • 2
    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. – SEJPM Nov 19 '20 at 14:18
  • 1
    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. – pinhead Nov 19 '20 at 14:45
  • OTP is not a solution for you, since you can change the message into whatever you want. Once you try to reveal the plaintext and say the OTP key is zyz then people who know the OTP, will smile at your face. – kelalaka Nov 19 '20 at 20:09
  • @kelalaka what do you mean? The ciphertext is signed and secured by proof of work, its unalterable. When I do reveal the plaintext in a future transaction, attackers will then be able to compute the OTP key I used, but it won't matter because I'll never use that key again. – pinhead Nov 19 '20 at 20:34
  • 1
    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! – kelalaka Nov 19 '20 at 20:37
  • consider the OPT encrypted text attack at down then you can easily say it is attack at dusk – kelalaka Nov 19 '20 at 20:39
  • @kelalaka ok I see, luckily that is not a requirement of the scheme. This is more like an encrypted backup/recovery scheme. It's just for the original user to recover. In fact in the larger project the value is already committed to by hash in a different step. My question right now is more a way of protecting the user from "forgetting" what that value was, by encrypting it to themself in a public place. – pinhead Nov 19 '20 at 21:33
  • 1
    but the plaintext will eventually also be public on the chain. What is the aim then? – kelalaka Nov 19 '20 at 21:38
  • 1
    @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 – pinhead Nov 19 '20 at 21:48
  • @kelalaka I made the assumption that the plaintext was to be encrypted prior to entering the blockchain and that the 4-byte block is part of the blockchain block. The blockchain would have no purpose AFAICT if completely encrypted.To OP - Maybe you could elaborate further on the scheme. If you had a maximum number of users then it might not be required to encrypt to lookup. If you use a universal hash it'd be quicker. Users who forget their blocks need to get and then check the whole blockchain, am i correct? Can they forget their blocks but remember their blockchain position? – Modal Nest Nov 19 '20 at 22:37
  • Sorry I shouldn't have mentioned Blockchain at all except to emphasize the ciphertext is public and signed and secured by proof of work. The message is not consensus critical. – pinhead Nov 19 '20 at 22:41
  • Then what is your actual question? Why are there are lots of blockchain stuff around? – kelalaka Nov 19 '20 at 22:57
  • You previously intimated the ciphertext is a way of "remembering" a forgotten block which suggests there is (potentially) no need for ciphertext. Encrypting wouldn't work as well (speed or functionality wise) as a uhash. In the case you simply need to encrypt 4 byte blocks, then any CPRNG with a counter of 2^64 should be enough for users to encrypt a 4byte block (with XOR, per ChaCha/Salsa) for every second of their lives. Should they so wish. – Modal Nest Nov 19 '20 at 23:27

2 Answers2

3

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.

Modal Nest
  • 1,443
  • 4
  • 18
  • 1
    In bitcoin and related systems we have a standard called BIP32 https://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 – pinhead Nov 19 '20 at 16:19
  • 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. – kelalaka Nov 19 '20 at 20:08
  • @kelalaka: "Reveal whatever they want" -> OP wants a backup/restore mechanism, not a delayed revelation mechanism. – Mooing Duck Nov 19 '20 at 22:48
  • 2
    @MooingDuck but the plaintext will eventually also be public on the chain. – kelalaka Nov 19 '20 at 22:49
2

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.

SEJPM
  • 45,967
  • 7
  • 99
  • 205
  • 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? – pinhead Nov 19 '20 at 16:23
  • @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). – SEJPM Nov 19 '20 at 19:21