Schedule

Signatures

“Real-life” signatures. Properties:

• Easy to verify
• Forging unlikely
• Hard to repudiate

Digital signatures. Should have same properties, in the absence of legal forces on the internet.

Topics:

• Assymetric cryptography
• Digital signatures
• Elliptic curve cryptography
• Implementation pitfalls

Ordinary (or symmetric) Crypto

• Both parties have to agree on a key

Diffie-Hellman key exchange

• Proposed in 1976
• Establishes a private secret key, unknown to any evesdropper

Whitfield Diffie and Martin E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, 1976.

The paper concludes with an interesting historical discussion (that gets bonus points for mentioning Thomas Jefferson):

While at first the public key systems and one-way authentication systems suggested in this paper appear to be unportended by past cryptographic developments, it is possible to view them as the natural outgrowth of trends in cryptography stretching back hundreds of years. Secrecy is at the heart of cryptography. In early cryptography, however, there was a confusion about what was to be kept secret. … After the invention of the telegraph, the distinction between a general system and a specific key allowed the general system to be compromised, for example by theft of a cryptographic device, without compromising future messages enciphered in new keys. … The development of computers has led for the first time to a mathematical theory of algorithms which can begin to approach the difficult problem of estimating the computational difficulty of breaking a cryptographic system. The position of mathematical proof may thus come full circle and be reestablished as the best method of certification.

The last characteristic which we note in the history of cryptography is the division between amateur and professional cryptographers. Skill in production cryptanalysis has always been heavily on the side of the professionals, but innovation, particularly in the design of new types of cryptographic systems, has come primarily from the amateurs. Thomas Jefferson, a cryptographic amateur, invented a system which was still in use in World War II, while the most noted cryptographic system of the twentieth century, the rotor machine, was invented simultaneously by four separate people, all amateurs. We hope this will inspire others to work in this fascinating area in which participation has been discouraged in the recent past by a nearly total government monopoly.

Observe how the them of amateurs being the ones who design the important cryptographic systems carries through with bitcoin. Although Satoshi’s actual identity is unknown, it seems pretty clear that they are not a professionally-trained cryptographer, and (so far, at least!) all the digital currencies developed by world renowned cryptographers have failed.

Discrete Logarithm Problem

Given g, y, and p, find x such that g^x mod p = y.

Discrete Logarithm Problem: easy to solve for real numbers.

What is the range of elements out of which we are randomly selecting?

Mod 5 exponentiation

Multiplicative order is the number of multiplication after which the result repeats.

Multiplicative order of g is n if n is the smallest positive integer such that gⁿ = 1.

Exponent Modulus

• Multiplicative order is at most p - 1.
• Pick random x such that 0 ≤ x < p - 1.
• g^a g^b mod p = g^a+b mod p = g^{(a+b) mod n} mod p

Public-key Cryptography

1. Google announces g^a.
2. Bob picks random secret b, computes (g^a)^b=g^ab.
3. Bob encrypts message m and sends: g^b, g^abm.

Man-in-the-middle (MITM)

Active adversary can still read everything. We have to know messages are coming from the right person.

Digital Signatures

Discrete-log based signature

ElGamal Signature Scheme

• Fixed global parameters: g, p
• Private key: a
• Public key: g^a mod p
• Signing:
  1. Input: message m
  2. Pick random k
  3. Compute r = g^k mod p; s = (m-ar)k^-1 mod p - 1
  4. Send (r, s) with message m
• Verification:
  1. Input: message m, (r,s)
  2. Verify that r^s(g^a)^r = g^m mod p.

Avoiding (overly) long numbers

Real-life keys are long. We can use any group where discrete log is hard.

A group is a set of elements and an associated operation such that it satisfies the following:

• Closure: a * b is also a group element.
• Associativity: for all a, b, c: (ab)c = a(bc).
• Identity element: there exists an element e, such that for every element a: a * e = a = e * a
• Inverse: for every element a, there exists an element b such that a * b = e = b * a.

Additional Cryptographic Properties:

• Discrete logarithm should be hard
• Group operation should be efficient

Elliptic Curve Cryptography (ECC)

• Group elements are points on a curve, e.g., y² = x³ + 7.
• Point “addition” using “geometry”

Elliptic Curve Digital Signature Algorithm

Follows the same structure as ElGamal signature, but only on x-coordinate.

Pitfalls

If we ever repeat signing nonce, we leak the private key. Sony actually did this with Playstation 3 consoles (Console Hacking 2010: PS3 Epic Fail, CCC 2010).

Poor randomness makes private keys predictable. Use /dev/urandom (Linux) or java.security.SecureRandom in Java. If you use a pseudorandom number generator that is seeded with an easily guessed value, you are in big trouble! A common mistake was to use Math.random() or srand(time(0)).

Logjam attack: downgrade security during handshake.

Notes

• How are digital signatures and real-life signatures different in terms of why we trust them? What stops each from being forged by others?

• Assume somebody really clever has a way of solving the discrete logarithm problem easily. That is, for any given g, y, and p, the adversary can compute x such that g^{x mod p = y}. How can this algorithm be used to break security of Diffie-Hellman protocol?

• What is a nonce? What breaks if we reuse it between encrypted messages?

• In elliptic curve cryptography, why do we use mod p integers? What would go wrong if we used real numbers? What would go wrong if we used unbounded integers?