CSCI 430
CSCI 430: Network Security
There are some confusing terms used in cryptography. To disambiguate, we will
use the following terms:
Key: A secret that is used to encrypt a message.
Message: A string of characters that is encrypted using a key.
Ciphertext: The encrypted message.
Plaintext: The decrypted message.
Cleartext: A term that is almost never used, and is not defined
in any official specification, text, or paper.
Cipher: A function that encrypts a message.
Secret Key: A key that is used to encrypt a message with a symmetric key algorithm. The key is not known to anyone other than the sender and the recipient. Because the key is a shared secret between these two parties, the key is called a secret key.
Public Key: A key that is used to encrypt a message with a public key algorithm. The key is need not be kept secret. It can be freely distributed to anyone. The public key can be used to encrypt messages that can only be decrypted using the corresponding private key. It can also be used to verify signature produced by a message that was encrypted with a private key.
Private Key: A key that is used to decrypt a message encrypted with a public key algorithm. The private key is not known to anyone, because it is the only key capable of decrypting messages encrypted with the corresponding public key. The private key can also be used to sign messages. Anyone holding the corresponding public key can verify the signature of a message encrypted using the private key.
Signature: A signature is a digital signature of a message. It is created by encrypting the message with a private key. The signature can be verified by anyone holding the corresponding public key.
Hashing: A function that converts a message into a fixed length string of bits.
Common Notation
| Symbol | Meaning |
|---|
| $M$ | A message |
| $\mathrm{H}(M)$ | A hash function $\mathrm{H}$ applied to message $M$ |
| $C$ | The ciphertext representation of a message |
| $P$ | The plaintext representation of a message |
| $\mathrm{D}(K,M)$ | The decryption function $\mathrm{D}$ applied to message $M$ using key $K$ |
| $\mathrm{E}(K,M)$ | The encryption function $\mathrm{E}$ applied to messagc $M$ using key $K$ |
| $K$ | A secret key used in symmetric key cryptography |
| $K_{AB}$ | A secret key shared between $A$ and $B$ |
| $\mathit{Pr}_a$ | A private key belonging to person $A$ |
| $\mathit{Pu}_a$ | A public key belonging to person $A$ |
Unlike MAC, the hash function $H$ does not take a key as an argument. It only
accepts a single argument, $M$, the message to be hashed, and returns a fixed
length string of bits, $MD$, known as the message digest.
$$ H(M) = \mathit{MD} $$
Notes from MIT 6.046 Spring 2015 Lecture 21
Hash Functions
A hash function is a function that takes a message and produces a hash value
with the following three properties:
- Fixed length output
- Deterministic output, meaning that the output of the same input is always the same
- Pseudorandom output, meaning that the output of the same input avoids collisions
Let $h(x)$ be a hash function, and let $d$ be a constant. It follows that:
$$ h \mid \lbrace 0, 1 \rbrace ^* \mapsto \ \lbrace 0, 1 \rbrace ^d $$
- Random Oracle
- a function that takes a message and produces a random
output that is the deterministic, known, and constant-time for messages
of arbitrary length. This is a theoretical goal state of a hash function, but
it is not possible to implement it in practice.
Message Authentication Codes
A message authentication code (MAC) is a crytographic primitive. There are
two main algorithms that pertain to message authentication codes: sign and
verify.
Ciphers
Cipher Block Chaining (CBC)
CBC-MAC is only secure for fixed-length strings.[[1]]
These types of cryptographic primitive can be distinguished by the security goals they fulfill (in the simple protocol of "appending to a message"):
Integrity: Can the recipient be confident that the message has not been accidentally modified?
Authentication: Can the recipient be confident that the message originates from the sender?
Non-repudiation: If the recipient passes the message and the proof to a third party, can the third party be confident that the message originated from the sender?
| Property | Hash | MAC | Signature |
|---|
| Encryption | None | Symmetric | Asymmetric |
| Integrity | Yes | Yes | Yes |
| Authentication | No | Yes | Yes |
| Non-repudiation | No | No | Yes |
Authentication without confidence in the keys used is useless. For digital signatures, a recipient must be confident that the verification key actually belongs to the sender. For MACs, a recipient must be confident that the shared symmetric key has only been shared with the sender.
A (unkeyed) hash of the message, if appended to the message itself, only protects against accidental changes to the message (or the hash itself), as an attacker who modifies the message can simply calculate a new hash and use it instead of the original one. So this only gives integrity.
A message authentication code (MAC) (sometimes also known as keyed hash) protects against message forgery by anyone who doesn't know the secret key (shared by sender and receiver).
A (digital) signature is created with a private key, and verified with the corresponding public key of an asymmetric key-pair. Only the holder of the private key can create this signature, and normally anyone knowing the public key can verify it.
- One-Wayness
- Also known as pre-image resistance, is a property that states even if an attacker knew the hash of a message, it would be infeasible for the attacker to find the message that produced that hash.
- Collision Resistance
- It is infeasible to find two messages which produce the same hash.
- Target Collision Resistance
- Given an initial message, and its hash, it is infeasible to find another message that produces the same hash.
- Secrecy
- TODO
- Integrity
- TODO