Previous: 07-CryptoMath.html
“The mantra of any good security engineer is:
Security is a not a product, but a process.
It’s more than designing strong cryptography into a
system;
it’s designing the entire system such that all security
measures,
including cryptography, work together.”
- Bruce Schneier
https://en.wikipedia.org/wiki/Bruce_Schneier
https://www.schneier.com/
Discussion question:
Which parts of a computer system matter the most?
A system have high and low level parts.
Do the high or low level parts matter more?
Why?
Does any pattern always hold?
http://inventwithpython.com/cracking/ Chapter 24
Very good tutorial on RSA; read it!
http://doctrina.org/How-RSA-Works-With-Examples.html
Very good tutorial on RSA; read it!
http://doctrina.org/Why-RSA-Works-Three-Fundamental-Questions-Answered.html
document.querySelector('video').playbackRate = 1.2Classification of Encryption Schemes
* Symmetric vs. Asymmetric
* Computationally secure vs. Information theoretically secure
A significant distinction.
Also referred to as private key encryption.
There is one private or secret key, which is generally shared between
two parties.
Both encryption and decryption use the same key, and a similar
process.
Key agreement and exchange can be a very challenging problem.
Relies on making a big mess of the data, using the pre-exchanged key,
reversibly.
Generally computationally efficient to encrypt and decrypt (fast).
Examples of “modern” symmetric algorithms:
AES, DES, 3DES
Faster than asymmetric.
It is also referred as public key encryption.
It has two keys: one public and one private.
The encryption operation uses only the public key,
which is known to everyone.
The decryption operation uses only the private key,
which is known to one person.
Modern innovation (newer algorithms).
Relies on math tricks (one way functions).
Moderately computationally expensive,
both in key-generation and in encryption and decryption.
Examples of “modern” asymmetric algorithms: RSA, DSA, ElGamal,
NTRU.
Slower than asymmetric.
+++++++++++++++++++++
Cahoot-08.1
A computationally secure encryption scheme,
assumes the adversary has limited computing
power.
The adversary can be assumed to solve polynomially-bounded
problems,
but not to solve computationally infeasible NP-Complete, NP-hard, etc.
problems
Almost all practical encryption schemes,
e.g., AES and RSA, are computationally secure.
An information-theoretically secure encryption scheme,
assumes the adversary has unlimited computing
power.
The adversary can be assumed to solve any computational problems
NP-Complete and NP-hard could hypothetically be efficiently
solved,
and the scheme would still offer perfect security
Unconditional or perfect security.
One-time pad is information theoretically secure.
There are variants of the OTP,
but it’s the only one that fits this criteria.
Proposed by Diffie and Hellman in 1976 (quite recently!)
Based on mathematical one-way functions.
Q: What do we mean by one-way?
A: Those operations where the best algorithm to reverse them is a form
of brute force.
Asymmetric schemes use two separate keys:
public key
private key
Public key is made public for others to use.
Plaintext: Readable message or data that is fed into
the algorithm as input
Encryption algorithm: Performs transformations on the
plaintext
Public and private key: Pair of keys, one for
encryption, one for decryption
Ciphertext: Scrambled message produced as output
Decryption key: Produces the original plaintext.
Q: Why seemingly redundant definition?
A: either can decrypt or encrypt
Decryption algorithm: Accepts the ciphertext and the
matching key, and produces the original plaintext.
Should be:
* Computationally easy to create key pairs
* Computationally easy for sender, knowing public key, to encrypt
messages
* Computationally easy for receiver, knowing private key, to decrypt
ciphertext
* Computationally infeasible for opponent to determine private key from
public key
* Computationally infeasible for opponent to otherwise recover original
message
* Useful (but not required) if either key can be used for each
role
* Either key used for encryption with the other used for decryption
(optional)
Computationally easy for a party B to generate a pair,
(public key PUb, private key PRb).
Computationally easy for a sender A,
knowing the public key and the message to be encrypted, M,
to generate the corresponding ciphertext:
C = E(PUb , M)
Computationally easy for the receiver B to decrypt the resulting
ciphertext,
using the private key to recover the original message:
M = D(PRb ,C) = D[PRb, E(PUb, M)]
Computationally infeasible for an opponent,
knowing the public key, PUb,
to determine the private key, PRb
Computationally infeasible for an opponent,
knowing the public key, PUb, and a ciphertext, C,
to recover the original message, M.
Optionally, either of the two related keys can be used for
encryption,
with the other used for decryption.
M = D[PUb, E(PRb, M)] = D[PRb,
E(PUb, M)]
This is a neat feature, that you will see exists in RSA!
Meet Alice and Bob (and sometimes evil Eve)!
https://en.wikipedia.org/wiki/Alice_and_Bob
http://cryptocouple.com/
Each user generates pair of related keys, public and private.
ob encrypts a message using Alice’s
public key.
Alice decrypts messages using her private key;
no other recipient can decrypt the message,
because only Alice knows Alice’s private key.
Go over this carefully:
Bottom half: switch key roles
User encrypts data using his or her own
private key.
Anyone who knows the corresponding public key will be
able to decrypt the message.
Used for authenticating both:
source identity, and data integrity.
Created by encrypting hash code with private key.
Does not provide confidentiality,
even in the case of complete encryption.
Message is safe from alteration, but not eavesdropping.
Encryption is provided independently.
RSA (Rivest, Shamir, Adleman)
Developed in 1977.
This is the most widely accepted and implemented approach to public-key
encryption.
Block cipher in which the plaintext and ciphertext are integers between
0 and n-1 for some n.
Diffie-Hellman key exchange algorithm
Enables two users to securely reach agreement about a shared
secret,
that can be used as a secret key for subsequent symmetric encryption of
messages.
Most widely accepted and implemented approach to key exchange.
Limited to the exchange of the keys, with no direct encryption.
Digital Signature Standard (DSS)
Provides only a digital signature function with SHA-1.
Cannot be used for encryption or key exchange.
Elliptic curve cryptography (ECC)
Security like RSA, but with much smaller keys for similar security.
Read Chapter 9 and all Appendices:
https://github.com/crypto101/crypto101.github.io/raw/master/Crypto101.pdf
https://en.wikipedia.org/wiki/RSA_(cryptosystem)
https://simple.wikipedia.org/wiki/RSA_algorithm
Video series detailing the algorithm:
https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/intro-to-rsa-encryption
Publically invented by Rivest, Shamir, and Adleman of MIT in
1977.
For a time, it was the best known, and widely used public-key
algorithm.
Uses exponentiation of integers, modulo some prime.
For a moment, let’s see the magic:
How?
Key generation involves multiple steps of repeated generate and
test.
Each key in the public key scheme is made of two numbers.
The public key will be two numbers, n and e.
The private key will be two numbers, n and d.
The steps to create these numbers follow:
Generate many random numbers,
until you find two that are distinct, very very large, and prime:
p and q
Multiply these two numbers,
p x q = n (n will then be the modulus for encryption).
Also, multiply these two numbers minus 1,
(p - 1) × (q - 1)
to get a number called \(\phi(n)\) (the
modulus for key generation).
Generate many more random numbers,
until you find another number, which we will call e,
which is relatively prime to n.
This is part of the public key.
Calculate the modular inverse of e, which we’ll call d.
This is part of the private key.
Side note:
In practice, e is often just chosen as 65537, or some other fixed
value…
Notice that the modulus, n, is used in both keys.
By convention, the d number must be kept secret,
as only it can decrypt messages encrypted to e,
which is pubic information.
More formally, generate
numbers p and q, where
where p and q are very very large primes, with roughly similar sizes,
and
n = p * q
The size of p or q needs to be at least 2,048
bits,
though 4096 is a practical current upper limit in most
implementations.
Plaintext space:
Zn
Ciphertext space:
Zn
Public key:
n, e, where,
e is an integer relatively prime to \(\phi(n)\)
Private key:
d where
\(ed \equiv 1 \mod \phi(n)\)
Each done in sequence, in either direction, will cancel the other out!
Encryption: E(x, n, e) = xe mod n
Decryption: D(c, n, d) = cd mod n
= xed mod n
= x1
The above formulation is an over-simplification of the real
proof,
but illustrates a key theoretical point.
Iteratively, pick two primes:
p = 11
q = 17
Multiply (p - 1) × (q - 1):
n = 11 * 17 = 187
\(\phi(n)\) = 10 * 16 = 160
Iteratively with GCD Euclidean,
pick a relative prime to \(\phi(n)\):
e = 3
Using Extended Euclidean,
compute the inverse of e mod \(\phi(n)\):
d = 107
Write your hypothetical message:
Plaintext character encoded here as x = 10
Encrypt, producing ciphertext:
c = 103 mod 187 = 65
To decrypt C,
compute: D(c, e):
65107 mod 187 = 10
Some are public.
Some are secret.
n - the modulus
e - the public exponent
c - the cipher text
p - the prime factor of n
q - the other prime factor of n
\(\phi(n)\) - Euler’s totient of
n
d - the private exponent
+++++++++++++++++++++
Cahoot-08.2
Brute force:
Involves trying all possible private keys.
Mathematical attacks:
There are several approaches,
all equivalent in effort to factoring the product of two primes.
Timing attacks:
These extract statistics based on on analyzing the running time of the
decryption algorithm.
Chosen cipehrtext attacks:
This type of attack exploits properties of the RSA algorithm,
given some oracle,
which can produce arbitrary encrypted data for the attacker.
The easiest way we know how to break RSA is to factor n back into p *
q,
which is a prime factorization…
After that, given p and q, the attacker could just repeat the analytical
process,
that the legitimate owner of the key does during key generation,
in order to compute the private exponent d.
Fortunately, we don’t have an algorithm that can factor such large
numbers in reasonable time.
Unfortunately, we also haven’t proven it doesn’t exist.
Even more unfortunately, is that there is a theoretical algorithm,
called Shor’s algorithm,
that would be able to factor such a number in reasonable time on a
quantum computer.
There is another memristive solution (non-Turing),
implemented in application-specific hardware,
that can factor primes in polynomial resources (energy).
Right now, quantum and memristive solutions are far from
practical,
but it does appear that, if someone in the future manages to build one
sufficiently large,
that RSA becomes ineffective.
Ask and discuss:
Does this just break RSA, or other algorithms too?
RSA Labs (http://www.rsasecurity.com/rsalabs/) sponsored a challenge to factor some large n:
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
Progress in Factorization:
What is a modern size?
How much bigger and better is it?
https://en.wikipedia.org/wiki/Integer_factorization_records
+++++++++++++++++++++
Cahoot-08.3
Read on your own:
08-AsymmetricEncryption/cryptomath.py
08-AsymmetricEncryption/primeNum.py
Trace the important parts briefly in class:
08-AsymmetricEncryption/makePublicPrivateKeys.py
08-AsymmetricEncryption/publicKeyCipher.py
Ask:
What line does the encryption?
Hint:
$ python3
>>> help(pow)
pow(x, y, z=None)
Equivalent to x**y (with two arguments)
or x**y % z (with three arguments).
Some types, such as ints,
are able to use a more efficient algorithm,
when invoked using the three argument form.Ask and discuss:
How do you take a string like 'Hello RSA’ to a power??
In order to encrypt text or data,
it must be turned into a number.
A method with blocks is used above.
How the text is turned into a number differs by implementation,
and is conceptually independent of the core RSA algorithm,
though it impacts the security!
To make textbook RSA actually secure,
padding on the encoded plaintext must be used:
https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding
If your RSA key is compromised,
what happens to past communications?
Should you keep using the key?
Forward secrecy protects the past…
This is something of a misnomer.
https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
https://en.m.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
https://en.wikipedia.org/wiki/Discrete_logarithm_problem
https://en.m.wikipedia.org/wiki/Primitive_root_modulo_n
https://en.m.wikipedia.org/wiki/Generating_set_of_a_group
In modular arithmetic,
some number g, is a primitive root modulo n,
if every number, a, co-prime to n,
is congruent to a power of g modulo n.
That is, g is a primitive root modulo n,
if for every integer, a, co-prime to n,
there is an integer, k,
such that \(g^k \equiv a \mod n\).
For example, g = 3, mod 7:
Here we see that the period of 3k modulo 7 is 6.
The remainders in the period,
which are 3, 2, 6, 4, 5, 1,
form a rearrangement of all nonzero remainders modulo 7,
implying that g = 3 is indeed a primitive root modulo 7.
It was the first published public-key algorithm,
by Diffie and Hellman in 1976.
They first explained public key concepts.
It is used in a number of applications.
It is a practical method to exchange a secret key securely,
that can then be used for subsequent encryption of messages.
Security relies on difficulty of computing discrete logarithms.
Mention:
We previewed this “baby Diffie-Hellman idea before,
using nothing but exponents and log:
07-CryptoMath.html
Two people, Alice (A) annd Bob (B).
Example Public Parameters:
Prime number: q = 353
Primitive root of q: \(\alpha = 3\)
Example Private Parameters:
Alice randomly selects XA = 97
Bob randomly selects XB = 233
Alice and Bob each compute their public keys:
Alice computes YA = 397 mod 353 = 40
Bob computes YB = 3233 mod 353 = 248
Then exchange the public keys and compute secret key:
Alice:
\(K = (Y_B)^{X_A} \mod 353 = 248^{97} \mod 353
= 160\)
Bob:
\(K = (Y_A)^{X_B} \mod 353 = 40^{233} \mod 353
= 160\)
160 is the shared secret they both possess.
Diffie-Hellman Key Exchange, Generation and Computation
Diffie-Hellman Key Exchange
red = secret
blue = public
(against DH, RSA, or any other of these algorithms)
https://en.wikipedia.org/wiki/Man-in-the-middle_attack
Example of evil Eve in the middle:
1. Alice transmits YA to Bob.
2. Eve generates private keys XD1 and XD2, and
their public keys YD1 and YD2
3. Eve intercepts YA and transmits YD1 to
Bob.
4. Eve also calculates \(K2 =
(Y_A)^{X_{D2}}\)
5. Bob receives YD1 and calculates \(K1 = (Y_{D1})^{X_B}\)
6. Bob transmits YB to Alice
7. Eve intercepts YB and transmits YD2 to
Alice
8. Eve calculates \(K1 =
(Y_B)^{X_{D1}}\)
9. Alice receives YD2 and calculates \(K2 = (Y_{D2})^{X_A}\)
If Alice and Bob were using these DH secrets as single-session
private keys,
which communications are compromised, past, present, or future?
+++++++++++++++++++++
Cahoot-08.4
When setting up your web server:
Use DH-* with TLS for this nice feature:
https://en.wikipedia.org/wiki/Transport_Layer_Security#Key_exchange_or_key_agreement
More to come later.
Using something like super-Turing solutions:
Which algorithms would primarily be directly vulnerable,
symmetric or asymmetric?
Even if both are not, does it matter?
If you are interested:
https://www.youtube.com/watch?v=lvTqbM5Dq4Q
https://aip.scitation.org/doi/abs/10.1063/1.4975761
https://arxiv.org/pdf/1512.05064.pdf
Next: 09-ModernSymmetric.html