Cryptography-Digest Digest #177, Volume #10 Sat, 4 Sep 99 23:13:03 EDT
Contents:
Re: NSA and MS windows ("Roger Schlafly")
Re: Alleged NSA backdoor in Windows CryptoAPI ("rosi")
Re: http://www.tmechan.freeserve.co.uk/wincrypt.html ("Trevor Jackson, III")
Re: Newbie needs help (Eric Lee Green)
Re: 512 bit number factored ("Trevor Jackson, III")
Re: IDEA- safe? ("Trevor Jackson, III")
Re: 512 bit number factored (Bob Silverman)
Re: Alleged NSA backdoor in Windows CryptoAPI ("Trevor Jackson, III")
Re: new user (Tom St Denis)
Re: IDEA- safe? (Tom St Denis)
criteria effecting the ability to factor? (Tom St Denis)
Re: THINK PEOPLE (Tom St Denis)
Re: THINK PEOPLE (Tom St Denis)
Re: NSA and MS windows (Gordon Burditt)
Re: NSA and MS windows (David Wagner)
arguement against randomness (Tom St Denis)
Re: THINK PEOPLE (Tom St Denis)
----------------------------------------------------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: NSA and MS windows
Date: Sat, 4 Sep 1999 15:18:36 -0700
David Wagner wrote in message
<7qrtjq$old$[EMAIL PROTECTED]>...
>In article <7qqgs3$oan$[EMAIL PROTECTED]>,
>Roger Schlafly <[EMAIL PROTECTED]> wrote:
>> Maybe. Perhaps someone from the NSA suggested using a
>> backup key, and the MS programmers called it the NSA key.
>
>That is indeed what the MS techies are claiming. It's hard to
>verify with 100% certainty, but it's certainly not an implausible
>explanation.
Yes, it is plausible, but not terribly convincing either. Why did
MS need 2 keys? Is the concern that MS would lose one private
key? If so, why don't they make 2 copies, instead of using 2 keys?
Is the 2nd key really just a backup, or are there circumstances
in which only one of the keys is used?
I don't think MS is telling us the full story.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Alleged NSA backdoor in Windows CryptoAPI
Date: Sat, 4 Sep 1999 18:55:17 -0400
Stephan Eisvogel wrote in message
<[EMAIL PROTECTED]>...
>
>I say screw them. The story first showed up on John Young's
>Cryptome site http://jya.com this morning. Took me only ten
>minutes to patch the 'problem' on my NT4SP5 machine, now an
>"NSA sig" will be no good no matter what (I didn't use the
>published bloat-fix but patched the check and the key).
>
Dear Stephan,
Thanks for the post. Am not an implementation guy and forgive
me for this stupid request. MS does not provide source
and it is not 'easy' (certainly not not possible) to do what you did.
For soly personal interest, I would be very appreciative if you could
describe (in sketch) the way the binary (?) was tweaked.
You may e-mail me at [EMAIL PROTECTED]
I hope the description would not get you into any trouble. If you
have the slightest inkling of that kind of risk, please do not respond.
Thank you very much.
--- (My Signature)
------------------------------
Date: Sat, 04 Sep 1999 21:17:29 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: http://www.tmechan.freeserve.co.uk/wincrypt.html
Terry Mechan wrote:
> Wincrypt is practically unbreakable and now works on Win NT as well as 95/98
The fact that you think anything running on any version of Windows is
unbreakable leads me to disbelieve the second part of your announcement: I
suspect you probably got it to run at least once and now consider it ready to
ship.
Sorry if this offends you, but the bare statement, standing alone as it does,
looks pretty silly.
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Newbie needs help
Date: Sat, 04 Sep 1999 17:41:39 -0700
B3avis wrote:
> Hey there. I am rather new at encryption and decryption, but I can handle
> some programming (Delphi, Borland). I want to knwo some basics, like :
> how does the stream-thing work ?
> how can you make your own algorithms ?
> what things are good, what things aren't good ?
There's no substitute for study. Go to http://www.amazon.com and do a
search on "cryptography". Buy a few books and read. Be forewarned, it's
a lot of math and if your sole goal is to be "3133t3" then this isn't
the way to do it. But that's the way to learn cryptography.
There's an IEEE standards committee at
http://grouper.ieee.org/groups/1363/
Appendix A of the document for the proposed standard is a math appendix.
Mike Rosing has a good intro to the math in his book "Implementing
Elliptic Curve Cryptography",
most books on cryptography blithely assume that you know what
"relatively prime" is and how it differs from a "strong prime", but he
aims his book more at engineers who are actually trying to build things.
The GNU 'mp' ('multi-precision math') library is quite useful for
budding cryptographers, because public key cryptography consists of
doing math on huge numbers (1024 bits long or more in many cases,
hundreds of decimal digits), and most compiled computer languages will
not natively handle numbers that big.
There are various resources on the web, go to www.yahoo.com and
www.hotbot.com and type in "crypto" or "cryptography" as the key word.
http://www.privacy.nb.ca/ has links to the worldwide crypto archives.
See you in a few weeks after you've finished digesting a couple of books
(grin).
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
Date: Sat, 04 Sep 1999 21:42:07 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (DJohn37050) wrote:
> > OK, some here are some reworded questions on RSA key size for Bob, Wei and
> > anyone else to comment on:
> > 1. My understanding is that the GNFS has 2 steps: (A) Gathering equations,
> > which can be done in parallel with little memory
>
> As I said, 700 bits would require 2-3 Gbytes per machine to do the
> sieving.
>
> If you choose to call this 'little', might I ask your definition of
> 'big'?
>
> We have seen memory size expand by about a factor of 4 in the
> last 9 years. In 1990 a typical workstation had 32 meg, now it
> has 128 Meg (and a large one perhaps 256 M).
>
> In the next 9 years, we might expect a similar factor of 4 improvment,
> yielding machines in the 1Gbyte range as being typical. This is still
> too small to do the sieving for 700 bits.
>
> If you think my numbers are wrong, please give your own.
If you will be so kind, I'd like to pose followup questions regarding memory size.
The first concerns locality of access to the memory required in the two phases. If
there is any kind of locality it may be possible to utilize hierarchical store, with
appropriate granularity, to support the larger-than-average-workstation memory
demands. Is there any referential locality in eityher GNFS phase?
Another concept that might mitigate the requirement for main memory is a
hierarchical memory manager tuned for the access pattern of the application
(presuming it is deterministic). Is the GNFS "well behaved" enough to merit a tuned
memory manager?
------------------------------
Date: Sat, 04 Sep 1999 21:08:21 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: IDEA- safe?
jerome wrote:
> typo, replace 4.5months by 4.5years
>
> On 3 Sep 1999 19:03:28 GMT, jerome wrote:
> >
> >and these attacks can use the key even if they are different than
> >brute force...
> >
> >moreover if currently everybody says that 56bits is easy to reach, 64bits
> >is only 256 times more, so in 4.5months 64bits would be as easy as
> ^^^^^^^^^
> 4.5 years obviously
>
> >56bits now, according to the principle "the cpu power double every 18months"
Can we do simple math?
64 - 56 = 8
8 * 1.5 years = 12 years.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Sun, 05 Sep 1999 01:54:11 GMT
In article <[EMAIL PROTECTED]>,
Robert Harley <[EMAIL PROTECTED]> wrote:
>
> Bob Silverman <[EMAIL PROTECTED]> writes:
> > Everyone seems to always forget about scaling the space requirements
> > and solving the matrix.
>
> No, they remember that if solving the matrix is the limiting factor
> then they can do more sieving (with a smaller factor base) to
> compensate
No. They can't.
The response curve for optimizing the factor base size is fairly
shallow in the neighborhood of the optimum for QS.
For NFS, it is much steeper. Much. As you sieve over norm(a + b alpha) you
MUST make the most of the 'small' values of a,b, because the yield rate
drops dramatically as a,b increase.
For QS, all polynomials are the same in terms of yield.
As you sieve 'longer' the yield remains the same.
For NFS, as you sieve longer, the yield drops . A lot. You can't just
'sieve longer' because you will find that the yield rate gets very
low. 'More' sieving can very easily become 100 to 1000 times
more sieving. I have seen it. A while back I did some experiments
on a 130 digit number, [doing only about .005% of the sieving
needed to actually finish]. I ran the same number with different sized
factor bases. As the factor base size dropped below optimal, the
estimated total amount of sieving needed increased. Then suddenly,
it increased DRAMATICALLY to the point where I estimated that if
I dropped the factor base size by another 10%, that I would NEVER
get enough relations [within the life of the universe that is]. That
point was reached at about where the factor base being used was
a littles less than HALF of what I estimated was optimal. [about a factor
of 2.2 if I remember correctly].
And the size of the matrix is not solely determined by the size of the
factor base. It also depends very strongly on the size of the primes
one accepts in the large prime variation. [and how many large primes
one accepts].
, and if memory for sieving is the limiting factor then they
> can switch to one of the memory-friendly sieving algorithms that
> nobody uses much yet (because memory is plentiful).
We do that now. The sieve region is partitioned into pieces that
fit in cache. The problem is that as the modulus increases, so must
the factor base. Most of the memory requirements for sieving come
not from the sieve region, but from the two factor bases, the roots
of the polynomials modulo those primes, the sieve start and end points,
and saving the sieve start points so factoring may be done by resieving.
If you start paging this data, sieving slows to a crawl.
Have you implemented the algorithm? Your response shows
a superficial view of what is really required to make it work.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
Date: Sat, 04 Sep 1999 22:17:37 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Alleged NSA backdoor in Windows CryptoAPI
Bruce Schneier wrote:
> On 3 Sep 1999 19:08:16 GMT, [EMAIL PROTECTED] (Ian Goldberg) wrote:
>
> >In article <[EMAIL PROTECTED]>,
> >DJohn37050 <[EMAIL PROTECTED]> wrote:
> >>The obvious reason for an NSA key (assuming that is what it is) is to allow NSA
> >>to write their own CSP's without needing to get permission from Microsoft.
> >>That is, they can put in their algorithms without going to Microsoft for
> >>approval. But the CSP still needs to be put on the machine somehow and this is
> >>a voluntary act (as far as I know), so I do not see anything nefarious.
> >>Don Johnson
> >
> >And the NSA key would then be in *all* shipped copies of Windows
> >worldwide, why?
>
> My guess is that it is really a backup key, and that Microsoft gave
> NSA a copy of it for their own internal use (as Don suggests).
Why are we guessing? Is this issue not worthy of a credible explanation?
(I stated to say "official" explanation, but considering the likely sources nothing
official is likely to be credible).
>
>
> Bruce
> **********************************************************************
> Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
> 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
> Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: new user
Date: Sun, 05 Sep 1999 02:33:31 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi,
> Dominic Doyle, Melboure Australia, BA Psychology, interest in crypt but
> not expert.
> Has anybody heard the news on the recent crack of 512bit?
> Does any body know of good faqs or sites on 1012bit aside from the
> obvious RSA etc.
> Is Netscape still fighting the US government over the export of these
> technologies? I also read some time back that high level encryption was
> available from Germany and Japan making that action somewhat futile.
The U.S govt, has some backwards views on how to 'protect' the digital
information of it's citizens. Too bad this is the wrong group to be
discussing this.
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: IDEA- safe?
Date: Sun, 05 Sep 1999 02:31:00 GMT
In article <[EMAIL PROTECTED]>,
"Trevor Jackson, III" <[EMAIL PROTECTED]> wrote:
>
>
> jerome wrote:
>
> > typo, replace 4.5months by 4.5years
> >
> > On 3 Sep 1999 19:03:28 GMT, jerome wrote:
> > >
> > >and these attacks can use the key even if they are different than
> > >brute force...
> > >
> > >moreover if currently everybody says that 56bits is easy to reach, 64bits
> > >is only 256 times more, so in 4.5months 64bits would be as easy as
> > ^^^^^^^^^
> > 4.5 years obviously
> >
> > >56bits now, according to the principle "the cpu power double every 18months"
>
> Can we do simple math?
> 64 - 56 = 8
> 8 * 1.5 years = 12 years.
Wouldn't that be 2^(64-56) times harder? not 64-56 times harder?
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: criteria effecting the ability to factor?
Date: Sun, 05 Sep 1999 02:37:11 GMT
Can someone please clarify where these various points come into play in the
NFS and QS algorithms?
1) Memory size and Cache Size
2) What is the factor base?
3) What is the yield? (presumably the amount of usefull information found?)
One thing I haven't been able to find are extrapolations for time/memory
required to solve x-bit RSA keys (say a table)....
Any help? Any good stuff online? Any papers?
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: THINK PEOPLE
Date: Sun, 05 Sep 1999 02:47:15 GMT
In article <7qjjfm$1kkm$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> It really amazes me how little thinking gets done in this group.
> It is if there is a bunch of grouppies waiting for the BS and David
> Wagner types to release some knowlede. Well it is not going
> to happen that is not in there agenda. I have an open question
> that I doubt if they have the honesty to anwser in a fair way.
> They talk about my crypto as that of a weak ametur but even
> when they announce it is dead and someone actually looks into
> it they are wrong.
>
> People here is an example that can not be done with the weak
> form of crypto these kinds of people and government wants you
> to use.
>
> Take a message several thousands of bytes long. Lets say
> you send this message to 3 people. You use the same encryption
> method for each person you also use the same key. But near
> the middle of the message you have information that is unique
> to each of the 3 people. Other than that the information and
> files used are the same. And the key used was the same.
> Lets suppose the enemy who every that could be. Gets
> the 2 of the mesage you sent to 2 of the people includeing
> all the source code the keys used and the the plain text
> and encrypted files. Lets say they raid the third house
> and due to a screw do not get a copy of the thrid message
> decrypted. But they get all but the last 100 bytes of the
> encrypted message. They have the KEY and they know
> what 90%+ of the message is.
>
> The question that Bruce and Dave will not honestly anwser is
> how safe is the information if coded with any of there AES methods
> or Blowfish or any other smelly fishy algorithm. Using only the
> approved 3-letter chaining methods.
>
> They will not anwser becasue they know the data is not safe by
> there methods. Beacasue they want you to use methods that
> are easy to break. If scott16u or scott19u is used your safe and
> it they had any honesy they would tell you.
>
> If I am wrong. Don't just scream and yell. SHow me. I have an
> open mind and will admit they errors of me ways. All you have
> to do is show me if you can.
Simple answer. It's called a salt. Second point, don't use the same key
with more then one person. (i.e random keys, or fixed unique private keys).
If all people in the group are to have the same key to share info, and an
attacker found two messages, they will not be able to discern the third cause
of the salt.
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: THINK PEOPLE
Date: Sun, 05 Sep 1999 02:51:27 GMT
In article <7qpf08$12hg$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> In article <7qpaec$lem$[EMAIL PROTECTED]>, David A Molnar
><[EMAIL PROTECTED]> wrote:
> >Frank Gifford <[EMAIL PROTECTED]> wrote:
> >
> >> If you don't have the final 100 bytes of the target encrypted message, how
> >> do you know that they are identical to the last 100 bytes of some other
> >> message?
> >
> >David Scott's scenario was three messages for three people, with the only
> >differences being in the middle, and the plaintext for two of the messages
> >known.
> >
> >-David
>
> And the same encryption key and program used for all three files.
> Two of the encrypted files where obtain in tact ( well since you have the key
> who cares) but the third encrypted file for which the plaintext is missing but
> is known to be the same except for a small portion in the middle has a 100
> bytes missing from the end.
> The point is if you use any of the AES methods with the 3-letter blessed NSA
> chaining methods. Which have passed the high standards of the NSA so they
> must be good. You can recover the missing portion of the text. Not so with
> a program like mine. Becasue I don't use the offical blessed chaining methods
> since I feel the term "error recovery" is a PR term for Back Door. But these
> are my feeling only. Go ahead and follow the crytpo gods and continue to
> worship at the altar of Bill Gates.
With a proper salt method, even if you find 2/3 of the session keys you will
not find the 3rd, and thus not the 3rd message.
Even still the other 2 users would have to reveal their secret key to get the
3rd message, and even then your magical crypto-crap will not stand up.
moral: Use a salt for EVERY message so that the same session key is not used.
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Gordon Burditt)
Subject: Re: NSA and MS windows
Date: 5 Sep 1999 03:01:11 GMT
>Microsoft has two keys, a primary and a spare. The Crypto-Gram
>article talked about attacks based on the fact that a crypto suite is
>considered signed if it is signed by EITHER key, and that there is no
>mechanism for transitioning from the primary key to the backup. It's
>stupid cryptography, but the sort of thing you'd expect out of
>Microsoft.
>
>Suddenly there's a flurry of press activity because someone notices
>that the second key is called "NSAKEY" in the code. Ah ha! The NSA
>can sign crypto suites. They can use this ability to drop a Trojaned
>crypto suite into your computers. Or so the conspiracy theory goes.
Convince me that the "NSAKEY" doesn't have at least one use
that has absolutely nothing with signed crypto modules.
How do we know that the session key for every message isn't
encrypted with the NSAKEY and included with every message - this
makes ALL traffic readable by NSA. This feature might be
remotely controllable so that extra encrypted session key isn't
so easily noticed, and they can only read traffic for which the
feature has been turned on. Another possibility is to encrypt
the session key and the encrypted message checksum with the NSA key,
then send it over the Internet (if possible) to the NSA.
I don't know a lot about the details of the Crypto API: is it
possible that code in the API itself could leak the session
key to the NSA *independent of the type of encryption implemented
by a module*?
Gordon L. Burditt
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NSA and MS windows
Date: 4 Sep 1999 18:55:02 -0700
In article <7qs5q0$[EMAIL PROTECTED]>,
Roger Schlafly <[EMAIL PROTECTED]> wrote:
> I don't think MS is telling us the full story.
They may not be, but regardless, it doesn't excuse claims that the
"_NSAKEY" lets the NSA spy on every Windows box around the world.
I haven't seen a single shred of evidence for claims like that.
(I realize you're not making those types of claims. I guess I'm just
disappointed with a lot of the reporting on this issue.)
If MS or the NSA have committed some sin here, so far it appears to
be at worst a minor one.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: arguement against randomness
Date: Sun, 05 Sep 1999 03:02:25 GMT
(pardon my ignorance....)
Isn't one of the laws of thermaldynamics stating the spontaneuous creation of
energy is impossible (or something to that effect)?
Also wouldn't something truly random fall into this category?
If I am dead wrong, please let me know.
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: THINK PEOPLE
Date: Sun, 05 Sep 1999 03:04:52 GMT
In article <7qjjfm$1kkm$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote: 1)
CtXMYZMJdmiiaaaaWKg3HSizgIR{fNVonEW9r3BrtfCPU7toVVE2kQBuCNlaaaaaaaaaaaaaaaaaa
aaaaaaaaaaa
2)
DtXMYZMJdmiiaaaa6mTZ3hQkNLkuyhHzIGXPM7FJf67Uf2Gq}HGemcYt1rfaaaaaaaaaaaaaaaaaa
aaaaaaaaaaa
3)
EtXMYZMJdmiiaaaa9zC6tmFSrhAb8tkY9FYNt{8v}h{AKT1BB3bRsKBm1bbaaaaaaaaaaaaaaaaaa
aaaaaaaaaaa
(ignore the 'a's my padding algorithm is a bit slouched). Tell me what these
three messages have in common? What is their content?
(hint: I used PB, twofish and a 3 letter password (lowercase))
(hint: this is to show off what a SALT can do)
Tom
--
damn windows... new PGP key!!!
http://people.goplay.com/tomstdenis/key.pgp
(this time I have a backup of the secret key)
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
** 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
******************************
