No. If your password is not in the hash database, and the password system is half decent (eg MD5 + salt), the probability of your password colliding with any of the passwords in the hash database above is so negligibly small that there is no point in checking for it.
No, the chances of entering a loop after 65536 hashes are roughly 2^-129. If you're using a 160-bit hash then you'd likely have to hash 2^80 times or so before reaching a value you'd seen before.
Passwords are generally so pathetic that even five bits are worth having, but fifteen or even twenty bits are practical if you don't mind a tiny bit of extra server load when verifying a password.
Obviously collisions exist, as a simple counting argument proves. "Collision free" is a technical term denoting that finding collisions in that hash function is hard.
This is called "key strengthening". It has its advantages, but I prefer "key stretching", the technique of iterating hashes I linked to earlier; it's harder to parallelize the attack and more predictable how long it will take. Google for "schneier low-entropy".
Use a random salt - that way, the salt changes every time you change your password, and the probability that two entries anywhere in the world have the same salt by accident can be bounded.
Actually I have seen many applications that fail to salt passwords before hashing them; it's depressing. Salt should be long enough to be globally unique when randomly generated. Old-style Unix passwords used a 12-bit salt, which was pathetic; 128 bits would be plenty.
In addition, it's best to iterate the hash many times, which slows down dictionary attacks. See Kelsey, Schneier et al, "Secure Applications of Low-Entropy Keys":
The proofs in that paper are based on the assumption that the hash function is collision free, which of course MD5 isn't; another hash function might be preferable.
It's OK for Tim O'Reilly to invite who he likes, and it's a very difficult thing to do. Far from creating a rival camp being a bitter and evil thing to do, it's an extremely constructive and positive response, and it could mean that there are two creative geek hothouse conferences where before there was one. Let a thousand flowers bloom!
Your picture of the history of crypto is a little weird. I recommend Steven Levy's "Crypto" for a clearer idea. Sadly he doesn't cover the AES process, but it's a fun read all the same. If you decide you want to understand the topic in more depth, "Handbook of Applied Cryptography" is a good direction to go next. Wikipedia's cover of crypto is sadly quite patchy; I've tried to address it in places, and clear up egregious errors, but it's a big job.
Also, factoring primes is pretty straightforward. It's the composite numbers that give us the trouble.
No shifts. XOR, 16-bit add, and a special multiply operation mod 2^16 + 1 (where 0 is treated as 2^16). Sadly it's very hard to do the multiply without opening yourself up to timing attacks. It's not a Feistel network; it's a network of its own kind.
The space of weak keys is so small that the chances of picking one at random are minuscule; it's not really a big problem. On the other hand, no weak keys are known for AES and many other well-studied ciphers, so IDEA can no longer claim to be in the front rank of security.
OK. Promise you'll familiarize yourself with this work in more detail before citing it again? The first demonstrated break against DES was (IIRC) Mitsuru Matsui's linear cryptanalyis in 1993.
You seem very sure of that for someone who doesn't know what they're talking about.
We have every reason to believe, for example, that factoring large semiprimes is hard. If it is, then the Blum-Blum-Shub RNG is strong. In which case, if you use BBS to encrypt your message with a sufficiently large key, it won't be broken. Not with being "clued to the nature of the algorithm". Not with "knowledge of a secret constant" (where on Earth did you get that notion from?). It might simply be the case that the algorithm that breaks BBS in reasonable time does not exist.
Contrariwise, P might even be equal to NP. We don't know - these are all big, unsolved problems in computer science and cryptography. But we have no reason to believe that every encryption algorithm has a corresponding cryptanalysis algorithm, and to blithely assert that it does just shows your ignorance.
OTPs may be perfect in theory, but in practice, for ordinary users, they are one of the least secure forms of encryption. You are trusting your security to the security of the channel through which you move your key material, and I don't think that channel is ever going to be as strong as (say) 256-bit AES. Of course, if you're setting up the red telephone between Washington and Moscow, you can use *both* a strong cipher *and* a one-time-pad.
There are no outstanding patents against Rabin, I believe. I imagine that fielded RSA hardware could probably also use Rabin. Of course many standards don't support Rabin, but that's a different question.
ECC is probably appropriate in a lot more circumstances than it is used, but I can see reasons why one might choose to use Rabin instead - if one needs the PK operation to be very fast (eg signature verification, see Bernstein's trick for insanely fast Rabin signature verification) or if you are more confident of the hardness of integer factorization than of the EC-DH problem. In other words, both have their advantages and disadvantages and there's reasons to choose either. (Note that I'm characterizing a huge range of possibilities under the one term "ECC" here).
However, there is absolutely no inherent reason why one would choose RSA over Rabin, and those who do so when they have a choice (ie when the choice is not dictated by standards or suchlike) thereby demonstrate their ignorance of cryptography.
The thing that should really kill RSA is that it has no advantages whatsoever over Rabin besides being slightly simpler, and it has several important disadvantages, particularly the absence of a provable relationship with factoring.
The most effective attacks on DES are brute force, linear cryptanalysis, and the improved davies attack (a form of differential cryptanalysis). This talk of paired primes is confused nonsense, probably to do with some sort of dictionary-based attack on Unix passwords, which is a different but related problem. It sounds like she might be using Hellman's time/space tradeoff.
Actually, reading on, it looks like the author really doesn't have a clue. At one point he suggests using RSA in place of DES. Even most Slashdot readers know that in practice, when you use RSA for encryption, you use it in conjunction with a symmetric encryption algorithm.
IBM has considerable cryptographic expertise; it's a shame none of it was brought to bear on this article.
DES was *not* considered "uncrackable" when it was launched. In fact, cryptographers such as Michael Weiner warned that the key was too short and described the dangers of a hardware-based key cracker practically as soon as it was announced.
The history of cryptography is not simply one of algorithms thought uncrackable being cracked. It is one of consistent refinement of our understanding and technique, but to imagine that the history of DES means we'll be breaking open 256-bit AES-encrypted messages in a few years is delusion.
The key question is, did their temporary move put enough pressure on Microsoft to get them a cheaper deal for Office? In which case, it's worth moving to OpenOffice even if you intend to move back...
The state of the art in exploiting what is known about generating MD5 collisions relies on generating executabe content with colliding checksums, and causing that content to behave differently because of the distinct blocks. Making two meaningfully different images that have colliding checksums is much, much harder. The best technique currently available for doing that is still brute force, which is just about on the edge of practical for a single pair of photos given a massive distributed effort - perhaps a ten or a hundred times more work than distributed.net's RC5-64 effort.
It's not proof in the mathematical sense - no real-world assertion admits such a proof - but I don't think one could entertain reasonable doubt that someone had gone to the effort of forging an MD5 collision in order to stick someone with a bogus speeding fine.
* RSA Factoring Challenge - because nobody has found a "magic" formula for instant factoring.
You're funny. It's very unlikely that a breakthrough in factoring is going to come from the tinkering of a bored coder. It's more likely to come from someone who has already mastered advanced number theory, algebraic number theory, elliptic curves and finite fields, the CFRAC method, the quadratic sieve, and the special and general number field sieves.
And no-one's ever proven that you have to factor large numbers to solve the RSA problem. Indeed, it's now believed that no such relation will ever be found.
I am always amused by this sort of completely zero-brain moral relativist moral absolutism. "You think that mass murder should carry a prison sentence? If I don't like the shirt you're wearing, should you go to prison?"
Please try thinking - it's more productive than you might imagine.
Slashdot Mirror
No. If your password is not in the hash database, and the password system is half decent (eg MD5 + salt), the probability of your password colliding with any of the passwords in the hash database above is so negligibly small that there is no point in checking for it.
No, the chances of entering a loop after 65536 hashes are roughly 2^-129. If you're using a 160-bit hash then you'd likely have to hash 2^80 times or so before reaching a value you'd seen before.
Passwords are generally so pathetic that even five bits are worth having, but fifteen or even twenty bits are practical if you don't mind a tiny bit of extra server load when verifying a password.
Obviously collisions exist, as a simple counting argument proves. "Collision free" is a technical term denoting that finding collisions in that hash function is hard.
This is called "key strengthening". It has its advantages, but I prefer "key stretching", the technique of iterating hashes I linked to earlier; it's harder to parallelize the attack and more predictable how long it will take. Google for "schneier low-entropy".
Use a random salt - that way, the salt changes every time you change your password, and the probability that two entries anywhere in the world have the same salt by accident can be bounded.
Actually I have seen many applications that fail to salt passwords before hashing them; it's depressing. Salt should be long enough to be globally unique when randomly generated. Old-style Unix passwords used a 12-bit salt, which was pathetic; 128 bits would be plenty.
In addition, it's best to iterate the hash many times, which slows down dictionary attacks. See Kelsey, Schneier et al, "Secure Applications of Low-Entropy Keys":
http://www.schneier.com/paper-low-entropy.html
The proofs in that paper are based on the assumption that the hash function is collision free, which of course MD5 isn't; another hash function might be preferable.
I take it any code produced there will be called "Bar Code"?
IGMC.
It's OK for Tim O'Reilly to invite who he likes, and it's a very difficult thing to do. Far from creating a rival camp being a bitter and evil thing to do, it's an extremely constructive and positive response, and it could mean that there are two creative geek hothouse conferences where before there was one. Let a thousand flowers bloom!
You might be interested to look at the crypto content on my website.
http://www.ciphergoth.org/crypto/
Your picture of the history of crypto is a little weird. I recommend Steven Levy's "Crypto" for a clearer idea. Sadly he doesn't cover the AES process, but it's a fun read all the same. If you decide you want to understand the topic in more depth, "Handbook of Applied Cryptography" is a good direction to go next. Wikipedia's cover of crypto is sadly quite patchy; I've tried to address it in places, and clear up egregious errors, but it's a big job.
Also, factoring primes is pretty straightforward. It's the composite numbers that give us the trouble.
No shifts. XOR, 16-bit add, and a special multiply operation mod 2^16 + 1 (where 0 is treated as 2^16). Sadly it's very hard to do the multiply without opening yourself up to timing attacks. It's not a Feistel network; it's a network of its own kind.
The space of weak keys is so small that the chances of picking one at random are minuscule; it's not really a big problem. On the other hand, no weak keys are known for AES and many other well-studied ciphers, so IDEA can no longer claim to be in the front rank of security.
OK. Promise you'll familiarize yourself with this work in more detail before citing it again? The first demonstrated break against DES was (IIRC) Mitsuru Matsui's linear cryptanalyis in 1993.
You seem very sure of that for someone who doesn't know what they're talking about.
We have every reason to believe, for example, that factoring large semiprimes is hard. If it is, then the Blum-Blum-Shub RNG is strong. In which case, if you use BBS to encrypt your message with a sufficiently large key, it won't be broken. Not with being "clued to the nature of the algorithm". Not with "knowledge of a secret constant" (where on Earth did you get that notion from?). It might simply be the case that the algorithm that breaks BBS in reasonable time does not exist.
Contrariwise, P might even be equal to NP. We don't know - these are all big, unsolved problems in computer science and cryptography. But we have no reason to believe that every encryption algorithm has a corresponding cryptanalysis algorithm, and to blithely assert that it does just shows your ignorance.
OTPs may be perfect in theory, but in practice, for ordinary users, they are one of the least secure forms of encryption. You are trusting your security to the security of the channel through which you move your key material, and I don't think that channel is ever going to be as strong as (say) 256-bit AES. Of course, if you're setting up the red telephone between Washington and Moscow, you can use *both* a strong cipher *and* a one-time-pad.
DES is also broken in that sense, with linear cryptanalysis and the improved Davies attack.
There are no outstanding patents against Rabin, I believe. I imagine that fielded RSA hardware could probably also use Rabin. Of course many standards don't support Rabin, but that's a different question.
ECC is probably appropriate in a lot more circumstances than it is used, but I can see reasons why one might choose to use Rabin instead - if one needs the PK operation to be very fast (eg signature verification, see Bernstein's trick for insanely fast Rabin signature verification) or if you are more confident of the hardness of integer factorization than of the EC-DH problem. In other words, both have their advantages and disadvantages and there's reasons to choose either. (Note that I'm characterizing a huge range of possibilities under the one term "ECC" here).
However, there is absolutely no inherent reason why one would choose RSA over Rabin, and those who do so when they have a choice (ie when the choice is not dictated by standards or suchlike) thereby demonstrate their ignorance of cryptography.
The thing that should really kill RSA is that it has no advantages whatsoever over Rabin besides being slightly simpler, and it has several important disadvantages, particularly the absence of a provable relationship with factoring.
The most effective attacks on DES are brute force, linear cryptanalysis, and the improved davies attack (a form of differential cryptanalysis). This talk of paired primes is confused nonsense, probably to do with some sort of dictionary-based attack on Unix passwords, which is a different but related problem. It sounds like she might be using Hellman's time/space tradeoff.
Actually, reading on, it looks like the author really doesn't have a clue. At one point he suggests using RSA in place of DES. Even most Slashdot readers know that in practice, when you use RSA for encryption, you use it in conjunction with a symmetric encryption algorithm.
IBM has considerable cryptographic expertise; it's a shame none of it was brought to bear on this article.
DES was *not* considered "uncrackable" when it was launched. In fact, cryptographers such as Michael Weiner warned that the key was too short and described the dangers of a hardware-based key cracker practically as soon as it was announced.
The history of cryptography is not simply one of algorithms thought uncrackable being cracked. It is one of consistent refinement of our understanding and technique, but to imagine that the history of DES means we'll be breaking open 256-bit AES-encrypted messages in a few years is delusion.
The key question is, did their temporary move put enough pressure on Microsoft to get them a cheaper deal for Office? In which case, it's worth moving to OpenOffice even if you intend to move back...
The state of the art in exploiting what is known about generating MD5 collisions relies on generating executabe content with colliding checksums, and causing that content to behave differently because of the distinct blocks. Making two meaningfully different images that have colliding checksums is much, much harder. The best technique currently available for doing that is still brute force, which is just about on the edge of practical for a single pair of photos given a massive distributed effort - perhaps a ten or a hundred times more work than distributed.net's RC5-64 effort.
It's not proof in the mathematical sense - no real-world assertion admits such a proof - but I don't think one could entertain reasonable doubt that someone had gone to the effort of forging an MD5 collision in order to stick someone with a bogus speeding fine.
I don't know of a cryptographic application of axiomatic set theory, can you point one out?
Finite fields, elliptic curves, algebraic number theory, linear algebra I'm used to, but not axiomatic set theory.
Can you have any conception of how annoying Charlie will be if he wins a Hugo?
* RSA Factoring Challenge - because nobody has found a "magic" formula for instant factoring.
You're funny. It's very unlikely that a breakthrough in factoring is going to come from the tinkering of a bored coder. It's more likely to come from someone who has already mastered advanced number theory, algebraic number theory, elliptic curves and finite fields, the CFRAC method, the quadratic sieve, and the special and general number field sieves.
And no-one's ever proven that you have to factor large numbers to solve the RSA problem. Indeed, it's now believed that no such relation will ever be found.
I am always amused by this sort of completely zero-brain moral relativist moral absolutism. "You think that mass murder should carry a prison sentence? If I don't like the shirt you're wearing, should you go to prison?"
Please try thinking - it's more productive than you might imagine.