Re: What is the accepted technical definition of the word break?

From: David Hopwood (david.hopwood@zetnet.co.uk)
Date: 03/24/03 

Date: Mon, 24 Mar 2003 18:37:51 +0000
From: David Hopwood <david.hopwood@zetnet.co.uk>

-----BEGIN PGP SIGNED MESSAGE-----

ekj@ekj.vestdata.no wrote:
> On Mon, 17 Mar 2003, Florian Greinecker wrote:
>
> > Trivially chipher is also broken if brute force can be done in
> > reasonably time.
>
> I don't agree. Neither does Schneier.
>
> It is a *given* that any cipher with a 40 bit key can be broken with at
> most 2^40 work. This is not a weakness.

Of course it's a weakness. There's no practical difference in strength
between an algorithm that is too weak because its parameters preclude it
from being strong, and an algorithm that is too weak because of a successful
cryptanalysis (with the same work factor and success probability). Note
that the formal definitions of security properties such as IND-CPA, etc.
do not make any distinction between these cases.

However, the normal definition of "broken" (in this technical context) is
that an algorithm meets its *claimed* security goals - no matter how weak
or strong the goals. So a cipher with a 40-bit key is necessarily weak, but
may not be broken.

> It is true that this makes such a cipher useless for modern
> applications, but this is a different matter.

It's the same matter: it is useless because it is weak. I think you have
the definitions of "broken" and "weak" the opposite way round to their
normal usage (which most posters to this thread seem to agree on).

- --
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPn9QTTkCAxeYt5gVAQHahQf8CBH7Fu214fNEE8rVswGyX2O+/PA1otZ3
NqeLDIOTKAz4BLV+YqEVmvIdifpWXwHOhYfC1zY1oDAodnZpagZj5IIYC+FP1/v1
NcPXQrppLbG+Q6jKNeC6vaQCOXht2iSzh7LFky6lfRwGa8rD7HL1rM3oD9RsA+53
ecelJPVbe2VVCjvLUP1KScIOqzi40Uga+03yYIqlJKQRPO1Y7I9YT/OgrqWWqLAn
hWgteIoCMTbG4XhSE4RSaDVImLi7fUki72tUxthOICL8oR96CMBIDFTaobGyw5Kq
2dv7Wb39AvBiCZybqJpW8LJ0jiKWnfoVsH6wiZzaCfa85uoktLFNSQ==
=ECb0
-----END PGP SIGNATURE-----

Relevant Pages

  • Re: Yet another substitute for Math.random
    ... matter truly random or pseudo-random, given that the tester is truly ... acting on some - possibly very sophisticated - algorithm. ... pseudo-random) then on the long run player B will loose more games ...
    (comp.lang.javascript)
  • Re: SF: New factoring method
    ... At this point I know it's a matter of quadratic residues ... I wasn't sure what JSH knows. ... but factoring /2 still is not an easy task in general. ... I doubt that JSH has the ability to implement his "algorithm". ...
    (sci.math)
  • Re: Accuracy of Orion XT IntelliScopes with Object Locator
    ... enough to "dead on" for government work. ... of the algorithm, to first order. ... The reason it might matter is if the ... The PleiadAtlas Home Page at http://www.astronomycorner.net/pleiadatlas/ ...
    (sci.astro.amateur)
  • Re: MODUNI a Good Key Generator
    ... key are useless. ... Don't use it for cryptography. ... It doesn't matter how long the pseudo-random sequence is. ... it doesn't matter how complex you make the algorithm ...
    (sci.crypt)
  • Re: Axcrypt program
    ... I suppose it might be worth pointing that out - but remember that an executable ... because that's not how you assess an algorithm. ... In case this matter has distracted us, may I rephrase my original question: ...
    (sci.crypt)