Security代写：ECE498 Attacks on RSA

发表于   |   分类于

代写密码学作业，攻击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.

Attacks on RSA

  1. Dan Boneh’s survey “Twenty Years of Attacks on the RSA Cryptosystem” 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.

  2. Let {N,e} be an RSA public key. Suppose you have access to an oracle O(-) that will return the least significant bit of m on input c = m^e mod N. Write an algorithm that computes the message m in full.

  3. Suppose Alice 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 = m^e1 mod N and c2 = m^e2 mod N compute the message m?

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

Reading Cryptography Library Documentation

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.

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. ChaCha20
  3. Hash functions
    • a. SHA-1
    • b. SHA-256
    • c. SHA-512
    • d. MD5

The crypto box interface provides which of the following security properties

  • a. Authentication
  • b. Encryption
  • c. Replay prevention
  • d. Forward secrecy

Identify four specific design decisions made in NaCL to improve security.

Note: By specific, I mean that just saying “sidechannels” does not count!

Consider the following maxim:

Don’t roll your own crypto.

  1. 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 “don’t roll your own compiler” or “don’t roll your own database”)

  2. Describe a scenario where it would be appropriate to roll your own crypto. Describe two precautions you can take to avoid security hazards.

Threshold Cryptography and Secret Sharing

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.

  • Describe the steps Alice must take to decrypt the message. Do not include any more steps than necessary!

  • Describe a scenario where enough of Alice’s key shares are stolen so an attacker can decrypt the message.

  • Describe a scenario where Alice loses enough keys that she cannot decrypt the message.

  • 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.

  • What is the unique degree-3 polynomial f over the finite field F53 that satisfies the following constraints.

Password based authentication

Read Matt Green’s 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.

True or False

  1. 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.
  2. The Secure Remote Password (SRP) PAKE protocol is secure against man-in-the-middle attacks and precomputation attacks.
  3. 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 about x.
  4. 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.

Ideal functionality

Illustrate an ideal functionality for Oblivious PRF evaluation.

PAKE Variations

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) in which it may attempt to authenticate as a user.
    • The attacker runs a long offline computation to make password lookup tables.
  • Online phase
    • The attacker compromises the server and obtains the PWD file.
    • The attacker now performs a small online phase computation to obtain the users’ passwords.

This PAKE 2 scheme is not secure against a precompute-online attack either. Explain an attack.