Misplaced Pages

#583416

115-507: The Secure Hash Algorithms are a family of cryptographic hash functions published by the National Institute of Standards and Technology (NIST) as a U.S. Federal Information Processing Standard (FIPS), including: The corresponding standards are FIPS PUB 180 (original SHA), FIPS PUB 180-1 (SHA-1), FIPS PUB 180-2 (SHA-1, SHA-256, SHA-384, and SHA-512). NIST has updated Draft FIPS Publication 202, SHA-3 Standard separate from

230-523: A S T {\displaystyle S^{T}} -valued random variable, where S T {\displaystyle S^{T}} is the space of all the possible functions from the set T {\displaystyle T} into the space S {\displaystyle S} . However this alternative definition as a "function-valued random variable" in general requires additional regularity assumptions to be well-defined. The set T {\displaystyle T}

345-406: A malicious adversary cannot replace or modify the input data without changing its digest. Thus, if two strings have the same digest, one can be very confident that they are identical. Second pre-image resistance prevents an attacker from crafting a document with the same hash as a document the attacker cannot control. Collision resistance prevents an attacker from creating two distinct documents with

460-724: A probability space , where the index of the family often has the interpretation of time . Stochastic processes are widely used as mathematical models of systems and phenomena that appear to vary in a random manner. Examples include the growth of a bacterial population, an electrical current fluctuating due to thermal noise , or the movement of a gas molecule . Stochastic processes have applications in many disciplines such as biology , chemistry , ecology , neuroscience , physics , image processing , signal processing , control theory , information theory , computer science , and telecommunications . Furthermore, seemingly random changes in financial markets have motivated

575-453: A process with continuous state space . If the state space is n {\displaystyle n} -dimensional Euclidean space, then the stochastic process is called a n {\displaystyle n} - dimensional vector process or n {\displaystyle n} - vector process . The word stochastic in English was originally used as an adjective with

690-446: A "projection" of the law μ {\displaystyle \mu } onto a finite subset of T {\displaystyle T} . For any measurable subset C {\displaystyle C} of the n {\displaystyle n} -fold Cartesian power S n = S × ⋯ × S {\displaystyle S^{n}=S\times \dots \times S} ,

805-447: A CRC was used for message integrity in the WEP encryption standard, but an attack was readily discovered, which exploited the linearity of the checksum. In cryptographic practice, "difficult" generally means "almost certainly beyond the reach of any adversary who must be prevented from breaking the system for as long as the security of the system is deemed important". The meaning of the term

920-498: A Middle French word meaning "speed, haste", and it is probably derived from a French verb meaning "to run" or "to gallop". The first written appearance of the term random process pre-dates stochastic process , which the Oxford English Dictionary also gives as a synonym, and was used in an article by Francis Edgeworth published in 1888. The definition of a stochastic process varies, but a stochastic process

1035-661: A block cipher. A hash function built with the Merkle–Damgård construction is as resistant to collisions as is its compression function; any collision for the full hash function can be traced back to a collision in the compression function. The last block processed should also be unambiguously length padded ; this is crucial to the security of this construction. This construction is called the Merkle–Damgård construction . Most common classical hash functions, including SHA-1 and MD5 , take this form. A straightforward application of

1150-420: A certain period of time. These two stochastic processes are considered the most important and central in the theory of stochastic processes, and were invented repeatedly and independently, both before and after Bachelier and Erlang, in different settings and countries. The term random function is also used to refer to a stochastic or random process, because a stochastic process can also be interpreted as

1265-595: A coin, where the probability of obtaining a head is taken to be p {\displaystyle p} and its value is one, while the value of a tail is zero. In other words, a Bernoulli process is a sequence of iid Bernoulli random variables, where each idealised coin flip is an example of a Bernoulli trial . Random walks are stochastic processes that are usually defined as sums of iid random variables or random vectors in Euclidean space, so they are processes that change in discrete time. But some also use

SECTION 10

#1732790384584

1380-501: A conventional mode of operation, without the same security guarantees; for example, SHACAL , BEAR and LION . Pseudorandom number generators (PRNGs) can be built using hash functions. This is done by combining a (secret) random seed with a counter and hashing it. Some hash functions, such as Skein , Keccak , and RadioGatún , output an arbitrarily long stream and can be used as a stream cipher , and stream ciphers can also be built from fixed-length digest hash functions. Often this

1495-408: A counting process. If a Poisson process is defined with a single positive constant, then the process is called a homogeneous Poisson process. The homogeneous Poisson process is a member of important classes of stochastic processes such as Markov processes and Lévy processes. The homogeneous Poisson process can be defined and generalized in different ways. It can be defined such that its index set

1610-432: A cryptographic hash is as follows: Alice poses a tough math problem to Bob and claims that she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, computes its hash, and tells Bob the hash value (whilst keeping the solution secret). Then, when Bob comes up with the solution himself a few days later, Alice can prove that she had

1725-553: A cryptographic hash to be calculated over the message. This allows the signature calculation to be performed on the relatively small, statically sized hash digest. The message is considered authentic if the signature verification succeeds given the signature and recalculated hash digest over the message. So the message integrity property of the cryptographic hash is used to create secure and efficient digital signature schemes. Password verification commonly relies on cryptographic hashes. Storing all user passwords as cleartext can result in

