Final Exam Prep Flashcards
1
Q
Cryptanalysis
A
Science of breaking crypto systems
2
Q
Symmetric Algorithm
A
Two parties, each with a decryption and encryption method for which they share a secret key
3
Q
Asymmetric Algorithm origin
A
Introduced in 1976 by Diffie, Hellman and Merkle
4
Q
What is an asymmetric Algorithm
A
Each user has their own secret key which they use to encrypt and a public key
5
Q
What is the substitution cipher?
A
Each letter is substituted with a different letter
6
Q
What is Kerckoff’s principle?
A
The idea that security should rely only on the key secrecy. The encryption algorithm is public knowledge to allow for ethical hacker feedback
7
Q
Explain unconditional security
A
A cryptographic strength such that no matter how much computing power or time you have it can never be cracked
8
Q
Explain Computational security
A
Given limited resources the cipher cannot be broken - e.g. it would take 1 billion years for a normal computer to crack through brute force
9
Q
What is the ideal cryptographic strength?
A
An algorithm that requires brute force search through the key space. Means that for keys of 128 bits it would take approximately 18 years to crack if you were testing a key every microsecond
10
Q
Ciphertext only cryptographic attack
A
Attacker only has access to the cipher text and no additional information
11
Q
Known-plaintext attack
A
When the attacker has access to cipher text and corresponding plaintext for some parts of the cipher text
12
Q
Chosen-plaintext attack
A
Attacker can choose arbitrary plaintexts and obtain their corresponding ciphertexts
13
Q
Chosen-ciphertext attack
A
Attacker can choose ciphertext and obtain the corresponding plaintext
14
Q
What are the 4 properties of a group?
A
- closure -> if a is an element of the group then a*b is as well
- Associativity -> a (bc) = b(ac)
- identity element -> there exists an element in the group such that ea = ae contained in G
- Inverse element -> for all a in the group there is an a’ such that a is contained in G and aa’ = a’a=e
- any inverse with its negative results in the identity element
15
Q
What makes a group Ableian?
A
Commutativity - you can do the operations in any order and get the same answer (ab = ba) for all ab
- Always true with integers
16
Q
What is a cyclic group?
A
generated by a single element called a generator (every element is a power of the generator) - 0,1 not elements of cyclic
e.g. for all {0,1,2,3,4} mod 5
- 2 is a generator because it can make all other elements -> 2,4,3,1,2
17
Q
What is a ring
A
a group but it needs to satisfy rules for both addition and multiplication
Addition - closure: adding 2 elements in R gives another element in R, identity element: a+0 = a for any element in a
18
Q
What makes a ring commutative?
A
if multiplication is commutative -> meaning ab =ba for all a and b
19
Q
what is an integral domain
A
Special type of commutative ring that satisfies 2 properties
1. there is a special element 1 in R such that multiplying any element by 1 doesn’t change it
2. if you multiply 2 elements and the result is 0 one of the elements is 0
20
Q
What is a field
A
An integral domain but there must be a multiplicative inverse for every element
a/b = a*b^-1 -> basically just adds division as a possibility
21
Q
What is a finite field?
A
A field with a finite number of elements
22
Q
What does relatively prime mean?
A
Numbers with no common factors with each other -> if modulo and a number are relatively prime than that number has a multiplicative inverse
23
Q
What is a Galois Field?
A
Another name for a finite field - it has an order which is the number of elements it contains
-> the order is always a prime number or prime power
-> for every prime number p and every positive integer k, there are fields order p^K
24
Q
What is Fermat’s Little Theorem?
A
if p is prime and a is a positive integer not divisible by p then
- a^(p-1) = 1 mod p
- a^p = a mod p
25
What are the two requirements for a strong Symmetric encryption algorithm?
1. A strong encryption algorithm that cannot be broken even if an opponent knows the algorithm and ciphertexts
2. A secure key
26
What is the brute force method and how many possible keys does it normally take?
Attacker tries every possible key one by one on ciphertext until the plaintext is found
- it takes half the possible keys in the keyspace on average to succeed
27
What is a caesar cipher and how do you crack it?
Where the letters are shifted by 1-25 places, the cryptanalysis is just brute force trying all 25 different keys
28
What is a monoalphabetic Cipher and how would one crack it?
Caesar but instead of shifting it, each letter is individually substituted with another one
- permutation of 26! possibilities which is computationally secure but letter frequency analysis can be used to crack this
29
What is a playfair Cipher?
Treats digrams (2 letters together) as single units and translates these units into ciphertext digrams
- done using a 5x5 matrix of letters structured using a keyword and the letters are made into digrams from the matrix, creating 26x26 possible combos instead of just 26
30
What is a hill Cipher?
Cipher developed by lester Hill which uses matrices and row vectors
- C = PK mod 26
where plaintext and cipher text are length 3 row vectors (e.g.(1, 2, 3)) and the key is a 3x3 matrix
31
What is a polyalphabetic cipher?
Essentially a set of related monoalphabetic substitution rules is used and a key determines which particular rule is chosen
32
What is the Vigenere Cipher?
polyalphabetic cipher where a set of related monoalphabetic substitution rules consists of the 26 Caesar ciphers with shifts 0-25
The first letter of the key is added to first letter of the plaintext mod 26, and so on until the key length is reached and then it is repeated
C1 = (p1 + k1mod m) mod 26
33
How is a Vigenere cipher broken?
Progress depends on determining the length of the keyword in order to look for repeats and ultimately determine the key. A way to strengthen a bit that is still vulnerable is to have the message become the key after the key is elapsed e.g. if key is fuck and message is "thiscourse"
key: fuckthisco added to plaintext thiscourse
34
What is a vernan cipher
An extension to the vigenere cipher but the keyword is as long as the plaintext but has no statistical relationship. uses a key stream generator which is xor'ed with the message bits to create the ciphertext
35
What is the One-time pad?
Vernam cipher but the random key is as long as the cipher. this makes it unbreakable to cryptanalysis as it produces random ciphertext with no statistical relationship to the plaintext
Even brute force doesn't work
36
What are the issues with the one-time pad?
1. making a truly random keys is difficult
2. Key distribution and protection is difficult since the keys must be very large if the message is
37
What a transposition cipher?
A permuatation on the plaintext letters.
e.g. rail fence -> plaintext is written as a sequence of diagonals and then read off as a sequence of rows
This philosiphy is taken further and the letters are written in rows, the rows are than moved around and the key is the order that the rows are displayed in
38
What is the rotor machine?
It uses a number of rotating cylinders, the cylinders have a connection in them for each of the letters with the output pins of a rotor connecting with the input pins of the next rotor
e.g. 5 rotor is 26^5 different alphabets
39
What is a stream cipher?
Encrypts data one bit or byte at a time
- it is a branch of symmetrical ciphers that uses a psuedorandom bit generator to produce a string of seemingly random bits called the keystream, the keystream is then xor'ed with the plaintext
40
What is RC4
A well known stream cipher with a key length of 1-256 bits
41
How long does it take to find a prime
primes near n are spaced every ln(n) numbers so using an existing known prime you need to test 1/2(ln(n)) numbers
e.g. 2^200 = 0.5(ln(2^200))
42
What is a claude shannon?
An approach to encryption where one alternates between substitution and permutation
43
What are the two distinct features of claude Shannon?
Diffusion - aims to spread the influence of each plaintext digit over many ciphertext ones
Confusion - seeks to make the relationship between key and cipher text as complex as possible to make determining statistical patterns difficult
44
What is an S-P Network?
An implementation of claude shannon using S-boxes which alternate between permuation and substitutions to map an n bit input block to an m-bit output one
Goes substitution -> permutation -> xor with key
45
What part of an s-p network is responsible for diffusion?
the avalanche effect creates diffusion -> changing one bit changes half the output bits and if this happens multiple times it is very hard to track
46
What part of an s-p network is responsible for confusion?
Same as diffusion changing one bit changes several of the round keys and with every change diffusing over multiple rounds it creates confusion
47
Explain the avalanche effect and where it holds
Changing any single bit of the input can change up to half the output bits
- it holds if each s-box is designed so that if a single bit changes in the input at least 2 outputs will change and the permutation layers are designed so any output bits of any s-box are input to different s-boxes in the next layer
48
what is the calculation for how many output bits change from a single input bit change?
2^r where r is the number of rounds
49
What is double DES?
Exactly what it sounds like, you perform DES on the output of another DES using a second key
- key length of 112 bits (2x 52)
50
Explain the details of a Feistel network (e.g. round size...)
Key length: k bits
block length: n bits
transformations: 2^k possible transformations
51
What is the encryption process of a feistel network?
Left3 = L1 ⊕ f(r1)
= R0 ⊕ f(L0 ⊕ f(r1))
R3 = L0 ⊕ f(r0)
52
What is the Data Encryption Standard (DES)?
NSA asked public for a standardized algorithm to transmit sensitive information. they selected fiestels but made modifications
53
What is the criteria of DES?
1. 64 bit plaintext -> 56 bit key for the s-boxes
2. No output bit of any s-box is close to a linear function of the input bits
3. each s-box row should include all 16 possible outputs
4. for any nonzero 6 bit difference between inputs no more than 8 of the 32 pairs of inputs exhibiting that difference may result in the same output difference
5. if 2 inputs differ by exactly one bit the output must differ by >= 2
54
How does a differential Cryptanalysis attack work
only works if the attacker can choose specific plaintext messages and obtain the corresponding cipher text
- It analyzes the differences between plaintext and cipher pairs to identify patterns and hopefully recover the key
55
How does Linear Cryptanalysis work?
Analyzes a large number of pt-ct pairs to find linear approximations of the non-linear parts of the cipher
- by exploiting approximations the attacker might be able to deduce key bits or other information
56
57
What are the problems with DES
It has the same problems as single DES if a K3 that provides the same output as the double des is found. It is vulnerable to a meet in the middle attack where given plaintext p and cipher text c:
encrypt p for all possible K1 and decrypt c for all possible key 2 and see if they line up
58
What is Triple DES (3 DES)
Either encrypts 3 times with 3 keys or, encrypts, decrypts and then encrypts again using DES. It has a brute force attack cost of 2^112
59
What is Advanced Encryption standard (AES)
specification for the encryption of data established by the US national institute of standards and technology in 2001
- much stronger than DES
60
What are the different types of AES and their corresponding round
Key lengths of 128, 192 or 256
- block cipher encrypts data in blocks of 128 bits
- 128 bit key = 10 rounds
- 192 = 12 rounds
- 256 = 14 rounds
61
How does AES work
Uses different number of rounds -> each round has a unique key derived from a main key
- operates in 128 bit blocks returning ciphertext of the same length
62
What are the four steps for each round of AES?
AES considers a 16 byte grid in matrix column arrangement
1. Subbytes -> each byte is substituted with another
2. ShiftRows -> left circular shift with each row doing an extra shift (R1+0, R2+1, R3+2, R4+3)
3. MixColumns -> each column is multiplied by a specific matrix thus position of each byte changes
4. RoundKey -> output of previous stage XOR with roundkey
63
What are the five modes of operation for block ciphers created by the NIST
Electronic codebook (ECB)
Cipher Block Chaining (CBC)
Cipher Feedback (CFB)
Output Feedback (OFB)
Counter (CTR)
64
What is ECB
A block cipher mode of operation: each block of plaintex bits is encoded independently using the same key
65
What is Cipher Block chaining?
The input to the encryption algorithm is the XOR of the next block of plaintext and the previous block of ciphertext. Initialization vector is used for the first block since there is no preceding cipher text
66
What is cipher feedback
Input is processed s bits at a time. preceding ciphertext is used as input to the encryption to produce psuedorandom output which is xored with the plaintext to produce the next unit of ciphertext
67
Output Feedback
Similar to CFB except that the input to the encryption algorithm is the preceding encryption output. Full blocks are used
68
What is counter (CTR)
- converts the block cipher into a stream cipher
each block of plaintext is XORed with an encrypted counter. the counter is then incremented for each block
69
What are the uses of ECB?
Should only be used to secure messages shorter than a single block of underlying cipher such as to encrypt a secret key -> vulnerabilities are created since it is the same key per block if and will return the same encoded phrase if it is present in both parts of the message
70
What is a Linear Congruent Generator?
A psuedo-random number generator, but it is very poor for cryptography because it is extremely predictable if the attacker finds the parameters
71
What is counter mode used for?
Psuedo random number generation -> should use double DES or greater key space
- if the master key is protected it is computationally infeasible to predict subsequent values
72
What is a Blum Blum Shub (BBS) Generator?
A publicly proven random number generator
1. Choose primes p and q where both are equivalent to 3 mod 4.
2. Compute n = p*q
3. choose s -> relatively prime to n
4. for each digit xi = x^2_(i-1)mod n and the return value bi = xi mod 2
73
What are the four methods of symmetric key distribution?
1. physical delivery
2. trusted 3rd party physical delivery
3. use previously shared key to send next one
4. trusted online authority
74
What is kerberos and how does it work?
Kerberos is a key distribution system
If Alice wants to send a key to bob:
1. alice asks kerberos to gen key for Alice bob
2. Kerb sends alice key which she uses to encrypt
3. bob receives alice's key
4. Bob asks kerberos for key and uses it to decrypt
75
What is symmetric key partitioning?
When a key is broken into shares, all of which are required for it to be used.
76
What is the idea behind Diffie-Hellman?
Introduction to public key cryptography: an alternate method of key distribution which proposes signing with a private key and verifying with a public one.
-> all can encrypt for u but only you can decrypt
-> all can verify your signature but only u can sign
77
What are the four requirements for Public key Cryptography?
1. key generation is computationally easy
2. decryption and encryption computationally easy
3. Infeasible to compute/derive private from public
4. infeasible to compute/derive message knowing public key and ciphertext
78
What is a one way function?
A function that has an inverse but calculating the inverse is computationally infeasible
79
What is a trap-door one-way function?
Inverse is infeasible unless additional info is known (e.g. key)
80
What is RSA and how does it work?
first published algorithm for public key cryptography that could encrypt and decrypt
Given a message m, where m is an integer:
- c= m^2 mod n
- c^d mod n = (m^e)^d mod n = m^{ed} mod n
where m = pt, c = ct, e = public key and d = private key
81
What is RSA security based upon?
It is based upon how difficult it is to factor n -> with n being the multiplication of two primes
81
How is RSA implemented efficiently?
Using a small base with exponent for the public key and using chinese remainder theorem for the private key -> using miller rabin to find probabilistic p and q primes
81
What is RSA with optimal Asymmetric Encryption Padding (OAEP)
A process to ensure that plaintexts are randomized before encryption to prevent chosen ciphertext attacks:
1. message is padded with bits to meet desired length
2. Random seed r is generated
3. two has-based masks, on masking the message and the other the seed
81
What are the 4 different attacks on RSA and how are they stopped?
1. Brute force -> large key negates
2. mathematical attack to find d by factoring n into p and q but factoring that has not been discovered yet
3. Timing attack, time the computational time to find 1's in d
4. Chosen ciphertext attack
82
What are the advantages and limitations of RSA with OAEP
Advantages
1. random seed r ensures unique ciphertext even for same plaintext
2. prevents chosen ciphertext
Limitations
1. computationally intensive
2. relies on integer factorization hardness
83
What is Eliptic Curve Cryptography?
A method of encryption that provides the same level of security as RSA with considerably shorter operands
- based on generalized discreate logarithm problem
84
What are elliptic curves?
A set of points satisfying a specific equation:
y^2 = x^3 + ax + b
- Points on the curve form an abelian group under addition
- if P and Q are on the curve so too is R= P+Q
85
Why use elliptic curves?
Given P and Q = kp finding k is computationally infeasible for larger curves and k is the randomly chosen scalar k
86
What are the 5 methods of Asymmetric Key Distribution?
1. Announcement - tell all public key
2. Directory - publish on a repo
3. Online Authority - another party controls distribution
4. Certificates - data structure containing an identifier of a user and that users public key signed by an authority
5. Diffie-Hellman
87
What is the announcement method and what are its issues?
Tell all public key
problems -> intended receiver might not see message and malicious other might replace message and private key
88
What is the online authority method and its issues?
A online party controls key distribution (e.g. kerberos)
- issues with workload and you need to completely trust online auth
89
What is the certificates method?
A data structure containing an identifier of a user (e.g. digital signature) and the users public key signed off on by an auth
- both an issue and a strength is you only need 1 authorize private key to access all private keys
90
What is diffie-hellman protocol
take a prime p and a primitive root g
1. Alice choose n_A and computes y_A = g^(n_a) mod p
2. Bob choose n_B and computes y_B = g^(n_b) mod p
3. alice computes k = (y_B?)^n_a mod p
4. Bob computes k = (y_A)^n_b mod p -> k is same
91
What is the primitive root of a number?
g is primitive root mod n if every number a coprime to n is congruent to a power of g mod n
e.g. there is some integer k for which g^k == a (mod n)
3 is a primitive root of mod 7 because:
3^1 = 3 mod 7
3^2 = 2 mod 7
3^3 = 6 mod 7
3^4 = 4 mod 7
3^5 = 5 mod 7
3^6 = 1 mod 7
All possible values are covered meaning 3
92
What is public key Infrastructure (PKI)?
set of hardware, software, policies and people needed to create, manage store and distribute digital certificates
93
What are the main elements of IETF PKIX (public key infrastructure x.509)
1. End entity -> anything needing certification
2. Certification authority (ca) -> entity to create and manage certifications
3. Registration authority (ra) -> checks certifications
4. CRL (certificate relocation list) --> displays a list of valid certifications that shouldn't be trusted anymore
5. Repository -> place to save info
94
What is the miller rabin algorithm?
An algorithm to determine if a number is a probabilistic prime
1. Find integers k, q with k>0, q odd so that:
n-1 = 2^k q
2. select random integers a, 1
95
What are the management functions of IETF PKIX?
registration
initialization -> get cert of target
certification
key pair/certificate update
revocation
cross-certification
private key backup
96
What is Attribute based encryption?
Encrypting based on attributes -> for system administration
e.g. an IT guy getting a different encryption than the HR rep
97
What is fully-Homorphic Encryption
When a message is sent already encrypted to a target which verifies the identity of the sender and sends it to the correct person
- Data is never decrypted
98
What is Broadcast encryption?
Basically netflix, they broadcast a signal which everyone can see but only certain people with the correct key can decrypt
99
What is oblivious transfer?
Sending a random item to someone else
-> say you have 5 messages, you transmit all of them and Alice accepts 1 but bob doesnt know which she accepted
100
What is a cryptographic hash function?
A function which accepts a message and produces a fixed size output smaller than the input - output called hash code/checksum/hash value
101
What are the requirements of a hash function?
h = H(m) -> easy to compute
for any h (output) its computationally infeasible to find m such that h(m) = h
102
What is the upper bound security of the hash function?
2^(m/2)
103
What is the birthday paradox?
a way of expressing the collision issue in hash functions. It asks what the minimum value of k is such that the probability of at least 2 people in a group having the same birthday
-> gives we want to use at least 80 bits for a hash function
104
What is the general structure of a has function?
Input data is divided into n bit blocks and each block is processed iteratively to produce an n-bit hash
105
What does improving a hash function with rotation do?
Introduces one-bit circular left shit before each block
-> increases randomness but still weak
106
For a hash code with a length n, with input messages of length b what are the total number of messages and has values?
total possible messages: 2^b
total possible hash values: 2^n
Average has value corresponds to 2^(b-n) preimages
107
What is a preimage in a hash function?
if h = H(x) -> x is the preimage
a hash function maps multiple inputs to the same output
108
What are the 5 security requirements for Crypto hash functions?
1. Practical properties - produces fixed length output regardless of input and same input always yields same output
2. Preimage resistant - one way
3. Second preimage resistance - given m it should be impossible to find another message that produces the same hash
4. Collision resistance - cant find 2 distinct messages with same hash
5. psuedorandomness - should appear random
109
What is the compression function and why is it important to security?
The compression function compresses the larger input into a smaller output, hopefully without collision -> it is important that this function makes it computationally infeasible to find collisions because collisions allow cryptanalysis of the hash function structure and from that maybe message retrieval
110
There is a hash function implementation using CBC what are the vulnerabilities of this?
Birthday attack -> looks for collisions
Meet in the middle attack -> variant of birthday but the attacker forges a message with the same hash code
111
Why use message authentication?
To prevent masquerade or modding of message
- prevent source or destination repudiation
2 Techniques:
- MAC
- Digital Signature
112
How does Symmetric MAC work?
uses a secret key to generate a small, fixed-size block of data that is appended to the message
- messages plus MAC are transmitted to the intended recipient
-the recipient then computes a new mac on the message using a secret key and compares the two
- IFF MACs are same there was no tampering, it came from Alice
113
Size of MAC message (Symmetric)?
msg = N, MAC = n, key = k
N>n and N>k
-if k>n attacker might need to do several rounds in order to find the correct key
if k = an -> an attacker needs a pairs e.g. 80 bit key 32 bit MAC 1rst pair 2^48, second 2^16, 3rd 1
if k
114
MAC constructions?
DES based MAC in CBC mode with an initialization of zero - it is widely used but ends up encrypting entire message twice if confidentiality is required
MAC based on hash function - HMAC (e.g. all the SHA algorithms)
115
What is the HMAC algorithm?
HMAC(k,m) = H[key⊕opad || H [(k⊕ipad|m]] where opad = outerpad, ipad = innerpad
if b is the size of block in hash, then k is padded with 0's so the result is b bits length
116
What is a digital signature?
Similar to MAC's but it prevents repudiation due to its assymetry
1. Arbitrated -> every signed message goes through an arbiter who checks the origin and content which lowers repudiation risk -> must trust arbiter and can have bottleneck
2. Direct -> send right to receiver but increases risks unless timestamps are implemented
117
How does RSA work for digital signatures?
public key = (e, n), private key = d
instead of e = m^e mod n Alice computes s = m^d mod n -> sign
Bob receives this and tests if s^e mod n = m
118
What are the attacks on RSA Digital signatures?
No message attack - Eve obtains D's public key and sends a random message impersonating someone
Forging a signature on arbitrary message - Eve chooses random m and sets m_2 = m/m_1 mod n_d then eve gets D to sign m1 and m2 to obtain s1 s2
119
What is the Digital Signature Standard (DSS)
A us government standard published by NIST in 1991 with revisions in 2000 -> it is DSA standards using SHA-1 to hash - security is based entirely on computing discrete log
120
What are blind signatures?
Sam provides a signing service
Alice wants message signed but wants it secret
-> alice chooses random # r and computes m' = mr^e mod n which completely hides m
->Sam then blind signs m'
121
What are malleable signatures?
A signature that for a given message and signature it is possible to modify the signature to be valid based on a related signature without using the private signing key
122
what is One-way authentication?
It establishes the identity of A that generates the message and maintains integrity using time stamp
123
Two-way authentication?
In addition to the properties of one way it establishes the identity of the receiver and provides mutual authentication
124
Three-way authentication
Same functionality as two-way but it doesn't require timestamps
125
Authenticated Encryption
Authenticates then adds MAC, or MAC then encrypt
126
What is a passive attack model?
It can read data and do stuff online
127
Active attack model?
Reads data and can modify it in transit
128
Meet in the middle attacker?
can insert into middle of convo and be passive or active
129
Honest-but-curious attacker model?
follow all protocol and learn things they aren't supposed to within the bounds
130
Fail-stop attacker model?
stops early in communication protocol if they think it gives them advantage
131
Malicious attacker?
opposite of honest-but-curious they do anything to get an advantage
132
Byzantine attacker model?
Super generalized and basically useless because you would rather use a specialized tool than one that does everything ok
133
2 types of crypto problems?
1. math problems
2. complex mapping of I/O
134
Two approaches to security strength?
Approach 1 -> very powerful but polynomially bounded - assume computational bounding
Approach 2 -> assume no computational limitations
135
What is the elliptic curve general equation?
y^2 = x^3 +x + 1 || y^2 = x^3 +ax + b
136
What is the key size, block size and number of rounds in DES and 3DES
R = 16
Key size = 56
Block size = 64
137
What is shors algorithm?
A quantum algorithm that can find prime factors of a number
- Threatens Diffie-hellman and RSA
138
What is grovers algorithm?
A Quantum algorithm that can brute force finding keys. It also allows inversions of functions
139
What is the BHT algorithm?
A quantum algorithm that solves the collision problem in O(n^{1/3})
-
Key Links
-
Subjects
-
Company
-
Find Us
-
