[Cryptography] Non-deterministic PRF as a MAC-and-Nonce for AEAD?

Jason Cooper cryptography at lakedaemon.net
Mon Jun 4 09:43:04 EDT 2018

Hi Alfie,

On Sun, Jun 03, 2018 at 02:28:57PM +1000, Alfie John wrote:
> On Mon, May 21, 2018 at 12:37:13PM +0000, Jason Cooper wrote:
> > On Mon, May 21, 2018 at 09:26:52AM +1000, Alfie John wrote:
> > > Quick question on if this would work as a safe AEAD scheme:
> > 
> > It'd help if you define "safe" and "AEAD" ;-)
> > 
> > >   If you use a non-deterministic PRF instead of a MAC when doing
> > > 	MAC-then-Encrypt, could the NDPRF be safely used as the nonce (or
> > > 	used to deterministically generate a nonce) to the cipher as it
> > > 	should never be repeated given the same plaintext?
> > 
> > iiuc, which I'm pretty sure I don't, you're asking for a
> > non-deterministic PRF to *deterministically* create a nonce...-EPARSE
> Non-deterministic-deterministic functions is an oxymoron... i know :)
> What I was trying to do was think of a way to get rid of the IV/nonce as
> a parameter to an encrypt function call. I've seen code from many
> organisation where the coder didn't know what to use for the IV
> parameter, so they used the static values from examples copied from the
> docs or even forum examples. Give a coder a footgun, and they'll use
> it...

Honestly, if the coder doesn't know to ask a cryptographer, or security
engineer when they encounter nonce generation for an API, that's an
education / experience problem.  A good manager should ensure the junior
coder is either a) not going near crypto, or b) is closely supervised by
an experienced crypto/security engineer when touching crypto.

I originally had written my response as a proposal for a thin
abstraction layer that handles nonce generation for the coder.  But this
is ultimately a security fail.  nonce generation is highly dependent on
the environment (entropy, counters, etc) and the use case.  There's
simply no secure way to abstract it away for all usecases.

> So my thinking was to use a probablistic PRF when generating the MAC,
> and overloading the MAC as a Subliminial Channal to generate the nonce.

In past cases where I've used AEADs, I've used either the output of HKDF
or some randomness as the first nonce, and then just incremented it for
each subsequent encryption call.  (chacha20-poly1305-ietf permits
counter-type nonces [1])

With regards to your proposal, I stand by my original response.  The
nonce is an *input*, the MAC is an *output*.  There's simply no way to
use the MAC as a nonce.

And, honestly, if you do figure out a way to implement this "Subliminal
Channal", it would introduce very serious security concerns.  The kind
of concerns that would only be alleviated by specifying the process
formally, publishing, and have cryptographers pound on it for five to
ten years.  I don't think the gains are worth the hassle.

The best / easiest solution to your problem isn't technical,
unfortunately.  It's human.  There's no substitute for experienced
developers mentoring junior developers while working in crypto and



[1] https://datatracker.ietf.org/doc/rfc7539/?include_text=1
	Section 4: Security Considerations
  "The most important security consideration in implementing this
   document is the uniqueness of the nonce used in ChaCha20.  Counters
   and LFSRs are both acceptable ways of generating unique nonces, as is
   encrypting a counter using a 64-bit cipher such as DES.  Note that it
   is not acceptable to use a truncation of a counter encrypted with a
   128-bit or 256-bit cipher, because such a truncation may repeat after
   a short time."

More information about the cryptography mailing list