cryptography faq technical miscellany archive name cryptography faq part last modified faq for sci crypt part technical miscellany this is the eighth 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 how do i recover from lost passwords in wordperfect how do i break a vigenere repeated key cipher how do i send encrypted mail under unix pgp ripem pem is the unix crypt command secure how do i use compression with encryption is there an unbreakable cipher what does random mean in cryptography what is the unicity point a k a unicity distance what is key management and why is it important can i use pseudo random or chaotic numbers as a key stream what is the correct frequency list for english letters what is the enigma how do i shuffle cards can i foil s w pirates by encrypting my cd rom can you do automatic cryptanalysis of simple ciphers what is the coding system used by vcr how do i recover from lost passwords in wordperfect wordperfect encryption has been shown to be very easy to break the method uses xor with two repeating key streams a typed password and a byte wide counter initialized to the password length full descriptions are given in bennett ben and bergen and caelli ber chris galas writes someone awhile back was looking for a way to decrypt wordperfect document files and i think i have a solution there is a software company named accessdata east south orem ut that has a software package that will decrypt any wordperfect lotus quatro pro ms excel and paradox files the cost of the package is steep prices but if you think your pw key is less than characters or char give them a call and ask for the free demo disk the demo disk will decrypt files that have a char or less pw key how do i break a vigenere repeated key cipher a repeated key cipher where the ciphertext is something like the plaintext xor keykeykeykey and so on is called a vigenere cipher if the key is not too long and the plaintext is in english do the following discover the length of the key by counting coincidences see gaines gai sinkov sin trying each displacement of the ciphertext against itself count those bytes which are equal if the two ciphertext portions have used the same key something over of the bytes will be equal if they have used different key then less than will be equal assuming random bit bytes of key covering normal ascii text the smallest displacement which indicates an equal key is the length of the repeated key shift the text by that length and xor it with itself this removes the key and leaves you with text xored with itself since english has about bit of real information per byte streams of text xored together has bits of info per bit byte providing plenty of redundancy for choosing a unique decryption and in fact one stream of text xored with itself has just bit per byte if the key is short it might be even easier to treat this as a standard polyalphabetic substitution all the old cryptanalysis texts show how to break those it s possible with those methods in the hands of an expert if there s only ten times as much text as key see for example gaines gai sinkov sin how do i send encrypted mail under unix pgp ripem pem here s one popular method using the des command cat file compress des private key uuencode mail meanwhile there is a de jure internet standard in the works called pem privacy enhanced mail it is described in rfcs through to join the pem mailing list contact pem dev request tis com there is a beta version of pem being tested at the time of this writing there are also two programs available in the public domain for encrypting mail pgp and ripem both are available by ftp each has its own newsgroup alt security pgp and alt security ripem each has its own faq as well pgp is most commonly used outside the usa since it uses the rsa algorithm without a license and rsa s patent is valid only or at least primarily in the usa ripem is most commonly used inside the usa since it uses the rsaref which is freely available within the usa but not available for shipment outside the usa since both programs use a secret key algorithm for encrypting the body of the message pgp used idea ripem uses des and rsa for encrypting the message key they should be able to interoperate freely although there have been repeated calls for each to understand the other s formats and algorithm choices no interoperation is available at this time as far as we know is the unix crypt command secure no see ree there is a program available called cbw crypt breaker s workbench which can be used to do ciphertext only attacks on files encrypted with crypt one source for cbw is ftpcb how do i use compression with encryption a number of people have proposed doing perfect compression followed by some simple encryption method e g xor with a repeated key unfortunately you can only compress perfectly if you know the exact distribution of possible inputs for all practical purposes it s impossible to describe the typical english text beyond coarse characteristics such as single letter frequencies you can build up more and more sophisticated models of your inputs but if the enemy has a slightly more accurate model he ll be able to find some redundancy in your compressed output note that nearly all practical compression schemes unless they have been designed with cryptography in mind produce output that actually starts off with high redundancy for example the output of unix compress begins with a well known three byte magic number that can serve as an entering wedge for cryptanalysis this is not to say that compression before encryption is inherently a bad idea it just has to be done very very carefully and by no means removes the need for strong encryption compression after encryption is silly is there an unbreakable cipher yes the one time pad is unbreakable see part unfortunately the one time pad requires secure distribution of as much key material as plaintext of course a cryptosystem need not be utterly unbreakable to be useful rather it needs to be strong enough to resist attacks by likely enemies for whatever length of time the data it protects is expected to remain valid what does random mean in cryptography cryptographic applications demand much more out of a pseudorandom number generator than most applications for a source of bits to be cryptographically random it must be computationally impossible to predict what the nth random bit will be given complete knowledge of the algorithm or hardware generating the stream and the sequence of th through n st bits for all n up to the lifetime of the source a software generator also known as pseudo random has the function of expanding a truly random seed to a longer string of apparently random bits this seed must be large enough not to be guessed by the opponent ideally it should also be truly random perhaps generated by a hardware random number source those who have sparcstation workstations could for example generate random numbers using the audio input device as a source of entropy by not connecting anything to it for example cat dev audio compress foo gives a file of high entropy not random but with much randomness in it one can then encrypt that file using part of itself as a key for example to convert that seed entropy into a pseudo random string when looking for hardware devices to provide this entropy it is important really to measure the entropy rather than just assume that because it looks complicated to a human it must be random for example disk operation completion times sound like they might be unpredictable to many people but a spinning disk is much like a clock and its output completion times are relatively low in entropy what is the unicity point a k a unicity distance see sha the unicity distance is an approximation to that amount of ciphertext such that the sum of the real information entropy in the corresponding source text and encryption key equals the number of ciphertext bits used ciphertexts significantly longer than this can be shown probably to have a unique decipherment this is used to back up a claim of the validity of a ciphertext only cryptanalysis ciphertexts significantly shorter than this are likely to have multiple equally valid decryptions and therefore to gain security from the opponent s difficulty choosing the correct one unicity distance like all statistical or information theoretic measures does not make deterministic predictions but rather gives probabilistic results namely the minimum amount of ciphertext for which it is likely that there is only a single intelligible plaintext corresponding to the ciphertext when all possible keys are tried for the decryption working cryptologists don t normally deal with unicity distance as such instead they directly determine the likelihood of events of interest let the unicity distance of a cipher be d characters if fewer than d ciphertext characters have been intercepted then there is not enough information to distinguish the real key from a set of possible keys des has a unicity distance of characters which is less than ciphertext blocks each block corresponds to ascii characters this may seem alarmingly low at first but the unicity distance gives no indication of the computational work required to find the key after approximately d characters have been intercepted in fact actual cryptanalysis seldom proceeds along the lines used in discussing unicity distance like other measures such as key size unicity distance is something that guarantees insecurity if it s too small but doesn t guarantee security if it s high few practical cryptosystems are absolutely impervious to analysis all manner of characteristics might serve as entering wedges to crack some cipher messages however similar information theoretic considerations are occasionally useful for example to determine a recommended key change interval for a particular cryptosystem cryptanalysts also employ a variety of statistical and information theoretic tests to help guide the analysis in the most promising directions unfortunately most literature on the application of information statistics to cryptanalysis remains classified even the seminal work of alan turing see koz for some insight into the possibilities see kul and goo what is key management and why is it important one of the fundamental axioms of cryptography is that the enemy is in full possession of the details of the general cryptographic system and lacks only the specific key data employed in the encryption of course one would assume that the cia does not make a habit of telling mossad about its cryptosystems but mossad probably finds out anyway repeated use of a finite amount of key provides redundancy that can eventually facilitate cryptanalytic progress thus especially in modern communication systems where vast amounts of information are transferred both parties must have not only a sound cryptosystem but also enough key material to cover the traffic key management refers to the distribution authentication and handling of keys a publicly accessible example of modern key management technology is the stu iii secure telephone unit which for classified use employs individual coded crypto ignition keys and a central key management center operated by nsa there is a hierarchy in that certain ciks are used by authorized cryptographic control personnel to validate the issuance of individual traffic keys and to perform installation maintenance functions such as the reporting of lost ciks this should give an inkling of the extent of the key management problem for public key systems there are several related issues many having to do with whom do you trust can i use pseudo random or chaotic numbers as a key stream chaotic equations and fractals produce an apparent randomness from relatively compact generators perhaps the simplest example is a linear congruential sequence one of the most popular types of random number generators where there is no obvious dependence between seeds and outputs unfortunately the graph of any such sequence will in a high enough dimension show up as a regular lattice mathematically this lattice corresponds to structure which is notoriously easy for cryptanalysts to exploit more complicated generators have more complicated structure which is why they make interesting pictures but a cryptographically strong sequence will have no computable structure at all see knu exercise ree and boy what is the correct frequency list for english letters there are three answers to this question each slightly deeper than the one before you can find the first answer in various books namely a frequency list computed directly from a certain sample of english text of course any such list will be correctly computed but exactly which list you get depends on which sample was taken the second answer is that the question doesn t make sense what do you mean by english letters the english language is not a fixed finite closed object that can be exactly characterized it has changed over time it is different between different authors any particular message will have different statistics from those of the language as a whole the third answer is that yes no particular message is going to have exactly the same characteristics as english in general but for all reasonable statistical uses these slight discrepancies won t matter in fact there s an entire field called bayesian statistics other buzzwords are maximum entropy methods and maximum likelihood estimation which studies questions like what s the chance that a text with these letter frequencies is in english and comes up with reasonably robust answers so make your own list from your own samples of english text it will be good enough for practical work if you use it properly what is the enigma for a project in data security we are looking for sources of information about the german enigma code and how it was broken by the british during wwii see wel dea koz hod kah how do i shuffle cards card shuffling is a special case of the permutation of an array of values using a random or pseudo random function all possible output permutations of this process should be equally likely to do this you need a random function modran x which will produce a uniformly distributed random integer in the interval x given that function you can shuffle with the following c code assuming arrlth is the length of array arr and swap interchanges values at the two addresses given for n arrlth n n swap arr modran n arr n modran x can not be achieved exactly with a simple ranno x since ranno s interval may not be divisible by x although in most cases the error will be very small to cover this case one can take ranno s modulus mod x call that number y and if ranno returns a value less than y go back and get another ranno value can i foil s w pirates by encrypting my cd rom someone will frequently express the desire to publish a cd rom with possibly multiple pieces of software perhaps with each encrypted separately and will want to use different keys for each user perhaps even good for only a limited period of time in order to avoid piracy as far as we know this is impossible since there is nothing in standard pc or workstation hardware which uniquely identifies the user at the keyboard if there were such an identification then the cd rom could be encrypted with a key based in part on the one sold to the user and in part on the unique identifier however in this case the cd rom is one of a kind and that defeats the intended purpose if the cd rom is to be encrypted once and then mass produced there must be a key or set of keys for that encryption produced at some stage in the process that key is useable with any copy of the cd rom s data the pirate needs only to isolate that key and sell it along with the illegal copy can you do automatic cryptanalysis of simple ciphers schneier chinet chi il us bruce schneier says accessdata of orem utah sells products that break the password scheme of a number of popular macintosh and pc software packages their telephone number is no pd software has been cited but there are many papers on the subject peleg s and rosenfeld a breaking substitution ciphers using a relaxation algorithm comm acm vol pp nov lucks michael a constraint satisfaction algorithm for the automated decryption of simple substitution ciphers advances in cryptology crypto springer lecture notes in computer science vol the paper also contains references to earlier work on the subject john carrol and steve martin the automated cryptanalysis of substitution ciphers cryptologia vol x number oct p john carrol and lynda robbins automated cryptanalysis of polyalphabetic ciphers cryptologia vol xi number oct p martin kochanski a survey of data insecurity packages cryptologia vol xi number jan p martin kochanski another data insecurity package cryptologia vol xii number july p cryptologia vol xiii number pp king and bahler probabilistic relaxation in the cryptanalysis of simple substitution ciphers cryptologia king and bahler an algorithmic solution of sequential homophonic ciphers cryptologia april in press r spillman et al use of genetic algorithms in cryptanalysis of simple substitution ciphers cryptologia vol xvii number jan p what is the coding system used by vcr one very frequently asked question in sci crypt is about how the vcr codes work the following article attempts to describe it k shirriff c welch a kinsman decoding a vcr controller code cryptologia july pp
