Right, but that was the simplifying assumption I started with - that you lose the drive, the bad guys get it, and that's it. This would mean that by policy, if your laptop turns up in the lost and found, the first thing you do when you get it back is wipe the disk and restore from backup. If they can access the disk inbetween your accesses, things get much harder, and the measures in the papers you link become important. However, I still can't see a reason to use CBC - I'd rather use CTR with a real nonce and MAC.
Read Damgård-Dupont, interesting stuff, thanks for the pointer!
Thanks! I think the Halevi and Rogaway paper was the one I was referring to - the other stuff is new to me.
Where the problem is using sector encryption to protect data on a stolen drive, I'm assuming the simple solution is a secure seekable stream cipher. SEAL provides one, but it's patented. A block cipher in CTR mode does a good job, except as you say that if you use a 64-bit block cipher then after about 2^35 bytes you can distinguish it from a random stream by the absence of collisions. But a 128-bit cipher should be good for about 2^68 blocks, which is plenty. Salsa20 might turn out to be a tempting choice - it doesn't have the problems you refer to. This option isn't affected by chosen-plaintext attacks.
I'm assuming that the disk is encrypted with a randomly-generated key, and that this key in turn is encrypted with the passphrase. This was the strategy used by SFS.
My paper on my (broken) large-block cipher Mercy includes a discussion of some of these issues.
I'll follow the other references you give - thanks again!
There are interesting security issues with full-disk encryption, but it depends on your attack model. If your attack model is simply that the encrypted disk falls into the hands of the bad guys who try to get the data from it, the problem is easy. If the model is that they have access to the disk inbetween times that you're using it, that's when things get interesting.
Since in this instance the plausible attacks by-and-large fall into the former category, I don't see a difficulty here, am I wrong?
I'm not aware of any interesting current work on full-disk encryption apart from Rogaway et al's interesting large-tweaked-blockcipher mode CMC - if you know any please enlighten me, thanks!
If specs were 100% accurate, then there would not be a need to write the code, because the specs could be automatically translated to code (we are talking about 100% accuracy here, not 99.999999%).
This is not true in general. It's quite straightforward to spec out a program that solves the Halting Problem, for example, but rather harder to code one. And there are issues to do with optimization and so forth that would not appear in a specification.
Nonetheless, there's a great deal of truth in what you say - for most real-world programs, a 100% complete formal specification of what they had to do would not be much shorter than the program itself. This is why agile development methodologies make sense.
According to the Tiger home page, Tiger2 is just Tiger using the MD5/SHA padding method. It's probably done to make it a more convenient drop-in replacement, rather than for any security reasons.
I disagree. First, a large part of the point of a hash function is to compress. The identity function is perfectly collision-free, but has the disadvantage that the output is as big as the input. For a lot of applications, a smaller hash output means smaller messages and more efficient use of bandwidth. Second, if the hash function is truly as good as we want them to be then it should be impossible to devise a halfway reasonable [1] compression function which results in a weak hash function when composed with your origina hash function. However, it could easily make the hash function stronger against attacks which are aimed at discovering something useful about the message given the hash.
[1] by which I mean "if every input is equiprobable then every output is equiprobable". Truncation for example has this property.
An extreme example is Panama hash. If you didn't have an output stage but output the entire state, the output would be *far* too big (about 1k IIRC) and vulnerable to all sorts of attacks to do with discovering useful things about the message. As it happens, Panama hash is weak, but (again IIRC) the attack causes a collision in the internal state, so outputting it all wouldn't help. I think the future of hash functions lies less in things like Whirlpool and more in things like Panama. Note that AES designers had a hand in both.
I heard in 2002 that the AES designers were working on a hash/stream primitive that combined ideas from AES and from Panama, but no sign so far. And again, Bernstein's cache timing attacks make table-based ciphers that bit less attractive.
If you think AES needs to be changed incompatibly to address Bernstein's attack then you're asserting that it's very serious indeed. You're basically talking about creating a new algorithm with some similarities to AES; such an algorithm would have to go through a long approval process before seeing use. If we were going to do that, why would we use a "tweaked" version of AES rather than a whole new algorithm?
Whirlpool is not "based on AES". It shares a few similiarities (and a designer) but it is a distinct algorithm in its own right. It has a larger block size, different S-boxes, a different linear component, a different key schedule and so on.
I would interpret "based on AES" as meaning it actually uses AES itself (perhaps in tandem Davis-Meyer mode or similar).
I like Whirlpool but it's not fast. I think Tiger is quite a bit faster.
Bernstein's cache timing attacks, and the ever-growing gap between processor speeds and memory access times, mean that table-based primitives (which both of these are) are going out of style.
You are right, Whirlpool does have this problem. The correct fix is to have an internal state markedly larger than the hash output size. Whirlpool has a 512-bit internal state, so a lot of attacks on the Merkle-Damgard structure are totally impractical; you can always truncate the output to be what you need. However, Whirlpool is not fast.
As stated, it's false. However, for certain messages, if |x| == |y| then H(x) == H(y) means H(x + q + r) == H(y + q + r) for a particular q that depends on |x|.
This just means that if you can find one collision, you can find another; if finding collisions is implausibly hard then this property isn't a problem. However, there's a related property ("length extension") which is a problem, and it's one all Merkle-Damgard hash functions (ie practically all of them) have in common.
To solve this problem, and resist various other attacks such as multicollision attacks, generic long message attacks and so forth, we need hash functions that don't use the Merkle-Damgard paradigm. This should be an interesting area of research for the next wee while. I wish I knew what to recommend in the meantime...
I don't see the irony. "Innovation is the key to success" implies "if they're successful, they must be innovative". Microsoft propogate the idea that innovation is the key to success precisely in order to obscure the fact that their success owes nothing to technological innovation on their part.
My calculations indicate that with a 32-bit hash, even if you use 1000 iterations the chances that you'll be able to loop around and find a preimage of H^1000(x) are less than 0.02. That's a slight approximation but I can't see that it'll be off by much. If you're interested in pursuing this further, why not copy your code into pastebin.net or similar and I can help you debug it?
This comment thread will be closed soon, so email me and let me know. You might also want to put your name to a comment - after all, if you have found an attack, it should be credited to you.
As I've shown, this attack doesn't work, because the probability that you're in the loop at that stage is too low, and in any case it requires 2^80 work with a 2^160 bit hash, which is impractical. If your demonstration is correctly implemented it should show the same thing - how many iterations did you test it with? With a 32-bit hash, 20 iterations or so should show this effect.
If you find an attack that does work, please do publish it!
Won't work. It looks like you have about a hundred questions? A spammer only has to have a database of ten answers and reload the page ten times to get in. To defeat this, you'd need millions of questions, which would be far too much work to make up.
Just done some sums and I can place an upper bound on the probablility of being in the loop after 65536 iterations of 3.49245965481e-10 - this is the sum of the probability that you will come back to a pre-existing value after fewer than 2^48 iterations, plus the probability that when you come back you hit the first 65536 iterations, given that you take more than 2^48 iterations to do it. That's for a 128-bit hash; for a 160 bit hash it's much less likely again.
No, the probability you'll have even entered the loop after 65536 iterations is still very low, though calculating it is harder.
I think on some level you're thinking as if the hash function was bijective; that's the only way your "crack" would work. Of course if it were, the expected length of the loop would be 2^159 (or 2^127 if you're using MD5). Why don't you try testing it? Use a "hash function" that truncates its output to, say, 10 bits, so you can see why it doesn't work (and cut down the number of iterations to a suitable number too)
If you find an attack on Kelsey, Schneier et al's technique, publish. But so far you haven't.
Only if the password verifier is secret. If it is public (such as if the password is used to encrypt a message) or if attackers break in and get hold of it, this technique will slow down a dictionary attack.
Slashdot Mirror
Right, but that was the simplifying assumption I started with - that you lose the drive, the bad guys get it, and that's it. This would mean that by policy, if your laptop turns up in the lost and found, the first thing you do when you get it back is wipe the disk and restore from backup. If they can access the disk inbetween your accesses, things get much harder, and the measures in the papers you link become important. However, I still can't see a reason to use CBC - I'd rather use CTR with a real nonce and MAC.
Read Damgård-Dupont, interesting stuff, thanks for the pointer!
Thanks! I think the Halevi and Rogaway paper was the one I was referring to - the other stuff is new to me.
Where the problem is using sector encryption to protect data on a stolen drive, I'm assuming the simple solution is a secure seekable stream cipher. SEAL provides one, but it's patented. A block cipher in CTR mode does a good job, except as you say that if you use a 64-bit block cipher then after about 2^35 bytes you can distinguish it from a random stream by the absence of collisions. But a 128-bit cipher should be good for about 2^68 blocks, which is plenty. Salsa20 might turn out to be a tempting choice - it doesn't have the problems you refer to. This option isn't affected by chosen-plaintext attacks.
I'm assuming that the disk is encrypted with a randomly-generated key, and that this key in turn is encrypted with the passphrase. This was the strategy used by SFS.
My paper on my (broken) large-block cipher Mercy includes a discussion of some of these issues.
I'll follow the other references you give - thanks again!
There are interesting security issues with full-disk encryption, but it depends on your attack model. If your attack model is simply that the encrypted disk falls into the hands of the bad guys who try to get the data from it, the problem is easy. If the model is that they have access to the disk inbetween times that you're using it, that's when things get interesting.
Since in this instance the plausible attacks by-and-large fall into the former category, I don't see a difficulty here, am I wrong?
I'm not aware of any interesting current work on full-disk encryption apart from Rogaway et al's interesting large-tweaked-blockcipher mode CMC - if you know any please enlighten me, thanks!
If specs were 100% accurate, then there would not be a need to write the code, because the specs could be automatically translated to code (we are talking about 100% accuracy here, not 99.999999%).
This is not true in general. It's quite straightforward to spec out a program that solves the Halting Problem, for example, but rather harder to code one. And there are issues to do with optimization and so forth that would not appear in a specification.
Nonetheless, there's a great deal of truth in what you say - for most real-world programs, a 100% complete formal specification of what they had to do would not be much shorter than the program itself. This is why agile development methodologies make sense.
According to the Tiger home page, Tiger2 is just Tiger using the MD5/SHA padding method. It's probably done to make it a more convenient drop-in replacement, rather than for any security reasons.
I disagree. First, a large part of the point of a hash function is to compress. The identity function is perfectly collision-free, but has the disadvantage that the output is as big as the input. For a lot of applications, a smaller hash output means smaller messages and more efficient use of bandwidth. Second, if the hash function is truly as good as we want them to be then it should be impossible to devise a halfway reasonable [1] compression function which results in a weak hash function when composed with your origina hash function. However, it could easily make the hash function stronger against attacks which are aimed at discovering something useful about the message given the hash.
[1] by which I mean "if every input is equiprobable then every output is equiprobable". Truncation for example has this property.
An extreme example is Panama hash. If you didn't have an output stage but output the entire state, the output would be *far* too big (about 1k IIRC) and vulnerable to all sorts of attacks to do with discovering useful things about the message. As it happens, Panama hash is weak, but (again IIRC) the attack causes a collision in the internal state, so outputting it all wouldn't help. I think the future of hash functions lies less in things like Whirlpool and more in things like Panama. Note that AES designers had a hand in both.
I heard in 2002 that the AES designers were working on a hash/stream primitive that combined ideas from AES and from Panama, but no sign so far. And again, Bernstein's cache timing attacks make table-based ciphers that bit less attractive.
If you think AES needs to be changed incompatibly to address Bernstein's attack then you're asserting that it's very serious indeed. You're basically talking about creating a new algorithm with some similarities to AES; such an algorithm would have to go through a long approval process before seeing use. If we were going to do that, why would we use a "tweaked" version of AES rather than a whole new algorithm?
Whirlpool is not "based on AES". It shares a few similiarities (and a designer) but it is a distinct algorithm in its own right. It has a larger block size, different S-boxes, a different linear component, a different key schedule and so on.
I would interpret "based on AES" as meaning it actually uses AES itself (perhaps in tandem Davis-Meyer mode or similar).
I like Whirlpool but it's not fast. I think Tiger is quite a bit faster.
Bernstein's cache timing attacks, and the ever-growing gap between processor speeds and memory access times, mean that table-based primitives (which both of these are) are going out of style.
You are right, Whirlpool does have this problem. The correct fix is to have an internal state markedly larger than the hash output size. Whirlpool has a 512-bit internal state, so a lot of attacks on the Merkle-Damgard structure are totally impractical; you can always truncate the output to be what you need. However, Whirlpool is not fast.
As stated, it's false. However, for certain messages, if |x| == |y| then H(x) == H(y) means H(x + q + r) == H(y + q + r) for a particular q that depends on |x|.
This just means that if you can find one collision, you can find another; if finding collisions is implausibly hard then this property isn't a problem. However, there's a related property ("length extension") which is a problem, and it's one all Merkle-Damgard hash functions (ie practically all of them) have in common.
To solve this problem, and resist various other attacks such as multicollision attacks, generic long message attacks and so forth, we need hash functions that don't use the Merkle-Damgard paradigm. This should be an interesting area of research for the next wee while. I wish I knew what to recommend in the meantime...
Oh, search the STFW!
I nearly always switch this off when I'm fiddling with the preferences on the browser. Haven't found anything it doesn't work with so far...
How do you think I feel?
I don't see the irony. "Innovation is the key to success" implies "if they're successful, they must be innovative". Microsoft propogate the idea that innovation is the key to success precisely in order to obscure the fact that their success owes nothing to technological innovation on their part.
I think charlie might have something to say about that...
My calculations indicate that with a 32-bit hash, even if you use 1000 iterations the chances that you'll be able to loop around and find a preimage of H^1000(x) are less than 0.02. That's a slight approximation but I can't see that it'll be off by much. If you're interested in pursuing this further, why not copy your code into pastebin.net or similar and I can help you debug it?
This comment thread will be closed soon, so email me and let me know. You might also want to put your name to a comment - after all, if you have found an attack, it should be credited to you.
Think of it as an 80% reduction in the bandwidth demands on your intermediary.
It's the link I provided at the start: http://www.schneier.com/paper-low-entropy.html
As I've shown, this attack doesn't work, because the probability that you're in the loop at that stage is too low, and in any case it requires 2^80 work with a 2^160 bit hash, which is impractical. If your demonstration is correctly implemented it should show the same thing - how many iterations did you test it with? With a 32-bit hash, 20 iterations or so should show this effect.
If you find an attack that does work, please do publish it!
Won't work. It looks like you have about a hundred questions? A spammer only has to have a database of ten answers and reload the page ten times to get in. To defeat this, you'd need millions of questions, which would be far too much work to make up.
It's pretty different from encryption as far as ways to defeat it go! But yes, I think it's a fascinating topic worthy of academic research.
One way to get around it might to make the response to the captcha a URL that the user types in to the location bar directly.
Just done some sums and I can place an upper bound on the probablility of being in the loop after 65536 iterations of 3.49245965481e-10 - this is the sum of the probability that you will come back to a pre-existing value after fewer than 2^48 iterations, plus the probability that when you come back you hit the first 65536 iterations, given that you take more than 2^48 iterations to do it. That's for a 128-bit hash; for a 160 bit hash it's much less likely again.
No, the probability you'll have even entered the loop after 65536 iterations is still very low, though calculating it is harder.
I think on some level you're thinking as if the hash function was bijective; that's the only way your "crack" would work. Of course if it were, the expected length of the loop would be 2^159 (or 2^127 if you're using MD5). Why don't you try testing it? Use a "hash function" that truncates its output to, say, 10 bits, so you can see why it doesn't work (and cut down the number of iterations to a suitable number too)
If you find an attack on Kelsey, Schneier et al's technique, publish. But so far you haven't.
They should use NAT punch-through.
Only if the password verifier is secret. If it is public (such as if the password is used to encrypt a message) or if attackers break in and get hold of it, this technique will slow down a dictionary attack.
I make that 2^83885952 (10*1024*1024*8-128) but relative to the error you're pointing out, you're roughly correct.