Scribed by Nick Jalbert
Summary
Today we begin to talk about signature schemes.
We describe various ways in which “textbook RSA” signatures are insecure, develop the notion of existential unforgeability under chosen message attack, analogous to the notion of security we gave for authentication, and discuss the difference between authentication in the private-key setting and signatures in the public-key setting.
As a first construction, we see Lamport’s one-time signatures based on one-way functions, and we develop a rather absurdly inefficient stateful scheme based on one-time signatures. The scheme will be interesting for its idea of “refreshing keys” which will be used next time to design a stateless, and reasonably efficient, scheme.
1. Signature Schemes
Signatures are the public-key equivalents of MACs. The set-up is that Alice wants to send a message to Bob, and convince Bob of the authenticity of the message. Alice generates a public-key/ secret-key pair , and makes the public key known to everybody (including Bob). She then uses an algorithm to compute a signature of the message; she sends the message along with the signature to Bob. Upon receiving , Bob runs a verification algorithm , which checks the validity of the signature. The security property that we have in mind, and that we shall formalize below, is that while a valid signature can be efficiently generated given the secret key (via the algorithm ), a valid signature cannot be efficiently generated without knowing the secret key. Hence, when Bob receives a message along with a signature such that outputs “valid,” then Bob can be confident that is a message that came from Alice. (Or, at least, from a party that knows Alice’s secret key.)
There are two major differences between signatures in a public key setting and MAC in a private key setting:
- Signatures are transferrable: Bob can forward to another party and the other party can be confident that Alice actually sent the message, assuming a public key infrastructure is in place (or, specifically that the other party has Alice’s public key).
- Signature are non-repudiable: Related to the first difference, once Alice signs the message and sends it out, she can no longer deny that it was actually her who sent the message.
Syntactically, a signature scheme is a collection of three algorithms such that
- takes no input and generates a pair where is a public key and is a secret key;
- Given a secret key and a message , outputs a signature ;
- Given a public key , a message , and an alleged signature , outputs either “valid” or “invalid”, with the property that for every public key/ secret key pair , and every message ,
The notion of a signature scheme was described by Diffie and Hellman without a proposed implementation. The RSA paper suggested the following scheme:
- Key Generation: As in RSA, generate primes , generate such that , define , and let and .
- Sign: for a message , the signature of is
- Verify: for a message and an alleged signature , we check that .
Unfortunately this proposal has several security flaws.
- Generating random messages with valid signatures: In this attack, you pick a random string and compute and now is a valid signature for . This can be an effective attack if there are a large number of messages that are useful to forge.
- Combining signed messages to create the signature of their products: Suppose you have and with valid signatures and respectively. Note that and . We can now generate a valid signature for :
- Creating signatures for arbitrary messages: Suppose the adversary wants to forge message . If it is able to get a valid signature for a random message and a specifically chosen message then the adversary can use the second attack to calculate a valid signature for (i.e. and .
Ideally, we would like the following notion of security, analogous to the one we achieved in the secret-key setting.
Definition 1 A signature scheme is existentially unforgeable under a chosen message attack if for every algorithm of complexity at most , there is probability that , given a public key and a signing oracle, produces a valid signature of a message not previously sent to the signing oracle.
It was initially thought no signature scheme could meet this definition. The so called “paradox” of signature schemes was that it seemed impossible to both have a scheme in which forgery is difficult (that is, equivalent to factoring) while simultaneously having this scheme be immune to chosen message attacks. Essentially the paradox is that the proof that a scheme is difficult to forge will generally use a black-box forging algorithm to then construct a factoring algorithm. However, if this scheme were subject to a chosen message attack, a new algorithm could be constructed which would simulate the constructed factoring algorithm and totally break the signature scheme. This new algorithm would be exactly the same as the one used in the forgery proof except every query to the black-box forging algorithm instead becomes one of the messages sent to the oracle. Goldwasser et al.’s paper “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks” gives further details and describes breaking the paradox.
2. One-Time Signatures and Key Refreshing
We begin by describing a simple scheme which achieves a much weaker notion of security.
Definition 2 (One-Time Signature) A signature scheme is a -secure one-time signature scheme if for every algorithm of complexity at most , there is probability that , given a public key and one-time access to a signing oracle, produces a valid signature of a message different from the one sent to the signing oracle.
We describe a scheme due to Leslie Lamport that is based on one-way function.
- KeyGen : pick a secret key which consists of -bit random strings
we now generate a public key by applying to each in our secret key:
- Sign : we sign an -bit message with the signature
e.g. the message M:= 0110 gets the signature
- Verify : we verify a message ‘s signature by using public key and checking
Theorem 3 Let be a one way function computable in time . Then there is a one-time signature scheme that signs messages of length and that is secure.
Suppose this scheme does not provide a -one time signature. This implies that there must be an algorithm with complexity which makes 1 oracle query and
Intuitively, when we are given a string we want to use to break the security of and determines the pre-image of .
We now describe the operation , the algorithm that breaks the security of . begins by generating a public key (which requires evaluations of ). Once generates , it sets a random position in it to the string . Note the distribution of values in this modified will look exactly to the same because is also an evaluation of .
now runs passing it , will query the oracle with a message to sign. With probability this message will not require to invert . If this is the case, then with probability generates a forged message and signature . must differ from the oracle query by at least one bit, that is this forgery finds the inverse of at least one element of not queried. This inverse will be with probability .
runs in time at most if is the running time of and and inverts with probability . Thus if we take to be -secure, then this signature scheme must be secure.
A disadvantage of the scheme (besides the fact of being only a one-time signature scheme) is that the length of the signature and of the keys is much bigger than the length of the message: a message of length results in a signature of length , and the public key itself is of length .
Using a collision resistant hash function, however, we can convert a one-time signature scheme that works for short messages into a one-time signature scheme that works for longer messages. (Without significantly affecting key length, and without affecting the signature length at all.)
We use the hash function to hash the message into a string of the appropriate length and then sign the hash:
- : generates a secret key and a public key as did above. Also picks a random seed which becomes part of the public key.
- :
- :
Theorem 4 Suppose is a secure one-time signature scheme for messages of length , which has public key length and signature length . Suppose also that we have a secure family of collision-resistant hash functions . Suppose, finally, that all have running time at most .
Then there exists a secure one-time signature scheme with public key length , signature length and which can sign messages of length .
We present a sketch of the proof of this theorem.
Suppose we had an algorithm that produced forged signatures with probability after one oracle query. That is, queries the oracle with message and gets back and then produces with probability a message signature pair, , such that and .
One of the two following cases must occur with probability :
- The message has the same hash as , . This means was able to find a collision in . If does this with probability then it contradicts our security assumptions on .
- If , then forged a signature for the original scheme for a fresh message. If can do this with probability then it contradicts our security assumptions on .
Because we reach a contradiction in both cases, must be a secure one-time signature scheme.
In particular, given a one-way function and a family of collision-resistant hash functions we can construct a one-time signature scheme in which the length of a signature plus the length of the public key is less than the length of messages that can be signed by the scheme.
If is such a one-time signature scheme, then the following is a stateful scheme that is existentially unforgeable under a chosen message attack.
Initially, the signing algorithm generates a public key/ secret key pair . When it needs to sign the first message , it creates a new key pair , and generates the signature . The signature of is the pair . When it, later, signs message , the signing algorithm generates a new key pair , and the signature . The signature of is the sequence
and so on. Of course it is rather absurd to have a signature scheme in which the signature of the 100th message contains in its entirety the previously signed 100 messages along with their signatures, but this scheme gives an example of the important paradigm of key refreshing, which will be more productively employed next time.