We’re rewarding the question askers & reputations are being recalculated! Read more.
36

Preimage resistance is about the most basic property of a hash function which can be thought. It means: For a given $h$ in the output space of the hash function, it is hard to find any message $x$ with $H(x) = h$. (Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash ...


22

Modern security has moved beyond looking just at passive attacks (in which the attacker is just a passive eavesdropper seeking to learn what was said); attackers are generally considered to be able and willing to pull off active attacks of various types (in which the attacker can modify or forge messages to achieve some goal). One-time pads are extremely ...


21

If you sample a random element, then you sample it according to some distribution. Uniformly then means that you sample from the uniform distribution, i.e., you sample it from a set where drawing each element is equally probable. Let us assume you have a set of 4 elements, then sampling uniformly at random from this set, every element is drawn with ...


20

AES is deemed secure because: Its building blocks and design principles are fully specified. It was selected as part of an open competition. It has sustained 15 years of attempted cryptanalysis from many smart people, in a high-exposure situation, and it came out relatively unscathed. Another reason, which is not as good but felt important by many people: ...


20

Perfect Secrecy (or information-theoretic secure) means that the ciphertext conveys no information about the content of the plaintext. In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is ...


19

(Notation. Sets are represented using the calligraphic font and algorithms using the straight font. Throughout, $\Sigma:=(\mathsf{K},\mathsf{S},\mathsf{V})$ denotes a signature scheme on a key-space $\mathcal{K}$, message-space $\mathcal{M}$ and signature-space $\mathcal{S}$. Since only a single key-pair is involved in the discussion, to avoid cluttering, ...


18

It fails to be a cryptographically-strong PRNG because it is predictable: given some outputs, you can predict the next outputs. For instance, if you observe the outputs at offsets 0, 1, and 4096, you can predict what the output will be at offset 4097. What it's missing: it's not that it's missing some little tweak (just change line 7 to use addition ...


16

Randomness is not a property of strings of bits (or characters of any sort). Rather it is a property of the process that generates those strings. However, it is convenient to conflate the string with the thing that produced the string, and thus to speak about strings being “random” or “not random”. The string 00000, for example, is random if it was the ...


15

That's not the same kind of key. Symmetric keys are bunch of bits, such that any sequence of bits of the right size is a possible keys. Such keys are subject to brute force attacks, with cost $2^n$ for a $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is "perfect" then enumerating all ...


15

Reductionist security In a reductionist security proof for some cryptographic protocol $\Pi$ to some alleged hard problem $P$ means, that we can build an algorithm $\cal B$ for solving $P$ if we have access to a hypothetical algorithm $\cal A$ that efficiently breaks the security definition for the protocol $\Pi$. In general, showing a polynomial time ...


15

A three-round Feistel network is a good example of a realistic construction that is a secure "weak" PRP, but not a "strong" PRP. A Feistel network uses the permutation $P_f(L, R) = R, (L\oplus f(R))$, where $f$ is an element of a pseudorandom function family. This PRP will be keyed with three keys $k_1, k_2, k_3$, which will be used to key a PRF $F$ ...


13

Negligible is a human term, not a precise definition. It refers to things which are sufficiently small that one is willing to ignore it in the interests of expediency. The threshold varies from person to person: a NSA mathematician will have a different threshold for a property than a CEO of a startup will). It also varies from topic to topic: $2^{-64}$ ...


12

Kerckhoffs's principle: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge. The principle does not state that it is unconditionally unacceptable to keep your algorithm or system a secret. (This answer provides an image of the original text Kerckhoffs used.) Just keeping the used algorithm a secret is ...


10

The classic standard assumptions (such as DDH, CDH) are not parametrized and always have constant size (are static). Consequently, the assumption when used in a reductionist proof is independent of any system parameters or oracle queries and only related to the security parameter. In contrast, non-static ($q$-type) assumptions as already mentioned by ...


10

According to the references, AES-GCM offers roughly 64-bit authenticity security (i.e., against forgery attacks) for 128-bit block size and long-enough (>=64-bit) tag size. When the number of queries appears in a security bound, "online" security should always be the case (for the bound items involving the number of queries). The word "query" corresponds to ...


9

The two primary techniques I'm familiar with is structuring a cryptographic primitive as a sequence of games and the universally composable security framework. Sequence of Games The idea here is to represent a protocol/primitive as a game played between an attacker and a challenger. You define a bad event and show through the game that the event happens ...


9

The notation $1^\lambda$ means a string with $\lambda$ characters all of them equal to 1. For instance, if $\lambda = 3$, then $1^\lambda$ is $111$. And yes, it typically stands to the security parameter, from which the probability of "breaking" the system is measured (as well as the resources needed to do so and also to execute the cryptosystem's ...


8

A collision attack is the ability to find two inputs that produce the same result, but that result is not known ahead of time. In a typical case (e.g., the attack on MD5) only a relatively small number of specific inputs are known to produce collisions. Collision resistance obviously means that a collision attack is difficult (for some definition of "...


8

An algorithm being probabilistic means that it is allowed to "throw coins", and use the results of the coin throws in its computations. This is reasonable because a realistic adversary has access to certain pseudo-randomness sources (such as the C rand() function). Of course, a probabilistic algorithm is not required to use its randomness source (i.e., throw ...


8

This lecture (PDF) has the solution in section 3. Here's my informal explanation of the proof: We have an unpredictable PRG $G$. We want to show that $G$ is secure, or in other words indistinguishable from $R$ (I'll use = to mean indistinguishable whenever referring to two distributions for the remainder of the proof). Using the notation that $G_k R_{n-...


8

The paper says that the parameters are $r ≈ 2^{\sqrt \eta}$ and $q ≈ 2^{\eta^3}$. Note that these values are expressed as functions of $\eta$, not $N$. With regard to the parameters, it is common practice to describe them using the asymptotic notation. $\omega(\cdot), \Theta(\cdot)$ and $\tilde O(\cdot)$ are instances of this notation. $\omega(g(n))$ ...


8

The TL;DR: From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness; In practice, most of the time you can replace Gaussians by other distributions without too much trouble. Theory First, let me elaborate on a few reasons why Gaussians are better in theory: When ...


8

Does this mean that the standard definitions for DDH, RSA or QR do no hold in that setting, because the definitions assume some bounds on the computational power of the adversary? That is correct; a computationally unbounded adversary could trivially solve any of these problems. For example, to solve the DDH problem ("given, $g, g^x, g^y, g^z$, does $g^{xy}...


7

Does anyone have a reliable source for this? Well, you are asking about the definition of a CSPRNG, and whether this second criteria is a necessary part. Well, it comes down the to exact definition of the term 'CSPRNG'. If we define a CSPRNG as something that generates output which is indistinguishable from random (your first criteria), then a CSPRNG ...


7

Randomness is the information loss of any causal relationship between events. The universe needn't be a clockwork universe for the assumption of pervasive causality - if events are "sticky" and accrue localised causality in the same way that a molecular cloud accretes into stars and planets. The underlying cause of the speed of light might also be the prime ...


7

Quoting the obvious (Wikipedia article about the term “security parameter”.) In cryptography, the security parameter is a variable that measures the input size of the computational problem. Both the resource requirements of the cryptographic algorithm or protocol as well as the adversary's probability of breaking security are expressed in terms of the ...


7

"It should not require secrecy, and it should not be a problem if it falls into enemy hands" Where "it" is the algorithm design itself, and not an input to it... But isn't the practice of security through obscurity still violating Kerckhoffs's second principle per definition? Yes. Obscurity is hardly a defense that demands prohibitive computational ...


7

The phrase ‘128-bit security’ is a bit glib to cover the online/offline distinction—the purpose of the explicit formulas is to quantify the forgery probability in terms of limits on the online and offline costs. The online costs depend on how scalable your application is; the offline costs depend only on how much the adversary is willing to pay to break ...


7

A company can make more money if the printers it sells only work with the cartridges they sell, which does not work if there is competition. It's cheaper to force a vendor lock-in than it is to innovate and ensure that your product holds up to the competition. All the printer's authentication does is prevent you from using cartridges made by other companies. ...


6

Often the hash (iterated and salted mostly) of a password is saved in a database, instead of the password. If a user logs in, the hash is computed and compared against the stored hash value. This way a user that can see the database of hashes does not see the password directly, but this property depends crucially on the hash being resistant to a pre-image ...


Only top voted, non community-wiki answers of a minimum length are eligible