Re: Is 3DES Broken?
| I think you meant ECB mode?
|
| No, I meant CBC -- there's a birthday paradox attack to watch out for.
|
| Yep. In fact, there's a birthday paradox problem for all the standard
| chaining modes at around 2^{n/2}.
|
| For CBC and CFB, this ends up leaking information about the XOR of a couple
| plaintext blocks at a time; for OFB and counter mode, it ends up making the
| keystream distinguishable from random. Also, most of the security proofs
| for block cipher constructions (like the secure CBC-MAC schemes) limit the
| number of blocks to some constant factor times 2^{n/2}.
|
| I'm surprised that no-one has said that ECB mode is unsafe at any speed.
Picking nits, but: ECB mode is unsafe at any speed to encrypt an arbitrary
data stream. If the data stream is known to have certain properties - e.g.,
because it has undergone some kind of transform before being fed into ECB -
then ECB is as good as any other mode.
After all, CBC is just ECB applied to a datastream transformed through a
particular unkeyed XOR operation.
There's a paper - by Ron Rivest and others? - that examines this whole issue,
and carefully separates the roles of the unkeyed and keyed transformations.
(I think this may be the paper where all-or-nothing transforms were
introduced.)
-- Jerry
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Is 3DES Broken?
| No, I meant CBC -- there's a birthday paradox attack to watch out for.
|
|
| Yep. In fact, there's a birthday paradox problem for all the standard
| chaining modes at around 2^{n/2}.
| For CBC and CFB, this ends up leaking information about the XOR of a couple
| plaintext blocks at a time; for OFB and counter mode, it ends up making the
| keystream distinguishable from random. Also, most of the security proofs
| for block cipher constructions (like the secure CBC-MAC schemes) limit the
| number of blocks to some constant factor times 2^{n/2}.
|
|
| It seems that the block size of an algorithm then
| is a severe limiting factor. Is there anyway to
| expand the effective block size of an (old 8byte)
| algorithm, in a manner akin to the TDES trick,
| and get an updated 16byte composite that neuters
| the birthday trick?
Many people have tried to do this. I know of no successes that are really
practical. (I've played around with many obviously good ideas myself, and
have always managed to break them with a little more thought. Everything
that gives you the desired security ends up costing much more than twice
the cost of the underlying block algorithm for a double-size block.)
The block size appears to be a fairly basic and robust property of block
ciphers. There's probably a theorem in there somewhere - probably one of
those that isn't hard to prove once you figure out exactly what it ought to
say!
-- Jerry
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Is 3DES Broken?
On 4 Feb 2005, at 10:51 AM, Greg Rose wrote: I'm surprised that no-one has said that ECB mode is unsafe at any speed. Because if they did, some smartass would chime in and say that ECB mode is perfectly fine at some speeds. For example, you could safely encrypt one bit in ECB mode, particularly if you permitted, nay encouraged the other 63 or 127 to be arbitrary nigh unto random. Surely you don't need to have an IV and padding and all if the small block were random-padded. We'd then get into a long debate over how many bits can be handled in such a system. 32? 127? 128? Then some other smartass would suggest that it's more efficient in such a case to just XOR the key on the data and effectively just use a one-time pad. And then we'd digress into a rambling discussion on one-time pads and how practical they are in real applications. Finally, some uber-smartass would point out that you can even get rid of the OTP by taking those small bits of data and padding appropriately and using a public-key op. By then, we'd all have lost sight of the fact that the main topic here is whether 3DES is broken and that the answer is a simple, no. (And it's a good thing that this is Cryptography, not Cypherpunks, as then there'd be another digression about Nader and how good the Corvair was or wasn't, along with URLs of nicely restored examples on eBay.) This is why no one has had the temerity to suggest that ECB mode is unsafe at any speed. Helpfully, Jon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Is 3DES Broken?
John Kelsey wrote:
From: Steven M. Bellovin [EMAIL PROTECTED]
No, I meant CBC -- there's a birthday paradox attack to watch out for.
Yep. In fact, there's a birthday paradox problem for all the standard chaining modes at around 2^{n/2}.
For CBC and CFB, this ends up leaking information about the XOR of a couple plaintext blocks at a time; for OFB and counter mode, it ends up making the keystream distinguishable from random. Also, most of the security proofs for block cipher constructions (like the secure CBC-MAC schemes) limit the number of blocks to some constant factor times 2^{n/2}.
It seems that the block size of an algorithm then
is a severe limiting factor. Is there anyway to
expand the effective block size of an (old 8byte)
algorithm, in a manner akin to the TDES trick,
and get an updated 16byte composite that neuters
the birthday trick?
Hypothetically, by say having 2 keys and running
2 machines in parallel to generate a 2x blocksize.
(I'm just thinking of this as a sort of mental challenge,
although over on the OpenPGP group we were toying
with the idea of adding GOST, but faced the difficulty
of its apparent age/weakness.)
iang
--
News and views on what matters in finance+crypto:
http://financialcryptography.com/
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Is 3DES Broken?
On Feb 2, 2005, at 1:32 PM, bear wrote: On Mon, 31 Jan 2005, Steven M. Bellovin wrote: snip re: 3des broken? [Moderator's note: The quick answer is no. The person who claims otherwise is seriously misinformed. I'm sure others will chime in. --Perry] [snip] When using CBC mode, one should not encrypt more than 2^32 64-bit blocks under a given key. [snip] whichever it is, as you point out there are other and more secure modes available for using 3DES if you have a fat pipe to encrypt. I don't want to take this down a rat-hole, but I respectfully disagree. The small block size of 3DES is also an issue with more secure modes. CCM states that only 128 but ciphers are to be used. The NIST document states For CCM, the block size of the block cipher algorithm shall be 128 bits; currently, the AES algorithm is the only approved block cipher algorithm with this block size. http://csrc.nist.gov/publications/nistpubs/800-38C/SP800-38C.pdf Ferguson points out that in OCB there is a birthday at the number of packets. From the paper, Collision attacks are much easier when 64-bit block ciphers are used. Therefore, we most strongly advise never to use OCB with a 64-bit block cipher. http://csrc.nist.gov/CryptoToolkit/modes/comments/Ferguson.pdf These basis of this is that the mode loses packet security at a birthday of the number of blocks. In communications, this is 2^32 blocks, and if we assume 1k blocks, this is 4TBytes, which occurs after transferring less than 2 full DVDs. As network performance grows, this will be a very common transfer size. While 3DES is not broken, it is my opinion that the 64 bit blocksize of 3DES is not adequate for today's requirements. In this sense, it is not broken, but obsolete. Thanks jim - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Is 3DES Broken?
On Mon, Jan 31, 2005 at 10:38:53PM -0500, Steven M. Bellovin wrote: When using CBC mode, one should not encrypt more than 2^32 64-bit blocks under a given key. That comes to ~275G bits, which means that on a GigE link running flat out you need to rekey at least every 5 minutes, which is often impractical. Notably for those encrypting data at rest, it's also rather smaller than current hard disk sizes, which are much harder to re-key. (Even for those only encrypting data in flight, it has practical implications regarding the feasibility of capturing that data for later analysis) -- Dan. pgpeucg0rdznT.pgp Description: PGP signature
Re: Is 3DES Broken?
On Jan 31, 2005, at 10:38 PM, Steven M. Bellovin wrote: When using CBC mode, one should not encrypt more than 2^32 64-bit blocks under a given key. That comes to ~275G bits, which means that on a GigE link running flat out you need to rekey at least every 5 minutes, which is often impractical. Since I've seen Gigabit Ethernet cards for US$25, this bears thinking about -- and while 10GigE is still too expensive for most people, its prices are dropping rapidly. With 10GigE, you'd have to rekey every 27.5 seconds... For reference purposes, with AES you'd be safe for 2^64*128 bits. That's a Big Number of seconds. --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb I would also like to reinforce Prof. Bellovin's comment that the 3DES block size is too small. In bulk storage system encryption, 3DES will require rekey every ~~65GBytes. Most PC's have more than this. With AES the number is ~250 Exabytes (which is 250 billion gigabytes). Thanks! jim - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Is 3DES Broken?
On Mon, 31 Jan 2005, Steven M. Bellovin wrote: snip re: 3des broken? [Moderator's note: The quick answer is no. The person who claims otherwise is seriously misinformed. I'm sure others will chime in. --Perry] I'll be happy to second Perry's comment -- I've seen no evidence whatsoever to suggest that it's been broken. But there are some applications where it's a bad choice for cryptographic reasons. When using CBC mode, one should not encrypt more than 2^32 64-bit blocks under a given key. I think you meant ECB mode? whichever it is, as you point out there are other and more secure modes available for using 3DES if you have a fat pipe to encrypt. Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Is 3DES Broken?
In message [EMAIL PROTECTED], Aram Perez writes: Hi Folks, I hate to bother you with what I consider a dumb question, but I'm trying to give a person the benefit of my doubts. There's a person on a legal forum that I participate in that claims that 3DES has been broken/cracked. However, he has not provided any documentation to the effect as his time at present is limited and valuable. He claims that the specifics were already posted on this and several other similar forums. Other than Ross Anderson and his students extracting a 3DES key from an IBM4758, has 3DES been in fact broken? Thank you, Aram Perez [Moderator's note: The quick answer is no. The person who claims otherwise is seriously misinformed. I'm sure others will chime in. --Perry] I'll be happy to second Perry's comment -- I've seen no evidence whatsoever to suggest that it's been broken. But there are some applications where it's a bad choice for cryptographic reasons. When using CBC mode, one should not encrypt more than 2^32 64-bit blocks under a given key. That comes to ~275G bits, which means that on a GigE link running flat out you need to rekey at least every 5 minutes, which is often impractical. Since I've seen Gigabit Ethernet cards for US$25, this bears thinking about -- and while 10GigE is still too expensive for most people, its prices are dropping rapidly. With 10GigE, you'd have to rekey every 27.5 seconds... For reference purposes, with AES you'd be safe for 2^64*128 bits. That's a Big Number of seconds. --Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
