Tag Info

11

In the Lecture Notes on Cryptography of Goldwasser and Bellare, one can find (page 35) the following text: Recall that f(x) does not necessarily hide everything about x even if f is a one-way function. E.g. if f is the RSA function then it preserves the Jacobi symbol of x, and if f is the discrete logarithm function EXP then it is easy to compute the ...

10

Sure. If you want a $b$-bit hash of the message $m$, then use the first $b$ bits of AES-CTR(SHA256($m$)). That'll do the trick. In other words, compute SHA256($m$) and treat the resulting 256-bit string as a 256-bit AES key. Next, use AES in counter mode (with this key) to generate an unending stream of pseudorandom bits. Take the first $b$ bits from ...

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 ...

8

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)$. ...

8

In general, each combination of a (secure) hash function for input with a (deterministic) pseudo random number generator for output will work here - one "state of the art" example is the one given by D.W. (using AES-CTR as PRNG and SHA-256 as hash). Another way is similar to what PBKDF-2 does to have output with the right length: hash the input (or a hash ...

7

As D.W. notes, you can use the output of any conventional hash function to key a stream cipher (or a block cipher in a streaming mode like CTR), and then take the output of the cipher as your digest. However, there has been a trend in modern hash function design to support arbitrary-length output directly, without the need for additional layers. For ...

7

It sounds like you're looking for a proof-of-work system. One way to implement such a system would be, given a message $m$, to ask for a suffix $s$ such that the hash $H(m \operatorname{\|} s)$, where $H$ is some standard cryptographic hash function and $\|$ denotes concatenation, begins with a specific prefix (e.g. $n$ zero bits). Of course, the execution ...

7

There are techniques for doing online surveys on sensitive subjects. They don't follow the approach you outlined, but here's a sketch of how they work. Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated ...

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 ...

6

I still don't understand your desire for a hash, especially considering (as already stated at other places in this forum) that you don't gain any entropy by subjecting a PW to a deterministic function like a hash. So, when decrypting your ciphertext, you will be as secure with a H(key) as with (key), thus you might as well just memorize a good long ...

6

The wide class of NP problems meets your general question, almost to the exact definition. The summary is that (we conjecture that) there are problems that cannot be solved in as little as polynomial time but have solutions that can be verified to be correct in just polynomial time, so solving for the answer takes much longer than verifying the answer is ...

6

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 ...

5

Many lattice schemes are based on the shortest vector problem and it's variants. Elliptic curve crypto systems are based on something akin to discrete logarithms but it is different in its details. Some authentication schemes like HB are based on learning parity with noise and systems are based on the more general learning with errors. Subset sum was ...

5

The Merkle–Hellman knapsack cryptosystem was based on a variation of the subset sum problem. (It was broken by Adi Shamir a few years after it was developed.) Given a set of numbers $A$ and a number b, find a subset of $A$, which sums to b. The cryptosystem relies on the fact that in this form of the subset sum problem if the set $A$ is ...

5

If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break. A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer. So if ...

5

The modulus 77 leads to a short period.

5

"Frequency analysis of the output might help determine simple words in the ciphertext such as 'the' etc if that word is repeated and sent multiple times. This isn't necessarily a problem as it's only a simple word and doesn't convey much meaning to the message". If the word "the" doesn't convey much meaning, then why have you used that particular ...

5

It is not entirely clear what you want, but suppose you need a trapdoor permutation - the function that is easy to invert only if you know a secret parameter - and which is not based on number-theoretic assumptions. There are two well known families of such schemes: Multivariate Cryptography (MQ) and Code-based cryptosystems (for instance, McEliece ...

4

No, there aren't any cryptographic hash functions like this. I'm pretty confident you're not going to find one. I have yet to see a white-box secure hash function that remains secure against dedicated attack, let alone one that you can implement securely on pencil and paper. Since this is a practical problem, I suggest finding another solution -- like ...

4

There exist efficient algorithms to compute quadratic roots modulo a prime or prime power. If you know the factorization of the modulus you can use the above to compute quadratic roots mod the prime factors and then combine them using the chinese remainder theorem to efficiently compute the quadratic root of the full modulus. Thus, if you can factor the ...

4

As Mike asked, it's not clear if you're asking about onewayness, or collision resistance (as you call the function a 'cryptographic compression function'). Assuming you're asking about onewayness, well, given a single 128 bit value $h(M)$, we obviously cannot uniquely deduce the 1408 bit value $M$. However (hint), let us assume that we can ask for the ...

4

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort $2^{n}$, then breaking the Lamport signature scheme with $G$ having k-bit digests requires effort $2^{n}/2k$. So strictly speaking, with $F$ truncated to 128 bits and $G$ having 256 bits $(2k=512=2^{9})$, you will have ...

4

This is a type of code book security. Code books can be very strong or very weak depending on operational security. If you never reuse a code book word even in a single message and the code words are genuinely random - this approach could work. Of course if you can't reuse code words and need perhaps 40 instances of THE and 30 instances BE to avoid ...

4

A trapdoor one-way injection is a trapdoor one-way function such that two different elements of a single domain are never mapped to the same element of the corresponding codomain. By Goldreich-Levin, if there exists an trapdoor one-way injection then semantically secure public key encryption exists.

4

Say $m$ is the number and $h=f(m)$ it will be pretty easy to find $m'$ (not necessarily equal to $m$) such that $f(m)=f(m')$ on a modern computer. Brute Force The output of $f(m)$ is 32 bits. The following python function will do it def find_collision(val): while True: test = random.getrandbits(32) target = ((test*test) >> 16) & 0xffffffff) ...

4

Someone can find a preimage (or prove that there is no such preimage) with about $2^{20}$ trial squares, and no precomputed storage. ACtually, I believe that the below procedure will actually achieve $2^{18}$ trial squares; that requires closer analysis than I feel like at the moment. Here is the key observation that we can take advantage of to show this: ...

4

There are only $10^{10} \approx 2^{33}$ 10-digit numbers. Therefore, brute-forcing seems always possible, except if evaluating the hash function is very slow. But there is another problem: a hash table associating the hash of any swedish social security number to its security number requires only about 100 GB, since each social security number can be ...

4

One-way in the context of cryptography is usually defined to mean that, given an element from the range of a function (or even a series of elements from the range), it is not possible in time polynomial in the input (or maybe output) size to identify the element(s) in the domain that yields the range element(s). This is purely a bound on computational ...

4

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 ...

3

I'm not sure how much simpler than Wikipedia one can explain this. Assume you have a function $f$ which gets some input $x$, and produces from it some output $y = f(x)$. As one example, consider the function $f(x) = x·x$. Assume that $x$ is a non-zero real (or rational, or integer) number. Then $y = f(x) = x·x$ is still a non-zero number, and ...

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