CS 4803 Computer and Network SecurityAlexandra (Sasha) BoldyrevaPKI, secret key sharing,implementation pitfalls .1pkCACAUserI want pkUUser IDU, pkUVerifies the ID,picks a random challenge R (e.g. a message to sign)R!=Sign(skU, R)Verifies that VF(pkU, R, !)=1cert=Sign(skCA, (IDU, pkU,exp.date,...))Verifies that VF(pkCA, (IDU, pkU,exp.date,...),cert)=12•The PKI also•makes the certified public keys, the corresponding identities and the certificates public•maintains the public certificate revocation list (CRL)•The PKI may be hierarchical with CAs certifying other CAs.•X.509 is the standard for digital certificates developed by the International Telecommunications Union (ITU).3References• • Internet X.509 Public Key Infrastructure - Certificate Management Protocol (CMP). Internet draft. Available from http://www.ietf.org/internet-drafts/draft-ietf-pkix-rfc2510bis-09.txt• C. Ellison and B. Schnier, “Ten risks of PKI.” Available at http://www.schneier.com/paper-pki.html (linked from the class web page)4Secret key sharing•Security of all symmetric and asymmetric schemes relies on secrecy of a secret key.•How to make a secret key “more secret”?• An idea: let’s split a secret key K and store the shares in different places (e.g. on n different computers), such that•any t shares allow to reconstruct K•if t-1 computers become compromised, we are still fine in that no one can learn anything about K from t-1 shares• To do any harm an adversary must compromise t computers• This is (t,n)-secret sharing scheme.5Shamir’s secret sharing•Let p be a large prime. •To (t,n) share a secret z!Zp:•Choose t-1 random elements of Zp: a1,...at-1. Let a0=z. View these as the coefficients of a polynomial f of degree t-1, meaning f(x)=a0+a1x+.....+at-1xt-1•Store yi=f(i) on each computer i=1,...,n.•To recover the secret given t pairs (i, yi) for i󲰉Suse the Lagrange interpolation to find:•The scheme is unconditionally securez = a0= f (0) = !i∈Syi"j∈S, j"=i− ji − j1Can be pre-computed6•There are several weaknesses of the Shamir’s secret sharing protocol:•if some parties cheat during the secret reconstruction, the secret cannot be recovered and others cannot detect cheating•the dealer needs to be trusted•A verifiable secret sharing protocol allows to overcome these difficulties•It is also desirable that parties be able to perform secret-key operations (decryption or signing) such that no party holds the whole secret key at any time•Threshold schemes allow to achieve this7(2,2) Visual secret sharing•Let’s consider a protocol to (2,2)- share a black-and-white image:•for each pixel compute the shares as follows:8An exampleShare 1Share 2The result? See in class9References•Secret Sharing•David Wagner’s lecture notes. Available from http://www.cs.berkeley.edu/~daw/teaching/cs276-s04/22.pdf•Visual cryptography•Doug Stinson’s visual cryptography page. http://www.cacr.math.uwaterloo.ca/~dstinson/visual.html10Implementation pitfalls•We learned about various cryptographic primitives and the provable security approach, saw many secure constructions.•You are almost ready to employ this knowledge in practice.•Let us review some common mistakes one needs to be aware of and avoid when implementing cryptographic protocols.11Always remember to•Use widely accepted and believed to be secure building blocks (e.g. AES).•Use provably secure (under reasonable assumptions) constructions (e.g. $CBC).•Do not assume that the schemes provide security properties other than what is proven about them (e.g. encryption does not provide authenticity).•Realize that the use of a provably secure scheme does not guarantee that the entire system will be secure.•Make sure that you implement exactly the scheme that was proven secure.12Not using the right primitives•ATM-based passive optical networks commonly use a block cipher called CHURN. It’s key size is 8 bits and it’s block size is 4 bits!•The use of the ECB mode and the Plain RSA encryption is still very common.Using the constructs without security proofs13Not using the right tool•It is tempting to believe that encryption provide some authenticity.•The first versions of the SSH protocol, IPsec specification and the WEP protocol did not use message authentication codes, and thus were subject to certain attacks. •A slightest tweak to a provably-secure scheme can make it insecure•Diebold voting machines encrypted the votes with $CBC, but used all-zero string as an IV.•Microsoft Word and Excel used a variation of CBCS$, but did not pick a new random R each time.Not implementing exactly the provable-secure schemes14Random numbers•It is usually straightforward to implement the pseudo-code descriptions in C or Java.•However, how do you implement commands like ?•The C offers a built-in random number generator, that works roughly as this6 IMPLEMENTATION PITFALLSGiven this description, and a description of the block cipher E, any experienced C or Java program-mer should b e able to easily implement most parts of the above algorithms. This is because almostall of the operations in the above pseudocode are common to all popular languages. For example,the “←” operation corresponds to the standard assignment operator (“=” in C and Java). Theprogrammer might, however, be puzzled about how to implement the “$←” randomized assignmentoperator from the linesK$← {0, 1}kandIV$← {0, 1}n.It is worth thinking about how a programmer might instantiate the “$←” operation in C or Java.In order to implement the algorithms exactly as described in the above pseudocode, the operation“$←” must select bits independently and uniformly at random. If an implementation of CBC$does not do this, then the implementation is not exactly the object described above and in Figure5.2. At a minimum, this means that the security of the software implementation of CBC$ doesnot immediately follow from Theorem 5.19. In the worst case, not only might the security ofthe software implementation not follow from Theorem 5.19, but the software implementation mayactually be insecure.The first problem is that it is hard for computers, which are inherently deterministic, to selectbits independently and uniformly at random. Therefore, people implementing cryptosystems areleft to approximate the$← operation as best they can. The second problem is that there are manynatural