Cryptography-Digest Digest #514, Volume #13 Sun, 21 Jan 01 09:13:01 EST
Contents:
Re: 32768-bit cryptography ("Wouter")
Re: Kooks (was: NSA and Linux Security) (digiboy | marcus)
Re: 32768-bit cryptography ("Wouter")
Re: using AES finalists in series? ("Gary Watson")
Re: Dynamic Transposition Revisited (long) (Mok-Kong Shen)
Re: using AES finalists in series? (Mok-Kong Shen)
Re: using AES finalists in series? (Mok-Kong Shen)
Re: using AES finalists in series? (Mok-Kong Shen)
Re: using AES finalists in series? (Mok-Kong Shen)
Re: Differential Analysis (Simon Johnson)
Re: 32768-bit cryptography (Richard John Cavell)
Re: brute force and Moore's law (was Re: 32768-bit cryptography) (Paul Rubin)
Re: 32768-bit cryptography (Paul Schlyter)
----------------------------------------------------------------------------
From: "Wouter" <[EMAIL PROTECTED]>
Subject: Re: 32768-bit cryptography
Date: Sun, 21 Jan 2001 13:09:53 +0100
>> > 1024 bit cryptography (If you are talking symmetric) will never be
broken
>> Pfffft!
>>
>> Computing power doubles every 18 months or so. Brute force is all you
>> need if you have enough power. Within your lifetime, 3xDES will be
>> completely crackable.
>>
>I doubt it. Brute force cracking of a cryptosystem is an *exponential
>time* solution to the cryptanalysis problem. Every doubling in the
>number of bits in a cryptographic key squares the amount of time you
>need to brute force it. Do some careful arithmetic and even with your
>(overly optimistic) assumption that Moore's law will hold indefinitely,
>you'll find nearly everyone on this newsgroup today will be dead by that
>time. And parallelism will not help; it merely linearly multiplies your
>computing power. You obviously have no exposure whatsoever to
>algorithmic complexity theory and more faith in the progress of
>technology than knowledge of the implications of an algorithm being
>O(2^N). Besides, it's highly doubtful that Moore's law will continue
>for more than ten years, considering that quantum effects are beginning
>to catch up with microprocessor fabrication and the heat being produced
>by such super-processors is becoming overwhelmingly excessive. Sometime
>soon we'll start having microprocessors you could strap on the nose of
>the Space Shuttle which you could still use after orbital reentry!
>(...)
According to me, we can learn from this thread that if we ever create an
32879-bit cryptography algorithm, it will never be crackable. Is it possible
to create such an algorithm? Even 8192 bits or less will probably be good
enough. If it's not possible, why not? Or does it exists already? I'm
curious.
Wouter
------------------------------
From: digiboy | marcus <[EMAIL PROTECTED]>
Subject: Re: Kooks (was: NSA and Linux Security)
Date: Sun, 21 Jan 2001 12:05:18 GMT
In article <94e1fj$u6l$[EMAIL PROTECTED]>,
Greggy <[EMAIL PROTECTED]> wrote:
> Give it a rest, will you?
Why do you end off each of your posts with such an idiotic line as
such? And isn't it questionable as to the relevance this all has with
cryptography now? You've managed to drag it _completely_ away from
anything relevant, into kookville.
--
[ marcus ] [ http://www.cybergoth.cjb.net ]
[ ---- http://www.ninjakitten.net/digiboy ]
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Wouter" <[EMAIL PROTECTED]>
Subject: Re: 32768-bit cryptography
Date: Sun, 21 Jan 2001 13:25:00 +0100
Wouter wrote in message <94ejfh$2f6$[EMAIL PROTECTED]>...
>According to me, we can learn from this thread that if we ever create an
>32879-bit cryptography algorithm, it will never be crackable. (...)
Sorry, that had to be 32768, off course.
------------------------------
From: "Gary Watson" <[EMAIL PROTECTED]>
Subject: Re: using AES finalists in series?
Date: Sun, 21 Jan 2001 12:34:42 -0000
"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> >After following AES for the last two years, we assess the
> >possibility that the proposers of each algorithm are shills for NSA at
about
> >5%, and 10% for Rijndael since it was actually chosen by NIST.
>
> I know it is just an example, but it seems to be the wrong way to
> think about the problem. It is not necessary for somebody to be a
> shill for NSA to create a cipher which has unnoticed faults. That
> means the probability of having a weak cipher is higher than the
> probability of being a shill, to an extent which we can neither
> estimate nor quantify.
At some point or another, my hypothetical terrorist group would have to make
an assessment as to whether they could "trust" their chosen crypto system
with their lives and the lives of their followers, plus more importantly to
them, their mission to kill all of us infidels. Whether they reduce their
assessment into numbers, or they simply wave their hands and talk in terms
of generalities, they still need to decide, yes or no. I'd speculate that
this type of group would be most concerned with deliberate weaknesses,
rather than the possibility that any of the five groups of respected
cryptographers would propose a cipher with some kind of mathematical flaw.
Myself, I'd go the other way and suspect that NSA, GCHQ, et al, would have
come up with two or three revolutionary breakthroughs which have some
bearing on solving one or more of the AES finalists (my only evidence is the
historic track record), but maybe it's less likely that they have clever
tricks for all five. The other thing which I didn't mention was the
possibility that NSA has tricks which greatly reduce the compute time to
solve one or more of the AES candidates, but perhaps solving my hypothetical
videoconferencing system is only of tactical value if it can be done
quickly, say, within 3 days of interception, and the reduction in solution
time might be negated by the superencipherment.
> >On the other hand, using a pair of high-end Xilinx FPGAs, it's possible
to
> >put all five AES finalists in series, pipelining them such that there is
no
> >loss of throughput in a streaming video application. The Great Satan has
> >thoughtfully published the VHDL for all five finalists, so the R&D cycle
> >would be negligible. Using a static RAM based FPGA has the advantage
that
> >it can be quickly zeroized if capture seems imminent or it could even
> >zeroize itself after a set period of time.
>
> What is the point in erasing devices which contain public algorithms?
> Only keys (and data) need be protected.
Only because I'd store the keying data in the internal block RAMs of the
FPGA so that it never need exit the chip, and you have to load the entire
design at the same time. Also, maybe at synthesis time when I'm making a
new batch of keys, I might shuffle the order of the ciphers, or add multiple
instances of one or more of them. Or maybe on a lark I'd sometimes xor the
cipher text with "BITEMEMOSSADBITEMEMOSSAD..."
Which brings up another amateur question -- in the simple case of using one
instance of Rijndael, let's say I have allocated 256 bits per day for keying
(the RAM inside the FPGA has loads of room for a monthly key schedule). Am
I better off using 128 bit keys and changing them twice a day, or using 256
bits and changing them once a day? In general, how do you calculate this?
Can I assume that it depends upon quantity of transmitted data? (I suppose
the system must be allowed to transmit dummy data 24x7 to reduce traffic
analysis possibilities).
> >So, if the above guesstimates of the liklihood of the candidates being
> >deliberately and covertly weakened are accurate, and assuming that
separate
> >randomly generated keying data were used for each cipher, the
probablility
> >that all five systems are compromised and thus of the eternal Boyzone
> >torture, is the product of the probabilities or 1 in 1.6 million, which
> >frightening though it is, is within reason.
>
> I think not. First, for the result to be correct, each of the
> individual probabilities would have to be independent, and I think we
> do not know that. When we have designs based on generally similar
> concepts of ciphering, the possibility of new generally-applicable
> attacks cannot be dismissed.
That's maybe the biggest risk, isn't it? Well, not the biggest really. The
biggest risk is that a hostile foreign service will insert a human spy
somewhere into the cryptonet and reveal the contents of it, or use remote
interception techniques to capture compromising EMI, mitigated somwhat by
the fact that my hypothetical videoconferencing system would be connected to
the ISP using a covertly buried, alarmed, and boobytrapped fiber optic
cable. Of course I'd have to kill the geezer who buried the cable for me...
> >Assuming all of the above is correct, another question I'm not competent
to
> >answer is how strong this cipher chain would be -- with each cipher at
256
> >bits, is it on the order of (2^256)^5, or is it closer to (2^256) * 5 ?
>
> Everything depends upon weakness which we do not know. If we do not
> know the weakness, we cannot compute the probability that it might
> exist. If we do know the weakness, there is no probability about it
> at all: it is either there or not.
Sorry, I changed subjects. I was digressing into the impact of
inefficiently using the available keying bits. My fuzzy point was that
there is so much keying data available that using it efficiently is beside
the point.
> I am that nobody. I routinely use message keys of 992 bits -- not
> because I think any fewer could be brute-forced, but instead because
> doing this can avoid an internal expansion stage which conceivably
> might add weakness. I may thus possibly avoid a form of technical
> weakness, and I am quite willing to impose a 128-byte key burden to do
> that. The era of needing keys to be "efficient" is long gone.
Amen. I think any secure system of distributing keys should not be human
readable, and about the smallest PROM one can buy these days has many tens
of thousands of bits in it. The cheapest parts are in the megabit range.
The top-of-the-range Xilinx-2 FPGA parts have 4.5 megabits of RAM, though
some of this would be needed for the algorithms.
--
Gary Watson
[EMAIL PROTECTED] (you should leave off the digit two for email)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sun, 21 Jan 2001 13:46:09 +0100
"John A. Malley" wrote:
>
[snip]
> This is only a first step in sizing up the dynamic transpositioning
> cipher for cryptanalysis. Does this generalize to other shuffling
> algorithms driven by linear congruential sequences? How does the choice
> of PRNG affect the number of permutations possible with a shuffling
> algorithm? Does the fraction of possible permutations achieved by
> Algorithm P driven by such a simple LCG PRNG still prevent any attacks
> other than "brute-force"? Is there a "fairly simple mathematical rule"
> relating characteristics of permutations produced by Algorithm P driven
> by this simple LCG PRNG (such as dependencies in the kinds of cycles in
> the permutations generated successively)? Don't know. Maybe others will
> see something to extend this.
I think that DT can't be provably secure because there
simply can't exist any magic that can turn something that
is predictable to unpredictable. Practically, though,
using double (or perhaps more) permutations would render
the job of analysis more difficult. Of course, one should
consider using better pseudo-random sequences from the
outset, e.g. through combining a number of PRNGs.
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: using AES finalists in series?
Date: Sun, 21 Jan 2001 13:45:52 +0100
Terry Ritter wrote:
>
> in sci.crypt "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>
> >Terry Ritter wrote:
> >> AES is of course an attempt to limit cipher development, ...
> >
> >No, it's an attempt to control the cost of implementation and
> >operation of commercial encryption by promoting interoperability.
> >
> >It's similar to the function of standards for screw threads,
> >programming languages, etc.
>
> The two statements are not necessarily contradictory: One could be
> the cover story; the other addresses what could be an internal agenda.
>
> The only standard needed for ciphering is a standard cipher
> *interface*, not a standard cipher. We have to deliver keys; we might
> as well deliver the name of the desired cipher, or actual running
> code. If we had a standard interface, we could change ciphers easily
> if something went wrong.
>
> But we get is a standard cipher, and *not* a standard interface. Odd.
But the common people would need something which they can
simply pick and obtain direct interoperability. Consider
the follow (a bit far-fetched) analogy: You have a kitchen
appliance with a plug that is double as big as the socket
at the wall and there is a standard interface (an adapter)
that allows you to connect. Of course that adapter functions.
But it's rather annoying, if not inconvenient, isn't it?
(Note my stress on 'common people'.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: using AES finalists in series?
Date: Sun, 21 Jan 2001 13:46:02 +0100
"Douglas A. Gwyn" wrote:
>
[snip]
> Thus my advice is to use all the key bits
> in a single unified method instead of partitioning
> them among several smaller-keyed independent methods.
Right. But in a situation where the first option is
not (yet) available, one is left with the second option.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: using AES finalists in series?
Date: Sun, 21 Jan 2001 13:45:47 +0100
Terry Ritter wrote:
>
[snip]
> That idea that we need "key efficiency" represents a time now long
> gone. In the context of modern communications, why should anyone be
> anxious about sending additional keying material? Do we really worry
> about sending another 256 bits, or 1024 bits, or whatever? This is
> message key material, random and endless; we can take all we need, and
> send it at almost no cost.
>
> There is no need to divide a single minimum keyspace into use by
> multiple ciphers. Just "bite the bullet" and send a key for each
> cipher! Make each random, independent, and as large as it needs to be
> to give the associated cipher stand-alone strength.
[snip]
And we can also change the keys sufficiently often to
reduce the chance (and the fear) of differential analysis
and the like to negligibility.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: using AES finalists in series?
Date: Sun, 21 Jan 2001 13:45:57 +0100
Terry Ritter wrote:
>
[snip]
> I have no problem at all with the idea of a modern communications
> system transporting whatever amount of key each cipher needs, and
> neither should anybody else.
I suppose that one could also economize somewhat, if
necessary, by employing master keys to generate the actual
keys for use.
M. K. Shen
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Sun, 21 Jan 2001 12:54:10 GMT
In article <93b7qo$i4q$[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> Simon Johnson wrote:
> > Bryan Olson wrote:
> > > One good on-line reference to mostly off-line sources is Bruce
> > > Schneier's self-study course in block cipher cryptanalysis.
> > > See:
> > >
> > > http://www.counterpane.com/self-study.html
>
> > I've looked at this, and its only any good if you know how
> > to do/how to work the attacks :)
>
> It's tough to know how much patience to have with the
> clueless newbie cipher designers, or worse - the clueless
> old-timers. There's nothing wrong with being a newbie or
> asking naive questions, but the inside of cipher is a
> dangerous place to play.
I differ in opinion slightly (because i'm learning :) ) There is
nothing wrong with designing a cipher to try and futher your knowledge
in the subject. What's 'dangerous' is claiming your cipher is completly
indestructable and recommending companies use it without having any
idea about cryptanalysis.
Would you agree with this?
> Last month we saw a thread eighty-some posts long, mostly
> devoted to convincing a couple guys who regularly post
> ciphers that a purely linear scheme is weak. Eventually
> they seemed to get that the particular method is worthless,
> but I don't think it dawned on them the extent to which they
> were fooling themselves. I wonder if it's just sci.crypt,
> or if they also send neurologists their new techniques for
> brain surgery, or NASA their designs for spaceships.
Anyone who does that is stupid. Claiming something is incorrect (to
test your knowledge) is okay provided your willing to accept that your
likely to be wrong. I have been guilty of this myself, numerous times.
But one can learn by their mistakes.
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Richard John Cavell <[EMAIL PROTECTED]>
Subject: Re: 32768-bit cryptography
Date: Mon, 22 Jan 2001 00:13:47 +1100
On Sun, 21 Jan 2001, Dido Sevilla wrote:
> You obviously have no exposure whatsoever to algorithmic complexity
> theory
You obviously have no exposure whatsoever to the future, and we differ in
our optimism of it.
> O(2^N). Besides, it's highly doubtful that Moore's law will continue
> for more than ten years, considering that quantum effects are beginning
> to catch up with microprocessor fabrication and the heat being produced
> by such super-processors is becoming overwhelmingly excessive.
A 1.5 Gigahertz Pentium 4 core has been demonstrated with no heatsink or
fan running continuously on an isotopically pure piece of silicon.
=============================================================
Richard Cavell - [EMAIL PROTECTED]
Newsgroups - Please keep any discussion on the group, and copy your
replies to me via email. (Server problems). Sending me bulk email
guarantees a nasty response.
Judge Thomas Penfield Jackson on Bill Gates: "He has a Napoleonic concept
of himself and his company, an arrogance that derives from power"
=============================================================
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: brute force and Moore's law (was Re: 32768-bit cryptography)
Date: 21 Jan 2001 05:18:39 -0800
Eric Smith <[EMAIL PROTECTED]> writes:
> > There are good reasons for this: a 168-bit 3DES key isn't
> > that much more secure than a 112-bit 3DES key,
>
> Doesn't the 2^112 operation attack on 168-bit 3DES require
> 2^112 words of memory?
No, just 2^56 words. The same MITM attack as usually mentioned
against 2DES, more or less.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: 32768-bit cryptography
Date: 21 Jan 2001 13:45:39 +0100
In article <[EMAIL PROTECTED]>,
Richard John Cavell <[EMAIL PROTECTED]> wrote:
> On 20 Jan 2001, Paul Schlyter wrote:
>
>> Finally: is it reasonable to assume computing power will continue to
>> double every 18 months also for the next 84 years?
>
> Yeah, I think so. The technology researchers will probably
................
Yep, people think or believe various things about the future....
During my school years in the late 1960'ies, I was convinced that
manned exploration of Mars would start in the 1980'ies, and that by
now there would be permanent inhabitated colonies on both the Moon
and Mars....
You'll never know what actually will happen in the future....
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
