Notes On Applied Cryptography, Chapter 2 - Protocol Building Blocks

2017-08-20

What is a protocol? Agreed series of steps among some participants, where each participant is expected to play their part. For example, saying hello when you step through the door and getting a hello back; eating at a restaurant and paying for dinner; voting.

If Alice wants to sell her car to Bob, she might not want to give her car to Bob straight away in exchange of a check. What if the check bounces? Instead, she can use a trusted arbitror, like a lawyer. The protocol might look something like this:

  1. Alice gives car (or title of) to arbitror
  2. Bob gives check to arbitror
  3. Arbitror verifies the check has coverage
  4. Arbitror gives check to Alice and car to Bob
  5. If check bounces Alice gets her car back

In this case, the arbitror doesn’t care if the check bounces or not, as they get paid regardless. Furthermore, they often have a reputation at stake.

If you move to a different country and the voting booth looks different, you can adapt. Computers are less flexible, so the protocols have to be more precise.

In cryptographic protocols, we usually have a set of standard participants that we use:

A basic example of a cryptographic protocol is when Alice and Bob wants to communicate securely:

  1. Alice and Bob agree on a cryptosystem and exchange a secret key K
  2. Alice encrypt her message with K and sends to Bob
  3. Bob decrypts the message with K

Oftentimes the key exchange is the tricky part. If we have a network of n individuals who want to communicate with each other, we need n^2 keys that have to be exchanged privately, which obviously gets expensive as the keys have to be exchanged out-of-band. Instead we can use public-key cryptography and some trusted key directory. Public-key cryptography relies on the existence of one-way functions.

One-way functions. x -> f(x) is simple, but f(x) -> x is not. Like breaking a plate; easy to do but hard to put back together. Intuitively it’s easier to compute x^2 than sqrt(x), but the existence of such functions and their computational cost is non-trivial.

There are also trapdoor functions, which rely on having a secret formula for going in the reverse direction. For example a manual watch is hard to put together after breaking it, but if we have instructions for it we can do.

Here’s what a protocol with public-key cryptography might look like:

  1. Alice and Bob agree on a cryptosystem to use, such as RSA
  2. Alice finds Bob’s public key, encrypt her message with it, and sends it to Bob
  3. Bob decrypts the message with his private key

However, a purely public-key cryptography is often not used, primarily for two reasons:

  1. It’s 1000 times slower than symmetric key encryption
  2. It’s vulnerable to a chosen-plain text attack, since the public key is available

In a chosen-plain text attack, Eve can quickly enumerate plain text possibilities and try Bob’s public key against it. This way the presencene or absence of a given plain text can be detected.

Instead, public-key crypto is often used to exchange a session key, which is a symmetric key that is used to communicate for that specific session. This is the key-exchange dance that often happens in practice. This also means a given session can’t necessarily be decrypted by Eve if she gets hold of the private key at a later point in time.

We can also have subprotocols, things that only happen in certain circumstances. For example, instead of having a lawyer present at every transaction, we can sign contracts and then appear before a judge in case of conflict. The protocol works like this:

  1. Alice and Bob agree on a contract and both sign it
  2. Alice presents her evidence
  3. Bob presents his evidence
  4. The judge decides how the matter should be resolved

This leads us to signatures. We have digital signatures, which act like “normal” signatures, but usually with more guarantees. Many protocols around this. Doesn’t necessarily have to be a straight public-key crypto scheme, but a basic example is Alice signing with her private key. Bob has Alice’s public key, so can verify that Alice’s message was indeed signed by her private key.

Instead of signing a whole document, which might be expensive, we can sign a hash of it. A hash function simply takes a variable-length text and compute fixed-length hash that is reasonably well-distributed and very likely to be unique.

Replay attacks. This is not the name that Schneier uses in the book, but as far as I can tell it’s similar. If Alice sends Bob a digitally signed check of $1000, Bob can go to a bank and show the bank proof that Alice send the check. He can then go to another bank and do the same thing. We can design protocols that uses timestamps to ensure this doesn’t happen.

Repudiation. Alice can claim they lost their private key and thus that a transaction actually never took place. We can design protocols around this property.

Questions

I suspect a few of these will be answered in future chapters.

What is the difference between an arbitror and an escrow?

Answer: An escrow is an instance of an arbitror. Arbitror are disinterested, trusted parties. Can also be used for wills or contract negotiation. Another example is a public notary.

What is an example of a judge being used in a cryptographic protocol?

Answer: Don’t know yet, but this type of protocol is called an adjudicated protocol. They alleviate the burden of having an arbitror in a protocol between two parties that don’t necessarily trust each other 100%. It’s a subprotocol that’s only executed in case of dispute. Peeking ahead, it seems to be used in secret splitting.

Why is public-key crypto so fundamentally slower than symmetric?

Why do we need so many different protocols for digital signing? What does the matrix of trade-offs look like?

It’d be useful to compile a list of various standard techniques and which properties they guarantee. Juxtaposition approach.

What is the fundamental property that we strive to maintain for all protocols?

Something like: the only weakness for the protocol should be knowing the key. But it was more generalized than that. Something about not giving any more information than what is specified in the protocol?

Answer: It should not be possible to do more or learn more than what is specified in the protocol. This is hard problem.

What are the basic classes of cryptographic protocols we use? what would a classification look like?