* Volker Armin Hemmann (volker.armin.hemmann@tu-clausthal.de) [27.06.08 00:12]:
> and this is why nobody uses brute force.
>
> There a better ways to crack keys. NSA has tons of experts in mathematics and
> cryptoanalysis. Plus very sophisticated hardware. I am sure for most ciphers
> they use something much more efficient than stupid brute force.
>

The thing about this keys is, that there is no better way than to brute
force such keys. The algorithm uses a function which inverse is a known
hard problem which resides in NP, which is a class of functions equal to
just guessing. If the NSA had a sufficient algorithm, that is capable of
reducing the time that much, they should also be able to prove P=NP.
This is worth 1.000.000$ iirc and somehow you should get a Nobel Prize
for it.

For deeper and better insight, take some courses in cryptography and
theoretical computer sience, they are quiet good at Clausthal.

Sebastian

--
" Religion ist das Opium des Volkes. " Karl Marx

On Fri, 27 Jun 2008 00:47:34 +0200, Sebastian Günther wrote:

> If the NSA had a sufficient algorithm, that is capable of
> reducing the time that much, they should also be able to prove P=NP.
> This is worth 1.000.000$ iirc and somehow you should get a Nobel Prize
> for it.

I'm sure the NSA would be happy to forego the prize and keep quiet about
being able to break a secure cipher. Just like our GCHQ came up with
public key cryptography several years before Rivest, Shamir and Adleman
published RSA but kept it secret for over 30 years.

--
Neil Bothwick

If I save time, when do I get it back?

06-27-2008, 12:16 AM

Volker Armin Hemmann

h

On Freitag, 27. Juni 2008, Sebastian Günther wrote:
> * Volker Armin Hemmann (volker.armin.hemmann@tu-clausthal.de) [27.06.08
00:12]:
> > and this is why nobody uses brute force.
> >
> > There a better ways to crack keys. NSA has tons of experts in mathematics
> > and cryptoanalysis. Plus very sophisticated hardware. I am sure for most
> > ciphers they use something much more efficient than stupid brute force.
>
> The thing about this keys is, that there is no better way than to brute
> force such keys. The algorithm uses a function which inverse is a known
> hard problem which resides in NP, which is a class of functions equal to
> just guessing. If the NSA had a sufficient algorithm, that is capable of
> reducing the time that much, they should also be able to prove P=NP.
> This is worth 1.000.000$ iirc and somehow you should get a Nobel Prize
> for it.

I now that AES is pretty good - but there are more ciphers out there - and a
lot of them are fishy at best. Some of them nobody really knows, because they
are closed and some are known weak. There are good ones and there are bad ones
- and I don't doubt that the NSA is pretty good at analyzing the not-so-good-
ones.
--
gentoo-user@lists.gentoo.org mailing list

There a better ways to crack keys. NSA has tons of experts in mathematics and
cryptanalysis. Plus very sophisticated hardware. I am sure for most ciphers
they use something much more efficient than stupid brute force.

The thing about this keys is, that there is no better way than to brute
force such keys. The algorithm uses a function which inverse is a known
hard problem which resides in NP, which is a class of functions equal to
just guessing.

I don't believe this is true. The algorithm uses a function which is
*assumed* to be a hard problem. You assume the problem is hard because
you and anyone you know have not been able to make it easy. That does
not mean that someone has not discovered some math that does make it easy.

Here's a reference to the interesting meet-in-the-middle attack which
reduced 3DES key space down to 112 bits from 192. Obviously that was
unknown when 3DES was built.

http://en.wikipedia.org/wiki/Triple_DES#Security

kashani
--
gentoo-user@lists.gentoo.org mailing list

06-27-2008, 08:42 AM

Alan McKinnon

h

On Friday 27 June 2008, Volker Armin Hemmann wrote:
> > Numbers don't lie.
>
> and this is why nobody uses brute force.
>
> There a better ways to crack keys. NSA has tons of experts in
> mathematics and cryptoanalysis. Plus very sophisticated hardware. I
> am sure for most ciphers they use something much more efficient than
> stupid brute force.

Like what for example? Decent algorithms tend to have no known published
weaknesses and their output is randomly distributed. Which brings us
back to relying on stupid user input errors (Debian, anyone?)

If anyone does know of weaknesses in the good algorithms, they are
certainly not telling. I doubt anyone could ever keep that genie in a
bottle for very long as it would be the mathematical coup of the
millenium.

So the reasonable real-world view of this to me is that not even the
almighty NSA can crack it yet. I'm betting they still use good
old-fashioned tried-and-proven social engineering and hosepipe
techniques for their successes.

--
Alan McKinnon
alan dot mckinnon at gmail dot com

