Cryptography-Digest Digest #223, Volume #9 Thu, 11 Mar 99 10:13:03 EST
Contents:
Re: Where have I seen this? (Dan S. Camper)
Re: updated rc4/5/6 code, birthday attack ("Christian König")
Re: Intel/Microsoft ID (David Lesher)
Re: Cyclotomic Number Generators (R. Knauer)
Re: Testing Algorithms [moving off-topic] (Doggmatic)
Re: Limitations of testing / filtering hardware RNG's ("Trevor Jackson, III")
Re: Limitations of testing / filtering hardware RNG's (Tom Thomson)
Re: Where have I seen this? ("almis")
Re: Testing Algorithms [moving off-topic] (Patrick Juola)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Dan S. Camper)
Subject: Re: Where have I seen this?
Date: Thu, 11 Mar 1999 07:23:23 -0600
In article <7c7ghs$so4$[EMAIL PROTECTED]>, "almis" <[EMAIL PROTECTED]>
wrote:
>Dan S. Camper wrote in message ...
>|All:
>|
>|Recently I've read -- somewhere -- about a scheme that supposedly allows
>|you to "reuse" a chunk of random numbers. The algorithm, if I remember
>|correctly, went something like this:
>|
>|1) Generate a bunch of random numbers (a pad).
>|2) Generate random offsets into the pad.
>|3) When you need a random byte, extract the bytes from
>| the pad at the offsets and XOR them together to get
>| a single output byte.
>|4) Increment all the offsets, wrapping them to zero
>| in case of overflow.
>|5) The total key, in this case, becomes the pad and
>| the original list of offsets. I believe that the
>| original discussions indicated that the pad could
>| be reused for many messages and/or users, in which
>| case only the offsets need to be transmitted as keys.
>|
>|I spent quite a while crawling through Deja News and a couple of other
>|archives trying to find discussions about this, with no luck. Does anyone
>|have any further information about it or can direct me to another source?
>|
>|Thanks for your time!
>|
>|DSC
>|
>|____________________________________________________________________
>|Dan S. Camper [EMAIL PROTECTED]
>|Borrowed Time, Inc.
>
>This, Dan, is a rotor machine.
>Efficiency requires that the rotors be 'parallel' stepped. and the most
>efficent form
>is when the length of the rotors are relativley prime.
>Randomly selecting starting points for each rotor (pad) has the disadvantage
>of possibly using the same section of several pads for long messages. Making
>the pads sucesptable to analysis.
>I have a paper on this subject. If interested let me know.
>
> ...al
Yes, I would be interested in reading the paper. Is it available online?
DSC
____________________________________________________________________
Dan S. Camper [EMAIL PROTECTED]
Borrowed Time, Inc.
------------------------------
From: "Christian König" <[EMAIL PROTECTED]>
Subject: Re: updated rc4/5/6 code, birthday attack
Date: Thu, 11 Mar 1999 14:37:28 +0100
Hi Tom!
>Also what is the birthday attack?
Look here:
http://astsun.astro.virginia.edu/~eww6n/math/BirthdayAttack.html
or - much better - read the RSA FAQ:
http://www.rsa.com/rsalabs/faq/
Cheers, Chris
------------------------------
Crossposted-To: talk.politics.crypto
From: [EMAIL PROTECTED] (David Lesher)
Subject: Re: Intel/Microsoft ID
Reply-To: [EMAIL PROTECTED] (David Lesher)
Date: Thu, 11 Mar 1999 13:44:05 GMT
"Roger Schlafly" <[EMAIL PROTECTED]> writes:
>Hmmm. NYTimes is free to everybody. You just have to
>register.
They admit to grief with Lynx:
We are aware of a problem with Lynx and our site and are
currently working to fix it. We appreciate your patience.
In the meantime, one work-around we suggest is to go to this page:
http://www.nytimes.com/login
Enter your ID and password at the top and click ENTER.
That should allow you access.
--
A host is a host from coast to [EMAIL PROTECTED]
& no one will talk to a host that's close........[v].(301) 56-LINUX
Unless the host (that isn't close).........................pob 1433
is busy, hung or dead....................................20915-1433
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Cyclotomic Number Generators
Date: Thu, 11 Mar 1999 13:45:10 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 11 Mar 1999 09:03:46 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>> The conclusion I reached after having waded thru that book was that
>> cyclotomic number generation was an important issue in stream ciphers,
>Assuming this is related to cyclotomic fields or cyclotomic integers,
Yes, it is.
>it might have some relevance to elliptic curve cryptography, but not
>to stream ciphers in general.
Then you should inform the authors of that book that they are all
wrong. I am sure they would want to know.
They are convinced that cyclotomic number generation is one of the
strongest cryptographic methods for making secure keystreams. They
talk about its linear and sphere complexity, its immunity to
differential cryptanalysis, and a whole bunch of other things that
only a cryptanalyst could love.
The book is:
Stream Ciphers and Number Theory (North-Holland
Mathematical Library, V. 55)
by Thomas W. Cusick, C. Ding, Ari Renvall
Hardcover (April 1998)
Elsevier Science; ISBN: 0444828737
>> The cyclotomic generator is supposedly the most secure
>> keystream generators known.
>One wonders what a proof of that would look like
>(assuming that the important missing details are filled in);
>it's hard to imagine.
Then read the book and see if they are correct or not.
>One reason to think that it's wrong is that it's a deterministic
>mathematical algorithm, and the objects involved have a lot of
>structure (which usually means there are ways to exploit the
>structure).
Not if the structure does not become manifest in ordinary use.
>Surely, a keystream generated from a thermal or
>radioactive source is "more secure" in any meaningful sense.
It is a PRNG and therefore is subject to that criticism. But, of the
PRNGs that have been proposed thus far, the claim is that it is the
one of the strongest cryptographically.
Bob Knauer
"There's no way to rule innocent men. The only power any government
has is the power to crack down on criminals. Well, when there aren't
enough criminals, one makes them. One declares so many things to be
a crime that it becomes impossible to live without breaking laws."
--Ayn Rand
------------------------------
From: Doggmatic <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithms [moving off-topic]
Date: Thu, 11 Mar 1999 01:03:04 GMT
In article <7c3f59$4f7$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Patrick Juola) wrote:
> In article <7bpipm$drj$[EMAIL PROTECTED]>,
> Doggmatic <[EMAIL PROTECTED]> wrote:
> >In article <7bonge$81b$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Patrick Juola) wrote:
> >> In article <7bn566$b44$[EMAIL PROTECTED]>,
> >> Doggmatic <[EMAIL PROTECTED]> wrote:
> >> >In article <7b70cj$1li$[EMAIL PROTECTED]>,
> >> > [EMAIL PROTECTED] (Patrick Juola) wrote:
> >> >> In article <7b6tmq$ojt$[EMAIL PROTECTED]>,
> >> >> Doggmatic <[EMAIL PROTECTED]> wrote:
> >> >>
> >> >> >But I will look up this "reversible computing." For such a
> >> >> >great idea researched 30 years ago, you think I'd have my Free-Energy
> >> >> >computer by now.
> >> >>
> >> >> I'll build one for you. Just buy me a frictionless surface.
> >> >[snip]
> >[snip my previous condescension]
> >> >accepted that there is no such thing as a "frictionless surface" in this
> >> >universe. Here is where you can correct me if I'm wrong. I know that
> >> >theoretically you can have smoother and smoother surfaces, but I thought
that
> >> >a frictionless surface is a physical impossiblilty, which is why I've also
> >> >wondered about why "parasitic losses" were mention as if they are
> >> >inconsequential.
> >>
> >> Because "parasitic losses" are the sort of things that engineers are
> >> really good at reducing as technology improves. Look at the amount
> >> of waste heat and waste power that a vacuum tube uses when compared
> >> with an identically functioning IC transistor.
> >>
> >> > If the ideal cannot be reached, which is my current belief,
> >> >then why even mention it, since this thread was originally about tractable
> >> >solutions and not impossible ideal solutions.
> >>
> >> Because what is tractable in fifty years will be a hell of a lot closer
> >> to the ideal than what's tractable today. And you don't have any idea
> >> how much closer.
> >>
> >> -kitten
> >
> > Okay .. we'll play your game. Sample program:
> >
> > Time equals 0; <--- some arbitrary number Friction of surface equals 10;
> ><-- some random number beginning of a loop { time advances by 50
years;
> >engineers reduce friction of surface by a factor of ten so new Friction of
> >surface now equals old Friction of surface divided by 10; Tell me what the
> >new Friction of surface is; } end of loop...repeat loop only until Friction
> >of surface equals 0 then stop; Tell me how many years have passed;
>
> Wrong stopping condition. Tell me; when friction is small enough that
> per-bit losses are less than 1/2^256 of an erg. At that point, you'll
> be able to count to 2^256 at a total cost of less than an erg of energy.
[snip approx answer]
>
> -kitten
I almost concur, except that the limit of one erg is unnecessary. So long as
you can, at least, count up to 2^256 with some x number of available ergs of
energy, which is likely greater than just one erg. So let's assume we've got
a whole bunch'a ergs to use. What sounds good to you? We'll go with 10^60
ergs just sitting in our energy bank; is that enough? I know ... I know ..
you're thinking, "Hey, that's more energy than the Sun will release before it
goes nova [not counting the supernova itself]." .. or maybe "Wait! There
aren't even 10^60 atoms in this solar system - maybe we shouldn't have 10^60
ergs?" But, don't worry about those piddly little details, just humor me.
We know that the energy of a state change is greater than or equal to
1.38e(-16) * TempOfUniv. We've got 10^60 ergs to spare and we want to run
something through 10^77 (2^256) state changes. So, we're looking for an
energy-per-state-change of (10^60 / 10^77) = 10^(-17). Let's plug that into
our equation. 10^(-17) >= 1.38e(-16) * TempOfUniv. So, TempOfUniv <=
10^(-17) / 1.38*10^(-16). T comes out to ... hmmm, let's see ... less than
or equal to ~10^(-1) K. The average temparature of the universe during our
computer's counting has to be at most 0.1 Kelvin. Oh darn, the temperature
of the universe exceeds that by an appreciable amount right now. Guess we'll
have to wait and see if this universe is open (i.e. no Big Crunch) and then
maybe in a gazillion years or so, we'll be able to make those 2^256 state
changes. We'll find out, at the longest, whether this universe is open or
closed in 10 billion years, but making 2^256 state changes now would cost
~10^61 ergs, which exceeds our original (very generous) allotment.
___/Mike ...two legs good, four legs bad? ... Why conform?
__/. | For my next trick, WATCH as this humble mouse breaks
\-__ \___ Windows at the mere press of a button.
\ Hey! Where are we going, and why am I in this handbasket?
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Wed, 10 Mar 1999 23:55:17 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Limitations of testing / filtering hardware RNG's
<HTML>
Jim Gillogly wrote:
<BLOCKQUOTE TYPE=CITE>I haven't been following this whole thread, so if
I'm being irrelevant
<BR>or redundant, I apologize.</BLOCKQUOTE>
The topic is not irrelevant. YOU have not been redundant.
<BLOCKQUOTE TYPE=CITE>Trevor Jackson, III wrote:
<BR>> R. Knauer wrote:
<BR>> > On 9 Mar 1999 15:03:26 -0500, [EMAIL PROTECTED] (Herman
Rubin)
<BR>> > wrote:
<BR>> > >Not just as diagnostics; if the outcome HAPPENS to be all 0's
or all
<BR>> > >1's, you would not want to use this for cryptography. There
are other
<BR>> > >outcomes which one would not want to use.
<BR>> >
<BR>> > If you filter the output as you suggest, then the TRNG is no longer
<BR>> > proveably secure in principle.
<BR>>
<BR>> Show me the leak. Otherwise stop repeating this nonsense.
<P>OK. Just to be definite, let's assume that you have some threshold
<BR>T where if you see T 0's in a row, you will remove all of them from
<BR>the random bit stream, then pick up and continue. To make the
example
<BR>obvious, let's assume T=8, so that we know there will never be a run
of
<BR>8 0-bits in a row.
<P>We now have a message coming in. The ciphertext starts "YNAQJ
BFPGD".
<BR>Since we know that there are never 8 0-bits in a row, we know that
the
<BR>first character of the plaintext is not Y, the second character is
not
<BR>N, the third character is not A, and so on. This is precisely
one of
<BR>the weaknesses of Enigma, which allowed the Allies to place guessed
<BR>plaintext. I can tell with certainty that this message did not
<BR>start with "YES" or "INREP LYTOY".</BLOCKQUOTE>
In principle (theory) you are correct. However, in practice it is
meaningless. Consider the 10 character message that you used as an
example. A perfect OTP would allow any plsible decruption of those
10 characters or N^10 possible decryptions where N is 64 or 256 depending
on your alphabet. Let's say N=64 to give you the maximum benefit
of the doubt.
<P>Given the above we're talking about a space of 2^60 possible messages;
or 10^18. Of these you have ruled out all messages containg one or
more characters of all zero, which amounts to 2^10 possible pads; or 10^3.
So we have reduced the attacker's confision by one part in 10^15.
Just how importantdo you consider that weakness? Based on approx
1.2 bits of entropy per character in English, the adversay is probably
looking at a sensible message space of 2^12, or 4e10 messages. The
loss of strength by filtering is lost in the rounding.
<P>Let's take a stronger example. Let's say we use very strict filters
that reject half of the possible pads as unsuitable. Thus the pad
space is only 2^59 instead of 2^60. In principle we've lost something.
In practice we haven't lost anything meaningful.
<P>If we take an even stronger filter, one that accepts only 2% of the
possible pads, we've lost about 6 bits of pad space, so the pads are down
to "only" 2^54 possibilities. At this point, if we're psychotic rather
than just paranoid, we can recover the "lost" strength by using an additional
character. Padding the message by 6 bits expands thspace back to
the original work factor of 2^60 possible messages.
<BLOCKQUOTE TYPE=CITE>The key fact of a one-time pad is that it can give
the attacker no
<BR>information about the plaintext other than a bound on its length.
<BR>Filtering the TRNG stream in the way you suggest (eliminating runs
<BR>of 0's or 1's) breaks this assumption.</BLOCKQUOTE>
In theory yes. In practice no. Try it yourself. Set up
a filter allowing only the best 50% of pads and show that it "breaks" the
cipher.
<BLOCKQUOTE TYPE=CITE>As everybody keeps saying, of course, it's necessary
to monitor your
<BR>TRNG to make sure it isn't broken, and sending all 0's for a long
<BR>time is a good sign that it's broken. However, "fixing" it so
that
<BR>it cannot produce certain strings even when it's working properly
<BR>breaks the provable security of the OTP, just as R. Knauer says above.</BLOCKQUOTE>
No. Security of the OTP system is only broken when the entropy of
the pad is less than the entropy of the message. The magic of a perfect
pad is that it works for all messages, even those of 100% entropy density. </HTML>
------------------------------
From: [EMAIL PROTECTED] (Tom Thomson)
Subject: Re: Limitations of testing / filtering hardware RNG's
Date: Thu, 11 Mar 99 14:37:03 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>The purpose of a TRNG is to circumvent those issues. It is a
>stand-alone true random number generator. It does not need to have its
>output tested (other than as a diagnostic warning) and it certainly
>cannot tolerate having its output filtered.
>
If that is true, a TRNG cannot be used to generate keys where the encryption
algorithm used has a significant proportion of weak keys; since no such key
can safely be used.
Nor can it be used to generate salts for stream encryption (since here
filtering to eliminate duplicates is required).
Really Bob, I think what you are trying to say is that statistical test on the
output can tell you there's a problem but can never tell yu there's nothing
wrong, and certainly can't be used to manipulate the output to "pput it
right". If that IS what you intend to say, i agree with you; but much of what
you write seems to be asserting something much stronger than that - something
which, as indicated by the two clear requirements for filtering pointed out
abouve, is in fact patently untrue.
------------------------------
From: "almis" <[EMAIL PROTECTED]>
Subject: Re: Where have I seen this?
Date: Thu, 11 Mar 1999 08:04:27 -0600
|Yes, I would be interested in reading the paper. Is it available online?
The paper and an application is available at:
http://ww2.netnitco.net/users/almis
...al
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Testing Algorithms [moving off-topic]
Date: 11 Mar 1999 09:55:31 -0500
In article <7c74o2$pqm$[EMAIL PROTECTED]>,
Doggmatic <[EMAIL PROTECTED]> wrote:
>In article <7c3f59$4f7$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Patrick Juola) wrote:
>> In article <7bpipm$drj$[EMAIL PROTECTED]>,
>> Doggmatic <[EMAIL PROTECTED]> wrote:
>> >In article <7bonge$81b$[EMAIL PROTECTED]>,
>> > [EMAIL PROTECTED] (Patrick Juola) wrote:
>> >> In article <7bn566$b44$[EMAIL PROTECTED]>,
>> >> Doggmatic <[EMAIL PROTECTED]> wrote:
>> >> >In article <7b70cj$1li$[EMAIL PROTECTED]>,
>> >> > [EMAIL PROTECTED] (Patrick Juola) wrote:
>> >> >> In article <7b6tmq$ojt$[EMAIL PROTECTED]>,
>> >> >> Doggmatic <[EMAIL PROTECTED]> wrote:
>> >> >>
>> >> >> >But I will look up this "reversible computing." For such a
>> >> >> >great idea researched 30 years ago, you think I'd have my Free-Energy
>> >> >> >computer by now.
>> >> >>
>> >> >> I'll build one for you. Just buy me a frictionless surface.
>> >> >[snip]
>> >[snip my previous condescension]
>> >> >accepted that there is no such thing as a "frictionless surface" in this
>> >> >universe. Here is where you can correct me if I'm wrong. I know that
>> >> >theoretically you can have smoother and smoother surfaces, but I thought
>that
>> >> >a frictionless surface is a physical impossiblilty, which is why I've also
>> >> >wondered about why "parasitic losses" were mention as if they are
>> >> >inconsequential.
>> >>
>> >> Because "parasitic losses" are the sort of things that engineers are
>> >> really good at reducing as technology improves. Look at the amount
>> >> of waste heat and waste power that a vacuum tube uses when compared
>> >> with an identically functioning IC transistor.
>> >>
>> >> > If the ideal cannot be reached, which is my current belief,
>> >> >then why even mention it, since this thread was originally about tractable
>> >> >solutions and not impossible ideal solutions.
>> >>
>> >> Because what is tractable in fifty years will be a hell of a lot closer
>> >> to the ideal than what's tractable today. And you don't have any idea
>> >> how much closer.
>> >>
>> >> -kitten
>> >
>> > Okay .. we'll play your game. Sample program:
>> >
>> > Time equals 0; <--- some arbitrary number Friction of surface equals 10;
>> ><-- some random number beginning of a loop { time advances by 50
>years;
>> >engineers reduce friction of surface by a factor of ten so new Friction of
>> >surface now equals old Friction of surface divided by 10; Tell me what the
>> >new Friction of surface is; } end of loop...repeat loop only until Friction
>> >of surface equals 0 then stop; Tell me how many years have passed;
>>
>> Wrong stopping condition. Tell me; when friction is small enough that
>> per-bit losses are less than 1/2^256 of an erg. At that point, you'll
>> be able to count to 2^256 at a total cost of less than an erg of energy.
>[snip approx answer]
>>
>> -kitten
>
>I almost concur, except that the limit of one erg is unnecessary. So long as
>you can, at least, count up to 2^256 with some x number of available ergs of
>energy, which is likely greater than just one erg. So let's assume we've got
>a whole bunch'a ergs to use. What sounds good to you? We'll go with 10^60
>ergs just sitting in our energy bank; is that enough? I know ... I know ..
>you're thinking, "Hey, that's more energy than the Sun will release before it
>goes nova [not counting the supernova itself]." .. or maybe "Wait! There
>aren't even 10^60 atoms in this solar system - maybe we shouldn't have 10^60
>ergs?" But, don't worry about those piddly little details, just humor me.
>We know that the energy of a state change is greater than or equal to
>1.38e(-16) * TempOfUniv. We've got 10^60 ergs to spare and we want to run
>something through 10^77 (2^256) state changes.
That's the point -- we're not running the universe through state changes
as we're using reversible computations.
-kitten
------------------------------
** 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
******************************
