12

In the Scouts, it is popular to use secret codes to write messages (which are simple ciphers).

I want to introduce Forward secrecy to the kids so they can use it with these ciphers. So, if the competing team found a ciphered message and decoded it successfully they can't decode old messages too.

My question, how can I do any of these simple ciphers with forward secrecy?

Rory Alsop
  • 61,367
  • 12
  • 115
  • 320
ScoutHelper
  • 131
  • 2

2 Answers2

19

What you describe is not forward secrecy.

Forward secrecy relates to the following property: a secured communication took place between entities A and B at some time T; the attacker recorded all the messages; at some later time T' the attacker obtains a copy of all the secret keys known to A and B; and yet, the attacker cannot recover the contents of the communication which occurred at time T. To achieve forward secrecy, then the following must hold:

  • Each communication (say, each individual message in a mail context) uses a specific encryption key that sender and recipient do not keep around. This necessarily entails some generation mechanism, with randomness.
  • It does not support stateless one-way emailing. Indeed, if the complete communication between two scouts is a single message from scout A to scout B, then this means that B "knows enough" to process the message and recover the contents. Unless B forces himself to forget what he once knew (i.e. is not stateless), B could do this feat again; and so can the attacker if he obtained all of B's secrets.

If two-way communications are possible (e.g. as with a SSL connection, with the initial handshake), then a key exchange algorithm like Diffie-Hellman can be used to produce a communication-specific session key, used only for the duration of the connection, and discarded afterwards. Any long-term secret known to both scouts will be used only for mutual authentication.

Since scout messages are one-way, and the average scout won't compute a 1024-bit DH key exchange anyway (he could: all these youngsters nowadays have smartphones, which are entirely up to the task; but I understand that is not the pedagogical point), this kind of solution cannot be used.

Instead, the solution is to make the scouts stateful. The model, here, is that of the One-Time Pad: make it so that sender and receiver share a long sequence of secrets, which they store on some physical medium such as a booklet. When they use a key (say a booklet page) for sending or receiving a message, they destroy it. Therefore, an enemy seizing the booklet after the fact will not obtain the key, and thus won't be able to decrypt a past message.

This is the historically correct solution; in the pre-computer era, field agents used OTP. Scouts can only be thrilled by using the exact same method as real spies and armies used for decades. Extra points for making the booklet in an edible material, so that destruction after usage is fun, easy and safe (the average scout would also find it quite fun to simply burn down the paper, but that might create environmental hazards). Further extra points for walking the scouts through cryptanalysis when OTP was badly used, i.e. the pad has been reused.

Forward secrecy is about what happens when a field agent is seized by the enemy, and forced to reveal his secrets. The scenario you envision is different: no secret forcibly revealed, but a passive decryption which occurred in an unspecified way (e.g. a lot of guesswork from a partially known plaintext). The property you describe (decrypting one message does not reveal other messages) only means that the encryption method is robust against known-plaintext attacks: even knowing some cleartext and the corresponding ciphertext is not enough to enable decryption of other ciphertext, and, in particular, is not enough to rebuild any keying component which is reused for other messages.

Pen-and-paper ciphers are usually weak, although some can be quite strong when the attacker only has a pen and paper too. See this question for suggestion and links.

One-Time Pad is the exception: it is computable with very low computing power, and yet is ultimately robust against known-plaintext attacks, because no employed keying component is reused for another message or message part.

Summary: use OTP. It provides the property you want; it also provides forward secrecy. It is pedagogical, and amenable to enlightening historical reconstruction.

Community
  • 1
Tom Leek
  • 168,808
  • 28
  • 337
  • 475
  • 2
    mmmm. OTP cookies. the code is the number of chocolate chips. – Rubber Duck Jan 14 '14 at 14:11
  • Hmm, why couldn't scouts do a difi-hellman key exchange? It isn't actually all that hard to calculate require only raising to the power and modulo other than the initial random integer generations. – ewanm89 Jan 14 '14 at 19:40
  • 1
    @ewanm89 It gets rather tedious doing it by hand for 1024+ bit parameters. – Thomas Jan 14 '14 at 21:19
  • Agreed but who said scouts needed 1024 bit security, as a learning tool it wouldn't be bad. I doubt they are using something like AES at the moment. – ewanm89 Jan 14 '14 at 21:21
  • 1
    At least the scout should end up, after the key exchange, with a key which can be broken through exhaustive search by a bored scout, otherwise he may fail to see the point. This means working with at least a three-digit modulus. I doubt many scouts may relish the prospect of doing a dozen hand computations on 3-6 digit integers (6 digits after multiplication, then modular reduction). The whole thing should remain _fun_. – Tom Leek Jan 14 '14 at 21:43
1

Yes.

I think that you are using symmetric keys with your scouts, that is, the same key is used to encrypt and decrypt the encrypted message.

Forward Secrecy would be achieved if:

a) Both parties (sender and receiver) contributed to the key generation b) Both parties agreed to contribute something which they can guarantee would not be used again...

So the scout leader might contribute: "22" and the scout would contribute "33" making the key "726" (22*33). It would be ideal if neither party knew the contribution of the other.

Edit:

Of course this scheme is not perfectly secure, the idea is to reach kids about Perfect Forward Secrecy, and it's goals:

  1. Both sender and receiver participate in the key generation
  2. The key is only used once, making knowledge of the key only useful for decrypting a single message
  3. The underlying encryption algorithm is unchanged and independent of PFS, the goal is to achieve better security regarding the key, and its eventual compromise

Worked Example: As above, the sender contributes "22", the recipient contributes "33", generating a "session" key to be used for this and only this message of "726". Using the "Numbers Stand For Letters" algorithm which is in your original link you create a simple substitution:

A B C D E F G H I ...
7 2 6 1 3 4 5 8 9 ...

(I chose to remove 726 from the set, but that is not, strictly speaking, necessary...)

The idea is not to achieve any effective cryptography, the idea is to let kids have fun and learn about the advantages of using an ephemeral key, and both parties contributing to the key.

An OTP is not a valid example of perfect forward secrecy because the key is generated by the sender without participation of the recipient. The recipient must simply trust the sender to have generated the key correctly.

RQ'
  • 76
  • 6