1840-525: A cryptographic hash to increase the time (and in some cases computer memory) required to perform brute-force attacks on stored password hash digests. For details, see § Attacks on hashed passwords . A password hash also requires the use of a large random, non-secret salt value that can be stored with the password hash. The salt is hashed with the password, altering the password hash mapping for each password, thereby making it infeasible for an adversary to store tables of precomputed hash values to which

1955-454: A deliberate attack. For example, a denial-of-service attack on hash tables is possible if the collisions are easy to find, as in the case of linear cyclic redundancy check (CRC) functions. Most cryptographic hash functions are designed to take a string of any length as input and produce a fixed-length hash value. A cryptographic hash function must be able to withstand all known types of cryptanalytic attack . In theoretical cryptography,

2070-515: A filtration F t {\displaystyle {\mathcal {F}}_{t}} is that as time t {\displaystyle t} passes, more and more information on X t {\displaystyle X_{t}} is known or available, which is captured in F t {\displaystyle {\mathcal {F}}_{t}} , resulting in finer and finer partitions of Ω {\displaystyle \Omega } . A modification of

2185-532: A fundamental process in queueing theory, the Poisson process is an important process for mathematical models, where it finds applications for models of events randomly occurring in certain time windows. Defined on the real line, the Poisson process can be interpreted as a stochastic process, among other random objects. But then it can be defined on the n {\displaystyle n} -dimensional Euclidean space or other mathematical spaces, where it

2300-425: A given probability space ( Ω , F , P ) {\displaystyle (\Omega ,{\mathcal {F}},P)} and a measurable space ( S , Σ ) {\displaystyle (S,\Sigma )} , a stochastic process is a collection of S {\displaystyle S} -valued random variables, which can be written as: Historically, in many problems from

2415-477: A hash by trying all possible messages in the set. Because cryptographic hash functions are typically designed to be computed quickly, special key derivation functions that require greater computing resources have been developed that make such brute-force attacks more difficult. In some theoretical analyses "difficult" has a specific mathematical meaning, such as "not solvable in asymptotic polynomial time ". Such interpretations of difficulty are important in

SECTION 20

#1732790384584

2530-801: A larger internal state size – which range from tweaks of the Merkle–Damgård construction to new constructions such as the sponge construction and HAIFA construction . None of the entrants in the NIST hash function competition use a classical Merkle–Damgård construction. Meanwhile, truncating the output of a longer hash, such as used in SHA-512/256, also defeats many of these attacks. Hash functions can be used to build other cryptographic primitives . For these other primitives to be cryptographically secure, care must be taken to build them correctly. Message authentication codes (MACs) (also called keyed hash functions) are often built from hash functions. HMAC

2645-454: A massive security breach if the password file is compromised. One way to reduce this danger is to only store the hash digest of each password. To authenticate a user, the password presented by the user is hashed and compared with the stored hash. A password reset method is required when password hashing is performed; original passwords cannot be recalculated from the stored hash value. However, use of standard cryptographic hash functions, such as

2760-516: A number of zero bits. The average work that the sender needs to perform in order to find a valid message is exponential in the number of zero bits required in the hash value, while the recipient can verify the validity of the message by executing a single hash function. For instance, in Hashcash, a sender is asked to generate a header whose 160-bit SHA-1 hash value has the first 20 bits as zeros. The sender will, on average, have to try 2 times to find

