Q1. A. a)
This function is not negligible.
For instance, if we take the polynomial p(n) = n. If was negligible, then p(n) < 1 for every n bigger than a certain N. But using the L’Hopital’s rule we have that
= = == ∞
For this reason, the function is unbounded, thus not negligible.
(b)
For any function ε such that
ε (λ)= =
the function is negligible because there exists a value d for which
ε(λ)⩽
Therefore, is negligible.
(c) 2−n
This function is negligible. For every polynomial p(n) = aknk +. . . + a0. Applying L’Hopital’s rule,
= = = 0
Hence, by definition of limit, we can ensure that there exists a certain N for which
p(n)2−n <1 for n>N
d)
The function is negligible because for every constant n, there exists a value from the function such that
>>0.
Converging functions are negligible.
e)
The function translates to , which converges. Therefore, at some point, there exists a constant N for which
>
Therefore, the function is negligible.
f)
This function is negligible, as has been shown in e, above. There exist a constant N for which
>
Q2. One-time pad
OTP => l=4, C = 0101.
In one-time-pad encryption, the XOR operation is carried out between the message and the plaintext to result in the cipher text. Therefore, without the knowledge about the key, we have the following possible decryptions (Katz & Lindell, 2014).
M = 0000
K = ?
C = 0101 = >reverse of K^M = > i. 0101
The message could also be 1010. There are 6 possible combinations between the Message and Key.
Pr[E(k,m)=c]= = = 0.167
Therefore, the probability is 0.167 that the message is 0000.
Q. 3 In order to prove that it is perfectly secure, we show that for every m ∈ M, and every ciphertext for which we have.
First we compute for arbitrary c ∈ C and ∈ M. For the one-time pad,
= Pr[K = m0 ⊕ c]
where the sum is over m0 ∈ M with Pr[M = m0 ] 6= 0. Bayes’ Theorem gives:
= Pr[M = m],
which completes the proof.
Q4. One Time Password is not secure against known plaintext attacks.
The one-time pad encryption utilizes the XOR operation between the key and plaintext message. Therefore, in the event of the knowledge of the plaintext and ciphertext, the key is found by the XOR operation on the ciphertext with the message as below
[c = (m2⊕k)]⊕m2=k
The randomization of k in the OTP implementation makes it secure. However, when the same key is used in encrypting a subsequent message, the XOR operation reveals the message as below.
(m2⊕k)]⊕k=m2
Under such circumstances, OTP is insecure.
Q5. Flaws that led to success of Venona Project.
The one-time pad encryption is strong because of the randomization of the keys used in generating the ciphertexts. The re-use of keys results in significant losses in security. In the second world war, the USSR encryption machines was randomized based on limited phases, cycles, potential overlaps, and keys. The Venona project was successful when this flaw in the USSR encryption became clear to the NSA after exhaustive analysis of captured ciphertexts and one-time pads (Martin, 2017). Having this information, it became possible to decipher messages being exchanged by USSR allies.
Q6. Decryption functions
- M = {0, 1}, K = {0, 1}.
uniform key from K, and Enck(m) returns [k AND m].
C= k&m.
Decryption m = C/k
The AND function is not secure because all the digits in a binary output for the reverse operation are easily recoverable based on a carefully considered guess.
If
Pr[E(k,m)=c]=
The number of keys provided in an AND operation are half of those produced in an XOR combination. Therefore, the function is not secure.
- M = {0, 1}, K = {0, 1}.
uniform key from K, and Enck(m) returns [k OR m].
C= k|m.
An OR operation results in a non-deterministic output of C. therefore, decryption is nearly impossible considering the number of outputs for which any input, key or plaintext, is valid. Therefore, such an encryption mechanism is impractical.
- M = {0, 1}, K = {0, 1}.
uniform key from K, and Enck(m) returns [k XOR m].
C= k^m.
Decryption m = C^k
The XOR operation is deterministic given the following conditions:
An OTP (one-time pad) is defined as (K,M,C) over (E,D) where E is random and D is deterministic such that
E: K^M=>C, D: K^C => M
Pr[E(k,m)=c]=
The k is chosen at random from a pool of K numbers. Therefore,
Pr[E(k,m0)=c]=Pr[E(k,m1)=c]
∀ c∈C, m0, m1∈M with |m0|=|m1|. In this case, the XOR cipher has perfect secrecy.
- M = {0, 1, 2, 3}, K = {0, 1, 2, 3}.
uniform key from K, and Enck(m) returns [k + m mod 4].
Decryption: m = (C-k)4 mod 4
This encryption function is secure only if k is made of a combination of unique combinations of prime numbers that are large enough to prevent short-time computation. Otherwise it is insecure.
- M = {0, 1, 2, 3}, K = {0, 1, 2, 3}.
uniform key from K, and Enck(m) returns [k · m mod 4].
Decryption: m = ()4 mod 4
The encryption mechanism is only secure if k is a combination of large sets of prime numbers that would take a longer than reasonable time to factorize (Pachghare, 2015). With n=4, the algorithm is not very secure.
- M = {1, 3}, K = {1, 3}.
uniform key from K, and Enck(m) returns [k · m mod 4].
Decryption: m = ()4 mod 4
The key length and message length are shorter than the length of n. Therefore, the encryption is not secure.
- M = {0, 1, 2}, K = {0, 1, 2}
uniform key from K, and Enck(m) returns [k + m mod 3].
Decryption: m = (C-k)3 mod 3
The algorithm is not secure because n= 3 reduces the computation complexity and the length of K is also short.
- M = {0, 1, 2}, K = {0, 1}
uniform key from K, and Enck(m) returns [k + m mod 3].
Decryption: m = (C-k)3 mod 3
The algorithm is not secure because n= 3 reduces the computation complexity and the length of K is also short than the message.
Q7. a. The message space is M = {0, . . . , 4}.
key space {0, . . . , 5}.
C= [k + m mod 5],
Deck(c) [c − k mod 5].
The algorithm is insecure because the computation is low in terms of mathematical complexity, especially given that the key space contains only 6 digits and the message space is only 5 digits. Therefore, a brute force attack would result in a broken encryption.
b.) The message space is M = {m ∈ {0, 1}L | the last bit of m is 0}.
Key: {0, 1}L−1 .
C = m ⊕ (k||0),
Deck(c) returns c ⊕ (k||0).
This algorithm is perfectly secure only in cases where one-time pad encryption is used. In such a case, the determination of all possible combinations at once is impossible. However, the re-use of the key results in significant loss of secrecy.
Q8. No, the modified scheme is no longer perfectly secret. To see this, we need to show that for an arbitrary ciphertext c ∈ C and message m ∈ M, Pr[M = m|C = c] ≠Pr[M = m]. Now, given the ciphertext c, we know that it cannot be the message m since k ≠ 0l , which means the message must be different from the ciphertext. Thus Pr[M = m|C = c] = 0. Clearly however, Pr[M = m] ≠0 since every element of the message space is a likely candidate. And so we have that Pr[M = m|C = c] ≠ Pr[M = m].
Part II
Q1. We prove the contrapositive statement. Given an encryption scheme Π, adversary A, security parameter n, messages m0 and m1, uniform bit b ∈ {0, 1} and a ciphertext c which is the encryption of plaintext mb. Suppose Π doesn’t have indistinguishable encryptions in the presence of an eavesdropper. Then
Pr[] > + negl(n).
This means
Pr[mb = m0|C = c] ≠ ≠ Pr[mb = m1|C = c].
Now let M be such that
Pr[M = m0] = Pr[M = m1] = .
This implies
Pr[M = mb|C = c] ≠Pr[M = mb] for b ∈ {0, 1}.
Therefore, the scheme is not perfectly secret.
Q2. This function is not a pseudo-random generator because the last bit can be computed from the rest of bits. In particular, the sum of all the elements of the output, it is always 0. That is,
1. let (s1, . . . , sn) ∈ {0, 1}n, and
2. let (y1, . . . , yn+1) = G(s1, . . . , sn).
3. Then
yi = n+1= i +i
Now let’s take the definition of pseudorandom generator. Taking into account the previous observation, we can define the distinguisher D as
D(y1, . . . , yn+1) = yi
Choosing r = (r1, . . . , rn+1) ∈ {0, 1}n+1 uniformly at random, we have
Pr[D(r) = 1] = .
Choosing (s1, . . . , sn) ∈ {0, 1}n uniformly at random, we have
Pr[D(G(s)) = 1] = 0.
Hence , and is not negligible. Therefore, G is not a pseudorandom function.
Q3. PRG: G : {0, 1} n → {0, 1} n+1 and G0 : {0, 1} n+1 → {0, 1} n+2
G’ : {0, 1} n → {0, 1} 2n+3 =>?
G’0(s1, . . . , sn) = (G(s1, . . . , sn), G’ (G(s1, . . . , sn)))
The definition of PRG considers a distinguisher D(y1, . . . , yn+1) = ⊕ n+1 i=1 yi.
The above problem has a composite generator that combines G and G’ to form G’0. A pseudo-random number needs to have unique characters each time. For a random generator, r = (r1, . . . , rn+1) ∈ {0, 1} n+1,
Pr[D(r) = 1] = 1/2
Computing Sn results in 0. Therefore,
Pr[D(G(s)) = 1] = 0.
The difference between the generator and distinguisher is 0.5, which is much greater than 0. Therefore, G is not a pseudorandom generator.
Q4. PRG: G : {0, 1} n → {0, 1} n+2
n G’ : {0, 1} n → {0, 1} n+1, defined by G’ (s1, . . . , sn) = (y1, . . . , yn+1) with
(y1, . . . , yn+1, yn+2) = G’ (s1, . . . , sn) is a PRG
From the above definition in Q3, a pseudorandom generator needs to produce no or insignificant difference between the Generator and distinguisher.
Choosing r = (r1, . . . , rn+1) ∈ {0, 1} n+1,
Pr[D(r) = 1] = 1
And
Pr[D(G(s)) = 1] = 1
The difference between D and G is zero. Therefore, the function is a pseudorandom one.
Q5. one-time pad is not CPA-secure
A private key encryption scheme has an indistinguishable encryption under CPA as long as
Pr [] = 1] ≤ 1/2 + negl(n)
Where A is random. A random one time pad with a chosen plain text assumes that the adversary can decipher the ciphertexts using messages of their choosing in an encryption oracle mode. When the oracle is queried, a ciphertext for the message is returned. In any case, the oracle may be stateful or non-deterministic. In cases of stateless and deterministic oracles, the ciphertext cannot be indistinguishable, thus failing to adhere to the definition of indistinguishability.
Q6. If Π is an encryption scheme in which Enc is a deterministic function of the key and the message, then Π cannot be CPA-secure.
A perfectly secure encryption model needs have :
P(A succeeds)=1/2
The definition of indistinguishability as in Q5. Above cannot be met because the adversary(A) can use the oracle access to compute
Enck(mi) for i=1,2
in a brute force until he succeeds in accessing and c←Enck(mb). Then the uniform bit b is revealed. The security of this scheme is dependent on the probabilistic polynomial time (PPT) of the adversary, which depends on computational power. Therefore, it is not secure.
Q6. In an encryption scheme Π in which Enc is a deterministic function of the key and the message, we have that there is only one unique encryption of an arbitrary message m. Thus, in a CPA setting, given that the adversary A always has oracle access to the encryption, he can always determine the precise message that was encrypted.
In clearer terms, given two messages m0 and m1, a uniform bit b ∈ {0, 1} and a ciphertext c such that Enc(mb) = c, the adversary can always output b’ with . Hence the output of the experiment is always 1.
Q7. A function Funcn mapping n-bit strings to n-bit strings is of the size 2n and may be declared as Funcn(2n).
Q8. Define the keyed, length-preserving function F by
F(k, x) = k ⊕ x.
For a function F:{0,1}*x{0,1}*-> {0,1}* that is length-preserving, F is a pseudorandom function if
|Pr[D F (.) (n)=1]-Pr[D f(.) (n)-1]| (n)
Where k is random and f maps n-bit strings to n-bit strings
k ⊕ x. results in a pseudorandom function because the XOR operation is indistinguishable given that identical bits result in 0 and non-identical bits result in 1.
Q9. Prove that F’ k (x) = Fk(0||x)||Fk(x||1). Is pseudorandom for a keyed function
F’: {0, 1} n x{0, 1} n−1 → {0, 1} 2n
For a length-preserving keyed function,
|Pr[DFk(·) (1n) = 1] – Pr[Df(·)(1n) = 1]| ≤ negl(n).
And k belongs to {0,1}n.
Pr[D(r) = 1] =1
Pr[Df(·)(2n) = 0
|Pr[DFk(·) (1n) = 1] – Pr[Df(·)(1n) -1]| =0
From the above, it can be inferred that the function is pseudorandom.
Q10. The choice of incrementing IV by any decodable factor. For instance a zero vector initial variable allows an adversary to perform an Adaptive Chosen Plaintext Attack (ACPA). Incrementing the IV by a single value can allow the creation of a zero vector value. XORing the IV with the cipher blocks causes the revelation of the plaintext.
(m⊕IV)⊕IV=m
Therefore, the security of a CBC encryption relies on a random IV selection.
Q11. Cipher Block architecture
- Modes
- Positional dependency: The blocks are encrypted based on the position of the plaintext by XORing them in sequence. Any changes in the position results in failure to decrypt (Lea, 2018). This reduces the success of attacks through statistical analysis.
- Error propagation: Since the cipher blocks are position-dependent, any error that occurs in the XORing the blocks and bits at any position is propagated in subsequent operations. This feature results in the increase in the security of the cipher method because it reduces chances of success in brute force attacks.
- Synchronization: Encryption and decryption have to share a common parameter in order to allow for validation between the sender and the receiver.
- The encryption circuits can be used for decryption: The circuits can perform a reverse operation, which results in decryption.
- Plaintext padding requirement: This technique is used to increase the size of the plaintext to ensure that it matches the length of the cipher blocks for correct encryption and synchronization.
- Parallelizable: The cipher blocks can be processed one at a time using different processing threads. This feature enhances the speed of encryption and decryption when many processors are involved.
- ECB, CBC, CFB, CTR satisfying the modes
Positional dependency: CBC, CFB, CTR. In each of the three, the XOR operations occur per block/bit combination. Therefore, any shift or skip operation either on the bits or blocks causes failure in length matching or another error, which is propagated.
Error propagation: ECB, CBC, CFB, CTR. All forms of error are propagated due to the XOR operations that occur block by block, from the positional dependency.
Synchronization: ECB, CBC, CFB, CTR. A common parameter between encryption and decryption allows for easy verification of authenticity of the sender and receiver.
The encryption circuits can be used for decryption: ECB, CBC, CFB, CTR. Similar circuits enable cost reduction and management on both ends of communication.
Plaintext padding: ECB, CBC, CFB, CTR. Length of the block ciphers is a key component in any block cipher encryption technique as it ensures accuracy and enables the other modes. Therefore, it increases security.
Parallelizability: ECB, CBC, CFB, CTR. Parallelization of processing increases the speed of encryption and decryption, thus enabling faster communication with the increase in processing cores.
Q12. CBC Block cipher: 256-bit key
128-bit block length
a 1024-bit message.
Ciphertext = 128+1024 = 1152 bits.
Q13. Pseudorandom permutations
ctr ∈ {0, 1} n
ith cipher block is
ci := Fk(ctr + i + mi).
The ctr is chosen from a pool of binary digits of power n. Such an operation is not difficult for a computer running a brute force attack. The PPT allows easy determination of ctr. Ci is obtained from an addition operation. Depending on the length of mi, ci can be recovered through a brute force attack in a statistical analysis of several data blocks.
References
Katz, J. & Lindell, Y., 2014. Introduction to Modern Cryptography, Second Edition. s.l.:CRC Press.
Lea, P., 2018. Internet of Things for Architects: Architecting IoT solutions by implementing sensors, communication infrastructure, edge computing, analytics, and security. s.l.:Packt Publishing Ltd.
Martin, K. M., 2017. Everyday Cryptography: Fundamental Principles and Applications. s.l.:Oxford University Press.
Pachghare, V., 2015. CRYPTOGRAPHY AND INFORMATION SECURITY. s.l.:PHI Learning Pvt. Ltd.
