Hash Functions and Digital Signatures Questions

Combines the relationship between cryptographic hashing and digital signature schemes and covers authentication and non repudiation. Candidates should understand how hashing is used together with signing to produce compact and secure signatures, and why message hashing is required before signing. Topics include signature algorithms and their security properties, for example RSA with Probabilistic Signature Scheme, elliptical curve signatures such as ECDSA and EdDSA, and differences in randomness and determinism across schemes. Understand verification workflows, signature malleability issues, replay and forgery attacks, use cases for authentication and non repudiation, and migration away from deprecated primitives. Candidates should also be able to explain practical considerations such as proper padding, deterministic versus randomized signatures, key management basics, and common pitfalls when implementing signing and verification in protocols.

EasyTechnical

64 practiced

What is signature malleability? Give a concrete explanation and show how an ECDSA signature (r, s) can be transformed into another valid signature for the same message (for example by mapping s to n - s). Explain why malleability matters for systems like blockchains, multi-signature protocols, or transaction identifiers.

Sample Answer

**Clear definition**

Signature malleability** is the property that a valid signature can be transformed into a different signature that still verifies for the same message and public key. It breaks the one-to-one mapping between (message, key) and signature.

**Concrete ECDSA example**

ECDSA signature is a pair (r, s) modulo curve order n. Verification checks that:

text

s^{-1} * z * G  +  s^{-1} * r * Q  =  R   (x-coordinate gives r)

Because s and n - s produce the same group point when multiplied by the inverse (up to sign in the elliptic curve group), if (r, s) is valid then (r, n - s) is also valid (assuming r nonzero). Intuitively:

text

(s)^{-1}  ≡  (n - s)^{-1} * (-1)  (mod n)

so the verification equation still holds after appropriate sign handling.

**Why it matters**

- Blockchains: transaction IDs often derive from signed data. Malleable signatures let an attacker change a signature and therefore the txid, breaking assumptions about immutability, replay protection, or dependency chains.- Multi-signature protocols: combining signatures or aggregating them assumes unique encodings; malleability complicates correct aggregation and verification and opens forgery/replay vectors.- Protocols & auditing: non-unique signatures complicate logs, replay detection, and can enable double spending or griefing.

**Mitigations**

- Enforce low-s values (s <= n/2) canonicalization- Use malleability-resistant schemes (EdDSA, Schnorr with unique encoding)

EasyTechnical

59 practiced

Why are deterministic signatures like those produced under RFC 6979 used? Describe the advantages (eliminating RNG dependency, reproducibility for testing) and disadvantages (predictability across identical messages, possible correlation with key leakage) and how deterministic methods relate to side-channel resistance.

HardTechnical

55 practiced

Compare signature malleability across these schemes: RSA-PSS, RSA PKCS#1 v1.5, ECDSA, EdDSA, Schnorr, and BLS. For each scheme state whether malleability exists, give a concise example or rationale (e.g., s -> n-s for ECDSA), and explain how malleability impacts higher-level protocols like blockchain transactions, TLS handshakes, or certificate transparency logs.

Sample Answer

**High-level summary**- Malleability means you can transform a valid signature into a different valid signature for the same message without the signer’s secret. This matters for transaction IDs, logs, and protocols that treat signatures as stable identifiers.

**RSA-PSS**- Malleability: effectively none in practice.- Rationale: PSS introduces randomized, non-algebraic padding so the signature operation is not a simple homomorphism; multiplicative attacks are broken.- Protocol impact: safe for use where unique, non-malleable signatures are required (TLS, CT).

**RSA PKCS#1 v1.5**- Malleability: algebraically malleable (multiplicative).- Rationale/example: RSA is multiplicative: given sig(m1)=s1 and sig(m2)=s2, s1*s2 mod n is a signature of m1*m2. PKCS#1 v1.5’s deterministic encoding still doesn’t remove the multiplicative structure.- Protocol impact: multiplicative malleability can break systems that assume signature uniqueness; careful domain separation and protocol-level checks are required.

**ECDSA**- Malleability: yes (simple).- Rationale/example: (r,s) is valid and (r, n - s) is also valid because verification uses s inverse; common description: s -> n - s.- Protocol impact: changes transaction IDs (Bitcoin historically), requires canonical-s normalization (enforce low-s) to avoid malleability.

**EdDSA (e.g., Ed25519)**- Malleability: largely prevented by specification; implementations enforce canonical encodings.- Rationale: EdDSA is deterministic and spec enforces canonical s in [0, L-1] and canonical R encoding; naive point-negation transforms generally produce non-canonical encodings and are rejected.- Protocol impact: when implemented per-spec, suitable for systems needing non-malleable signatures; beware non-canonical encodings in lax implementations.

