# Tag Info

33

It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction ...

24

What you're missing is the fact that multiple logic gates can share the same input(s). So you can't look at each logic gate individually and "reverse" the entire circuit that way, because choosing the inputs of a logic gate may constrain the outputs of other logic gates (so not all possible choices of input for any logic gate will work, only some will). So ...

7

They don't, and in fact the sponge construction used in Keccak (SHA-3) allows for variable length output. In other hashes the Merkle-Damgård construction was used which has a fixed output length due to the nature of its design. But there is no reason to not allow for variable output length other than ease of development or use.

7

There's a problem with boundaries here; how much "complication" is allowed? I could argue that SHA-2 is a complication of SHA-1 because they both use a Merkle-Damgård construction and have other similar elements. Then again, they are significantly different internally. On the other hand the addition of a single bitwise rotation did make SHA-1 significantly ...

5

A length extension attack doesn't let you find a collision. It lets you predict the hash for an input with an unknown component in the prefix. If you have $h = H(x)$ for unknown (or partially unknown) $x$, you can generate $h_y = H(x \vert\vert y)$ for arbitrary $y$ (this is not strictly correct; I've ignored padding, but for the purposes of this discussion ...

5

Basic Building Blocks of a Hash Function The part of a hash function that leads to the digest always being the same size regardless of input length is called the compression function. The compression function is then linked with a domain extender which extends the compression function to allow it to map across any length of input. Construction From Block ...

5

There's absolutely zero need to have the token tied to the user's email address. Just add a column in the database for the token, generate the token randomly, and send it out to the user. If you want to go one step further, send the user the token, but only store $H(token)$ in the database, where $H$ is a sound cryptographic hash function of your choosing.

4

From a cryptographic standpoint a MAC would be perfect (e.g. HMAC-SHA256(strong secret key, email)). As long as no-one knows your secret key it is infeasible to find a token for another mail. One thing you will probably have to handle is: What happens when someone changes their email? What if someone resubmits the same form? Should the token be invalidated ...

4

Because a hash function essentially destroys the inputs, or information. For example, a common operation in hashing is modular math, which is basically the remainder after the division. 9 mod 2 = 1 (9 / 2 = 4, remainder 1). The 1 moves on in the hashing function. But the modular operation is irreversible - all that is left is the output of 1, but there ...

4

In general, no: two bitstrings with the same MD5 need not be related by a simple relation (other than the obvious have the same MD5). Argument: take $2^{128}+1$ distinct random $1024$-bit bitstrings; by the pigeonhole principle, at least two are bound to have the same MD5; since less than $2^{257}$ pairs of distinct bitstrings can be picked among ...

3

As of now I can think of four different applications for XOFs. Note that some change the padding depending on the requested output size and so the outputs are truly unrelated, Skein does this. Signature message hashing. Using an XOF you don't have to rely on ad-hoc constructions for hashing the message in signature schemes to the appropriate size. For ...

3

One solution is to use the choice of which equivalent message you send as a way to encode a MAC value. Take a "base message", where e.g. each word choice is the alphabetically first one. (Or some other known rule.) Calculate the MAC for that: MAC(key, message). The MAC should be $m$ bits or less. HMAC, possibly truncated would work fine. Encode that MAC ...

3

This approach will work, but there's another approach I want you to suggest. As for why it's secure (or better the ways to attack): Break the elliptic curve discrete logarithm problem. If you can do this you can just grab the first address out of your addresses, solve for the private key and derive all subsequent ones. This is generally considered ...

3