2875-405: A particular kind, cryptographic hash functions lend themselves well to this application too. However, compared with standard hash functions, cryptographic hash functions tend to be much more expensive computationally. For this reason, they tend to be used in contexts where it is necessary for users to protect themselves against the possibility of forgery (the creation of data with the same digest as

2990-510: A random element in a function space . The terms stochastic process and random process are used interchangeably, often with no specific mathematical space for the set that indexes the random variables. But often these two terms are used when the random variables are indexed by the integers or an interval of the real line . If the random variables are indexed by the Cartesian plane or some higher-dimensional Euclidean space , then

3105-532: A random walk is known as the simple random walk , which is a stochastic process in discrete time with the integers as the state space, and is based on a Bernoulli process, where each Bernoulli variable takes either the value positive one or negative one. In other words, the simple random walk takes place on the integers, and its value increases by one with probability, say, p {\displaystyle p} , or decreases by one with probability 1 − p {\displaystyle 1-p} , so

3220-472: A sample function that maps the index set T {\displaystyle T} to the state space S {\displaystyle S} . Other names for a sample function of a stochastic process include trajectory , path function or path . An increment of a stochastic process is the difference between two random variables of the same stochastic process. For a stochastic process with an index set that can be interpreted as time, an increment

3335-412: A stationary stochastic process only if the random variables are identically distributed. A stochastic process with the above definition of stationarity is sometimes said to be strictly stationary, but there are other forms of stationarity. One example is when a discrete-time or continuous-time stochastic process X {\displaystyle X} is said to be stationary in the wide sense, then

3450-464: A stochastic process X : Ω → S T {\displaystyle X\colon \Omega \rightarrow S^{T}} defined on the probability space ( Ω , F , P ) {\displaystyle (\Omega ,{\mathcal {F}},P)} , the law of stochastic process X {\displaystyle X} is defined as the image measure : where P {\displaystyle P}

3565-925: A stochastic process has an index set with a total order, then a filtration { F t } t ∈ T {\displaystyle \{{\mathcal {F}}_{t}\}_{t\in T}} , on a probability space ( Ω , F , P ) {\displaystyle (\Omega ,{\mathcal {F}},P)} is a family of sigma-algebras such that F s ⊆ F t ⊆ F {\displaystyle {\mathcal {F}}_{s}\subseteq {\mathcal {F}}_{t}\subseteq {\mathcal {F}}} for all s ≤ t {\displaystyle s\leq t} , where t , s ∈ T {\displaystyle t,s\in T} and ≤ {\displaystyle \leq } denotes

Secure Hash Algorithms - Misplaced Pages Continue

3680-532: A stochastic process is another stochastic process, which is closely related to the original stochastic process. More precisely, a stochastic process X {\displaystyle X} that has the same index set T {\displaystyle T} , state space S {\displaystyle S} , and probability space ( Ω , F , P ) {\displaystyle (\Omega ,{\cal {F}},P)} as another stochastic process Y {\displaystyle Y}

3795-418: A stochastic process is called its state space . This mathematical space can be defined using integers , real lines , n {\displaystyle n} -dimensional Euclidean spaces , complex planes, or more abstract mathematical spaces. The state space is defined using elements that reflect the different values that the stochastic process can take. A sample function is a single outcome of

3910-437: A stochastic process is said to be stationary if its finite-dimensional distributions are invariant under translations of time. This type of stochastic process can be used to describe a physical system that is in steady state, but still experiences random fluctuations. The intuition behind stationarity is that as time passes the distribution of the stationary stochastic process remains the same. A sequence of random variables forms

4025-471: A stochastic process, so it is formed by taking a single possible value of each random variable of the stochastic process. More precisely, if { X ( t , ω ) : t ∈ T } {\displaystyle \{X(t,\omega ):t\in T\}} is a stochastic process, then for any point ω ∈ Ω {\displaystyle \omega \in \Omega } ,

4140-442: A valid header. A message digest can also serve as a means of reliably identifying a file; several source code management systems, including Git , Mercurial and Monotone , use the sha1sum of various types of content (file content, directory trees, ancestry information, etc.) to uniquely identify them. Hashes are used to identify files on peer-to-peer filesharing networks. For example, in an ed2k link , an MD4 -variant hash

4255-540: Is a σ {\displaystyle \sigma } - algebra , and P {\displaystyle P} is a probability measure ; and the random variables, indexed by some set T {\displaystyle T} , all take values in the same mathematical space S {\displaystyle S} , which must be measurable with respect to some σ {\displaystyle \sigma } -algebra Σ {\displaystyle \Sigma } . In other words, for

4370-465: Is a probability measure, the symbol ∘ {\displaystyle \circ } denotes function composition and X − 1 {\displaystyle X^{-1}} is the pre-image of the measurable function or, equivalently, the S T {\displaystyle S^{T}} -valued random variable X {\displaystyle X} , where S T {\displaystyle S^{T}}

4485-442: Is a real number, then the resulting stochastic process is said to have drift μ {\displaystyle \mu } . Almost surely , a sample path of a Wiener process is continuous everywhere but nowhere differentiable . It can be considered as a continuous version of the simple random walk. The process arises as the mathematical limit of other stochastic processes such as certain random walks rescaled, which

4600-440: Is a stationary stochastic process, then for any t ∈ T {\displaystyle t\in T} the random variable X t {\displaystyle X_{t}} has the same distribution, which means that for any set of n {\displaystyle n} index set values t 1 , … , t n {\displaystyle t_{1},\dots ,t_{n}} ,

4715-403: Is actually a function of two variables, t ∈ T {\displaystyle t\in T} and ω ∈ Ω {\displaystyle \omega \in \Omega } . There are other ways to consider a stochastic process, with the above definition being considered the traditional one. For example, a stochastic process can be interpreted or defined as

Secure Hash Algorithms - Misplaced Pages Continue

4830-410: Is also used to refer to a stochastic or random process, though sometimes it is only used when the stochastic process takes real values. This term is also used when the index sets are mathematical spaces other than the real line, while the terms stochastic process and random process are usually used when the index set is interpreted as time, and other terms are used such as random field when

4945-593: Is an abuse of function notation . For example, X ( t ) {\displaystyle X(t)} or X t {\displaystyle X_{t}} are used to refer to the random variable with the index t {\displaystyle t} , and not the entire stochastic process. If the index set is T = [ 0 , ∞ ) {\displaystyle T=[0,\infty )} , then one can write, for example, ( X t , t ≥ 0 ) {\displaystyle (X_{t},t\geq 0)} to denote

5060-427: Is based on a sponge construction, which can also be used to build other cryptographic primitives such as a stream cipher. SHA-3 provides the same output sizes as SHA-2: 224, 256, 384, and 512 bits. Random function In probability theory and related fields, a stochastic ( / s t ə ˈ k æ s t ɪ k / ) or random process is a mathematical object usually defined as a family of random variables in

5175-591: Is based on a substantially modified version of the Advanced Encryption Standard (AES). Whirlpool produces a hash digest of 512 bits (64 bytes). SHA-2 (Secure Hash Algorithm 2) is a set of cryptographic hash functions designed by the United States National Security Agency (NSA), first published in 2001. They are built using the Merkle–Damgård structure, from a one-way compression function itself built using

5290-421: Is called the index set or parameter set of the stochastic process. Often this set is some subset of the real line , such as the natural numbers or an interval, giving the set T {\displaystyle T} the interpretation of time. In addition to these sets, the index set T {\displaystyle T} can be another set with a total order or a more general set, such as

5405-422: Is combined with the file size, providing sufficient information for locating file sources, downloading the file, and verifying its contents. Magnet links are another example. Such file hashes are often the top hash of a hash list or a hash tree , which allows for additional benefits. One of the main applications of a hash function is to allow the fast look-up of data in a hash table . Being hash functions of

5520-423: Is considered to be an important contribution to mathematics and it continues to be an active topic of research for both theoretical reasons and applications. A stochastic or random process can be defined as a collection of random variables that is indexed by some mathematical set, meaning that each random variable of the stochastic process is uniquely associated with an element in the set. The set used to index

5635-412: Is defined as: This measure μ t 1 , . . , t n {\displaystyle \mu _{t_{1},..,t_{n}}} is the joint distribution of the random vector ( X ( t 1 ) , … , X ( t n ) ) {\displaystyle (X({t_{1}}),\dots ,X({t_{n}}))} ; it can be viewed as

5750-508: Is done by first building a cryptographically secure pseudorandom number generator and then using its stream of random bytes as keystream . SEAL is a stream cipher that uses SHA-1 to generate internal tables, which are then used in a keystream generator more or less unrelated to the hash algorithm. SEAL is not guaranteed to be as strong (or weak) as SHA-1. Similarly, the key expansion of the HC-128 and HC-256 stream ciphers makes heavy use of

5865-416: Is given by the extension to the "SHA" name, so SHA-224 has an output size of 224 bits (28 bytes); SHA-256, 32 bytes; SHA-384, 48 bytes; and SHA-512, 64 bytes. SHA-3 (Secure Hash Algorithm 3) was released by NIST on August 5, 2015. SHA-3 is a subset of the broader cryptographic primitive family Keccak. The Keccak algorithm is the work of Guido Bertoni, Joan Daemen, Michael Peeters, and Gilles Van Assche. Keccak

SECTION 50

#1732790384584

5980-802: Is how much the stochastic process changes over a certain time period. For example, if { X ( t ) : t ∈ T } {\displaystyle \{X(t):t\in T\}} is a stochastic process with state space S {\displaystyle S} and index set T = [ 0 , ∞ ) {\displaystyle T=[0,\infty )} , then for any two non-negative numbers t 1 ∈ [ 0 , ∞ ) {\displaystyle t_{1}\in [0,\infty )} and t 2 ∈ [ 0 , ∞ ) {\displaystyle t_{2}\in [0,\infty )} such that t 1 ≤ t 2 {\displaystyle t_{1}\leq t_{2}} ,

6095-484: Is insufficient for many practical uses. In addition to collision resistance, it should be impossible for an adversary to find two messages with substantially similar digests; or to infer any useful information about the data, given only its digest. In particular, a hash function should behave as much as possible like a random function (often called a random oracle in proofs of security) while still being deterministic and efficiently computable. This rules out functions like

6210-434: Is often interpreted as a random set or a random counting measure, instead of a stochastic process. In this setting, the Poisson process, also called the Poisson point process, is one of the most important objects in probability theory, both for applications and theoretical reasons. But it has been remarked that the Poisson process does not receive as much attention as it should, partly due to it often being considered just on

6325-439: Is said to be a modification of X {\displaystyle X} if for all t ∈ T {\displaystyle t\in T} the following holds. Two stochastic processes that are modifications of each other have the same finite-dimensional law and they are said to be stochastically equivalent or equivalent . Instead of modification, the term version is also used, however some authors use

6440-442: Is similar to content-addressable memory . CAS systems work by passing the content of the file through a cryptographic hash function to generate a unique key, the "content address". The file system 's directory stores these addresses and a pointer to the physical storage of the content. Because an attempt to store the same file will generate the same key, CAS systems ensure that the files within them are unique, and because changing

6555-430: Is such a MAC. Just as block ciphers can be used to build hash functions, hash functions can be used to build block ciphers. Luby-Rackoff constructions using hash functions can be provably secure if the underlying hash function is secure. Also, many hash functions (including SHA-1 and SHA-2 ) are built by using a special-purpose block cipher in a Davies–Meyer or other construction. That cipher can also be used in

6670-412: Is the amount that a stochastic process changes between two index values, often interpreted as two points in time. A stochastic process can have many outcomes , due to its randomness, and a single outcome of a stochastic process is called, among other names, a sample function or realization . A stochastic process can be classified in different ways, for example, by its state space, its index set, or

6785-418: Is the real line, and this stochastic process is also called the stationary Poisson process. If the parameter constant of the Poisson process is replaced with some non-negative integrable function of t {\displaystyle t} , the resulting process is called an inhomogeneous or nonhomogeneous Poisson process, where the average density of points of the process is no longer constant. Serving as

6900-446: Is the space of all the possible S {\displaystyle S} -valued functions of t ∈ T {\displaystyle t\in T} , so the law of a stochastic process is a probability measure. For a measurable subset B {\displaystyle B} of S T {\displaystyle S^{T}} , the pre-image of X {\displaystyle X} gives so

7015-436: Is the subject of Donsker's theorem or invariance principle, also known as the functional central limit theorem. The Wiener process is a member of some important families of stochastic processes, including Markov processes, Lévy processes and Gaussian processes. The process also has many applications and is the main stochastic process used in stochastic calculus. It plays a central role in quantitative finance, where it

SECTION 60

#1732790384584

7130-478: Is therefore somewhat dependent on the application since the effort that a malicious agent may put into the task is usually proportional to their expected gain. However, since the needed effort usually multiplies with the digest length, even a thousand-fold advantage in processing power can be neutralized by adding a dozen bits to the latter. For messages selected from a limited set of messages, for example passwords or other short messages, it can be feasible to invert

7245-415: Is traditionally defined as a collection of random variables indexed by some set. The terms random process and stochastic process are considered synonyms and are used interchangeably, without the index set being precisely specified. Both "collection", or "family" are used while instead of "index set", sometimes the terms "parameter set" or "parameter space" are used. The term random function

7360-488: Is used, for example, in the Black–Scholes–Merton model. The process is also used in different fields, including the majority of natural sciences as well as some branches of social sciences, as a mathematical model for various random phenomena. The Poisson process is a stochastic process that has different forms and definitions. It can be defined as a counting process, which is a stochastic process that represents

7475-570: The SHA-256 hash function. Concatenating outputs from multiple hash functions provide collision resistance as good as the strongest of the algorithms included in the concatenated result. For example, older versions of Transport Layer Security (TLS) and Secure Sockets Layer (SSL) used concatenated MD5 and SHA-1 sums. This ensures that a method to find collisions in one of the hash functions does not defeat data protected by both hash functions. For Merkle–Damgård construction hash functions,

7590-483: The SWIFFT function, which can be rigorously proven to be collision-resistant assuming that certain problems on ideal lattices are computationally difficult, but, as a linear function, does not satisfy these additional properties. Checksum algorithms, such as CRC32 and other cyclic redundancy checks , are designed to meet much weaker requirements and are generally unsuitable as cryptographic hash functions. For example,

7705-475: The mapping is called a sample function, a realization , or, particularly when T {\displaystyle T} is interpreted as time, a sample path of the stochastic process { X ( t , ω ) : t ∈ T } {\displaystyle \{X(t,\omega ):t\in T\}} . This means that for a fixed ω ∈ Ω {\displaystyle \omega \in \Omega } , there exists

7820-521: The shattered attack and the hash function should be considered broken. SHA-1 produces a hash digest of 160 bits (20 bytes). Documents may refer to SHA-1 as just "SHA", even though this may conflict with the other Secure Hash Algorithms such as SHA-0, SHA-2, and SHA-3. RIPEMD (RACE Integrity Primitives Evaluation Message Digest) is a family of cryptographic hash functions developed in Leuven, Belgium, by Hans Dobbertin, Antoon Bosselaers, and Bart Preneel at

7935-655: The COSIC research group at the Katholieke Universiteit Leuven, and first published in 1996. RIPEMD was based upon the design principles used in MD4 and is similar in performance to the more popular SHA-1. RIPEMD-160 has, however, not been broken. As the name implies, RIPEMD-160 produces a hash digest of 160 bits (20 bytes). Whirlpool is a cryptographic hash function designed by Vincent Rijmen and Paulo S. L. M. Barreto, who first described it in 2000. Whirlpool

8050-543: The Cartesian plane R 2 {\displaystyle \mathbb {R} ^{2}} or n {\displaystyle n} -dimensional Euclidean space, where an element t ∈ T {\displaystyle t\in T} can represent a point in space. That said, many results and theorems are only possible for stochastic processes with a totally ordered index set. The mathematical space S {\displaystyle S} of

8165-504: The Davies–Meyer structure from a (classified) specialized block cipher. SHA-2 basically consists of two hash algorithms: SHA-256 and SHA-512. SHA-224 is a variant of SHA-256 with different starting values and truncated output. SHA-384 and the lesser-known SHA-512/224 and SHA-512/256 are all variants of SHA-512. SHA-512 is more secure than SHA-256 and is commonly faster than SHA-256 on 64-bit machines such as AMD64 . The output size in bits

8280-564: The German term had been used earlier, for example, by Andrei Kolmogorov in 1931. According to the Oxford English Dictionary, early occurrences of the word random in English with its current meaning, which relates to chance or luck, date back to the 16th century, while earlier recorded usages started in the 14th century as a noun meaning "impetuosity, great speed, force, or violence (in riding, running, striking, etc.)". The word itself comes from

8395-428: The Merkle–Damgård construction, where the size of hash output is equal to the internal state size (between each compression step), results in a narrow-pipe hash design. This design causes many inherent flaws, including length-extension , multicollisions, long message attacks, generate-and-paste attacks, and also cannot be parallelized. As a result, modern hash functions are built on wide-pipe constructions that have

8510-488: The SHA series, is no longer considered safe for password storage. These algorithms are designed to be computed quickly, so if the hashed values are compromised, it is possible to try guessed passwords at high rates. Common graphics processing units can try billions of possible passwords each second. Password hash functions that perform key stretching – such as PBKDF2 , scrypt or Argon2 – commonly use repeated invocations of

8625-1621: The Secure Hash Standard (SHS). In the table below, internal state means the "internal hash sum" after each compression of a data block. All SHA-family algorithms, as FIPS-approved security functions, are subject to official validation by the CMVP (Cryptographic Module Validation Program), a joint program run by the American National Institute of Standards and Technology (NIST) and the Canadian Communications Security Establishment (CSE). Cryptographic hash function Cryptographic hash functions have many information-security applications, notably in digital signatures , message authentication codes (MACs), and other forms of authentication . They can also be used as ordinary hash functions , to index data in hash tables , for fingerprinting , to detect duplicate data or uniquely identify files, and as checksums to detect accidental data corruption. Indeed, in information-security contexts, cryptographic hash values are sometimes called ( digital ) fingerprints , checksums , or just hash values , even though all these terms stand for more general functions with rather different properties and purposes. Non-cryptographic hash functions are used in hash tables and to detect accidental errors; their constructions frequently provide no resistance to

8740-525: The algorithm was published in 1993 under the title Secure Hash Standard, FIPS PUB 180, by U.S. government standards agency NIST (National Institute of Standards and Technology). It was withdrawn by the NSA shortly after publication and was superseded by the revised version, published in 1995 in FIPS ; PUB 180-1 and commonly designated SHA-1. Collisions against the full SHA-1 algorithm can be produced using

8855-802: The collection of random variables is usually called a random field instead. The values of a stochastic process are not always numbers and can be vectors or other mathematical objects. Based on their mathematical properties, stochastic processes can be grouped into various categories, which include random walks , martingales , Markov processes , Lévy processes , Gaussian processes , random fields, renewal processes , and branching processes . The study of stochastic processes uses mathematical knowledge and techniques from probability , calculus , linear algebra , set theory , and topology as well as branches of mathematical analysis such as real analysis , measure theory , Fourier analysis , and functional analysis . The theory of stochastic processes

8970-409: The concatenated function is as collision-resistant as its strongest component, but not more collision-resistant. Antoine Joux observed that 2-collisions lead to n -collisions: if it is feasible for an attacker to find two messages with the same MD5 hash, then they can find as many additional messages with that same MD5 hash as they desire, with no greater difficulty. Among those n messages with

9085-484: The corresponding n {\displaystyle n} random variables all have the same probability distribution . The index set of a stationary stochastic process is usually interpreted as time, so it can be the integers or the real line. But the concept of stationarity also exists for point processes and random fields, where the index set is not interpreted as time. When the index set T {\displaystyle T} can be interpreted as time,

9200-566: The definition "pertaining to conjecturing", and stemming from a Greek word meaning "to aim at a mark, guess", and the Oxford English Dictionary gives the year 1662 as its earliest occurrence. In his work on probability Ars Conjectandi , originally published in Latin in 1713, Jakob Bernoulli used the phrase "Ars Conjectandi sive Stochastice", which has been translated to "the art of conjecturing or stochastics". This phrase

9315-402: The dependence among the random variables. One common way of classification is by the cardinality of the index set and the state space. When interpreted as time, if the index set of a stochastic process has a finite or countable number of elements, such as a finite set of numbers, the set of integers, or the natural numbers, then the stochastic process is said to be in discrete time . If

9430-535: The difference X t 2 − X t 1 {\displaystyle X_{t_{2}}-X_{t_{1}}} is a S {\displaystyle S} -valued random variable known as an increment. When interested in the increments, often the state space S {\displaystyle S} is the real line or the natural numbers, but it can be n {\displaystyle n} -dimensional Euclidean space or more abstract spaces such as Banach spaces . For

9545-442: The expected data) by potentially malicious participants. Content-addressable storage (CAS), also referred to as content-addressed storage or fixed-content storage, is a way to store information so it can be retrieved based on its content, not its name or location. It has been used for high-speed storage and retrieval of fixed content, such as documents stored for compliance with government regulations . Content-addressable storage

