Les wrote:
On Wed, 2007-01-17 at 11:50 -0600, Marc Schwartz wrote: Snip
And that is dedicating the entire 17 TFLOP system just to break
_one_ key.
The current concensus age of the universe in years:
1.37e+10
Nuff said?
snip
No one has ever broken a crypto system by pure brute force, no matter
what you may think. This is an argument put up by the uninitiated
to substantiate their belief that they are secure.
I never stated that any crypto system has been "broken" using brute
force. Breaking an algorithm or system infers that something
meaningfully short of brute force at the advertised key length is an
alternative.
There are dozens of different algorithms used, purmutations of how
systems are broken and in any event encryption is not just the XOR of
a random stream with data any longer (although that is used in some
moderately secure systems).
There are many methods used for engaging in cryptanalytic attacks and
anyone with 30 seconds of Google time can easily locate many of them.
However, the notion of "breaking" reasonably strong crypto is predicated
not on the system being rendered "transparent", but on the effective
strength of the system relative to it's advertised key length.
Take a system using a 256 bit key length and come up with an approach
such that the complexity to decrypt the ciphertext would be no worse
than that of a 200 bit key length, and the system would be labeled as
having been broken. However, even at a 200 bit key length, the system
would still require longer than the age of the universe on your hardware
to brute force.
This was the issue with CMEA. It had an advertised key length of 64
bits, but weaknesses in the algorithm reduced the effective key length
to 24 or 32 bits, which is short enough to enable even moderately
powered hardware to "break it" in a usable time frame.
Using your 17 TFLOP system, it would be able to brute force CMEA based
crypto (at the 32 bit figure) in:
Keyspace:
2 ^ 32
[1] 4294967296
Time to brute force in seconds:
(2 ^ 32) / (17 * (10 ^ 12))
[1] 0.0002526451
So, yes, if one is using their CMEA encrypted digital cell phone, the
NSA could easily be engaging in real time, effectively transparent
decryption, since it would only take 0.00025 seconds to attempt all
possible keys on your hardware.
Now you have turned the problem into a bandwidth and capacity issue
given the tens of millions of such calls, not a crypto/computational
complexity issue.
The same reasoning is behind the replacement of WEP with WPA(2) for
wireless networking and of course DES with AES.
Again for some context, your 17 TFLOP system could brute force the
following key lengths in the given time frame. This is using the base 2
log of the system's performance per second times the number of seconds:
1 second:
> log((17 * (10 ^ 12)), 2)
[1] 43.9506
1 minute:
> log((17 * (10 ^ 12)) * (60), 2)
[1] 49.85749
1 hour:
> log((17 * (10 ^ 12)) * (60 * 60), 2)
[1] 55.76438
1 day:
> log((17 * (10 ^ 12)) * (60 * 60 * 24), 2)
[1] 60.34934
1 month:
> log((17 * (10 ^ 12)) * (60 * 60 * 24 * 30), 2)
[1] 65.25623
1 year:
> log((17 * (10 ^ 12)) * (60 * 60 * 24 * 365.25), 2)
[1] 68.86208
So, brute force approaches become rapidly impractical, if one is not
focusing on a specific "target" and simply casting a wide net. The
backlog of data in the latter scenario would rapidly become unmanageable.
Is it possible that the NSA has other, not yet public, means of engaging
in more sophisticated cryptanalytic attacks on current more commonly
used algorithms such as RSA, AES, etc.?
Sure.
Biham and Shamir published their papers on differential
cryptanalysis in the late 80's/early 90's, even though IBM later
acknowledged they knew about it as early as 1974, which is certainly
well after NSA mathematicians knew about it. Anyone knowing the history
of DES will be well familiar with this.
Anyway, if you feel secure, good for you. I, however, feel that we
all are vulnerable, and that each of us needs to make our own
assessment.
I am more concerned with the idiots walking around with laptops with
unprotected data and the loss of that data to folks with less than
honorable intentions. That has happened more in the past year or so than
should have been allowed and in my mind, presents a more contemporary
and realistic threat to my privacy.
But, let's say that rather than your 17 TFLOP machine, the NSA's
basement is filled with large scale quantum computers instead.
If that was reality, then all bets are off, because quantum computers
would be reasonably expected to render all current and generally
available cryptosystems useless.
In that case, I wouldn't worry about them having backdoors into
operating systems or even co-opting Intel, AMD, Broadcom and the other
chip makers to put backdoors in their chips.
The NSA wouldn't need them.
My knowledge was hard won, and is valid. Perhaps yours is just as
valid to you. I wish you all the best. I hope that the people
concerned do their homework and help all of us attain the state you
now enjoy.
Perhaps.
Regards,
Marc Schwartz
