Digital Signatures Flashcards
What are the characteristics of digital signatures?
- Goal: integrity – Message came from sender & is unmodified
- Public verifiability: Everybody with access to pk can verify a signature.
- Transferability: One can convince others of the signature’s validity.
- Non-repudiation: Alice cannot repudiate that she has signed the message.
- Key authenticity: Publish pk by distributing it with integrity.
Compare Digital Signatures vs MACS
Digital signatures is the asymmetric equivalent of MACS they have no preshared secret whereas MACS need key exchange. Digital Signatures has a private key independent of verifiers and macs have secret key for each pair of parties. In Digital signatures, anyone who wants to verify can verify but with macs only the dedicated partner can verify. With digital signatures you only have one key to keep secret but with macs you need a large number of keys. Signatures provide non-repudiation whereas macs are deniable but they are 2-3 orders of magnitude faster than signature schemes.
What is digital signatures used for?
Email, contracts, etc
one use: Software/ Update Distribution (the vender gives a public key, when you receive an update, it signs it with secret key so you can verify)
What is existential unforgeability and how can we prove it?
A signature scheme is existentially unforgeable under an adaptive chosen-message attack if all probabilistic and polynomial-time adversaries A only have negligible success probability.
A gets signatures on an arbitrary set of messages m in Q.
A wins the game if it can provide a valid message signature pair not already signed.
What are some attacks on Textbook RSA Signatures?
1 - No message attack
Adversary A only has access to pk=(N, e).
So the adversary start off by a random number that he pretends is the signature. and you encrypt this number with RSA (raise to public exponent e ) and gets the corresponding message. so by that the adversary broke existential unforgeability.
This is essentially working the RSA process backwards: instead of encrypting a message m to get a ciphertext σ, Alice decides on a “ciphertext” σ and computes the corresponding “message” m
2 - Selected Message Attack I
Adversary A has access to pk=(N, e) and can obtain two signatures from the signer.
How can A forge a signature on any chosen message m?
In a Selected-Message Attack against RSA signatures, the attacker cleverly manipulates two chosen messages such that their product, when each is signed separately, results in a valid signature for a third message. This is possible due to the multiplicative property of RSA. The attacker chooses a random message, obtains its signature, calculates a second message to neutralize the first in the product modulo N, obtains the signature for the second message, and multiplies the two signatures. The result is a valid signature for the target message, which compromises the security of the signature scheme
What can we implement for Textbook RSA Signatures to solve the problem of no message attack and selected message attack?
Hashed RSA where you hash the message before you do RSA signing
- we check if the hashes match.
- No-message attack wont work for example because hash function is collision resistant
- Hash is also not homophorbic so you cant get a no- message attack
Briefly explain the authenticity bootstrap problem and a solution for it
public key sent over the wire with no protection causes an authenticity problem. An adversary can send over their own public key with their own secret key.
How to state trust in a key?
- Certification authority (universally trusted) inspects Alice’s public key and sends signed saying its actually alices public key. so then Alice sends her public key with a signed signature from CA
- The certification authority knows the public key is from Alice. Alice needs to prove she has the corresponding secret key. Alice needs to sign a random nonce so they know they have the corresponding secret key
What do public key certificates contain?
A public-key certificate is a data structure consisting of a data part and a signature part.
The data part contains cleartext data including, as a minimum, a public key and a string identifying the subject entity to be associated with it.
lot of scaffolding to make sure its the right entity
The signature part consists of the digital signature of a certification authority over the data part.
It, thereby, binds the subject entity’s identity to the specified public key.
What are some auxiliary data in public key certificates?
- Validity period of the public key
- A serial number/key identifier identifying the certificate/key
- Additional information about subject entity
- Additional information about key (e.g., algorithm, intended use)
- Quality measures related to identification, generation of key pair, etc.
- Information facilitating the verification of the signature
Briefly explain the public key certificate verification procedure
- Acquire the authentic public key pkc of the CA
- Obtain an identifying string idA which uniquely identifies party A
- Acquire over an unsecure channel the public key certificate pkA of party A, agreeing with the identifying string idA
- Verify:
a) current data and time against the validity period of pkA
b) current validity of CA’s public key pkc
c) signature on A’s certificate using the CA’s pkC
d) Certificate on pkA not revoked - If all checks succeed, accept pkA in the certificate as authentic public key
How to create a certificate chain?
Charlie is a Certificate Authority (CA) that issues digital certificates. Charlie uses his private key (sk_c) to sign Alice’s public key (pk_A), which effectively endorses Alice’s identity. Alice then uses her private key (sk_A) to sign Bob’s public key (pk_B). Each step involves a party using their private key to sign another’s public key, creating a chain of trust. Finally, Bob uses his private key (sk_B) to sign a message (m) that Dee will receive. Dee can verify the message signed by Bob by checking it against Bob’s public key, whose authenticity is backed by Alice, and in turn, Alice’s public key is backed by the CA, Charlie. This chain ensures that Dee can trust the message came from Bob, as long as she trusts the CA at the root of the chain.
What is a public key infrastructure (PKI)?
The Root-CA is the most trusted entity in the PKI and is responsible for issuing digital certificates that authenticate the identity of other entities within the infrastructure. Charlie issues certificates to two subordinate Certificate Authorities (Sub-CAs): Chang and Charlene. He does this by signing their public keys (pk_c1 for Chang and pk_c2 for Charlene) with his private key (sk_c). The signing process essentially means that Charlie is vouching for the authenticity of Chang’s and Charlene’s identities. These Sub-CAs can then issue certificates to other entities, extending the trust chain established by the Root-CA. This structure allows for a scalable trust model where the Root-CA does not have to directly sign every certificate in the network, but can delegate trust to Sub-CAs.
Sub-CA’s will accept any server endorsed by the Root-CA so if that is compromised, there is a problem
What is the web of trust in a public key signature scheme?
In this system, Charlie trusts Alice and Dee, as indicated by him signing their public keys with his private key. Alice and Dee reciprocate this trust by signing Charlie’s public key with their private keys. Furthermore, Alice, who is trusted by Charlie and Dee, signs a message to Bob using her private key. Bob can then use Alice’s public key to verify the message’s authenticity. This web of trust model allows for decentralized trust, where individuals can trust a message if they trust the signer’s public key and the chain of individuals who have vouched for each other’s keys.
We are given an El Gamal encryption scheme with the following parameters. The prime modulus p is 587. We
are operating in a group G with generator g=12 and prime oder q=293. The public key h=431.
An adversary Eve happens to observe two cipher texts both with the first cipher text part c1=430. The other two cipher text parts are c2,1=79 and c2,2=158.
What relation (multiple of one another) can the adversary determine about the two plain texts corresponding to these two cipher texts?
-> 2
The two observed ciphertexts share the same c1 value, which implies that the same k value was used in both
encryptions (which is a mistake in using El Gamal, as k should be unique for each encryption).
Given values
c2_1 = 79
c2_2 = 158
# Compute the relationship between the plaintexts m1 and m2
relationship = c2_1 / c2_2
relationship
OUTPUT: 0.5
What are the properties we expect to obtain from a secure padding scheme for public-key encryption?
→ Structure
Correct. Structure prevents mangling of cipher texts.
→ Randomization
Correct. Randomization is crucial to achieve CPA security.
→ Use of full message length
Correct. Using the full message length prevents attacks on short messages.
