Cryptography-Digest Digest #777, Volume #9 Fri, 25 Jun 99 19:13:02 EDT
Contents:
Re: Kryptos article ("Renegade")
Re: DES-NULL attack (Casper H.S. Dik - Network Security Engineer)
Re: one time pad (AllanW)
Re: Tough crypt question: how to break AT&T's monopoly??? (JPeschel)
Re: DES-NULL attack ([EMAIL PROTECTED])
Re: Kryptos article (Jim Gillogly)
Re: one time pad (AllanW)
Re: one time pad (Jerry Coffin)
Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day (Dave Salovesh)
Re: one time pad (William Tanksley)
Re: one time pad (John Savard)
----------------------------------------------------------------------------
From: "Renegade" <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Fri, 25 Jun 1999 15:54:07 -0500
> I use Perl for one-off programs and things that aren't computationally
> intensive -- analyzing and diagnosing unknowns, for example. C is
> better for the serious crunching,
Perl? C? Stop the horror. Real cryppies code in IMP! Next you be telling
us it ran on a Wintel box......
:-)
-Mike
------------------------------
From: [EMAIL PROTECTED] (Casper H.S. Dik - Network Security Engineer)
Subject: Re: DES-NULL attack
Date: 25 Jun 1999 20:22:18 GMT
[[ PLEASE DON'T SEND ME EMAIL COPIES OF POSTINGS ]]
[EMAIL PROTECTED] writes:
>In article <7l029h$4q6$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> Suppose we use DES encryption algorithm.
>>
>> Let a plain text block contains only bits with NULL value.
>>
>> Then correspondent cipher block is well-defined function
>> of the encryption key, which can be recovered.
>That is not true. It's a function of the plaintext register, key and
>sboxes. You forget that the key and sboxes will not always produce
>degenerative output and their is a feedback (the other unmodified half
>in each round).
>For NULL it's just as hard as for '12345678'. By your argument though
>the all one plaintext would reveal the complement of the key.
>That's not true. If it were this would apply to many other ciphers
>(Blowfish, CAST, Kafre, etc...)
Darn, I just though of the DES-1 through DES-(2^64-2) attacks, you mean those
don't work either?
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 20:36:29 GMT
In article <7l0all$8jm$[EMAIL PROTECTED]>,
Greg Ofiesh <[EMAIL PROTECTED]> wrote:
>
> > The probability of a long stream of zero's is
> > so vanishingly small, that
> > worrying about it is counter productive.
>
> If it is vanishingly small, then at some point you do not expect
> to see it in nature. For example, what are the odds that all
> photons in the universe come together and cancel each other out
> in a moment of time? So slim that you do not expect to ever see
> it happen.
Right. So there's no sense protecting against it.
To extend your example, let's say that you were buying a camera.
When you take a picture, the camera first measures the light for
1/100 of a second, so that the flash will automatically activate
if there is not enough light.
But if your astronomically-improbable event occurs, and all of
the photons cancel each other out for 1/100 of a second *AFTER*
the camera has measured the light level, then your picture
would be ruined.
That's the $200 camera. Now, for $500, I can sell you a different
camera. It has exactly the same quality, the same features and
guarantees, etc. However, it measures the amount of light WHILE
you take a picture. In the event that photons all cancel each
other out while you take the picture, the shutter will remain
open until that astronomically-improbable event is complete, and
light levels return to normal, so that the picture will not be
ruined. All of this for only $300 more.
But wait! This scheme also protects you for several other
possible events, which are also astronomically improbable.
For instance, what if all of the photons suddenly decide to
aim themselves at your target, making her much more brilliantly
lit than they had been a moment earlier? Once again, the camera
will close the shutter at the appropriate time -- and your
picture is saved. Now how much would you pay?
Myself, I wouldn't pay even $1 more for it. The reason is
obvious: I would consider it to be a feature that I don't
need and would never use. After all, the events in which
these features would hypothetically be useful are beyond
merely rare; they are so astronomically improbable that
(as you say) I "do not expect to see it in nature." Why
pay for marginal protection against something I do not
expect to ever see?
> Therefore I ask, what do you do if your RNG produces an event
> that is too unlikely to occur in nature? Assume the RNG is
> broken and replace it?
If I even notice it, then yes.
> Why not filter the output with: "I want only those events that
> meet a threshold of probability. Anything lower than this
> given threshold is demonstrative of an inperfect RNG because
> the event shows a bias toward a probability that is too slim
> to occur in nature."
Because no matter what the output, that particular output was
so improbable that I never did expect to see it.
Oh, dear, that isn't very satisfying. Let's try another
angle.
Getting back to the RNG, you want to disallow obvious
patterns. Our current example has you disallowing long
strings of 0-bytes. Is this sufficient to avoid claims
that the output has patterns?
No, it isn't. Your original example was 100 bytes of 0xA7.
In fact, you said that you want to prevent the occurance of
ANY byte 100 times in a row. But presumably this also applies
to 99 times in a row, and 98 times in a row... Let's just
call it N, and let the local user set this value as desired.
Now we've eliminated 256 special cases. Does that satisfy the
need for no patterns?
No, it doesn't. What about non-repeating obvious sequences
such as 0x01, 0x02, 0x03, 0x04, ...? Clearly, such sequences
don't have to add 1 for each byte, because 0x01, 0x03, 0x05...
is also a pattern. And it's no good detecting the patterns
that start with 0x01, because 0x42, 0x44, 0x46, ... is also
a pattern. We have to eliminate patterns that start with any
value and increment by a fixed amount. That's 256x255=65280
patterns, plus the 256 we already got makes 65536 patterns
so far. Is that all of them?
Well, what about non-constant increases? 0x22, add 15. to
get 0x31, add 16. to get 0x41, add 17. to get 0x52, ...
In general, for any starting pattern, we need to skip patterns
where the increase follows any of the 65280 patterns in the
previous paragraph. That's 256x65280=16711680 more patterns,
for a running total of 16777216.
But we're still not there. Since we just identified 16711680
more patterns, I could talk about patterns where the increase
follows any of those patterns, and I could continue this line
of reasoning forever. But we haven't even talked about
irrational patterns yet. Another post in this thread
considered outputting digits of PI as the random bytes, but
Pi is well known so this is weak. And what happens when we
use AX+B, where A and B are constants and X is a digit from
PI? What about digits of PI in bases other than 10? What
about digits from e, or sqrt(2), or sqrt(5), or some
combination? Consider adding digit D of pi to digit 2D of
sqrt(2)!
Now look at some other sequences, and tell me if they form
one of the patterns we should protect ourselves from:
0x80, 0x7F, 0x01, 0x33, 0x9C, 0x9C, 0x71 ...
0x00, 0xF0, 0xC8, 0x20, 0x78, 0x07, 0x18 ...
0x31, 0x41, 0x59, 0x26, 0x53, 0x58, 0x97 ...
0xF3, 0x89, 0xB0, 0xCC, 0xA7, 0xE1, 0x00 ...
After a while, all of these sequences start to look alike.
You may find that one day you think you see a pattern, but
if you don't write down the description then the next day
you no longer see it.
Thus, the total number of possible patterns that we should
protect ourselves from varies, depending on the nature of the
person doing the counting and the mood he was in at the time.
But it is clearly very large. Consider a hypothetical case
where we have eliminated 75% of all possible pads as being
"too patternlike." We have just made our attacker's job
easier by 75%!
What say you?!?
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Tough crypt question: how to break AT&T's monopoly???
Date: 25 Jun 1999 21:27:02 GMT
> [EMAIL PROTECTED] (Jayjames99) writes:
>I am trying to send an encypted file to somebody who is not computer savvy,
>in
>a format so that the receiving party does not have to know how to decrypt the
>file. It will simply self-extract, ask for the private key to be entered,
>and
>voila...the file is now readalble.
>
>I think AT&T is the only vendor of this kind of a program--but it costs
>$1000+
>for a network license. Outrageouis. And probably patented.
>
>Does anybody know of a cheap workaround?
>
>
Puffer will let you create self-extracting encrypted files. It's shareware
and upon registration uses strong encryption.
http://www.briggsoft.com/puffer.htm
Symantec has Norton Secret Stuff, which uses 32-bit Blowfish. This
is not terribly secure and I have a brute-force cracker for it.
>Also, in the alternative, please recommend any NON-PGP program (except ROT13)
>for half-way decent protection from casual intruders, so that somebody can
>simply send an encryped file that can be easily decrpyted (especially a
>binary
>file sent as an attachment)
I would avoid software that would protect you from casual intruders, there
may be crack for that program somewhere on the web, for instance, the
site below.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
Date: Fri, 25 Jun 1999 20:47:30 GMT
Hello Tom,
I'm very sorry. You must ask for training in math.
You is doing your job not good enough.
But, I love you.
Regards.
Alex.
In article <7l0mkc$dt7$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <7l0ir0$c7b$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Oh! You are on duty today.
> > You should get a more salary.
> > The case is out of your confidence
>
> Ok what's this about?
>
> Your argument is not substantiated. Just because you pass a zero
block
> thru does not mean you will find out the key faster then any other
> method. In the standard attacks they use differences between pairs no
> single inputs.
>
> Tom
> --
> PGP key is at:
> 'http://mypage.goplay.com/tomstdenis/key.pgp'.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
>
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Fri, 25 Jun 1999 14:29:58 -0700
Renegade wrote:
>
> > I use Perl for one-off programs and things that aren't computationally
> > intensive -- analyzing and diagnosing unknowns, for example. C is
> > better for the serious crunching,
>
> Perl? C? Stop the horror. Real cryppies code in IMP! Next you be telling
> us it ran on a Wintel box......
I'm not that depraved -- Linux, of course.
--
Jim Gillogly
2 Afterlithe S.R. 1999, 21:28
12.19.6.5.10, 1 Oc 18 Zotz, Second Lord of Night
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 21:57:23 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
>
> AllanW wrote:
> > Consider a CPU which has no fixed clock speed. That is, instead
> > of (say) 450MHz, we allow the clock speed to "drift" very
> > slowly -- sometimes as low as 400MHz, other times as high as
> > 450MHz, in a cycle that repeats 100 times per second.
> >
> > To this we attach a single-bit counter attached to it's own
> > clock source, independant of the CPU and much faster. Give
> > the counter a known duty cycle; ideally, 50% of the time it
> > contains "0" and the other 50% of the time it contains a
> > "1". (Other duty cycles can be adjusted algorithmically.)
> > Like the CPU's clock, we will allow the counter's clock to
> > "drift", sometimes as low as 3GHz, other times as high as
> > 4GHz, in a cycle that repeats 500 times per second.
> >
> > Note that the CPU's clock drift is not connected to the
> > counter's clock drift in any way.
> >
> > Even when the CPU is at it's fastest (450MHz) and the counter
> > is at it's slowest (3GHz), the counter will change states
> > many times during one CPU clock. So the value retrieved by
> > the CPU during any one poll depends on the exact timing of
> > the polling pulse. By giving the two clocks different speeds
> > and having each of them drift, the timing will vary each time
> > that the CPU polls the counter. If the result of one such
> > poll is truely random and has a 50% duty cycle, then the
> > results of N polls should be enough to create a truely-
> > random N-bit integer.
> >
> > I don't claim to have proven that my device is truely random.
> > But it does seem to me that it should be possible to
> > mathematically prove (or disprove) it.
>
> It will work as a decent RNG, but not a really good one. The
> problem is in frequency locking -- the counter systems need
> to be very carefully isolated from each other -- otherwise
> the possibility of mode locking between the two oscillators
> exists. (or between them and some other coupled component.
That's why they have independant clocks, running at different
frequencies.
> Be careful of hidden multiplier effects -- i.e. clock A is
> exactly 8X as fast as clock B will mean that the 0's will
> be more common than 1's.
That's why both clocks have intentional drifts, which are not
synchronized with each other. If there is an instant in time
in which the counter is exactly 8 times as fast as the CPU,
then by the next CPU clock cycle this will no longer be true.
> There are other possible problems -- I'd use a radioactive
> decay based method ALA hotbits in preference to this method.
Could you elaborate on this? I don't know about hotbits.
In any case, my device was for exposition only. My real
question is, would it be possible to create a hardware
high-speed true-random-number generator without spending
a fortune? By high-speed I mean that the CPU coul read
(at least one bit of) a new random number from the device
as often as it wished, without having to do any
synchronization, and without distorting the random factor
(i.e. because of synchronized clocks). And by true-random-
number, I mean the usual: regardless of previous values
received (or the timing when they were received), every
possible outcome is equally likely for the next value.
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 15:27:28 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> >[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
> >
> >>The issue here is whether even minor forms of predictability are
> >>mathematically prohibited, or even wildly impossible given what we
> >>know about the real system. I think not: these are reasonable
> >>concerns. There is no process in place, no tool we have, no test we
> >>can make which can eliminate the possibility of weakness in a pad.
> >>And the possibility of weakness destroys any claim to absolute
> >>strength.
To summarize this: what you're saying is NOT really that an OTP
doesn't give guaranteed security. What you're really saying is that
an OTP can't be implemented.
IOW, the basic definition of an OTP is that you start with the ability
to produce a truly random bitstream with which to do the encryption.
You're saying that in a real implementation, it's impossible to
produce a bitstream and prove that it's really random.
IMO, this isn't really proving much anything: for the most part, OTP
isn't practical to start with. Proving that a real implementation can
only approximate it doesn't mean a lot because nearly anything that's
practical is KNOWN to only be an approximation to start with.
------------------------------
From: [EMAIL PROTECTED] (Dave Salovesh)
Subject: Re: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Fri, 25 Jun 1999 23:01:12 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Lincoln Yeoh) opined:
>Given a totally random generator running for an eternity, eventually you
>may get Shakespeare. But it's still random.
And while you're waiting for Shakespeare in English, you're equally
likely to get Shakespeare translated into French, German, Spanish, etc.,
and you'd also be likely to see all the posts to this newsgroup over the
last 5 years, including all the spams, headers, PGP signatures, and
munged addresses everyone has sent.
This would be alarming if you were looking for "simple, regular"
sequences, but it would still be wrong compared to the target.
And if you don't know the target is Shakespeare, you'll see -something-
you recognize and quit looking long before you get the right answer.
--
Dave Salovesh
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (William Tanksley)
Subject: Re: one time pad
Reply-To: [EMAIL PROTECTED]
Date: Fri, 25 Jun 1999 22:43:45 GMT
On Fri, 25 Jun 1999 16:27:48 GMT, Greg Ofiesh wrote:
>> The probability of a long stream of zero's is
>> so vanishingly small, that
>> worrying about it is counter productive.
>If it is vanishingly small, then at some point you do not expect to see
>it in nature. For example, what are the odds that all photons in the
>universe come together and cancel each other out in a moment of time?
>So slim that you do not expect to ever see it happen.
>Therefore I ask, what do you do if your RNG produces an event that is
>too unlikely to occur in nature? Assume the RNG is broken and replace
>it? Why not filter the output with: "I want only those events that
>meet a threshold of probability. Anything lower than this given
>threshold is demonstrative of an inperfect RNG because the event shows
>a bias toward a probability that is too slim to occur in nature."
We've all repeatedly stated that every string is equally unlikely with a
true random stream. A stream of zeroes is no more unlikely than a
specific stream of gibberish.
There is NO single stream of data coming out of an alleged RNG which would
prove to me that it wasn't an RNG.
>What say you?
--
-William "Billy" Tanksley
Utinam logica falsa tuam philosophiam totam suffodiant!
:-: May faulty logic undermine your entire philosophy!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: one time pad
Date: Fri, 25 Jun 1999 22:51:01 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote, in part:
>I
>claim we would do well to check even "obviously random" physical
>generators to see if anything funny is going on. And even that does
>not give us peace of mind.
I would not disagree that we would do well to check *some* physical
generators...others, though, are rather well checked by our
understanding of how they work. And peace of mind can exist without
mathematical-quality proof for many things in life - cryptography (and
many other things even our lives depend on) included.
It would be difficult for people to function otherwise.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
** 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
******************************
