Fast Public Key Crypto and Curve25519

Kevin Burke

@derivativeburke

What is cryptography?

Sending messages without someone in the middle being able to read them

Assumes someone in the middle can read (encrypted) message

Wifi
Radio
Intercepted messenger

Middleman may try to forge/tamper with messages

Not: steganography

Steganography: grape juice

Steganography: blinking

Symmetric cryptography

Applying a reversible transformation to a message

Usually involves a secret key

Example: rot13

O M A R C O M I N
B Z N E P B Z V A

Example: shared text

  O M A R C O M I N
+ W E T H E P E O P
  -----------------
  K Q T Y G D Q W C

Decrypt shared text

  K Q T Y G D Q W C
- W E T H E P E O P
  -------------------
  O M A R C O M I N

Example: Enigma

    1 | 2 | 3
O | D | H | U = S
  | M | Q | Q
  | T | Z | N

Example: Enigma 2

    1 | 2 | 3
M | M | H | U = Z
  | T | Q | Q
  | D | Z | N

Example: Enigma 3

    1 | 2 | 3
A | T | H | U = U
  | D | Q | Q
  | M | Z | N

Example: Enigma 4

    1 | 2 | 3
R | D | Q | U = N
  | M | Z | Q
  | T | H | N

Example: Enigma 10

    1 | 2 | 3
G | D | H | Q = G
  | M | Q | N
  | T | Z | U

Example: One time pad

Example: SIGSALY

SIGSALY (Pentagon)

   Eisenhower
+ (White noise)
---------------
  (Secret noise)

SIGSALY (Downing St)

  (Secret noise)
- (White noise)
---------------
   Eisenhower

Nowadays: Stream ciphers

Stream ciphers

for i := 0; i < 20; i += 2 {
  u := x0 + x12
  x4 ^= u<<7 | u>>(32-7)
  u = x4 + x0
  x8 ^= u<<9 | u>>(32-9)

Stream cipher inputs:

32-byte secret key
24-byte nonce
64-byte block "counter"

What is a nonce?

Without it, ciphertext is identical

Imagine SIGSALY twice

SIGSALY (Pentagon)

   Eisenhower
+ (White noise 1)
---------------
  (Secret noise 1)

SIGSALY (Pentagon)

   Marshall
+ (White noise 1)
-----------------
  (Secret noise 2)

Attacker

  (Secret noise 1)
- (Secret noise 2)

Attacker

   Eisenhower
  (White noise 1)
- (White noise 1)
-  Marshall
-----------------

What if you want to accept messages from anyone?

Public-key cryptography

Basics

Alice generates secret key (SK_alice)
Alice computes public key (PK_alice)
Bob generates secret key (SK_bob)
Bob computes public key (PK_bob)

Alice, Bob exchange public keys only

Basics, cont'd

Alice computes f(PK_bob, SK_alice)
Bob computes f(PK_alice, SK_bob)
These produce the same key
Use symmetric encryption with that key

Key Math Points

Need f with the magic property
Given PK_bob, hard to find SK_bob

Diffie Hellman basics

p = 37
(p should be prime)
g = 5

Alice's public/private keys

a = random() % 37
  = 87 % 37 = 13
A = g^a  % p
  = 5^13 % 37 = 13

Bob's public/private keys

b = random() % 37
  = 106 % 37 = 32
B = g^b   % p
  = 5^32 % 37 = 9

Alice computes shared key

s1 = B^a  % p
   = 9^13 % 37 = 12

Bob computes shared key

s2 = A^b   % p
   = 13^32 % 37 = 12

Hard to reverse

Given A (13), find a
13 (mod 37) = 5^a
Or 13 = 5^a (mod 37)
(Discrete logarithm problem - hard!)

Pick a number (mod 37)

Why curve25519?

1. Misuse resistance

Which way does this door open?

Which way does this door open?

Bad design has consequences

Victoria Hall

1,100 children rushed toward lobby
Lobby door opened inward (toward stairs)
Bolted so one child could pass at a time
Front children were trapped, crushed

Crash bars became law

Don Norman

Prone to misuse: JWT
small subgroup attack

JWT small subgroup attack

all the libraries that I checked missed validating that the received public key ... is on the curve

Curve25519: deliberately chosen to avoid small subgroup attacks

Generating a private key

Generate 32 bytes of random data
byte[0] = byte[0] & 248
byte[31] = byte[31] & 127
byte[31] = byte[31] | 64

1,2,4,8 is the only subgroup
`byte[0] = byte[0] & 248`

2. Speed

Floating point math works well with Intel registers

Add/mult mod 2²⁵⁵ - 19
is fast to compute

Alice's public/private keys

a = random() % 37
  = 87 % 37 = 13
A = g^a  % p
  = 5^13 % 37 = 13

3. Timing Attacks

Array lookups are not constant time

Compute values in pairs

x[b] (b ∈ {0, 1})
x[b] = (1 - b)x[0] + bx[1]

Paper ships with assembly implementation

burke.services

Thanks!

Kevin Burke

kev.inburke.com

kev@inburke.com

@derivativeburke

These slides are available at:

Fast Public Key Crypto and Curve25519

Kevin Burke

@derivativeburke

What is cryptography?

Sending messages without someone in the middle being able to read them

Assumes someone in the middle can read (encrypted) message

Middleman may try to forge/tamper with messages

Not: steganography

Steganography: grape juice

Steganography: blinking

Symmetric cryptography

Applying a reversible transformation to a message

Usually involves a secret key

Example: rot13

Example: shared text

Decrypt shared text

Example: Enigma

Example: Enigma 2

Example: Enigma 3

Example: Enigma 4

Example: Enigma 10

Example: One time pad

Example: SIGSALY

SIGSALY (Pentagon)

SIGSALY (Downing St)

Nowadays: Stream ciphers

Stream ciphers

Stream cipher inputs:

What is a nonce?

Without it, ciphertext is identical

Imagine SIGSALY twice

SIGSALY (Pentagon)

SIGSALY (Pentagon)

Attacker

Attacker

What if you want to accept messages from anyone?

Public-key cryptography

Basics

Alice, Bob exchange public keys only

Basics, cont'd

Key Math Points

Diffie Hellman basics

Alice's public/private keys

Bob's public/private keys

Alice computes shared key

Bob computes shared key

Hard to reverse

Pick a number (mod 37)

Why curve25519?

1. Misuse resistance

Which way does this door open?

Which way does this door open?

Bad design has consequences

Victoria Hall

Crash bars became law

Don Norman

Prone to misuse: JWT small subgroup attack

JWT small subgroup attack

Curve25519: deliberately chosen to avoid small subgroup attacks

Generating a private key

1,2,4,8 is the only subgroup byte[0] = byte[0] & 248

2. Speed

Floating point math works well with Intel registers

Add/mult mod 2255 - 19is fast to compute

Alice's public/private keys

3. Timing Attacks

Array lookups are not constant time

Array lookups are not constant time

Compute values in pairs

Paper ships with assembly implementation

burke.services

Thanks!

Kevin Burke

kev.inburke.com

kev@inburke.com

@derivativeburke

kev.inburke.com/slides/curve25519

Prone to misuse: JWT
small subgroup attack

1,2,4,8 is the only subgroup
`byte[0] = byte[0] & 248`

Add/mult mod 2²⁵⁵ - 19
is fast to compute