CHAPTER 13 – from crypto-practice to crypto-theory In this chapter we deal in more details with several new practical and theoretical issues of contemporary cryptography: Namely, we deal with the following topics: -- RSA – from theory to practice and back -- Stream cryptosystems -- Electronic voting -- Anonymity protocols -- Privacy preservation -- Key agreement on networks -- E-money transactions VARIATIONS on RSA RSA cryptosystem is the most important public-key cryptosystems and therefore It has been analyzed carefully. In the following we discuss the following related problems: :-- Randomized version of RSA that is perfectly secure (what does not hold for standard version of RSA). -- Cases when one can break RSA -- RSA standard -- Special attacks on RSA To start with we repeat basic description of RSA. DESIGN and USE of RSA CRYPTOSYSTEM Invented in 1978 by Rivest, Shamir, Adleman Basic idea: prime multiplication is very easy, integer factorization seems to be unfeasible. Randomized version of RSA-like cryptosystems The scheme works for any trapdoor function (as in case of RSA), for any pseudorandom generator G: {0,1} ^k ® {0,1} ^l, k << l and any hash function h: {0,1}^ ^l ® {0,1} ^k, where n = l + k. Given a random seed s Î {0,1} ^k as input, G generates a pseudorandom bit-sequence of length l. Cases when RSA is easy to break – If an user U wants to broadcast a value x to n other users, using for a communication with a user P[i] a public key (e, N[i]), where e is small, by sending y[i] = x^e mod N[i] • If e = 3 and 2/3 of the bits of the plaintext are known, then one can decrypt efficiently • If two plaintexts differ only in a (known) window of length 1/9 of the full length and e = 3, one can decrypt the two corresponding cryptotext • Wiener showed how to get secret key efficiently if d < 1/3 N^1/4 RSA Standards PKCS (PublicKey Cryptography Standards) is a set of algorithms published by the RSA Data Security Company. One of them is PKCS#1v2.1 a modification of randomized RSA. Let modulus n have k bytes, algorithm will encrypt messages m of length at most k - 11 bytes. – Generate a pseudorandom string PS such that m and PS have total length k - 3 bytes – Create k-byte string 00||02||PS||00||m, where 0i is the byte representing i – Use RSA to encrypt the integer version of the previous string and convert the result into a k byte string Decryption: – Convert the cryptotext into an integer and reject it if it is greater than modulus – Perform the RSA decryption – Check that string has form 00||02||PS||00||m for some PS that has no zero bytes – The resulting m is plaintext Side-channel attacks on cryptosystems Powerful “cryptosystems to attack philosophy” is to attack their physical implementations, i.e. the devices on which the cryptographic protocols are implemented. Since crypto-protocols descriptions say a prior nothing about how protocols should be physically carried out over some physical devices, theoretical security proofs, even though they remain totally valid, do not provide any security guarantee against attacks made via physical side-channels, such as electromagnetic radiation, heat dissipation, noise, observation of computation time, power assumption, ... There are two basic types of attacks: • Passive side-channel attacks, also known as ”information leakage attacks”. Such attacks do not require to actively manipulate the computation, but only to monitor the side-channel leakage during the computation. • Active side-channel attacks, in which we assume that the attacker actively manipulates the execution of cryptographic algorithm (trying for example to introduce faults in the computation). Attacks on RSA implementations In 1995, Paul Kocher, an undergraduate of Stanford, discovered that Eve could recover decryption exponent by counting time (energy consumption) needed for exponentiation during several decryptions. The point is that if d = d[k]d[k][−1] . . . d[1], then, at the computation of c^d, in the i-th iteration a multiplication is performed only if d[i] = 1 (and that requires time and energy). STREAM CRYPTOSYSTEMS A stream cryptosystem encrypts a stream of plaintext on the fly. Stream cryptosystems are of large practical importance. Most of the stream cryptosystems use onetime pad for encryption and differ in the way (pseudo)random keystream is generated. Two basic keystream generation techniques are: • using a pseudorandomgenerator • (in the past using shift-registers and rotors based devices) • using a finite automaton Encryption is done either bitwise or bytewise. Additive ciphers Cryptosystem/machine LORENZ and its decrypting It was addaptive cryptosystem – one-time pad used with pseodorandom sequence generated by machine LORENZ SZ, for communic. between Hitler and generals. During his trial period, on 30.8.1941, Allies obtained two encryptions of the same message with the same (pseudorandom) key and obtained a pseudorandom sequence of 3976 symbols produced by the unknowed machine. British cryptographers/mathematicians were able to find out, out of that sequence, that unknown machine has 12 rotors of 43, 47, 51, 53, 59, 41, 31, 29, 26, 23, 61 and 37 “teeth” and how they rotate. They were able, from 3976 pseudorandom symbols only, to make reverse engineering of the LORENZ macines. They were able to find a method, heavy on computation, how to determine particular settings of rotors for a daily use. RC4 STREAM CRYPTOSYSTEM RC4 was designed by R. Rivest in 1987 and kept as a commercial secret till 1994. Some internet browsers/servers use RC4. RC4 works as a finite automaton with internal states. Its initial state is derived from the secret key only. Its internal state and next byte of the plaintext determine its next internal state and a new byte of the cryptotext, by making XOR of the last bytes of plaintext and key. The internal state consists of a triple (i, j, s), where i and j are bytes and s is a permutation on the set {0, 1, ..., 255} of bytes and it is encoded as an array s[0], s[1], ..., s[255]. Key is represented as an array k[0], k[1], ..., k[l - 1] of bytes. RC4 STREAM CRYPTOSYSTEM (cont.) The initial state is designed as follows: j ¬ 0; for i = 0 to 255 do S[i] ¬ i; for i = 0 to 255 do j ¬ j + s[i] + K[i mod l]; swap(S[i], S[j]) i ¬ 0; j ¬ 0 Plaintexts are iteratively encrypted and the initial state for a new plaintext is equal to the final state of the previous plaintext. Keystream generator: i ¬ i + 1; j ¬ j + S[i]; swap (S[i], S[j]); output S[S[i] + S[j]] A5/1 – GSM encryption A5/1 is used in the GSM mobile telephone networks. The description of A5/1 was secret, but it was reverse engineered and published on Internet. A5/1 is based on a FA A that is based on the following three LFSRs (linear feedback shift registers) with a mutual shift control. Three registers R[1], R[2] and R[3], contain 19 + 22 + 23 = 64 bits. Every time unit some of the registers are shifted that is its content is shifted by one position and one new bit is pushed in. The new bit is the XOR of a few bits of the three LFSRs involved. A5/1 – GSM encryption (cont.) At each step those registers are shifted that have in a special cell, denoted by x, such a bit that is in the majority of bits of all three special cells. Initiation phase (that uses a 64bit secret key register K): 1: set all registers to zero; 2. for i = 0 to 63 do R[1][0] ¬ R[1][0] Å count[i]; R[2][0] ¬ R[2][0] Å count[i]; R[3][0] ¬ R[3][0] Å count[i]; 3. Shift all registers; 4. for i = 0 to 21 do R[1][0] ¬ R[1][0] Å count[i]; R[2][0] ¬ R[2][0] Å count[i]; R[3][0] ¬ R[3][0] Å count[i]; 5. Shift all registers; 6. for i = 0 to 99 do shift the automaton where “count” is a 22bit registers that counts “frames” of the plaintexts, where each frame has 114 bits. All that corresponds to 4 hours of GSM communication. SYMMETRIC CRYPTOSYSTEMS BRUTE FORCE ATTACKS We will discuss several types of brute force attacks that can be applied to any symmetric cryptosystem C[k] considered as an oracle that for each given to-be-key as input replies whether it is a correct key. Exhaustive search This method consists of trying all possible keys until the correct key is found. Such a search can be made more efficient if a probability distribution on keys can be guessed, or if keys are known to satisfy some relations. Dictionary attack Creation of dictionary: For a fixed x and many k values C[k](x) are computed and pairs (C[k](x), k) are inserted into dictionary that is ordered according to the first item of each pair. Search: If we obtain a C[k](x) value (by chosen plaintext attack), dictionary gives us a list of potential keys. A generalization of searching for several keys having several values C[k](x) is easy. Hellman's method This method (suitable for the chosen plaintext attack) speeds up exhaustive search using large pre-computed tables and making a timememory tradeoff. Method assumes that all encryptions of a given plaintext x have the same size, larger than the key length. The methods uses various (random) “reduction functions” R[l], that map cryptotext to strings of the key length, and functions f[l](k) = R[l](C[k](x)) to compute, using the iteration k[s,i,j] = f[s](k[i,j-1]) for a chosen l, m and s = 0, 1, ..., l and i = 0, 1, ... , m and randomly chosen k[s,i,0] values k[s,i,t] to get triplets (s, k[s,i,t], k[s,i,0]). Attack for an input y = C[k](x): for s = 1 to l do i ¬ 0; k ¬ R[s](y); while there is no (s, k, .) entry and i < t do i ¬ i + 1; k ¬ f[s](k); if there is an (s, k, .) entry (s, k, k’) then while C[k’](x) ≠ y and i < t do i ¬ I + 1; k’ ¬ f[s](k’); if C[k’](x) = y then output(k’); otherwise the attack failed. Secure communication in practice Secure communication (session) between two parties usually proceeds by the following protocols: • Protocol for parties (peer) identification. • Exchange of the publickey material. • Authenticated key generation protocol (and the resulting key is divided into several subkeys). • Message security (integrity, authentication, confidentiality) is ensured by means of MAC and encryption protocols. Some additional security requirements: • To ensure proper sequentiality of messages (usually done by means of a synchronized message counter). • Timeliness of message delivery (in time). • Termination fairness: parties should be ensured to terminate the session in the same state. • Anonymity (of parties should not leak out). • Untraceability (of parties in later sessions). SSH Secure SHell protocol SSH is to enable secure remote access to a computer to implement secure (i.e. confidential and authenticated) communication channel in a clientserver session. When a client wishes to connect to a server, the server sends its publickey together with a certificate (if available). Either client is able to authenticate the public key or the client has to trust that the public key is correct. The client then stores the public key in a file that has integrity protection. If the above first connection is OK, then all future connections to the same server should be secure by comparing the received key with the stored key. If keys do not match, the user gets a security warning (that can be ignored). VOTING PROTOCOLS To make electronic voting to work and to be really robust In case of large (country) votings is a VERY NON-TRIVIAL Task. In the following several voting protocols will be discussed. A commitment scheme based on discr. log. Alice commits herself to an m Î {0,…,q - 1}. Scheme setting: Bob randomly chooses primes p and q such that q | (p - 1). Bob chooses random generators of the subgroup G of order q Î Z[n]*. Bob sends p, q, g and v to Alice. Commitment phase: To commit to an m Î {0,…,q - 1}, Alice chooses a random r Î {0,…,q - 1}, and sends c= g ^rv ^m to Bob. Opening phase: Alice sends r and m to Bob who then verifies whether c = g ^rv ^m. COMMITMENTS and ELECTRONIC VOTING Let com(r, m) = g ^rv ^m denote commitment to m in the commitment scheme based on discrete logarithm. If r [1], r [2], m [1], m [2] Î {0,…,q - 1}, then com(r [1], m [1]) × com(r [2], m [2]) = com(r [1] + r [2], m [1] + m [2]). Commitment schemes with such a property are called homomorphic commitment schemes. Homomorphic schemes can be use to cast yes-no votes of n voters V [1],…, V [n], by the trusted authority TA for whom e [T] and d [T] are ElGamal encryption and decryption algorithms. Each voter V [i] chooses his vote m [i] Î {0,1}, a random r [I][ ]Î {0,…, q - 1} and computes his voting commitment c [I][ ]= com(r [i], m [i]). Then V [i] makes c [i] public and sends e [T](g ^r[i]) to TA and TA computes where and makes public g ^r. Now, anybody can compute the result s of voting from publicly known c [i] and g ^r since with s can now be derived from v ^s by computing v ^1, v ^2, v ^3,… and comparing with v ^s if the number of voters is not too large. Voting Protocols – Advanced Settings • In voting protocols we have a set V = {v[1], . . . , v[n]} of voters and a set A = {a[1], . . . , a[m]} of election authorities • Communication is through a communication channel with memory called bulletin board. Each subject can write to his part of the bulletin board any message and that can then be read by anyone. • Electronic voting schemes are clearly ways to go. However, it is not easy to make them to be sufficiently reliable. • A voting protocol specifies to voters and authorities how they should behave: • before voting (initialization phase) • during voting • after voting (counting of the votes phase) Basic Requirements on Voting Protocols • Only legitimate voters can vote and each only once. [• ]There is a security parameter t, such that no group of voters not containing a voter v[i] and at most t - 1 voting authorities, can determine the vote of v[i][.] • Each voter can verify whether his vote was counted • Anyone can verify the final result of elections . • There is a t[0] such that the system can manage incorrect behavior of any group of voters and at most t[0] - 1 voting authorities. • No voters is able to prove how (s)he voted . SECURE ELECTIONS Another set of the desirable properties of voting protocols: 1. Only authorized voters can vote. 2. No one can vote more than once. 3. No one can determine for whom anyone else voted. 4. No one can change anyone else vote without being discovered. 5. All voters can make sure that their votes were counted. Additional requirement: Everyone knows who voted and who didn't. Voting protocol (Nurmi, Salomaa, Santean, 69) • CEB publishes a list of all legitimate voters. • Within a given deadline, everybody intended to vote reports his/her intention to CEB. • CEB publishes a list of voters participating in elections. • Each voter V receives an identification number, i, using a special protocol that very likely assigns different numbers to different users. • Each voter V creates a public encryption function e [V] and secret decryption function d [V]. • *If v is a vote of the voter V, then V generates the following message and sends it to CEB: (i, e [V](i, v)) • The CEB acknowledges the receipt of the vote by publishing e [V][ ](i, v). • Each voter V sends to CEB the pair (i [V], d [V]). • The CEB uses d [V] to decrypt the vote (i, e [V][ ](i, v)). • At the end of the elections CEB publishes the results of the election and, for each different vote, the list of all e [V][ ](i, v) - values that contained that vote. • It is possible that two voters get the same identification number. In such a case, the • CEB generates a new identification number, i [1], chooses one of two votes, and publishes: (i [1], e [V][ ](i, v)). The owner of that vote recognizes that and sends in a second vote, repeating step (*) with the new identification number i [1]. Anonymous money order Digital cash idea has one big problem: how to hide to whom you gave the money. Protocol 1 (1) Alice prepares 100 anonymous money order for 1000$. ANONYMITY problems Very often it is of importance for a party involved in an information transmittion process that its identity remains hidden. There is a variety of problems that require that a communicating party remains hidden or anonymous. For example, anonymous broadcast is a process P that has one anonymous sender and all other parties in communication receive the message m that has been sent by A. Another example of anonymity in communication is so-called anonymous many-to-one communication at which all parties send their messages and there is only on receiver Anonymous transfer protocols • The term anonymous transfer includes a variety of different tasks. • Anonymity of an object is the state of being not identifiable with any particular element of a set of subjects known as an anonymity set. • An anonymity set consists of a set P of participants able to perform a particular action we are interested in. (For example, that a real sender (receiver) is not identifiable within a set of potential senders (receivers)). * Cheating is usually modeled by an adversary A not in P, who has a full control of some subset M of P of (malicious) participants. (A is assumed to have access to memories, inputs and outputs of all participants from M – this way one can model the case malicious participants cooperate.) Chaum’s anonymous brodcast Let a communicating scheme be modeled by an unoriented graph G= (V,E), With V={1,2,…,n}, representing nodes (parties) and E edges (communication links). PROTOL: Each party P[i] performs (all in parallel) [ ]the following actions: • For each j ε {1,2,…,n} it sets k[ij ]= 0; • If (i,j) є E, i < j , randomly chooses a key k[ij ] and sends it securely to P[j ]; • If (i,j) є E, j < i, after receiving k[ij] it sets k[ij] = k[ij] mod n; • It broadcasts O[i]=m[i]+Σ k[ij] mod n, where m[i ]ε {0,1,…,n-1} is the message being sent by P[i] • P[i] computes the global sum S = Σ O[j ]mod n. • Clearly, S=Σ m[j] mod n, and therefore if only one m[j ]/= 0, all participants get that message. • One can show that to preserve anonymity of a correctly behaving sender P[i ], It is sufficient that one another participant P[j] such that (i,j) ε E behaves correctly. PRIVACY PRESERVATION PROBLEM: An important problem is whether and how we can build a statistical database D of important information about a population P so that privacy of individuals of P is preserved. Can we define perfect privacy in the following way that would be analogical to the perfect semantical security of encryptions: Nothing about an individual of P should be learnable from the database that could not be learned without the access to the database. ANSWER: NO SOLUTION: Differential privacy: The risk to one’s privacy, or in general, any type of the risk, should not substantially increase as the result of participation in the statistical database. EXAMPLE The reason why the ideal privacy, namely that the access to a statistical database should not enable one to learn anything about an individual that could not be learned without access, is not achievable, is due to the fact that an auxiliary information can be available from the database to the adversary. For example, let us assume that we have a statistical database of heights of women of different nationalities in Asia and the auxiliary information that Madona is 3 cm higher than an average women in Pakistan That would provide a potentially sensitive information about Madonna, in spite of the fact that she did not participate at the creation of the above mentioned database.. DINNING CRYPTOGRAPHERS • Three cryptographers have dinner at a round table of a 5-star restaurant. • Their waiter tells them that an arrangement has been made that their bill for dinner will be paid anonymously – either by one of them, or by NSA. • Cryptographers respect each other’s right to make anonymous payment, but they would like to know whether payment was done by NSA. • Is there a way for them to learn whether one of them paid the bill without knowing which one (for other two)? PROTOCOL for CRYPTOGRAPHERS PROTOCOL: • Each cryptographer flips a perfect coin between him and the cryptographer on his right, so that only two of them can see the outcome. • Each cryptographer who did not pay the bill states aloud whether the two coins he see – the one he flipped and the one his right-hand neighbor flipped – fell on the same side or on different sides. • The cryptographer who paid the bill states aloud the opposite he sees. CORRECTNESS: • An odd number of differences claimed by cryptographers implies that a cryptographer paid the bill. • An even number implies that NSA paid the bill. • In case a cryptographer paid the bill the other two will have no idea he did. Secure contract signing protocol I Alice and Bob want to sign a contract C. They will use a SKC S and an 1-2 OT (oblivious transfer) as follows. • Alice and Bob, independently and randomly, select each a set of n keys for S {(l[j]^A , r[j]^A)}^n[j=1 ]{(l[j]^B , r[j]^B)}^n[j=1] [ ] • Alice and Bob, independently, generate n signatures of C {S[j]^A=(L[j]^A , R[j]^A)}^n[j=1] {S[j]^B=^ (L[j]^B , R[j]^B)}^n[j=1] where L[j]^X and R[j]^X, for X Î {A,B} are let and right halves of their respective signatures. Each S[j]^X is assumed to be accompanied by a time stamp. (The contract will be considered to be signed if all L[j]^X and R[j]^X can be produced by each of the parties.) Secure contract signing protocol II. • Alice and Bob, independently, encrypt each signature as follows {(l[j]^A(L[j]^A), r[j]^A(R[j]^A))}^n[j=1] {(l[j]^B(L[j]^B), r[j]^B(R[j]^B))}^n[j=1] and they send, to each other, their respective pairs of the encrypted signatures. • Using 1-2 OT, Alice and Bob send to each other exactly one their keys (l[i]^X , r[i]^X) for all i, so neither of them knows which half they got. • Alice and Bob, independently, decrypt what messages they can, ensuring as they do so that they do indeed have a legitimate message in each case. • Alice and Bob alternate in sending bits of their 2n keys, until all verifying bits have been received by both of them. Once this is done each of them can decrypt second half of the corresponding message and contract is signed. Key agreement and authentication over internet • A variety of protocols have been developed to connect hosts on Internet. (Hosts are here those computers that provide services to other computers and users of Internet.) • TCP/IP (Transmission Control Protocol/Internet protocol) is a set of communication protocols used to connect hosts on Internet. • Important protocols are EKE (Encrypted Key Exchanged patented in 1993) and SPEKE (Simple Password Exponential Key Exchange) and their various modifications. • Of large importance is Secure Remote Protocol (SRP-6). In this protocol Alice interacts with Bob to establish a password k, and upon mutual authentication, a session key S is derived that is then used to establish a ”permanent” key, to be used to encrypt all future traffic. SRP-6 Public values: A large prime p is chosen, such that (p − 1)/2 is also prime, a primitive root a modulo p and a hash function h. Protocol: 1. To establish a password k with Bob, Alice picks a salt s and computes d = h(s, k), v = a^d (mod p). Bob stores v and s as Alice’s password and salt. 2. Alice sends to Bob her identification I[a] and A = a^a, where a is a nonce. 3. Bob looks up Alice’s password entry, retrieves v and s from her database and sends both s and B = 3v + a^b, where b is another nonce, to Alice. 4. Alice and Bob compute, independently, u = h(A,B). 5. Alice computes S = (B − 3a^d )^(a+ud). Bob independently computes S = (Av^u)^b. 6. Both, Alice and Bob compute K = h(S). 7. To verify that she has the correct key, Alice sends to Bob h[1] = h(h(p Å h(a)), h(I[a]), s, A, B, K). 8. Bob computes h[1], compares with value received from Alice and if they agree, he sends to Alice h[2] = h(A, h[1],K). 9. Upon receiving h[2] Alice verifies that K is a correct key. E-BUSINESS - revisited A new approach to e-money transactions will be presented in the following. Digital cash transactions II Basic players and procedures: Bank uses RSA with encryption (decryption) exponent e (d) and modulus n. Digital money (m,m^d), where m is unique identification number of a coin, m^d is its bank signature. Bank records all coin identification numbers in a database of used coins together with an identification of the money owner. Blind signatures - blinding To sign a coin m by a bank, customer (Bob) chooses a random r, sends t = r ^em (mod n) to bank. the bank signs it and sends u = t ^d to Bob. By computing ur ^−1 Bob gets m^d. Secret splitting (sharing) To split a binary-string secret s a random r is chosen and s is split to r and s Å r. E-cash withdraw • Bob generates 100 sets of 100 unique strings S[j] = {I[jk]}[k=1]^100, 1 £ j £ 100, such that each I[jk ]uniquely identifies Bob. • Bob splits each I[jk] into two pieces I[jk] = (L[jk], R[jk]). • Bob sends to bank 100 blinded money orders M[j] = (100$, m[j ], r[j]^e m[j ], {L[jk], R[jk]}[k=1]^100), where all m[j] and r[j] are randomly chosen. • Bank chooses randomly one of 100 money orders, say M[100], checks that all remaining ones are for the same amounts, have different m[j] and that each L[jk] Å R[jk] identifies Bob. If all is O.K. Bank signs M[j]. • Bob unblinds signature to get ECash coin (m[100], m[100]^d). E-cash spending 1. Shop verifies bank’s signature by computing (m[100]^d)^e = m[100]. 2. Shop sends Bob a random binary string b[1]b[2 ]. . . b[100] and asks Bob to reveal L[100k] if b[k] = 1 and R[100k] if b[k] = 0 what Bob does, for all k. Afterwards, shop sends the money order to bank together with the chosen binary string b and Bob’s responses. 3. Bank checks its used coins database. If m[100] is not there, bank deposits 100$ into shop’s account and m[100] into its used coins database, together with Bob’s identification, and let shop to know that the money order is O.K. Shop then sends goods to Bob. E-cash spending II 4. If m[100] is in the database of used coins, the money order is rejected. Bank then compares the identity string on false money order with the stored identity string attached to m[100]. If they are the same, bank knows that shop duplicated the money order. If they differ, then bank knows that the entity who gave it to the shop must have copied it. In case the coin (m[100], m[100]^d). was spent with another shop, then that shop gave Bob another binary string (in step 2). Bank compares corresponding binary strings to find an i, where i-th bits differ. This means that one shop asked Bob to reveal R[i] and second L[i]. By computing L[i ]Å[ ]R[i] bank reveals Bob’s identity, which can be reported to authorities.