Unit 5: Digital Signature and Key management - Subjective Questions

Digital signature: A digital signature is a cryptographic value generated from a message and the signer's private key. It allows a recipient to verify the message's origin and integrity using the corresponding public key.

Security services provided:

• Authentication: Confirms the identity of the signer.
• Integrity: Detects unauthorized modification of the signed message.
• Non-repudiation: Prevents the signer from credibly denying the signature, provided the private key remained under the signer's control.
• Public verifiability: Anyone possessing the authenticated public key can verify the signature.

Digital signatures do not provide confidentiality by themselves. Encryption must be used separately when message secrecy is required.

Digital signature versus handwritten signature:

• A digital signature depends on both the message and the private key, whereas a handwritten signature is usually similar for every document.
• Changing a digitally signed message invalidates its signature.
• A digital signature can be verified automatically using a public key.
• A handwritten signature is physically associated with a document, while a digital signature is represented as data and must be cryptographically bound to the message.

Digital signature versus message authentication code (MAC):

• A digital signature uses an asymmetric key pair; a MAC uses a shared secret key.
• A signature can provide non-repudiation, while a MAC generally cannot because either party sharing the key can generate it.
• Signature verification may be public, whereas MAC verification is restricted to parties possessing the shared secret.
• MAC operations are generally faster than public-key signature operations.

Signature generation:

1. The signer generates a private key and a corresponding public key .
2. A cryptographic hash function is applied to message :
   
3. The signer applies the signing algorithm to using :
   
4. The pair is sent to the recipient.

Signature verification:

1. The recipient obtains an authenticated copy of .
2. The recipient computes:
   
3. The verification algorithm processes , , and .
4. The signature is accepted only if:
   

A secure hash function improves efficiency and ensures that even a small change in produces a different digest.

Direct digital signature:

• The sender signs the message using a private key.
• The receiver verifies it directly using the sender's authenticated public key.
• No third party participates in each signing transaction.
• It is efficient, but its reliability depends on private-key security, public-key authenticity, and trusted timestamps.

Arbitrated digital signature:

• A trusted arbiter participates in the communication.
• The sender submits the signed message to the arbiter.
• The arbiter validates it and forwards or certifies it for the receiver.
• The arbiter can help resolve disputes and verify transaction timing.

Comparison:

• Direct schemes provide better efficiency and privacy.
• Arbitrated schemes provide stronger dispute resolution and transaction control.
• Arbitrated schemes introduce delay, dependence on a trusted third party, and a possible single point of failure.

Attack models based on the attacker's capabilities:

• Key-only attack: The attacker knows only the signer's public key.
• Known-message attack: The attacker has valid signatures for messages that were not selected by the attacker.
• Generic chosen-message attack: The attacker obtains signatures for selected messages before choosing a specific target.
• Directed chosen-message attack: Queries are selected for an intended target or attack strategy.
• Adaptive chosen-message attack: Later signature queries depend on the results of earlier queries.

Possible attack outcomes:

• Total break: The private key is recovered.
• Universal forgery: Signatures can be generated for arbitrary messages.
• Selective forgery: A valid signature is generated for a particular target message.
• Existential forgery: At least one new valid message-signature pair is produced.

A strong signature scheme should be existentially unforgeable under an adaptive chosen-message attack, commonly abbreviated as EUF-CMA.

Hash-collision attack: An attacker finds different messages and such that . A signature on one message may then appear valid for the other. Use collision-resistant hash functions such as SHA-256 or SHA-3.

Replay attack: A valid signed message is captured and submitted again. Include timestamps, sequence numbers, transaction identifiers, expiration times, or nonces in signed data.

Private-key compromise: An attacker possessing the private key can create apparently legitimate signatures. Protect keys using hardware security modules, strong access controls, secure backups, revocation procedures, and key rotation.

Implementation weaknesses: Side-channel leakage, faulty randomness, incorrect padding, and timing differences can expose secrets or permit forgery. Use reviewed libraries, constant-time implementations, tested random-number generators, and standardized encodings.

Signatures should also include clear domain separation and contextual information to prevent a valid signature from being misused in another protocol.

Key generation:

1. Select large primes and , and compute .
2. Compute .
3. Choose such that .
4. Compute satisfying:
   
