notes/docs/lectures/cryptography/14_digital_signatures.md

Digital Signatures

• A signature is proof of authenticity of the sender
• Verification is performed by checking the signature against a known signature
• Mostly works for the real world, not very robust
  • This does not scale

Electronic Signature

• Create a binary signature and append this to any document

This is incredibly easy to forge, we need a cryptographic solution

• In many cases two parties will share a symmetric key k

Verification

To verify a message one must have the message and the signature

(x,y)\rightarrow ver_k(x,y)=\begin{cases}\textrm{True; y is valid}\\\textrm{False; y is invalid}\end{cases}

Non-repudiation

Symmetric keys for verification don’t work, because both parties have access to key k, either party can sign it.

Bob needs to be able to prove that Alice and no one else signed the signature

This requires using a private key

Symmetric signatures give us:

Authenticity: The sender is confirmed as authentic - only Alice or Bob could have generated the signature

Integrity: The signature confirms the message hasn’t been altered - this is better than the real-world signature scheme

Non-Repudiation: We don’t have this - the symmetric key means that either Alice or Bob could have sent the message

Public Key Signatures

• By using asymmetric cryptography we have non-repudiation.

RSA Signatures

Notation:

• m - message
• s - signature

Efficiency

Signing: x^d\mod n

Verification: s^e\mod n

• Signing and verification require one use of the square and multiply algorithm
• Efficiency depends on the exponents
• We often keep e small
  • 65537=2^{16}+1=10000000000001_2
• This prioritises verification speed

Signature Forgeries

• A forgery is the ability to create a valid message / signature pair (m,s) where m hasn’t previously been signed by the legitimate signer
  • For example, a replay attack using a previous (m,s) wouldn’t count as a forgery
  • As we cannot control the message contents
• Various severities of attack exist depending on the control over the message m

Existential Forgeries

• The attacker is able to create a valid message / signature pair (m,s)
• There are no constraints on m, it may well be entirely random
• m does not need to be a valid message to be understood by a recipient

An attacker has access to Alice’s public key (n,e)

• They can calculate
  • s=\textrm{random}
  • m' =s^e\mod n
• It is trivial to generate message and signature pairs based on an RSA public key
  • Not very useful

Selective Forgeries

• The attacker is able to create a valid message / signature pair (m,s) where they have selected m in advance
• m may have some mathematical properties, or be all zeros etc.
• It is a requirement that m be fixed prior to the attack

Universal Forgeries

• The attacker can create a valid signature from any message m
• This is the strongest attack, and implies the previous attacks too
• In RSA, this would imply the attacker has access to the private key

Malleability

• RSA is also malleable: RSA(m_1\cdot m_2)=RSA(m_1)\cdot RSA(m_2)
• Given two messages x_1, x_2 and corresponding signatures s_1,s_2
  • (m_3,s_3)\equiv(m_1\cdot m_2, s_1\cdot s_2)(\mod m)
• This is more control for an attacker than we would like to have for a signature scheme
• Malleability is a weakness of encryption with textbook RSA too

Padding

• If we enforce rules about valid formatting on m, random messages produced by attackers are unlikely to pass

  • 

• Likelihood of a successful forgery is 2^{-y}

  • Probability of last bit 2^{-1}
  • Probability of last 2 bits 2^{-2}
  • etc. up to y

Hash-then-sign

• It is common to hash the message within any padding scheme
  • sig_{k_{prvA}}(x)\equiv H(x)^d \mod n
• Verification recomputes the hash
  • ver_{k_{pubA}}(x,s)= s^e \mod n \equiv H(x)'
  • H(x)\stackrel{?}{=}H(x)'
• Existential forgeries are much harder
  • You’d need a random message that’s also a valid hash
• Longer messages can be signed, the hash outputs a smaller message digest

PKCS v1.5

Public Key Cryptography Standards

• Modern padding schemes use hashing and padding for security
• Prevents existential forgeries, and attacks on small messages
  • This is deterministic, the same message gives the same signature

RSASSA-PSS

RSA Signature Scheme with Appendix

• “with appendix” refers to any scheme that sends (m,s) separately
• PKCS and similar schemes are deterministic
• The probabilistic signature scheme adds a random salt to the process, meaning repeated signatures on the same document produce different results
  • Doesn’t affect security that much; some standards have gone back to a probabilistic approach

PSS Encoding

1. Hash message
2. Concatenate padding, hash and salt to create M'
3. Hash M’ into final hash H
4. Append padding to salt to create data block DB
5. Expand H using MGF
6. Calculate DB \oplus MGF(H) to create maskedDB
7. Output is maskedDB, H and a constant 0xbc
   • 0xbc is just a constant, no specific meaning other than formatting
8. Use RSA to calculate signature and send (m,s) as normal

PSS Verifying

(if any of these steps fail, return false)

1. Use RSA public key to obtain unsigned signature
2. Check length and 0xbc constant
3. Split signature into maskedDB and H
4. Calculate MGF(H) and therefore DB
5. Check DB padding 00 .. .. 00 1
6. Extract salt from DB
7. Recreate M' from padding, message and salt
8. Calculate H(M')
9. Verify H(M')=H

Nothing is faster than RSA verification, signing is slower

It's quick because of how 65537 is structured