02 CryptoBasics Flashcards
(49 cards)
1
Q
Define Cryptology
A
Cryptology = Science concerned with communications in secure and usually secret form.
2
Q
Define Cryptography
A
Cryptography = Study of the principles and techniques by which information can be concealed in ciphertext and later revealed by a secret key.
3
Q
Define Cryptanalysis and its types
A
Cryptanalysis = The Science/process of recovering information (plaintext or key) from ciphers without the knowledge of the key.
Types:
- Ciphertext only (plaintext patterns in thecipher)
- Known ciphertext/plaintext pairs
- Chosen plaintext/ciphertext
4
Q
What is the Encryption of data?
A
The process of transforming plaintext data into ciphertext to conceal it’s meaning.
5
Q
What is the Signing of data?
A
Computing a “check value” or “digital signature” to a cipher/plaintext, that can be verified by some or all entities able to access the signed data.
6
Q
Describe the principal categories of cryptographic algorithms:
A
-
Symmetric cryptography (1 key)
- Modes of Operation
- DES
- AES
-
Asymmetric cryptography (2 keys)
- RSA
Diffie-Hellman - ElGamal
- RSA
-
Cryptographic hash functions (0 key, appended/mixed with data)
- MDC’s & MAC’s
- MD-5
- SHA-1
- CBC-MAC
7
Q
Graphically describe the Cryptographic Algorithms outline:
A
8
Q
What is the aim of the Cryptanalysis of public keys?
A
Public key cryptanalysis aim at breaking the cryptosystem itself through mathematical research.
9
Q
What does a Brute Force Attack does?
A
A brute force attack tries every possible key until it finds an intelligible plaintext.
Every cryptographic algorithm (in theory can be attacked by brute force). On average, 50% of possible keys will have to be tried.
10
Q
What is Error propagation?
A
Error propagation characterizes the effects of bit-errors during transmission of ciphertext to reconstructed plaintext.
An erroneous ciphertext bit could produce 1 or more erroneous plaintext bits.
11
Q
What is Synchronization?
A
Synchronization characterizes the effects of lost ciphertext data units to the reconstructed plaintext.
Some algorithms need explicit synchronization (can’t recover from lost ciphertext). Other algorithms automatically re-synchronize after 0 to n ciphertext bits.
12
Q
What is Substitution?
A
Mapping each element (bit, letter, groups of bits/letters) in the plaintext into another element.
13
Q
What is Transposition?
A
Re-arranging elements in the plaintext.
14
Q
What is the main difference between Stream ciphers and Block ciphers?
A
Stream ciphers work on bit streams (encrypting one bit after another). Based on linear feedback shift registers. They don’t propagate errors but are sensible to loss of synchronization.
Block ciphers work on blocks of width b. They handle errors and synchronization in different ways.
15
Q
What are Modes of Operation?
A
Ways of using a block cipher (of b-lenght) for encryption.
16
Q
How do stream ciphers encrypt a message?
A
They encrypt the digits of a message one at a time.
17
Q
How does block ciphers encrypt?
A
Taking a chunk/number of bits and encrypt them as single units, padding them to have a multiple of the block size.
18
Q
What are the types of cryptanalysis?
A
- Ciphertext only
- Known ciphertext/plaintext pairs
- Chosen plaintext
- Chosen ciphertext
- Differential cryptanalysis
- Linear cryptanalysis
19
Q
What is the aim of the cryptanalysis of public key cryptography?
A
- One key is publicly exposed, the aim is to break the cryptosystem itself.
- Usage of computation of discrete logarithms or the factorization of large integers.
20
Q
Describe the key elements of Symmetric Encryption:
A
- P denotes a plaintext message
- E(KA,B, P) denotes a ciphertext creation
- D(KA,B, E(KA,B, P)) = P denotes the decryption process.
21
Q
What is ECB and describe how it works:
A
ECB = Electronic Code Book Mode.
- Every block pi of length b is encrypted independently ci =E(K, pi).
- A bit error in ciphertext block ci= wrongly recovered plaintext pi’
- Loss of sync doesn’t affect if integer multiples of the block size b are lost.
- Drawback = identical plaintext blocks are encrypted to identical ciphertext! (direct encryption and decryption)
22
Q
What is CBC and describe how it works:
A
CBC = Cipher Block Chaining Mode.
- Before encrypting a plaintext block pi it is XORed with the previous ciphertext block ci-1.
- Parties agree on an Initialization Vector (IV) for C0.
- A distorted ciphertext block results in two distorted plaintext blocks.
- If the number of lost bits is a multiple integer of b, one additional block pi+1 is distorted before synchronization is re-established.
- Advantage = identical plaintext blocks don’t produce identical ciphertext.
23
Q
How is the decryption process in CBC?
A
In CBC, decryption is the inverted process of the encryption steps:
- C1 is taken as an input and K is applied to decrypt it, the result is XORed with the IV to recover P1
- C2 is taken as an input and K is applied to decrypt it, the result is XORed with C1 (previous step) to produce P2
- Cn is taken as an input and K is applied to decrypt it, the result is XORed with Cn-1 to obtain Pn
24
Q
What is CFB and describe how it works:
A
CFB = Ciphertext Feedback Mode.
- A block encryption algorithm working on block size b is converted to an algorithm working on blocks size j (where j is the previous Ciphertext)
- The IV is encrypted with K and a “select-discard” (the b-j right-hand bits) is done to have just a j which is exactly the size of the first part P1.
- P1 is now XORed and then taken to the next operations (Time=2) to conform: R1 (or IV1) = shifted IV0+C1
- The process continues with that new input in T=2 to be Encrypted with K and so on..
25
How is the **decryption** process in **CFB**?
* **Time 1:** The IV is shifted to the left and then encrypted using K
* The encrypted right-part (b-j) is discarded and the remaining left-part j is XORed with C1j to produce P1
* **Time 2** The IV is shifted j-places to the left and complemented with C1
* The result is encrypted using K and then the right-part (b-j) is discarded
* The remaining left-part j is XORed with C2j to produce P2
26
What is **OFB** and describe how it works:
**OFB** = Output Feedback Mode
* It operates in a very similar way to CFB but takes the output "j" after the select-discards as the complement of the next Shifted-Register, instead of the C1.
* The process keeps working in a similar way, every time the "j" part of the output is taken as the next input.
* This chain can be **precomputed** and then just the XORed parts be applied to gain speed in transmission.
* Message **cannot be selectively encrypted/decrypted**.
27
How is the decryption process in **OFB**?
Almost exactly the same of the encryption process, except that the XOR part is applied to the Cn to produce Pn (**reversing the XOR**).
28
What is **DES** and what are some key **characteristics** of it?
**DES = Data Encryption Standard.**
* A cryptographic algorithm.
* Accepted by the NBS (National Bureau of Standards, now **NIST** National Institute of Standards and Technology) through a contest.
* Decided to have a **block size of 64 bits** and a **key size of 56 bits**
29
How does **DES** works? (**iterations**)
* The initial plaintext (64 bits) is processed through a permutation. It is then processed through **16 iterations**. Then it has a 32 bit swap and an inverse initial permutation.
* In one single iteration (1/16):
* The right-hand 32 bit of the data to be encrypted are **expanded** to 48 bits with a expansion/permutation table.
* This matches the **56-bit key** that is divided in two 28 bit parts that receive a **left shift** to later be **contracted to 48 bits**.
* The previously expanded 48 bits of data and contracted 48 bits of shifted keys are **XORed**, this result is placed in a **substitution box** that produces **32 bits output**.
* These 32 bits are **permuted and later XORed with the left-hand side** part of the original data block of size 64 to form **the new right-hand 32 bit of data**.
* The **new left-hand 32 bits are the right-hand value** of the previous iteration (original right side of plain-text in this case).
* The **decryption** process is essentially the same, although a**pplying the subkeys in reverse** order and using the **ciphertext as input**.
30
What are key characteristics of a **Feistel Network**? (org. of data and equations).
Feistel networks are a specific **construction for designing symmetric encryption schemes**.
It splits the data into **two halfs** and organize the encryption using the equations:
**Li** = Ri-1
**Ri** = Li-1 XOR **f (Ri-1, Ki)**
31
What are some key **weaknesses** of **DES**?
* As a whole **64-bit keys are weak.**
* Weak keys = **4 keys** are weak as they generate **subkeys with either all 0 or 1s**
* Semiweak keys = **6 pairs of keys** which **encrypt plaintext to identical ciphertext** (generate only two dif. subkeys).
* Possibly weak keys = 48 keys that generate only four different subkeys.
* The **key length** of DES (56 bits) is considered **too short** and no longer as sufficiently secure.
32
What does **Differential cryptanalysis** does?
Looks specifically for **differences in ciphertexts** whose plaintexts have particular differences and tries to guess the correct key from this.
Basic approach requires chosen plaintext with its ciphertext.
33
What is **AES** and what are some key **characteristics** of it?
**AES = Advanced Encryption Standard**, also known as Rijndael (pronounced **Rhine Dahl**).
It has a **block size of 128 bits** but three different **key lengths: 128, 192 and 256 bits.**
34
How does **AES** works?
* AES is based on a **substitution-permutation network** (combination of both substitution and permutation).
* Can be described as a **large matrix operation**.
* **Doesn't use a Feistel structure** (different encryption and decryption functions).
* Use of different operations: **ByteSub** (S-box) **ShiftRow** **MixColumn** **RoundKey** (XORed)
* Key size: **128, 192 or 256 bits.**
35
What is the general idea of **Public-Key Cryptography**?
* Public Crypto uses t**wo different keys K+ and K-** for encryption and decryption. C={P}K+ K- private key K+ public key (unsecured exchanged)
* Shouldn't be feasible to compute K- with K+
* Encrypted with **K+ = normal encryption**.
* Encrypted with **K- = signing (public reading)**. "Cross-exchange of encrypted messages".
36
Graphically explain the general idea of Public Key Cryptography:
37
* What are requirements of Asymmetric Crypto-Systems?
* **Difficulty** (**independent** existence of K+ and K- although both can **encrypt**).
* **Low computational overhead** (encryption/decryption not computational expensive).
* **Low memory overhead** (en/decryption not causing too much memory overhead).
* **Low message expansion** (encrypted data should not be too long).
* **Variable and manageable key length**.
38
What is the **math problem analogy with Asymmetric Crypto-Systems**?
Taking a math/CS problem **hard to solve with K+** but **easy when knowing K-**
Secured problems used:
* Discrete logarithm
* Factorization
* Elliptic Curves
39
RSA related: what are the basics of the **Euclidian algorithm**?
It can be used to **find the biggest number that divides two other numbers** (**gcd**, greatest common divisor).
40
RSA related: what are the **basics of the Extended Euclidean algorithm**?
An extension to the Euclidean algorithm, **besides the gcd** of a and b, computes the coeficients (integers) x and y such that the **identity ax + by = gcd(a,b)** is created
41
RSA related: what are the basics of the **Euler function**?
The **totient (phi (n))** of a positive integer is the number of integers less than the number which are coprime to n (they share no factors).
To assure secrecy calculating the private key the totient of (n) -\> phi(n) is used.
Example to set up a key pair for RSA:
p= 17 q=11
n= p x q = 17x11 = 187
totient(n) = (p-1) x (q-1) = 16 x 10 = 160
e relatively prime to "totient(n) = 160" and "e \< totient(n)"
e = 7 is chosen
determine d, so dxe := 1 mod 160
d= 23 as 23x7 = 161 = (1 x 160) +1
K+ = (e,n) = (17, 187)
K- = (d,n) = (23, 187)
42
RSA related: what are the basics of the **Chinese remainder theorem**?
In its basic form, the Chinese remainder theorem will determine a **number n that, when divided by some given divisors, leaves given remainders.**
For example, what is the lowest number n that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2?
43
What is the **pseudo** code of the **Euclidean algorithm**?
int Euclid (int a,b)
{ if (b=0) return (a)
else return Euclid (b, a mod b) }
44
What are the **characteristics of the RSA algorithm**?
* It is an asymmetric cryptographic algorithm. (or public key cryptography K+ and K-).
* **Based on the fact that finding the factors of an integer is hard (factoring problem).**
* Using RSA means **creating and publishing the product of two large prime numbers**, along with an auxiliary value as their public key. The **prime factors must be kept secret.**
45
Describe the mode of operation of RSA:
* n = p x q
* e x d ::: 1 mod phi(n)
Where: p,q primes
M message
K+ the pair (e,n)
K- the pair (d,n)
Encrypt E = M^e mod n Decrypt M' = E^d mod n
46
What are some **security** considerations and **implications of RSA**?
* The security of RSA lies in the **difficulty of factoring n = p x q**
* **P and q** should be same bit length and **sufficiently large**
* Truly **random generation** of primes P and q is required!
* No proof that integer factorization is actually difficult.
* There is a lot of mathematical research in primality testing and factorization.
* **Integer factorization is becoming faster over time.**
* RSA with short key-sizes has already been broken (\<1024 bits) thanks to improving computational power (**1024-2048 bit keys is recommended**).
* Quantum computers (and Moore's law) will aid to break RSA
47
What are the basics of the **Diffie-Hellman key exchange** and how it works?
* It is a way of generating a shared secret between two parties A and B in such a form that the secret can't be seen by observing the communications. --\> Creating a key together.
* The key is not saved, transmitted or visible in the communication channel.
* Two parties generate two prime numbers and exchange them.
* Both parties pick a secret number and solve a discrete logarithm using them with shared prime numbers. Their results of this operation are exchanged.
* Both parties now solve a discrete logarithm, this time using their partner's results and one of the prime numbers.
* After performing that last step, both parties arrive to the same shared key.
Other explanation:
* It enables two parties A and B to agree upon a shared secret (secret key) using a public channel.
* This key is later used in a symmetric-key cipher.
1. A and B agree upon values p and g
2. Parties compute v and w
* A computes v = g^q MOD p and sends B:{p,g,v}
* B computes w = g^r MOD p and sends A:{p,g,w}
3. Both parties compute the common secret using v and w
* A computes s = w^q MOD p
* B computes s' = v^r MOD p
4. Now they have the same shared secret.
48
Describe the **man-in-the-middle attack of the Diffie-Hellman Key Exchange** and a some countermeasures:
* A third party C could **intercept** messages over the public channel and decrypt and re-encrypt them before **forwarding** them to A and B.
* **Countermeasures**:
* The **shared secret is authenticated** after being agreed upon.
* A and B use an **interlock protocol** (checkable messages, **split messages** in 2 parts and **send the 2nd part first**).
* The used encryption algorithm makes it hard to encrypt the the 2nd part without the 1st part.
* C needs to invent messages and can be detected.
49
What are the most practical **algorithms that are still considered to be secure**?
**RSA** (based on the difficulty of factoring, with \> 1024-bits key lenght)
**Diffie-Hellman** (it is actually a key agreement protocol, not an asymmetric algorithm).
**ElGamal** (like DH based on difficulty of computing discrete logarithms).
