G'day,
GIANT SNAKEOIL SLICK THREATENS COAST OF FIREWALLS LIST
Authorities Blame the NSA
Good evening, viewers...
In light of the many _many_ odd views that have recently been espoused in
the name of cryptography, I am forced to (yet again) pretend to know
something about this field.
In no order:
[Larry Paul]
>Wouldn't 4 kb take a gazillion years to decrypt?
Yes, assuming that the algorithm is 'strong'. Put it this way - keylength is
one part of a large number of factors that affects the strength of a cipher.
A cipher with a 4kb key could be anywhere from impossible to decrypt (<4kb
message encrypted with 4kb truerandom OTP) to amazingly easy (XOR with a 4kb
block). For a real algorithm, though, 4kb is way off the scale in terms of
security for a symmetric cipher. That's where we start saying things like
"even if every atom in the universe were actually a supercomputer then it
would still not be done before heat death".
[Also Larry]
> Is it true that as the key expands bit-wise, the factoring time increases
at
> a non-linear rate?
Yes. It's exponential time. In other words, it's about twice as hard to
factor a 513 bit number as a 512 bit one.
[Fred Avolio]
>But it would be very, very, *very* secure.
And would undoubtedly NOT make the system it was used in secure. This is not
really aimed at Fred, since he knows this, but it's really important to
remember that strong crypto is NOT NOT NOT NOT NOT a panacea. Just because
you have amazing crypto doesn't mean your data isn't at risk. Cryptographic
systems are hard and people make mistakes all the time. The actual cipher is
rarely the bit that falls over.
[Renee Lee]
> Not quite, With the availability of Massively Parallel Processors capable
of
> Gig-instructions
> per second you could find the key in a shorter time than you may think.
No. You couldn't. Brute forcing a 4kb key is not possible without a trapdoor
or flaw in the algorithm. IOW - even taking factoring as an example...
Quantum computing may become real. This effectively square roots the
complexity of an arbitrary calculation. That makes a 4096 bit number as hard
to factor as a 2048 bit one. Big deal. 2048 bits is well outside the realms
of possibility with an amazing new algorithm for factoring.
[Martin]
> However, since encryption is typically based on large primes and
> factoring them together,
Odd. This statement is really wrong...
> Of course, storage
> isn't keeping up with Moore, so that does tend to slow things down a
> bit,
Whereas this one is quite incisive.
Only one class of encryption (Public Key) is based on messing about with
large primes ('factoring' them is really easy - I have an O(n) algorithm, if
you're interested ;). I know of no symmetric ciphers that have anything to
do with large primes or factoring.
Your storage comment is really clueful. Many of the better than brute force
attacks that cryptographers or mathematicians dream up involve vast amounts
of storage, for pre-computed data. As an example, unix passwords are
trivially attacked by having a dictionary of hashed english words in O(n)
(very good time, requires storage). That's why they "salt" the word before
they hash it - to make it harder to mount this attack - you'd need to have
one copy of the dictionary per salt (which is many). The space requirements
for some of the attacks against AES with reduced rounds, for example, were
Just Silly.
[Rick]
> However, to my knowledge your
> government in conjunction with IBM has allready made a quantum computer
with
> 4 atoms, and the swiss have one with 11, at the last count. They work via
> utilising quantum theory to perform calculations. The upshot of this is
that
> any calculation, no matter how large, is carried out
instantanesously......
This is a very common misconception about quantum computing. Shor's
algorithm is proved to be able to reduce the factoring problem from
exponential time to polynomial time. Poly time does NOT equal instant
success. The comparision I tend to go with is that we can expect RSA style
keys to be worth about half their "weight" - 4096 -> 2048 in terms of
"difficulty". I'm afraid that I have no academic reference for this
assertion, however.
And finally....
[Larry again]
> Actually there IS sort of a hole in MS Products (NT) concerning an NSA
> crypto key placed there BY Microsoft FOR the NSA.(documented) I believe
Ben
> N. or Bernd E. has more info on that. Or is anyone else familiar with
that?
Assuming that I'm Ben N, please don't drag my name into THAT sorry bucket or
rumour and innuendo. I did enough research into that issue to convince
myself that it's bunk (but I've never been a huge fan of NSA conspiracy
theories). The NSA Key is used so that the NSA can insert their own
classified crypto into Windows. This is important, because certain levels of
data in the US cannot be protected by non-classified algorithms. End of
story.
Anyway, I'd better not go on - the message length troll will catch and eat
me.
Cheers,
--
Ben Nagy
Marconi Services
Network Integration Specialist
Mb: +61 414 411 520 PGP Key ID: 0x1A86E304
-
[To unsubscribe, send mail to [EMAIL PROTECTED] with
"unsubscribe firewalls" in the body of the message.]
