Don't like this style? Click here to change it! blue.css

LOGIN:
Welcome .... Click here to logout

Key Sharing

And the PKI Story

Diffie-Hellman Key Exchange

AKA: The magic algorithm that runs the internet

So I have some stories to tell you:

Today's flag is actually the mechanics of this system.

So we can use it as our baseline and maybe I can do some light walkthroughs of how to approach some of the others.

Your project 2 is going to be submitting video solutions to CTF problems as a tour of the OWASP top 10, so it's all pertinent.

THE GOAL

We've figured out that we can do fantastic encryption by:

NOTE: we forgot to do any message authentication... so people will totally tamper with our packets.

HOW CAN WE MAKE A SHARED SECRET KEY?

ON THE INTERNET?

WHILE EVERYONE IS LISTENING?

Today's Flag Lecture

The math is basically like this pick a random \(a\) and a big prime \(p\).

Protect that little \(a\) it is your super secret private key.

Now tell the world \(A = 2^a\) mod \(p\).

Listen for your partner to tell you their \(B = 2^b\) mod \(p\).

Here's the magic: You use your \(a\) and calculate \(B^a\) mod \(p\).

How does this work? \(B^a = (2^b)^a = 2^{ab}\) but the other person knows \(b\) and \(A=2^a\), so they calculate \(A^b = (2^a)^b = 2^{ab} \).

Little demo:

First we solve the flag, then pick a partner, and have a secret conversation in our public discord.

OK swapping keys in public:

Public Key Infrastructure

So we can setup a secure channel roughly. In fact here's my helper scripts from last time:

This is cool. Setting up a secure channel in public! So what's the catch?

Flaw 1: number theory needs care (backdoors included)

Play this game with me:

See the Pen Chinese Remainder Theorem Game by Andy Novocin (@AndyNovo) on CodePen.

This is called the Chinese Remainder Theorem, and it's pretty intuitive and clever and useful.

Here is how that undermines Diffie-Hellman:

Topic 1: Pohlig-Hellman

You have this problem to solve, given \(g, h, p\) find the unknown \(x\) such that \(g^x = h\) mod \(p\).

We know, thanks to Fermat's little Theorem, that \(m^{p-1} = 1 \) mod \(p\) for any integer \(m\).

So we're interested in reducing the search space for \(x\) from \(1, \cdots, p-2\) to something much smaller.

The idea is that we can actually figure out \(x\) mod \(m\) for any \(m\) that divides \(p-1\)

When I go concrete I'll use \(p=31\) in the following to match the notes.

To show how that works let's play with \(x\) mod \(3\). Every integer can be written down as \(3k, 3k+1,\) or \(3k + 2\) for an arbitrary integer \(k\). This comes from when we looked at modular arithmetic as infinite sets, like \(3 \cdot \mathbb{Z} + 1\) as this big infinite set of all things that are 1 larger than a multiple of 3.

We don't know which of those 3 worlds \(x\) lives in but we could say that \(x = 3k + y\) where \(y\) is either 0, 1, or 2.

At this point maybe it seems a tad abstract but if we can change this problem from hunting for \(x\) inside the range \(1, \cdots, p-2\) to hunting for \(y\) in the range \(0,1,2\) we've certainly made a smaller problem.

OK NOW we're ready to play with the original equation: \(g^x = h\)

Let's replace \(x\) with \(3k + y\):

\(g^{3k + y} = h\)

We know that \(g^{p-1} = 1\). Now if 3 happens to divide \(p-1\) like in the \(p=31\) case then we have a trick we can use:

In our \(p=31\) case Fermat's little theorem gives \(g^{30} = 1\). So the big idea is that we can raise both sides of the main equation to the 10th power.

Watch what happens

\(g^{10 \cdot (3k + y)} = h^{10}\)

Playing with the left hand side we get:

\( g ^{10 \cdot (3k + y)} = g^{30k + 10y} = g^{30k} \cdot g^{10y} = (g^{30})^{k} \cdot g^{10y} = (1)^{k} \cdot g^{10y} = g^{10y} \)

So that means \(g^{10y} = h^{10}\)

Did we make progress?

Well now we have a simple search to do, look at \(g^0, g^{10}, g^{20}\) and compare those 3 values with \(h^{10}\) (all of this is mod 31)

So we calculate \(h^{10}\) and compare it with the three possible values of \(y\) and we KNOW that one of them will match up. Let's say when \(y=1\) for some specific value of \(h\) then it must be that \(g^{10} == h^{10}\) which would imply that \(x = 3k + 1\) for some value of \(k\). Now we know that the final answer will be 1 mod 3.

You can imagine that we could repeat this process for other factors of \(p-1\). When \(p=31\) that would mean 2, 3, 5.

But could the trick work for other moduli?

Like, no one is stopping us from writing down \(x = 7k + y\). So plug it in to the original equation: \(g^x = h\) We get \(g^{7k + y} = h\) But since 7 doesn't divide 30 we don't have some nice way to get rid of needing to find the \(k\) AND find the \(y\). Raising both sides to any power is never going to reduce my search space.

That is the heart of Pohlig-Hellman, for numbers \(m\) that divide \(p-1\) we can change the search space from \(m \cdot k + y\), (where \(y = x\) mod \(m\) ), to ignoring needing the \(k\) and only needing to find \(y\) which is ALOT less work.

After all of that use Chinese Remainder Theorem to finish the problem.

Daily Flag Friday:

Flaw 2: Man-in-the-middle attack

OK, so in a public-key exchange I can establish a secure connection with anyone (up to the number theory choices/risks). BUT now identity of WHO I am talking to becomes very important.

The most common application of this DHKE process is TLS the HTTPS protocol for encrypting website traffic. So the act of ensuring that no one is pretending to be a site that they are not is important.

Public Key Infrastructure

This is the idea of certs, and who signs them, and what is a digital signature. Also the chain of trust and DNSSEC and a whole TON of work by the IETF and Certificate Authorities and so on.

https://www.cloudflare.com/learning/ssl/how-does-ssl-work/

Friday Afternoon Fun

Look at a real certificate in Wireshark

Make a self-signed certificate at the command-line

Use let's encrypt to sign a cert automagically for a domain you own

Digital Signatures

Behind all of these certs is the idea of a digital signature. It works like this:

When a digital signature "signs" a message it provides:

  1. INTEGRITY - your message was not altered
  2. AUTHENTICATION - your message was indeed sent by you alone
  3. NON-REPUDIATION - you cannot deny that you signed that document

There are two (ok maybe 3) digital signature paradigms out there:

RSA Digital Signatures

The text book version of an RSA digital signature is do RSA encryption but flip the public and private key. That textbook version is not secure engough for reality.

In practice it's all about the padding: https://www.rfc-editor.org/rfc/rfc3447#section-8

DSA (and ECDSA)

This is the "Digital Signature Algorithm" and it's elliptic curve equivalent.

This is the key behind the blockchain (this plus the hashing toy problem and maybe a merkle tree).

Here are some old notes on the matter

Extra Flag

So I had imagined a problem where I gave you a cert and the private key that goes with it. Then the pcap of me visiting a secret site encrypted.

But that really only helps if it was pure RSA encryption so I changed the problem to the more modern technique:

Here is the pcap: tls.pcapng and this other file my malware exfiltrated from the target: sslkey.log