# Tag Info

9

No, theoretically a SHA1 hash can be any 160-bit value, including the string of 160 zeroes. As for your second question, if we fudge a little bit and consider SHA1 a truly random function this becomes the same question as the following: If we flip 160 coins, what is the probability that at least 128 of them will be heads? Solution is left as an exercise ...

8

First of all, if your goal is to keep the garbled messages to "once every hundred years", well, you already don't meet that goal, even before the change. With an 8 bit CRC, a random change has a probability 1/256 of being accepted; hence if your wireless network has a transmission error at least once every three months (which, to me, sounds like an ...

8

Let's get terminology right. If you talk of "unknown s" then s is not a salt; when some piece of data is secret, we call it a key. And your "hash function" is then a MAC. In the context of "password hashing", such things are sometimes called "peppering" (as always, technical terminology is, at its core, a collection of bad puns). If your MAC is correct ...

7

The problem with a hash function like you ask for is that, if you hash an $n$-bit string and give the hash to someone else, they can recover the string using $n$ hash calculations with a binary search. For a simple example, let's say the $n=8$, your string is $01011001$ in binary, and its hash is $Y = H(01011001)$. To recover the string from the hash, I ...

5

Password strength is typically measured in bits of entropy, or in layman's terms, the amount of "true randomness" in the system. This is measured by the process of how the password is generated rather than by the number of bits in the output. It's a simple extension of Kerckhoff's principle: assume your attacker knows your process, and the only information ...

4

Your first assumption is assuming this is a hash digest value at all. It might be a block of data encrypted with AES-128 and a secret key. (I suppose finding the digest value in association with a name like PREFS_SUPERPOWERS_COUNT_HASH would be more of a giveaway that it is indeed the product of a hash.) One way to attack this would be to dump the binary ...

4

