SFL Prof. Dr. C. Rossow / S. Hausotte TU Dortmund WS 2021/2022 Exercise 2 (Hashes & Crypto)
Important announcement: Due to the student council meeting, the on-campus tutorial on November 10th is postponed to November 17th!
2.1 Modular Exponentiation
(a) Which of the following expressions are generally true, assuming all numbers are positive integers? You may use Euler’s theorem: aφ(n) mod n = 1 if a⊥n (a and n are coprime)
Copyright By PowCoder代写 加微信 powcoder
(1) ab modn=(amodn)b modn
(2) abmodn modn=ab modn
(3) ab modn=abmodφ(n) modn forn=pq,φ(n)=(p−1)(q−1)anda⊥n
(1) True.Leta=p·n+q.Thena modn=q.
ab mod n = (p · n + q)b mod n = qb mod n
=(a modn)b modn (2) False. Counter example: a = 3, b = 12, n = 10.
(3) True. Actually true for any n. Let x = b mod φ(n). Then b = x + yφ(n).
ab mod n = ax+yφ(n) mod n = ax · ayφ(n) mod n
x φ(n)y
=a · a modn
(1) x φ(n) y =a·a modnmodn
= ax · 1y mod n Euler’s theorem: aφ(n) ≡ 1 mod n =ax modn
(a) Given p = 7, q = 11 and e = 13, compute d. Feel free to use trial-and-error search to determine d or use the extended Euclidean algorithm.
(b) Assume you obtain Alice’s public key, and then you learn Alice’s φ(n). Can you compute p and q? If not, why not, and if so, how?
Solution: We first compute n = 77 and φ(n) = (p − 1)(q − 1) = 60. We have to find a d < φ(n) for which e · d mod φ(n) = 1, i.e., 13 · d mod 60 = 1. The only d < φ(n) that fulfills this is d = 37, since 13 · 37 mod 60 = 1.
Solution: We know that n = pq, and n is part of the public key. We also know that φ(n) = (p − 1)(q − 1)
SFL Prof. Dr. C. Rossow / S. Hausotte TU Dortmund WS 2021/2022 Exercise 2 (Hashes & Crypto)
From that follows that i.e.,
To substitute q, we build
φ(n) = pq − p − q + 1
p + q = n + 1 − φ(n)
q = n + 1 − φ(n) − p This implies that n = pq is the same as
n = p · (n + 1 − φ(n) − p)
Using a quadratic formula we can find 12
p= 2 n+1−φ(n)± |n+1−φ(n)| −4n
(c) PKCS is a standard that defines how to add random padding to plaintexts prior to RSA encryption. Why is such random padding actually required? Hint: Assume an attacker that knows to whom a message m was sent and has an intuition what the message might look like.
如果没有添加随机填充，用相同的公钥加密相同的信息将导致两个相同的密码文。这样的攻击者可以进行选择明文 攻击来猜测加密信息的内容。如果攻击者选择了m′=m，那么{m}KA={m′}KA，攻击者就能得知m。
2.3 Hash Functions
preimage是已知一 个hash值，寻找它对应 的message;
Second preimage是已 知一个message1，寻 找另一个与它有相 同hash值 的message2;
Collision是在没有已知 量(message和hash值 )的情况下，寻找任意 两个具有相同hash值 的message。
Solution: If no random padding was added, encrypting the same message with the same public key would result in two identical ciphertexts. Such an attacker can perform a chosen-plaintext attack to guess the content of an encrypted message. If an attacker chooses m′ = m, then {m}KA = {m′}KA, and the attacker learns m.
(a) Which of the following functions are technically hash functions? Rate their quality using the criteria given in the lecture. Assume a message M of equally sized blocks m1, m2, . . . , mn.
(1) H1(m1m2m3 · · · mn) = mn Solution:
Compression Output has a fixed length
Preimage resistance # A possible preimage for a hash h is 0|h. Second preimage resistance # H(M) = H(0 | M)
Collision resistance # see second preimage resistance
(2) H2(m1m2m3···mn)=m1+m2+...+mn (+referstointegeraddition)
(3) H3(M) = G(G(M)) where G fulfills all criteria of a hash function
Compression # Output length is not fixed
Preimage resistance # A possible preimage for a hash h is 0|h. Second preimage resistance # H(m1m2 · · · mn) = H(mnmn−1 · · · m1) Collision resistance # see second preimage resistance
Compression As the output of G has a fixed length, so does the output of H.
SFL Prof. Dr. C. Rossow / S. Hausotte TU Dortmund WS 2021/2022 Exercise 2 (Hashes & Crypto)
Preimage resistance Assume it would be possible find a preimage M from h. Based on M, one could then determine G(M) which is the preimage of G(G(M)). Therefore, G can not be preimage resistant. Since G is preimage resistant, we know that G ◦ G must also be preimage resistant.
Collision resistance Assume G ◦ G is not collision resistant. That means one can find M ̸= M′ with G(G(M)) = G(G(M′)). There are now to possible cases:
G(M) = G(M′): We have found a collision in the first application of G.
G(M) ̸= G(M′): We have found a collision in the second application of G.
In both cases, G can not be collision resistant. Per contradiction, G◦G must be collision
resistant.
Second preimage resistance see collision resistance
(b) Download the files fileA.bin and fileB.bin which are provided with this exercise. Compare the size of these files as well as their contents. Compute the hashes of these files using the MD5 and SHA256 algorithms.
Hint: You can use the virtual machine that you already used for the practical exercises.
(c) What can you learn about these two algorithms by comparing the hashes of both files? What conclusions can you draw about their usage in cryptographic systems?
(d) Let H be a hash function, and let H−1 be a deterministic inverse hash function that guarantees H(H−1(hash)) = hash. From the existence of this inverse function it follows that H is not preimage resistant. Assume that the corresponding H has a 512-bit input space mapped to a 160-bit output space and let both H and H−1 create outputs in a uniform distribution.
Can H still be collision resistant? If so, why? If not, how hard would it be to find a collision?
wc -c fileA.bin
wc -c fileB.bin
md5sum fileA.bin
md5sum fileB.bin
sha256sum fileA.bin
sha256sum fileB.bin
128 fileA.bin
128 fileB.bin
79054025255FB1A26E4BC422AEF54EB4
79054025255FB1A26E4BC422AEF54EB4
8D12236E5C4ED9F4E790DB4D868FD5C399DF267E18FF65C1107C328228CFFC98
B9FEF2A8FC93B05E7701E97196FDA6C4FBEEA25FF8E64FDFEE7015ECA8FA617D
Solution: MD5 has known collisions, even for very short inputs. That means MD5 should not be considered cryptographically secure and therefore not be used in cryptography!
Solution: H(H−1(hash)) = hash does not imply m = H−1(H(m)). To find a collision given H and H−1, the attacker can choose a random m. m and H−1(H(m)) are most likely colliding inputs.
In fact, if an attacker uses H on any attacker-chosen input m to get hash := H(m) and
m′ := H−1(hash), the chance that m = m′ depends on the size of the input and output
space. In our example, 2512 inputs map to 2160 outputs. Given uniform distribution, H−1(hash)
returns any m′ for which H(m′) = hash, and thus the chance that m′ = m is 2160 . But if 2512
m′ ̸= m, then we have a collision (since H(m) = H(m′) = hash), this happens with probability p = 1 − 2160 .
This implies that if we know an inverse function and the input space is larger than the output
space, H cannot be collision free.
Definitions used in the context of hash functions:
Preimage Resistance For any given hash value, it is computationally infeasible to find any input value that maps to this hash value.
SFL Prof. Dr. C. Rossow / S. Hausotte TU Dortmund WS 2021/2022 Exercise 2 (Hashes & Crypto)
2.4 Key Exchange
(a) Compare the basic concept of a Diffie- Exchange to the idea of Merkle’s Puzzle. Examine what their security is based on.
Solution: DHKE’s security is based on the hardness of the discrete logarithm problem, which is suspected to be a hard problem in terms of complexity. Merkle’s Puzzle is based on the fact that an attacker has to break about half of the transmitted puzzles, while the intended recipient
only needs to solve a single one.
默克尔之谜是基于这样一个事实:攻击者必须破解大约一半的传输谜题，而预期的接收者只需要解决一
(b) Explain the vulnerabilities and weaknesses of both concepts. Are there vulnerabilities that are shared by both DHKE and MP?
DHKE和MP都很容易受到中间人攻击。此外，MP容易受到暴力攻击，因为攻击者需要的计算能力与所 选谜题集的大小成线性关系。
Weak Collision Resistance For any given input value, it is computationally infeasible to find a second input value, that maps to the same hash value.
Strong Collision Resistance It is computationally infeasible to find any pair of two different input values, which map to the same hash value.
Solution: Both DHKE and MP are vulnerable to Man-In-The-Middle Attacks. In addition, MP is vulnerable to brute force attacks in the sense that the computational power needed by the attacker scales linearly with the size of the chosen set of puzzles.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com