Cryptography-Digest Digest #461, Volume #13 Fri, 12 Jan 01 15:13:00 EST
Contents:
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: Different DES ("madcow")
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Novell Netware authentication (David Wagner)
Re: Different DES (John Myre)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Need of very simple algorithms? (John Myre)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: Need of very simple algorithms? (John Myre)
Re: NSA and Linux Security ("Douglas A. Gwyn")
Re: NSA and Linux Security ("Douglas A. Gwyn")
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: Differential Analysis (Benjamin Goldberg)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: NSA and Linux Security ("Paul Pires")
Re: NSA and Linux Security (David Wagner)
Re: keeping secret keys secret ("Joseph Ashwood")
Re: 16bit collision resistance hash function? (Jim Gillogly)
Re: HackSDMI challenge (Mok-Kong Shen)
Re: NSA and Linux Security (Mok-Kong Shen)
$$$$$ Compiler positions $$$$$ ("Kris DeGiacomo")
Re: NSA and Linux Security ("Joseph Ashwood")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 12 Jan 2001 16:13:52 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
DJohn37050 wrote:
>In this case I would say that anything DL keys can do, ECC keys can do better,
That may or may not be, but that's a different topic for discussion.
It seems hard to deny that integer-DL cryptosystems such as El Gamal,
Diffie-Hellman, and DSA are easier to implement than ECC, and their
implementations are simpler to verify. Apparently, if one truly finds
simplicity the deciding feature, then one should prefer El Gamal to
ECC, because it is indisputably harder to master the math needed for
implementing ECC than the math needed for implementing El Gamal.
Remember, this was held out as an important claimed advantage of ECC.
I find it misleading to conveniently omit mention of cryptosystems that
are even better than ECC in this regard.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 12 Jan 2001 16:20:19 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Bob Silverman wrote:
>These results show that there is an entire spectrum of time/space
>tradoffs that are possible (especially Hellman's result). One
>can go from O(1) space and exponential time to O(1) time and
>exponential space or (almost) ANYTHING IN BETWEEN.
Yes, but SPACE >> TIME only makes sense where we are using precomputation
to break many keys. It doesn't make any sense when breaking just one key.
And usually when one quotes the complexity of (say) factoring, one is
discussing the complexity of factoring a single number, not the amortized
cost of factoring many numbers after a lengthy one-time precomputation.
Consider an attack that uses space S and time T to break each key.
In the usual model, the cost of writing to (or reading from) each
unit of memory requires one unit of time. Consequently, if S >> T,
then there must have been some precomputation stage that took at
least S units of running time to initialize the memory, and the
total running time (including precomputation) is at least S+T [1].
[1] The above is a slight lie -- in theory, the precomputation might
run in time S-T and the total running time might be just S -- but
the conclusion does not change.
------------------------------
From: "madcow" <[EMAIL PROTECTED]>
Subject: Re: Different DES
Date: Fri, 12 Jan 2001 11:28:11 -0500
You can find it at the NIST web site:
http://www.itl.nist.gov/fipspubs/fip46-2.htm
The document also references some other useful standards, such as FIPS Pub
81, etc.
You may not be aware that DES is being replaced by AES:
http://csrc.nist.gov/encryption/aes/
<[EMAIL PROTECTED]> wrote in message news:93n7ac$f5l$[EMAIL PROTECTED]...
> Hi,
>
> I'm trying to write a DES encrypion routine and
> have read 3 different explanation on DES. My
> problem is that all this three explanations are
> different from each other. Here are some examples.
>
> 1. Different S-boxes how can this be?
> 2. One uses a table called PC1 another don't.
> 3. One uses IP and IP^-1 the others don't.
>
> Where can I find an official description of DES?
>
> Regards,
> Phyz
>
>
> Sent via Deja.com
> http://www.deja.com/
>
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 16:29:41 GMT
Subject: Re: Comparison of ECDLP vs. DLP
David Wagner wrote:
"
DJohn37050 wrote:
>In this case I would say that anything DL keys can do, ECC keys can do better,
That may or may not be, but that's a different topic for discussion.
It seems hard to deny that integer-DL cryptosystems such as El Gamal,
Diffie-Hellman, and DSA are easier to implement than ECC, and their
implementations are simpler to verify. Apparently, if one truly finds
simplicity the deciding feature, then one should prefer El Gamal to
ECC, because it is indisputably harder to master the math needed for
implementing ECC than the math needed for implementing El Gamal.
Remember, this was held out as an important claimed advantage of ECC.
I find it misleading to conveniently omit mention of cryptosystems that
are even better than ECC in this regard."
The conversation did start with RSA and ECC comparison. I do agree that the
arithmetic of DL is easier to understand than ECC, this is obvious as ECC
includes modexp math in it, plus the curve arithmetic. In my white paper, I
discuss ECC, DL, and RSA and comparing all of them, but a newsgroup response is
not a paper. And this topic is seeming to grow like topsy. I do try to look
at all factors and recommend that others do also when making any decision. But
it is always a judgement call when answering a question how much to answer.
As a cryptographer, I appreciate having 3 methods (RSA, DL, ECC) in my toolkit,
this is like having a hammer, saw and screwdriver, and allows more flexibility
in fitting the right solution to the problem. But to decide which fits best,
one needs to look at ALL the attributes. Saying c = m**e mod n, therefore use
RSA is practically a non sequitur, yet some are still saying it, apparently.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Novell Netware authentication
Date: 12 Jan 2001 16:41:22 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Chris Johnson wrote:
>Does anybody have any information on the authentication protocol used to
>log a user into a netware server ?
Check out the links at the bottom of
http://www.cs.berkeley.edu/~daw/compsec.html
Also, the following may be of interest:
http://www.cs.berkeley.edu/~daw/my-posts/netware-bad-rng
That won't give you everything, but it may get you started.
I haven't looked too deeply at the authentication protocol, but I did
look at some of their block ciphers and hash functions, and in general,
the stuff I looked at seemed more or less pretty terrible -- attackable
with easy differential cryptanalytic attacks, that sort of thing. But,
that's about par for the course, when you're looking at proprietary,
homebrew cryptosystems. (Caveat: That was several years ago. They could
have fixed all the flaws since then, for all I know.)
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Different DES
Date: Fri, 12 Jan 2001 09:32:13 -0700
[EMAIL PROTECTED] wrote:
<snip>
> Where can I find an official description of DES?
<snip>
http://csrc.nist.gov/fips/fips46-3.pdf
is about as official as you can get.
JM
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 16:43:42 GMT
Subject: Re: Comparison of ECDLP vs. DLP
David Wagner wrote:
"I don't understand. You said earlier that you want to be able to prove
that some private key exists. Being able to sign a random challenge proves
that some private key exists.
If you meant to talk about proving "validity" of the public key, and if
"validity" means something more than the mere existence of a private key,
could you tell me what you mean by "validity"?
Are you perhaps referring to the ANSI checks for weak keys? If so,
I must admit in advance that I will be underwhelmed by this so-called
`advantage'. The ability to check the public key for weak keys seems to
me to be such a second- or third-order concern for most real systems as to
not be a very important consideration in the choice of cryptosystems.
(By the way, in RSA it is also possible to validate the candidate
public key for weak keys: Just insist that the key generator issue a
non-interactive zero-knowledge proof of validity. It will be slower
and more complicated for RSA than for ECC, but it is possible.)"
On invalid keys, if they do not meet the spec, they should be assumed to be
weak.
See my talk at RSA 1999 or I can send it to you. POP, showing you own the
private key and PKV, showing a candidate public key is arithmetically valid,
are 2 different beasts. Conceptually, they are complementary. This is really
clear in the ECC case, if a bit flips in a private key (say), the public key is
valid, but I do not own the associated private key. Conversely, just because I
own the associated private key (that is, can invert the public key) does NOT
mean the public key represents a hard problem to invert. It might be that
ANYONE can invert it. So just because I can show POP does not necessarily mean
the public key is valid. When you recall the rare Intel HW bug and remember
that SW can have rarely occuring bugs also, it just seems prudent to me to do
both POP and PKV, especially for high value or high risk keys. This use of PKV
is akin to the "good engineering practise" of checking your calculations. But
these is another concern, a deliberate (somehow) invalid key. We see this at a
simpler level in the internet all the time, someone sends an invalid formatted
message, gets a buffer overflow (say), and gets root authority. Cheating, you
bet, outside the scope of the standard, sure; but adversaries can cheat and
what do we do about it.
Don Johnson
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Fri, 12 Jan 2001 09:42:57 -0700
Paul Rubin wrote:
<snip>
> $1 is a lot of money for a low end device. If my company wants to
> ship 100 million smart cards, and AES needs a $1 processor but
> Skipjack needs a 35 cent processor, I'm going to have an awful hard
> time convincing the CEO to give up $65 million from the company's
> bottom line in exchange for some abstract theoretical security
> improvement.
Especially as the security improvement probably would
have no practical effect: 80-bit keys are perfectly
adequate for almost everything, at present. By the time
that 80-bit keys are inadequate, the cost equation for
smart cards will be radically different, anyway.
JM
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 16:53:22 GMT
Subject: Re: Comparison of ECDLP vs. DLP
Regarding infeasibility, I recall where I read that someone once proved that a
heavier than air machine could NEVER leave the earth. He shows that the
chemical energy to overcome gravitation was MORE than could be stored by any
machine. His one teensy little mistake was to assume that the machine did not
lose weight. (This assumption is ALMOST always true when you think about it.)
However, a rocket loses weight as it rises and can therefore escape earth.
Don Johnson
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Need of very simple algorithms?
Date: Fri, 12 Jan 2001 09:54:56 -0700
Lyalc wrote:
>
> The cost may not all be attributed to any security improvement, but the
> 'comfort' of using a government ratfied choice of algorithm, which may even
> become so widely used that anyone not using it could seen as less competent.
In this particular case, Rubin mentioned Skipjack, which
naturally has at least as much government imprint as AES.
> In other words, a market call, not a technical decision.
Often true in general, but for $65M, I think I could spin
Skipjack pretty well: it was invented by the NSA! And from
the technical security perspective, you'd have a hard time
convincing me that smart-card transactions need more than
80-bit keys.
JM
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 17:03:52 GMT
Greggy wrote:
> I don't remember the NSA bothering too much to explain the NSA key in
> Windows...
They didn't have to; it wasn't their doing, and Microsoft explained
it quite well.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 17:09:28 GMT
Mok-Kong Shen wrote:
> You are right in theory. On the other hand, how is one
> in practice to get the needed accurate information?
My point is that if one does *not* have the necessary
information, it is only rational to withhold judgment.
There are various ways of setting up watchdog (oversight)
agencies, etc., but the most effective method is for
morality and ethics to be widely propagated throughout
society, making it difficult for any sizeable outfit
to successfully conspire against the people it is
supposed to serve.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Fri, 12 Jan 2001 10:19:11 -0800
DJohn37050 wrote:
> On invalid keys, if they do not meet the spec, they should be assumed to be
> weak.
> See my talk at RSA 1999 or I can send it to you.
Why don't you just post the URL?
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Fri, 12 Jan 2001 18:42:55 GMT
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
[snip]
> > 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.
>
> Yup should be 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);*/
> > }
>
> I would memset the table first. I dunno if = { 0 } will set all the
> elements. Also this function should work...
>
> > Any idea what I'm doing wrong, here?
>
> Is the SBOX valid? Look at my sboxgen code if you need pointers.
Of course the sbox is valid. In fact, you even said that my AES sbox
generating code was correct. Besides, even with an invalid sbox, it
should be quite impossible to get all differences have probability
1/256. In fact, I think that all differences must be (even number)/256.
So what's wrong with my differential probability calculating code?
> > > > 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 :)
>
> Hehehehe
So what's wrong with my differences calculating code now?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 12 Jan 2001 18:53:05 GMT
Subject: Re: Comparison of ECDLP vs. DLP
Roger Schlafly wrote:
"DJohn37050 wrote:
> On invalid keys, if they do not meet the spec, they should be assumed to be
> weak.
> See my talk at RSA 1999 or I can send it to you.
Why don't you just post the URL?"
Good idea, it was at RSA 2000. I need to request putting in as a Certicom
white paper. In the meantime, I can send out individual requests.
Don Johnson
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 10:48:48 -0800
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Mok-Kong Shen wrote:
> > You are right in theory. On the other hand, how is one
> > in practice to get the needed accurate information?
>
> My point is that if one does *not* have the necessary
> information, it is only rational to withhold judgment.
>
> There are various ways of setting up watchdog (oversight)
> agencies, etc., but the most effective method is for
> morality and ethics to be widely propagated throughout
> society, making it difficult for any sizeable outfit
> to successfully conspire against the people it is
> supposed to serve.
Careful, That sounds remarkably like common sense.
Conspiracy theory works against that. It must be hard
to instill a sense of respect and duty to the public when
so many of those they should respect and protect are
(best case) missing anything resembling rational judgement
and (worst case) paranoid and resentful. Maybe
we get the government we deserve. Perhaps we have
had slightly better than we deserve and should thank
our lucky stars.
Too long we have been "consumers of government
services" rather than a part of the government.
Simply voting once every four years just doesn't
do it. Those who serve, do our duty by proxy.
1, If they screw up, we screwed up.
2, You can't take a bad act (real or imagined)
and paint every individual in the entire staff with it
and remain virtuously un-painted.
Paul
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NSA and Linux Security
Date: 12 Jan 2001 19:15:29 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>My point is that if one does *not* have the necessary
>information, it is only rational to withhold judgment.
Ahh, but there's the rub.
The question, as always, is where the burden of proof lies.
If you trust the NSA, you might argue that until we have incontrovertible
proof of abuse, we should give the NSA the benefit of the doubt.
However, if you do not have this level of blind faith in NSA, you
might argue exactly the opposite: If there are credible allegations
of abuse, they should be investigated very thoroughly, even if the
evidence is not incontrovertible.
And when one considers that the NSA are the only folks with the
information one needs to judge whether there was abuse, it seems
that placing the burden of the proof on the NSA may be the best choice.
Consider the requirement that all drivers have insurance.
If you get pulled over and can't show your insurance card ("I forgot it"),
is the policeman going to accept that? No, probably not. The reason is
that the owner of the insurance is the one who has the documents needed
to prove whether or not he is in violation. The police do not have any
easy way to tell. Thus, the burden of proof is on the owner, not the cops.
In other words, all other things being equal, it is rational to place
the burden of proof on the party who has the ability to prove or disprove
compliance.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: keeping secret keys secret
Date: Fri, 12 Jan 2001 11:07:15 -0800
You seem to have a fairly solid basic idea. Personally here's what I'd
change to make the security more apparent.
Each user has a key pair, a diffie-hellman varient (call these UserPubK, and
UserPrivK), they are all in the same field. You have a choice of using group
keys, or single target keys. If you choose group keys then your steps will
be different from what I give.
When adding a file, the user adding the file chooses a random key (K),
computes all the shared secrets will all the other valid users, for each
user hash the shared secret(Sk = hash(shared secret)), use each individual's
shared secret to encrypt the key (SS = 3DES(Sk, K)). Store those values with
their names alongside the file. Encrypt the file using the chosen key
(cryptFile = 3DES(K, file)). Send the encrypted file (with the name,
encrypted value pairs along with the source UserPubK) to the server.
For decryption the user requests the file, the (name, encrypted key) pair,
and the UserPubK that submitted the file (call it UserPubKSubmit). User uses
the personal UserPrivK along with UserPubKSubmit to generate the shared
secret, use the shared secret to decrypt the real key, use the key to
decrypt the file.
This moves trust away from the server, the server is only trusted to not
mangle or delete the files. You can add signatures and anything else you
want to the mix to help out security.
Joe
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: 16bit collision resistance hash function?
Date: Fri, 12 Jan 2001 11:25:19 -0800
"[Basic]" wrote:
>
> thats exactly the problem. I only have 16bit to hash a single 64bit block. I
> can not calculate md5 for rounds and rounds and store the first 16bit as the
> maximum space for the hash value IS 16bit.
If you know which 64-bit values you'll need to be hashing, you can choose
your hash function to minimize collisions in that specific set of hashes.
If this is what you need, do a web search on "perfect hash" and "cichelli".
Obviously if you need to hash all 2^64 64-bit values your 2^16 buckets will
be quite full, but if fewer than 2^16 of them are of interest, you'll be
able to do much better. I believe there's a GNU package called "gperf"
that does the heavy lifting for you.
This isn't a cryptographically secure operation, but you did say collision
resistance was the only criterion you needed to satisfy.
--
Jim Gillogly
Sterday, 21 Afteryule S.R. 2001, 19:16
12.19.7.15.17, 9 Caban 20 Kankin, Second Lord of Night
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: HackSDMI challenge
Date: Fri, 12 Jan 2001 20:34:31 +0100
Julien Stern wrote:
>
> A web page detailling our results is located at
> http://www.julienstern.org/sdmi/
I have no knowledge but a couple of questions of sheer
ignorance: (1) What is norm(s_i[j])? (2) You wrote that
the function beta is unknown to you. So how could you
reverse the marking operation performed on s[j] that involves
that beta? (3) In actual work, you will only have the marked
version of the music and not the unmarked version and I guess
that the mark is only at a specific location that is unknown
to you. How are you going to find that location? Thanks in
advance.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 20:34:37 +0100
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > You are right in theory. On the other hand, how is one
> > in practice to get the needed accurate information?
>
> My point is that if one does *not* have the necessary
> information, it is only rational to withhold judgment.
>
> There are various ways of setting up watchdog (oversight)
> agencies, etc., but the most effective method is for
> morality and ethics to be widely propagated throughout
> society, making it difficult for any sizeable outfit
> to successfully conspire against the people it is
> supposed to serve.
My point is that, if one doesn't have 'acurate' information
about something, it doesn't follow that one doesn't
have to worry about the probability of its existence or
its possible impact. Pushing up moral and ethics is good
for the society. Spreading the influence religion is also
good, maybe even better. But on the other hand we learned
from history that these are not strong engough against certain
political forces, at least during certain not too short
time intervals. Yes, in democratic countries, this shouldn't
apply. But then one comes into the vicious circle of having
to define 'democractic countries', I am afraid.
M. K. Shen
------------------------------
From: "Kris DeGiacomo" <[EMAIL PROTECTED]>
Crossposted-To: alt.sources.crypto,ott.jobs
Subject: $$$$$ Compiler positions $$$$$
Date: Fri, 12 Jan 2001 14:42:59 -0500
Company Profile Description
Our client is a leading edge start-up located in Ottawa's Silicon Valley
North. The company develops and sells security products and technologies
that enable E-Commerce. Their mission is to become a leader in the market
for software protection technology and applications.
This company has developed a radical new security technology that converts
software into a tamper resistant form. It is believed to be the first
software technology to provide a high degree of protection against both
tampering and reverse engineering. The company is focused on commercializing
this technology through partnerships with leading OEMs and by developing
applications of the technology.
This dynamic organization is growing rapidly with unbounded opportunity for
career growth and continued learning. Competitive salaries and benefits are
standard along with stock options.
Responsibilities
This expert would be expected to design new software in the below areas for
incorporation into our client’s secret-hiding, tamper resistant software
encoding tools, and to program key components for incorporating such designs
into tool-set.
Skills Required:
Knowledge any or a combination of the following: Optimization, Program
Transformation, Combinatorics, Obfuscation Techniques, Program slicing
Techniques, Numerical Analysis, Semetric, Representations for Control- and
Data-Flow, Control- and Data-Flow Dependencies.
Knowledge of Java, C++, Eiffel, Modula-3, or some similar object-oriented
language, is essential.
--
Please forward all resumes to [EMAIL PROTECTED]
Thank you for your time and have a super day!
Kris DeGiacomo
Placement Director
(613) 237-8888 ext.336
[EMAIL PROTECTED]
[EMAIL PROTECTED]
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Fri, 12 Jan 2001 11:36:58 -0800
<[EMAIL PROTECTED]> wrote in message news:93n794$f51$[EMAIL PROTECTED]...
> In article <93mfk8$5j0$[EMAIL PROTECTED]>,
> the problem is not to find collisions.
Actually the problem is exactly collisions. The problem is that if finding
collisions is easy, then it is possible to reverse the DSA computation to
some degree.
> It has been shown that for the
> 160 bit SHA-1 hash, the likelihhod of finding a collision is extremely
> rare, and beyond the realm of reasonable worry.
Actually all that has been shown is that SHA-1 has a maximum security level
equivalent to the maximum security level of 160-bit hash. That is trivial
information. However no lower bound has been created for it. Various
specific bounds have been, we know it's differenetial cryptanalysis
resistance is suitable. We know a lot of things about it, but we haven't
proven it's resistance against the unknown attack.
>
> the problem is a different one, that of the hash *leaking* the secret
> key, if the hash algorithm is broken:
The hash won't leak the key, the hash is completely seperated from the key,
the hash however will allow the DSA computation to be reversed to gather
information about the private key.
[snip information of little import]
> but, this is a general problem in how the algorithm is
> cryptographically implemented, and not really an *NSA* security issue.
Far from it. This is an issue of the design of the cryptographic primitive,
specifically the design of DSA, which as I recall came from the NSA.
Now as to motivation for the NSA, to either give us a weak algorithm, or a
strong one. For encryption it is clear that from their perspective they
should give the public a cipher that is strong enough to resist all public
work, but is weak to them, DES seems like a good example, 56-bits was
assumedly weak enough at the time for them to brute-force as necessary, but
strong enough against attacks from the public that it would remain unbroken
for long enough. On the other hand, with a hash algorithm, and more
importantly with a signature algorithm, their goal is better placed at
certification of gathered communication. The link here needs to be as strong
as possible, so the algorithm needs to be as strong as possible without
leaking NSA only information, based on what we have seen DSA and SHA-1 both
meet this requirement. There was an attack on SHA, it reduced the strength
of the hash by a very minor amount, SHA-1 was published before that attack
came to light. More importantly from my view, I have examined SHA-1, I see
little likelihood of an attack against it reducing it below 2^70 work (from
the current 2^80), and that is being probably overly pessimistic.
Joe
------------------------------
** 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
******************************
