Cryptography [without end-system integrity] is like investing
in an armored car, to carry money between a customer living in a cardboard
box, and a person doing business on a park bench.
- Gene Spafford
This is basically the situation with most smart-phones
currently…
Side-channel attacks, backdoors, and hardware compromises,
can negate the good cryptography in your secure open-source apps.
There is hope, and some degree of security, though!
Tip: If anyone wants to speed up the lecture videos a little,
inspect the page, go to the browser console, and paste this in:
document.querySelector('video').playbackRate = 1.2
This is the original message or data that is fed into the algorithm
as input.
Encryption algorithm:
The encryption algorithm performs various
substitutions and transformations on
the plaintext (with the key as extra input).
Secret key:
The secret key is also input to the encryption algorithm.
The exact substitutions and transformations performed by the
algorithm depend on the key (important!).
Ciphertext:
This is the scrambled message produced as output.
It depends on the plaintext and the secret key.
For a given message, two different keys will produce two different
ciphertexts.
Decryption algorithm:
This is essentially the encryption algorithm reversed.
It takes the ciphertext and the secret key, and produces the
original plaintext.
1.4.2 Overview
Symmetric is the most common technique for providing confidentiality
for transmitted or stored data.
Also referred to as conventional,
secret-key, or single-key
encryption
Two requirements for secure use:
Strong encryption algorithm: The opponent should be
unable to decrypt ciphertext or discover the key, even if in possession
of a number of ciphertexts together with the plain-text that produced
each ciphertext.
Shared secret: Sender and receiver must have
obtained copies of the secret key in a secure fashion, and
must keep the key secure
1.4.3 Simplified model
09-ModernSymmetric/f1-crop.png
What kind of encryption is the Caesar cipher?
1.4.4 Attacking Symmetric
Encryption
1.4.4.1 Cryptanalytic Attacks
Rely on:
Nature of the algorithm
Some knowledge of the general characteristics of the plaintext
Some sample plaintext-ciphertext pairs
Exploits the characteristics of the algorithm to attempt to deduce a
specific plaintext or the key being used
If any attack is successful, all future and past messages encrypted
with that key are compromised
1.4.4.2 Brute-Force Attack
Try all possible keys on some ciphertext, until an intelligible
translation into plaintext is obtained
On average, half of all possible keys must be tried to achieve
success
1.4.5 Modern (or sort-of modern)
symmetric algorithms
1.4.5.1 Data Encryption Standard
(DES)
https://en.wikipedia.org/wiki/Data_Encryption_Standard
DES is the archetypal block cipher, an algorithm that takes a
fixed-length string of plaintext bits and repeatedly transforms it
through a series of complicated operations into another ciphertext
bitstring of the same length.
09-ModernSymmetric/des.png
Was a widely used encryption scheme
Uses 64 bit plaintext block and 56 bit key to produce a 64 bit
ciphertext block
Strength concerns:
Concerns about algorithm:
No critical weakness, and DES is the most studied encryption
algorithm in existence (maybe now AES is most studied, though this used
to be true).
Use of 56-bit key:
With a key length of 56 bits, there are 256 possible
keys, which is approximately 7.2 * 1016 keys.
January 1999, distributed.net and the Electronic Frontier Foundation
(EFF) collaborated to publicly break a DES key in 22 hours and 15
minutes
1.4.5.1.1 Time to brute force
How much time is required for a brute-force attack for various key
sizes?
Right column is supercomputer, second from right is a personal
computer.
1.4.5.2 Triple DES
09-ModernSymmetric/image8.png
Repeats basic DES algorithm three times using either two or three
unique keys
First standardized for use in financial applications in 1985
Attractions:
168-bit key length overcomes the vulnerability to brute-force attack
of DES
Underlying encryption algorithm is the same as in DES
Drawbacks:
Algorithm is sluggish in software (aside: hardware implementations
of fast crypto, why?)
Uses a 64-bit block size
The whole 3DES key space can be searched thoroughly by affordable
consumer hardware since 2015 or so.
AES operates on a 4 x 4 column-major order matrix of bytes
AES is based on a design principle known as a
substitution-permutation network, a combination of both substitution and
permutation, and is both fast in software, and can be implemented
quickly in application-specific hardware.
Needed a replacement for 3DES.
3DES was not reasonable for long term use
NIST called for proposals for a new AES in 1997
Should have a security strength equal to or better than 3DES
1.4.6 Practical Security Issues:
Modes of operation
Typically symmetric encryption is applied to a unit of data larger
than a single 64-bit or 128-bit block
Electronic codebook (ECB) mode is the simplest approach to
multiple-block encryption
Each block of plaintext is encrypted using the same key
Cryptanalysts may be able to exploit regularities in the
plaintext
(e.g., regularities in image file can actually show image)
Alternative techniques developed to increase the security of
symmetric block encryption for large sequences
Overcomes the weaknesses of ECB
1.4.6.1 ECB mode
image, ECB mode, ECB Randomized mode
1.4.6.2 Cipher Block Chaining (CBC)
mode
* Kick-start with an initialization vector (IV), which is just another
number that has to be really random!
* Each block of plaintext is XOR’ed with the previous ciphertext block
before being encrypted.
* This way, each ciphertext block depends on all plaintext blocks
processed up to that point.
* To make each message unique, an initialization vector must be used in
the first block.
* Can we decrypt in parallel for speed and efficiency?
1.4.7 Block versus Stream
Ciphers
1.4.7.1 Block Cipher (top image
below)
Processes the input one block of elements at a time
Produces an output block for each input block
Can reuse keys
More common
Seemingly easier to make a secure algorithm (empirically, not
intuitively).
How might we know this?
09-ModernSymmetric/f2-crop.png
1.4.7.2 Stream Cipher (bottom image
above)
Processes the input elements continuously
Produces output one element at a time
Primary advantage is that they are almost always faster, and use far
less code
Encrypts plaintext one byte at a time
Pseudorandom stream is one that is unpredictable without knowledge
of the input key
Seemingly much harder to design securely!
Competitions to develop new algorithms have produced fewer good
candidates, for whatever reason.
The key is input to a pseudorandom bit generator, that produces a
stream of 8-bit numbers, that should be apparently random (but are
determinitistically reproducible).
A pseudorandom stream is one that is unpredictable without knowledge
of the input key, and which has an apparently random character over
time, and which we do not know how to predict without knowing the
seed.
The output of the generator, called a keystream, is combined one
byte at a time with the plaintext stream, using the bitwise exclusive-OR
(XOR) operation.
All complexity and randomness has to come from the keystream
generator (stream), as opposed to substitutions and transformations of
the data (block).
