69
Data integrity is another usage. For example, when you want to send/download data, you want to make sure that the data is not modified or transmitted/downloaded correctly. To achieve this the data hashed and the hash value sent/downloaded on another channel. One may see examples of this file verification on Linux ISO download pages. Of course, hashing is not ...
33
No, it is not a good idea to hash phone numbers. There are only a limited number of phone numbers, so it is pretty easy for an adversary to try and hash all of them. Then you can simply compare the hash of each with the stored hash. Generally you don't have to deal with all telephone numbers, only a subsection of phone numbers anyway (for a specific country ...
28
Applications for one-way-functions in cryptography
Hash-collisions may happen in rare cases, but are mostly disregarded here.
Data integrity
Integrity
A quick way to ensure integrity of data is to compare two hashes, where one is a previously calculated hash and the other is the newly calculated hash of the data, which is presumed to be unmodified. If the ...
26
A trapdoor function is a function that is easy to perform one way, but has a secret that is required to perform the inverse calculation efficiently. That is, if $f$ is a trapdoor function, then $y = f(x)$ is easy to compute, but $x = f^{-1}(y)$ is hard to compute without some special knowledge $k$. Given $k$, then it is easy to compute $y = f^{-1}(x, k)$. ...
22
The main fundamental issue with this approach, as with approaches that attempt to base cryptography on NP-completeness, is that the hardness you refer to is worst case hardness, and not average case hardness. In particular, the fact that the halting problem is hard merely means that for every algorithm there exists a TM $M$ for with the algorithm fails upon. ...
14
I'm also afraid you couldn't understand this as D.W., but let us start.
I sometimes cannot understand your questions. Please restate them, if possible.
The definition of the Ajtai hash functions
Let $n$, $m$, and $q$ be positive integers.
Let $R = \mathbb{Z}_q$ be the quotient ring of integers modulo $q$.
Let us define a function, which maps a vector in $D^...
14
While poncho's answer gives an interesting example, why this can go wrong in practice, it does not necessarily answer the question from a theoretical point of view.
After all, we don't know whether $f(x) = AES_k(x) \oplus x$ is one-way. (Even if it might be reasonable to assume that.)
So, let's give a theoretical example.
Assume that a one-way function $h$ ...
14
It is easier to prove that $P = \mathit{NP}$ implies one-way functions do not exist:
Let $P = \mathit{NP}$, and assume $f$ is one-way. Then consider the language $L$ of pairs $(x^\ast, y)$ such that $x^\ast$ is a prefix of some $x$ satisfying $f(x) = y$. $L$ is in $\mathit{NP}$ because $x$ itself is a witness (up to minor formal details; see this question ...
13
The function $f$ introduced by Maeher in this answer to a related question should also do the job here (as both $g$ and $h$). For convenience, let me quote that answer here:
Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$
...
13
Simon [Sim98] showed that is not possible to build a collision-resistant hash function from a one-way permutation (which is a stronger statement) in a black-box manner .
The main idea is to use the so-called oracle-separation technique. You can read more about it either here or in this survey.
[Sim98]: Daniel Simon. Finding collisions on a one-way ...
12
It is always a bad idea to hash data that has a limited set of length or characters.
A phone number in Germany for example has normally no more than 12 digits.
The first digit is always a 0 and the vast majority of numbers is longer as 3 digits, as those are normally reserved for emergency services.
This effectively leaves us with 10^11-10^3 possible ...
12
In the general sense, The problem is known as the small input space on the hash functions, and in short simple hashing won't be secure.
If you hash data ( here a phone number) and an attacker tries to find an input value that matches the hash value is called the pre-image attack. In a secure Cryptographic hash functions pre-image attack requires $\mathcal{O}(...
10
ChaCha builds on a 512 bit permutation and then applies a feed-forward by xoring the input into the output. Without truncation, that feed forward is essential for one-way-ness.
We're going to build a one-way function that maps a 32 byte value x to another 32 byte value y.
Using truncated ChaCha including the feed-forward
Put the x into the 32 key part of ...
10
It is going to be pretty hard to achieve collision resistance without one-wayness. Indeed, negation of one-wayness means that for a given output, you can find a corresponding input. So a collision is easily obtained by simply choosing a random input m, hashing it into output x, then finding a preimage m' for the obtained output x. The only way for such a ...
9
This requirement is a killer:
The paper (or any medium other than the brain) must not at any time contain data that leaks information about the plaintext.
Almost any security proof for a hash assumes an adversary only gets to see digests, not any mid-state. Mid-state has not had enough confusion and diffusion, so it leaks information.
This means that ...
9
Factoring $\longrightarrow$ square roots.
Computing square roots modulo a prime $p$ is easy: if $p \equiv 3 \pmod 4$ and $a$ is a quadratic residue modulo $p$, then $a^{(p + 1)/4}$ is a square root of $a$ modulo $p$; for $p \equiv 1 \pmod 4$, you can use Cipolla or Tonelli–Shanks.
Computing square roots modulo a composite of known prime factorization is ...
9
This is very confusing because it seems as it should be something really easy to prove. However, it actually is not, and in fact the proof uses the Borel-Cantelli lemma. Anyway, it was formally proven by Rudich and Impagliazzo in their groundbreaking work on black-box separations. You can find a formal proof in Rudich's thesis, Section 6.2, or in the paper ...
9
If a permutation $f$ is not one way, we can not conclude about the one-wayness of $f^{p(n)}$. In fact, even $f^2$ could be one-way, if there are one-way length-preserving permutations that is.
Constructive proof: assume $g:\{0,1\}^*\rightarrow \{0,1\}^*$ is a length-preserving OWP, not invertible starting with rank $m$. Define $f$ from $g$ such that, for ...
8
An advantage of a cryptographic accumulator and actually the reason to use them is that due to the quasi commutativity you can compute witnesses for
membership of values in the accumulator where the accumulator and the witnesses are of constant size.
Say you
have a set $Y=\{y_1,y_2,y_3\}$ and compute the accumulator as $acc=f(f(f(x,y_1),y_2),y_3)$ you ...
8
No, it is not collision-free. All possible sequences of 0's produce the same output:
0 --> (2 ** 0) = 1
00 --> (2 ** 0) * (3 ** 0) = 1
000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) = 1
0000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1
In fact, it can be seen that $f(s) = f(s||0)$, for every bit-string $s$.
This could be easily solved by ...
8
There are a variety of ways to construct a hash function. The two you will probably hear about the most are the Merkle–Damgård construction and the sponge function. The former is an older construction(dated 1979), and suffers from length extension attacks. New hashes might opt for the sponge construction, as it is immune to that particular attack.
As for how ...
8
You'll find it in any textbook on basics of cryptography, for example Foundations of Cryptography by Goldreich. I have added a figure which sums up the relationship between the primitives: arrow represent reductions (i.e. $A\rightarrow B$ means that primitive $B$ can be constructed in a black-box manner from primitive $A$) and dashed arrows represent ...
8
Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).
However, this is really a minor issue: the answers to this question that you read ...
8
Yes, you are looking for the notion of a universal one-way function.
Rafael Pass/abhi shelat's notes contain a construction on page 49. The construction is "unnatural" in the sense that it involves parsing the input to the OWF $y$ as a pair $\langle M\rangle || x$, where $\langle M\rangle$ is interpreted as the description of a Turing machine. Then ...
7
This is probably not secure enough for a proof of work. I'll outline some attacks, of increasing sophistication/complexity and increasing effectiveness (decreasing runtime).
Brute force
The obvious attack is brute force: enumerate all $2^{32}$ possible inputs and check to find the first that produces the desired output. This takes $2^{32}$ time. I'm ...
7
This is highly insecure, for the same reason that ECB mode and simple substitution ciphers are. Every time you use the word the in your message, it will be encrypted the same way. The same goes for other, lower-frequency (but still fairly common) words -- like as or with or will (or any of hundreds of other examples).
This is a humongous clue to ...
7
Your scheme would make a nice puzzle for amateur codebreakers. That's about the best that can be said for it.
It does not meet the generally accepted standards for a modern encryption scheme; in particular, it is not semantically secure. In fact, the security of your scheme would be seriously compromised if an attacker obtained even a small amount of ...
7
No, you can find $f$ such that $f(x)$ is a OWF, but $f(x)\oplus x$ is not.
One example would be $f(x) = AES_k(x) \oplus x$ (for a public key $k$, perhaps the all-zeros key). $f(x)$ is believed to be one way; as there is no known practical way, given a value $y$, to find an $x$ with $f(x) = y$. However, $g(x) = f(x) \oplus x = AES_k(x)$ is easy to invert (...
7
Security is clearly broken if there is a polynomial-length period with non-negligible probability (where by this I mean if a random point falls in a cycle with a poly-length period with non-negligible probability). In order to find a preimage, just go forward until you get back to the starting point, keeping the previous value each time.
Only top voted, non community-wiki answers of a minimum length are eligible