9660-597: The extensive use of stochastic processes in finance . Applications and the study of phenomena have in turn inspired the proposal of new stochastic processes. Examples of such stochastic processes include the Wiener process or Brownian motion process, used by Louis Bachelier to study price changes on the Paris Bourse , and the Poisson process , used by A. K. Erlang to study the number of phone calls occurring in

9775-455: The file will result in a new key, CAS systems provide assurance that the file is unchanged. There are several methods to use a block cipher to build a cryptographic hash function, specifically a one-way compression function . The methods resemble the block cipher modes of operation usually used for encryption. Many well-known hash functions, including MD4 , MD5 , SHA-1 and SHA-2 , are built from block-cipher-like components designed for

9890-476: The finite-dimensional distributions of a stochastic process X {\displaystyle X} can be written as: The finite-dimensional distributions of a stochastic process satisfy two mathematical conditions known as consistency conditions. Stationarity is a mathematical property that a stochastic process has when all the random variables of that stochastic process are identically distributed. In other words, if X {\displaystyle X}

10005-461: The hashes are posted on a trusted site – usually the originating site – authenticated by HTTPS . Using a cryptographic hash and a chain of trust detects malicious changes to the file. Non-cryptographic error-detecting codes such as cyclic redundancy checks only prevent against non-malicious alterations of the file, since an intentional spoof can readily be crafted to have the colliding code value. Almost all digital signature schemes require

