Is perfect forward secrecy (PFS) possible without public key cryptography

Question

I have an understanding of PFS as used in most key agreement algorithms as well as things like TextSecure protocol and ratchets. My undestanding is that PFS is not possible without asymmetric (public key) cryptography. Am I missing something? Can PFS be achieved with symmetric cryptography and preshared keys only.

Answer 1

Yes, perfect forward secrecy is possible using symmetric primitives alone.

Take for instance a set of one time pads:

1. Alice generates two identical stacks of one time pads and hands one of the stacks to Bob.
2. Alice encrypts a message with the first one time pad and then passes the ciphertext to Bob.
3. Bob decrypts the message with the first one time pad and then both Alice and Bob destroy the first one time pad. So long as all copies of the one time pad are destroyed the ciphertext is now undecipherable.
4. The next message is passed using the second one time pad and at the conclusion of that protocol round all copies of the second one time pad are destroyed. And so on.

This basic protocol achieves perfect forward secrecy.

Of course it's likely not a practical protocol for many applications as, for instance, it requires secure advance exchange of a set of one time pads and the message length is limited by the length of a one time pads which much be agreed in advance. Nevertheless you can start from this model and apply some basic cryptographic improvements such as:

• replace each one time pad with a key and a stream cipher so now we just need to exchange a set of keys
• replace the set of keys with a single key and a one way function to obtain the next key so now we just need one key (and of course you simply destroy the previous key each time you derive the next key).

It's not difficult obtain a relatively practical scheme assuming pre-shared keys. The security of this construction is not too difficult to bound (How secure is the stream cipher? How secure is the one way function?).

Answer 2

Yes, If in case your derived keys are not calculated from previous key. If you use a randomly generated key everytime, that would still gurantee PFS

Answer 3

I have designed a protocol that tries to achieve PFS using ephemeral Diffie-Hellman key exchange, symmetric key cryptography, and hash function. Please check the attached image

Edit: $R_A$ and $R_B$ are Alice's and Bob's nonces respectively. $K_{AB}$ is a shared symmetric key between them, '$a$' and '$b$' are their respective chosen exponents, and '$g$' and '$p$' are publicly known. $h$ is the hash function.

Here, after step 3, a session key would be generated and Alice and Bob will continue using their session key until the session ends.

P.s.: I would be happy to get corrected on this answer.

Answer 4

Technically no....

Diffe-Hellman isn't a public key algoritm but it does allow for key exchange. It is acually what is used in PFS... Public-key is not used to establish shared keys.