Chapter 7: Digital signatures Digital signatures – basic goals Digital sigantures should be such that each user should be able to verify signatures of other users, but that should give him/her no information how to sign a message on behind of other users. An important difference from a handwritten signature is that digital signature of a message is always intimately connected with the message, and for different messages is different, whereas the handwritten signature is adjoined to the message and always looks the same. Technically, a digital signature signing is performed by a signing algorithm and a digital signature it is verified by a verification algorithm. A copy of a digital (classical) signature is identical (usually distinguishable) to (from) the origin. A care has therefore to be made that a classical signature is not misused. This chapter contains some of the main techniques for design and verification of digital signatures (as well as some attacks to them). Digital signatures Digital Signature Schemes I Digital signatures are basic tools for authentication and nonreputation of messages. A digital signature scheme allows anyone to verify signature of any sender S without providing any information how to generate signatures of S. A Digital Signature Scheme (M, S, K[s], K[v]) is given by: – M a set of messages to be signed – S a set of possible signatures – K[s] a set of private keys for signing – K[v] a set of public keys for verification Moreover, it is required that: – For each k from K[s,] there exists a single and easy to compute signing mapping sig[k]: {0,1}* x M ® S – For each k from K[v] there exists a single and easy to compute verification mapping ver[k]: M x S ® {true, false} such that the following two conditions are satisfied: Digital Signature Schemes II Correctness: For each message m from M and public key k in K[v], it holds ver[k](m, s) = true if there is an r from {0, 1}* such that s = sig[l](r, m) for a private key l from K[s] corresponding to the public key k . Security: For any w from M and k in K[v] , it is computationally infeasible, without the knowledge of the private key corresponding to k, to find a signature s from S such that ver[k](w, s) = true. Attacks on digital signatures Total break of a signature scheme: The adversary manages to recover the secret key from the public key. Universal forgery: The adversary can derive from the public key an algorithm which allows to forge the signature of any message. Selective forgery: The adversary can derive from the public key a method to forge signatures of selected messages (where selection was made prior the knowledge of the public key). Existential forgery: The adversary is able to create from the public key a valid signature of a message m (but has no control for which m). A digital signature of one bit RSA signatures and their attacks ENCRYPTION versus SIGNATURE DIGITAL SIGNATURE SYSTEMS – simplified version A digital signature system (DSS) consists: • P - the space of possible plaintexts (messages). • S - the space of possible signatures. • K - the space of possible keys. • For each k Î K there is a signing algorithm sig[k] Î S[a] and a corresponding verification algorithm ver[k] Î V such that - sig[k] : P ® S. - ver[k] : P Ä S ® {true, false} and ver[k] (w,s) = true, if s = sig (w); false, otherwise. Algorithms sig[k] and ver[k] should be computable in polynomial time. Verification algorithm can be publically known; signing algorithm (actually only its key) should be kept secret. FROM PKC to DSS - again ElGamal signatures ElGamal signatures - example Security of ElGamal signatures Forging and misusing of ElGamal signatures There are ways how to produce, using ElGamal signature scheme, some valid forged signatures, but they do not allow an opponent to forge signatures on messages of his/her choice. For example, if 0 -L- i, j -L- p -2 and gcd(j, p -1) = 1, then for a = q ^i y ^j mod p; b = -aj ^-1 mod (p -1); w = -aij ^-1 mod (p -1) the pair (a, b) is a valid signature of the message w. This can be easily shown by checking the verification condition. There are several ways ElGamal signatures can be broken if they are used not carefully enough. For example, the random r used in the signature should be kept secret. Otherwise the system can be broken and signatures forged. Indeed, if r is known, then x can be computed by x = (w - rb) a ^-1 mod (p -1) and once x is known Eve can forge signatures at will. Another misuse of the ElGamal signature system is to use the same r to sign two messages. In such a case x can be computed and system can be broken. Digital Signature Standard Digital Signature Standard From ElGamal to DSA Fiat-Shamir signature scheme Sad story Alice and Bob got to jail – and, unfortunately, to different jails. Walter, the warden, allows them to communicate by network, but he will not allow that their messages are encrypted. Problem: Can Alice and Bob set up a subliminal channel, a covert communications channel between them, in full view of Walter, even though the messages themselves that they exchange contain no secret information? Ong-Schnorr-Shamir subliminal channel scheme One-time signatures Undeniable signatures I Undeniable signatures are signatures that have two properties: • A signature can be verified only at the cooperation with the signer – by means of a challenge-and-response protocol. • The signer cannot deny a correct signature. To achieve that, steps are a part of the protocol that force the signer to cooperate – by means of a disavowal protocol – this protocol makes possible to prove the invalidity of a signature and to show that it is a forgery. (If the signer refuses to take part in the disavowal protocol, then the signature is considered to be genuine.) Undeniable signature protocol of Chaum and van Antwerpen (1989), discussed next, is again based on infeasibility of the computation of the discrete logarithm. Undeniable signatures II Fooling and Disallowed protocol Fooling and Disallowed protocol Signing of fingerprints Signatures scheme presented so far allow to sign only "short" messages. For example, DSS is used to sign 160 bit messages (with 320-bit signatures). A naive solution is to break long message into a sequence of shortones and to sign each block separately. Disadvantages: signing is slow and for long signatures integrity is not protected. The solution is to use fast public hash functions h which maps a message of any length to a fixed length hash. The hash is then signed. Example: message w arbitrary length message digest z = h (w) 160bits El Gamal signature y = sig(z) 320bits If Bob wants to send a signed message w he sends (w, sig(h(w)). Collision-free hash functions revisited Timestamping Blind signatures The basic idea is that Sender makes Signer to sign a message m without Signer knowing m, therefore blindly – this is needed in e-commerce. Blind signing can be realized by a two party protocol, between the Sender and the Signer, that has the following properties. • In order to sign (by a Signer) a message m, the Sender computes, using a blinding procedure, from m an m* from which m can not be obtained without knowing a secret, and sends m* to the Signer. • The Signer signs m* to get a signature s[m*] (of m*) and sends s[m*] to the Sender. Signing is done in such a way that the Sender can afterwards compute, using an unblinding procedure, from Signer’s signature s[m*] of m* -- the signer signature s[m] of m. Chum’s blind signatures This blind signature protocol combines RSA with blinding/unblinding features. Bob’s RSA public key is (n,e) and his private key is d. Let m be a message, 0 < m < n, PROTOCOL: • Alice chooses a random 0 < k < n with gcd(n,k)=1. • Alice computes m* = mk^e (mod n) and sends it to Bob (this way Alice blinds the message m). • Bob computed s* = (m*)^d(mod n) and sends s* to Alice (this way Bob signs the blinded message m*). • Alice computes s =k^-1s*(mod n) to obtain Bob’s signature m^d of m (Alice performs unblinding of m*). Verification is equivalent to that of the RSA signature scheme. Fail-then-stop signatures They are signatures schemes that use a trusted authority and provide ways to prove, if it is the case, that a powerful enough adversary is around who could break the signature scheme and therefore its use should be stopped. The scheme is maintained by a trusted authority that chooses a secret key for each signer, keeps them secret, even from the signers themselves, and announces only the related public keys. An important idea is that signing and verification algorithms are enhanced by a so-called proof-of-forgery algorithm. When the signer see a forged signature he is able to compute his secret key and by submitting it to the trusted authority to prove the existence of a forgery and this way to achieve that any further use of the signature scheme is stopped. So called Heyst-Pedersen Scheme is an example of a Fail-Then-Stop siganture Scheme. Digital signatures with encryption and resending A surprising attack to the previous scheme A MAN-IN-THE-MIDDLE attack Probabilistic signature schemes - PSS Authenticated Diffie-Hellman key exchange Security of digital signatures It is very non-trivial to define security of digital signature. Definition A chosen message attack is a process which on an input of a verification key can obtain a signature (corresponding to the given key) to a message of its choice. A chosen message attack is considered to be successful (in so called existential forgery) if it outputs a valid signature for a message for which it has not requested a signature during the attack. A signature scheme is secure (or unforgeable) if every feasible chosen message attack succeeds with at most negligible probability. Treshold Signature Schemes The idea of a (t+1, n) treshold signature scheme is to distribute the power of the signing operation to (t+1) parties out of n. A (t+1) treshold signature scheme should satisfy two conditions. Unforgeability means that even if an adversary corrupts t parties, he still cannot generate a valid signature. Robustness means that corrupted parties cannot prevent uncorrupted parties to generate signatures. Shoup (2000) presented an efficient, non-interactive, robust and unforgeable treshold RSA signature schemes. There is no proof yet whether Shoup’s scheme is provably secure. Digital Signatures - Observation Can we make digital signatures by digitalizing our usual signature and attaching them to the messages (documents) that need to be signed? No, because such signatures could be easily removed and attached to some other documents or messages. Key observation: Digital signatures have to depend not only on the signer, but also on the message that is being signed. SPECIAL TYPES of DIGITAL SIGNATURES • Append-Only Signatures (AOS) have the property that any party given an AOS signature sig[M[1]] on message M[1 ] can compute sig[M[1]II M[2]] for any message M[2]. (Such signatures are of importance in network applications, where users need to delegate their shares of resources to other users). • Identity-Based signatures (IBS) at which the identity of the signer (i.e. her email address) plays the role of her public key. (Such schemes assume the existence of a TA holding a master public-private key pair used to assign secret keys to users based on their identity.) • Hierarchically Identity-Based Signatures are such IBS in which users are arranged in a hierarchy and a user at any level at the hierarchy can delegate secret keys to her descendants based on their identities and her own secret keys. GROUP SIGNATURES • At Group Signatures (GS) a group member can compute a signature that reveals nothing about the signer’s identity, except that he is a member of the group. On the other hand, the group manager can always reveal the identity of the signer. • Hierarchical Group Signatures (HGS) are a generalization of GS that allow multiple group managers to be organized in a tree with the signers as leaves. When verifying a signature, a group manager only learns to which of its subtrees, if any, the signer belongs. Unconditionally secure digital signatures Any of the digital signature schemes introduced so far can be forged by anyone having enough computer power. Caum and Rojakkers (2001) developed, for any fixed set of users, an unconditionally secure signature scheme with the following properties: • Any participant can convince (except with exponentially small probability) any other participant that his signature is valid. • A convinced partipant can convince any other participant of the signature’s validity, without interaction with the original signer.