[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