Re: [openpgp] [Cfrg] streamable AEAD construct for stored data?

Watson Ladd <> Fri, 30 October 2015 12:30 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 3D2641B2B10 for <>; Fri, 30 Oct 2015 05:30:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=unavailable
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id NAubsKYQAK_6 for <>; Fri, 30 Oct 2015 05:30:47 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:400c:c05::22b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id B7A521B2B08 for <>; Fri, 30 Oct 2015 05:30:46 -0700 (PDT)
Received: by wicfx6 with SMTP id fx6so9546674wic.1 for <>; Fri, 30 Oct 2015 05:30:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=5dnSDYYfhPEJqMVug9Qcrxstj9vm97kmrba0GxlixO8=; b=GU1D2mWmDwFjJz32mQ8nwljavV9ZliJpLx9D4afVsH1/UABfC99XLdQ1o68uuZy+z/ i080LCRm+RV+uMmpr8ZVsLpXABhbq4yHWGLdybtStnUe5Azl4Gp0K9QyINpBuG9iKWS3 Xp/SL64VG7sx77mcSmT8eLalFlNdF+Yk5F3vqtSrKajInmnTEe/K1IHZtOyzHRGHxhs8 ggIqd4u7GrjDT7Ifz+UBD94SFS69bywu+A4SnWrxTF9No2XCgli5zZH4wXzwng2Vh4if Sr9Okt4XWQlgEmWli57uP08IyVRU5QZIgOD/Fx2imMMlloFhN6A1W0i80opcyG6D2o/j /dRg==
MIME-Version: 1.0
X-Received: by with SMTP id kp5mr8031876wjc.64.1446208245250; Fri, 30 Oct 2015 05:30:45 -0700 (PDT)
Received: by with HTTP; Fri, 30 Oct 2015 05:30:44 -0700 (PDT)
Received: by with HTTP; Fri, 30 Oct 2015 05:30:44 -0700 (PDT)
In-Reply-To: <>
References: <> <>
Date: Fri, 30 Oct 2015 08:30:44 -0400
Message-ID: <>
From: Watson Ladd <>
To: Natanael <>
Content-Type: multipart/alternative; boundary=047d7b622670babff30523519828
Archived-At: <>
Cc: IETF OpenPGP <>,, Daniel Kahn Gillmor <>
Subject: Re: [openpgp] [Cfrg] streamable AEAD construct for stored data?
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 30 Oct 2015 12:30:50 -0000

On Oct 30, 2015 8:25 AM, "Natanael" <> wrote:
> Den 30 okt 2015 11:01 skrev "Daniel Kahn Gillmor" <>et>:
> >
> > Hi CFRG folks--
> >
> > We're looking into fixing the OpenPGP symmetrically-encrypted data
> > formats for RFC4880bis.  The structures are used for mail messages but
> > also for large file encryption.  It's clear that the OpenPGP CFB mode
> > isn't designed to modern symmetric encryption standards, so we're hoping
> > to introduce a better approach.
> >
> > We need, among other things to address integrity protection in a more
> > meaningful way than the current OpenPGP MDC (modification detection
> > code), which is basically a SHA-1 hash of the cleartext.  This was never
> > much better than a band-aid.  And as discussed in the recent "OpenPGP
> > SEIP downgrade attack" thread, an "integrity-protected" packet with an
> > MDC can be stripped down to produce a syntactically-valid packet without
> > integrity protection.
> >
> > But one of our constraints is the OpenPGP use case that streams
> > decrypted data, like this:
> [...]
> > This approach still has two notable problems i can see, which may or may
> > not be addressable (but if they are, i'd love to hear it):
> >
> >  a) it doesn't deal with truncation -- the initially-streamed data has
> >     already been streamed by the time a truncation is discovered.
> >     (there may be no way to fix this; it seems kind of like a fact of
> >     nature, and if so, systems should only do streaming decryption if
> >     they're capable of coping with truncation)
> Does it help to define the ciphertext length and check that first, before
decrypting? Doesn't help if the file isn't local and the connection is
broken, but then at least your software should detect that and halt of
> >  b) it doesn't seem to compose as well with asymmetric signatures as one
> >     might like: a signature over the whole material can't itself be
> >     verified until one full pass through the data; and a signature over
> >     just the symmetric key would prove nothing, since anyone getting the
> >     symmetric key could forge an arbitrary valid, decryptable stream.
> >     Is there an intermediate approach that would combine an asymmetric
> >     signature with a chunkable authenticated encryption such that a
> >     decryptor could stream one pass and be certain of its origin (at
> >     least up until truncation, if (a) can't be resolved)?
> >
> > Thoughts, pointers, or suggestions would be much appreciated.

Use authenticated encryption so no signatures are required. Detached
signature verification is used for large public messages already: no
streaming needed.
> To solve B what you need to do is something like signing a list of
ciphertext hashes/authentication tags.

The idea below demands conditions beyond MAC security.

> One thought I've had before (my idea is to use it for FDE*) is to for
example use HMAC over segments (including counters) or to extract AEAD tags
(prefixed with counters to preserve order) and create a Merkle tree hash of
those lists when creating the message, to then sign that Merkle tree, such
that when you decrypt and recreate the tags for comparison you can confirm
that nothing has been modified (with the level of assurance that the tags
can provide). Or you skip the standard AEAD and MAC constructs and use a
signed Merkle tree hash of the ciphertext itself as your own custom MAC.
> One benefit of using a hash-tree like algorithm with a signature is the
reduction of storage overhead and memory usage, and that you retain the
ability to independently verify each segment. Ideally you would use a
hash-tree like algorithm which also can be generated efficiently in a
single pass over even large ciphertexts with reasonable memory usage (does
anybody know of one?).
> Not that I've also read the referenced Tahoe-LAFS link, it looks like
they're doing something very close to what I described above, but slightly
> They use AES-CTR over the whole file with a unique key, one plain hash
over the entire ciphertext, one Merkle tree hash over the ciphertext blocks
and one Merkle tree hash over the erasure coded shares of the blocks, if
I'm reading it correctly, with all three hashes stored in plaintext with
the shares and then hashed together (also including the length of the
file). They also have some sort of hash chain, but the graphics don't load
and I can't figure out how exactly it is applied, beyond potentially having
to do with confirming the order of blocks. Instead of using HMAC they use
double SHA256 in a particular format.
> Minus the erasure coding** and with an added signature of the file
hashes/header, that's almost exactly what I imagined, I'm just worried
about the risk of the performance penalty limiting adoption. If the
performance of this method is considered acceptable or can be improved to
an acceptable level, I definitely support using it.
> * A bit off topic here, but for FDE I imagine changing the encryption key
every write-session using a KDF and session counter, keeping an
authenticated encrypted list of which segments uses which session write
keys. This way you prevent partial ciphertext reversal and prevent
detection of when ciphertext segments repeat over time (re-zeroized or
restored files). You can also arbitrarily re-encrypt random segments to
obscure your real write patterns (and reduce the list size occasionally by
purging unused keys after re-encrypting the last segments using them).
> ** In Tahoe-LAFS, erasure coding of blocks is used to allow you to split
files across storage nodes with minimal risk of data loss. That's not
applicable here, as it can be applied independently when considered
> _______________________________________________
> Cfrg mailing list