CM30173: Cryptography
eserved@d =[@let@token art VI
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Part VI
Signature schemes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
RSA signature scheme
Definition
Let n = pq, p, q prime.
P = A = Zn
K = {(n, p, q, a, b) | ab ! 1 (mod !(n))}
For k = (n, p, q, a, b) ” K we have
sig
k
(x) = xa (mod n)
and
verk(y) = t # x ! y
b (mod n)
for x, y ” Zn.
sig
k
is private and verk is public
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Anyone can create a forgery!
Alice has RSA key k. To create a forgery:
1 Choose random y
2 Compute ek(y)
3 y = sig
k
(x) is now a valid signature for x
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Anyone can create a forgery!
Alice has RSA key k. To create a forgery:
1 Choose random y
2 Compute ek(y)
3 y = sig
k
(x) is now a valid signature for x
This is a key-only existential forgery
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Multiplicative property
Let x1, x2 be two messages with signatures
y1 = sigk(x1) and y2 = sigk(x2). Notice that
verk(x1x2 (mod n), y1y2 (mod n)) = t
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Multiplicative property
Let x1, x2 be two messages with signatures
y1 = sigk(x1) and y2 = sigk(x2). Notice that
verk(x1x2 (mod n), y1y2 (mod n)) = t
An attacker can create a valid signature on
message x1x2.
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Multiplicative property
Let x1, x2 be two messages with signatures
y1 = sigk(x1) and y2 = sigk(x2). Notice that
verk(x1x2 (mod n), y1y2 (mod n)) = t
An attacker can create a valid signature on
message x1x2.
This is a known message existential forgery
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
A variation on the theme
Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.
1 Oscar finds x1, x2 ” Zn such that
x ! x1x2 (mod n)
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
A variation on the theme
Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.
1 Oscar finds x1, x2 ” Zn such that
x ! x1x2 (mod n)
2 Oscar requests Alice’s signature on x1 and x2. She
sends him y1 = sigk(x1) and y2 = sigk(x2)
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
A variation on the theme
Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.
1 Oscar finds x1, x2 ” Zn such that
x ! x1x2 (mod n)
2 Oscar requests Alice’s signature on x1 and x2. She
sends him y1 = sigk(x1) and y2 = sigk(x2)
3 Oscar now creates a signature y1y2 (mod n) for
x = x1x2 (mod n)
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
A variation on the theme
Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.
1 Oscar finds x1, x2 ” Zn such that
x ! x1x2 (mod n)
2 Oscar requests Alice’s signature on x1 and x2. She
sends him y1 = sigk(x1) and y2 = sigk(x2)
3 Oscar now creates a signature y1y2 (mod n) for
x = x1x2 (mod n)
This is a chosen message selective forgery
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
The process
x ” {0, 1}!
$ z = h(x) ” P
$ y = sig
k
(z) ” A
h a public hash function
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
The process
x ” {0, 1}!
$ z = h(x) ” P
$ y = sig
k
(z) ” A
h a public hash function
(x, y) is then transmitted
Verification is performed by reconstructing
z = h(x) and then checking that verk(z, y) = t
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What do we mean by secure? (Again!)
As well as considering the security of the signature
scheme we now have to consider what properties h
must satisfy to prevent attack.
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What do we mean by secure? (Again!)
As well as considering the security of the signature
scheme we now have to consider what properties h
must satisfy to prevent attack.
I’ll tell you the attacks, you tell me the required
property…
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 1
Oscar has a valid signature pair (x, y) where
y = sig
k
(h(x)) previously signed by Alice.
Oscar computes h(x) and finds x” %= x such that
h(x”) = h(x)
Oscar has found a valid signature pair (x”, y)
y is now a forgery for x”
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 1
Oscar has a valid signature pair (x, y) where
y = sig
k
(h(x)) previously signed by Alice.
Oscar computes h(x) and finds x” %= x such that
h(x”) = h(x)
Oscar has found a valid signature pair (x”, y)
y is now a forgery for x”
What type of attack is this?
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 1
Oscar has a valid signature pair (x, y) where
y = sig
k
(h(x)) previously signed by Alice.
Oscar computes h(x) and finds x” %= x such that
h(x”) = h(x)
Oscar has found a valid signature pair (x”, y)
y is now a forgery for x”
What type of attack is this?
What property of h do we require to avoid this?
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 2
Oscar finds two messages x %= x” such that
h(x) = h(x”)
Oscar gives x to Alice and persuades her to sign
h(x), Alice sends back signature y
Oscar now has a valid signature pair (x”, y)
y is a forgery for x”
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 2
Oscar finds two messages x %= x” such that
h(x) = h(x”)
Oscar gives x to Alice and persuades her to sign
h(x), Alice sends back signature y
Oscar now has a valid signature pair (x”, y)
y is a forgery for x”
Type of attack?
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 2
Oscar finds two messages x %= x” such that
h(x) = h(x”)
Oscar gives x to Alice and persuades her to sign
h(x), Alice sends back signature y
Oscar now has a valid signature pair (x”, y)
y is a forgery for x”
Type of attack?
Property of h?
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 3
Alice is using a signature scheme in which it is
possible to forge signatures on random messages z
(e.g. RSA)
That is, the scheme is subject to key-only
existential forgery
Oscar computes a signature on some message
digest z and finds some x such that z = h(x)
Oscar has a valid signature pair (x, y)
y is a forgery for x
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack 3
Alice is using a signature scheme in which it is
possible to forge signatures on random messages z
(e.g. RSA)
That is, the scheme is subject to key-only
existential forgery
Oscar computes a signature on some message
digest z and finds some x such that z = h(x)
Oscar has a valid signature pair (x, y)
y is a forgery for x
What property do we need for h?
Signature schemes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes