Cryptography-Digest Digest #131, Volume #13 Thu, 9 Nov 00 18:13:01 EST
Contents:
Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware (Larry Kilgallen)
Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware (d)
Re: RSA security (Paul Rubin)
Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware (Richard Heathfield)
Re: RSA security (Francois Grieu)
Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile Software (Scott
Craver)
Re: CHALLENGE TO cryptanalysts (Ichinin)
Re: hardware RNG's (David Schwartz)
Re: hardware RNG's (David Schwartz)
Re: Brute force against DES (JPeschel)
Re: Hardware RNGs (Steve Portly)
Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware (Tom St Denis)
Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware (Tom St Denis)
Re: RSA security (Jim Gillogly)
Re: Q: Computations in a Galois Field (Mok-Kong Shen)
Re: RSA security (Mok-Kong Shen)
Re: A question about RSA (Zulfikar Ramzan)
Re: CHALLENGE TO cryptanalysts ("Douglas A. Gwyn")
Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile Software
(Bill Godfrey)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Larry Kilgallen)
Subject: Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware
Date: 9 Nov 2000 13:09:52 -0500
In article <8ue3fo$iun$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> writes:
> I would bet "secret agent behind enemy lines" would rather carry a
> smart card with the cipher+128 bit key embedded in it then a computer +
> MASS storage device for the OT pad...
The clever agent would demand that the PHB provide the OTP on a CDROM,
so the agent does not have to carry the hardware device and only needs
to find a machine with a compatible reader. There are several brands :-)
Even the most clever agent does not have more than 680,000,000 characters
of his own words to transmit in one outing. It won't work for graphics,
but there are some stories better told in words.
------------------------------
From: d <[EMAIL PROTECTED]>
Subject: Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware
Date: Thu, 09 Nov 2000 18:21:34 +0000
Tom St Denis wrote:
> In article <[EMAIL PROTECTED]>,
> d <[EMAIL PROTECTED]> wrote:
> > Command line One Time Pad utility. Options: pad generation, randomness
> > testing, en/decryption, base64 en/decoding and disk wiping. ANSI-C
> > source and DOS executable included.
> >
> > Free download at <http://www.vidwest.com/otp/>
> >
> > Your bug reports/other feedback will be gratefully received.
>
> Perhaps you missed the boat, OTP's are not practical solutions!
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
also, I'm not sure you're right. If secure key distribution is not a problem
(clandestine meetings in the park etc.), and if a provably unbreakable code
is a 'requirement', then what other options are there...?
(for me, having nothing to hide is/would be the best practical solution)
Thanks for giving this your attention,
David West. <[EMAIL PROTECTED]>
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: 09 Nov 2000 10:20:19 -0800
Francois Grieu <[EMAIL PROTECTED]> writes:
> Yes. Note that 512 bit is a bare minimum, because this key will
> be a long-term key (reused from session to session) and 512 bit
> is factorable now, though with considerable effort (was done
> publicly once only, in mid 1999, by leading researchers using
> many workstations and a Cray with lots of memory). Better be safe
> and go to 1024 bits, which looks like safe for some time.
No, it was done again by some Swedes to solve the last stage of
the Simon Singh Cipher Challenge last month. They used a lot of
workstations but no Cray.
------------------------------
Date: Thu, 09 Nov 2000 18:29:20 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware
Larry Kilgallen wrote:
>
> In article <8ue3fo$iun$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> writes:
>
> > I would bet "secret agent behind enemy lines" would rather carry a
> > smart card with the cipher+128 bit key embedded in it then a computer +
> > MASS storage device for the OT pad...
Smart cards can be stolen, so this is insufficient security (although it
might be possible to add extra safeguards to make this idea work).
>
> The clever agent would demand that the PHB provide the OTP on a CDROM,
> so the agent does not have to carry the hardware device and only needs
> to find a machine with a compatible reader. There are several brands :-)
>
> Even the most clever agent does not have more than 680,000,000 characters
> of his own words to transmit in one outing. It won't work for graphics,
> but there are some stories better told in words.
The problem here is one of key security. With a genuine One Time *PAD*,
you can destroy each sheet as it is used, so that the adversary cannot
steal it and re-use it to decrypt messages you have previously
broadcast. If your OTP key is on a CD-ROM, however, you either use it to
send just one mother of a message and then utterly destroy the CD-ROM
(by fire, ideally), or you risk your previous messages being decrypted
by anyone who can get their hands on the CD-ROM, either through theft or
after arrest.
A One Time Tape, however, might have its advantages. High storage
capacity, reasonably fast delivery of bits, and you could have the tape
marked with little yellow strips* across it, so that you could cut the
tape at a marked boundary, discard (sorry! DESTROY...) the used part,
re-splice the tape, and you're ready for the next message.
My understanding is that the original implementation of the One Time Pad
algorithm did in fact use a tape, but I could be wrong about that.
[* Yes, they must be yellow. It shows up better in a night scene, in spy
thrillers.]
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Thu, 09 Nov 2000 19:56:57 +0100
Paul Rubin <[EMAIL PROTECTED]> wrote:
> No, it (factoring a 512 bit RSA key) was done again by some
> Swedes to solve the last stage of the Simon Singh Cipher
> Challenge last month. They used a lot of workstations but no Cray
Interesting; is there a public report on the techniques they used,
especialy the matrix part ?
Francois Grieu
------------------------------
From: [EMAIL PROTECTED] (Scott Craver)
Crossposted-To: talk.politics.misc,talk.politics.crypto
Subject: Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile Software
Date: 9 Nov 2000 19:17:56 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>Richard Heathfield <[EMAIL PROTECTED]> wrote:
>>
>> Sorry? You thought of XOR? You invented the One Time Pad? Pure BS.
>>
>> > and engineered
>> > it and I am not going to just give it to you all.
>What does the OP mean by "give it all to us". a program that xors
>bytes is not particularly ingenius...
I was amused by the strong language of having "engineered"
his exclusive-or utility. I can imagine that on a resume:
singlehandedly planned, engineered and implemented a piece
of computer software for XOR-ing two files together.
>I would consider myself an avid cryptographer and even I am wrong
>often. It's part of the learning curve. You have to realize and
>accept that you could be wrong to learn however.
Ditto. I've screwed up, here, publicly, enough times that
I breathed a quiet sigh of relief when the deja news archive
began to suck.
Tom, you're a high school student, right? Or are you in
college now? Or am I confusing you with someone else?
And if you are a senior in HS, does that mean you're
presently applying to universities?
>My program runs on all platforms capable of file I/O :-)
What, you have a DLX assembler version?
>And I disagree with you. Most people run PGP without checking the
>source regardless of it's availability.
Further, even if a big mass of people decided to scrutinize
available source they may still not find a cleverly hidden
trap door for a good while. Especially if the code is
confusingly written.
>Tom
-S
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: CHALLENGE TO cryptanalysts
Date: Tue, 07 Nov 2000 05:12:39 +0100
Melinda Harris wrote:
<stuff>
How about this:
http://www.sandelman.ottawa.on.ca/SSW/ietf/rfc-3rot13
...or this?
http://www.interhack.net/people/cmcurtin/snake-oil-faq.html
(*Yawn*)
--
Ichinin (.SE)
"Anything-over-IP-&-802.11"-Solutions provider.
===============================================================
NOTE: EMAIL ADDRESS IS FOR SPAMMERS, IT WILL BOUNCE REGARDLESS.
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Thu, 09 Nov 2000 11:54:50 -0800
Dan Oetting wrote:
> Only the statistical definintion of random is absolute. The common usage
> of the term before statistics perverted it never imposed such
> restrictions.
Even the statistical definition of random allows samples to have a mode
and for normal curves where not all results are equally probable.
DS
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Thu, 09 Nov 2000 11:53:25 -0800
Alan Rouse wrote:
>
> I wrote:
> > You seem to be equating an event's randomness with your ability to
> > predict that event. I think that is an inadequate definition of
> > randomness. An event that occurs with statistical bias is not random,
> > but it still might be extremely difficult to predict.
>
> David Schwartz wrote
> >That is total nonesense. If an event can only be described
> >statistically (bias or no) that means it's random.
> >Random and unpredictable are synonymous
>
> Not true. Every sample can be described statistically. For example,
> if I select one object from a population of one object, there is a 100%
> statistical chance that I'll get the same object in every trial. That
> is NOT random.
That's why I said, "If an event can _ONLY_ be described statistically".
> More importantly, your ability to predict depends upon your knowledge.
> However, the randomness of a sample is independent of a particular
> person's knowledge. If not, then a sample that is random to one person
> would not be random to another person.
That's why I said, "If an event can _ONLY_ be described statistically."
> If a sample is random, then by definition no information exists,
> whether known to you or not, which would reduce the size of a brute
> force search for the sample's value.
>
> There is a difference between a random sample and one that contains
> some entropy. Random is absolute. It means that there are no patterns
> and no biases.
Nonesense. Random is not absolute. If I roll a die with a '1' on one
side and a '2' on five other sides, the result is random, however it
will have biases. Your formulation defies common usage as well.
DS
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Brute force against DES
Date: 09 Nov 2000 20:04:20 GMT
"Douglas A. Gwyn" [EMAIL PROTECTED] writes:
>JPeschel wrote:
>> [EMAIL PROTECTED] writes:
>> >Sundial Services wrote:
>> >> And it was actually a pretty good demonstration of just
>> >> how strong the DES algorithm actually is.)
>> >More a demonstration of the poor state of public cryptanalysis.
>> Describe a good cryptanalytic attack on DES.
>
>Whether or not I know one (and could divulge it if I did)
>is irrelevant to my point, which is that there has not
>been any public *proof* of the "strength" of DES, just
>some negative results of attempts to break it.
Damn. I was hoping you were on to something you could
share. Didn't B. Olson say he had an attack on block
ciphers that would work better on DES than the other
current attacks?
Anyway, this is helluva lot more interesting than the
other thread on the XOR program.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Thu, 09 Nov 2000 15:00:34 -0500
David Schwartz wrote:
> Steve Portly wrote:
>
> > For applications that are network intensive, timing packets would be a better
> > alternative than timing interrupts. Network jitter is over 100 times greater than
> > system jitter so the laws of physics give you a natural firewall. "One cycle
>count"
> > is easily lost to signal rise times even inside your system case. I doubt anyone
>would
> > be able to monitor TS intervals from a distance of more than a few feet. This is
> > sci.crypt so a detailed explanation of system jitter would probably be off
> > topic.
>
> These are measuring the same thing. So it's not an alternative.
>
> DS
An assembly language call to int 13 takes a different amount of time than a packet
arrival.
The key is to find the minimum time period that will always produces at least one bit
of
entropy.
Since 1995 CPU frequency wander and system jitter have become a source of entropy.
http://www.ednmag.com/ednmag/reg/1995/070695/graphs/14dfcfga.htm
With my crude analysis I found that it takes about 40 microseconds to get a bit of
entropy.
My window of error could be anywhere from 10 to 100 microseconds depending on the
speed,
type of system, and entropy rollup you use. I tested on a pentium 90, 233, and 350mhz
platforms with good results (a little slower on the 90).
Have you found a richer source of entropy using packet arrival as a trigger?
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware
Date: Thu, 09 Nov 2000 20:33:00 GMT
In article <[EMAIL PROTECTED]>,
Richard Heathfield <[EMAIL PROTECTED]> wrote:
> Larry Kilgallen wrote:
> >
> > In article <8ue3fo$iun$[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> writes:
> >
> > > I would bet "secret agent behind enemy lines" would rather carry a
> > > smart card with the cipher+128 bit key embedded in it then a
computer +
> > > MASS storage device for the OT pad...
>
> Smart cards can be stolen, so this is insufficient security (although
it
> might be possible to add extra safeguards to make this idea work).
I would argue that your stealing of a card in my pocket is a bit less
trivial then a remote online attack. So I doubt that's a serious
threat with smart cards.
> The problem here is one of key security. With a genuine One Time
*PAD*,
> you can destroy each sheet as it is used, so that the adversary cannot
> steal it and re-use it to decrypt messages you have previously
> broadcast. If your OTP key is on a CD-ROM, however, you either use it
to
> send just one mother of a message and then utterly destroy the CD-ROM
> (by fire, ideally), or you risk your previous messages being decrypted
> by anyone who can get their hands on the CD-ROM, either through theft
or
> after arrest.
>
> A One Time Tape, however, might have its advantages. High storage
> capacity, reasonably fast delivery of bits, and you could have the
tape
> marked with little yellow strips* across it, so that you could cut the
> tape at a marked boundary, discard (sorry! DESTROY...) the used part,
> re-splice the tape, and you're ready for the next message.
>
> My understanding is that the original implementation of the One Time
Pad
> algorithm did in fact use a tape, but I could be wrong about that.
The problem with OTP is that how do we store the tape securely in the
first place. By your argument I could have just copied (instead of
stolen) the tape and use it to decrypt all your messages covertly.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Announcement: One Time Pad Encryption - 0.9.3 - freeware
Date: Thu, 09 Nov 2000 20:35:09 GMT
In article <[EMAIL PROTECTED]>,
d <[EMAIL PROTECTED]> wrote:
>
> also, I'm not sure you're right. If secure key distribution is not a
problem
> (clandestine meetings in the park etc.), and if a provably
unbreakable code
> is a 'requirement', then what other options are there...?
For all intents and purposes there are a lot of block ciphers that
would fit the bill. They are a heck of a lot more pratical and in some
sense empiracly secure. Sure there is no proof, but OTP's are not
provably secure in all instances (I could have copied the tape without
your noticing).
My original point was that OTP's are utopian crypto and can't possibly
exist.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Thu, 09 Nov 2000 21:46:55 +0000
Francois Grieu wrote:
>
> Paul Rubin <[EMAIL PROTECTED]> wrote:
>
> > No, it (factoring a 512 bit RSA key) was done again by some
> > Swedes to solve the last stage of the Simon Singh Cipher
> > Challenge last month. They used a lot of workstations but no Cray
>
> Interesting; is there a public report on the techniques they used,
> especialy the matrix part ?
They used their own modification of Peter Montgomery's CWI code to run
on very fat and fast SMP Alphas, including an ES40. They said it's like
a supercomputer except 1/100 the cost. While they made extensive mods
to Montgomery's code, they basically used the same NFS and blocked Lanczos
strategy used for RSA-155.
See http://www.simonsingh.com/cipher.htm for their paper (HTML, PDF, ps
or dvi).
--
Jim Gillogly
Highday, 19 Blotmath S.R. 2000, 21:37
12.19.7.12.13, 10 Ben 16 Zac, First Lord of Night
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Thu, 09 Nov 2000 23:47:53 +0100
Paul Crowley wrote:
>
> Mok-Kong Shen wrote:
> > No. I mean exactly GF(2^m), the finite field of order 2^m
> > (a Galois field that is known to exist). I don't know
> > the mathematical object you referred to or its relationship
> > to GF(2^m).
>
> GF(2)^m is the space of vectors of bits. For example, Rijndael mostly
> treats byte value as representing values from GF(2^8), but the affine
> transformation in the S-box can (AFAIK) only be sensibly defined in
> GF(2)^8 - ie treating the byte simply as a vector of bits and doing a
> matrix multiply followed by a vector addition.
The diffusion property of Rijndael's substitution is, I
suppose, mainly dependent on the 1/x transformation, which
is done in GF(2^8) and which was the object of my original
question. As noted by others in another previous thread,
the affine transformation seems to be able to be replaced
by similar ones without adverse effects. It would be
fine if someone would say something definite about these
points and give the corresponding explanations.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Thu, 09 Nov 2000 23:54:07 +0100
Francois Grieu wrote:
>
> "Martin Otten" <[EMAIL PROTECTED]> wrote:
>
> > You mean, instead of using very strong asymetric encryption all
> > the time, I should use a 512 bit RSA just for transmitting a
> > 128 symetric key for the main data, because symetric en/decoding
> > is much more faster.
>
> Yes. Note that 512 bit is a bare minimum, because this key will
> be a long-term key (reused from session to session) and 512 bit
> is factorable now, though with considerable effort (was done
> publicly once only, in mid 1999, by leading researchers using
> many workstations and a Cray with lots of memory). Better be safe
> and go to 1024 bits, which looks like safe for some time.
A bit off-topic: Since you mentioned Cray, I like to
point out that the currently top supercomputer of the
world is the Asci White of IBM with 8192 Power-3 processors.
M. K. Shen
------------------------------
Date: Thu, 09 Nov 2000 18:01:35 -0500
From: Zulfikar Ramzan <[EMAIL PROTECTED]>
Subject: Re: A question about RSA
You can actually easily find p and q given \phi(pq) by solving a couple of
simultaneous equations.
It turns out that you can also factor n=pq if you are given any (unknown) multiple
of \phi(n) -- I believe this result is contained in a paper of Gary Miller's --
which I'm fairly certain is referenced in the original RSA paper.
Also, it is possible to efficiently factor any n given \phi(n) and n -- for
example n=pqr (with p,q,r primes). This is more tricky than just a couple of
simultaneous equations.
Hope this helps.
Zulfikar.
Simon Johnson wrote:
>
> In article <[EMAIL PROTECTED]>,
> Chenghuai Lu <[EMAIL PROTECTED]> wrote:
> > Suppose we know n (= p * q), which is a multiple of two large primes,
> > and phi(n) where phi(x) is the Euler function. Can anybody give the
> > algorithm to find p and q in polynomial time?
> >
> > Thanks.
> >
> > --
> >
> > -Chenghuai Lu ([EMAIL PROTECTED])
> >
> oooh, u can't without solving P=NP.... for which there is a million
> dollars going.
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
--
--Zully
=======
Zulfikar Ramzan (AKA Zully)
Laboratory for Computer Science, MIT
NE43-311, (617) 253-2345
http://theory.lcs.mit.edu/~zulfikar/homepage.html
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: CHALLENGE TO cryptanalysts
Date: Thu, 9 Nov 2000 22:09:02 GMT
Sundial Services wrote:
> The now-familiar SSL (Secure Socket Layer) technology is a perfect
> example of security like this.
It's also important enough that one might actually be motivated
to try to crack it.
------------------------------
From: Bill Godfrey <[EMAIL PROTECTED]>
Crossposted-To: alt.freespeech,talk.politics.misc,talk.politics.crypto
Subject: Re: Updated XOR Software Utility (freeware) Version 1.1 from Ciphile
Software
Date: 09 Nov 2000 23:04:08 +0100
Reply-To: [EMAIL PROTECTED]
Richard Heathfield <[EMAIL PROTECTED]> writes:
> (Actually, I can't help thinking there might be a useful cryptographic
> role for SNA-Coil (provided I back out the lameness add-ins, of course).
> I'm not sure what that role might be, because it sure as hell isn't
> encryption!)
Given a working XOR program...
Deniability.
A, B and C want to publish (say) a 10k file. A does a 10k dump of
/dev/random and B XORs those random bits with the file.
Both A and B publish thier file of random bits simply as files of
random numbers.
C then announces that if you XOR the two files together, you get
the original file. A and B blame each other. "I just published a
load of random bits. It's the other one that must have done the
XORing!"
RIP dodging.
"Give us the key to this email."
"Okay. I use OTP, here's the key, and a decoder."
"It's the words to 'Ying tong yuddle aye po'!"
"Yep."
"Sod it. We'll jail you for two years anyway."
Bill, on holiday.
------------------------------
** 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
******************************
