In cryptography, a cipher is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. To encipher or encode is to convert information into cipher or code. In common parlance, "cipher" is synonymous with "code", as they are both a set of steps that encrypt a message. Codes substitute different length strings of characters in the output, while ciphers substitute the same number of characters as are input. There are exceptions and some cipher systems may use more, or fewer, characters when output versus the number that were input. Codes operated by substituting according to a large codebook which linked a random string of characters or numbers to a word or phrase. For example, "UQJHSE" could be the code for "Proceed to the following coordinates." When using a cipher the original information is known as plaintext, the encrypted form as ciphertext. The ciphertext message contains all the information of the plaintext message, but is not in a format readable by a human or computer without the proper mechanism to decrypt it.
The operation of a cipher depends on a piece of auxiliary information, called a key. The encrypting procedure is varied depending on the key, which changes the detailed operation of the algorithm. A key must be selected before using a cipher to encrypt a message. Without knowledge of the key, it should be difficult, if not impossible, to decrypt the resulting ciphertext into readable plaintext. Most modern ciphers can be categorized in several ways By whether they work on blocks of symbols of a fixed size, or on a continuous stream of symbols. By whether the same key is used for both encryption and decryption, or if a different key is used for each. If the algorithm is symmetric, the key must be known to no one else. If the algorithm is an asymmetric one, the enciphering key is different from, but related to, the deciphering key. If one key cannot be deduced from the other, the asymmetric key algorithm has the public/private key property and one of the keys may be made public without loss of confidentiality.
The word "cipher" in former times meant "zero" and had the same origin: Middle French as cifre and Medieval Latin as cifra, from the Arabic صفر sifr = zero. "Cipher" was used for any decimal digit any number. There are many theories about how the word "cipher" may have come to mean "encoding". Encoding involved numbers; the Roman number system was cumbersome because there was no concept of zero. The concept of zero, now common knowledge, was alien to medieval Europe, so confusing and ambiguous to common Europeans that in arguments people would say "talk and not so far fetched as a cipher". Cipher came to mean concealment of clear messages or encryption; the French formed the word "chiffre" and adopted the Italian word "zero". The English used "zero" for "0", "cipher" from the word "ciphering" as a means of computing; the Germans used the words "Ziffer" and "Chiffre". The Dutch still use the word "cijfer" to refer to a numerical digit; the Slovaks also use the word "cifra" to refer to a numerical digit.
The Bosnians and Serbians use the word "cifra", which refers to a digit, or in some cases, any number. Besides "cifra", they use word "broj" for a number; the Italians and the Spanish use the word "cifra" to refer to a number. The Swedes use the word "siffra"; the Greeks use the word "τζίφρα" to refer to a hard-to-read signature one written with a single stroke of the pen. Ibrahim Al-Kadi concluded that the Arabic word sifr, for the digit zero, developed into the European technical term for encryption; as the decimal zero and its new mathematics spread from the Arabic world to Europe in the Middle Ages, words derived from sifr and zephyrus came to refer to calculation, as well as to privileged knowledge and secret codes. According to Ifrah, "in thirteenth-century Paris, a'worthless fellow' was called a'... cifre en algorisme', i.e. an'arithmetical nothing'." Cipher was the European pronunciation of sifr, cipher came to mean a message or communication not understood. In non-technical usage, a " code" means a "cipher".
Within technical discussions, the words "code" and "cipher" refer to two different concepts. Codes work at the level of meaning—that is, words or phrases are converted into something else and this chunking shortens the message. An example of this is the Commercial Telegraph Code, used to shorten long telegraph messages which resulted from entering into commercial contracts using exchanges of Telegrams. Another example is given by whole word ciphers, which allow the user to replace an entire word with a symbol or character, much like the way Japanese utilize Kanji characters to supplement their language. Ex "The quick brown fox jumps over the lazy dog" becomes "The quick brown 狐 jumps 过 the lazy 狗". Ciphers, on the other hand, work at a lower level: the level of individual letters, small groups of letters, or, in modern schemes, individual bits and blocks of bits; some systems used both codes and ciphers in one system, using superencipherment to increase the security. In some cases the terms codes and ciphers are used synonymously to substitution and transposition.
Cryptography was split into a dichotomy
Cryptanalysis is the study of analyzing information systems in order to study the hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages if the cryptographic key is unknown. In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of side-channel attacks that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation. Though the goal has been the same, the methods and techniques of cryptanalysis have changed drastically through the history of cryptography, adapting to increasing cryptographic complexity, ranging from the pen-and-paper methods of the past, through machines like the British Bombes and Colossus computers at Bletchley Park in World War II, to the mathematically advanced computerized schemes of the present. Methods for breaking modern cryptosystems involve solving constructed problems in pure mathematics, the best-known being integer factorization.
Given some encrypted data, the goal of the cryptanalyst is to gain as much information as possible about the original, unencrypted data. It is useful to consider two aspects of achieving this; the first is breaking the system —, discovering how the encipherment process works. The second is solving the key, unique for a particular encrypted message or group of messages. Attacks can be classified based on; as a basic starting point it is assumed that, for the purposes of analysis, the general algorithm is known. This is a reasonable assumption in practice — throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through espionage and reverse engineering.: Ciphertext-only: the cryptanalyst has access only to a collection of ciphertexts or codetexts. Known-plaintext: the attacker has a set of ciphertexts to which he knows the corresponding plaintext. Chosen-plaintext: the attacker can obtain the ciphertexts corresponding to an arbitrary set of plaintexts of his own choosing.
Adaptive chosen-plaintext: like a chosen-plaintext attack, except the attacker can choose subsequent plaintexts based on information learned from previous encryptions. Adaptive chosen ciphertext attack. Related-key attack: Like a chosen-plaintext attack, except the attacker can obtain ciphertexts encrypted under two different keys; the keys are unknown. Attacks can be characterised by the resources they require; those resources include: Time -- the number of computation steps. Memory — the amount of storage required to perform the attack. Data — the quantity and type of plaintexts and ciphertexts required for a particular approach. It's sometimes difficult to predict these quantities especially when the attack isn't practical to implement for testing, but academic cryptanalysts tend to provide at least the estimated order of magnitude of their attacks' difficulty, for example, "SHA-1 collisions now 252."Bruce Schneier notes that computationally impractical attacks can be considered breaks: "Breaking a cipher means finding a weakness in the cipher that can be exploited with a complexity less than brute force.
Never mind that brute-force might require 2128 encryptions. The results of cryptanalysis can vary in usefulness. For example, cryptographer Lars Knudsen classified various types of attack on block ciphers according to the amount and quality of secret information, discovered: Total break — the attacker deduces the secret key. Global deduction — the attacker discovers a functionally equivalent algorithm for encryption and decryption, but without learning the key. Instance deduction — the attacker discovers additional plaintexts not known. Information deduction — the attacker gains some Shannon information about plaintexts not known. Distinguishing algorithm — the attacker can distinguish the cipher from a random permutation. Academic attacks are against weakened versions of a cryptosystem, such as a block cipher or hash function with some rounds removed. Many, but not all, attacks become exponentially more difficult to execute as rounds are added to a cryptosystem, so it's possible for the full cryptosystem to be strong though reduced-round variants are weak.
Nonetheless, partial breaks that come close to breaking the original cryptosystem may mean that a full break will follow. In academic cryptography, a weakness or a break in a scheme is defined quite conservatively: it might require impractical amounts of time, memory, or known plaintexts, it might require the attacker be able to do things many real-world attackers can't: for example, the attacker may need to choose particular plaintexts to be encrypted or to ask for plaintexts to be encrypted using several keys related to the secret key. Furthermore
Password strength is a measure of the effectiveness of a password against guessing or brute-force attacks. In its usual form, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to guess it correctly; the strength of a password is a function of length and unpredictability. Using strong passwords lowers overall risk of a security breach, but strong passwords do not replace the need for other effective security controls; the effectiveness of a password of a given strength is determined by the design and implementation of the factors. The first factor is the main focus in this article; the rate at which an attacker can submit guessed passwords to the system is a key factor in determining system security. Some systems impose a time-out of several seconds after a small number of failed password entry attempts. In the absence of other vulnerabilities, such systems can be secured with simple passwords; however the system must store information about the user passwords in some form and if that information is stolen, say by breaching system security, the user passwords can be at risk.
Passwords are created either automatically or by a human. While the strength of randomly chosen passwords against a brute-force attack can be calculated with precision, determining the strength of human-generated passwords is challenging. Humans are asked to choose a password, sometimes guided by suggestions or restricted by a set of rules, when creating a new account for a computer system or Internet Web site. Only rough estimates of strength are possible, since humans tend to follow patterns in such tasks, those patterns can assist an attacker. In addition, lists of chosen passwords are available for use by password guessing programs; such lists include the numerous online dictionaries for various human languages, breached databases of plaintext and hashed passwords from various online business and social accounts, along with other common passwords. All items in such lists are considered weak. For some decades, investigations of passwords on multi-user computer systems have shown that 40% or more are guessed using only computer programs, more can be found when information about a particular user is taken into account during the attack.
Systems that use passwords for authentication must have some way to check any password entered to gain access. If the valid passwords are stored in a system file or database, an attacker who gains sufficient access to the system will obtain all user passwords, giving the attacker access to all accounts on the attacked system, other systems where users employ the same or similar passwords. One way to reduce this risk is to store only a cryptographic hash of each password instead of the password itself. Standard cryptographic hashes, such as the Secure Hash Algorithm series, are hard to reverse, so an attacker who gets hold of the hash value cannot directly recover the password. However, knowledge of the hash value lets the attacker test guesses offline. Password cracking programs are available that will test a large number of trial passwords against a purloined cryptographic hash. Improvements in computing technology keep increasing the rate at which guessed passwords can be tested. For example, in 2010, the Georgia Tech Research Institute developed a method of using GPGPU to crack passwords much faster.
Elcomsoft invented the usage of common graphic cards for quicker password recovery in August 2007 and soon filed a corresponding patent in the US. As of 2011, commercial products are available that claim the ability to test up to 112,000 passwords per second on a standard desktop computer using a high-end graphics processor; such a device will crack a 6 letter single-case password in one day. Note that the work can be distributed over many computers for an additional speedup proportional to the number of available computers with comparable GPUs. Special key stretching hashes are available that take a long time to compute, reducing the rate at which guessing can take place. Although it is considered best practice to use key stretching, many common systems do not. Another situation where quick guessing is possible is when the password is used to form a cryptographic key. In such cases, an attacker can check to see if a guessed password decodes encrypted data. For example, one commercial product claims to test 103,000 WPA PSK passwords per second.
If a password system only stores the hash of the password, an attacker can pre-compute hash values for common passwords variants and for all passwords shorter than a certain length, allowing rapid recovery of the password once its hash is obtained. Long lists of pre-computed password hashes can be efficiently stored using rainbow tables; this method of attack can be foiled by storing a random value, called a cryptographic salt, along with the hash. The salt is combined with the password when computing the hash, so an attacker precomputing a rainbow table would have to store for each password its hash with every possible salt value; this becomes infeasible if the salt has a big enough range. Many authentication systems in common use do not employ salts and rainbow tables are available on the Internet for several such systems, it is usual in the computer industry to specify password strength in terms of information entropy, measured in bits and is a concept from information theory. Instead of the number of guesses needed to find the password with certainty, the base-2 logarithm of that number is given
A password is a word or string of characters used for user authentication to prove identity or access approval to gain access to a resource, to be kept secret from those not allowed access. The use of passwords is known to be ancient. Sentries would challenge those wishing to enter an area or approaching it to supply a password or watchword, would only allow a person or group to pass if they knew the password. In modern times, user names and passwords are used by people during a log in process that controls access to protected computer operating systems, mobile phones, cable TV decoders, automated teller machines, etc. A typical computer user has passwords for many purposes: logging into accounts, retrieving e-mail, accessing applications, networks, web sites, reading the morning newspaper online. Despite the name, there is no need for passwords to be actual words; some passwords are formed from multiple words and may more be called a passphrase. The terms passcode and passkey are sometimes used when the secret information is purely numeric, such as the personal identification number used for ATM access.
Passwords are short enough to be memorized and typed, although they may be longer and more complex if the user wishes to be more secure. Most organizations specify a password policy that sets requirements for the composition and usage of passwords dictating minimum length, required categories, prohibited elements; some governments have national authentication frameworks that define requirements for user authentication to government services, including requirements for passwords. Passwords or watchwords have been used since ancient times. Polybius describes the system for the distribution of watchwords in the Roman military as follows: The way in which they secure the passing round of the watchword for the night is as follows: from the tenth maniple of each class of infantry and cavalry, the maniple, encamped at the lower end of the street, a man is chosen, relieved from guard duty, he attends every day at sunset at the tent of the tribune, receiving from him the watchword—that is a wooden tablet with the word inscribed on it – takes his leave, on returning to his quarters passes on the watchword and tablet before witnesses to the commander of the next maniple, who in turn passes it to the one next him.
All do the same until it reaches the first maniples, those encamped near the tents of the tribunes. These latter are obliged to deliver the tablet to the tribunes before dark. So that if all those issued are returned, the tribune knows that the watchword has been given to all the maniples, has passed through all on its way back to him. If any one of them is missing, he makes inquiry at once, as he knows by the marks from what quarter the tablet has not returned, whoever is responsible for the stoppage meets with the punishment he merits. Passwords in military use evolved to include not just a password, but a password and a counterpassword. S. 101st Airborne Division used a password—flash—which was presented as a challenge, answered with the correct response—thunder. The challenge and response were changed every three days. American paratroopers famously used a device known as a "cricket" on D-Day in place of a password system as a temporarily unique method of identification. Passwords have been used with computers since the earliest days of computing.
The Compatible Time-Sharing System, an operating system introduced at MIT in 1961, was the first computer system to implement password login. CTSS had a LOGIN command. "After typing PASSWORD, the system turns off the printing mechanism, if possible, so that the user may type in his password with privacy." In the early 1970s, Robert Morris developed a system of storing login passwords in a hashed form as part of the Unix operating system. The system was based on a simulated Hagelin rotor crypto machine, first appeared in 6th Edition Unix in 1974. A version of his algorithm, known as crypt, used a 12-bit salt and invoked a modified form of the DES algorithm 25 times to reduce the risk of pre-computed dictionary attacks; the easier a password is for the owner to remember means it will be easier for an attacker to guess. However, passwords which are difficult to remember may reduce the security of a system because users might need to write down or electronically store the password, users will need frequent password resets and users are more to re-use the same password.
The more stringent requirements for password strength, e.g. "have a mix of uppercase and lowercase letters and digits" or "change it monthly", the greater the degree to which users will subvert the system. Others argue longer passwords provide more security than shorter passwords with a wide variety of characters. In The Memorability and Security of Passwords, Jeff Yan et al. examine the effect of advice given to users about a good choice of password. They found that passwords based on thinking of a phrase and taking the first letter of each word are just as memorable as naively selected passwords, just as hard to crack as randomly generated passwords. Combining two or more unrelated words and altering some of the letters to special characters or numbers is another good method, but a single di
In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the key, created from the password using a key derivation function; this is known as an exhaustive key search. A brute-force attack is a cryptanalytic attack that can, in theory, be used to attempt to decrypt any encrypted data; such an attack might be used when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier. When password-guessing, this method is fast when used to check all short passwords, but for longer passwords other methods such as the dictionary attack are used because a brute-force search takes too long. Longer passwords and keys have more possible values, making them exponentially more difficult to crack than shorter ones. Brute-force attacks can be made less effective by obfuscating the data to be encoded making it more difficult for an attacker to recognize when the code has been cracked or by making the attacker do more work to test each guess.
One of the measures of the strength of an encryption system is how long it would theoretically take an attacker to mount a successful brute-force attack against it. Brute-force attacks are an application of brute-force search, the general problem-solving technique of enumerating all candidates and checking each one. Brute-force attacks work by calculating every possible combination that could make up a password and testing it to see if it is the correct password; as the password's length increases, the amount of time, on average, to find the correct password increases exponentially. The resources required for a brute-force attack grow exponentially with increasing key size, not linearly. Although U. S. export regulations restricted key lengths to 56-bit symmetric keys, these restrictions are no longer in place, so modern symmetric algorithms use computationally stronger 128- to 256-bit keys. There is a physical argument that a 128-bit symmetric key is computationally secure against brute-force attack.
The so-called Landauer limit implied by the laws of physics sets a lower limit on the energy required to perform a computation of kT · ln 2 per bit erased in a computation, where T is the temperature of the computing device in kelvins, k is the Boltzmann constant, the natural logarithm of 2 is about 0.693. No irreversible computing device can use less energy than this in principle. Thus, in order to flip through the possible values for a 128-bit symmetric key would, require 2128 − 1 bit flips on a conventional processor. If it is assumed that the calculation occurs near room temperature, the Von Neumann-Landauer Limit can be applied to estimate the energy required as ~1018 joules, equivalent to consuming 30 gigawatts of power for one year; this is equal to 30 × 109 W × 365 × 24 × 3600 s = 9.46 × 1017 262.7 TWh. The full actual computation – checking each key to see if a solution has been found – would consume many times this amount. Furthermore, this is the energy requirement for cycling through the key space.
However, this argument assumes that the register values are changed using conventional set and clear operations which generate entropy. It has been shown that computational hardware can be designed not to encounter this theoretical obstruction, though no such computers are known to have been constructed; as commercial successors of governmental ASIC solutions have become available known as custom hardware attacks, two emerging technologies have proven their capability in the brute-force attack of certain ciphers. One is modern graphics processing unit technology, the other is the field-programmable gate array technology. GPUs benefit from their wide availability and price-performance benefit, FPGAs from their energy efficiency per cryptographic operation. Both technologies try to transport the benefits of parallel processing to brute-force attacks. In case of GPUs some hundreds, in the case of FPGA some thousand processing units making them much better suited to cracking passwords than conventional processors.
Various publications in the fields of cryptographic analysis have proved the energy efficiency of today's FPGA technology, for example, the COPACOBANA FPGA Cluster computer consumes the same energy as a single PC, but performs like 2,500 PCs for certain algorithms. A number of firms provide hardware-based FPGA cryptographic analysis solutions from a single FPGA PCI Express card up to dedicated FPGA computers. WPA and WPA2 encryption have been brute-force attacked by reducing the workload by a factor of 50 in comparison to conventional CPUs and some hundred in case of FPGAs. AES permits the use of 256-bit keys. Breaking a symmetric 256-bit key by brute force requires 2128 times more computational power than a 128-bit key. Fifty supercomputers that could check a billion billion AES keys per second would, in theory, require about 3×1051 years to exhaust the 256-bit key space. An underlying assumption of a brute-force attack is that the complete keyspace was used to generate keys, something that relies on an effective random number generator, that there are no defects in the algorithm or its implementation.
In algorithms, precomputation is the act of performing an initial computation before run time to generate a lookup table that can be used by an algorithm to avoid repeated computation each time it is executed. Precomputation is used in algorithms that depend on the results of expensive computations that don't depend on the input of the algorithm. A trivial example of precomputation is the use of hardcoded mathematical constants, such as π and e, rather than computing their approximations to the necessary precision at run time. In databases, the term materialization is used to refer to storing the results of a precomputation, e.g. in a materialized view. Precomputing a set of intermediate results at the beginning of an algorithm's execution can increase algorithmic efficiency substantially; this becomes advantageous when one or more inputs is constrained to a small enough range that the results can be stored in a reasonably sized block of memory. Because memory access is constant in time complexity, any algorithm with a component which has worse than constant efficiency over a small input range can be improved by precomputing values.
In some cases efficient approximation algorithms can be obtained by computing a discrete subset of values and interpolating for intermediate input values, since interpolation is a linear operation. Before the advent of computers, printed lookup tables of values were used by people to speed up hand calculations of complex functions, such as in trigonometric tables, logarithm tables, tables of statistical density functions School children are taught to memorize "times tables" to avoid calculations of the most used numbers; as early as 493 A. D. Victorius of Aquitaine wrote a 98-column multiplication table which gave the product of every number from 2 to 50 times and the rows were "a list of numbers starting with one thousand, descending by hundreds to one hundred descending by tens to ten by ones to one, the fractions down to 1/144" Even modern computer implementations of digital trigonometric functions use precomputed lookup tables to either provide coefficients for interpolation algorithms or to initialise successive approximation algorithms.
Many attacks on cryptosystems involve precomputation. Examples of large-scale precomputation as part of modern efficient algorithms include: Rainbow tables Perfect hashes The cube attack Precalculated BSP trees for visibility calculations in 3D graphics Radiosity precomputation for illumination in 3D graphicsCompilers use precomputation extensively as a means of increasing the run-time speed of the resulting code: this precomputation can be regarded as in effect a form of partial evaluation of the program code itself. Examples of this sort of precomputation include dataflow strength reduction steps. Mathematical table Algorithmic efficiency Partial evaluation