Cryptography-Digest Digest #395, Volume #11 Thu, 23 Mar 00 00:13:01 EST
Contents:
Re: Factoring Large Numbers - I think I figured it out! (Xcott Craver)
Re: NIST publishes AES3 papers ("Trevor L. Jackson, III")
Re: Simple algorithm, difficult crack ("RecilS")
Re: implementing rot13 (Paul Schlyter)
Re: Hashing Algorithms. (basic newbie question) (Johnny Bravo)
Re: An RC5-like cipher ("Tom St Denis")
Re: Factoring Large Numbers - I think I figured it out! (Trav8race)
Re: Gray Code like (Vincent J. Perricelli)
Re: Card shuffling (DMc)
Re: An RC5-like cipher ("Scott Fluhrer")
Re: Does anybody know of a secure FTP server? (Paul Rubin)
Re: avoid man-in-the-middle known plaintext attack using a stream cipher ("Scott
Fluhrer")
Re: Factoring Large Numbers - I think I figured it out! ([EMAIL PROTECTED])
Re: 2048 Bit Encryption? ([EMAIL PROTECTED])
Re: Does anybody know of a secure FTP server? ("Adam Durana")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: 23 Mar 2000 02:09:02 GMT
Ben655 <[EMAIL PROTECTED]> wrote:
>
>Scott, I beg to disagree about the financial aspects. It does NOT beg the
>imagination to think that NSA would pay substantially more that a puny million
>dollars to be the sole possessor of such knowledge.
Why would they have to pay money for this?
>My advice to Mr. Hein would be: Seek professional help to protect your
>intellectual property in whatever way you can. If Scott is right and it is not
>commercially valuable then you can always publish later.
Patenting _is_ publishing, of a certain kind. No matter what,
he's going to have to publish. I suspect, however, that this
is all academic, because without knowledge of algorithmic analysis
(perhaps without knowledge of what a computer program is, etc,)
Mr. Hein likely doesn't even know how fast his method is, nor how
it compares to others. He may have simply rediscovered the sieve.
My own guess (JMHO) is that he got the mistaken impression, perhaps
through imprecise sources of info, that factoring was something we
didn't even have a method for, at any big Oh; and that he stumbled
upon _some_ way to do it. He does, after all, seem to believe that
he's "figured it out" without any idea of how much time it will take.
>Steve Rosenberg
-Scott
------------------------------
Date: Wed, 22 Mar 2000 21:29:12 -0500
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: NIST publishes AES3 papers
The Harvey Paper of Jan 2000 raises an interesting issue as regards the "winner" of
the AES contest. His paper presents three types of NIST decisions that would
characterize the winners (plural) of the contest. I'd like to pose an issue that his
paper mentions, but does not analyze. As a debatable resolution it would be:
"Resolved, that if NIST selects multiple cipher "winners" then the candidate
with the largest margin of strength should be one of them even if it is not close to
_optimal_".
An alternate thesis is:
"Resolved: That if NIST selects primary and secondary 'winners', that the
distinguishing characteristic of the primary winner should be strength instead of
optimality".
The rational for these conclusions is as follows. One of the advantages of multiple
winners is that such a decision leaves freedom for implementors to choose a cipher
optimal for their application. Thus multiple cipher selections relieve NIST from
having to make optimality choices in an application vacuum. How should the freedom
presented by multiple ciphers be utilized? A case can be made for diversity in that a
collection of diverse ciphers is presumably stronger than a collection of similar
ciphers. Another way to utilize this freedom, and the point of the above resolutions,
is to include the cipher that offers the largest margin of strength. Further, if
there is to be a primary winner among several other winners it should be distinguished
from the secondary winners on the basis of strength rather than any other criteria.
Are there any significant objections to these resolutions?
------------------------------
From: "RecilS" <[EMAIL PROTECTED]>
Subject: Re: Simple algorithm, difficult crack
Date: Wed, 22 Mar 2000 21:22:13 -0500
RecilS wrote in message <8bblqf$719$[EMAIL PROTECTED]>...
>I'm just gonna throw ideas out until I'm stopped so here goes one I've been
>thinking about...
Thanks for helping. I'm getting live help from some people now though.
Thanks
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: implementing rot13
Date: 23 Mar 2000 01:42:10 +0100
In article <[EMAIL PROTECTED]>,
Dan Day <[EMAIL PROTECTED]> wrote:
> On Tue, 21 Mar 2000 09:21:37 +0100, Terje Mathisen
> <[EMAIL PROTECTED]> wrote:
>>If you absolutely don't want to use an init function and a 256-byte
>>table, then I suggest something like this:
>
> And if you want to be really anal and do it in a single
> C/C++ expression:
>
> for (i=0; i<strlen(string); i++)
> {
> if (isalpha(string[i])
> string[i] = 'A' + (toupper(string[i])-'A'+13)%26 +
> islower(string[i])*('a'-'A');
> }
Why not instead:
for ( char *s=string; *s; s++)
*s += isalpha(*s) ? (toupper(*s)<('A'+13))*26-13 : 0;
:-)
--
================================================================
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
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Hashing Algorithms. (basic newbie question)
Date: Wed, 22 Mar 2000 21:12:32 -0500
On Wed, 22 Mar 2000 15:21:23 -0000, "@"
<[EMAIL PROTECTED]> wrote:
>Why are there no hashing algorithms using Pseudo-Random number generators?
>
>Why not perform a simple little digest on the message and use it to seed a
>random number generator, then produce a random stream of 160bits?
>
>How secure is this approach?
Pretty secure, but the problem is that you have to send the unencrypted
message to your recipient so they can generate the digest needed to
decrypt the encrypted copy you sent them.
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: An RC5-like cipher
Date: Thu, 23 Mar 2000 02:50:15 GMT
Samuel Paik <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > > for (i = 0; i <= 2*R+1; i++)
> > > {
> > > B = B + S[i];
> > > A = A ^ B;
> > > A = ROTL(A, B);
> > > SWAP(A, B);
> > > }
> >
> > I don't like this. the modification of A and B is entirely linear. I
can
> > for example work A backwards one round by doing
>
> Well, it isn't linear, it just is completely independent of any key bits
> and completely determined by known to the attacker data.
Um
B = B + S[i]
A = A ^ B
are BOTH linear. And after around I can rever the rotation, so ...
Tom
------------------------------
From: [EMAIL PROTECTED] (Trav8race)
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: 23 Mar 2000 03:10:49 GMT
>Okay, I'll bite -- how on earth would an ability to factor large
>numbers help in speeding up solutions to the traveling salesman problem?
>
I don't see that one.........try a neural network it may work alittle
better.....I think that is the fastest way I have ever seen.....but hey I am a
17 year old kid so I guess I probably don't know very much about that sort of
thing.....Richard I do give you a plus in my book for having a subscription on
popular science...I liked the article about dna computers too, but would a cray
not be faster at factoring(and cheaper) Than some prototype DNA computer that
isn't even doing complex operations yet?
------------------------------
From: Vincent J. Perricelli <[EMAIL PROTECTED]>
Subject: Re: Gray Code like
Date: Thu, 23 Mar 2000 03:17:00 GMT
In article <8ba1v8$942$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> I have encountered a form of encoding that's very similar to Gray
> Code, but isn't quite the same. In Gray Code only a single symbol at
> a single position may change when you move to an adjecent code word.
> What I'm looking at here is a list of code words where a new symbol
> is shifted in from the right when you move to the next code word and
> all codewords are unique.
>
> An example: 000 001 010 101 011 111 110 100
> [...]
> My question is if anyone knows what this kind of encoding is called
> and if there is any litterature about it and its uses.
.
You appear to be describing de Bruijn sequences, named after the
Dutch mathematician N. G. de Bruijn, who first published papers about
them in (I think) the mid-1940s. I believe work on such sequences
actually goes back about a century to a French mathematician, whose
name escapes me.
.
The literature on de Bruijn sequences is extensive. To get some of
its flavor, go to the Computer Science Bibliography at:
http://liinwww.ira.uka.de/bibliography/waisbib.html#search
Set the maximum number of hits to 170 and use the search string:
(Bruijn OR deBruijn) AND sequence*. You may also want to look at:
(Bruijn OR deBruijn) AND graph*.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: DMc <[EMAIL PROTECTED]>
Subject: Re: Card shuffling
Date: Thu, 23 Mar 2000 03:30:29 GMT
On Wed, 22 Mar 2000 23:38:26 GMT, [EMAIL PROTECTED] (Scott Nelson)
wrote:
>Randomness is a negative property.
I have no idea what you mean. Negative property?
>It's thus extremely difficult, if not impossible, to test for or
>quantify.
>That being said, It's possible to pick almost any property and
>method for assigning to a deck a number corresponding to that
>property. The probability of that number being assigned to a
>fully randomized deck can be calculated, and a comparison made.
>For example, order the deck, then shuffle it. Now count the number
>of cards that are in sequence. Call it the "sequence value." The
>probability of a particular sequence value is roughly;
>
>0: 0.37
>1: 0.37
>2: 0.18
>3: 0.06
>4: 0.015
>5: 0.003
>6: 0.0005
>7: 0.00001
>
I think the first few rifflings of a new, or intentionally ordered,
deck is far too limited in circumstances to be of much general
discussion value.
Also, the resulting state of a riffled deck has no analysis value
by itself. The difference between it and the previous state is the
beginning of some possible analysis value.
Choosing to focus solely on riffling extracted from a more complete
process of riffling, cutting, dealing, playing, card collecting, and
then back to riffling makes this discussion very much like determining
how many angels can fit on the head of a pin.
>
>Note that a sequence value of 1 doesn't _prove_ the deck was well
>shuffled, or poorly shuffled, but it does at least provide some
>measure. If the shuffler knows what our method is, and can choose
>the order of the deck, he is almost certain to be able to defeat
>the analysis. For example, simply reversing the order of the cards
>would result in a sequence value of 0, which is "good" but the deck
>is hardly well shuffled.
>
I do not agree. On your probability scale all possible sequences, or
lack of sequences, will total 1. Of course, you may have a mental
picture of what you mean by a sequence value of 0, and the
reversible card ordering which will cause that 0. I am interested in
seeing such an example from you.
[EMAIL PROTECTED]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: An RC5-like cipher
Date: Wed, 22 Mar 2000 19:27:38 -0800
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:HDfC4.61069$[EMAIL PROTECTED]...
>
> Samuel Paik <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Tom St Denis wrote:
> > > > for (i = 0; i <= 2*R+1; i++)
> > > > {
> > > > B = B + S[i];
> > > > A = A ^ B;
> > > > A = ROTL(A, B);
> > > > SWAP(A, B);
> > > > }
> > >
> > > I don't like this. the modification of A and B is entirely linear. I
> can
> > > for example work A backwards one round by doing
> >
> > Well, it isn't linear, it just is completely independent of any key bits
> > and completely determined by known to the attacker data.
>
> Um
>
> B = B + S[i]
> A = A ^ B
>
> are BOTH linear. And after around I can rever the rotation, so ...
Errrr, no. Each of them is a linear operation if you look in the
appropriate group, but if you look in that group, the other operation is
nonlinear. And so, while each one is linear, using them in combination is
not.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Does anybody know of a secure FTP server?
Date: 23 Mar 2000 03:49:54 GMT
In article <[EMAIL PROTECTED]>,
Abid Farooqui <[EMAIL PROTECTED]> wrote:
>I was just wondering if there is a secure FTP server available for
>different Unix flavors and possibly for NT, W2K. SSL works on Webservers
>but how about a strong ciphered FTP server? There is got to be someone
>out there who has applied SSL to something similar to FTP. I just can't
>find one.
Yes, there is a standard ftps (ftp over ssl) protocol.
There is even a standard port number for it, but I've forgotten it.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: avoid man-in-the-middle known plaintext attack using a stream cipher
Date: Wed, 22 Mar 2000 19:42:59 -0800
David Hopwood <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Adam Back wrote:
> > David Hopwood wrote:
> > > The most obvious, and a robust way of doing this is to append a MAC,
> > > with an output length of n bits. In principle it might be possible to
> > > combine the authentication with the encryption for performance
reasons,
> > > but previous attempts at doing that (e.g. PCBC, iaPCBC, CBCC) have
> > > not been resounding successes from a security point of view.
> >
> > What is iaPCBC? or is this a typo?
>
> iaPCBC is "integrity aware Propagating Cipher Block Chaining", by
> Virgil Gligor and Pompiliu Donescu, as described in [1] and [2].
>
> It was broken by David Wagner et al at Counterpane in [3] (despite
> a "proof of security"). There was also a thread about it in sci.crypt [4].
Huh? I thought that they made two claims in their original paper:
1. It was difficult to forge messages without knowing the key
2. It was more secure than CBC mode
I though David Wagner disproved claim 2, but I thought claim 1 is still
valid (or at least, not disproven yet).
If I'm wrong, I'd like to know the details.
--
poncho
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Factoring Large Numbers - I think I figured it out!
Date: Thu, 23 Mar 2000 03:56:44 GMT
In article <
1IcC4.5914$[EMAIL PROTECTED]>,
"Richard Anthony Hein" <[EMAIL PROTECTED]>
wrote:
>
> <[EMAIL PROTECTED]> wrote in message news:8bbcfv$p0t$[EMAIL PROTECTED]...
>
> > The traveling salesman problem is an NP-
> > complete problem (NP-complete problems are
> > the hardest NP problems). Factoring is
> > believed to be hard but there is no public proof
> > that it is hard so we must assume that your
> > assumption above is incorrect.
> > Regarding factoring on DNA computers, there
> > is a different major problem- Using Adelman's
> > original approach it would take 10^200000
> > liters of DNA to factor a 1000 bit number.
>
> "Data can be stored on DNA at a density of approximately 1 bit per cubic nm,
> while existing storage media require 10^12 cubic nm to store 1 bit",
> according to http://dna2z.com/dnacpu/dna2.html. It seems to me that you
> need 1 strand for each digit from 1 to the n + the complementary strands, +
> the path strands for a total of 3n + whatever is reasonable amount of
> strands representing n + whatever is a reasonable multiple of extra digit,
> path and complementary strands you would need to ensure that the DNA find
> each other and bond. One thousand bits is a lot but only 1000 cubic nm per
> strand. I figure about 1 m^3 is enough to do the trick. Maybe I am totally
> wrong, but I never heard that it was so much before.
>
> Please cite your source, because that doesn't seem right.
>
My source is a paper by D. Beaver called
"Factoring: the DNA solution" in "Advances in
Cryptology Asiacrypt 94" pages 419-423.
Different advances in DNA computing have
been made since Adelman's original
achievement but this paper gives a sense of
the amount of DNA needed for factoring large
numbers.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto
Subject: Re: 2048 Bit Encryption?
Date: Thu, 23 Mar 2000 06:35:26 GMT
On Wed, 22 Mar 2000 12:47:47 -0600, James Felling
<[EMAIL PROTECTED]> wrote:
>
>
>Anthony Stephen Szopa wrote:
>
>> [EMAIL PROTECTED] wrote:
>> >
>> > Even with the NSA's new holographic computer technology?
>> >
>> > see -> http://www1.ekstrabladet.dk/VisArtikel.iasp?PageID=43390
>> >
>> > On Tue, 21 Mar 2000 21:41:55 -0800, Anthony Stephen Szopa
>> > <[EMAIL PROTECTED]> wrote:
>> >
>> > >[EMAIL PROTECTED] wrote:
>> > >>
>> > >> Can the NSA break a 2048 bit encrypted email message? If they can,
>> > >> is there anything out there that they can't break?
>> > >
>> > >I don't think they can break OAP-L3
>> > >
>> > >http://www.ciphile.com
>>
>> Let's start to address this point by asking this question:
>>
>> What is your wildest upper estimate as to how fast such a computer
>> might be?
>>
>> Can it perform, maybe, 1E12 operations per second? Perhaps 1E24
>> operations per second? How about 1E100 operations per second?
>> Even 1E1000 operations per second?
>>
>> Even if this holographic computer can perform at 1E1000 operations
>> per second (or faster), it will still be ineffective in cracking
>> messages encrypted with OAP-L3 if the key were simply made long
>> enough. And this key would not be difficult to process by a user
>> of OAP-L3.
>>
>> OAP-L3 is not susceptible to factoring attacks.
>
>Nor is any other stream cypher (the family of cyphers that OAP-L3 fals
>into). OAP-L3 has never been subject to any formal reviewal process, and its
>algorithim has not been subjected to a public examination to determine its
>quality. There are many other stream cyphers of which this is true.
>
So in other words OAP-L3 isn't official at all. Does this mean that
it could have flaws?
>> If you want to
>> crack OAP-L3 encrypted messages you must guess a key, process
>> it to generate OTPs, then attempt to decrypt the message using
>> these OTPs.
>
>> This is quite a computationally intensive process
>> for each and every possible key.
>
>Assuming you are attacking OAP-L3 by brute force, as opposed to a more
>rational attack such as cryptoanalisys. Calling the bitstream it generates
>an "OTP" is a misnomer. A stream cypher may have an exceptionally long
>period, but it can and does repeat, and even if it does not have repeating
>values there will be characteristics of the stream that prevent it from
>generating truly random data( an absolute necessity in an OTP -- calling a
>stream cypher an OTP is like calling a rusted out chevy with no wheels up on
>blocks with a cracked engine block and no seats a car -- they are related
>entities, and may look similar to the untrained eye, but one does the job,
>and the other does not. )
>
>>
What are some characteristics of a streams without repeating values?
Are there ways to generate truly random data?
>>
>> If the OAP-L3 key length provides a security level of 1E100000
>
>1E100000 what? bits? possible keys?
>
>> and
>> this holographic computer can perform 1E1000 operations per second
>> then at a minimum it would take 1E99000 seconds to just generate all
>> possible keys (not to mention all the time it would also take to
>> generate the OTPs from each of these keys, etc.)
>
>Anyone worth their salt won't generate all keys, they will attack the
>algorithim. In addition just because there are X many possible keys doesn't
>mean that the algorithim used in key generation will select randomly from
>that space -- attacks based on the fact that most people want a
>password\phrase that is shorter than the Declaration of Independence will
>limit that to a much smaller amount in practice, and that is assuming that
>such a phrase is of good quality.
>
What are some steps that one would take to determine the algorithim?
>>
>>
>> If you are a US or Canadian citizen currently residing in the US or
>> Canada and your ISP is physically located in the US or Canada, you can
>> get the OAP-L3 Shareware Version 4.1 via email. Go to
>> http://www.ciphile.com and go to the Pricing and Ordering web page.
>> Click on the blue underlined "email" anchor tag in the third paragraph.
>> Send us this email.
>>
>> Or you can go to the web site and directly download the OAR-L3 random
>> number generation software directly.
>
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: Does anybody know of a secure FTP server?
Date: Wed, 22 Mar 2000 23:54:33 -0500
You can always encrypt traffic over a protocol that is not normally
encrypted if both parties are running SSH. And you should be running SSH if
you access your machine remotely! Check out http://www.openssh.com You can
forward traffic through your encrypted session, so its encrypted over all
networks and once it gets to the remote machine its decrypted and sent to
the local port the service runs on.
"Abid Farooqui" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I was just wondering if there is a secure FTP server available for
> different Unix flavors and possibly for NT, W2K. SSL works on Webservers
> but how about a strong ciphered FTP server? There is got to be someone
> out there who has applied SSL to something similar to FTP. I just can't
> find one.
> Thanks
> Sincerely,
> Abid Farooqui
>
------------------------------
** 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
******************************
