Notes.8 - Public Key KPS 5, 6, Pfl. 3 Intro to PKC Traditional cryptography is symmetric: both principals hold a common secret (the key) used for both encryption and decryption. There, the primary problem is key distribution. PKC can help solve that problem by providing cryptographically secure channels for key distribution. It can also provide a means for A to sign messages that can be verified by anyone without that party being able to sign a different message pretending to be A. However, PKS has a new problem, that of secure association of the key with the principal. Consideration of this problem leads to some very deep philosophical issues, and solutions lead to such concepts as the "web of trust" and PKI. One further consideration: speed. PKC is usually very slow, because it relies on large integer arithmetic. For this reason, it is usually used to send a symmetric key that is then used for encrypting and decrypting messages. Likewise, to sign a message, rather than signing the whole message, a small message digest is computed using one of the one-way hash functions and that result is then signed. Basics The fundamental idea behind PKC is that two keys are used instead of one. One of the keys may be made public, and so it is not necessary to distribute it over a secure channel. The other key is kept secret, available only to the principal with which the key pair is associated. If e is the public key and d is the private key, then for plaintext p, ciphertext c is c = E(p,e) which is decrypted by p = D(c,d) = D(E(p,e),d) Anyone with e can encrypt a message, but only the keyholder with d can decrypt it. For signing purposes, the reverse operations may be done: s = D(p,d) and to verify, the recipient needs to check that v = E(s,e) = E(D(p,d),e) = p For this, it is necessary that encryption and decryption commute, but they do in most cases. If not, then a different signing key is used and the message is encrypted with it, then verified by decrypting with the public verification key. Modular Arithmetic Groups - CAIN - Closure, Associative, Identity, Inverse G=, S is a set, * is a binary operator for all a, b, c in S, C: a*b is also in S A: a*(b*c) = (a*b)*c I: exists! e in S such that for all a in S, a*e = e*a = a N: for all a in S, exists! a^-1 s.t. a*(a^-1) = (a^-1)*a = e Abelian groups - some groups are also commutative, i.e., for all a, b in S, a*b = b*a Examples: <[0..N-1], +%N> <[1..P-1], *%P> where P is a prime number <{x in [1..N]: (x,N)=1}, *%N>, note (x,N)=GCD(x,N) Euler's Totient Function phi(N) = |{x in [1..N]: (x,N)=1}| is the number of positive integers less than N that are relatively prime to N. Define Phi(N) = {x in [1..N]: (x,N)=1} If N is prime, then phi(N) = N-1 If N=pq, where p and q are prime, then phi(N)=(p-1)(q-1) Modular Exponentiation Fact: If N is square-free (i.e., it does not have p^2 as a factor for any prime p), then for all x in [1..N], x^y % N = x^(y % phi(N)) % N If y = 1 % phi(N), then x^y = x^1 = x mod N RSA Pick large primes p and q, let N=pq Pick e in [1..N-1], (e, phi(N)) = 1 Public Key = Find d, the multiplicative inverse of e mod phi(N). Private Key = To encrypt message m < N, (if larger, then break into chunks), compute c = m^e % N To decrypt, compute m = c^d % N = (m^e%N)^d % N = m^(de%N) % N = m % N = m To sign, compute s = m^d % N To verify a signature, compute v = s^e % N = (m^d % N)^e % N = m^(de%N)%N = m and compare v to m. Security: Factoring large numbers appears to be very hard, and that is the only way we theoretically know of to break RSA. Implementation of RSA Do the exponentiation using the binary expansion of the exponent: x^a = x^(a_n-1*2^(n-1)) * x^(a_n-2*2^(n-2)) * ... * x^(a_1 *2^1 ) * x^(a_0 *2^0 ) where a = a_n-1 a_n-2 ... a_1 a_0 in binary Precompute the powers of x to powers of 2 by repeated squaring x, x^2, x^4, x^8 Perform modular reduction after each multiply Total work is linear in the number of bits of a. Finding large primes: Use Euler's Theorem Attacks on RSA Factoring - good luck if N is large enough and p and q were chosen randomly Limited plaintext attack - if the set of possible messages to be encrypted is small, then an attacker can encrypt all of them and compare them to the message sent.... System approach - Observe the properties of the implementation under various conditions and deduce information from its behavior. Example: Timing attack - using the efficient methods above, a fixed number of multiplications will be done to generate the powers of x, then a number of multiplications that depends on the number of 1's in the key will be performed. By timing the system, an estimate of the number of 1's in the secret key can be made, which narrows the keyspace to be searched. PKCS - Public Key Cryptography Standards RSADSI has produced a number of standards for use of PK crypto so that the subtle ways in which the system may be used in an insecure way are avoided, and so that different organizations can build software that interoperates. See http://www.rsasecurity.com/standards/ PKCS#1 - RSA encryption Format: [0|2| >=8 random bytes |0|data] Explanation: The MSByte of zero is to guarantee that the message is less than the modulus The 2 is a format type (1 is for signatures) The random bytes are non-zero so that zero can be used to delimit the data from the padding, and for confusion (this so-called confounder will prevent the same data from looking the same after encryption). The 0 delimits the pad from the data. The confounder helps eliminate the threat of encrypting a limited number of possible messages and comparing to the encrypted message sent - the attacker would have to guess the padding as well. It also prevents problems from sending the same message to multiple recipients when e=3 as long as the padding is different for each recipient. If e=3, then it prevents the problem of sending a message that is no more than one third the length of the modulus - the second byte is non-zero so this will never happen (the cubic root attack). RSA Signing Format: [0|1| >=8 ff bytes |0|formatted digest] the formatted digest is the digest type and the digest encoded in ASN.1 Explanation: The MSByte of zero is to guarantee that the message is less than the modulus The 1 is the format type for signatures The padding bytes ensure that the number is large and unlikely to be a smooth number The 0 delimits the pad from the digest The digest formatting includes the digest type to prevent attacks that use a weak digest type to produce a different message with the same digest as the digest you used, and then have the recipient believe that you signed the other message with the weaker digest type. Diffie-Hellman Oldest PKC still in use, it provides a means for generating a shared secret, but will not provide authentication by itself. A and B start out with no knowledge at all, then exchange some information publically, after which each will be able to derive a secret that nobody else knows, even though the exchange was public. Once A and B have a secret, they can use this to derive symmetric keys for conventional encryption, signing, etc. A B publically announce prime number p and base g < p pick S_A at random pick S_B at random compute T_A = g^(S_A)%p compute T_B = g^(S_B)%p send T_A to B send T_B to A compute K=T_B^(S_A)%p compute K=T_A^(S_B)%p T_B^(S_A)%p = (g^(S_B)%p)^(S_A)%p = g^(S_B)(S_A)%p = g^(S_A)(S_B)%p = (g^(S_A)%p)^(S_B)%p = T_A^(S_B)%p So A and B now share secret K, which nobody without knowledge of S_A or S_B can derive. To derive S_A or S_B, an attacker must compute the discrete logarithm of a large number, which is believed to be very hard. S_A = discrete log base g of T_A modulo p Bucket-Brigade Attack If C interposes herself between A and B, then C can spoof A and B into believing that she is the other party. To combat this, the p, g, and T may be made public for each principal and distributed reliably. Alternatively, all members of a group may agree upon a common p and g, then each member A is associated with T_A. This is done in SSL. Encryption with D-H If the first scheme above is used, then B may publish for anyone to access. A may then pick S_AB and compute T_AB = = g_B^(S_AB)%p_B as well as K_AB = T_B^S_AB%p_B, then send B the message encrypted with K_AB along with T_AB, which B then uses to generate K_AB and decrypt the message. El-Gamal Signatures Each principal has long-term, public/private key pair (,S), where the public and the private S are as in D-H: T = g^S%p. For a message M, the signer generates a new secret, S' and computes T' = g^(S')%p. A digest d is then computed of M concatenated with T', d = H(M|T'). Then a signature X is computed by X = S' + dS % (p-1). The message M is sent along with X and T'. To verify, the recipient computes d (knowing H, M and T'), then checks that g^X = T'T^d % p, since g^X%p = g^(S'+dS %(p-1))%p = g^S' g^dS %p = = (g^(S')%p)(g^dS%p)%p = T' ((g^S)^d)%p = = T' T^d %p All of these are available, since the recipient knows g, p, T, T', M, X and H, and can compute d and the other quantities from these. DSS - Digital Signature Standard (NIST 1991) Uses DSA - Digital Signature Algorithm It is based on El-Gamal, which uses primes of 512 bits or more, but is modified to used a modulus of q, where q is a prime of 160 bits that divides p-1. Generate p and q as above: find 160-bit prime q, then find a 512-bit prime p of the form kq+1. Generate g, where g^q = 1 mod p, by generating random number h and taking g = h^((p-1)/q) % p, since g^q = (h^((p-1)/q))^q = h^(p-1) = 1 mod p (Fermat) (Note: if this g = 1, try again!) Choose long-term public/private key pair by chosing random S < q and computing T = g^S % p Make p, q, g, and T public. On a per-message basis, choose by choosing a random S' and computing T' = (g ^ S' % p) % q Compute S'^(-1) mod q. Calculate d = H(M) for some hash function H. Compute the signature X = S'^(-1) (d + ST') % q Send M, T' and X. To verify, calculate X^(-1) mod q and d, then x = d X^(-1) mod q y = T' X^(-1) mod q z = (g^x T^y mod p) mod q and check that z = T'. If we define v = (d + ST')^(-1) mod q, then X^(-1) = (S'^(-1)(d+ST'))^(-1) % q = = (d+ST')^(-1) (S'^(-1))^(-1) % q = = (d+ST')^(-1) S' % q = S' (d+ST')^(-1) % q = = S'v % q x = d X^(-1) % q = dS'v % q y = T' X^(-1) % q = T'S'v % q z = (g^x T^y % p) % q = (g^(dS'v%q) T^(T'S'v%q))%p)%q = = (g^(dS'v)g^(ST'S'v) %p )%q = = (g^((d+ST')S'v)%p )%q = = (g^((d+ST')S'(d+ST')^(-1)))%p )%q = = (g^S' %p )%q = T' Note: the mod q in the exponents of g is OK since g^q = 1 mod p Attacks on El-Gamal and DSS The signer must generate a unique secret number for each new message. If the same secret number were used for two messages, then the signer's long-term secret number would be exposed. If that is the case, then anyone may forge the signature. Let messages M and M' be DSS signed using the same secret number S'. Let X and X' be the signatures and d and d' be the hashes of M and M', respectively. Then (X - X')^(-1)(d - d') %q = S' %q. Given a per-message secret S' for message with signature X using T' and havng hash d, compute (XS' - d)T'^(-1) %q = S %q. That is sufficient to generate signatures. Zero-Knowledge Proof Systems A zero-knowledge proof system does only authentication by proving that you know a secret associated with your public key without revealing that secret. RSA does that by allowing you to prove you know the private key without revealing it. A class of these are based on NP-hard problems, such as graph isomorphism. A generates a large graph G, then renames the vertices of G to produce G', preserving the mapping between G and G'. These two graphs (G, G') are A's public information. When B wants to authenticate A, B asks A for a set of graphs {G1, G2, ..., Gk} isomorphic to G (and G'). A generates these and sends them to B, preserving the mapping from G to each Gi. B then may, for each Gi, request the mapping from either G or G' to Gi, but not both. If a third party C tries to impersonate A, then even if the graphs had been used before, there would only be a 50-50 chance that B requests the same mapping for the same graph, so the probability the C gets lucky on all k graphs is (1/2)^k, which may be made arbitrarily small by making k large. As long as A never reveals a mapping for any graph to both G and G', that will remain secret. A more efficient, almost-zero knowledge authentication scheme works as follows. A publishes , where n = pq, where p and q are large primes as in RSA, and v is a number for which only A knows the square root modulo n. A may produce v by simply picking a random number x and squaring it modulo n. When B wants to authenticate A, A chooses k random numbers r1, r2, ..., rk, and for each she sends si = ri^2 % n to B. B partitions the si's into two sets, S and T, then sends these to A. For each si in S, A sends xri % n to B, and for each si in T, A sends ri to B. B then verifies each of the numbers received. For each si in S, he checks that the reply is vsi % n, for each si in T, he checks that the reply is ri (i.e., si = ri^2 % n). If C tries to impersonate A, C may have some si's from previous exchanges for which she knows the response for set S. C may also generate some numbers and square them to get some numbers for which she knows the square root mod n. But when B partitions these two types of numbers into the sets S and T, for each number there is only a 50-50 chance that C will have the correct answer available (C will only know xri for the si from the previous exchanges, but not ri; C will know ri for the numbers she generates, but not xri). With k numbers, the probability that C gets away with it are (1/2)^k, which may be made arbitrarily small. Signing with ZKPSs In the authentication scheme, there is an interactive exchange, where B queries A in an unpredictable manner about the data A has sent B. In a signature scheme, there is no interaction, so the one-way hash takes its place. Since the hash is not predictable from the message, the bits of the hash are taken to represent the queries, and since the data items on which the queries are based are included in the message, it is not possible to rearrange them so as to answer only the questions the signer may want to answer. The number of questions may be higher to reflect the opportunity that the signer has to try many different message/data combinations in order to find one that only asks for the information he has.