Digital Signatures

• Application of public key cryptography

Signatures

• 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
• Does not scale!

Electronic Signature

• Create a binary signature and append this to any document
• Isn't very secure as anyone can copy this
• In many cases two parties will share a symmetric key $k$
• Non repudiation - Can the signer deny having signed a message

Message Authentication

Authenticity - The sender is confirmed as authentic - only 2 parties have generated the signature Integrity - The signature confirms the message hasn't been altered - better than real-world signature scheme Non-Repudiation - Don't have this - symmetric key means that either parties could have sent the message

Public Key Signatures

• By using asymmetric cryptography can add non-repudiation to the list of features
• 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
• Often keep $e$ small
• This priorities 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
• E.g. a replay attack using a previous ($m,s$) wouldn't count as a forgery
• 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
• 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

Selective Forgeries

• The attacker is able to create a valid message/signature pair 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 likely imply that the attacker had obtained the private key

Existential Forgeries

• An attacker has access to Alice's public key
• They can calculate: $s = random$...
• It is trivial to generate message and signature pairs based on RSA public key

Malleability

• RSA is also malleable ???
• More control for an attacker than we would like to have for a signature scheme
• 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

Hash-the-sign

• Common to have the message within any padding scheme
• ..
• Verification recomputes the hash:
• ...
• 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

PKCSv1.5

• Modern padding schemes use hashing and padding for security
• Prevents existential forgeries, and attacks on small messages

RSASSA-PSS

• RSA Signature Scheme 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

PSS Encoding

1. Hash message
2. Concatenate padding, has 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$ xor $MGF(H)$ to create maskedDB
7. Output is maskedDB, H and a constant 0xbc