5. The public key is and the private key is .

Signing: For an appropriately encoded digest , calculate:

Verification: Calculate:

The signature is accepted when after validating the required encoding.

Correctness: Since for some integer ,

under the conditions established by RSA and Euler's theorem. In practice, RSA signatures must use a secure encoding such as RSA-PSS, rather than applying raw RSA directly to a message.

Problems with textbook RSA:

• RSA has a multiplicative property: if and , then
  
  which can support forgery attacks.
• It is deterministic, so the same message produces the same signature.
• It lacks secure message formatting and domain separation.
• Signing arbitrary values can expose the scheme to chosen-message attacks.

RSA-PSS protection:

• Hashes the message before signing.
• Introduces a random salt, making signatures probabilistic.
• Uses a mask generation function to produce a structured encoded block.
• Validates the complete encoding during verification.
• Has strong security justification under standard assumptions when correctly parameterized.

Thus, implementations should use standardized RSASSA-PSS with a secure hash function and adequate RSA key size.

Key generation:

• Choose a large prime and a generator of an appropriate multiplicative group modulo .
• Select a private key with .
• Compute the public key:
  

Signature generation:

1. Compute .
2. Select a fresh random integer satisfying .
3. Compute:
   
4. Compute:
   
5. The signature is .

Verification: Check the valid range of and then verify:

The random value must be unpredictable, secret, and never reused.

In ElGamal signing, the value is selected so that:

Multiplying by gives:

Therefore:

Because exponents in the multiplicative group modulo are reduced modulo ,

This can be separated as:

Using the public key and signature component gives:

Hence, a correctly generated signature satisfies the verification equation.

For an ElGamal signature,

which can be rearranged as:

If the random value is disclosed, an attacker may solve for private key from:

subject to the corresponding modular solvability conditions.

If the same is reused for two messages, the signatures have the same . For hashes and signature components :

This relation can reveal , after which can often be recovered.

Countermeasures:

• Generate a unique unpredictable nonce for every signature.
• Use a cryptographically secure random-number generator.
• Use approved deterministic nonce-generation procedures where the signature standard permits them.
• Protect nonce generation against side-channel and fault attacks.

Parameters and keys: Let be a cyclic group of prime order with generator . The signer selects private key and computes public key . One common convention is shown below; equivalent standards may use and a different response sign.

Signing:

1. Select a fresh nonce .
2. Compute commitment:
   
3. Compute challenge:
   
4. Compute response:
   
5. Output signature .

Verification:

1. Reconstruct the commitment:
   
2. Compute:
   
3. Accept if .

Correctness follows because .

RSA:

• Security is based on the difficulty of integer factorization and the RSA problem.
• Uses modular exponentiation over a composite modulus.
• Secure implementations use RSA-PSS encoding.
• Signatures are typically comparable in size to the RSA modulus.

ElGamal:

• Security is based on the discrete logarithm problem.
• Requires a fresh random nonce for every signature.
• Produces two signature components and is relatively long in its basic form.
• Forms the conceptual basis for several later signature schemes.

Schnorr:

• Security is based on the discrete logarithm problem in a selected group.
• Has a simple structure and supports compact signatures.
• Its security proof is closely connected to the random-oracle model.
• Requires a unique secure nonce, like ElGamal-derived schemes.

All three require authenticated public keys, secure parameter sizes, validated inputs, and protection of private-key operations.

Digital signature standards specify approved algorithms, parameters, encodings, key sizes, hash functions, and validation rules so that independently developed systems can interoperate securely.

Digital Signature Algorithm (DSA):

• Standardized in the Digital Signature Standard (DSS).
• Operates in a finite-field subgroup.
• Its security is based on the discrete logarithm problem.
• Generates a two-component signature .
• Requires a unique secret nonce for every message.
• Traditionally supports only signature operations, not encryption.

Other standardized approaches:

• RSA signatures: Commonly standardized using RSA-PSS.
• ECDSA: A DSA variant using elliptic-curve groups, offering smaller keys and signatures.
• EdDSA: Uses Edwards curves and deterministic nonce derivation, with careful standardized encoding.

A standard is secure only when key generation, parameter validation, hashing, randomness, encoding, and implementation requirements are all followed.

Cryptographic hash function:

