Spy stuff: symmetric crypto with forward secrecy

November 25, 2017 by Konstantin Ryabitsev

We're all impatiently waiting on quantum-proof asymmetrical crypto algorithms to become commonplace. Until that happens, we must all live with the assumption that all currently used asymmetric crypto will be trivially decryptable once quantum computers become powerful enough. This is probably the reason why government agencies have been wholesale logging all encrypted traffic -- doubtless it's done in hopes that eventually it can be decrypted and analyzed.

The only sure way to remain quantum-proof using today's technology is to use symmetric cryptography with good key sizes, but there are huge downsides when it comes to two-way communication using symmetric crypto:

you have to establish and exchange symmetric keys
if you reuse the same keys for multiple messages, the entirety of your conversation becomes known to the adversary if they get the encryption key (i.e. no "forward secrecy")
the encryption key can be obtained from you or your correspondent using coercion (a.k.a. "rubber-hose cryptanalysis")

I was pondering how I would go about devising a way to communicate online today that would address some of the above problems, but would also be:

cheap
practical
2-factor
offer forward/backward secrecy

What I came up with fits all of the above, but with the notable caveat that it is not scalable. It's a scheme that can be used between two secret agents, but not something that can be used by run of the mill internauts. Still, I hope it proves to be a fun read if you're a crypto-nerd. :)

The setup

You will need two devices capable of doing standard OATH-HOTP. They are extremely cheap and fairly commonplace -- in my example I will be using two original Yubikey Nanos (not the latest 4th gen stuff, but you can use those just as well). You can get them pretty much anywhere, in almost any country, and they are not generally controlled as crypto devices, even though they have a crypto chip. Certainly, finding a techie with a yubikey is not at all suspicious.

The goal is to configure two of these in an identical way. One would be given to Alice, and another to Bob.

Configuring the yubikeys

There are two "slots" on the yubikey where the pre-shared key can go. In my example, I will be configuring the slots in the following way:

Slot 1: key used to generate the long static password (always the same)
Slot 2: key used to generate changing 8-digit OATH-HOTP codes

While we don't absolutely need to use the static password key in slot 1, it's handy for giving our encryption key extra entropy that will be unrecoverable if the yubikey is destroyed, so why not use it?

Here are the commands:

$ unset HISTFILE
$ ykpersonalize -1 -ostatic-ticket -o-append-cr \
      -a7fd554b1e4a711155d20e9f9615b0451
$ ykpersonalize -2 -ooath-hotp -ooath-hotp8 -o-append-cr \
      -a7fd554b1e4a711155d20e9f9615b0451152db3bb
# Remove first key, insert the second, and repeat

What follows the -a are hexadecimal keys that will be used for AES operations inside the yubikey. In the example they are almost the same, but they don't have to be, though whether they are similar or not does not matter much for our needs.

You can generate your random keys on the system where you're doing provisioning, the 16-bit for the static key and the 20-bit for the HOTP key:

xxd -l 16 -p /dev/random
xxd -l 20 -p /dev/random

Do remember that they have to be the same on both yubikeys.

Using the yubikeys to generate symmetric encryption keys