**Schnorr**- Malleability: simple two-form malleability (R, s) ↔ (−R, −s) if encodings allow negatives.- Rationale: verification sG = R + eX; negating R and s preserves equation. Protocols can mandate canonical R (e.g., x-only with even y) and canonical s to remove malleability.- Protocol impact: Schnorr is preferred for multisig/aggregation (Bitcoin Taproot) after canonicalization; without it, tx IDs or aggregated signatures can be malleated.

**BLS**- Malleability: different class — deterministic per private key but supports aggregation/combination which is protocol-level malleability.- Rationale: single BLS sig is unique if canonicalized. However signature aggregation (sum of sigs) and pairing properties enable flexible transforms (and also enable rogue-key aggregation attacks if keys aren’t committed).- Protocol impact: excellent for compact multisig/aggregation, but protocols must use anti-rogue techniques (key aggregation, proof of possession) and canonical encodings to avoid malleability/forgery in aggregations.

Practical mitigations across schemes- Enforce canonical encodings and low-s/normalized s where relevant.- Use padding schemes that break algebraic structure (PSS).- For aggregating schemes (Schnorr, BLS) use key-commitment or proof-of-possession and domain separation.- Treat signatures as non-unique unless protocol explicitly enforces uniqueness; design identifiers (txids, CT entries) to hash canonical encodings.

HardTechnical

63 practiced

You have access to an ECDSA signing oracle that leaks one bit of information about each ephemeral nonce k (for example, whether k is even or odd). Design an attack to recover the signer’s private key. Describe the math behind your approach, estimate sample complexity (number of signatures needed), and explain practical obstacles and countermeasures.

Sample Answer

**Approach summary (high level)** Use the leaked 1 bit per nonce to convert ECDSA signatures into approximate linear equations in the private key d and unknown small integers. Collect many such equations and solve the Hidden Number Problem with a lattice (LLL / Babai) to recover d.

**Math / derivation** From ECDSA signature (r, s) on message with hash h and group order q:

text

s * k ≡ h + r * d   (mod q)

Solve for k:

text

k ≡ s^{-1} * (h + r * d)   (mod q)

If the oracle gives b = k mod 2, write k = 2 t + b for integer t. Substitute:

text

2 t + b ≡ s^{-1} * (h + r * d)   (mod q)

Rearrange to linear form:

text

r' * d - 2 t ≡ c   (mod q)   where r' = s^{-1} r,   c = s^{-1} h - b  (all modulo q)

Lift to integers by choosing representative in [ -q/2, q/2 ] to get:

text

| r' * d - 2 t - c |  < q/2

Unknowns are integer d (same for all eqns) and small t_i. This is an instance of the Hidden Number Problem / closest vector problem and can be attacked by building a lattice whose short vector encodes d.

**Attack steps**- Collect m signatures with leaked bits b_i, compute r'_i and c_i.- Build lattice with rows encoding 2 and r'_i scaled by a factor B (to balance sizes) and target vector of c_i.- Apply LLL to find small integer solution vector; use Babai rounding to recover candidate d.- Verify d by checking a public key.

**Sample complexity (estimate)** Required m is proportional to bit-length of q. In practice for single-bit leaks, experiments and literature indicate m ≈ 1–3 × n where n = bit-length(q). For a 256-bit q, expect O(300–800) signatures. Exact number depends on lattice conditioning and scaling choices.

**Practical obstacles**- Lattice attacks rely on good scaling and sufficient equations; LLL may fail if m too small or noise (wrong bit) exists.- Modular reductions and wrap-around require careful lifting to integers.- Real-world noise: oracle errors, rate-limited signing, or non-uniform nonce selection degrade success.- Computational cost: lattice dimension equals m+1; large m increases runtime and LLL may be slow.

**Countermeasures**- Use deterministic nonces (RFC6979) or strong CSPRNG so no leakage.- Blinding: randomize k or use multiplicative/additive blinding per-signature.- Ensure constant-time implementations to avoid side-channels leaking nonce bits.- Use signature schemes with provable nonce reuse protections or adopt EdDSA style deterministic constructions.

This attack is well-studied (Bleichenbacher / Boneh-Venkatesan / Nguyen-Shparlinski styles) and demonstrates that even 1 bit of per-signature leakage suffices to recover the private key with a lattice-based Hidden Number Problem solver given enough samples.

EasyTechnical

61 practiced

Define and distinguish the three standard security properties of cryptographic hash functions: preimage resistance, second-preimage resistance, and collision resistance. For each property, give a concrete example of how a failure of that property could break a digital signature scheme or a MAC in a real system.

Unlock Full Question Bank

Get access to hundreds of Hash Functions and Digital Signatures interview questions and detailed answers.

Join thousands of developers preparing for their dream job.