Subject: Re: Avoiding double writes

From: Sergey Matveev <[email-masked]>
Date: Tue, 2 Nov 2021 23:48:39 +0300

*** John Goerzen [2021-11-02 10:26]:
>Yes, exactly.  This metadata could be as simple as a u32 indicating how much
>of the following block is actual data.  Any u32 value beneath 128K
>(including zero) would indicate we've reached EOF of the original data and
>everything past that should be authenticated but discarded, I think.

Well, after some thoughts I came to the following construction.

* I do not like the fact that each payload-block will hold constant
  u32/whatever integer, that will differ only in single block in the
  whole stream. It is waste of space. Of course I understand that we are
  talking about mostly negligible 32-bits per every 128KiB of data, but
  I still do not like that waste :-)
* It can be replaced with "signalling" bit, or actually single byte (for
  convenience), telling that either current block is fully "payloaded"
  or holds an additional metadata, signalling the reaching end of the
  payload stream
* So actually we just have to differentiate single special block with
  metadata inside. It can be done by using different encryption key for
  it. That hack is used in widely-used CMAC for example: it uses one key
  to encrypt block with the pad, and another to signal that encrypted
  block has no padding. CMAC deals with just single 64-128 bit block,
  but NNCP with huge 128KiB one -- I think it is still acceptable CPU
  burn, because anyway excess 128KiB symmetric AEAD-decryption is much
  more cheaper that any of curve25519/ed25519 operations

So we derive two encryption keys: "ordinary" and "signalling" ones. When
block is encrypted with signalling key, that means that it holds two
64-bit integers at the beginning: full payload and padding sizes.
Period. That is completely enough change to the packets format. Let's
assume that each block holds 128-bytes of plaintext:

* If we are sending 200-bytes of data, then we generate two blocks:
  0: key=ordinary, 128-bytes of payload
  1: key=signalling, 64-bit integer with value 200 (full payload size)
                     64-bit integer with value 0 (no padding)
                     72-bytes of remaining payload
* If we wish to pad it with 30-bytes, then:
  1: key=signalling, 64-bit integer with value 200
                     64-bit integer with value 30
                     72-bytes of remaining payload
                     30-bytes of zeros
* If we are sending 128-bytes of data, then:
  0: key=ordinary, 128-bytes of payload
  1: key=signalling, 64-bit integer with value 128
                     64-bit integer with value 0 (no padding)
                     nothing else, 0 payload bytes remaining to read
* If we are sending 10 bytes of data, then:
  0: key=signalling, 64-bit integer with value 10
                     64-bit integer with value 0 (no padding)
                     10-bytes of payload
* If we are sending 126 bytes of data, plus 50 padding bytes then:
  0: key=signalling, 64-bit integer with value 126
                     64-bit integer with value 50
                     110-bytes of payload
  1: key=ordinary, 16-bytes of remaining payload
                   50-bytes of padding

If pad size exceeds free space inside the block, then I wish to use
current BLAKE3-XOF as a generator of random sequence. No real
AEAD-encrypted blocks, but just a stream of XOF output. But we do not
need to use cryptographic authentication, because that XOF is completely
deterministic (when we know session keys of course, adversary does not),
so we just can generate that stream too and compare them byte-by-byte:
it is much more faster. And we know exact pad size, to be sure that
noone stripped it off.

Slightly more bigger code (that is actually very simple, just some state
transitioning), slightly more CPU time spent on failed (initial)
decryption of signalled block, but minimal waste of additional space in
packets.

If we see that first block is already less that 128(KiB), then we can
decrypt it with signalling key immediately: so for very short packets
everything will be even more compact and faster than current
implementation, because in that "new" one there is only single encrypted
block, instead of two (one for SIZE encryption, another for the payload).

-- 
Sergey Matveev (http://www.stargrave.org/)
OpenPGP: CF60 E89A 5923 1E76 E263  6422 AE1A 8109 E498 57EF