So, now we have two yubikeys configured identically. Alice takes one, and Bob takes the other (and hopefully they don't have photographic memory good enough to remember the 16-bit and 20-bit keys loaded onto the yubikeys). Both of them also agree on an additional shared passphrase that they will use, let's make it "somethingiknow" in our example.

Now what?

HOTP protocol's purpose is to generate one-time passwords by performing a HMAC operation on the pre-shared key stored on the device and the keypress event counter. Normally, a user would press a button on the device, which will cause it to increment the internal event counter, and then perform a simple math operation to calculate the combined passphrase+counter HMAC. It is then truncated and represented as a 6- or 8-digit one-time code. HOTP is designed in a way such that knowing any number of previously generated one-time codes would still make it impossible to predict the codes generated in the future (or those generated in the past, which is equally important for our use-case).

We will be using this to generate one-time encryption passwords that would allow Alice and Bob to generate identical encryption/decryption keys without having to coordinate them with each other. Each encryption key will consist of:

The pre-shared phrase both agents know, "somethingiknow"
The long static password using the yubikey slot 1 (one "quick tap")
Three 8-digit codes using the Yubikey slot 2 (three "2-second taps")

If you're curious, starting with the HOTP counter at 0 and using the keys in the above examples, this will generate the following string:

somethingiknowlnrvntetfedgrgtfbhudrljbgrtrunjh475935282635905679326316

We can use more than 3 HOTP codes if we want to increase the key entropy. We don't want to use a single HOTP code because this would make the encryption key easily brute-forceable if Eve finds out about Alice and Bob's scheme and manages to get her hands on the yubikey (e.g. Bob didn't have time to flush it down the toilet).

Using 3 or 4 keypresses should make brute-forcing decryption unfeasible -- it will be cheaper (but still really expensive) to get the keys from the yubikey's crypto chip.

Avoiding key desync

One of the obvious downsides to this method would be if Alice and Bob's yubikeys become desynchronized. Say, Bob fumbles his key and accidentally fires off the HOTP keypress, therefore incrementing the counter by 1. If that happens, identical operations done by Alice and Bob will generate different encryption passwords and the scheme would break down.

This is one of the reasons why the HOTP code is in the 2nd slot, which fires only after 2 seconds of being touched continuously. Even with that precaution, accidental misfires will still undoubtedly happen, which is why the agents need to pass along their counter information to each-other with each message, in cleartext (remember, knowing the value of HOTP code does not give any useful information about the key, nor weakens future generated codes, so this is a safe operation).

Easiest would be for each agent to perform 5-6 intentional discards before each message, and then pass the HOTP code immediately preceding the encryption key generation to the other agent in cleartext.

For example, if Alice's counter is at 3 and she needs to communicate with Bob, she does several long keypresses to discard a few HOTP codes, and then uses the last one to pass it along in cleartext in the message to Bob, before using the following 3 HOTP codes as part of the encryption key.

When Bob receives that message, he locates the HOTP code in cleartext and discards his own HOTP codes until the one returned by his key matches the one in cleartext from Alice. He now knows that the next 3 HOTP codes will be the ones used by Alice to generate the encryption key. This scheme allows the agents to synchronize their keys before each decryption -- as long as the HOTP counter desync between the keys remains minor (as would be expected from accidental keypresses).

Example with GnuPG

We assume that both Alice and Bob use an amnesiac system like Tails for their communication. If Alice needs to send Bob a message, she would boot up Tails, write out the message into message.txt and then perform the encryption operation (first discarding a few tokens for the reasons mentioned above, until she gets to 51951508, which she sticks into the comment field of the PGP header):

$ echo "somethingiknowlnrvntetfedgrgtfbhudrljbgrtrunjh629455431454256015151006" \
  | gpg2 -c -a --batch --passphrase-fd 0 --comment '51959508' message.txt

This results in the following output:

She then posts it in some pre-arranged public resource (pastebin, a public forum, etc) or sends it via regular email or chat software that would look inconspicuous and indistinguishable from her regular internet use (Gmail, Whatsapp, Facebook, etc).

Bob (also using Tails, of course), receives the communication and saves it into message.txt.asc. He then starts discarding his HOTP codes until he gets to 51959508, and then generates the identical decryption password using his yubikey and his remembered passphrase:

$ echo "somethingiknowlnrvntetfedgrgtfbhudrljbgrtrunjh629455431454256015151006" \
  | gpg2 -d --batch --passphrase-fd 0 message.txt.asc

Example with OpenStego

It's also possible to use OpenStego to conceal your message using steganography. To generate an encrypted payload and conceal it inside a PNG image, Alice can do the following (I am using the official 150-anniversary of Canada picture of the Queen, which I converted to png):

$ ./openstego.sh embed -mf message.txt -cf thequeen.png -sf 51959508.png -e \
  -p "somethingiknowlnrvntetfedgrgtfbhudrljbgrtrunjh629455431454256015151006"

She then uploads the resulting file to some image sharing service that Bob monitors (here it is below).

To get the contents of the message, Bob would then download the original image (just make sure the service doesn't optimize/recompress the image files -- or if it does, that it always preserves the originals). He then uses the name of the file to synchronize his HOTP counter and generates the password needed to get the message back out of the concealed file:

$ ./openstego.sh extract -sf 51959508.png \
  -p "somethingiknowlnrvntetfedgrgtfbhudrljbgrtrunjh629455431454256015151006"

Try it out yourself with the picture seen above, it's pretty cool. :)

Why this method is awesome

As stated above, this method has the following things going for it:

it is cheap (HOTP devices cost about $10, or a bit more for better crypto chips, like those in Yubikey 4s)
it is practical, and not even that tedious
it requires both a physical device (something you have) and a passphrase (something you know), meaning that it's inherently 2-factor
it offers forward and backward secrecy -- even if one of the used passwords becomes fully known to Eve, she cannot use that knowledge to read previous or future messages
even if the agent is captured and is coerced to divulge the scheme, the pre-shared passphrase, and the HOTP device -- even that won't allow Eve to read previous communications unless she gets the HOTP master key from the yubikey (which is expensive, but not impossible -- so don't expect this to save you if well-funded state actors are on your tail and you didn't manage to flush the yubikey down the toilet or bake it in a microwave)
if both devices are destroyed, all exchanged communication remains forever encrypted in a manner that is extremely resistant even to very powerful quantum computers of the distant future (at least, much more so than any asymmetric algorithm used today)

The downsides

As I said, this is "spy games" kind of stuff -- you have to a be a very dedicated and paranoid person to stick to this kind of protocol. It is good for one-to-one or one-to-many communication, but would quickly break down if attempted for group messaging due to inevitable HOTP counter desync. That said, it can probably be used to establish time-limited group chat sessions that are rekeyed daily.

If anything, this is just a mental paranoia exercise -- it was fun to do, but I certainly hope never to be in a situation where I have to worry about needing to use anything like it.

Thanks for reading, and please feel free to email me at hbic@paranoidbeavers.ca if you have any comments.

tags: crypto, security, privacy, quantum