CHAPTER 9: User identification and message authentication, Secret sharing and E-commerce USER IDENTIFICATION (AUTHENTICATION) User identification (authentication) is a process at which a Prover (one party often referred to as a Prover (Alice)) convinces a Verifier (second party often referred to as a Verifier (Bob)) of Prover’s identity and that the Prover has actually participated in the identication process (I.e. that the Prover is active in the time the confirmative evidence of identity is acquired). The purpose of any identification (authentication) process is to preclude some impersonation (zosobnenie). Identication serves to control access to a resource (often a resource should be accessed only by privileged users). OBJECTIVES of IDENTICATION User identification has to satisfy the following objectives: • The Verifier has to accept Prover’s identity if both parties are honest; • The Verifier cannot later, after successful identication, pose as a Prover and identicate himself (as the Prover) to another Verifier; • A dishonest party that claims to be the other party has only negligible chance to identicate itself successfully; • Each of the above conditions remains true even if an attacker has observed or has participated in several identification protocols. USER IDENTIFICATION PROTOCOLS Identification protocols have to satisfy two security conditions: • If one party, say Bob (a verifier), gets a message from the other party, say Alice (a prover), then Bob is able to verify that the user is indeed Alice. • There is no way to pretend, for a third party, say Charles, when communicating with Bob, that he is Alice without Bob having a large chance to find out that. Identification system based on a PKC • Alice chooses a random r and sends e [B] (r) to Bob. • Alice identifies a communicating person as Bob if he can send her back r. • Bob identifies a communicating person as Alice if she can send him r. A misuse of the above system We show that (non-honest) Alice could misuse the above identification system. Indeed, Alice could intercept a communication of a Jane ( a new “player'') with Bob, and get a cryptotext e [B] (w) Jana has been sending to Bob, and then Alice could send e [B] (w) to Bob. Honest Bob, who follows fully the protocol, would then return w to Alice and she would get this way the plaintext w. ELEMENTARY AUTHENTICATION PROTOCOLS Three-way authentication and key agreement A PKC will be used with encryption/decryption algorithms (e, d) and DSS with pairs (s, v). Alice and Bob will have their identity strings I[A] and I[B]. 1. Alice chooses a random r[A], sets t = (I[B], r[A]), signs sig[sA](t) and sends m[1] = (t, sig[sA](t)) to Bob. 2. Bob verifies Alice’s signature, chooses random r[B] and a random session key k. He encrypts k with Alice’s public key, E[eA](k) = c, sets t[1] = (I[A], r[A], r[B], c), signs it with sig[sB](t[1]). Then he sends m[2] = (t[1], sig[sB](t[1])) to Alice. Three-way authentication and key agreement 3. Alice verifies Bob’s signature, and checks that the r[A] she just got matches the one she generated in Step 1. Once verified, she is convinced that she is communicating with Bob. She gets k via D[dA](c) = D[dA](E[eA](k)) = k, sets t[2]= (I[B], r[B]) and signs it with sig[sA](t[2]). Then she sends m[3] = (t[2], sig[sA](t[2])) to Bob. 4. Bob verifies Alice’s signature and checks that rB he just got matches his choice in Step 2. If both verifications pass, Alice and Bob have mutually authenticated each other identity and have agreed upon a session key k. DATA AUTHENTICATION The goal of data authentication schemes (protocols) is to handle the case that data are sent through insecure channels. By creating so-called Message Authentication Code (MAC) a sending this MAC, together with a message through an insecure channel, one can create possibility to verify whether data were not changed in the channel. The price to pay is that communicating parties need to share a secret random key that need to be transmitted through a very secure channel.l Schemes for Data Authentication Basic difference between MACs and digital signatures is that MACs are symmetric. Anyone who is able to verify MAC of a message is also able to generate the same MAC, and vice versa. A scheme (M, T, K) for data authentication is given by: – M is a set of possible messages (data) – T is a set of possible MACs – K is a set of possible keys Moreover, it is required that – to each k from K there is a single and easy to compute authentication mapping auth[k]: {0,1}* x M ® T – and a single easy to compute verification mapping ver[k]: M x T ® {true, false} Two conditions should be satisfied for such a scheme: Correctness: For each m from M and k from K it holds ver[k](m, c) = true, if there exists an r from {0, 1}* such that c = aut[k](r, m) Security: For any m from M and k from K it is computationally unfeasible, without a knowledge of k, to find c from T such that ver[k](m, c) = true FROM BLOCK CIPHERS to MAC – CBC-MAC Let C be an encryption algorithm that maps kbit strings into kbit strings. If a message m = m[1]m[2]...m[l] is divided into blocks of length k, then socalled CBCmode of encryption assumes a choice (random) of a special block y[0] of length k, and performs the following computations for i = 1, . . . ,l y[i] = C(y[i-1] AA m[i]) and then y[1]||y[2] || . . . ||y[l ] is the encryption of m and y[l] is MAC for m. A modification of this method is to use another cryptoalgoritm to encrypt the last block m[l]. WEAKNESS of CBS-MAC METHOD Let us have three pairs: a message and its MAC (m[1], c[1]), (m[2], c[2]), (m[3], c[3]) Where m[1] and m[3 ] have the same length and m[2] = m[1]||B||m’[2]. and let the length of B be also k. The encryption of the block B within m[2] is C(B AA c[1]). If we now define B’ = B AA c[1] AA c[3] , m[4] = m[3]||B’||m’[2] , then, during the encryption of m[4], we get C(B’ AA c[3]) = C(B AA c[1]), This implies that MAC's for m[4] and m[2] are the same. One can therefore forge a new valid pair (m[4], c[2]). ANALYSIS of CBCMAC – a view Theorem Given two independent random permutations C[1] and C[2] on the set of message blocks M of cardinality n, let us define MAC(m[1], m[2], . . . , m[l]) = C[2](C[1](...C[1](C[1](m[1]) AA m[2]) AA... AA m[l-1 ] AA m[l]). We assume that the MAC function is implemented by an oracle, and consider an adversary who can send queries to the oracle with a limited total length of q: if m[1], ..., m[d] denote the finite block sequences on M which are sent by the adversary to the oracle, we assume that the total number of blocks is less than q. The purpose of the adversary is to output a message m which is different from all m[i] together with its MAC value c. The probability of success of any adversary (i.e. the probability that the MAC value is correct) is smaller than When q = qn^1/2, this is approximately a = q^2/2 (which is greater than 1 – e^-a ) Implication: if the total length of all authenticated messages is negligible against # n, there is no better way than the brute force attack to get collisions on the CBCMAC. FROM HASH FUNCTIONS TO MAC So called HMAC was published as the internet standard RFC2104. Let a hash function h processes messages by blocks of b bytes and produces a digest of l bytes and let t be the size of MAC, in bytes. HMAC of a message m with a key k is computed as follows: • If k has more than b bytes replace k with h(k). • Append zero bytes to k to have exactly b bytes. • Compute h(k AA opad||h(k AA ipad||m)). and truncate the results to its t leftmost bytes to get HMAX[k](m). In HMAX ipad (opad) consists of b bytes equal to 0x36 (0x5c) hexadecimal. SECURITY of HMAC It can be shown that if • h(k AA ipad||m) defines a secure MAC on fixed length messages, and • h is collision free, then HMAC is a secure MAC on variable length messages with two independent keys. More precisely: Theorem Let h be a hash function which hashes into l bits. Given k[1], k[2] from {0, 1}^l consider the following MAC algorithm MAC[k1,k2](m) = h(k[2]||h(k[1]||m)) If h is collision free and m ® h(k[2]||m) is a secure MAC algorithm for messages m of the fixed length l, then the MAC is a secure MAC algorithm for messages of arbitrary length. Disadvantage of static user identification schemes Everybody who knows your password or PIN can impersonate you. Using so called zero-knowledge identification schemes, discussed in next chapter, you can identify yourself without giving to the identificator the ability to impersonate you. Simplified Fiat-Shamir identification scheme Analysis of Fiat-Shamir identification I Analysis of Fiat-Shamir identification II HOW CAN A BAD EVE CHEAT? Eve can send, to fool Bob, as her commitment, either for a random r or In the first case Eve can respond correctly to the Bob’s challenge b=0, by sending r; but cannot respond correctly to the challenge b = 1. In the second case Eve can respond correctly to Bob’s challenge b = 1, by sending r again; but cannot respond correctly to the challenge b = 0. Eve has therefore a 50% chance to cheat. Fiat-Shamir identification scheme parallel version In the following parallel version of Fiat-Shamir idenitification scheme the probability of false identification is decreased. Choose primes p,q, compute n = pq. Choose quadratic residues v [1],…,v [k] Î QR [n]. Compute s [1],…,s [k] such that public-key: v [1],…,v [k] secret-key: s [1],…,s [k] of Alice (1) Alice chooses a random r < n, computes a = r ^2 mod n and sends a to Bob. (2) Bob sends Alice a random k-bit string b [1]… b [k]. (3) Alice sends to Bob (4) Bob accepts if and only if Alice and Bob repeat this protocol t times, until Bob is convinced that Alice knows s[1],…,s[k] . The chance that Alice fools Bob is 2 ^-kt, a decrease comparing with the chance 1/2 of the previous version of the identification scheme. The Schnorr identification scheme - setting Schnorr identification scheme Okamoto identification scheme Okamoto identification scheme – basics once more Basic setting TA chooses: a large prime p -L- 2 ^512,large prime q ^3 2 ^140 dividing p -1; two elements a [1], a [2] Î Z [p]* of order q. TA keep secret (also from Alice and Bob) c = lg[a1] a [2]. Issuing a certificate to Alice • TA establishes Alice's identity and issues an identification string ID(Alice). • Alice randomly chooses 0 -L- a [1], a [2] -L- q -1 and sends to TA. v = a[1] ^-a1a [2] ^-a2 mod p. • TA generates a signature s = sig [TA](ID(Alice), v) and sends to Alice the certificate C (Alice) = (ID(Alice), v, s). Okamoto identification scheme Authentication codes Attacks and deception probabilities There are two basic types of attacks Mallot, the man in the middle,can do. Impersonation. Mallot introduces a message (w, t) into the channel expecting that message will be received as being sent by Alice. Substitution. Mallot replaces a message (w, t) in the channel by a new one, (w', t'), expecting that message will be accepted as being sent by Alice. With any impersonation (substitution) attack a probability P [i] (P [s]) is associated that Mallot will deceive Bob, if Mallot follows an optimal strategy. In order to determine such probabilities we need to know probability distributions p [m] on messages and p [k] on keys. The |K| ´ |M| authentication matrix tabulates all authenticated tags. The item in a row corresponding to a key k and in a column corresponding to a message w contains the authentication tag t [k] (w). The goal of authentication codes is to decrease probabilities that Mallot performs successfully impersonation or substitution. Example Computation of deception probabilities I Computation of deception probabilities II Since Mallot wants to maximize his chance of deceiving Bob, he needs to compute p [w,t] = max {payoff(w', t', w, t) | w‘Î M, w ^1 w', t' Î A}. p [w,t] therefore denotes the probability that Mallot can deceive Bob with a substitution in the case (w, t) is the message observed. If Pr[Ma](w, t) is the probability of observing a message (w, t) in the channel, then and The next problem is to show how to construct an authentication code such that the deception probabilities are as low as possible. The concept of orthogonal arrays, introduced next, serves well such a purpose. Orthogonal arrays Construction and bounds for OAs In an orthogonal array OA(n, k, l) • n determines the number of authenticators (security of the code); • k is the number of messages the code can accommodate; • l relates to the number of keys - ln ^2. The following holds for orthogonal arrays. • If p is prime, then OA(p, p, 1) exits. • Suppose there exists an OA(n, k, l). Then • Suppose that p is a prime and d -L- 2 an integer. Then there is an orthogonal array OA(p, (p ^d -1)/(p -1), p ^d-2). • Let us have an authentication code with |A| = n and P [i] = P [s] = 1/n.Then |K| ^3 n ^2. Moreover, |K| = n ^2 if and only if there is an orthogonal array OA(n, k,1), where |M| = k and P [K] (k) = 1/n ^2 for every key k Î K. The last claim shows that there are no much better approaches to authentication codes with deception probabilities as small as possible than orthogonal arrays. Secret sharing between two A moderator distributes a binary-string secret s, between two parties P[1] and P[2] by choosing a random binary string b, of the same length as s, and • sending b to P[1] and • sending s AA b to P[2]. This way, none of the parties P[1] and P[2] alone has a slightest idea about s, but both together easily recover s by computing b AA (s AA b) = s. Threshold secret sharing scheme Shamir's (n,t)-threshold scheme Shamir's scheme - technicalities Shamir's (n,t)-threshold scheme - summary To distributes n shares of a secret S among users P [1],…, P [n] a trusted authority TA proceeds as follows: • TA chooses a prime p > max{S, n} and sets a [0] = S. • TA selects randomly a [1],…, a [t-1] Î Z [p] and creates polynomial • TA computes s [i] = f (i), i = 1,…, n and transfers (i, s [i]) to the user P [i] in a secure way. Any group J of t or more users can compute the secret. Indeed, from the previous corollary we have In case |J| < t, then each a € Z [p] is likely to be the secret. SECRET SHARING – GENERAL CASE A serious limitation of the threshold secret sharing schemes is that all groups of users with the same number of users have the same access to secret. Practical situations usually require that some (sets of) users are more important than others. Let P be a set of users. To deal with above situation such concepts as authorized set of user and access structure are used. An authorized set of users is a set of users who can together construct the secret. An unauthorized set of users is a set of users who alone cannot learn anything about the secret. Let P be a set of users. The access structure is a set such that for all authorized sets A and for all unauthorized sets U. Theorem: For any access structure there exists a secret sharing scheme realizing this access structure. Secret Sharing Schemes with Verification • Secret sharing protocols increase security of a secret information by sharing it between several subjects. • Some secret sharing scheme are such that they work even in case some participants behave incorrectly. • A secret sharing scheme with verification is such a secret sharing scheme that: [– ] Each P[i] is capable to verify correctness of s[i ]– No participant P[i] is able to provide incorrect information and to convince others about its correctness Feldman’s (k,n)-Protocol This protocol is an example of the secret sharing scheme with verification. The protocol is a generalization of Shamir's protocol. It is assumed that all participants can broadcast messages to all others and each of them can determine all senders.. Given are large primes p, q, q|(p - 1), q > n and h < p a generator of Z*[p] . All these numbers, and also the number g = h^(p-1)/q mod p, are public. As in Shamir's scheme, the dealer assigns to each P[i] a specific x[i] from {1, . . . , q – 1} generates a random polynomial f(x) = (1) such that f(0) = s and sends to each P[i] value y[i] = f(x[i]). Moreover, using broadcasting the dealer sends to all P[i] all values v[j] = g^aj mod p. Feldman’s (k,n)-Protocol (cont.) Each P[i] verifies that If (1) does not hold, P[i] asks, using broadcasting, the dealer to broadcast correct value of y[i]. If there are at least k such requests, or some of the new values of y[i] does not satisfies (1), the dealer is considered as not reliable. One can easily verify that if the dealer works correctly, then all relations (1) hold E-COMMERCE DUAL SIGNATURE PROTOCOL We present a protocol to solve the following security and privacy problem in e-commerce: shoppers banks should not know what cardholders are ordering and shops should not learn credit cards numbers. Participants of the protocol: a bank, a cardholder, a shop The cardholder uses the following information: • GSO - Goods and Service Order (cardholder's name, shop's name, items being ordered, their quantity,...) • PI - Payment instructions (shop's name, card number, total price,...) Protocol uses a public hash function h. RSA cryptosystem is used and • e [C], e [S] and e [B] are public keys of cardholder, shop, bank and • d [C], d [S] and d [B] are their secret keys. CARDHOLDER and SHOP ACTIONS BANK and SHOP ACTIONS Bank has received HEPI, HEGSO, e [B](PI), and DS and performs the following actions. • Computes h (e [B](PI)) - what should be equal to HEPI. • Computes h (h (e [B](PI)) || HEGSO) what should be equal to e [C](DS) = HPO. • Computes d [B](e [B](PI)) to obtain PI; • Returns an encrypted (with e [S]) digitally signed authorization to shop, guaranteeing the payment. Shop completes the procedure by encrypting, with e [C,] the receipt to the cardholder, indicating that transaction has been completed. It is easy to verify that the above protocol fulfils basic requirements concerning security, privacy and integrity. DIGITAL MONEY Is it possible to have electronic (digital) money? It seems that not, because copies of the digital information are indistinguishable from origin and one could hardly prevent double spending,.... T. Okamoto and K. Ohia formulated six properties any digital money system should have. • One should be able to send e-money through e-networks. • It should not be possible to copy and reuse e-money. • Transactions using e-money should be done off-line - that is no communication with central bank should be needed during translation. • One should be able to sent e-money to anybody. • An e-coin could be divided into e-coins of smaller values. Several system of e-money have been created that satisfy all or at least some of the above requirements. BLIND SIGNATURES - applications BLIND SIGNATURES - protocols