Subject: Re: [Cfrg] Discuss/standardize Preview extension to AEAD abstraction?

From: Alex Elsayed <[email-masked]>
Date: Fri, 19 Feb 2016 07:20:59 +0000 (UTC)

On Fri, 04 Dec 2015 11:53:02 +0100, Bryan Ford wrote:

<major snip>

Apologies for the (very!) late reply, but was off-list for quite a while.

> Is there anything seriously
> problematic or unsound from a crypto perspective about such an APEAD
> interface extension or feature, aside from the well-known risks
> associated with any use of (“previewed”) data before it’s been
> integrity-checked?

One particular problem is that APEAD is hard-incompatible with MRAE - in 
order for an AEAD to satisfy MRAE, every bit of the ciphertext must 
depend on every input bit from (nonce, ad, pt). As a result, "previewing" 
some prefix is infeasible for the exact same reason as MRAE and "online" 
AEAD being disjoint (Hoang, Reyhanitabar, Rogaway, and Vizar have a 
fascinating paper on this - https://eprint.iacr.org/2015/189).

However, this does leave some options regarding length-hiding on the 
table.

For one, given an AEAD based on the encode-then-encipher paradigm with 
variable \tau, one can increase the length of the verifier arbitrarily. 
This permits essentially padding each message to any extended length and 
gaining that length as additional integrity protection.

---

From: Bryan Ford <[email-masked]>
Date: Fri, 26 Feb 2016 11:39:57 -0500

Hi Alex,

> fascinating paper on this - https://eprint.iacr.org/2015/189).

That concern occurred to me as well.  But in subsequent discussion with Philipp (co-author of one of the recent misuse-resistant schemes - https://eprint.iacr.org/2015/999), we realized that it *is* possible to create an APEAD scheme that’s also misuse-resistant.  

But we also realized that for some of the purposes motivating the APEAD property - particularly hiding sequence numbers in out-of-order transports such as DTLS or IPSEC - just using a misuse-resistant scheme and transmitting the sequence number inside the encrypted payload presents a reasonable and perhaps conceptually simpler and cleaner alternative to the APEAD approach.

> gaining that length as additional integrity protection.

I’m not sure I follow the details of this suggestion - but definitely agree that in general that there are several reasonable approaches to length-hiding, with or without the APEAD property.

Cheers
Bryan

> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Alex Elsayed <[email-masked]>
Date: Mon, 29 Feb 2016 18:14:30 +0000 (UTC)

> On Feb 19, 2016, at 2:20 AM, Alex Elsayed <[email-masked]> wrote:
<snip>
>> This permits essentially padding each message to any extended length
>> and gaining that length as additional integrity protection.
> 
> I’m not sure I follow the details of this suggestion - but definitely
> agree that in general that there are several reasonable approaches to
> length-hiding, with or without the APEAD property.

Basically, for encode-than-encipher MRAE (such as AEZ), encryption works 
in two stages - encode (in AEZ, padding with a 1 bit followed by 0 bits) 
and encipher (actually running AEZ/AEZ-tiny on the encoded plaintext).

The cool part is that, due to MRAE's property of depending on every bit 
of the input, one can exploit any structure in the plaintext to increase 
the effective bits of integrity protection - including the structure of 
the padding.

As a result, every extraneous bit of padding used beyond the necessary 
is, in effect, an additional bit of MAC, with *no upper limit* - 
permitting length-hiding-by-padding that has the beneficial side effect 
of increasing integrity protection.