• Converts an arbitrary-length message into a fixed-length digest.
• Makes signing large messages efficient.
• Must resist preimage, second-preimage, and collision attacks.
• Ensures that a modified message produces a different verification result.

Timestamp:

• Records evidence that a signature existed at a particular time.
• Helps determine whether a signature was created before key expiration or revocation.
• Must come from a trustworthy source when legally significant timing is required.

Digital certificate:

• Binds a public key to an identified subject.
• Is signed by a certification authority (CA).
• Prevents an attacker from substituting an unauthenticated public key.
• Includes validity information, issuer details, key usage, and related attributes.

Together, these mechanisms bind the message, signer, public key, and relevant signing time into a verifiable trust framework.

Principal methods:

1. Physical delivery: One party securely delivers the shared key to the other. This is practical only for small or highly controlled systems.
2. Trusted third-party delivery: A trusted authority generates and securely delivers the key to both parties.
3. Distribution using an existing shared key: A new session key is encrypted with an older key-encryption key. Compromise of the long-term key threatens distributed keys.
4. Key Distribution Center (KDC): Each participant shares a long-term key with the KDC, which distributes temporary session keys.
5. Public-key transport: One party generates a symmetric session key and encrypts it using the recipient's authenticated public key.

Effective distribution must provide confidentiality, authentication, freshness, key separation, expiration, and resistance to replay. Session keys limit the amount of data exposed if an individual key is compromised.

Assume users and share long-term master keys and respectively with a Key Distribution Center (KDC).

Typical process:

1. requests a session with and includes a nonce .
2. The KDC generates a fresh session key .
3. The KDC returns information encrypted under , including , 's identity, , and a ticket for .
4. The ticket may be represented as:
   
5. forwards to .
6. and authenticate one another using challenge-response messages protected by .

Roles:

• The session key protects one communication session.
• The nonce associates the response with the current request and counters replay.
• The ticket allows to obtain the session key securely without direct prior contact with .

The KDC must be highly protected because it is trusted by all participants.

Symmetric-key distribution: A key is selected by one party or a trusted authority and securely transported to other participants. The receiving parties do not contribute equally to its value.

Symmetric-key agreement: Two or more parties jointly establish a shared secret, usually by combining contributions from each participant. The final symmetric key is commonly derived from an agreed secret using a key derivation function.

Required security properties:

• Key confidentiality: Outsiders cannot determine the established key.
• Mutual authentication: Each participant verifies the identity of the peer.
• Freshness: The resulting key is new and is not a replayed old key.
• Key confirmation: Each side obtains evidence that the peer derived the same key.
• Known-key security: Compromise of one session key does not expose other session keys.
• Forward secrecy: Compromise of long-term credentials does not reveal earlier session keys when ephemeral contributions were securely erased.
• Resistance to man-in-the-middle attacks: Protocol messages and identities must be authenticated.

Let be a group with generator and suitable order.

Agreement process:

1. Alice chooses a fresh private value and sends:
   
2. Bob chooses a fresh private value and sends:
   
3. Alice computes:
   
4. Bob computes:
   
5. Both derive the session key using contextual data:
   

Plain Diffie-Hellman is vulnerable to a man-in-the-middle attack because the exchanged values are not authenticated. Authentication can be added using digital signatures, certificates, pre-shared keys, or an authenticated key-exchange protocol. Including identities and the transcript in the key derivation or authentication calculation prevents substitution and unknown key-share attacks. Ephemeral Diffie-Hellman can provide forward secrecy.

Public announcement: Users publish or transmit their public keys. It is simple but vulnerable to key substitution and impersonation.

Public directory: A trusted directory maintains identity-to-public-key mappings. Entries must be securely registered, protected against modification, and retrieved through authenticated channels.

Public-key authority: An online trusted authority returns authenticated and fresh public-key information for each request. It provides strong control but adds communication overhead and creates a central availability dependency.

Public-key certificates: A certification authority signs a structure that binds an identity to a public key:

Certificates can be distributed through untrusted channels because recipients verify the CA's signature. They support scalable offline verification but require certificate-chain validation, expiration checks, hostname or identity checks, and revocation handling.

The certificate-based public key infrastructure approach is widely used because it combines scalability with authenticated key binding.