‹#› 1 Digital signatures Chapter 7: Digital signatures Chapter 7: Digital signatures IV054 Example: Assume that each user A uses a public-key cryptosystem (eA,dA). Signing a message w by a user A, so that any user can verify the signature; dA(w) Signing a message w by a user A so that only user B can verify the signature; eB(dA(w)) Sending a message w, and a signed message digest of w, obtained through a hash function h: (w, dA(h(w))) Example Assume Alice succeeds to factor the integer that Bob used, as modulus, to sign his will, using RSA, 20 years ago. Even the key has already expired, Alice could rewrite Bob's will, leaving fortune to her, and date it 20 years ago. Moral: It may pay of to factor a single integers using many years of many computers power. > ‹#› Digital signatures 2 Digital signatures – basic goals Digital signatures – basic goals IV054 ‹#› 3 Digital signatures Digital signatures Digital signatures IV054 Indeed, if an active enemy, called tamperer, intercepts the message, then he can compute dT(eA(c)) = dT(eB(w)) and can send the outcome to Bob, pretending that it is from him/tamperer (without being able to decrypt/know the message). Any public-key cryptosystem in which the plaintext and cryptotext spaces are the same can be used for digital signature. > ‹#› 4 Digital signatures Digital Signature Schemes I Digital Signature Schemes I IV054 ‹#› 5 Digital signatures Digital Signature Schemes II Digital Signature Schemes II IV054 ‹#› 6 Digital signatures Attacks on digital signatures Attacks on digital signatures ‹#› 7 Digital signatures A digital signature of one bit A digital signature of one bit IV054 Signature of a bit b: (b, kb). Verification of such a signature sb = f (kb) SECURITY? > ‹#› 8 Digital signatures RSA signatures and their attacks RSA signatures and their attacks IV054 > > > > > > > Attacks • It might happen that Bob accepts a signature not produced by Alice. Indeed, let Eve, using Alice's public key, compute we and say that (we, w) is a message signed by Alice. Everybody verifying Alice's signature gets we = we. • Some new signatures can be produced without knowing the secret key. Indeed, is and are signatures for w1 and w2, then and are signatures for w1w2 and w1-1. ‹#› 9 Digital signatures ENCRYPTION versus SIGNATURE ENCRYPTION versus SIGNATURE IV054 PUBLIC-KEY SIGNATURES Signing: dU (w) Verification of the signature: eU (dU (w)) > ‹#› 10 Digital signatures DIGITAL SIGNATURE SYSTEMS – simplified version DIGITAL SIGNATURE SYSTEMS – simplified version IV054 > ‹#› 11 Digital signatures FROM PKC to DSS - again FROM PKC to DSS - again IV054 Signing of a message w by a user A so that only user B can verify the signature; eB (dA (w)). Sending of a message w and a signed message digest of w obtained by using a (standard) hash function h: (w, dA (h (w))). If only signature (but not the encryption of the message) are of importance, then it suffices that Alice sends to Bob (w, dA (w)). > ‹#› 12 Digital signatures ElGamal signatures ElGamal signatures IV054 Signature of a message w: Let r  Z p-1* be randomly chosen and kept secret. sig(w, r) = (a, b), where a = q r mod p and b = (w - xa)r -1 (mod (p –1)). Verification: accept a signature (a,b) of w as valid if yaab  qw (mod p) (Indeed: yaab  qaxqrb  qax + w – ax + k(p -1)  qw (mod p)) > ‹#› 13 Digital signatures ElGamal signatures - example ElGamal signatures - example IV054 > ‹#› 14 Digital signatures Security of ElGamal signatures Security of ElGamal signatures IV054 1. If Eve chooses a and b and tries to determine such w that (a,b) is signature of w, then she has to compute discrete logarithm lg q y a a b. Hence, Eve can not sign a “random” message this way. > ‹#› 15 Digital signatures Forging and misusing of ElGamal signatures Forging and misusing of ElGamal signatures IV054 ‹#› 16 Digital signatures Digital Signature Standard Digital Signature Standard IV054 > Design of DSA 1. The following global public key components are chosen: • p - a random l-bit prime, 512 Ł l Ł 1024, l = 64k. • q - a random 160-bit prime dividing p -1. • r = h (p –1)/q mod p, where h is a random primitive element of Zp, such that r>1 (observe that r is a q-th root of 1 mod p). 2. The following user's private key components are chosen: • x - a random integer (once), 0 < x < q, and y = r x mod p is made public. 3. Key is K = (p, q, r, x, y) ‹#› 17 Digital signatures Digital Signature Standard Digital Signature Standard IV054 Verification of signature (a, b) •compute z = b -1 mod q •compute u1 = wz mod q, u2 = az mod q verification: ver K(w, a, b) = true <=> (r u1y u2 mod p) mod q = a > ‹#› 18 Digital signatures From ElGamal to DSA From ElGamal to DSA IV054 Any proposal for digital signature standard has to go through a very careful scrutiny. Why? Encryption of a message is usually done only once and therefore it usually suffices to use a cryptosystem that is secure at the time of the encryption. On the other hand, a signed message could be a contract or a will and it can happen that it will be needed to verify a signature many years after the message is signed. Since ElGamal signature is no more secure than discrete logarithm, it is necessary to use large p, with at least 512 bits. However, with ElGamal this would lead to signatures with at least 1024 bits what is too much for such applications as smart cards. In DSA a 160 bit message is signed using 320-bit signature, but computation is done modulo with 512-1024 bits. Observe that y and a are also q-roots of 1. Hence any exponents of r,y and a can be reduced module q without affecting the verification condition. This allowed to change ElGamal verification condition: y a a b = q w. > ‹#› 19 Digital signatures Fiat-Shamir signature scheme Fiat-Shamir signature scheme IV054 > > > (2) Alice uses a publically known hash function h to compute H=h(wx1x2… xt) and then uses first kt bits of H, denoted as bij, 1 Ł i Ł t, 1 Ł j Ł k as follows. (3) Alice computes y 1,…,y t (4) Alice sends to Bob w, all bij all y i and also h { Bob already knows Alice's public key v 1,…,v k } (5) Bob computes z 1,…,z k and verifies that the first k  t bits of h(wx1x2… xt) are the bij values that Alice has sent to him. Security of this signature scheme is 2 -kt. Advantage over the RSA-based signature scheme: only about 5% of modular multiplications are needed. ‹#› 20 Digital signatures Sad story Sad story ‹#› 21 Digital signatures Yes. Alice and Bob create first the following communication scheme: They choose a large n and an integer k such that gcd(n, k) = 1. They calculate h = k -2 mod n = (k -1) 2 mod n. Public key: h, n Trapdoor information: k Let secret message Alice wants to send be w (it has to be such that gcd(w, n) =1) Denote a harmless message she uses by w ' (it has to be such that gcd(w ',n) = 1) Signing by Alice: Signature: (S 1, S 2). Alice then sends to Bob (w ', S 1, S 2) Signature verification by Walter: w ' = S 12 – hS 22 (mod n) Decryption by Bob: Ong-Schnorr-Shamir subliminal channel scheme Ong-Schnorr-Shamir subliminal channel scheme IV054 > > ‹#› 22 Digital signatures One-time signatures One-time signatures IV054 Signing of a message x = x 1… x k  {0,1} k sig(x 1… x k) = (y 1,x1,…, y k,xk) = (a 1,…, a k) - notation and ver K(x 1… x k, a 1,…, a k) = true <=> f(a i) = z i,xi, 1 Łi Ł k Eve cannot forge a signature because she is unable to invert one-way functions. Important note: Lampert signature scheme can be used to sign only one message. > ‹#› 23 Digital signatures Undeniable signatures I Undeniable signatures I ‹#› 24 Digital signatures Undeniable signatures II Undeniable signatures II IV054 Chaum-van Antwerpen undeniable signature schemes (CAUSS) • p, r are primes p = 2r + 1 • q  Zp* is of order r; • 1 Ł x Ł r -1, y = q x mod p; • G is a multiplicative subgroup of Zp* of order q (G consists of quadratic residues modulo p). Key space: K = {p, q, x, y }; p, q, y are public, x € G is secret. Signature: s = sig K (w) = w x mod p. > ‹#› 25 Digital signatures Disallowed protocol Basic idea: After receiving a signature s Alice initiates two independent and unsuccessful runs of the verification protocol. Finally, she performs a “consistency check'' to determine whether Bob has formed his responses according to the protocol. • Alice chooses e1, e2  Zr*. • Alice computes c = se1ye2 mod p and sends it to Bob. • Bob computes d = cx^(-1) mod r mod p and sends it to Alice. • Alice verifies that d  w e1q e2 (mod p). • Alice chooses f1, f2  Zr*. • Alice computes C = s f1y f2 mod p and sends it to Bob. • Bob computes D = Cx^(-1) mod r mod p and sends it to Alice. Fooling and Disallowed protocol Fooling and Disallowed protocol IV054 > ‹#› 26 Digital signatures CONCLUSIONS It can be shown: Bob can convince Alice that an invalid signature is a forgery. In order to that it is sufficient to show that if s  w x, then (dq -e2) f1  (Dq -f2) e1 (mod p) what can be done using congruency relation from the design of the signature system and from the disallowed protocol. Bob cannot make Alice believe that a valid signature is a forgery, except with a very small probability. • Alice verifies that D  w f1q f2 (mod p). • Alice concludes that s is a forgery iff (dq -e2) f1  (Dq -f2) e1 (mod p). Fooling and Disallowed protocol IV054 > ‹#› 27 Digital signatures Signing of fingerprints Signing of fingerprints IV054 ‹#› 28 Digital signatures Collision-free hash functions revisited Collision-free hash functions revisited IV054 Definition A hash function h is strongly collision-free if it is computationally infeasible to find messages w and w ' such that h(w) = h(w '). Example 2: Eve computes a signature y on a random fingerprint z and then find an x such that z = h(x). Would she succeed (x,y) would be a valid signature. In order to prevent the above attack, it is required that in signatures we use one-way hash functions. It is not difficult to show that for hash-functions (strong) collision-free property implies the one-way property. > ‹#› 29 Digital signatures Timestamping Timestamping IV054 A method for timestamping of signatures: In the following pub denotes some publically known information that could not be predicted before the day of the signature (for example, stock-market data). Timestamping by Bob of a signature on a message w, using a hash function h. • Bob computes z = h(w); • Bob computes z ‘ = h(z || pub); • Bob computes y = sig(z '); • Bob publishes (z, pub, y) in the next days's newspaper. It is now clear that signature was not be done after triple (z, pub, y) was published, but also not before the date pub was known. > ‹#› 30 Digital signatures Blind signatures Blind signatures ‹#› 31 Digital signatures Chum’s blind signatures Chum’s blind signatures ‹#› 32 Digital signatures Fail-then-stop signatures Fail-then-stop signatures ‹#› 33 Digital signatures Digital signatures with encryption and resending Digital signatures with encryption and resending IV054 2. Alice encrypts the signed message: eB(sA(w)) and sends it to Bob. 3. Bob decrypt the signed message: dB(eB(sA(w))) = sA(w). 4. Bob verifies signature and recovers the message vA(sA(w)) = w. Resending the message as a receipt 5. Bob signs and encrypts the message and sends to Alice eA(sB(w)). 6. Alice decrypts the message and verifies the signature. Assume now: vx = ex, sx = dx for all users x. > ‹#› 34 Digital signatures A surprising attack to the previous scheme A surprising attack to the previous scheme IV054 2. Later Mallot sends eB(sA(w)) to Bob pretending it is from him (from Mallot). 3. Bob decrypts and “verifies” the message by computing eM(dB(eB(dA(w)))) = eM(dA(w)) - a garbage. 4. Bob goes on with the protocol and returns Mallot the receipt: eM(dB(eM(dA(w)))) 5. Mallot can then get w. Indeed, Mallot can compute eA(dM(eB(dM(eM(dB(eM(dA(w)))))))) = w. > ‹#› 35 Digital signatures A MAN-IN-THE-MIDDLE attack A MAN-IN-THE-MIDDLE attack IV054 What can an active eavesdropper C do? •C can learn (eA(eA(w) B), A) and therefore eA(w'), w ‘ = eA(w)B. •C can now send to Alice the pair (eA(eA(w ') C), A). •Alice, thinking that this is the step 1 of the protocol, acknowledges by sending the pair (eC(eC(w ') A), C) to C. •C is now able to learn w ' and therefore also eA(w). •C now sends to Alice the pair (eA(eA(w) C), A). •Alice acknowledges by sending the pair (eC(eC(w) A), C). •C is now able to learn w. > ‹#› 36 Digital signatures Probabilistic signature schemes - PSS Probabilistic signature schemes - PSS IV054 > > Signing: of a message w  {0,1}*. 1. Choose random r  {0,1} k and compute m = h (w || r). 2. Compute G(m) = (G1(m), G2(m)) and y = m || (G1(m)  r) || G2(m). 3. Signature of w is  = f -1(y). Verification of a signed message (w, ). • Compute f() and decompose f() = m || t || u, where |m| = l, |t| = k and |u| = n - (k+l). • Compute r = t  G1(m). • Accept signature  if h(w || r) = m and G2(m) = u; otherwise reject it. ‹#› 37 Digital signatures Authenticated Diffie-Hellman key exchange Authenticated Diffie-Hellman key exchange IV054 1. Alice chooses a random x and Bob chooses a random y. 2. Alice computes q x mod p, and Bob computes q y mod p. 3. Alice sends q x to Bob. 4. Bob computes K = q xy mod p. 5. Bob sends q y and eK (sB (q y, q x)) to Alice. 6. Alice computes K = q xy mod p. 7. Alice decrypts eK (sB (q y, q x)) to obtain sB (q y, q x). 8. Alice verifies, using an authority, that vB is Bob's verification algorithm. 9. Alice uses vB to verify Bob's signature. 10. Alice sends eK (sA (q x, q y)) to Bob. 11. Bob decrypts, verifies vA, and verifies Alice's signature. An enhanced version of the above protocol is known as Station-to-Station protocol. > ‹#› 38 Digital signatures Security of digital signatures Security of digital signatures IV054 ‹#› 39 Digital signatures Treshold Signature Schemes IV054 Treshold Signature Schemes ‹#› 40 Digital signatures Digital Signatures - Observation Digital Signatures - Observation IV054 ‹#› 41 Digital signatures SPECIAL TYPES of DIGITAL SIGNATURES IV054 SPECIAL TYPES of DIGITAL SIGNATURES ‹#› 42 Digital signatures GROUP SIGNATURES IV054 GROUP SIGNATURES ‹#› 43 Digital signatures Unconditionally secure digital signatures IV054 Unconditionally secure digital signatures