ECE498AM Final
作业security | Algorithm | 密码学代写 – 这是一个网络安全方面的practice, 考察对加密相关的理解, 包括了security/Algorithm/RSA算法等方面
Instructions
Please either 1) typeset your answers in LATEX and submit a PDF file through Piazza, or else 2) write answers by hand and turn in a physical copy in class, 3) write answers by hand and send a scanned PDF file. We prefer to read succinct and precise answers. If you can be precise while being succinct with your answers, please try.
Academic integrity reminder: We treat academic integrity very seriously. You are supposed to do this exam individually. You may refer to lecture notes, optional textbooks, or internet searches. However, you should not talk about the problems with peers or ask for help online.
How multiple choice is graded. Multiple choice questions may have multiple correct answers. If there areNmultiple correct answers, then each correct answer is worth 1/Nof the total points for the question. You lose 1/N points for every wrong answer you circle. The total cannot go negative. In code,score = points * max(numcorrect – numwrong, 0) / totalcorrect
Clarity, succinctness, writing your name and Netid: [4 pts].
1 Attacks on RSA
- Dan Bonehs survey Twenty Years of Attacks on the RSA Cryptosystem^1 covers four categories of attacks: (1) elementary attacks, (2) low private exponent attacks, (3) low public exponent attacks, and (4) implementation attacks (questions about these below). For each category, summarize one of the attacks and explain a possible defense.
(^1) https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
- LetN,ebe an RSA public key. Suppose you have access to an oracleO() that will return the least significant bit ofmon inputc=me modN. Write an Algorithm that computes the messagemin full.
- Suppose Alice has public keyN,e 1 and Bob has public keyN,e 2 where gcd(e 1 ,e 2 ) = 1 (one should never share an RSA modulus!). How can an adversary who observes two ciphertextsc 1 =me^1 modN andc 2 =me^2 modN compute the messagem? (Hint: There exist integersX andY such that Xe 1 +Ye 2 = gcd(e 1 ,e 2 ).)
2 Broadcast Protocols
Broadcast protocols occupy a large design space, differing along two main axes: the model of fault-tolerance and the model of communication. Fill in the table below, identifying the models used for each of the protocols.
Crash faults Byzantine faults Partially sychronous Synchronous Asynchronous
Raft
PBFT
Bracha
Dolev-Strong
3 Reading Cryptography Library Documentation [12pts]
The crypto library NaCL^2 (pronounced salt) is a modern cryptographic library, that applies many practical engineering choices. These are discussed in detail in the technical paper, The security impact of a new cryptographic library. by Daniel J. Bernstein, Tanja Lange, and Peter Schwabe.^3 Refer to the technical paper and the website documentation to answer the following questions.
(^2) https://nacl.cr.yp.to/ (^3) https://cr.yp.to/highspeed/coolnacl-20120725.pdf
3.1 NaCL includes an implementation of the following crypto primitives (circle
all that apply):
1.Public key signatures a. RSA b. ECDSA c. EdDSA
2.Symmetric encryption a. AES b. Salsa20 c. ChaCha
3.Hash functions a. SHA-1 b. SHA-256 c. SHA-512 c. MD
3.2 Thecryptoboxinterface provides which of the following security properties:
a. Authentication b. Encryption c. Replay prevention d. Forward secrecy
3.3 Identify four specific design decisions made in NaCL to improve security.
Note: Byspecific, I mean that just saying sidechannels does not count!
3.
Consider the following maxim:
Dont roll your own crypto.
- In a couple of sentences, explain what this maxim means. Give three arguments in support of this maxim. At least two of your arguments should be special to cryptography (i.e., they should not also apply to dont roll your own compiler or dont roll your own database)
- Describe a scenario where it would be appropriate to roll your own crypto. Describe two precautions you can take to avoid security hazards.
4 Threshold Cryptography and Secret Sharing [14pts]
Alice wishes to split her Crypto Egg private key into three backup copies. She uses the Shamirs Secret sharing program (SSSS) to generate three files. She writes down one of them on a piece of paper and stores it in her closet. She keeps one on a USB drive she carries in her pocket. She mails one of them to her parents house in another state. Alice receives an anonymous message that appears to be encrypted using her Crypto Egg public key.
4.1 [2pts]
Describe the steps Alice must take to decrypt the message. Do not include any more steps than necessary!
4.2 [2pts]
Describe a scenario where enough of Alices key shares are stolen so an attacker can decrypt the message.
4.3 [2pts]
Describe a scenario where Alice loses enough keys that she cannot decrypt the message.
4.4 [2pts]
Recall that Shamirs Secret Sharing represents a secret by a polynomial over a finite field. Fill in the blanks. The degree of the polynomial in this case is. This configuration is referred to as -of- secret sharing.
4.5 [3pts]
What is the unique degree-3 polynomialfover the finite fieldF 53 that satisfies the following constraints:
f(0) = 0
f(1) = 37
f(2) = 47
f(3) = 33
f(4) = 51
f(5) = 51
You can do this by hand or using any tools you like.
4.6 [3pts]
How many degree-3 (or smaller degree) polynomials ofF 53 satisfy the constraintsf(0) = 0 andf(1) = 37?
5 Garbled Circuits Optimizations [6pts]
Consider the following portion of a boolean circuit used in a garbled circuits protocol. (Those are both XOR gates, in case you forgot which shape is which 🙂
w 1 w 2 w 3
w
4
w
5
G
1
G
2
Your task will be to show to encode the wire labels for this portion of a garbled circuit using the Free XOR
technique, without needing any garble tables. Assume that the global offset {$ 0 , 1 }+1has already been sampled by the circuit-generating party. You can also assume the following wire labels are already determined:
k^01
$
{ 0 , 1 }, k^11 =k^01
k^02 {$ 0 , 1 }, k^12 =k^02
k^03
$
{ 0 , 1 }, k^13 =k^03
5.1 [3pts]
Whats left for you to do is just to do define the remaining wire labels:
k^04 =
k^14 =
k^05 =
k^15 =
5.2 [3pts]
Briefly justify your choice above. What invariants do they satisfy? Mention something about both correctness and secrecy.
6 Symmetric Encryption Security Definitions [16pts]
This question uses the following security definitions for symmetric encryption:
- Indistinguishability under Chosen Plaintext (IND-CPA).In this setting, the adversary has access to just an encryption oracle.
A.Pr
kGen(1);
(m 0 ,m 1 )AEnck()(1);
b
$
{ 0 , 1 };
cEnck(mb);
bAEnck()(1,c) :b=b
1
2
+negl()
- Indistinguishability under Chosen Ciphertexts (IND-CCA2). In this setting, the adversary has access to both an encryption oracle and a decryption oracle.
A.Pr
kGen(1);
(m 0 ,m 1 )AEnck(),Dec()(1);
b
$
{ 0 , 1 };
cEnck(mb);
bAEnck(),O(k,c,)(1,c) :b=b
1
2
+negl()
where the oracleOallows the adversary to see the decryption of an arbitrary ciphertext except for the
challenge ciphertextc.
O(k,c,c) :=
{
c=c
Deck(c) c 6 =c
6.1 Application Analysis [8pts]
Alice is designing a web-based service for Bob that converts text into nicely typeset PDF files. Bobs messages are important to keep confidential, so she is usinghttps. Due to bizarre external constraints, the way Alice has implemented her webservice, the text to convert must be included as part of the URL, for examplehttps://pdfwebservice.com/?user=Bob&ciphertext={XX}, and furthermore the entire sequence of visited URLs islogged to a publicly accessible page. However, Alice already has a shared key with her client Bob, and so to provide confidentiality, the text to include is encrypted first using this shared key, as in the{XX}above. In her initial version, she used a symmetric encryption scheme that is known to be IND-CPA secure.
Explain to Alice why IND-CPA does not guarantee confidentiality to Bob.
In her second version, Alice uses an encryption scheme that is IND-CCA2 secure. Explain why this is appropriate to ensure confidentiality.
6.2 Security proof of encryption scheme [8pts]
Letf:{ 0 , 1 }{ 0 , 1 } { 0 , 1 }be a pseudorandom function family. Consider the following encryption scheme:
- Gen(1) :k 1 $ { 0 , 1 },k 2 $ { 0 , 1 }, return (k 1 ,k 2 )
- Enck 1 ,k 2 (m) : sampler{ 0 , 1 } c 1 fk 1 (rm) c 2 mfk 2 (r) output (r,c 1 ,c 2 )
- Deck((r,c 1 ,c 2 )) : Fill in an appropriate decryption scheme yourself TODO: Your answer goes here
Setm=fk 2 (r)c 2
Check the tagfk 1 (rm) =c 1
Returnmif the tag matches, otherwise.
Prove that this scheme is secure under IND-CCA2.
Given an adversary A that breaks we need to construct anAthat breaks.
Define how requests to the encryption and decryption oracles are handled.
Use a sequence of hybrid games and reduction proofs to show thatAis as successful asA.
Hint: The proof in Pass and Shelat,7.1.3 A CCA2-Secure Encryption Schemecan be used as a starting point. However, the scheme in this question is slightly different, so the proof must be adapted. Similar to this proof, you can assume that scheme from99.1: Many-message Encryption Schemeis IND-CPA secure.
7 Password based authentication [20pts]
Read Matt Greens blogpost^4 on password-authenticated key exchange (PAKE) and answer the following questions. Note that these may require you to dig into the papers mentioned in the blogpost.
7.1 True or False [8pts]
- When storing passwords on a server, the best practice is to salt each password with a unique random value, and hash the salted password using a fast, cryptographic hash function such as SHA-256. True False
- The Secure Remote Password (SRP) PAKE protocol is secure against man-in-the-middle attacks and precomputation attacks. True False
- LetFbe a PRF,kbe a key to the PRF known by a serverS, andxbe an input to the PRF known by a clientC. An oblivious PRF protocol allows theCandSto computey=Fk(x) such thatConly learnsyandSdoes not learn anything aboutx. True False
- Asymmetric PAKE schemes protect against server compromise. If an attacker obtains the file that the server uses to authenticate users, the best she can do is launch an offline dictionary attack. True False
7.2 Ideal functionality [2pts]
Illustrate an ideal functionality for Oblivious PRF evaluation.
(^4) https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/
7.3 PAKE Variations [10pts]
The following two questions are about variations of PAKE protocols, which are intended to defend against precomputation attacks. To summarize, the attack scenario is:
Precompute – Online attack scenario:
The attacker starts out knowing a list of user names. The attackers goal is to compromise the server,
andshortly thereafterto obtain the users passwords.
Precompute phase.
- The attacker can start asmallnumber of sessions with the server (not more than one per user) in which it may attempt to authenticate as a user.
- The attacker runs alongoffline computation to make password lookup tables. Online phase.
- The attacker compromises the server and obtains the PWD file.
- The attacker now performs asmallonline phase computation to obtain the users passwords.
7.3.1 PAKE 1 [5pts]
Consider the following variation of a PAKE scheme:
Setup:
- The user chooses their password,P
- The PWD file on the server consists of (for each user):
- salt: a unique per user, 32-byte string derived from the password as PBKDF(userserviceP)
wherePBKDFis a slow password based key derivation function
- x: a salted password hash, x=PRF(salt,P)
To authenticate using passwordP:
User connects to the server using HTTPS.
The User and Server run anOPRFprotocol so that the User obtains
x=PRF(salt,P)
User usesxand Server usesxas a shared secret for an authenticated session. Ifx=xthen the
session authenticated. Otherwise the session is terminated.
This PAKE 1 scheme is not secure against a precompute-online attack. Explain an attack.
7.3.2 PAKE 2 [5pts]
Consider the following variation of a PAKE scheme:
Setup:
- The user chooses their password,P
- The PWD file on the server consists of (for each user):
- salt: a unique per user, 32-byte string chosen randomly derived from the password as
- ciphertext: an encryption of the salt using AES,
ciphertext=AESk(salt)
wherekis a secret key derived from the password,
k=PBKDF(userserviceP)
- x: a salted password hash x=PRF(salt,P)
To authenticate using passwordP:
User connects to the server using HTTPS.
The Server sendsciphertextto the user.
User computeskas
k=PBKDF(userserviceP)
User useskto decryptsalt=AESk(ciphertext
User computesx=PRF(salt,P)
Users usesxand Server usesxas a shared secret for an authenticated session. Ifx=xthen the
session authenticated. Otherwise the session is terminated.
This PAKE 2 scheme is not secure against a precompute-online attack either. Explain an attack.