Cryptography-Digest Digest #458, Volume #13 Fri, 12 Jan 01 00:13:00 EST
Contents:
Re: Comparison of ECDLP vs. DLP (Bill Unruh)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: Comets, Meteors, and Mitotic Spindles /Mars Life angle ("Scot Mc Pherson")
Re: NSA and Linux Security (Greggy)
Re: NSA and Linux Security (Greggy)
Re: NSA and Linux Security (Greggy)
Re: NSA and Linux Security (Greggy)
Re: NSA and Linux Security (Greggy)
---- Free public domain encryption is released from EAR. (Greggy)
Re: Differential Analysis (Benjamin Goldberg)
Re: rc4 in javascript bug (Benjamin Goldberg)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 12 Jan 2001 01:29:13 GMT
In <[EMAIL PROTECTED]> Benjamin Goldberg <[EMAIL PROTECTED]> writes:
]DJohn37050 wrote:
]>
]> Bob Silverman said:
]> > It is clear that time/space issues can not be separated. Any
]> > algorithm can be broken in time O(1) if enough space for suitably
]> > large lookup tables is available."
]>
]> I would say that time is involved to BUILD the lookup table and that
]> that TIME counts as part of the TIME cost of the attack.
]> Don Johnson
]And what keeps one from making all entries of the table simultaneously/
]in parallel? Each entry takes O(1) time to create, right?
And where will you find 10^50 machines to carry out this parallel table
build? Any crypto system can be broken in O1 time is you use O(2^N)
machines. It is an emminantly parallelizable problem.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 01:32:08 GMT
Subject: Re: Comparison of ECDLP vs. DLP
I thought this was clear but will spell it out more. The REASON for the order
(power) of the poly time complexity is due to the COMPLEXITY of the algorithm.
The higher the order the more complex it is. So I was not just speaking about
TIME, I was speaking about complexity also.
RSA Key Gen compared to ECC key gen is complex. Both must be done in private
protected code that is not available for normal examination. Out pops a public
key. How do I know it is any good. Well, I MUST have the output of a good
RNG, or a bad guy attacks that. With ECC, once I have that, that IS the
private key, a random number in a specific set of domain parms. WIth RSA, I
need to test primes, do GCD, calculate an inverse, etc. This is more open to
failure, wierd rare errors, etc.
Now look at the output. With ECC, I can validate for a candidate public key
that a private key logically exists. With RSA, I can only do limited
validation without access to the private key or an oracle knowning the private
key.
So not only is RSA more likely to have an error in key gen, it is also more
difficult to test to see if there WAS an error. If I have a "bet-the-company"
key, I really, really, really want to KNOW there was no error, such as the
Intel HW bug, or a SW bug, etc.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 12 Jan 2001 01:47:34 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
DJohn37050 wrote:
>I thought this was clear but will spell it out more. The REASON for the order
>(power) of the poly time complexity is due to the COMPLEXITY of the algorithm.
>The higher the order the more complex it is. So I was not just speaking about
>TIME, I was speaking about complexity also.
I think you are talking about `computational complexity' here,
right?
But `computational complexity' has nothing to do with whether
it is difficult to write a RSA implementation (or verify one).
A cryptosystem might be slow to encrypt, but easy to implement.
The CPU time it takes to do a RSA encryption has nothing to do
with the difficulty of writing to code to perform this computation.
They are orthogonal.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 12 Jan 2001 01:49:56 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
DJohn37050 wrote:
>With ECC, I can validate for a candidate public key
>that a private key logically exists.
Yeah, but why would you want to? What threat does this protect against?
But, if for some reason you need to verify this property, it is trivial
to do, no matter what cryptosystem you use: just verify that the key-owner
can sign a random challenge.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 12 Jan 2001 01:51:07 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
DJohn37050 wrote:
>So not only is RSA more likely to have an error in key gen, it is also more
>difficult to test to see if there WAS an error. If I have a "bet-the-company"
>key, I really, really, really want to KNOW there was no error, such as the
>Intel HW bug, or a SW bug, etc.
In that case, it seems that you will want El Gamal, not ECC or RSA.
El Gamal keys are even easier to verify than either ECC or RSA.
------------------------------
From: "Scot Mc Pherson" <[EMAIL PROTECTED]>
Crossposted-To: alt.sci.astro.eclipses,sci.geo.earthquakes
Subject: Re: Comets, Meteors, and Mitotic Spindles /Mars Life angle
Date: Fri, 12 Jan 2001 01:59:14 GMT
Part of the interest of finding things is finding them and not having them
placed on a silver platter for you...How much better do you feel when you
look at Jupiter through your backyard self made telescope? Does it compare
to looking at a photo taken by the Hubble? I would prefer my own telescope
and the work that goes along with it.
I am sorry if I disappointed you by merely pointing the direction to look.
Next time I will make sure I take all the fun out of it for you
Scot Mc Pherson
Ed Augusts <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Scot Mc Pherson wrote:
> >
> > > After all, do you see a mars-sized crater on earth from the moon's
> > > creation?
> >
> > Actually yes you do...Find a map or globe that displays underwater
> > terrain...Then look at Australia again....Then come back here and say
the
> > above again....I know you won't =)) I believe the phrase you will come
up
> > with will be something like holy s***
> >
> > Scot Mc Pherson
>
> Instead of referring us to the map or globe, it would have been nice if
> you had said, "there is a two thousand km diameter depression in the
> shape of a crater located...." You are not giving information, you are
> just teasing. See, I would have been very interested to know if this
> underwater feature is in the middle of the Indian Ocean, or in the
> Indonesian Archipelago, but I'm not going to go on a big search for the
thing!
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 03:21:16 GMT
> > > Prehaps the NSA have been forced to shift there policy somewhat
due
> to
> > > the possibilitity of having their funding cut. In the times of the
> > cold
> > > war, the NSA needed to be a secret agency which did secret things.
> > > Since this role doesn't exist in the same capacity as before, they
> > must
> > > be forced to do other work.
> >
> > What on earth could you possibly point to as the basis for your
> > statement?
>
> Okay, there is no real foundation for this argument however is there
> any _real_ evidence for yours? We're both stabbing in the dark.
Lots of history and good old common sense, pal.
> If the American Goverment allowed the existance of an unaccountable
> power then they are dumb and stupid.
You have an unrealistic view of how any government works, let alone
America's. The government is corrupt and the people are sheep.
> The government of the USA pays for the NSA,...
So you know who they work for. That is a step in the right direction.
> > Fine, but what of Echelon?
> What about it?
What the hell do you mean, "What about it?" You sound like violating
the privacy of citizens is fine with you!!!
> Echelon is designed to catch the stupid criminal who thinks e-mail is
> secure & safe.
I don't believe you are naive to believe that lame excuse. That's like
the one, "The truth about JFK's assassination must be kept from the
people of America for national security reasons."
>>It should be the policy of the United States of America never to enter
>>into secret association with any entity. If a foreign government
>>cannot do business with the United States in the open, then that
>>should be their problem not ours.
> But if the NSA is unaccountable, as you say, then it wouldn't have to
> answer to law or policy, it would still communicate anyway.
I can't believe you are saying this.
> > With the cloak of National Security, those in power have no
> > accountability to the people of America and as a result, time and
> > again, we have seen criminal actions covered up.
>
> But of course, because the 'criminal' actions are covered up you have
> no evidence to back up these claims.
Oh, come on! You aren't that naive!
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 03:27:32 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Greggy wrote:
> > Take your pick, but reality is, they are dark and they have
> > chosen we the people to be their next target.
>
> That's not reality, it's a figment of a parnoid imagination.
> I know many fine people who work for NSA, and they would not
> participate in a domestic espionage program. Indeed, they
> are trained in the requirement to obey the laws against such
> activity.
I suppose the fourth amendment does not mean much to you...
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 03:33:03 GMT
In article <93l5m9$ol7$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> Perhaps I
> > am paranoid but I wish that I was confident that neither NSA nor
UKUSA
> > product leaked to the FBI.
> >
> >
> by your reasoning, would you be reluctant to use a PGP dh/dss key just
> because the SHA-1 was developed by the NSA?
>
> {there is, in fact, a sizable minority of people who will use only RSA
> keys [apart from the ADK issue ] primarily for this reason, but most
> people are content with the scrutiny that SHA-1 has undergone by
> experts in the cryptographic community, without finding a 'backdoor'
in
> the program.}
>
> similarly, since the NSA version of Linux is open source, it is
> reasonable to assume that if there were a backdoor in the program,
> *somebody* of the very many capable people in the Linux community
would
> find it, gain instant fame, and the NSA would have a great deal of
> uncomfortable explaining to do.
I don't remember the NSA bothering too much to explain the NSA key in
Windows...
>
> granted, that if they *could* put in a backdoor without worrying about
> being found,
That's right. They could put one in without worrying because so what
if it is found? At least they tried. If it was not found, they would
be ahead. If it were found, they would not lose any ground, would they?
Look, the bottom line is if they don't trust me with national security
then neither do I trust them with national security.
Sort of like if a politician doesn't trust me with a gun, I don't trust
him with an office. It really is simple if you want to let go of your
preconceived opinions and just think about it for a moment.
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 03:34:54 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> "Douglas A. Gwyn" wrote:
> >
> > William Hugh Murray wrote:
> > > ... I have spoken the same message in front of NSA people for
> > > two decades and have yet to have one of them take offense.
> >
> > "Eternal vigilance is the price of liberty" applies to one's own
> > government as well as to foreign ones, perhaps moreso since the
> > native threat is subtler and more long-range. (How to boil a
> > frog.) But accurate information is required if one is to keep a
> > meaningful watch.
>
> This is a very difficult area in which to write in any case. I try to
> choose my words carefully so as not to mislead. However, my
experience
> is that no matter how careful I am, I often fail.
I sort of was like that. Then I decided, what the hick. Life is too
short to sit in front of a keyboard hoping you please everyone...
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Al Gore and the Florida Robes - More than just another rock group;
a clear and present danger to America's national security.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 03:36:46 GMT
In article <93leji$cm0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > Greggy wrote:
> >> Take your pick, but reality is, they are dark and they have
> >> chosen we the people to be their next target.
>
> > That's not reality, it's a figment of a parnoid imagination.
> > I know many fine people who work for NSA, and they would not
> > participate in a domestic espionage program. Indeed, they
> > are trained in the requirement to obey the laws against such
> > activity.
>
> I'm sure people would have said that at other times as well, but
> history has shown that the NSA *has* spied on U.S. citizens within its
> borders in the past. Just out of curiosity, what gives you such
> apparent confidence that things have changed?
More importantly, why should we share his apparent confidence?
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: ---- Free public domain encryption is released from EAR.
Date: Fri, 12 Jan 2001 04:08:00 GMT
EAR 734.3 discusses items subject to the EAR. In one section,
encryption is discussed:
EAR 734.3(b)(3)
Publicly available technology and software, except software controlled
for EI (encryption) reasons under ECCN 5D002 on the Commerce Control
List that:
(i) Are already published or will be published as described
in 734.7 of this part;
...
However, notwithstanding 734.3(b)(2), encryption source code in
electronic form or media (...) remains subject to the EAR (see 734.3(b)
(3)).
In other words, this is saying that technology and software are
controlled by the EAR, except for encryption software that meets one of
the criteria outlined, one being publicly available through publication
as described in 734.7. If encryption source code does not meet the
requirements listed in 734.3(b)(3), then it remains subject to the
EAR. Now if it is not subject, then there is no jurisdiction over it.
740.13 - Technology and Software Unrestricted (TSU)
740.13(e) Unrestricted encryption source code
(1) Encryption source code controlled under ECCN 5D002, which would be
considered pubicly available under 734.3(b)(3) [e.g.- publication of
source code] of the EAR and which is not subject to an express
agreement for the payment of a licensing fee or royalty for commercial
production or sale of any product developed with the source code IS
RELEASED FROM EI CONTROLS AND MY BE EXPORTED OR REEXPORTED WITHOUT
REVIEW under license exception TSU, provided you have submitted written
notification to BXA of the Internet location...
...
(4) Posting of the source code or corresponding object code on the
Internet (...) where it may be downloaded by anyone would not
establish "knowledge" of a prohibited export...
What this says is in effect that encryption software that is made
publicy available is released from the EAR - the EAR has no
jurisdiction over the exporting of the software. You can freely post
your source and object code to the web for anyone to download without
fear of violating the EAR.
According to these two sections, it seems clear that if someone wishes
to post their strong encryption software to the web, then all they need
to do is make it publicly available and notify BXA of the download web
page address at the time (or before) they actually post it.
Now I called the BXA and asked about Q&A #26 (see
http://www.bxa.doc.gov/Encryption/Oct2KQandAs.html). Specifically, I
asked if posting is adequate for making the source publicly available
or must I publish it some other way first to qualify it for posting on
the internet. The person I talked to was very certain in her answer,
that you can post it and that is adequate.
This makes sense if you read through the material from BXA, such as the
Q&A. You will find that if the author of the software is WILLING to
let his work go public with no rewards to follow, then the US
government is willing to not infringe on the author in any way.
I am also requesting from the BXA a formal written legal opinion to
affirm this position which should be returned in about a month.
If anyone has any twists to this to share, I am all ears. Once I get
the opinion from BXA, I will make all of my source and binaries freely
available at www.ciphermax.com. Until then, I want to make sure I
don't jump the gun on an interpretation of the EAR that only two people
(that I know of todate) share.
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Fri, 12 Jan 2001 05:08:31 GMT
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > Tom St Denis wrote:
> > >
> > > In article <[EMAIL PROTECTED]>,
> > > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > > > Tom St Denis wrote:
> > > > >
> > > > > In article <[EMAIL PROTECTED]>,
> > > > > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > > > [snip]
> > > > > > In the AES sbox, there are 23 diferentials which have a
> > > > > > probability of 6/256. There are a large number of
> > > > > > differentials with probability of 4/256, 2/256, and 0.
> > > > >
> > > > > Wrong. The highest xor-pair probability is 4/256 not 6/256.
> > > >
> > > > Each of these XOR pair differences occur with probability 6/256.
> > > >
> > > > 08->53 09->62 15->3a 26->94 28->5f 2e->52 34->73 3f->16 46->31
> > > > 4d->80 57->30 5b->5a 68->26 71->c8 7a->b9 80->a6 85->f4 86->27
> > > > 89->c4 ce->e8 db->d2 de->7e fe->d8
> > >
> > > Something is wrong in your prgoram. There are NO pairs higher
> > > then 4/256 in the Rijndael sbox. It's fact given the construction
> > > of the sbox. Basically the simple way to calc an xor-pair table
> > > is do this
> > >
> > > table[256][256] = { 0 };
> > > for (x = 0; x < 256; x++)
> > > for (y = 0; y < 256; y++)
> > > ++table[x^y][sbox[x]^sbox[x^y]];
> > >
> > > Then scan the table for the highest element (ignoring
> > > table[0][0]).
> > >
> > > (Can you tell I program in C? hehehehe)
> >
> > Hmm. What I've been doing for finding XOR pairs is this:
> > for (x = 0; x < 256; ++x) {
> > table[256] = { 0 };
> > for (y = 0; y < 256; ++y)
> > ++table[sbox[x]^sbox[x^y]];
> > for (z = !x; z < 256; ++z) {
> > if( table[z] <= 4 ) continue;
> > fprintf(f,"%02x->%02x ",x,z);
> > fprintf(f,"(%d/256)\n",table[z]); }
> > }
> >
> > Is this correct or incorrect?
>
> Incorrect. You tell me why :-)
The code is mostly similar, except where you have the line:
++table[x^y][sbox[x]^sbox[x^y]];
I have something which is equivalent to:
++table[x][sbox[x]^sbox[x^y]];
I'm not quite certain why there should be a difference.
Anyway... I now have changed to something resembling your code, and it
strangely tells me that *all* differences (even 0->0) have probability
1/256 -- which is clearly wrong.
Here's my new code:
void probs(/*char* file,*/ unsigned char *sbox) {
int x, y;
FILE * f = /*fopen(file,"w")*/ stdout;
unsigned int table[256][256] = {0};
for( x = 0; x < 256; ++x )
for( y = 0; y < 256; ++y )
++table[x^y][sbox[x]^sbox[x^y]];
printf("Differences calculated\n");
for( x = 0; x < 256; ++x )
for( y = 0; y < 256; ++y ) {
if( table[x][y] <= 1 ) continue;
fprintf(f,"%02x->%02x ",x,y);
fprintf(f,"(%d/256)\n",table[x][y]);
}
/*fclose(f);*/
}
Any idea what I'm doing wrong, here?
> > Here's my AES sbox generating code (copied verbatim):
[snip]
> > Is this correct or incorrect?
> >
> > I suppose that either the XOR pair, or the sbox generator, is wrong,
> > but I don't know which, or how.
>
> The former is wrong.
Good, I guess -- I was afraid that both might be wrong :)
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: rc4 in javascript bug
Date: Fri, 12 Jan 2001 05:08:34 GMT
[EMAIL PROTECTED] wrote:
>
> Hi there !
>
> I adapted the rc4 to javascript but it seems to have a bug. Although
> encypting the same string twice by nesting the cipher function call
> returns the plain text without any problems, it seems that encrypting
> it once, copying the encrypted text and having it decrypted fails to
> decrypt some characters.
It's undoubtably due to the fact that when copying the ciphertext,
information gets lost, due to non-printable characters not getting
copied.
> Basically, I encapsulated the encrypted text in a html file and the
> encrypted text is the body of the html file. I load in the html reader
> file the encrypted text in an invisible floating frame and get the
> encrypted text through the document object model, submit it to my rc4
> function along with the key.
Simply encapsulating is not enough. The encrypted text should be
encoded with some sort of all-printable method, such as hexidecimal,
base64, or uuencode.
[snip]
> <script>
> <!--
> function cipher(source,key){
> var state=new Array();
> var outp="";
> for (i=0;i<256;i++){
> state[i]=i;
> };
> var j=0;
> for (i=0;i<256;i++){
> j=(j+state[i]+key.charCodeAt(i%key.length))%256;
> swap("state[i]","state[j]");
> };
Why not write this as swap(i,j) (with swap redefined slightly)
> i=0,j=0;
> for (k=0;k<source.length;k++){
> i=(i+1)%256;
> j=(j+state[i])%256
> swap("state[i]","state[j]");
> outp+=String.fromCharCode(source.charCodeAt(k)^state[(state[i]
> +state[j])%256]);
> };
> function swap(item1,item2){
> eval("var temp="+item1);
> eval(item1+"="+item2);
> eval(item2+"="+temp);
> };
You would be much better of defining swap as:
function swap(index1, index2) {
var temp = state[index1];
state[index1] = state[index2];
state[index2] = temp;
}
With no eval()s anywhere in it. Doing eval is slow.
> return outp;
> };
> /-->
> </script>
>
> What do you thing might be wrong ? I need to escape before encryption
> and then unescape after decryption when encrypting html code but I
> want to sort this for plain text only, encypting html is easy after
> that.
That's backwards, I think. After encrypting, encode with hex, base64,
or uuencoding. Before decypting, decode.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
