Cryptography-Digest Digest #174, Volume #10 Sat, 4 Sep 99 09:13:04 EDT
Contents:
Re: Description of SQ ("Kostadin Bajalcaliev")
Re: Cracked ? (JPeschel)
Re: Schneier/Publsied Algorithms (SCOTT19U.ZIP_GUY)
Random bits on a PC (Bartosz Zoltak)
Re: NSA and MS windows (SCOTT19U.ZIP_GUY)
Re: http://www.tmechan.freeserve.co.uk/wincrypt.html (JPeschel)
Re: 512 bit number factored (Paul Crowley)
Re: Alleged NSA backdoor in Windows CryptoAPI (Stephan Eisvogel)
Re: Random bits on a PC (Tom St Denis)
Re: 512 bit number factored ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "Kostadin Bajalcaliev" <[EMAIL PROTECTED]>
Subject: Re: Description of SQ
Date: Sat, 4 Sep 1999 11:32:45 +0200
David Wagner wrote in message
<7qpebd$no2$[EMAIL PROTECTED]>...
>In article <7qp20o$[EMAIL PROTECTED]>,
>Kostadin Bajalcaliev <[EMAIL PROTECTED]> wrote:
>> /* initialization */
>> for j=0 to 2^w { P[j]=j; V[j]=0; }
>> For j=0 to 2^w { V[j]=K[r]; r=(r+1) mod L; }
>> For j=0 to 2*2^w SQ1();
>>
>>
>> /* generator iteration */
>> {1} A=P[Sr]; B=P[V[A]];
>> {2} V[A]=B; Swap P[A], P[B]; P<<<1;
>> {3} Out=P[A+B mod 2w];
>> {4} Sr<<<1; Sr=Sr+Out;
>> Return Out
>
>Interesting. (A much clearer presentation of the algorithm. Thanks.)
>
>
>Here's an observation on the basic structure. Consider what happens
>if you add an _extra_ P[] lookup to step {1}. One might imagine that
>adding more lookups can only increase security, but actually it can
>weaken the cipher, which might be a surprise. Consider replacing {1} by
> {1'} A=P[Sr]; B=P[V[P[A]]];
>Then the modified cipher becomes insecure, for some keys.
>
Just read the thesis, this situation is explained, no more that 2 recurzive
look-ups P[P[x]]
>Consider: After the first step of initialization, we have
> lsb(P[j]) = lsb(j) for all j,
>where lsb(x) = x mod 2 stands for the least significant bit of x.
>Suppose a similar condition holds for V (which is a L-bit condition on
>the 8L-bit key). Then at the first SQ1() iteration, we have
> lsb(A) = lsb(P[Sr]) = lsb(Sr)
> lsb(B) = lsb(P[V[P[A]]]) = lsb(V[P[A]]) = lsb(P[A]) = lsb(A) = lsb(Sr)
>and thus the first half of step {2} (`V[A]=B; Swap P[A], P[B];') doesn't
>disturb the lsb-properties of V or P. The rotation `P<<<1' changes the
>lsb-property on P[] to a new one, namely lsb(P[j]) = 1-lsb(j) for all j.
>
>Now look at the second iteration. After step {1'}, we have
> lsb(A) = lsb(P[Sr]) = 1-lsb(Sr)
> lsb(B) = lsb(P[V[P[A]]]) = 1-lsb(V[P[A]]) = 1-lsb(P[A]) = lsb(A) =
1-lsb(Sr)
>Again, the first half of step {2} (`V[A]=B; Swap P[A], P[B];') doesn't
>disturb the lsb-properties of V or P. Finally, the rotation `P<<<1'
>returns the lsb-property on P[] to lsb(P[j]) = lsb(j) for all j.
>
>After two cycles, we're back to where we started (in terms of the
>lsb-properties of V[] and P[]). By induction, after any even number of
>cycles, the lsb-properties for V[] and P[] will always hold, if your
>key is of the special form mentioned above. In this case, lsb(Out) will
>form the sequence 0,1,0,1,0,1,0,1, and thus this situation is readily
>detectable.
>
>In other words, 1/2^L of the L-byte keys are very weak for this
>modification of the cipher. Does the "Information Lose" theory predict
this?
You have analyzed a situation with a lot of assumptions, ok it is a real one
(that kind of lsb property of V and P can happened. But you have missed two
things. P rotates but V does not. So in the second iteration they are going
to be in opposite position lsb(P[i])=1-lsb(V[i]); So the swap will change
the lsb property of P because P[A] will retain lsb property but not
P[V[P[a]]]; And the second thing that is part of the algorithm is Sr<<<1. If
your case happened than there is no chance all the bits to be threaten is
this way, so Sr<<<1 will practically save the situation, msb of Sr became
lsb for the next iteration, and if msb is secure bit the whole sequence is
safe. This two thing you have missed guarantee the SQ "good" behavior in
this special case. If you find such a state of SQ from which it will start
to produce 0,1,0,1,0,1 sequence please inform me.
My advice to you is: Do not look on cryptography so formally it is one of
the most humanistic sciences, try to found analogies in the real live for a
given algorithm or theory in order to understand them. Shannon theories are
just theories nothing else, you can not prove that a given theory is false
because there exist other theory that claim the opposite. May be
"Information Lose" is not the best name but try to be little bit
philosophical in place of mathematical, every process in the universe, every
emission of energy or movement create information about its existence, but
into the process of matter-energy transformation imagine the information as
the third component and mediator. The information can be both a material and
energetic form of existence. But in every process very little of the thing
goes to free information most of it became energy or materia. And this is
the "Information Lose". To fully describe a given process where N changes
has occur you need at least N-bit of information, but until the process ends
we can not extract the information so on the end we are unable to have the
whole information produced by the process. So the SQ is a simulation of such
a case, you can not stop the generator and look the intermediate variables,
only the final result is available to you. And the algorithms is designed in
such a way that the output to be something as hash of the inner state.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Cracked ?
Date: 04 Sep 1999 10:09:53 GMT
[EMAIL PROTECTED] writes:
>Where can the information be found as to how (scientifically) these were
>cracked?
See the address in my signature.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Schneier/Publsied Algorithms
Date: Sat, 04 Sep 1999 10:57:54 GMT
In article <[EMAIL PROTECTED]>, Eric
Lee Green <[EMAIL PROTECTED]> wrote:
>"SCOTT19U.ZIP_GUY" wrote:
>> I don't think it is that mature yet. Yes will have computers and we can
>> measure things for certain forms of attack. But we aren't there yet. I still
>> think it is foolish to use short keys and any block less than the largest
>> possible.
>
>Well, in my case I am not encrypting top secret data, I am encrypting
>data sent over a public network, in real time if possible. Thus using a
>key longer than 128 bits just won't do it with today's computers, which
>just aren't fast enough. Even with 128 bit Blowfish, a fairly fast
>algorithm, I can see a significant performance drop over just doing,
>e.g., a plain FTP transfer. In fact, on my machine (a K6/2-333), I can
>do an FTP transfer basically as fast as my hard drive will go, but using
>Blowfish with 'ssh' gets me down to around 400K per second.
>
>I agree that for sensitive data you should encrypt it with the longest
>key and largest block size that are computationally feasible, even if no
>known attack will be able to break it within a reasonable amount of
>time. It's just that the definition of "computationally feasible"
>depends upon your application. CPU power is limited. In addition, you
>should be careful to use an efficient algorithm for time-critical
>operations. For example, Triple DES is a pig, use RC5 or Blowfish or any
>of the AES finalists (the finalists appear to be the fastest of the
>submitted algorithms, which makes sense if you assume that, in a mature
>field like block ciphers, all of the algorithms had similar
>cryptographic strength). My understanding is that the typical criticism
>of your program is that it's rather slow for the amount of cryptographic
>strength provided.
And naturally you belive that with out even trying it. People have
compared the speed of scott16u to blowfish and it was not that slow.
The real time hog is the actual seting up of the S-box. But that can
be done independent of the actaul encryption.
>
>> Most people think I am kidding but when it comes to AES don't any of
>> the so called creditable crypto people think that it is just a front for
>> the NSA or are they all so caught up in the excitement they stop
>> thinking.
>
>The problem is that, as I've browsed the web looking for crypto sites,
>I've found a lot of people who have looked at the AES candidates, people
>who have done algorithms of their own or at least implemented the major
>algorithms and presumably know what they're doing. The finalists appear
>to be the ones that were fastest and easiest to implement (or in the
>case of Twofish, complex to implement but also rather flexible, one guy
>referred to it as an "engineer's cipher" because of the way it could be
>optimized differently for different applications). I've seen plenty of
>criticism of the AES contest, even some of the folks who've contributed
>candidates have said that AES should be a family of algorithms rather
>than a single algorithm, but few signs that the NSA has somehow
>"trojaned" the contest (unless RC6 is a trojan, but if RC6 is a trojan,
>then so is RC5, from which it apparently is derived, and as far as I can
>tell RC5 seems to be considered secure). The NSA's choices for finalists
>seem to be pretty close to what the public community predicted before
>the finalists were announced.
>
>In addition, at least two of the AES candidates are based on prior work,
>i.e. RC6 is basically a derivative of RC5, and Twofish is a derivative
>of Blowfish. Both RC5 and Blowfish have been hit on pretty hard, making
>it unlikely that their derivatives have a weakness that would allow
>anybody to crack them in significantly less time than is currently
>conjectured.
>
I think you greatly underestime the strength of the NSA decrpytion ability.
As well as there ability to make current research go in the wrong direction.
They use any and all means to prevent the world from having safe encryption
The microsoft thing is just the tip of the iceberg.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: Bartosz Zoltak <[EMAIL PROTECTED]>
Subject: Random bits on a PC
Date: Sat, 04 Sep 1999 10:01:16 GMT
All I've read here on the value of real entropy made me willing to try
to find a source of it inside a standard PC.
I admit it actually took a few sleepless nights to meke the program but
today it generates bits - basing on minimal unsynchronizations of chips
on the PC's mainboard.
And the generated bits are... That's right. It's more that I can ask
you about my bits than I can tell you.
The generated bits "seem" random to me and their arithmetical average
is close to 0.50.
However something tells me that it is not a great proof...
So please:
If you know any methods of testing the generated bits for
randomness (or - how much randomness is in them) - I would really
appreciate it.
Big thanks in advance!
Bartosz Zoltak
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: NSA and MS windows
Date: Sat, 04 Sep 1999 11:08:27 GMT
In article <[EMAIL PROTECTED]>, pbboy <[EMAIL PROTECTED]> wrote:
>NSA : "P-p-p-please sign this thingamajig, Mr. Gates. I'll do anything
>you want...I'll be your best friend...!"
>Gates: "HA! Lick my feet! Bow to me, the omnipotent Gates!"
>NSA: *Lick-lick-slobber-slobber* (wipes crusties from mouth, removes gum
>from forehead) (*sniffling*)"Now w-will you sign it?"
>Gates: "No! Do it again, just so you know who's boss!"
>
>I don't think so.
>
>
>Maybe I overestimate the NSA's power, but why would the NSA _ask_ MS for
>anything?!? This is a game, people! Why hack/crack/reverse-engineer
>anything? The NSA has soooo much influence, and even more power they don't
>need permission for anything like this. Here's the way I would obtain
>anything from anyone, including MS.
>
>Moles
>
>1) Recruit some young brilliant software engineer, one that even MS would
>fight for.
>2) Send him on a mission: Get recruited by MS (they hire by the bus-load,
>i hear)
>3) lay low for a while, gaining trust (read: security clearance) from the
>Company.
>4) Somehow get assigned to the "encryption and security" (hehe!) task
>force
>5) keep head quarters (NSA) informed about the direction the company is
>taking towards its security =) features
>6) Hand over the source and any other info pertaining to the mission.
>7) remain in MS as long as possible, divulging as many secrets and as much
>dirty laundry as possible (NSA just LOVES secrets!) Could lead to future
>extortion / blackmail / bribery of high ranking executives ect..
>8) Gain as high a position as possible in the Company to have a more
>direct influence over it and its future
>
>Espionage, corporate espionage. now that's fun!
>
>I don't doubt for one second the above scenerio, or a similar one, hasn't
>happend yet or is taking place as we type.
>
>OR
>
>Maybe I underestimate MS's power....
>
>
>
>--------
>
>pbboy
>
>
>HEHE! Do you really think, IF the NSA were to use any MS products, they
>would actually pay for the licenses? Do ya think the NSA has a software/OS
>engineering department of their own?
>
What you file to realize is that the NSA would use all means to corrupt the
MS sytem for there uses. So your right in assuming that the NSA has moles
in MS it only makes sense. But that does not mean another department of the
NSA also is buddy buddy with Gates and they team up to put back doors.
Ms is closed source and problably full of holes. As Gates once said no one
needs more than 650K. While then why is his stuff so complex.
Don't forget in the US government the same time we give add to crooked
countries around the world proping them up. We may be paying more money
through the CIA to take them down. Its the American way.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: http://www.tmechan.freeserve.co.uk/wincrypt.html
Date: 04 Sep 1999 10:21:26 GMT
"Terry Mechan" <[EMAIL PROTECTED]> writes:
>Wincrypt is practically unbreakable and now works on Win NT as well as 95/98
>
>Download from
>
>http://www.tmechan.freeserve.co.uk/wincrypt.html
Terry, I've no idea if your product is any good, but you might
want to consider changing its name. Wincrypt is the name
of an old PC Magazine utility for which there is a cracker.
Guess where. :-)
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: 4 Sep 1999 10:04:43 +0100
Bob Silverman <[EMAIL PROTECTED]> writes:
> 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).
I think your 1990 workstation was very much more expensive than your
current one. During my year out in 1992 I worked for a City database
software firm and sat at the biggest machine I had ever used: a Sparc
ELC with a whole *eight megabytes* of memory. The Lisp hacker across
the room had even more: 24 Mb, which at the time seemed to me an
implausibly huge amount. I'd say a better guide would be the progress
of the $1500 PC, and I'd guess those machines have gone from 4Mb to
256Mb since 1989, just a little behind the Moore's Law prediction of a
100x increase.
However, memory access times have not improved commensurately. If
these are the bound on the running time of the sieving, it may not get
much faster over the next ten years.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: Stephan Eisvogel <[EMAIL PROTECTED]>
Subject: Re: Alleged NSA backdoor in Windows CryptoAPI
Date: Sat, 04 Sep 1999 13:45:14 +0200
Bill Unruh wrote:
> The problem is the
> bunch of stuff that has not been discovered yet. Where else has MS
> hidden deliberate security holes in their system?
Hrm. Microsoft depends on the reputation of NT's security to reach
a broader customer base. If they'd get caught deliberately planting
weaknesses into their system, I doubt that they would sell as many
copies as they do now. They are sloppy sometimes when it comes to
implementing things, PPTP and TCP/IP comes to mind, that's for sure.
Most serious security holes are fixed after a couple of days or
weeks, which is a different thing than releasing a weak IE w/ 40-bit
because of export regulations.
Since I know about MS's track-record when it comes to security, I
rely on 3rd party add-ons or my own kernel modules, especially for
disk encryption. It's just TOO EASY to make EFS use a fscked-up
CryptGenKey or CryptDeriveKey. In that NTFS v5 mess, you couldn't
tell the difference!
--se
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Random bits on a PC
Date: Sat, 04 Sep 1999 11:58:20 GMT
In article <7qqql9$voi$[EMAIL PROTECTED]>,
Bartosz Zoltak <[EMAIL PROTECTED]> wrote:
> All I've read here on the value of real entropy made me willing to try
> to find a source of it inside a standard PC.
>
> I admit it actually took a few sleepless nights to meke the program but
> today it generates bits - basing on minimal unsynchronizations of chips
> on the PC's mainboard.
>
> And the generated bits are... That's right. It's more that I can ask
> you about my bits than I can tell you.
>
> The generated bits "seem" random to me and their arithmetical average
> is close to 0.50.
> However something tells me that it is not a great proof...
>
> So please:
>
> If you know any methods of testing the generated bits for
> randomness (or - how much randomness is in them) - I would really
> appreciate it.
>
> Big thanks in advance!
Well generally if you can't find a correlation between the input data, and
the output bits, and they are statistically sound, it's good enough for
random.
Like Yarrow for example takes a lot of data and squeezes out a few bits which
without complete knowledge of all the inputs and the current state you can't
reproduce...
Other sources: audio input (take lots of it, and hash it!), timings (free
running counter) between keystrokes...
Tom
--
PGP 6.5.1 Key
http://mypage.goplay.com/tomstdenis/key.pgp
PGP 2.6.2 Key
http://mypage.goplay.com/tomstdenis/key_rsa.pgp
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 512 bit number factored
Date: 4 Sep 1999 08:50:23 -0400
In article <7qqab8$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Paul Rubin)
writes:
>In article <7qpp6k$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>> A disappointment here. Perhaps Mr. Rubin has forgotten that the
>> last time he posted on this topic he was replying (supposedly) to
>> my note clarifying the source 95% estimate?
>
>Yes, I don't remember what this was about.
Ah. Then I was overly oblique; sorry. Our report on the
factorization of RSA140 has a reference to Shamir's paper.
(And, to anyone interested, the report in question is not
available online; is not yet in print; and when it does
appear in the AsiaCrypt proceedings in November, the copywrite
will belong to Springer-Verlag. "Want to know the rest? Buy the
rights.")
Without getting into "telling tales out of school", the initially
proposed CWI press release went through a somewhat heated revision.
While I was not present when the final decisions were made, the only
statement about the use of 512-bit rsa in commerce that was retained
was Shamir's 95% estimate, which I'm fairly certain we regarded as
having been widely_circulated and well_known from the TWINKLE paper.
While some readers of SCI.CRYPT will have forgotten the widespread
speculation about Shamir's new "factoring discovery" last April, and
the likelyhood that TWINKLE could be used to factor 512-bit numbers,
those of us that were working on factoring RSA155 since February (when,
ahem, the number field used was found here at Lehigh) will be likely to
remember fairly well for some time. Especially since we did not expect
to finish until September.
B. Dodson
------------------------------
** 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
******************************
