1
$\begingroup$

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

Detailed Scenario:

Imagine a chat application where two people, Alice and Bob, are sending messages -- each with the agreement to delete any messages received 7 days after they are sent. And let's assume that some attacker is recording all of the encrypted communications between them. The goal is to prevent an attacker who compromises a phone from getting more than 7 days of messages, either from the phone, or using any copy of a key on the phone. Protecting against this requires both Alice and Bob to do two things:

  1. Encrypt each message with a different key
  2. Delete each message after 7 days
  3. Also delete the key used to decrypt the message after 7 days

If they don't delete the key, then when the attacker compromises the phone, they can decrypt any previous messages from their historical record of the encrypted communications.

Partial Solution:

One way this could be done is for each side to publish a new asymmetric public key every day, with the promise that "any message encrypted to this public key (for me to decrypt with its corresponding private key) will be deleted, along with the private key used to decrypt it, on YYYY-MM-DD". So, each side would receive the updated key every day, and encrypt messages to that public key (or more likely, use that public key to encrypt and deliver an ephemeral symmetric key used for all messages in that 24 hour range). So long as both sides deleted their message after 7 days, and the recipient deleted their copy of the private key for that day (along with any ephemeral key), then forward secrecy would be maintained: compromising a device would only reveal at most 7 days of messages.

Problem:

The problem with that solution is it requires both sides to be in constant communication, in order to receive a daily key update from the other side. If Alice were to go offline for, say, a month, then Bob wouldn't know which of Alice's public keys to encrypt a new message with.

Solution / Question:

Which brings me to my question:

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

This is easy with a symmetric key: if you have the key for N=1 in the sequence, both sides can apply the same hash function, and generate the key for N=2 in the sequence. I'm wondering if there is any equivalent for asymmetric keys, where:

  • Alice applies a one-way hash function to Alice's private key for N=1, to generate a private key for N=2
  • Bob applies a one-way hash function to Alice's public key for N=1, to generate a public key for N=2

If so, then both Alice and Bob could anticipate what key will be used for any future date by both "advancing" their side of the asymmetric keypair, even if they lose contact with the other side for extended periods of time.

Thanks!

PS: I'm aware there are other ways to solve this, such as by having each side publish a pool of "pre-keys" that are allocated out as necessary. I'm specifically asking about if there's any way to directly ratchet both the public and private key.

$\endgroup$
1
  • $\begingroup$ In the Partial Solution, "each side would receive the updated key every day" can be eased slightly: if we want safety for messages older than T (e.g. the 7 days in the question), (a) if the participants exchange messages bidirectionally, it suffices that they communicate more often than T (b) if unidirectional (e.g. email) with a delivery delays D<T, we can reneew keys with any period less than T-D. $\endgroup$ – fgrieu Feb 27 at 7:28
2
$\begingroup$

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

Here is one way, based on elliptic curves (or finite field based on discrete logs); one such public key encryption method is the Integrated Encyption Scheme. Now, it does have the drawback that if the attacker learns a prior public key, he can then (with knowledge of the current private key), he can learn the prior private key. However, this limitation may still be acceptable to you.

In such a scheme, there is a private key (which is an integer $p$ in the range $[0, q)$), and the public key is a point $P = p \cdot G$ (where $\cdot$ is point multiplication if you're using elliptic curves, and exponentiation, more commonly written as $G^p$ if you're using a finite field group).

To ratchet the key forward, the two sides would compute:

  • Private key: $p' = hash(P) \times p \bmod q$
  • Public key: $P' = hash(P) \cdot P$

(where $hash$ is a cryptographic hash function).

This works, in that the relationship between the new public key $P'$ and new private key $p'$ still holds; $p' \cdot G = hash(P) \times p \cdot G = hash(P) \cdot P = P'$.

In addition, it is ratcheting; given $p'$, you cannot recover $p$ without knowing the hash of $P$ (and we assumed that he doesn't know that)

$\endgroup$
8
  • $\begingroup$ Thank you for the incredibly fast and helpful explanation! $\endgroup$ – quinthar Feb 27 at 3:17
  • $\begingroup$ @qinthar: be sure to weight the limitation: w.r.t. the goal of confidentiality of old messages if current private key leaks, it becomes unsafe to make public keys public, if we assume that what's public gets publicly archived, or adversaries know they are adversaries in advance. $\endgroup$ – fgrieu Feb 27 at 7:46
  • $\begingroup$ Yes, that's a tricky constraint I won't deny. I'm trying to see if I can find a way to make it work. Can you think of any other solution that doesn't have this constraint? $\endgroup$ – quinthar Feb 27 at 18:35
  • $\begingroup$ @poncho I'm sure this is obvious to others, but can you explain how you calculate a previous private key given a previous public key and future private key? I believe you, I just don't quite understand how to do it. $\endgroup$ – quinthar Feb 28 at 22:48
  • $\begingroup$ @quinthar: if you have the previous public key $P$ and the current private key $p'$, then the previous private key $p = p' \times hash(P)^{-1} \bmod q$; that is, multiplied by the modular inverse of $hash(P)$ $\endgroup$ – poncho Mar 1 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.