Cryptography-Digest Digest #311, Volume #10 Fri, 24 Sep 99 17:13:04 EDT
Contents:
Re: frequency of prime numbers? ("Trevor Jackson, III")
Re: RSA weak? (Tim Tyler)
Re: EAR Relaxed? Really? (Greg)
Re: msg for Dave Scott ([EMAIL PROTECTED])
Re: EAR Relaxed? Really? ("Trevor Jackson, III")
Re: Increasing password security dramatically without making it harder to (Tom St
Denis)
Re: Relating cyrptology to factoring? ("karl malbrain")
Proving cipher strength (Toby Kelsey)
Re: Second "_NSAKey" (Greg)
Re: low diffie-hellman exponent (Tom St Denis)
Re: DES source code? (Tom St Denis)
Re: Second "_NSAKey" ("A [Temporary] Dog")
Re: some information theory (very long plus 72K attchmt) (Tom St Denis)
Re: Random and pseudo-random numbers ([EMAIL PROTECTED])
----------------------------------------------------------------------------
Date: Fri, 24 Sep 1999 15:18:06 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Douglas A. Gwyn wrote:
> "Trevor Jackson, III" wrote:
> > Sure they can. In this context "proved" does not mean "show to be true" it means
> > "truth value resolved", which applies to both possible truth values.
>
> No wonder I didn't understand what you were saying.
> You should have used the standard term "decidability";
> "proof" means a valid derivation.
OIC. You thought "unprovable false statement" meant "unprovable true statement"? Now
I see where the confusion lies.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: RSA weak?
Reply-To: [EMAIL PROTECTED]
Date: Fri, 24 Sep 1999 18:29:47 GMT
Kem <[EMAIL PROTECTED]> wrote:
: OK, I am convinced, now, other question. is it possible to decompose n in
: more that two factor? maybe decimals? Example n=3*7=21; n=6*3'5=21
3 x 2 x 3.5 does equal 21 - a number that has only two prime factors -
but this helps not one jot with locating the prime factors of a large
number with two large prime factors - which is what you need to do
to decrypt.
Decomposing N = p x q, where p and q are prime into more than two
positive integer factors is, of course, impossible.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
It is not enough to succeed - others must fail.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: EAR Relaxed? Really?
Date: Fri, 24 Sep 1999 18:40:23 GMT
> If it sounds impossible to be so, you do are unaware
> of the real bastards that deal is such corrupt practices.
The phrase is "in denial". Many people are in denial because
if they confronted the issues they would not know how to
conduct themselves in our society.
> Note the latest ad from Apple reflecting the government's
> philosophy that good computers should not be exported. It is
> interests of our government foreign computers be vulnerable.
Where can I see this at? Is it on the web?
--
Truth is first ridiculed, then violently opposed, and then it is
accepted as self evident ("obvious").
I love my president... I love my president... I love my president...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: msg for Dave Scott
Date: Fri, 24 Sep 1999 19:32:55 GMT
In article <7se7no$2cdi$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Johnny Bravo) wrote:
> >On Thu, 23 Sep 1999 12:51:20 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY)
> >wrote:
> >
> >> I have looked at the 3-letter chaining modes and so they are weak
> >>becasue all they are all "error recoveryabel" So that an ememy needs
> >>to only have a small sample of the code to see if a KEY works. This
> >>is not possibel in an "all or nothing cipher" like scott16u. But
then
> >>again you may not have understood the simple tests to see this.
> >
> > Even if you could check each one of these keys by checking a single
byte,
> >it doesn't change the simple fact that a 256 bit symmetric key will
need an
> >average of 5.789e76 tests to break that key.
> >
> > Even if these so called "weak" systems made it a trillion times
easier to
> >brute force than a cipher didn't have error recovery. You could get
a billion,
> >billion computers that can try a billion, billion keys each and every
second
> > and
> >it would still take 18 billion, billion, billion years to check the
1/2 of the
> >keyspace that it would take to give you a 50/50 chance of cracking
that one
> > key.
> >
> >
> > But then again you may not have understood the simple math it takes
to see
> >this.
> Yes John I understand this. But I doubt if you do becasue you may
be
> under the illusion enigma is still safe. All your doing is saying it
is safe
> do to a dumb blind search as if a blind search means everything. It
doesn't
> but you can't seen to understand that.
David, how doesn't it? How is it unsafe?
Marc
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Fri, 24 Sep 1999 15:25:05 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: EAR Relaxed? Really?
Jim Gillogly wrote:
> "Douglas A. Gwyn" wrote:
> > The interesting question is whether the "technical review"
> > will be allowed to end with the product failing to be approved
> > (presumably because it is too secure, although that might not
> > be the officially stated reason).
>
> Why else would there be a requirement for a technical review?
> On what other grounds would a product fail to be approved?
Tough question.
These days it's hard to believe the stated grounds are the actual grounds
for government policy (c.f., IBD lead article today) even when the agency
involved is both supposed and believed to be above board. In dealing
with the dark agencies one has to assume hidden agendas as a matter of
course, so assuming correlation between the stated and actual grounds may
be a mistake.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp
Subject: Re: Increasing password security dramatically without making it harder to
Date: Fri, 24 Sep 1999 19:46:07 GMT
In article <7sfome$2p8u$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] () wrote:
> >Thomas J. Boschloo ([EMAIL PROTECTED]) wrote:
> >: Instead of hashing the whole pass phrase, you hash the pass phrase with
> >: some random data appended. I think I'll patent it! It's a great idea and
> >: it is funny nobody thought of it before.
> >
> >Surely you jest. This is called "salt", and was used in Unix password
> >files.
>
> Actually I don't think this alone would prevent one from patenting the idea
> many things that are in the public domain get patented over and over again
> becasue patent lawyers and the system are only in place to suck money.
> What you really mean is it may be dumb to patent this idea. Because
> when it comes time to inforceing it in a court of law. If the person being
> attacked has a "good lawyer" than at that time the suit may be throuwn out
> and the patent determined to be weak.
>
Hehehe no it can't be used because it was used in UNIX over 15 years ago
thats why. Even if the idea did have a patent it would have expired.
Dude the only way any 'system' (refering to government) is going to work is
if the people make it work. I.e the hospitals wouldn't work if you threw
your OHIP (or insurance card) out every 3 days, and came in and stole
equipment and asked for help cuz you have a scrape on your knee and protested
and made picket lines .... etc... We make (for example) hospitals work by
co-operating. We do first aid at home, we pay bills etc... Have faith man.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Reply-To: "karl malbrain" <[EMAIL PROTECTED]>
From: "karl malbrain" <[EMAIL PROTECTED]>
Subject: Re: Relating cyrptology to factoring?
Date: Fri, 24 Sep 1999 11:06:40 -0700
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Jeffrey ([EMAIL PROTECTED]) wrote:
> : I can not find any depth of
> : information on how factoring numbers can break codes.
> : What algorithms of encryption are effected by factoring? DES? RC5?
> : And where can I find a more in-depth explanation of how factoring and
> : the algorithms blend, what steps of the algorithms?
>
> No, algorithms like DES, RC5, IDEA, or Blowfish can't be broken by
> factoring.
ABSTRACT TENSOR FIELD THEORY onto LINEAR ALGEBRA as an order to begin
FACTORING (don't DIFFERENTIATE your statement above without first contacting
an expert.) Karl M
------------------------------
From: Toby Kelsey <[EMAIL PROTECTED]>
Subject: Proving cipher strength
Date: Fri, 24 Sep 1999 19:43:38 +0100
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes
>A cipher is not proven strong by surviving cryptanalysis. Such survival is
>merely weak corroborating evidence of strength, which is the best thing we
>have.
I wonder if the usual assumption that cipher strength can only be
disproven, and not proven, is actually valid. Suppose we try a
mathematical approach:
(a) Choose a model for computation (e.g. a Turing machine) with
weights for each operation representing time/effort.
(b) Select our trial cipher, which can take variable-length keys.
(c) Show, using an exhaustive search of possible faster programs,
that for a trivial key-length (e.g. 8 bits), brute-force search of
the key-space is the most efficient method of breaking the cipher.
(d) Prove by induction that brute-force is the most efficient method
for all key lengths (for specified message lengths).
The details of the critical step (d) will depend on the structure of
the cipher, and it may be possible to design one which makes proving
this easier (which, say, operates sequentially on the key bits).
The induction step would require showing that a program which can beat
brute-force for a certain key-length can be used to beat it at a shorter
length. This might seem impossible since the program may be specific to
that length key, but one way around that is if several encryptions with
short keys can be combined to make an encryption with a longer key.
It is likely that the proof will only work for one cryptanalysis mode
(i.e. ciphertext only), but even that would be significant.
Has anything like this been attempted?
Toby
--
Toby Kelsey
------------------------------
From: Greg <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Second "_NSAKey"
Date: Fri, 24 Sep 1999 19:33:14 GMT
> > Be my guest. Show me why the conspiracy theory to give
> > NSA a key CANNOT be correct. That is what I mean by refute.
> > Show that it CANNOT be correct.
>
> This is in the same category as:
>
> "Show that Santa Claus does NOT exist."
>
> It can't be refuted. ever. Let's move on, shall we?
Let's put things into perspective- Santa is too busy making
toys that he aint a threat to my privacy.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: low diffie-hellman exponent
Date: Fri, 24 Sep 1999 19:37:52 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> These are all estimates to number of operations needed. See my paper at
> www.certicom.com at PKS'99 on ECC, Future Resiliency and High Security Systems
> which discusses this some. Also, Bob Silverman had a paper on "Mythical MIPS
> Years" in a recent Computer.
>
> Some things to remember:
> 1) counting OPS is a best-guess estimate.
> 2) just counting OPS ignores storage and other factors like inability to
> parallelize
Thanks for the info. Just as long as it's an educated reasonning to say
'solving 2048-bit discrete logarithms' is hard is good enough for me.
First off the algorithm for solving here is the generalized NFS right? Where
can I find info on it? (Or should I read up on the NFS first?). Second how
much time does an 'OPS' take? Is that like a multiplication-square? or what?
(lets say on a good x86 machine)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: DES source code?
Date: Fri, 24 Sep 1999 20:04:25 GMT
In article <[EMAIL PROTECTED]>,
Jesper Gadeberg Jensen <[EMAIL PROTECTED]> wrote:
> Does anybody know were I can find the C source code for DES?? I was told
> that an Australian named Eric Young, was suppose to have it but I
> haven't been able to find it! Can anyone help?
Again (hehe) I ask why DES? Is this a legacy application or something new?
If it's new get with the times and use something else. Below is the complete
source you need to setup/use RC4.
Tom
---
/* RC4 in C */
typedef struct rc4_key {
unsigned char state[256];
int x, y;
};
/* setup an RC4 key */
void rc4_setup(unsigned char *key, int len, rc4_key *k)
{
unsigned char *s, tmp;
int i, x, y;
/* make the state a permutation */
s = k->state;
for (i = 0; i < 256; i++)
s[i] = (unsigned char)i;
/* shuffle the permutation */
for (i = x = y = 0; i < 256; i++) {
y = (y + s[i] + key[i % len]) & 255;
tmp = s[x]; s[x] = s[y]; s[y] = tmp;
x = (x + 1) & 255;
}
/* drop the first 1024 bytes to avoid weak keys */
for (x = y = i = 0; i < 1024; i++) {
x = (x + 1) & 255;
y = (y + s[x]) & 255;
tmp = s[x]; s[x] = s[y]; s[y] = tmp;
}
/* clear stack */
k->x = x; k->y = y;
x = y = tmp = 0;
}
/* encrypt/decrypt a block */
void rc4(unsigned char *block, int len, rc4_key *k)
{
int x, y;
unsigned char tmp, *s;
/* load indexes */
x = k->x; y = k->y; s = k->state;
while (len--) {
x = (x + 1) & 255;
y = (y + s[x]) & 255;
tmp = s[x]; s[x] = s[y]; s[y] = tmp;
*block++ ^= s[(s[x] + s[y]) & 255];
}
/* restore */
k->x = x; k->y = y;
x = y = tmp = 0;
}
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "A [Temporary] Dog" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Second "_NSAKey"
Date: Fri, 24 Sep 1999 16:51:27 -0400
On Fri, 24 Sep 1999 19:33:14 GMT, Greg <[EMAIL PROTECTED]> wrote:
>
>> > Be my guest. Show me why the conspiracy theory to give
>> > NSA a key CANNOT be correct. That is what I mean by refute.
>> > Show that it CANNOT be correct.
>>
>> This is in the same category as:
>>
>> "Show that Santa Claus does NOT exist."
>>
>> It can't be refuted. ever. Let's move on, shall we?
>
>Let's put things into perspective- Santa is too busy making
>toys that he aint a threat to my privacy.
>
How wrong you are. He knows when you are sleeping. He knows when
you're awake. He knows if you've been bad or good. He also keeps
lists. Santa is a grave threat to both privacy and individual liberty.
- A (Temporary) Dog |"Intelligent, reasonable
The Domain is *erols dot com* |people understand that -
The Name is tempdog |unfortunately, we're dealing
|with elected officials"
Put together as name@domain | - name withheld
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: some information theory (very long plus 72K attchmt)
Date: Fri, 24 Sep 1999 19:55:44 GMT
In article <7sfq1e$35b4$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> >Tom St Denis wrote:
> >> Compression is not to enhance the security of a system, I don't even use it
> >> in peekboo and you can't break it or even suggest a possible break.
> >> Compression is used to cut transmission times. Think of it. If your modem
> >> was a 1tbps connection and you had a 50tb hd would you are to compress
> >> anything?
> >
> >Precompression *does* make cryptanalysis harder,
> >since it greatly complicates the mapping from the
> >source, which may have lots of known statistical
> >properties, to the interceptable message. For
> >example, ASCII source has every 8th bit 0, and
> >if it is an English-language document, there is
> >a statistical bias in the LSB, which could be
> >exploitable by certain cryptanalytic attacks.
> >After compression, such biases are no longer
> >present at the input to the encryptor, which
> >renders moot that encryptor vulnerability.
> I agree the goal of compression is to remove such known statistical
> properties from files so that decrption from an advisory is harder. The
> problem that I have encountered with the main stream compression
> programs. Is that the act of compression itself adds properites to the
> file that can be exploited by the attacker. Headers are only one of the
> structural features. You can compress random data and run the compressors
> which in the case of random data the file gets longer and the structure
> added to the compression aids the attacker in breaking the encryption.
> This is why I have taken a hard look at compression and how it
> should be used if the intent is to encrypt after using compression.
> I think it should be obvious that if a compressor/decompresor
> combination can map any file of 8-bit bytes to another file of 8-bit
> bytes in a unique way then that compression method does not add
> information that would help in decryption since any file resulting from
> a bad key would be decompressable in a unique way. That is why
> I call it "one-to-one" compression.
> So far at my site I only have adaptive huffman compression that meets
> this critteria. But I do want to explore aritmetic coding in this area. The
> problem is I keep thinking up extensions. Like a many file to one file
> compression that is one to one I will release this soon. Also found a
> cleaver way to do RLE with huffman coding that is one-to-one. The
> trick is to use more than one adaptive huffman coding tree and the
> use of internal tress of more than 256 symbols. The problem gets
> getting deeper and deeper. May main interest is still encryption
> but since that is basically illegal here I am getting deeper into
> compression however my wife a mexican citazen may explore
> encryption extensions on her on in Mexico. Also I may get
> a printer any give her prited material to input in computers
> in Mexcio and I talk in my sleep. I hope talking in ones
> sleep is still not illegal in our emerging police state.
Ok anyways.... uh... you can brute force a compressed/encrypted message. You
have to agree to this for this idea to work.
Let's call the decompression D, and decryption d, now you have todo this to
get a message P = D(dk(C)) instead of just P = dk(C) so what. No matter what
compression algorithm you use you can do this.
By your arguement deflate for example puts headers in the compressed data to
describe the input. The only thing there is maybe an ID, CRC32 and length.
And if you tell me 1.5 blocks is enough to mount a successfull iterative
attack you are friggin loony. I have NEVER seen any block cipher fall to a
mere 2 blocks. Deflate output (stream data) is highly efficient. It's as
random as the input of the message. It's not perfect but it works wonders.
So this means 'detecting' valid deflate blocks requires decompressing them
first, just like in your method.
I can sit for a while decrypting/decompressing blocks of scottu19 ciphertext
and find the message (albeit it might take a while).
Let's make a proposition here. If any function is one to one (i.e
invertible) it can be brute forced, because AT LEAST one valid solution must
be found (note for some ciphers you have to use a few blocks to correctly
(with a high prob) detect a valid key). So this means RC5, CAST, Blowfish
and even Scottu19 is vulnerable to this attack. Time now is simply a
function of the keyspace and time per trial, denotable as T = PQ / 2, where P
is the keyspace (power of 2, or whole num if the keyspace is non-flat) and Q
is the time per trial in seconds.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Random and pseudo-random numbers
Date: Fri, 24 Sep 1999 20:04:46 GMT
In article
<[EMAIL PROTECTED]>,
Eric Lee Green <[EMAIL PROTECTED]> wrote:
>
> My problem is under Solaris, HP/UX, AIX, etc., where I don't have easy
> access to the innards. Windows, FreeBSD, and Linux are not a problem
> (Windows because Yarrow has uncovered various sources of entropy,
> Linux/FreeBSD because they have a /dev/random device that already is
> fairly strong). Setting up an entropy daemon may be a possibility (and
> it is something I have considered doing), but conflicts with other
parts
> of the project specifications and thus is something I want to avoid.
>
> I have found more than 24 random bits under Solaris etc., but not many
> more. Just enough to build a single unpredictable 128-bit value (that
> is, it should have 2^128 possible initial states). But I need a lot
> more, thus my interest in using this to seed a PRNG. (And even under
> Linux/FreeBSD, /dev/random doesn't accumulate entropy as fast as I'd
> need to generate dozens of 1024-bit numbers).
>
(I hope a late reply to this query is still helpful.)
It might be useful to port the Yarrow PRNG to Solaris or the other
operating systems, by developing some routines for each OS that burrow
into the OS's internals. I think this should be a relatively easy thing
to do for Solaris; I don't know about the other OSes you mentioned.
The Solaris kstat interface (see man kstat) lets you burrow into all
sorts of interesting places. The gethrtime system call also gives you
access to a 64-bit nanosecond-resolution clock. This information could
be fed into Yarrow to provide the initial entropy. I believe this is
basically the same approach that Peter Gutmann describes in "Software
Generation of Practically Strong," except that kstat provides a
relatively efficient way to random data to feed to the PRNG.
I would be interested in using a Yarrow-based PRNG on Solaris, so I
would be very happy if you decided to implement one. ;-)
Jeremy
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
