cryptography faq mathematical cryptology archive name cryptography faq part last modified faq for sci crypt part mathematical cryptology this is the fourth of ten parts of the sci crypt faq the parts are mostly independent but you should read the first part before the rest we don t have the time to send out missing parts by mail so don t ask notes such as kah refer to the reference list in the last part the sections of this faq are available via anonymous ftp to rtfm mit edu as pub usenet news answers cryptography faq part xx the cryptography faq is posted to the newsgroups sci crypt sci answers and news answers every days contents in mathematical terms what is a private key cryptosystem what is an attack what s the advantage of formulating all this mathematically why is the one time pad secure what s a ciphertext only attack what s a known plaintext attack what s a chosen plaintext attack in mathematical terms what can you say about brute force attacks what s a key guessing attack what s entropy in mathematical terms what is a private key cryptosystem a private key cryptosystem consists of an encryption system e and a decryption system d the encryption system e is a collection of functions e k indexed by keys k mapping some set of plaintexts p to some set of ciphertexts c similarly the decryption system d is a collection of functions d k such that d k e k p p for every plaintext p that is succesful decryption of ciphertext into plaintext is accomplished using the same key index as was used for the corresponding encryption of plaintext into ciphertext such systems wherein the same key value is used to encrypt and decrypt are also known as symmetric cryptoystems what is an attack in intuitive terms a passive attack on a cryptosystem is any method of starting with some information about plaintexts and their corresponding ciphertexts under some unknown key and figuring out more information about the plaintexts it s possible to state mathematically what this means here we go fix functions f g and h of n variables fix an encryption system e and fix a distribution of plaintexts and keys an attack on e using g assuming f giving h with probability p is an algorithm a with a pair f g of inputs and one output h such that there is probability p of computing h h p p n if we have f f p p n and g g e k p e k p n note that this probability depends on the distribution of the vector k p p n the attack is trivial or pointless if there is probability at least p of computing h h p p n if f f p p n and g g c c n here c c n range uniformly over the possible ciphertexts and have no particular relation to p p n in other words an attack is trivial if it doesn t actually use the encryptions e k p e k p n an attack is called one ciphertext if n two ciphertext if n and so on what s the advantage of formulating all this mathematically in basic cryptology you can never prove that a cryptosystem is secure read part we keep saying a strong cryptosystem must have this property but having this property is no guarantee that a cryptosystem is strong in contrast the purpose of mathematical cryptology is to precisely formulate and if possible prove the statement that a cryptosystem is strong we say for example that a cryptosystem is secure against all passive attacks if any nontrivial attack against the system as defined above is too slow to be practical if we can prove this statement then we have confidence that our cryptosystem will resist any passive cryptanalytic technique if we can reduce this statement to some well known unsolved problem then we still have confidence that the cryptosystem isn t easy to break other parts of cryptology are also amenable to mathematical definition again the point is to explicitly identify what assumptions we re making and prove that they produce the desired results we can figure out what it means for a particular cryptosystem to be used properly it just means that the assumptions are valid the same methodology is useful for cryptanalysis too the cryptanalyst can take advantage of incorrect assumptions often he can try to construct a proof of security for a system see where the proof fails and use these failures as the starting points for his analysis why is the one time pad secure by definition the one time pad is a cryptosystem where the plaintexts ciphertexts and keys are all strings say byte strings of some length m and e k p is just the sum let s say the exclusive or of k and p it is easy to prove mathematically that there are no nontrivial single ciphertext attacks on the one time pad assuming a uniform distribution of keys note that we don t have to assume a uniform distribution of plaintexts here s the proof let a be an attack i e an algorithm taking two inputs f g and producing one output h with some probability p that h h p whenever f f p and g g e k p i e g g k p then because the distribution of k is uniform and independent of p the distribution of k p must also be uniform and independent of p but also the distribution of c is uniform and independent of p hence there is probability exactly p that h h p whenever f f p and g g c over all p and c thus a fortiori a is trivial on the other hand the one time pad is not secure if a key k is used for more than one plaintext i e there are nontrivial multiple ciphertext attacks so to be properly used a key k must be thrown away after one encryption the key is also called a pad this explains the name one time pad what s a ciphertext only attack in the notation above a ciphertext only attack is one where f is constant given only some information g e k p e k p n about n ciphertexts the attack has to have some chance of producing some information h p p n about the plaintexts the attack is trivial if it has just as good a chance of producing h p p n when given g c c n for random c c n for example say g c c and say h p is the first bit of p we can easily write down an attack the guessing attack which simply guesses that h p is this attack is trivial because it doesn t use the ciphertext it has a fifty fifty chance of guessing correctly no matter what on the other hand there is an attack on rsa which produces one bit of information about p with success using c if it is fed a random c then the success rate drops to so this is a nontrivial attack what s a known plaintext attack the classic known plaintext attack has f p p p g c c c c and h p p depending only on p in other words given two ciphertexts c and c and one decryption p the known plaintext attack should produce information about the other decryption p note that known plaintext attacks are often defined in the literature as producing information about the key but this is pointless the cryptanalyst generally cares about the key only insofar as it lets him decrypt further messages what s a chosen plaintext attack a chosen plaintext attack is the first of an increasingly impractical series of active attacks on a cryptosystem attacks where the cryptanalyst feeds data to the encryptor these attacks don t fit into our model of passive attacks explained above anyway a chosen plaintext attack lets the cryptanalyst choose a plaintext and look at the corresponding ciphertext then repeat until he has figured out how to decrypt any message more absurd examples of this sort of attack are the chosen key attack and chosen system attack a much more important form of active attack is a message corruption attack where the attacker tries to change the ciphertext in such a way as to make a useful change in the plaintext there are many easy ways to throw kinks into all of these attacks for instance automatically encrypting any plaintext p as t e k h t r p r p where t is a time key sequence number chosen anew for each message r is a random number and h is a one way hash function here comma means concatenation and plus means exclusive or in mathematical terms what can you say about brute force attacks consider the following known plaintext attack we are given some plaintexts p p n and ciphertexts c c n we re also given a ciphertext c n we run through every key k when we find k such that e k p i c i for every i n we print d k c n if n is big enough that only one key works this attack will succeed on valid inputs all the time while it will produce correct results only once in a blue moon for random inputs thus this is a nontrivial attack its only problem is that it is very slow if there are many possible keys what s a key guessing attack what s entropy say somebody is using the one time pad but isn t choosing keys randomly and uniformly from all m bit messages as he was supposed to for our security proof in fact say he s known to prefer keys which are english words then a cryptanalyst can run through all english words as possible keys this attack will often succeed and it s much faster than a brute force search of the entire keyspace we can measure how bad a key distribution is by calculating its entropy this number e is the number of real bits of information of the key a cryptanalyst will typically happen across the key within e guesses e is defined as the sum of p k log p k where p k is the probability of key k
