A discussion of what it means to claim a cipher is "broken."
Subject: Many attacks, one break? Date: Fri, 6 Nov 1998 15:42:01 +0900 From: "Hiroshi Fujita" <lenz@als.aoyama.ac.jp> Message-ID: <71u5q4$fcf$1@ac-nws.cc.aoyama.ac.jp> Newsgroups: sci.crypt Lines: 17 There are many different terms for attacks (ciphertext-only and so on), but only one term for success (break). Why not use the same convention as for attacks when talking about success? That is, ciphertext-only break, known-plaintext break and so on. I would also like to propose the terms theoretical break (like reducing a workload from 128 bits bruteforce to 110 bits bruteforce) and practical break (obtaining any information on key or message in real life). Karl-Friedrich Lenz :-) www.toptext.com
Subject: Re: Many attacks, one break? Date: 6 Nov 1998 07:30:16 GMT From: stl137@aol.com (STL137) Message-ID: <19981106023016.29961.00001044@ng34.aol.com> References: <71u5q4$fcf$1@ac-nws.cc.aoyama.ac.jp> Newsgroups: sci.crypt Lines: 9 "Theoretical" is a personal opinion, not really quantifiable. (If you put the limit somewhere, I can either A. Show you how more funding can break it, or B. Show you how no one could have that kind of funding". ------ STL137@aol.com ===> Website: http://members.aol.com/stl137/ PGP keys: ~~~pgp.html Quotes: ~~~quotes.html "I have sworn upon the altar of God eternal hostility against every form of tyranny over the mind of man" - Thomas Jefferson
Subject: Re: Many attacks, one break? Date: 6 Nov 1998 03:45:08 -0800 From: Karl-Friedrich Lenz <Karl-Friedrich@newsguy.com> Message-ID: <71ung4$mb5@edrn.newsguy.com> References: <19981106023016.29961.00001044@ng34.aol.com> Newsgroups: sci.crypt Lines: 17 In article , stl137@aol.com says... > >"Theoretical" is a personal opinion, not really quantifiable. (If you put the >limit somewhere, I can either A. Show you how more funding can break it, or B. >Show you how no one could have that kind of funding". If you can show that no one could have the funding to brute force 110 bits, the break of reducing 128 to 110 (which is considered a break by Bruce Schneier in his cryptanalysis self-study course) would clearly be a theoretical break. On the other hand, reading plaintext in a ciphertext-only attack against some simple historical system or a system some newbie amateur came up with would clearly be a practical break. So while there might be borderline cases, in quite a lot of cases the distinction will be not only a matter of opinion. Karl-Friedrich Lenz www.toptext.com/crypto/
Subject: Re: Many attacks, one break? Date: Fri, 6 Nov 1998 09:32:55 +0100 From: <tbb03ar@mail.lrz-muenchen.de> Message-ID: <Pine.GSO.4.03.9811060816420.513-100000@sun5.lrz-muenchen.de> References: <71u5q4$fcf$1@ac-nws.cc.aoyama.ac.jp> Newsgroups: sci.crypt Lines: 37 On Fri, 6 Nov 1998, Hiroshi Fujita wrote: > There are many different terms for attacks (ciphertext-only and so on), but > only one term for success (break). > > Why not use the same convention as for attacks when talking about success? > That is, ciphertext-only break, known-plaintext break and so on. > > I would also like to propose the terms theoretical break (like reducing a > workload from 128 bits bruteforce to 110 bits bruteforce) and practical > break (obtaining any information on key or message in real life). I think your 'theoretical break' is an successful attack (like the known-plaintext-attacks against DES) but not a break (DES was never broken). Your 'practical break' would simply be called 'break'. Such a break may need some known or even chosen plaintext (every algorithm should be strong against attacks with some kilobytes of known plaintext, stronger ones should be strong against attacks with megabytes or even gigabytes of chosen plaintext). Andreas Enterrottacher enterrottacher@lrz.tu-muenchen.de enterrottacher@t-online.de > > Karl-Friedrich Lenz :-) > www.toptext.com > > > > > > >
Subject: Re: Many attacks, one break? Date: 6 Nov 1998 03:38:31 -0800 From: Karl-Friedrich Lenz <Karl-Friedrich@newsguy.com> Message-ID: <71un3n$lvv@edrn.newsguy.com> References: <Pine.GSO.4.03.9811060816420.513-100000@sun5.lrz-muenchen.de> Newsgroups: sci.crypt Lines: 16 In article , >I think your 'theoretical break' is an successful attack (like the >known-plaintext-attacks against DES) but not a break (DES was never >broken). Your 'practical break' would simply be called 'break'. Look at Ritter's glossary: He defines break as the result of a successful attack. In that definition, there is no difference between successful attack and break, contrary to your usage. But leaving words aside, we seem to agree that it does make a difference if a break has real-world applications or is only of theoretical value. Many so called breaks of modern ciphers seem to be quite far away from really reading ciphertext or getting keys from a reasonable amount of known plaintext. Karl-Friedrich Lenz www.toptext.com/crypto/
Subject: Re: Many attacks, one break? Date: Fri, 6 Nov 1998 14:32:04 +0100 From: <tbb03ar@mail.lrz-muenchen.de> Message-ID: <Pine.GSO.4.03.9811061428550.10463-100000@sun5.lrz-muenchen.de> References: <71un3n$lvv@edrn.newsguy.com> Newsgroups: sci.crypt Lines: 35 On 6 Nov 1998, Karl-Friedrich Lenz wrote: > In article , > >I think your 'theoretical break' is an successful attack (like the > >known-plaintext-attacks against DES) but not a break (DES was never > >broken). Your 'practical break' would simply be called 'break'. > > Look at Ritter's glossary: He defines break as the result of a successful > attack. In that definition, there is no difference between successful attack and > break, contrary to your usage. I think this definition is not the commonly used one: This would imply that as well DES (because of Bihams attack) as IDEA (don't know who was the attacker) were broken, but practically both algorithms are secure (except the small keyspace of DES). > > But leaving words aside, we seem to agree that it does make a difference if a > break has real-world applications or is only of theoretical value. Many so > called breaks of modern ciphers seem to be quite far away from really reading > ciphertext or getting keys from a reasonable amount of known plaintext. Accepted. > > Karl-Friedrich Lenz > www.toptext.com/crypto/ > > Andreas Enterrottacher enterrottacher@lrz.tu-muenchen.de enterrottacher@t-online.de
Subject: Re: Many attacks, one break? Date: Tue, 10 Nov 1998 03:34:42 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3647b447.4474700@news.io.com> References: <Pine.GSO.4.03.9811061428550.10463-100000@sun5.lrz-muenchen.de> Newsgroups: sci.crypt Lines: 73 On Fri, 6 Nov 1998 14:32:04 +0100, in <Pine.GSO.4.03.9811061428550.10463-100000@sun5.lrz-muenchen.de>, in sci.crypt <tbb03ar@mail.lrz-muenchen.de> wrote: >On 6 Nov 1998, Karl-Friedrich Lenz wrote: > >> In article , >> >I think your 'theoretical break' is an successful attack (like the >> >known-plaintext-attacks against DES) but not a break (DES was never >> >broken). Your 'practical break' would simply be called 'break'. >> >> Look at Ritter's glossary: He defines break as the result of a successful >> attack. In that definition, there is no difference between successful attack and >> break, contrary to your usage. > >I think this definition is not the commonly used one: This would imply >that as well DES (because of Bihams attack) as IDEA (don't know who was >the attacker) were broken, but practically both algorithms are secure >(except the small keyspace of DES). From the Handbook of Applied Cryptography: "1.23 Definition. An encryption scheme is said to be *breakable* if a third party, without prior knowledge of the key pair (e,d), can systematically recover plaintext from corresponding ciphertext in some appropriate time frame." [p.14] ...and... "*Breaking* an information security service (which often involves more than simply encryption) implies defeating the objective of the intended service." [p.15] 1. It seems to me that "break" needs to apply to an arbitrary attack, including attacks on hashing. Thus: "a successful attack." 2. The issue seems to be a conflict between the normal English understanding of "broken" as "impractical to use," versus the crypto, where "broken" does not necessarily imply that a cipher is impractical. This is a real confusion and a slur on a good cipher. But it would be very hard to state at just what strength a cipher *is* no longer "useful": Even weak ciphers can be effective and *useful* in low-bandwidth situations. One alternative would seem to be to reserve "break" for "a practical attack," but then we have to define "practical." Or a "break" could be "the current best attack," but that would mean that past breaks would no longer be breaks. Or we could require that a "break" be better than the advertised keyspace, but that still means we can have very powerful "broken" ciphers and so does not solve the problem. Presumably we can clarify the situation by using "practical break" to express the sentiment of a serious weakness. In the opposite direction we might have: "impractical break," "academic break," "theoretical break," or "certificational break." So the designer of a slurred cipher could retort: "that 'break' was only academic; the cipher is still secure in practice." On the other hand, a "break" that doesn't work is no break at all. 3. One thing I *have* thought to do is to require that a "break" be less effort than the advertised strength. But then what do we call a successful attack that takes *more* effort? Is that a "failed" attack? Obviously not. It is just a (currently) useless break. So I think we stay where we are. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Many attacks, one break? Date: Tue, 10 Nov 1998 11:43:43 +0100 From: <tbb03ar@mail.lrz-muenchen.de> Message-ID: <Pine.GSO.4.03.9811100818350.11312-100000@sun5.lrz-muenchen.de> References: <3647b447.4474700@news.io.com> Newsgroups: sci.crypt Lines: 110 On Tue, 10 Nov 1998, Terry Ritter wrote: > > On Fri, 6 Nov 1998 14:32:04 +0100, in > <Pine.GSO.4.03.9811061428550.10463-100000@sun5.lrz-muenchen.de>, in > sci.crypt <tbb03ar@mail.lrz-muenchen.de> wrote: > > >On 6 Nov 1998, Karl-Friedrich Lenz wrote: > > > >> In article , > >> >I think your 'theoretical break' is an successful attack (like the > >> >known-plaintext-attacks against DES) but not a break (DES was never > >> >broken). Your 'practical break' would simply be called 'break'. > >> > >> Look at Ritter's glossary: He defines break as the result of a successful > >> attack. In that definition, there is no difference between successful attack and > >> break, contrary to your usage. > > > >I think this definition is not the commonly used one: This would imply > >that as well DES (because of Bihams attack) as IDEA (don't know who was > >the attacker) were broken, but practically both algorithms are secure > >(except the small keyspace of DES). > > From the Handbook of Applied Cryptography: > > "1.23 Definition. An encryption scheme is said to be *breakable* if a > third party, without prior knowledge of the key pair (e,d), can > systematically recover plaintext from corresponding ciphertext in some > appropriate time frame." [p.14] > > ...and... > > "*Breaking* an information security service (which often involves more > than simply encryption) implies defeating the objective of the > intended service." [p.15] > > The first definition says clearly 'in some appropriate time frame'. This frame may be different for different ciphers - days for some ones, decades for others, but this is clearly a 'practical break'. The other one tells about the same with 'defeating the objective of the intended service': An attack may allow to reduce the effective keysize but not to break the cipher - who cares if the keysize of GOST could be reduced to 192 bit? > 1. It seems to me that "break" needs to apply to an arbitrary attack, > including attacks on hashing. Thus: "a successful attack." Accepted. > > 2. The issue seems to be a conflict between the normal English > understanding of "broken" as "impractical to use," versus the crypto, > where "broken" does not necessarily imply that a cipher is > impractical. This is a real confusion and a slur on a good cipher. > But it would be very hard to state at just what strength a cipher *is* > no longer "useful": Even weak ciphers can be effective and *useful* > in low-bandwidth situations. > > One alternative would seem to be to reserve "break" for "a practical > attack," Exactly this is done in the definitions you mentioned :-) > but then we have to define "practical." And this depends on the usage of the cipher. I think, all ciphers that couldn't be broken with the present technology within - let's say a century - is strong (first definition). To call a cipher 'broken' it would (in addition) be neccessary to break it faster than with brute force (meets as well first as second defintion). RC4 with 40 bits keysize is weak but not broken. DES is weak but not broken. > ... > 3. One thing I *have* thought to do is to require that a "break" be > less effort than the advertised strength. But then what do we call a > successful attack that takes *more* effort? Is that a "failed" > attack? Obviously not. It is just a (currently) useless break. So I > think we stay where we are. Every attack faster than brute force is successful. It may or may not be a break - depending on the neccessary time/computer power needed for a break. For weak ciphers I think every successful attack is a break while for a stronger one it is only a break if the speed of the attack allows to break the cipher within acceptable time - let's say a century. I don't see why anybody should use weak ciphers (except existing laws) in a time where ciphers exist that are at the same time strong and fast (at least I don't know of any successful attack on RC4, for example). I'd prefer usage of key-escrow instead of using 40 bit ciphers (why use something that could be broken by everybody instead of using something that can be broken only by the government) while strong ciphers that aren't escrowed are of course the better choice. > ... Andreas Enterrottacher enterrottacher@lrz.tu-muenchen.de enterrottacher@t-online.de
Subject: Re: Many attacks, one break? Date: Sun, 08 Nov 1998 22:09:22 GMT From: schneier@counterpane.com (Bruce Schneier) Message-ID: <36461506.7272610@news.visi.com> References: <71u5q4$fcf$1@ac-nws.cc.aoyama.ac.jp> Newsgroups: sci.crypt Lines: 48 On Fri, 6 Nov 1998 15:42:01 +0900, "Hiroshi Fujita" <lenz@als.aoyama.ac.jp> wrote: >There are many different terms for attacks (ciphertext-only and so on), but >only one term for success (break). > >Why not use the same convention as for attacks when talking about success? >That is, ciphertext-only break, known-plaintext break and so on. > >I would also like to propose the terms theoretical break (like reducing a >workload from 128 bits bruteforce to 110 bits bruteforce) and practical >break (obtaining any information on key or message in real life). You have a real complaint. There is much abuse of the term "break" in the literature. For some, a "break" means that you can read traffic encrypted in the cipher in an operational setting. For others, a "break" is demonstrating that one of more of the security claims of the cipher is false. I have heard the terms "theoretical break" or "academic break" to describe the latter. For example, an attack against a 128-bit key that has a workfactor of 2^110 is clearly impractical, but does mean that the 128-bit cipher is providing less security than advertised. This is an academic break. There are also attacks against simplified versions of ciphers. For example, the current best attack against IDEA works against 4.5 rounds (the complete cipher is 8 rounds). The attack itself is impractical, but even if it weren't, it wouldn't be able to decrypt any traffic encrypted with the full 8 rounds of IDEA. Why do we care about impractical breaks? Because we are constantly required to make decisions about which ciphers to use. Given that we don't know how to formulate proofs of security for block ciphers, all we can do is pick the best we can of the available pile. And that means disgarding ciphers that have academic breaks if there are other, also well studied, ciphers that don't. This will become important in the AES selection process. There are fifteen candidates. If an attack is discovered against a candidate, even if it is a theoretical attack, it will likely knock that cipher out of the running as long as there are alternatives that prevent such attacks. Bruce ********************************************************************** Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590 Free crypto newsletter. See: http://www.counterpane.com
Subject: Re: Many attacks, one break? Date: Tue, 10 Nov 1998 04:38:12 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3647c322.8278074@news.io.com> References: <36461506.7272610@news.visi.com> Newsgroups: sci.crypt Lines: 34 On Sun, 08 Nov 1998 22:09:22 GMT, in <36461506.7272610@news.visi.com>, in sci.crypt schneier@counterpane.com (Bruce Schneier) wrote: >[...] >Why do we care about impractical breaks? Because we are constantly >required to make decisions about which ciphers to use. Given that we >don't know how to formulate proofs of security for block ciphers, all >we can do is pick the best we can of the available pile. And that >means disgarding ciphers that have academic breaks if there are other, >also well studied, ciphers that don't. I claim that cryptanalysis provides no information at all beyond a break or argument of weakness. A cipher without an academic break is not necessarily stronger, it just has yet to be broken. One could even argue that the broken cipher is a better bet because it is better understood. >This will become important in the AES selection process. There are >fifteen candidates. If an attack is discovered against a candidate, >even if it is a theoretical attack, it will likely knock that cipher >out of the running as long as there are alternatives that prevent such >attacks. Without a deeper argument of weakness, avoiding a cipher because of an impractical attack would seem irrational. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Many attacks, one break? Date: 10 Nov 1998 11:02:54 -0500 From: giff@eng.us.uu.net (Frank Gifford) Message-ID: <729o3e$eqm@perrier.eng.us.uu.net> References: <3647c322.8278074@news.io.com> Newsgroups: sci.crypt Lines: 21 In article <3647c322.8278074@news.io.com>, Terry Ritter <ritter@io.com> wrote: > >On Sun, 08 Nov 1998 22:09:22 GMT, in <36461506.7272610@news.visi.com>, >in sci.crypt schneier@counterpane.com (Bruce Schneier) wrote: > >>This will become important in the AES selection process. There are >>fifteen candidates. If an attack is discovered against a candidate, >>even if it is a theoretical attack, it will likely knock that cipher >>out of the running as long as there are alternatives that prevent such >>attacks. > >Without a deeper argument of weakness, avoiding a cipher because of an >impractical attack would seem irrational. Wouldn't you then agree that avoiding a cipher because of an unknown future attack is also irrational? -Giff -- giff@uu.net Too busy for a .sig
Subject: Re: Many attacks, one break? Date: Tue, 10 Nov 1998 18:43:44 GMT From: ritter@io.com (Terry Ritter) Message-ID: <36488954.5026441@news.io.com> References: <729o3e$eqm@perrier.eng.us.uu.net> Newsgroups: sci.crypt Lines: 26 On 10 Nov 1998 11:02:54 -0500, in <729o3e$eqm@perrier.eng.us.uu.net>, in sci.crypt giff@eng.us.uu.net (Frank Gifford) wrote: >In article <3647c322.8278074@news.io.com>, Terry Ritter <ritter@io.com> wrote: >>[...] >>Without a deeper argument of weakness, avoiding a cipher because of an >>impractical attack would seem irrational. > >Wouldn't you then agree that avoiding a cipher because of an unknown future >attack is also irrational? I don't see your point. We do avoid ciphers which seem like they *might* have some particular attack strategy -- I suppose that would be an extrapolation argument. But without such an argument and without practical weakness, avoiding the cipher BECAUSE IT IS WEAK would seem irrational, yes. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Many attacks, one break? Date: Thu, 12 Nov 1998 05:11:05 GMT From: dianelos@tecapro.com Message-ID: <72dql9$2nr$1@nnrp1.dejanews.com> References: <729o3e$eqm@perrier.eng.us.uu.net> Newsgroups: sci.crypt Lines: 24 In article <729o3e$eqm@perrier.eng.us.uu.net>, giff@eng.us.uu.net (Frank Gifford) wrote: > In article <3647c322.8278074@news.io.com>, Terry Ritter <ritter@io.com> wrote: > >... > >Without a deeper argument of weakness, avoiding a cipher because of an > >impractical attack would seem irrational. > > Wouldn't you then agree that avoiding a cipher because of an unknown future > attack is also irrational? Several of the AES candidates include features designed specifically as a possible defense against unknown attacks. Unknown future attacks are a real threat and should be a present worry. If all other factors are comparable, I think it does make sense to avoid a cipher where unknown attacks have played no role in its design. -- http://www.tecapro.com email: dianelos@tecapro.com -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Subject: Re: Many attacks, one break? Date: 10 Nov 1998 11:07:39 -0500 From: giff@eng.us.uu.net (Frank Gifford) Message-ID: <729ocb$esk@perrier.eng.us.uu.net> References: <3647c322.8278074@news.io.com> Newsgroups: sci.crypt Lines: 17 >On Sun, 08 Nov 1998 22:09:22 GMT, in <36461506.7272610@news.visi.com>, >in sci.crypt schneier@counterpane.com (Bruce Schneier) wrote: > >>This will become important in the AES selection process. There are >>fifteen candidates. If an attack is discovered against a candidate, >>even if it is a theoretical attack, it will likely knock that cipher >>out of the running as long as there are alternatives that prevent such >>attacks. More to the point, it's possible that what is a theoretical attack today could be tweaked by others in the crypto community and make it into a viable attack for tomorrow. -Giff -- giff@uu.net Too busy for a .sig
Subject: Re: Many attacks, one break? Date: Tue, 10 Nov 1998 18:29:32 GMT From: schneier@counterpane.com (Bruce Schneier) Message-ID: <364b85ff.2098415@news.visi.com> References: <729ocb$esk@perrier.eng.us.uu.net> Newsgroups: sci.crypt Lines: 23 On 10 Nov 1998 11:07:39 -0500, giff@eng.us.uu.net (Frank Gifford) wrote: >>On Sun, 08 Nov 1998 22:09:22 GMT, in <36461506.7272610@news.visi.com>, >>in sci.crypt schneier@counterpane.com (Bruce Schneier) wrote: >> >>>This will become important in the AES selection process. There are >>>fifteen candidates. If an attack is discovered against a candidate, >>>even if it is a theoretical attack, it will likely knock that cipher >>>out of the running as long as there are alternatives that prevent such >>>attacks. > >More to the point, it's possible that what is a theoretical attack today >could be tweaked by others in the crypto community and make it into a >viable attack for tomorrow. "Attacks always get better." Bruce ********************************************************************** Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590 Free crypto newsletter. See: http://www.counterpane.com
Subject: Re: Many attacks, one break? Date: Tue, 10 Nov 1998 18:44:13 GMT From: ritter@io.com (Terry Ritter) Message-ID: <36488971.5055875@news.io.com> References: <729ocb$esk@perrier.eng.us.uu.net> Newsgroups: sci.crypt Lines: 21 On 10 Nov 1998 11:07:39 -0500, in <729ocb$esk@perrier.eng.us.uu.net>, in sci.crypt giff@eng.us.uu.net (Frank Gifford) wrote: >[...] >More to the point, it's possible that what is a theoretical attack today >could be tweaked by others in the crypto community and make it into a >viable attack for tomorrow. Anything is possible already. We don't need a theoretical attack for that. In fact, a theoretical attack could be seen as a clear bill of health for a cipher with respect to that attack, unless there is some particular basis for an extrapolation of weakness. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Many attacks, one break? Date: Tue, 10 Nov 1998 18:29:01 GMT From: schneier@counterpane.com (Bruce Schneier) Message-ID: <364a85af.2018107@news.visi.com> References: <3647c322.8278074@news.io.com> Newsgroups: sci.crypt Lines: 26 On Tue, 10 Nov 1998 04:38:12 GMT, ritter@io.com (Terry Ritter) wrote: >I claim that cryptanalysis provides no information at all beyond a >break or argument of weakness. > >A cipher without an academic break is not necessarily stronger, it >just has yet to be broken. One could even argue that the broken >cipher is a better bet because it is better understood. I just don't agree. And I am willing to disagree. >>This will become important in the AES selection process. There are >>fifteen candidates. If an attack is discovered against a candidate, >>even if it is a theoretical attack, it will likely knock that cipher >>out of the running as long as there are alternatives that prevent such >>attacks. > >Without a deeper argument of weakness, avoiding a cipher because of an >impractical attack would seem irrational. And it is possible that we are all irrational. Such is life. Bruce ********************************************************************** Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590 Free crypto newsletter. See: http://www.counterpane.com
Terry Ritter, his current address, and his top page.
Last updated: 1999-01-19