[Cryptography] AEAD modes for signed ciphertext
Ned Ulbricht
nedu at netscape.net
Mon May 11 17:45:48 EDT 2015
I am looking for resources to help with a specific problem. In
particular, I'd appreciate pointers to papers, security proofs,
specifications and/or implementations that would throw light on this
specific problem.
I'm sorry about the length of this email post. I have organized it as
follows: In this intro, I apologize for the complexity of the problem,
but offer that the devil is always in the details. Then in part 1, I
partially sketch a communications system, which contains a cryptosystem
as one of its components. Part 2 describes the embedded cryptosystem
with a tiny bit of detail. Part 3 hand-waves an attack on that
cryptosystem. In part 4, I outline some of my preliminary thoughts on
countering that attack. Then, finally, in conclusion I repeat my
request for help with this problem.
Part 1: Partial sketch of the communications system
The communications system is a greenfield design for an asynchronous,
store-and-retrieve messaging system. I am sketching just enough of it
to provide necessary context for the cryptosystem.
In this communications system, receivers must pre-approve senders before
messages from that sender will be relayed to the receiver. The
whitelisting is initiated through outside channels, when a potential
sender (alice at foo.example) exchanges her user-readable "tofu tag" with a
potential receiver (bob at bar.example). Within the communications system,
Bob then uses Alice's "tofu tag" to locate Alice's directory server and
her directory entry. Having Alice's directory data in hand, Bob commands
his message relay server to accept and store messages from Alice.
Without this pre-approval, the relay will reject messages.
To send Bob a message, Alice uses Bob's "tofu tag", looking up Bob's
communication parameters from Bob's directory entry. Those parameters
include the designation of Bob's relay server, where Alice drops off her
message. Bob must initiate contact with his relay in order to pick up
any messages stored there.
Part 2: The end-to-end cryptosystem
The boundary between the overall communications system context, and its
cryptosystem component is not a clean, modular separation. Rather, what
I am calling "the cryptosystem" is merely what I shall describe with a
teensy bit more detail. Notably, "the" cryptosystem is not the only use
of cryptography in this communications system--I have omitted some
irrelevant cryptographic subsystems for brevity's sake.
The cryptosystem has a number of goals: Those goals are end-to-end
message confidentiality, integrity, authenticity and authorization.
Also, along the way, the cryptosystem authorizes use of the message relay.
The cryptosystem is hybrid, composed of standard building blocks: It
uses both asymmetric (public-key) and symmetric encryption, as well as
off-the-shelf hashes, padding, and modes for assembling the building
blocks into a coherent whole. Further, the communications system
supports crypto algorithm agility (and full buzzword compliance, too!),
so I shall not provide excessive detail on the exact cryptographic
primitives employed. All the same, it is expected that users will
default to a single crypto suite, and my focus here is on the top-level
crypto architecture for that suite.
Sub-part 2A: Userids for principals
In part 1 above, I referred to senders and receivers by their "tofu
tags" (alice at foo.example and bob at bar.example). Those are what end users
see. The cryptosystem internally identifies principals by hashes of
their long-term public signature keys. A directory server certifies
that a "tofu tag" in its domain maps to a public signature key hash, at
the time when the directory is queried. Following that initial query,
the cryptosystem stores and uses the hash as a userid.
The mis-match between the human-readable "tofu tag" seen in an
end-user's address book, and userids internal to the cryptosystem may
cause the end-user to fail to grasp the security guaranteed by the
cryptosystem--as well as the security NOT guaranteed. While no effort
is made to hide userids, in practice, the chance that users will
understand, compare or exchange their userids ranges from slim to
laughably absurd.
Sub-part 2B: Outer message wrapper for authorization
Authorization for messaging is checked in two places: first, at the
receiver's message relay, and second at the receiver. Because these two
checks are the same, I describe only the authorization check at the relay.
When Bob wants to authorize Alice to send him messages, he adds Alice's
userid to a list stored on his relay server. When Alice connects to
Bob's relay with a message for him, she must transmit everything else
needed for the relay to check her authorization.
More specifically, Alice transmits to Bob's relay: Bob's userid as
intended message recipient, a message datestamp, a blob of ciphertext
and associated data, a signature certificate, various formatting and
padding, and an outer signature which covers all the preceding items.
Signatures are stock constructs, conventionally composed from padding,
hash and asymmetric primitives. However, Alice does not create the
outer message signature directly with her long-term private/public
keypair. Instead, Alice employs a shorter-term, intermediate, signing
keypair. The public key of her shorter-term pair as well as the public
key of her long-term pair, along with the signature suite version, are
all provided in a certificate signed by Alice's long-term keypair. This
transmitted signature certificate provides a verifiable chain from the
outer signature up to Alice's userid.
The relay decides authorization from the chain, comparing a userid
computed from the transmitted certificate to its stored list of Bob's
authorized-sender userids. If the computed userid is not authorized, or
if the signature chain fails, then the relay rejects the message. If
Alice's userid is authorized, and the chain is valid, the relay stores
all the transmitted items for Bob to pick up later.
Sub-part 2C: Encrypted message and associated data
End-to-end message confidentiality is provided by a hybrid composed of
asymmetric and symmetric encryption. The primitives are all standard
ones. The composition modes though, may or may not be typical, as here
is near where the problem lurks. But I am getting ahead of myself.
The additional data associated with the ciphertext specifies the
algorithms used to encrypt the message, and indicates which one of Bob's
public encryption keys Alice encrypted to.
To round out this section, let me quickly note that in part 1, where I
said that Alice uses Bob's "tofu tag" to obtain his communication
parameters, that was not entirely accurate in complete detail. Instead,
as you may guess, after the initial lookup, Alice's address book stores
Bob's userid. However, the exact process of subsequent parameter queries
seem irrelevant to the problem at hand, so I shall omit it. Anyhow,
Bob's parameters should be stable enough that Alice may cache them for
some time.
In Bob's directory server's responses to both initial and subsequent
queries, Bob's public encryption key and other communication parameters
are certified through a chain which culminates in his userid. (As I
mentioned in part 1, Bob's userid is further bound to his
bob at bar.example "tofu tag" by the authority of the directory server at
bar.example.)
Thus Alice has some bit of confidence that she has obtained Bob's public
encryption key and is encrypting her message with agreed ciphers and modes.
Part 3: Signature substitution attack
The cryptosystem that I have partially sketched out in part 2 above, is
vulnerable to a classic signature substitution attack.
Suppose that Mallory (mallory at baz.example) is another one of Bob's
authorized senders. If Mallory obtains one of Alice's messages to Bob,
then Mallory may strip off Alice's signature, and create his own
signature for that message, even though he is unable to read the
encrypted ciphertext. Bob will then accept Alice's message as one
generated by Mallory.
In short, the outer message signature may guarantee authorization, but
fails at authenticity.
It gets worse. After Mallory has stripped off Alice's outer signature,
he may alter the ciphertext or associated data before creating his own
outer signature. That might provide a springboard for other attacks.
Thus, in some sense, the outer signature also fails to assure message
integrity.
Note that I'm handwaving just a little bit over exactly how Mallory
intercepts Alice's message to Bob. Recall that I have only partially
sketched out "the" cryptosystem, and there do actually happen to be
other, unmentioned cryptographic barriers for interception in transit.
Yet, after all, Mallory might be in control of Bob's relay server.
Part 4: Preliminary thoughts on countermeasures
The simplest countermeasure for a signature substitution attack is to
have Bob somehow recognize that the message's decrypted plaintext
obviously was generated by Alice, and therefore Mallory's outer
signature only indicates an attack underway. That solution seems less
than satisfactory, though.
My latest thinking on the problem tends towards computing a separate MAC
(MIC) for the ciphertext and associated data. This is motivated by my
current gravitation towards AES in CBC mode as the symmetric part of the
default confidentiality suite.
My previous thinking considered automated validation of decrypted
plaintext as a very desirable feature. Thus, solutions as simple as...
never mind. I could go on for pages, but I'll stop right here.
Conclusion: Request for help
In a perfect world, someone here on this list would point me to an
open-source Super-Whizbangomatic v.42, that does exactly what I want, as
well as providing all the additional features that I have left out of
this overly-long post.
Short of that perfect world, though, I am looking for previous work
which will throw light on the specific problem that I have focused on.
That is, I am looking for research papers, security proofs,
specifications, or source code which illuminate approaches to providing
authenticity and integrity for encrypted messages and associated data,
when the ciphertext and data is wrapped with an outer signature.
Lastly, I would also welcome most other remarks or criticism that anyone
has about this architecture. I shall warn people that if their remarks
or questions stray too far afield from the specific problem I have
focused on, that may prompt me to write quite a bit more, fleshing out
and inflicting further details in response.
--
Ned Ulbricht
mailto:nedu at netscape.net
More information about the cryptography
mailing list