Cryptography-Digest Digest #967, Volume #12 Sat, 21 Oct 00 00:13:00 EDT
Contents:
Re: Encrypting large blocks with Rijndael (Tom St Denis)
Re: Dense feedback polynomials for LFSR (Joaquim Southby)
Re: Dense feedback polynomials for LFSR (Joaquim Southby)
Re: SDMI Successfully Hacked (Mack)
Re: How to post absolutely anything on the Internet anonymously (Anthony Stephen
Szopa)
Re: Encrypting large blocks with Rijndael (Mack)
Re: Dense feedback polynomials for LFSR ("Trevor L. Jackson, III")
Re: newbie pathetic question (Chris McKenzie)
Re: Dense feedback polynomials for LFSR ("Trevor L. Jackson, III")
Re: It's Rijndael (Chris McKenzie)
Re: My comments on AES ("Stephen M. Gardner")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Encrypting large blocks with Rijndael
Date: Sat, 21 Oct 2000 02:05:04 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
>
> Ah, I'm sorry, I shouldn't have told you to check.
> It's obvious that you don't have time.
I don't want to be rude, are you being sincere or what?
> What I meant was, I believe that "40% slower" is a
> correct prediction for encrypting with 256-bit blocks
> as compared to 128-bit blocks. That is because each
> round does work proportional to the block size.
>
> Therefore each round of 256-bit Rijndael is twice as
> slow as 128-bit Rijndael. To encrypt 256 bits, we
> call 128-bit Rijndael twice (assuming one of the
> standard modes) or 256-bit Rijndael once. Thus the
> total amount of work done is proportional to the
> number of rounds. 128-bit Rijndael has 10 rounds.
> 256-bit Rijndael has 14 rounds. Therefore 256-bit
> Rijndael takes 1.4 times as long as 128-bit Rijndael
> to encrypt the same amount of data, and is thus
> 40% slower.
>
> I hope that wasn't too long for you to read.
Yeah, ok is this a wise-crack remark?
Try this logic on for size... in each of those 14 rounds you are moving
TWICE the amount of memory. Thus you have more register usage, stalls
and latency.
I seriously doubt the difference is 40% exactly.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Date: 21 Oct 2000 02:20:11 GMT
In article <[EMAIL PROTECTED]> Tim Tyler, [EMAIL PROTECTED] writes:
>: One of the most straightforward ways of checking to see if a polynomial
>: is primitive is to use it as the tap sequence of an LFSR, plug in an init
>: vector, and start clocking. If one were to note not only the primitive
>: polynomials (i.e., those that made it to 2^n - 1 clocks before repeating
>: the init vector), but also those that happened to show a large state
>: space for that init vector (i.e., a large number of clocks before
>: repeating the init vector), a library of such sub-maximal LFSR's could be
>: built. [...]
>
>This is an exhaustive search.
I'm curious about your definition of "exhaustive search". Would
examining all the factors of a polynomial be non-exhaustive?
>You're never going to get vary large
>guaranteed minimum period,
As I've said before, some of the state spaces of non-maximal LFSR's can
contain almost all the possible state space of the given register --
sometimes up to 99% of it. The period of that state space is constant
providing your init vector is contained in the state space, "guaranteed".
>nor are you going to be able to use seeds off
>the path you test on without losing any guarantee of minimum period.
>
I thought the last paragraph in my post made it obvious that you didn't
need any init vector other than the one tested. The key for a
sub-maximal LFSR is the clock value, not the init vector.
>I expect most folks would simply choose a primitive polynomial,
>if this is the alternative.
>
If that's what makes most folks happy, fine. Some folks like to explore
areas off the beaten track.
>: With a maximal-length LFSR, the key is any number between zero and 2^n.
>: Advantage: very easy to choose a suitable key. With a sub-maximal LFSR,
>: the known init vector is seeded to the LFSR, then the LFSR is clocked a
>: number of times equal to the key value before using the stream output.
>: Advantage: key can be larger than 2^n since the clock count will
>: effectively be the key moduloed by the size of the state space.
>
>You call discarding much of the information in your key an "advantage"?
>
I misspoke on this; I was thinking of something else similar in nature.
The salient point that you missed here is that (key modulo state space)
reduces the actual key space to the size of the state space.
------------------------------
From: Joaquim Southby <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Date: 21 Oct 2000 02:32:58 GMT
In article <[EMAIL PROTECTED]> Trevor L. Jackson,
[EMAIL PROTECTED] writes:
>Let's see, we load the initial (known) state and clock a number of times equal
>to the 256 bit key value before using the stream output. Strange as it seems
>this actually works. By the time the PRNG is ready to use the value of the
>message to be encoded is guaranteed to have decayed to zero. Thus no valuable
>information will ever leak, even to the intended recipient. ;-)
>
>Even for a 64-bit key this is probably true ( ... pi seconds is a nanocentury
>... so the first message takes a couple millennia if the LFSR can be clocked at
>100 MHz.
>
>For a server doing 1,000 key setups/sec we use a 10-bit key ... so it can be
>cracked by hand?
>
Damn, Trevor, I wanted someone to actually try this without thinking
about it. Now you've let the key out of the register (to strain an
already cliched metaphor).
Seriously, you may have missed the first parts of the thread (or you are
wisely ignoring them). My arguments were that less-than-perfect
protection schemes should not be summarily dismissed, that there are many
instances where such schemes are sufficient for the task at hand. The
weakness you cite in Rip Van Winkling an LFSR also holds for a
maximal-length LFSR -- it takes a long time to do that counting on larger
registers. In cases where time is not a driving factor (and in smaller
registers than you cited), the counting becomes less of an irritant.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: SDMI Successfully Hacked
Date: 21 Oct 2000 03:25:01 GMT
>
>"Mack" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Officially - SDMI is alive and well
>> and may remain that way.
>>
>> Unofficially - It didn't have a prayer.
>> SDMI is deader than roadkill on the 610
>> loop in Houston, TX.
>> Mack
>> Remove njunk123 from name to reply by e-mail
>
>Maybe if all 450 cracks get posted here, SDMI will really die.
>
> *David Barber*
Simple crack
do random 1% phase shifts
and level shifts. Destroys
the watermark with minimal
distortion.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.freespeech
Subject: Re: How to post absolutely anything on the Internet anonymously
Date: Fri, 20 Oct 2000 20:26:12 -0700
jungle wrote:
>
> how this is better then old remailer method ?
> they are asking to use proxy ...
>
> Anthony Stephen Szopa wrote:
> >
> > How to post absolutely anything on the Internet anonymously
> >
> > http://www.sciam.com/2000/1000issue/1000techbus2.html
I am not terribly familiar with the remailer method. Sounds to me
that the remailer method is emailing data anonymously.
Whereas this system actually posts the data to numerous internet
servers where anyone can down load it while at the same time making
it highly unlikely that anyone, including the government, could
remove the information from all the servers.
While also providing to make it impossible for the server owner to
be held accountable since the server owner has no way of knowing
what is on their server since this file is encrypted.
Since the data is encrypted, no one knows what is contained in the
files unless they have the key.
The key is broken up into, say, 100 fragments, any of 20 will
generate the entire key. Thus like the encrypted file, removing the
fragmented key from numerous servers will also prove very difficult
if not impossible even for a government.
It is the Publius software that will search the net for the file and
the key fragments and will decrypt the file and download it to your
web browser.
I am not sure, but using an anonymous service may not be required
but it does add another layer through which it will be very
difficult to trace the poster through. It was suggested that a
poster could use Publius while posting through a public host. This
would certainly anonymize the poster.
But the power of Publius is that the file can be posted on the
Internet and even the government will not be able to censor it, even
if the post is deemed illegal.
Power to the People!
It is a little more involved than this but these are some of the
characteristics and advantages.
I have downloaded the paper but have not had time to read it yet.
It is 14 pages long.
But Scientific American thinks it is a big deal.
That is enough for me to look into it further.
"INTERNET_ANONYMITY
Speech without Accountability
New software makes it nearly impossible to remove illegal material
from the Web--or to find out who put it there"
Scientific American
http://www.sciam.com/2000/1000issue/1000techbus1.html
Publius Site
http://www.cs.nyu.edu/~waldman/publius/publius.html
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Encrypting large blocks with Rijndael
Date: 21 Oct 2000 03:36:21 GMT
>Runu Knips wrote:
>>
>> John Myre wrote:
><snip>
>> > Do you mean to say that encrypting with larger blocks
>> > is more secure? (If not, why not go with smaller blocks?)
>>
>> Yep.
><snip>
>
>Fine. Under what circumstances would the increase in
>security over 128-bit blocks be justified?
>
>JM
>
>
On the issue of efficiency, going with larger block sizes
slows Rijndael considerably. In addition to the increased
number of rounds you also have a larger number of steps
in each round. The number of lookups in each round is
directly proportional to the block size.
Larger block sizes would be appropriate when doing
MACs. Or if large quantities of data are being encrypted
under the same key. By large I mean on the
order of 2^64 or more.
But either case you are probably better off switching to a
different method. In the first case a secure hash and
in the second case a cipher designed for the larger
block size.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
Date: Fri, 20 Oct 2000 23:41:05 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Tim Tyler wrote:
> Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Joaquim Southby <[EMAIL PROTECTED]> wrote:
> :> : In article <8sg0h7$a1b$[EMAIL PROTECTED]> Tim Tyler, [EMAIL PROTECTED] writes:
>
> :> :>The question then becomes: how do you have the faintest idea what the
> :> :>period of the LFSR is without looking at the corresponding polynomial's
> :> :>properties, and checking to see whether it is primitive.
> :> :>
> :> :>Without performing such a procedure, I don't see how you can claim that
> :> :>99% of the state spece is covered from a given position - unless you
> :> :>perform an exhaustive search - something which becomes impractical as
> :> :>the size of the register grows.
>
> [snip exhaustive search]
>
> :> : With a maximal-length LFSR, the key is any number between zero and 2^n.
> :> : Advantage: very easy to choose a suitable key. With a sub-maximal LFSR,
> :> : the known init vector is seeded to the LFSR, then the LFSR is clocked a
> :> : number of times equal to the key value before using the stream output.
> :> : Advantage: key can be larger than 2^n since the clock count will
> :> : effectively be the key moduloed by the size of the state space.
> :>
> :> You call discarding much of the information in your key an "advantage"?
>
> : Let's see, we load the initial (known) state and clock a number of
> : times equal to the 256 bit key value before using the stream output.
> : Strange as it seems this actually works. [snip tongue in cheek analysis
> : based on large time taken]
>
> : Even for a 64-bit key this is probably true ( ... pi seconds is a nanocentury
> : ... so the first message takes a couple millennia if the LFSR can be
> : clocked at 100 MHz.
>
> You seem to think it takes a long time to calculate the result of an
> LFSR stepping forwards a large number of steps.
Not quite. I think it takes a long time to "clock a number of times equal to the
key value".
>
>
> This is not so - you can clock an LFSR forwards 2^100 steps in the blink
> of an eye, bu exploiting the fact that it's a linear operation, and
> multiple applications of it produce linear operations (all of which can be
> represented concisely by matrix operations).
Yes.
I've implemented this kind of mechanism for arbitrarily large registers. I even
have an x86/MMX implementation that is reasonably fast. But the time is not linear
for an arbitrary number of steps. IIRC it's O(N^2) space and O((N^4)/2) time. On
current machines the space is hardly a problem, but the time grows uncomfortably
quickly. Of course this is still much smaller than counting which is exponential
on N.
>
>
> The original idea makes no sense, but execution time does not appear to be
> a problem with it.
In the general case general it's not a problem, but as stated by the OP it is. I
suspect the OP has been using small registers and neglected to consider the effect
of scaling on feasibility.
------------------------------
From: Chris McKenzie <[EMAIL PROTECTED]>
Subject: Re: newbie pathetic question
Date: Fri, 20 Oct 2000 20:49:35 +0000
Danilo wrote:
> I wonder why is arithmetic coding not used to scramble messages ?
>
> If I arithmetic compress a message, but using a frequency table which
> is actually my key (both in the frequencies and in the order of the bytes),
> wouldn't it be very hard to decrypt ?
>
> Excuse in advance for my pathetic ignorance of the matter.
>
> Danilo
This is actually the cause of some exciting research I have been doing. If
I here you correctly you are implying that the use of a one time pad wherein
you randomly enumerate a sequence of elements in a set (let's say an alphabet)
to the length of the plaintext. After this there should be a 1/26 ratio
(using an english alphabet) when doing a frequency analysis of the
ciphertext. This has upto this point been seen as perfect encryption.
However the flaw here is that you have to transmit the one time pad. In other
words you have to secure a connection to send the pad. This in its essense
defeats the true purpose of cryptography because if one was to use
cryptography they have already implied that their connection with the reciever
is insecure. If this is so, a one-tiem pad offers the same kind of security
as sending say every odd letter and then every even letter. All that Eve has
to do is listen in to both transmissions and the painstaking effort is gone
because she can easily reconstruct the message. My research falls under many
theoretical implications that may be incorrect so I do not want to embarass
myself by telling you what it is. However if you are duly interested in it
you can e-mail me privately.
------------------------------
Date: Fri, 20 Oct 2000 23:53:41 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Joaquim Southby wrote:
> In article <[EMAIL PROTECTED]> Trevor L. Jackson,
> [EMAIL PROTECTED] writes:
> >Let's see, we load the initial (known) state and clock a number of times equal
> >to the 256 bit key value before using the stream output. Strange as it seems
> >this actually works. By the time the PRNG is ready to use the value of the
> >message to be encoded is guaranteed to have decayed to zero. Thus no valuable
> >information will ever leak, even to the intended recipient. ;-)
> >
> >Even for a 64-bit key this is probably true ( ... pi seconds is a nanocentury
> >... so the first message takes a couple millennia if the LFSR can be clocked at
> >100 MHz.
> >
> >For a server doing 1,000 key setups/sec we use a 10-bit key ... so it can be
> >cracked by hand?
> >
> Damn, Trevor, I wanted someone to actually try this without thinking
> about it. Now you've let the key out of the register (to strain an
> already cliched metaphor).
>
> Seriously, you may have missed the first parts of the thread (or you are
> wisely ignoring them). My arguments were that less-than-perfect
> protection schemes should not be summarily dismissed, that there are many
> instances where such schemes are sufficient for the task at hand.
I suspect the optimal application for such schemes is as decoys and chaff. One might
utilize under-strength systems to saturate an opponent's cryptanalytic capability
with traffic using many (00s or 000s?) such schemes, expecting that the opponents
would have to spend considerable effort trying to map cipher systems onto message
sensitivity.
Of course one needs to insure that such under-strength systems only handle laundry
lists rather than launch codes. But this is precisely the kind of problem that
bureaucracies are created to solve. They are good a both generating large quantities
of trivia and assigning it to appropriate bins. Like an OS that spends an
appreciable fraction of the machine's capacity just keeping track of itself when no
applications are running.
> The
> weakness you cite in Rip Van Winkling an LFSR also holds for a
> maximal-length LFSR -- it takes a long time to do that counting on larger
> registers. In cases where time is not a driving factor (and in smaller
> registers than you cited), the counting becomes less of an irritant.
Perhaps I did miss something. I don't see a need to perform counting during setup of
a maximal-length or near-maximal-length LFSR. Any but a trivially small (1-2) number
of keys is a suitable key. So why does the RVW weakness hold for maxlen LFSRs?
------------------------------
From: Chris McKenzie <[EMAIL PROTECTED]>
Subject: Re: It's Rijndael
Date: Fri, 20 Oct 2000 20:58:08 +0000
Roger Schlafly wrote:
> Joseph Ashwood wrote:
> > plainly that the ok of RU-486 was "wrong", while Gore praised it (Source:San
> > Jose Mercury News),
>
> Big deal. Clinton also held up RU-486 for 8 years, so I can't see
> the pro-abortion folks getting excited about this issue.
>
> There is a whole assortment of pluses and minuses for Gore and
> Bush. But on the subject of crypto and privacy, Clinton/Gore/Reno/Freeh
> are the worst administration ever. Bush couldn't possibly be as bad.
However one thing to note is that Bush may go key escrow. Ralph Nader wouldn't.
------------------------------
From: "Stephen M. Gardner" <[EMAIL PROTECTED]>
Subject: Re: My comments on AES
Date: Fri, 20 Oct 2000 23:06:38 -0500
==============61093AFFF1F137D86681EAC3
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Runu Knips wrote:
> Bruce Schneier wrote:
> >
> > Recently there was a thread where people discussed my scant comments
> > on AES. Those who expected them to appear in Crypto-Gram were
> > correct:
> >
> > http://www.counterpane.com/crypto-gram-0010.html#8
>
> Seems to me that Schneier also believes Rijndael is breakable.
Let's read what he actually said: "Rijndael was not my first choice,
but it was one of the three algorithms I thought suitable for the
standard. The Twofish team performed extensive cryptanalysis of Rijndael,
and will continue to do so. While it was not the most secure choice (NIST
said as much in their report), I do not believe there is any risk in using
Rijndael to encrypt data.
Now what makes you think that he said it was breakable.
--
Take a walk on the wild side: http://www.metronet.com/~gardner/
There is a road, no simple highway, between the dawn and the
dark of night. And if you go no one may follow. That path is
for your steps alone.
The Grateful Dead ("Ripple")
==============61093AFFF1F137D86681EAC3
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Runu Knips wrote:
<blockquote TYPE=CITE>Bruce Schneier wrote:
<br>>
<br>> Recently there was a thread where people discussed my scant comments
<br>> on AES. Those who expected them to appear in Crypto-Gram were
<br>> correct:
<br>>
<br>> <a
href="http://www.counterpane.com/crypto-gram-0010.html#8">http://www.counterpane.com/crypto-gram-0010.html#8</a>
<p>Seems to me that Schneier also believes Rijndael is breakable.</blockquote>
Let's read what he actually said: "<font size=+1>Rijndael
was not my first choice, but <b><i><u>it was one of the three algorithms
I thought suitable for the standard</u></i></b>. The Twofish team performed
extensive cryptanalysis of Rijndael, and will continue to do so. While
it was not the most secure choice (NIST said as much in their report),
<b><i><u>I do not believe there is any risk in using Rijndael to encrypt
data.</u></i></b></font>
<p>Now what makes you think that he said it was breakable.
<p>--
<br>Take a walk on the wild side: <A
HREF="http://www.metronet.com/~gardner/">http://www.metronet.com/~gardner/</A>
<p>There is a road, no simple highway, between the dawn and the
<br>dark of night. And if you go no one may follow. That path is
<br>for your steps alone.
<br> The Grateful Dead ("Ripple")
<br> </html>
==============61093AFFF1F137D86681EAC3==
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