In practice, maybe, if you got additional information, such as that the hash function is known to conform to some published standard (you just don't know which). Theoretically, though, for any finite list of values, there is always more than one bounded algorithm that generates the list. You can never be absolutely sure you figured out the correct ...

4

If a hash function is a random oracle, which is about as perfect as can be expected for a hash function, then we actually expect a lot of collisions. If the hash function output is in a space of size $N$ (e.g. $N = 2^n$ for a "$n$-bit output") then collisions are expected, on average, when about $\sqrt{N}$ distinct inputs are hashed (see the birthday problem ...

4

Instead of that home-grown scheme, I would use PBKDF2 instead if you simply are sold on the idea of iterated hash schemes. It uses an such a scheme, although not exactly the one you have described, and is well-studied and considered secure. However, PBKDF2 doesn't offer many advantages over bcrypt, as PBKDF2 is still vulnerable to GPU and FPGA/ASIC ...

4

I like the didactic approach in this answer. But for something that behaves more like a hash function should, we might define $H$ for strings of digits $s$ as: $H(s)=(((1||s)\bmod 97)||s)\bmod 99991$ where $a||s$ is the number resulting from prepending the decimal representation of $a$ to the string $s$. Worked out example for $H(012345678)$ ...

4

If you want to demonstrate the properties of a good cryptographically secure hash, you could start with a non-cryptographically secure hash, and show why collisions are bad, why reversibility is bad, and why allowing modifications is bad. Once they've learned the "bad", they should better understand why those properties make a cryptographic hash "good". ...

4

This started as a comment to @Poncho's fine answer, and grew over the 600-char limit. Point is: a careful choice of the definition of V2 messages can keep some the existing capabilities of the original CRC to always detect some kinds of errors. Foremost, we are interested in short error bursts (where all bits in error are within a small number of ...

4

Since the output of the configuration of Skein is 1024 bits, we would expect to get 512 bits correct just by random hashing. So the question is, what is the probability of getting 640 bits correct? From that we can figure out how long it would take for that to occur. There are ${1024 \choose 640}\approx 4.16\cdot 10^{292}\approx 2^{972}$ ways this can ...

4

CRAM-MD5 is a protocol to demonstrate knowledge of a password. In the context of email, it is sometime used by an email client to authenticate to a POP, IMAP, or/and SMTP server. Basically, the password is used as the key of HMAC-MD5 in a challenge-response protocol. Among positive things there are to say about CRAM-MD5: The password is not exchanged in ...

3

Given the clarified answer, I suggest you do the following: $T = F_k(\text{password})$ $Y = H(T, \text{salt})$ where $F$ is a PRF (pseudorandom function) and $H$ is a slow hash. Here $k$ is the secret key (the "pepper"). You can instantiate $F$ with AES-CMAC or SHA256-HMAC (or any other good PRF). When you use $F$, feed the secret key $k$ (the pepper) ...

3

If there was a better known way than brute force, I suppose someone would already have made a paper about this (or lets this be secret to use it for attacks – but then this person wouldn't enter in such a competition). So it looks like just brute force. Why are these people better than you? Some guesses (and most likely it is a combination of these): They ...

3

That sort of thing is known as multi-party computation, and you should use a Socialist Millionaire Protocol for your particular instance.

3

First, a hash does not provide integrity. You would need a MAC (like HMAC) or a digital signature to ensure the message hasn't changed in transit. You'll have to put some standard value (say all zeros) into the field which holds the MAC, compute the MAC, then insert the value. Otherwise you have a chicken and egg problem. You need the MAC value to compute ...

3

"Efﬁcient, Compromise Resilient and Append-only Cryptographic Schemes for Secure Audit Logging" (PDF) gives a publicly verifiable approach that allows fine-grained verification, but it is in the Random Oracle Model. The Simple Method: The verifier and logger start with a seed for a forward-secure pseudo-random number generator. To denote a valid ending ...

2

A hash function is not supposed to provide this kind of security: if you have access to some message m and H(m), you can compute h(m) yourself for a given hash function h and check if they match. So, if you really have hash outputs, you can test the usual suspects MD4, MD5, SHA-1, SHA-2, RIPEMD and a few others depending on the hash length. If it's a ...

2

Bitcoin doesn't use RSA, it uses ECDSA. Every 256-bit value is a valid private key. (Though a very small fraction of them have to be folded.) But even if the numbers had to be special, it still wouldn't matter. You could use every 256-bit value as a seed to a pseudo-random number generator which you could use to deterministically generate numbers that had ...

2

Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output? A good (secure) hash function has output that is uniformly and evenly distributed and shouldn't be distinguishable from random value. Chi-squared tests of several hash functions So the minimum number of possible ones is $0$ and the maximum ...

2

First, separate the idea of "salt" from "hash". Salting is no more than a process applied to the message in a known way, such as appending the salt value to the end of the original data, yielding a "salted" message that differs from the original message. The hash algorithm is then performed using the salted message as input, yielding a digest value. A ...

2

I wouldn't even go so far as to say that a good hash function must have "as few collisions as possible" as you state in your question. The identity function has no collisions if we restrict the domain to be the inputs having the same size as the digest. But it's clearly a lousy hash function. To be "good" as a hash function is hard to define (which is ...

2

$\displaystyle \text{cycles per byte} = \frac{\text{cycles per second}}{\text{bytes per second}} = \frac{2.1 ~ \text{GHz}}{4.3 ~ \text{MiB}} = \frac{2.1 \times 10^9}{4.3 \times 1024^2} \approx 466 ~ \text{cpb}$ Of course this may be way off because processors are complex beasts these days, and may not work at their full potential all the time, and the ...

1

One problem not mentioned here is that CRC collisions are a certainty. If you were using a cryptographically secure hash, you would never encounter a false positive where both solutions were possible. In this scheme, every 256 messages would yield identical CRC values, and your different versions would be indistinguishable. You might be able to "stutter" ...

1

CRCs are not cryptographically secure. If you need cryptographic security, replace the CRC with a message authentication code (MAC). If you don't need cryptographic security, then your question is off-topic for Crypto.SE and you should probably flag it to ask the moderators to migrate it to Computer Science.SE.

1

The scheme you described above has some flaws. Because you aren't seeding the hash input each iteration, you are really increasing your chance of getting collisions. This is a great example of why you should try to avoid implementing these things yourself. It's really easy to overlook something subtle that undermines your system's security. As previously ...

1

In the first part of your question, you appear to be describing a password hashing scheme. A common (or, at least, commonly recommended) way to construct such schemes is based on a message authentication code (MAC). Specifically, let $\operatorname{MAC}_K(m)$ be a message authentication code with key $K$ and message $m$, and let $H(s,r) = d = (r, c)$, ...

1

If I understand the question correctly, you got an unknown value $s$, and known values $d$ and $r$, such that, for some one way function $H$, $H(s,r) = d$. You want to find both a function $G:\{0,1\}^*\times\{0,1\}^*\to \{0,1\}^*$ and a function $V:\{0,1\}^*\times\{0,1\}^*\to \{0,1\}$ such that for any $x$, $V(G(d,r'),s) = V(d,s) = 1$. Technically, at ...

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