This specific hash function is weak; it appears that what this hash function does is pad out the string to be hashed into a 32 byte string, and then take the 8 4-byte substrings, and maps each substring individually into an individual byte. This immediately makes it trivial to find a preimage; start with a random 31 byte preimage (there appears to be a bug ...

3

That's a simple substitution cipher. Base 64 uses the following alphabet A-Za-z0-9+/. Here A encodes 000000, B encodes 000001 etc. In your case the g encodes 000000, P encodes 000001 etc. Instead of writing your own decoder for that you can simply take the ciphertext, iterate through the characters of the ciphertext and replace g with A, P with B etc. After ...

3

This is a really bad (and somewhat pointless) idea (if you do it on your own), because it provides less security than standard hashing and should only be considered if password escrow is a necessary feature. If you don't need the password escrow (= recover the password using the heavily secured airgapped private key) you can simply password-hash the password ...

3

You can simply handle password verification on login and escrow independently: Store a salted password hash (e.g. bcrypt) together with its salt. You can use this to verify logins, just like what you'd use if you had no escrow. Also store the password encrypted with asymmetric encryption (e.g. RSA-OAEP, ECIES). Since these are randomized, they are not ...

2

Q: Why do cryptographic hashes need to have a fixed length output? I know that the shallow answer is that an output that varies by key size or file size can leak information somehow, leading to cryptanalysis, but I would like some more intuition as to why this is the case. It depends on what you mean with that. If you mean that they need to have a ...

2

Your error is here: An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output. A set of possible inputs can be derived from any given output. For each output that is a 1, there are three possible combinations of input (01, 10, and 11). If you add enough gates in sequence, ...

2

A mathematically elegant and rather simple way of hashing are the parity bits of a Hamming code, as small changes in the data will yield different parity bits. You can weakly hash 4-bit strings to 3-bit strings with the standard (7,4) Hamming code, but the general Hamming code construction has high enough rate that you can hash longer strings (say, 26 bits ...

2

Consider that I, as an attacker, suspects what you're sending in your secret messages. If what you propose were possible, then I could know your plaintext by comparing my encryption of what I thought you were sending to what you actually sent, and brute for variations until I could confirm what you had sent. This would be VERY bad. Therefore, I assume you ...

2

This answers a comment to Stephen Touset's fine answer. With SHA-256, or any collision-resistant hash, no known attack (including length extension) allows producing a file different from the original file and that has the same hash as the original, even if an adversary could choose the original. Even with the practically-broken MD5, or the broken SHA-1, no ...

2

Your key derivation function is not particularly memory hard. The second loop walks the array in order, so an optimized implementation which an attacker would use can avoid the whole array, keeping only some elements in memory at a time. For example, you can halve the memory use by only storing the second half of M initially. Then for the first N/2 ...

2

Coming up with a specific number is hard. Realistically, all three options take you well out of the realm of ever having more than the absolute worst passwords brute-forced by an attacker. The primary gain of scrypt and argon2 over bcrypt is a hit to parallelism due to the addition of memory requirements. GPUs with thousands cores will need (but don't have) ...

2

It is unlikely that a secure X-bit hash function's X/2-bit truncation would not be X/2-bit secure. For example, suppose you have a faster than $2^{128}$ second preimage attack on the 128-bit truncation of a 256-bit hash. Then you can run that attack $2^{128}$ times and expect to find a second preimage for some value of the full 256-bit hash, so that hash ...

2

If you use a deterministic encryption algorithm (so that you can actually verify passwords without the private key) it basically works like a backdoored hash. An attacker will be able to use a brute force or dictionary attack normally. One obvious problem with any reversible encryption is that it reveals (at least something about) the password length. (E.g. ...

2

Collisions are not much of a concern, since you have to compute them to know they happen, and assuming your values are a typical hash size (256+ bits) they will never happen randomly anyway. But yes, having identical computation that use the same data is wasteful if you don't store the intermediate values. However, the main problem your function has is that ...

2

In general there is no default hash algorithm in the PKCS#1 standards, neither for RSA with PKCS#1 v1.5 padding or RSA with PSS. Both these schemes are defined in RFC 3447 RSA PKCS#1 v2.1. Note that PKCS#1 v2.2 adds a few SHA-2 hash functions (SHA-224 and SHA-512/224 and SHA-512/256) to the mix - neither of which makes much sense. PSS uses a Mask Generation ...

1

Yes, this is known as convergent encryption. The usual way to do it is content hash keying, where you hash the plaintext, then use that hash as a key for deterministic symmetric encryption. You get authentication "for free" by checking that the hash matches, though that means the ciphertext is unauthenticated and you probably want to avoid modes like CBC ...

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