Offline authenticated encryption for pub/sub

Question

Requirements:

• only publisher can create messages
• publisher & subscriber can both read messages and authenticate the publisher
• offline message transfer
• messages can't be read by non-participants
• subscribers can be mobile platforms (Android, iPhone), i.e. less powerful processors
• messages lifetime target is 15 years
• messages are small, a few dozen bytes

I was looking at ECIES with ECDSA but I cannot seem to find a reference using ECIES where the sender has the static key and the receiver is using an ephemeral key. https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme#Informal_description seems typical, but in my scenario Alice wants to send a message and have any of Bob and his friends read it and know that it is from her.

I know that RSA can do this by encrypting a message specific key using a private key and decrypting using the public key (waving hands over some details here) but the exact same construction doesn't seem to work with ECs. Is there an EC construction that has similar properties? I don't want mobile devices to have to suffer 4k RSA keys (to make them hopefully secure into the 2030s).

Answer 1

You need to sign your messages and then encrypt them (sign-then-encrypt). The signature generation is performed using the private key from the publisher (sender) and the encryption is performed using the public key from the subscriber (receiver). The decryption is performed using the private key of the receiver and the signature verification is performed by the public key of the sender. The private keys remain private, the public keys need to be trusted.

---

only publisher can create messages

Anybody can create messages, they are just bytes after all. Only the publisher should be able to create messages accepted by the subscriber.

publisher & subscriber can both read messages and authenticate the publisher

Encrypt not just for the subscriber but also for the publisher and you should be fine.

offline message transfer

Sure thing, but note that you may still have all the problems of a transport protocol. For instance, you could be vulnerable to padding oracle attacks if you encrypt using CBC mode.

messages can't be read by non-participants

Only the subscribers (receivers) and publisher would have the corresponding private keys, so yeah.

subscribers can be mobile platforms (Android, iPhone), i.e. less powerful processors

Neither of the schemes here would be troublesome for relatively low powered devices (if you can call the latest sets of smart phones "low powered" with 64 bit operations, hardware crypto accellerators and over 2 GHz clock speeds for the top and midrange models).

messages lifetime target is 15 years

15 years is a long, long time in crypto. But if you use 512 / 512 bit curves and 256 bit symmetric cryptography (256 bit AES, for instance) then your message should be secure for a long time, unless crypto-analysis using quantum computing takes off on a large scale.

messages are small, a few dozen bytes

An ECDSA signature at 512 bits is already 128 bytes minimum, and an ephemeral public key (needed for ECIES) would take around 64 bytes. A few dozen bytes seems a very small amount of available message space.

---

I know that RSA can do this by encrypting a message specific key using a private key and decrypting using the public key (waving hands over some details here)

No, it cannot. The public key should be considered public.

Answer 2

If you don't know ahead of time who all the subscribers are, simple public key cryptography is not going to work well, even if you can tolerate the expansion of the message to include the signature and an ephemeral public key. Even if you know all the subscribers that might need access for the next fifteen years, but there are a lot of them, it's not great. If you don't want to share the same private key with all of them, you would have to encrypt the message to each one of the subscribers' public keys, which would scale poorly as the number of subscribers increased.

An alternative is to use a proxy re-encryption scheme. Proxy re-encryption (PRE) is designed to allow the holder of a public/private keypair to delegate the ability to decrypt messages encrypted to her public key to someone else without giving that other person her private key. If you have a PRE scheme, you could create a keypair that represents the topic/message queue, and the publisher could encrypt each message to that public key. Then independently of that, you could delegate access to those messages to each of the subscribers (create a re-encryption key from the topic key to the subscriber key).

A benefit of this scheme is that if someone is subscribed to the topic, then subsequently unsubscribed, that subscriber can't decrypt any new messages published to the topic. A drawback is that a fair number of PRE algorithms use pairing-based crypto, which is pretty CPU-intensive.

A paper that describes a system based on PRE that would support this use case is available here. Disclaimer - I am an author of the paper and CTO of a company that is building a product based on the scheme. But the paper describes the use cases, how PRE works to solve them, presents the algorithms, and includes references in the bibliography to preceding works in PRE that are interesting. Sorry to steer you through our website to the paper, but that allows you to access it if you don't have access to the ACM Digital Library.