Goals for this lesson

Cryptography Landscape

Operating Context

The internet is a public space.

We communicate over public channels. Adversaries may want to:

Operating Context

Resources are constrained.

• Network, storage, computation, etc.: We don't want to send, store, or operate on the same data, but we want guarantees about it, e.g. that we agree on a message's contents.
• Privacy: We must assume that all channels can be monitored, and thus closed channels are heavily constrained (i.e. assumed to not exist).

Open vs. Closed Channels

Cryptography based on public systems is more sound.

Kerckhoff's Principle: Security should not rely on secret methods,
but rather on secret information.

Cryptographic Guarantees*

Data Accessibility

A party may gain access to information
if and only if they know some secret (a key).

Message Authenticity

Like physical signatures, cryptography may be used to give a reasonable expectation of a message's provenance (origin), in order to give the users the credible expectation that the stated origin is authentic.

Data Integrity

Physical signatures provide weak authenticity guarantees
(i.e. they are quite easy to forge), and no integrity guarantees.

Data Integrity

One-Way Functions

One-way functions form the basis of both
(cryptographic) hashing and asymmetric cryptography.

• Functions for which we know fast algorithms to compute
• But for which we believe to be hard to invert
• And for which there may be some secret which makes it easy

Hash Functions

Motivation: We often want a succinct representation of some data with the expectation that we are referring to the same data. A "fingerprint".

Hash Function Applications

Hashes can be useful for many applications:

Cryptographic vs. Non-Cryptographic

Cryptographic hash functions provide stronger guarantees
on the last three properties.

But non-cryptographic hash functions are much faster.

Symmetric Cryptography

Symmetric encryption assumes all parties begin with some shared secret information, a potentially very difficult requirement.
The shared secret can then be used to protect further communications from others who do not know this secret.

In essence, it gives a way of extending a shared secret over time.

Symmetric Encryption

For example, the Enigma cipher in WW2. A channel was initiated by sharing a secret ("key") between two participants. Using the cipher, those participants could then exchange information securely.

However, since the key contained only limited entropy ("information"), enough usage of it eventually compromised the secret and allowed the allies to decode messages. Even altering it once per day was not enough.

Asymmetric Cryptography

• In asymmetric cryptography, we devise a means to transform one value (the "secret") into some corresponding counterpart (the "public" key), preserving certain properties.

• We believe that this is a one-way function (that there is no easy/fast inverse of this function).

• Aside from preserving certain properties, we believe this counterpart (the "public key") reveals no information about the secret.

Asymmetric Encryption

• Using only the public key, information can be transformed ("encrypted") such that only those with knowledge of the secret are able to inverse and regain the original information.

Digital Signatures

• Using the secret key, information can be transformed ("signed") such that anyone with knowledge of the information and the counterpart public key is able to affirm the operation.

• Digital signatures provide message authenticity and integrity guarantees.

• The next two lessons are dedicated to digital signatures,
  this is strictly an intro.

Digital Signatures

signing function: a pure function which operates on some
message data and some secret to yield a signature.

A signature proves that the signer had knowledge of the secret,
without revealing the secret itself.

The signature cannot be used to create other signatures.

Non-repudiation

Only those with knowledge of some secret information
could have produced a valid signature.

The signer cannot claim that the signature was forged, unless they can defend a claim that the secret was compromised prior to signing.
Symmetric cryptography does not provide this guarantee: someone else knows the secret.

Practical Considerations

Symmetric cryptography is much faster, but requires more setup (key establishment) and trust (someone else knows the secret).

Asymmetric cryptography is slow, but typically preserves specific algebraic relationships, which then permit more diverse if fragile protocols.

Hybrid Cryptography

Hybrid cryptography composes new mechanisms from different cryptographic primitives.

For example:

• Symmetric encryption can provide speed, and often confidentiality,
• Hash functions can reduce the size of data while preserving identity,
• And asymmetric can dictate relations among the participants.

Certifications

Certifications are used to make attestations about public key relationships.

Typically in the form of a signature on:

• One or more cryptographically strong identifiers (e.g. public keys, hashes).
• Information about its ownership, its use and any other properties that the signer is capable of attesting/authorizing/witnessing.
• (Meta-)information about this information itself, such as how long it is valid for and external considerations which would invalidate it.

Entropy, Randomness, and Key Size

• Entropy: Amount of non-redundant information contained within some data.
• Randomness: Unpredictability of some information. Less random implies lower entropy.
• Key size: Upper limit of possible entropy contained in a key. Keys with less random (more predictable) data have less entropy than this upper bound.
• One-time pad: A key of effectively infinite size. If it is perfectly random (i.e. has maximal entropy), then the cipher is theoretically unbreakable.

Randomness Generation

fn roll_die() -> u32 {
  // Guaranteed random: it was achieved through a real-life die-roll.
  4u32
}

• Pseudo-random sequences
• Physical data collection (e.g. cursor movement, LSB of microphone)
• Specialised hardware (e.g. low-level noise on silicon gates, quantum-amplifiers)

Summary

Cryptography is much more than encryption.