Cryptography Reference
In-Depth Information
Existential Forgery Attack Against RSA Digital Signature
Alice
Oscar
Bob
k
pr
=
d
k
pub
=(
n
,
e
)
(
n
,
e
)
←−−−−−−
(
n
,
e
)
←−−−−−−
1. choose signature:
s
∈
Z
n
2. compute message:
x
≡
s
e
mod
n
(
x
,
s
)
←−−−−−−
verification:
s
e
≡
x
mod
n
since
x
=
x
=
⇒
valid signature!
The attacker impersonates Bob, i.e., Oscar claims to Alice that he is in fact Bob.
Because Alice performs exactly the same computations as Oscar, she will verify
the signature as correct. However, by closely looking at Steps 1 and 2 that Oscar
performs, one sees that the attack is somewhat odd. The attacker chooses the signa-
ture first and then
computes
the message. As a consequence, he cannot control the
semantics of the message
x
. For instance, Oscar cannot generate a message such as
“
Transfer $1000 into Oscar's account
”. Nevertheless, the fact that
an automated verification process does not recognize the forgery is certainly not a
desirable feature. For this reason, schoolbook RSA signature is rarely used in prac-
tice, and padding schemes are applied in order to prevent this and other attacks.
RSA Padding: The Probabilistic Signature Standard (PSS)
The attack above can be prevented by allowing only certain message formats.
Roughly speaking, formatting imposes a rule which allows the verifier, Alice in our
examples, to distinguish between valid and invalid messages; this is called
padding
.
For example, a simple formatting rule could specify that all messages
x
have 100
trailing bits with the value zero (or any other specific bit pattern). If Oscar chooses
signature values
s
and computes the “message”
x
s
e
mod
n
, it is extremely un-
likely that
x
has this specific format. If we require a certain value for the 100 trailing
bits, the chance that
x
has this format is 2
−
100
, which is considerably lower than
winning any lottery.
We now look at a padding scheme which is widely used in practice. Note that a
padding scheme for RSA encryption was already discussed in Sect. 7.7. The
prob-
abilistic signature scheme
(RSA-PSS) is a signature scheme based on the RSA
cryptosystem. It combines signature and verification with an encoding of the mes-
sage.
≡