--
gentoo-user@lists.gentoo.org mailing list

06-27-2008, 08:51 AM

Alan McKinnon

h

On Friday 27 June 2008, kashani wrote:
> > The thing about this keys is, that there is no better way than to
> > brute force such keys. The algorithm uses a function which inverse
> > is a known hard problem which resides in NP, which is a class of
> > functions equal to just guessing.
>
> I don't believe this is true. The algorithm uses a function which is
> *assumed* to be a hard problem. You assume the problem is hard
> because you and anyone you know have not been able to make it easy.
> That does not mean that someone has not discovered some math that
> does make it easy.

It's more than a thumb-suck assumption. In maths, "assume" is overloaded
to have an entirely different meaning to what it has in everyday life,
much like "theory" in science.

The assumption comes from all the solid maths surrounding the NP
problem. As any decent mathematician/cryptologist will tell you,
cracking this one is the current holy grail in their field and the
amount of man-power being applied to solving it is staggering. Neil
mentioned GCHQ developing public key several years before RSA, but do
note that RSA still had the same bright idea that GCHQ had, only a few
short years later. There are thousands of examples in math and science
of the same huge advances being made by two parties independently -
because they are working from the same known base. I feel quite
confident that the NP problem will be no different.

--
Alan McKinnon
alan dot mckinnon at gmail dot com

--
gentoo-user@lists.gentoo.org mailing list

06-27-2008, 08:59 AM

Neil Bothwick

h

On Fri, 27 Jun 2008 10:51:57 +0200, Alan McKinnon wrote:

> Neil
> mentioned GCHQ developing public key several years before RSA, but do
> note that RSA still had the same bright idea that GCHQ had, only a few
> short years later.

The important point was that they kept quiet about it. Even after RSA
entered the public domain, they let everyone think it was news to them.

Mind you, the UK government kept quiet about breaking Enigma after WWII
was over, so they could sell these "secure" systems to their Commonwealth
"friends".

--
Neil Bothwick

Top Oxymorons Number 2: Exact estimate

06-27-2008, 09:44 AM

Stroller

h

On 27 Jun 2008, at 00:37, Neil Bothwick wrote:

On Fri, 27 Jun 2008 00:47:34 +0200, Sebastian Günther wrote:

If the NSA had a sufficient algorithm, that is capable of
reducing the time that much, they should also be able to prove P=NP.
This is worth 1.000.000$ iirc and somehow you should get a Nobel
Prize

for it.

I'm sure the NSA would be happy to forego the prize and keep quiet
about

being able to break a secure cipher.

I can't help wondering if - since P=NP is such a big problem - the
advantages of having this knowledge in the public domain might
override the advantages of mere spying.

Stroller.

--
gentoo-user@lists.gentoo.org mailing list

06-27-2008, 10:08 AM

Neil Bothwick

h

On Fri, 27 Jun 2008 10:44:00 +0100, Stroller wrote:

> > I'm sure the NSA would be happy to forego the prize and keep quiet
> > about
> > being able to break a secure cipher.
>
> I can't help wondering if - since P=NP is such a big problem - the
> advantages of having this knowledge in the public domain might
> override the advantages of mere spying.

I'm sure the holy grail for the NSA is a cipher that everyone thinks is
totally secure but they can break. These agencies aren't interested in the
greater good, only furthering their own goals.

--
Neil Bothwick

Tagline file empty. Please refill the bit bucket.

06-27-2008, 01:21 PM

Sebastian Wiesner

h

kashani <kashani-list@badapple.net> at Friday 27 June 2008, 02:28:21
> Here's a reference to the interesting meet-in-the-middle attack which
> reduced 3DES key space down to 112 bits from 192.
3DES always had an effective key size of 112 bits, because it uses the
original DES algorithm applied in the following scheme E1(D2(E1(M)) with
two different 56-bit DES keys. 3DES never had 192 bit keys.

The meet-in-the-middle attack has nothing to do with 3DES. In fact, 3DES
was designed the way it works now to _prevent_ meet-in-the-middle attacks.
Such attacks can be applied to ciphers, that apply a single algorithm with
two different keys: E1(E2(M))

Mathematical, the key size of the latter cipher is equal to 3DES: 56+56 =
112. But the latter cipher is vulnerable to meet-in-the-middle attacks,
which is why 3DES uses the second key to apply the DES decryption function
with a different key right between the consecutive DES encryptions.

> Obviously that was unknown when 3DES was built.
I doubt. If meet in the middle was unknown at the time of 3DES development,
we wouldn't have 3DES today, but 2DES, being as simple as E1(E2(M)).

--
Freedom is always the freedom of dissenters.
(Rosa Luxemburg)