ECE498AM Final
ECE Final代写 Please either 1) typeset your answers in LATEX and submit a PDF file through Piazza, or else 2) write answers by hand and turn
Instructor: Andrew Miller November 27, 2018
Name NetID
Instructions ECE Final代写
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.
Due date: 11:59pm, Dec 6, 2018.
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.ECE Final代写
How multiple choice is graded. Multiple choice questions may have multiple correct answers. If there are N multiple correct answers, then each correct answer is worth 1/N of 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(num correct – num wrong, 0) / total correct
Clarity, succinctness, writing your name and Netid: [4 pts].
1 Attacks onRSA ECE Final代写
- Dan Boneh’s survey “Twenty Years of Attacks on the RSA Cryptosystem”1covers 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.
1https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
- Let N, e be an RSA public Suppose you have access to an oracle ( ) that will return the least significant bit of m on input c = memod N . Write an algorithm that computes the message m in full.ECE Final代写
- SupposeAlice has public key N, e1 and Bob has public key N, e2 where gcd(e1, e2) = 1 (one should never share an RSA modulus!). How can an adversary who observes two ciphertexts c1 = me1 mod N and c2 = me2 mod N compute the message m? (Hint: There exist integers X and Y such that
X · e1 + Y · e2 = gcd(e1, e2).)
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 | ECE Final代写 | ||||
| Bracha | |||||
| Dolev-Strong |
3 Reading Cryptography Library Documentation [12pts]
The crypto library NaCL2 (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
3 |
https://nacl.cr.yp.to/ | ECE Final代写 | |
| https://cr.yp.to/highspeed/coolnacl-20120725.pdf | |||
3.1 NaCL includes an implementation of the following crypto primitives (circle all that apply):
- Public keysignatures RSA b. ECDSA c. EdDSA
- Symmetricencryption AES b. Salsa20 c. ChaCha20
- Hashfunctions SHA-1 b. SHA-256 c. SHA-512 c. MD5
3.2 The crypto box interface provides which of the following security properties:
- Authentication b.Encryption c. Replay prevention d. Forward secrecy ECE Final代写
3.3 Identify four specific design decisions made in NaCL to improve security.
Note: By specific, I mean that just saying “sidechannels” does not count!
3.4
Consider the following maxim:
Don’t 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 applyto “don’t roll your own compiler” or “don’t roll your own database”)ECE Final代写
- Describe a scenario where it would be appropriate to roll your own crypto. Describe two precautions you can take to avoid security
4 Threshold Cryptography and Secret Sharing [14pts]
Alice wishes to split her Crypto Egg private key into three backup copies. She uses the Shamir’s 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.ECE Final代写
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 Alice’s key shares are stolen so an attacker can decrypt the message.
4.3 [2pts] ECE Final代写
Describe a scenario where Alice loses enough keys that she cannot decrypt the message.
4.4 [2pts]
Recall that Shamir’s 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 polynomial f over the finite field F53 that satisfies the following constraints:
| f (0) = | 0 |
| f (1) = | 37 |
| f (2) = | 47 |
| f (3) = | 33 |
| f (4) = | 51 |
| f (5) = | 51 ECE Final代写 |
You can do this by hand or using any tools you like.
4.6 [3pts]
How many degree-3 (or smaller degree) polynomials of F53 satisfy the constraints f (0) = 0 and f (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 🙂
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}λ+1 has already been sampled by the circuit-generating party. You can also assume the following wire labels are already determined:
k0 ←${0, 1}λ, k1 = k0 ⊕ ∆
k0 ←${0, 1}λ, k1 = k0 ⊕ ∆
k0 ←${0, 1}λ, k1 = k0 ⊕ ∆
5.1 [3pts]
What’s left for you to do is just to do define the remaining wire labels:
k0 =
k1 =
k0 =
k1 =
5.2 [3pts]
Briefly justify your choice above. What invariants do they satisfy? Mention something about both correctness and secrecy.ECE Final代写
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.
Indistinguishability under Chosen Ciphertexts (IND-CCA2). In this setting, the adversary has access to both an encryption oracle and a decryption oracle.
where the oracle O allows the adversary to see the decryption of an arbitrary ciphertext except for the challenge ciphertext c.
6.1 Application Analysis [8pts]
Alice is designing a web-based service for Bob that converts text into nicely typeset PDF files. Bob’s messages are important to keep confidential, so she is using https. Due to bizarre external constraints, theway Alice has implemented her webservice, the text to convert must be included as part of the URL, for example https://pdfwebservice.com/?user=Bob&ciphertext= XX , and furthermore the entire sequenceof visited URLs is logged to a publicly accessible page. However, Alice already has a shared key with herclient 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.ECE Final代写
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]
Let f : {0, 1}λ × {0, 1}∗ → {0, 1}λ be a pseudorandom function family. Consider the following encryption
- Gen(1λ): k ←$ {0, 1}λ, k ←$
- Enck1,k2 (m) :
{0, 1}λ, return (k1, k2)
sample r ← {0, 1}λ
c1 ← fk1 (r“m) c2 ← m ⊕ fk2 (r) output (r, c1, c2)
- Deck((r, c1, c2)) :
Fill in an appropriate decryption scheme yourself ECE Final代写
TODO: Your answer goes here
Set m = fk2 (r) ⊕ c2
Check the tag fk1 (r“m) = c1
Return m if the tag matches, otherwise ⊥.
Prove that this scheme is secure under IND-CCA2.
Given an adversary A that breaks we need to construct an Aj that breaks .
Define how requests to the encryption and decryption oracles are handled.
Use a sequence of hybrid games and reduction proofs to show that Aj is as successful as A.
Hint: The proof in Pass and Shelat, 7.1.3 A CCA2-Secure Encryption Scheme can 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 from 99.1: Many-message Encryption Scheme is IND-CPA secure.ECE Final代写
7 Password based authentication [20pts]
Read Matt Green’s blogpost 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 asSHA-256.ECE Final代写
True False
- The Secure Remote Password (SRP) PAKE protocol is secure against man-in-the-middle attacks and precomputation
True False
- Let F be a PRF, k be a key to the PRF known by a server S, and x be an input to the PRF known by a client C. An oblivious PRF protocol allows the C and S to compute y = Fk(x) such that C only learns y and S does not learn anything aboutx.
True False
- Asymmetric PAKE schemes protect against server compromise. If an attacker obtains the file thatthe server uses to authenticate users, the best she can do is launch an offline dictionary
True False
7.2 Ideal functionality [2pts]
Illustrate an ideal functionality for Oblivious PRF evaluation.
4https://blog.cryptographyengineering.com/2018/10/19/lets-talk-about-pake/
7.3 PAKE Variations [10pts]ECE Final代写
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 attacker’s goal is to compromise the server, and shortly thereafter to obtain the users’ passwords.
Precompute phase.
- The attacker can start a small number of sessions with the server (not more than one per user) inwhich it may attempt to authenticate as a
- Theattacker runs a long offline computation to make password lookup Online phase.
- Theattacker compromises the server and obtains the PWD
- Theattacker now performs a small online phase computation to obtain the users’
7.3.1 PAKE 1 [5pts] ECE Final代写
Consider the following variation of a PAKE scheme: Setup:
- Theuser chooses their password, P
- ThePWD file on the server consists of (for each user):
- salt:a unique per user, 32-byte string derived from the password as
PBKDF(user“service“P ) where PBKDF is a slow password based key derivation function
- x: a salted passwordhash,
To authenticate using password P j:
x = PRF(salt, P )
User connects to the server using HTTPS.
The User and Server run an OPRF protocol so that the User obtains
xj = PRF(salt, P j)
User uses xj and Server uses x as a shared secret for an authenticated session. If xj = x then 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:
- Theuser chooses their password, P
- ThePWD file on the server consists of (for each user):
- salt: a unique per user, 32-byte string chosen randomly derived from the passwordas
- ciphertext:an encryption of the salt using AES,
ciphertext = AESk(salt) where k is a secret key derived from the password,
k = PBKDF(user“service“P )
- x: a salted passwordhash
x = PRF(salt, P )
To authenticate using password P j: ECE Final代写
User connects to the server using HTTPS. The Server sends ciphertext to the user.
User computes kj as
kj = PBKDF(user“service“P j)
User uses kj to decrypt salt’ = AESkt (ciphertext User computes xj = PRF(salt’, P j)
Users uses xj and Server uses x as a shared secret for an authenticated session. If xj = x then the session authenticated. Otherwise the session is terminated.
This PAKE 2 scheme is not secure against a precompute-online attack either. Explain an attack.
更多其他：C++代写 r代写 代码代写 考试助攻 C语言代写 finance代写 lab代写 计算机代写 code代写 data代写 report代写 matlab代写 project代写 物理代写 数学代写