10120-430: The index set being uncountable. If the index set is the integers, or some subset of them, then the stochastic process can also be called a random sequence . If the state space is the integers or natural numbers, then the stochastic process is called a discrete or integer-valued stochastic process . If the state space is the real line, then the stochastic process is referred to as a real-valued stochastic process or

10235-812: The index set is n {\displaystyle n} -dimensional Euclidean space R n {\displaystyle \mathbb {R} ^{n}} or a manifold . A stochastic process can be denoted, among other ways, by { X ( t ) } t ∈ T {\displaystyle \{X(t)\}_{t\in T}} , { X t } t ∈ T {\displaystyle \{X_{t}\}_{t\in T}} , { X t } {\displaystyle \{X_{t}\}} { X ( t ) } {\displaystyle \{X(t)\}} or simply as X {\displaystyle X} . Some authors mistakenly write X ( t ) {\displaystyle X(t)} even though it

10350-404: The index set is some interval of the real line, then time is said to be continuous . The two types of stochastic processes are respectively referred to as discrete-time and continuous-time stochastic processes . Discrete-time stochastic processes are considered easier to study because continuous-time processes require more advanced mathematical techniques and knowledge, particularly due to

10465-474: The index set of this random walk is the natural numbers, while its state space is the integers. If p = 0.5 {\displaystyle p=0.5} , this random walk is called a symmetric random walk. The Wiener process is a stochastic process with stationary and independent increments that are normally distributed based on the size of the increments. The Wiener process is named after Norbert Wiener , who proved its mathematical existence, but

