186 lines
6.0 KiB
Markdown
186 lines
6.0 KiB
Markdown
# 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
|
||
|
||
**P**ublic **K**ey **C**ryptography **S**tandards
|
||
|
||
- 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** **S**ignature **S**cheme with **A**ppendix
|
||
|
||
- “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
|