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

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 18 Mar 2016 11:16:47 +0000

Bryan, all,

Removing my chair's hat, I wanted to point you to this work:

https://eprint.iacr.org/2015/059

(this is the full version of a paper that we published at Eurocrypt'12).

The relevance to your discussion below is that the paper presents formal
security models and constructions for symmetric encryption schemes which
are, amongst other things, "boundary hiding". Essentially, this means that
different sequences of ciphertexts are indistinguishable from one another,
in a strong and precisely defined sense.

The paper also deals with the fragmented decryption setting which may be
inherent in such a setting (depending on the characteristics of the
underlying network transport): ciphertext bits/bytes arrive, and the
decryption algorithm cannot tell ab initio when it has received a complete
ciphertext (since there can be no metadata to provide length information,
and an atomic ciphertext may have been fragmented over multiple network
packets during transmission).

The paper was inspired by SSHv2's attempts to hide length information,
make sequences of ciphertexts look like random bits, allow for fragmented
delivery, and provide cryptographic security. That didn't work out too
well for SSH in CBC mode, but the paper shows that a combination of
properties like this (and more) *can* be achieved efficiently.

I think it is relevant to the problem of metadata protection that you are
concerned with here.

The paper is not particularly easy to read, and so I'd be happy to offer
my services as an interpreter.

Regards

Kenny 

On 26/02/2016 16:39, "Cfrg on behalf of Bryan Ford" <[email-masked]
on behalf of [email-masked]> wrote:

>Hi Alex,
>
>On Feb 19, 2016, at 2:20 AM, Alex Elsayed <[email-masked]> wrote:
>> 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).
>
>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.
>
>> 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.
>
>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: "Salz, Rich" <[email-masked]>
Date: Fri, 18 Mar 2016 11:46:15 +0000

> https://eprint.iacr.org/2015/059

Is there any change you could come to the TLS WG at the IETF and summarize?

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 18 Mar 2016 12:20:42 +0000

>Is there any change you could come to the TLS WG at the IETF and

Unfortunately, I won't be in Buenos Aires :-(

Berlin, yes, but that may be too late.