10580-475: The key changes each block; and related-key attacks make it potentially less secure for use in a hash function than for encryption. A hash function must be able to process an arbitrary-length message into a fixed-length output. This can be achieved by breaking the input up into a series of equally sized blocks, and operating on them in sequence using a one-way compression function . The compression function can either be specially designed for hashing or be built from

10695-541: The law of a X {\displaystyle X} can be written as: The law of a stochastic process or a random variable is also called the probability law , probability distribution , or the distribution . For a stochastic process X {\displaystyle X} with law μ {\displaystyle \mu } , its finite-dimensional distribution for t 1 , … , t n ∈ T {\displaystyle t_{1},\dots ,t_{n}\in T}

10810-400: The message) calculated before, and after, transmission can determine whether any changes have been made to the message or file . MD5 , SHA-1 , or SHA-2 hash digests are sometimes published on websites or forums to allow verification of integrity for downloaded files, including files retrieved using file sharing such as mirroring . This practice establishes a chain of trust as long as

10925-498: The natural sciences a point t ∈ T {\displaystyle t\in T} had the meaning of time, so X ( t ) {\displaystyle X(t)} is a random variable representing a value observed at time t {\displaystyle t} . A stochastic process can also be written as { X ( t , ω ) : t ∈ T } {\displaystyle \{X(t,\omega ):t\in T\}} to reflect that it

