suppose there is a router with limited storage but good network connection; it could be a good worker for deterministic authenticated encryption on streams; that means it receives data from another machine, encrypts and sends it back; however, siv algorithms need to calculate iv over the entire plaintext before that iv is usable in the encryption; that is a two-pass algorithm;

there are stream-able mac and encryption algorithms; but the stream does not come back again; and the router has too limited storage to buffer the entire stream; this effectively means the algorithm needs to be one-pass; are there any known solutions to this problem?

  • $\begingroup$ Is the length of a message (in bytes) known at the start of its transmission (or at least a range of possible lengths)? $\endgroup$ – SEJPM Dec 7 '19 at 19:21
  • $\begingroup$ @SEJPM currently no; seems the only way to know its length is to consume the entire stream, which is unacceptable; but result with known length is also welcome; $\endgroup$ – Cyker Dec 7 '19 at 19:41

It is impossible for a one-pass algorithm to achieve the highest nonce-reuse security notion which only leaks equality of messages because the first few bits can't depend on the last few bits.
The best one could hope for is that the length of common prefixes between any two pairs of messages is leaked on nonce-reuse. One can strengthen this to only leaking the length of common prefixes for equal-length messages by prepending the message length before encryption.

If you want to achieve this strongest one-pass security notion, you can't use a paralellizable encryption algorithm because each bit / block has to depend on all previous ones which by definition is not possible for parallelizable schemes.

As for MACs, if you use a PRF-based MAC, like AES-PMAC (which is parallelizable) or AES-CMAC you should get plenty of robustness to nonce re-use, as these are deterministic MACs to begin with.

As for encryption, all the fancy modes are out of the question and I think the best bet you have is actually CBC. This is due to the fact that CBC does block-by-block processing which reduces the accuracy of the "common prefix" to number of totally equal blocks which should prevent an adversary from using an attack that guesses a small amount of bits at once until they get a longer shared prefix to recover a message as the smallest group for this would be 128 bit.

So in total, the best option you probably have is to use (AES-)CBC-then-PRF with AES-PMAC or AES-CMAC as PRFs.

  • $\begingroup$ i agree single-pass and determinism together cause a prefix problem, namely the prefix in ciphertext is correlated to the prefix in plaintext; $\endgroup$ – Cyker Dec 8 '19 at 12:33
  • $\begingroup$ In "Cryptographic Sponge Functions" by the Keccak team, section 4.1.4, the authors defined a "SpongeWrap" mode of operation for permutations that is a single-pass authenticated encryption that doesn't need a nonce; although, subject to the constraint on plaintext (and the "header") that initial prefix duplication could leak information about the ciphertext, which is true of any single-pass encryption. $\endgroup$ – DannyNiu Jul 22 '20 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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