11040-416: The password hash digest can be compared or to test a large number of purloined hash values in parallel. A proof-of-work system (or protocol, or function) is an economic measure to deter denial-of-service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer. A key feature of these schemes is their asymmetry:

11155-525: The process X {\displaystyle X} has a finite second moment for all t ∈ T {\displaystyle t\in T} and the covariance of the two random variables X t {\displaystyle X_{t}} and X t + h {\displaystyle X_{t+h}} depends only on the number h {\displaystyle h} for all t ∈ T {\displaystyle t\in T} . Khinchin introduced

11270-446: The process can be defined more generally so its state space can be n {\displaystyle n} -dimensional Euclidean space. If the mean of any increment is zero, then the resulting Wiener or Brownian motion process is said to have zero drift. If the mean of the increment for any two points in time is equal to the time difference multiplied by some constant μ {\displaystyle \mu } , which

11385-620: The process is also called the Brownian motion process or just Brownian motion due to its historical connection as a model for Brownian movement in liquids. Playing a central role in the theory of probability, the Wiener process is often considered the most important and studied stochastic process, with connections to other stochastic processes. Its index set and state space are the non-negative numbers and real numbers, respectively, so it has both continuous index set and states space. But

11500-976: The purpose, with feedback to ensure that the resulting function is not invertible. SHA-3 finalists included functions with block-cipher-like components (e.g., Skein , BLAKE ) though the function finally selected, Keccak , was built on a cryptographic sponge instead. A standard block cipher such as AES can be used in place of these custom block ciphers; that might be useful when an embedded system needs to implement both encryption and hashing with minimal code size or hardware area. However, that approach can have costs in efficiency and security. The ciphers in hash functions are built for hashing: they use large keys and blocks, can efficiently change keys every block, and have been designed and vetted for resistance to related-key attacks . General-purpose ciphers tend to have different design goals. In particular, AES has key and block sizes that make it nontrivial to use to generate long hash values; AES encryption becomes less efficient when

11615-433: The random number of points or events up to some time. The number of points of the process that are located in the interval from zero to some given time is a Poisson random variable that depends on that time and some parameter. This process has the natural numbers as its state space and the non-negative numbers as its index set. This process is also called the Poisson counting process, since it can be interpreted as an example of

11730-469: The random variables is called the index set . Historically, the index set was some subset of the real line , such as the natural numbers , giving the index set the interpretation of time. Each random variable in the collection takes values from the same mathematical space known as the state space . This state space can be, for example, the integers, the real line or n {\displaystyle n} -dimensional Euclidean space. An increment

11845-428: The real line, and not on other mathematical spaces. A stochastic process is defined as a collection of random variables defined on a common probability space ( Ω , F , P ) {\displaystyle (\Omega ,{\mathcal {F}},P)} , where Ω {\displaystyle \Omega } is a sample space , F {\displaystyle {\mathcal {F}}}

11960-410: The related concept of stationarity in the wide sense , which has other names including covariance stationarity or stationarity in the broad sense . A filtration is an increasing sequence of sigma-algebras defined in relation to some probability space and an index set that has some total order relation, such as in the case of the index set being some subset of the real numbers. More formally, if

12075-479: The same MD5 hash, there is likely to be a collision in SHA-1. The additional work needed to find the SHA-1 collision (beyond the exponential birthday search) requires only polynomial time . There are many cryptographic hash algorithms; this section lists a few algorithms that are referenced relatively often. A more extensive list can be found on the page containing a comparison of cryptographic hash functions . MD5

12190-527: The same hash. A function meeting these criteria may still have undesirable properties. Currently, popular cryptographic hash functions are vulnerable to length-extension attacks : given hash( m ) and len( m ) but not m , by choosing a suitable m ′ an attacker can calculate hash( m ∥ m ′ ) , where ∥ denotes concatenation . This property can be used to break naive authentication schemes based on hash functions. The HMAC construction works around these problems. In practice, collision resistance

12305-465: The security level of a cryptographic hash function has been defined using the following properties: Collision resistance implies second pre-image resistance but does not imply pre-image resistance. The weaker assumption is always preferred in theoretical cryptography, but in practice, a hash-function that is only second pre-image resistant is considered insecure and is therefore not recommended for real applications. Informally, these properties mean that

12420-461: The solution earlier by revealing it and having Bob hash it and check that it matches the hash value given to him before. (This is an example of a simple commitment scheme ; in actual practice, Alice and Bob will often be computer programs, and the secret would be something less easily spoofed than a claimed puzzle solution.) An important application of secure hashes is the verification of message integrity . Comparing message digests (hash digests over

12535-537: The stochastic process. One of the simplest stochastic processes is the Bernoulli process , which is a sequence of independent and identically distributed (iid) random variables, where each random variable takes either the value one or zero, say one with probability p {\displaystyle p} and zero with probability 1 − p {\displaystyle 1-p} . This process can be linked to an idealisation of repeatedly flipping

12650-414: The study of provably secure cryptographic hash functions but do not usually have a strong connection to practical security. For example, an exponential-time algorithm can sometimes still be fast enough to make a feasible attack. Conversely, a polynomial-time algorithm (e.g., one that requires n steps for n -digit keys) may be too slow for any practical use. An illustration of the potential use of

12765-441: The term to refer to processes that change in continuous time, particularly the Wiener process used in financial models, which has led to some confusion, resulting in its criticism. There are various other types of random walks, defined so their state spaces can be other mathematical objects, such as lattices and groups, and in general they are highly studied and have many applications in different disciplines. A classic example of

12880-437: The total order of the index set T {\displaystyle T} . With the concept of a filtration, it is possible to study the amount of information contained in a stochastic process X t {\displaystyle X_{t}} at t ∈ T {\displaystyle t\in T} , which can be interpreted as time t {\displaystyle t} . The intuition behind

12995-508: The work must be moderately hard (but feasible) on the requester side but easy to check for the service provider. One popular system – used in Bitcoin mining and Hashcash – uses partial hash inversions to prove that work was done, to unlock a mining reward in Bitcoin, and as a good-will token to send an e-mail in Hashcash. The sender is required to find a message whose hash value begins with

13110-454: Was designed by Ronald Rivest in 1991 to replace an earlier hash function, MD4, and was specified in 1992 as RFC 1321. Collisions against MD5 can be calculated within seconds, which makes the algorithm unsuitable for most use cases where a cryptographic hash is required. MD5 produces a digest of 128 bits (16 bytes). SHA-1 was developed as part of the U.S. Government's Capstone project. The original specification – now commonly called SHA-0 – of

13225-412: Was used, with reference to Bernoulli, by Ladislaus Bortkiewicz who in 1917 wrote in German the word stochastik with a sense meaning random. The term stochastic process first appeared in English in a 1934 paper by Joseph Doob . For the term and a specific mathematical definition, Doob cited another 1934 paper, where the term stochastischer Prozeß was used in German by Aleksandr Khinchin , though

#583416