Cryptography-Digest Digest #308, Volume #10 Fri, 24 Sep 99 10:13:07 EDT
Contents:
Re: RSA 640 bits keys factored, French banking smart card system craked! ("Dmitriy
Morozov")
Re: msg for Dave Scott (Tom St Denis)
Re: low diffie-hellman exponent (Tom St Denis)
Re: msg for Dave Scott (Tom St Denis)
Re: Increasing password security dramatically without making it harder to
(SCOTT19U.ZIP_GUY)
Re: Increasing password security dramatically without making it harder (Peter Gunn)
PKCS#7 implementation ("Roberto Gaudenzi")
Re: msg for Dave Scott (Tom St Denis)
Re: msg for Dave Scott (Tom St Denis)
Re: some information theory (very long plus 72K attchmt) (Tom St Denis)
Re: Schrodinger's Cat and *really* good compression (SCOTT19U.ZIP_GUY)
Re: low diffie-hellman exponent (DJohn37050)
Re: some information theory (very long plus 72K attchmt) (SCOTT19U.ZIP_GUY)
Re: Comments on ECC (Patrick Juola)
Re: Comments on ECC (Patrick Juola)
Composite SNAKE (Peter Gunn)
Re: Relating cyrptology to factoring? (Tom St Denis)
----------------------------------------------------------------------------
From: "Dmitriy Morozov" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: RSA 640 bits keys factored, French banking smart card system craked!
Date: Fri, 24 Sep 1999 07:26:45 -0400
> It doesn't matter how fast the algorithm is if you can't ever use it to
solve
> the problem. Even if you could run your algorithm with 0 time per
iteration
> you still can't set up the tables you need before you can run it. :)
Again I was talking about what would be better for smaller numbers... Though
I agree with the above argument.
--
Dmitriy Morozov
[EMAIL PROTECTED]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Fri, 24 Sep 1999 11:28:29 GMT
In article <7se7no$2cdi$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> 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.
The thing is if the cipher is designed properly you will not know which keys
to test before hand. Take for example a simple cipher of C = P xor K, and
your C is 0x91 (an 'A' with the high bit set) you know that you have to
search a keyspace with the highbit set to find the key.
If you take RC5 for example, given an output you have no clue what the key
could be (unless you use 12 rounds and have 2^53 chosen plaintext handy).
So generally a 'blind' keysearch is the only way. And may I remind this
group the brute force of the keyspace is not the only way to go. You can
attack almost any part of the cryptosystem to get it to do things it's not
suppose to.
Tom
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 11:32:03 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (DJohn37050) wrote:
> 1024 bit DL is about 80 bits of security, 2048 is about 112 bits (3 key triple
> DES) and 3072 is about 128 bits (low AES). This is according to NIST in DSA-2.
> Don Johnson
Meaning what? It will take 2^112 operations to solve a 2048 discrete
logarithm?
That's cool. Do you have any papers/reports/websites that discuss this?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Fri, 24 Sep 1999 11:41:35 GMT
Here is the source... check it out yourself. The format for the output is
actually a base64 coding but I call it binhex cuz it sounds better (plus it's
not the RFC standard base64 anyways). Originally the padding at the end was
because I didn't know how to calculate the EXACT size of the message so I
just made sure it was bigger then the message it self. Now I fixed that in
the 1.51 peekboo ----
/* encrypt a message and make a packet */
void do_encrypt(void)
{
unsigned char temp[8192], in_buf[8500], out_buf[16384];
unsigned long size, h[5];
++msg_encrypted;
memset(in_buf, 0, sizeof(in_buf));
memset(out_buf, 0, sizeof(out_buf));
/* get current cipher */
current_cipher = SendMessage(cipher_box, LB_GETCURSEL, 0, 0);
/* get message and salt */ size = SendMessage(message_box,
WM_GETTEXT, (WPARAM)sizeof(in_buf) - 20, (LPARAM)&in_buf[20]);
sha_memory(in_buf + 20, size, h); salt = h[0] ^ h[1] ^ h[2] ^
time(NULL); salt2 = h[3] ^ h[4] ^ GetTickCount();
/* store header (salt, size and cipher) and init the cipher */
*((unsigned long *)in_buf + 0) = VERSION;
*((unsigned long *)in_buf + 1) = salt;
*((unsigned long *)in_buf + 2) = salt2;
*((unsigned long *)in_buf + 3) = size;
*((unsigned long *)in_buf + 4) = current_cipher;
ciphers[current_cipher].init();
/* get message and encrypt */
SendMessage(message_box, WM_GETTEXT, (WPARAM)8192, (LPARAM)temp);
ciphers[current_cipher].encrypt(&in_buf[20], size);
/* bin to text and paste */ if (size %
ciphers[current_cipher].size) size +=
(ciphers[current_cipher].size - (size % ciphers[current_cipher].size));
size += 20;
if (size % 3)
size += (3 - (size % 3));
size = bin_to_text(in_buf, out_buf, size);
SendMessage(message_box, WM_SETTEXT, 0, (LPARAM)out_buf);
SendMessage(message_box, EM_SETSEL, 0, -1);
SendMessage(message_box, WM_COPY, 0, 0);
SendMessage(message_box, WM_SETTEXT, 0, (LPARAM)temp);
memset(temp, 0, sizeof(temp));
memset(out_buf, 0, sizeof(out_buf));
memset(in_buf, 0, sizeof(in_buf));
}
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: alt.security.pgp,comp.security.pgp
Subject: Re: Increasing password security dramatically without making it harder to
Date: Fri, 24 Sep 1999 12:52:28 GMT
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.
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: Peter Gunn <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp
Subject: Re: Increasing password security dramatically without making it harder
Date: Fri, 24 Sep 1999 12:13:02 +0100
"Lassi Hippeläinen" wrote:
> [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.
>
> ... and even if the idea were novel, it couldn't be patented any more.
> Disclosing it in a newsgroup makes it public.
Which is no bad thing :-)
ttfn
PG.
------------------------------
From: "Roberto Gaudenzi" <[EMAIL PROTECTED]>
Subject: PKCS#7 implementation
Date: Fri, 24 Sep 1999 14:23:45 +0200
Hi,
I'm looking for a C or C++ implementation of PKCS#7 standard, possibly with
source code.
Does anybody known where I can find it ?
Thanks in advance
Roberto Gaudenzi
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Fri, 24 Sep 1999 11:49:08 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> > Well you say you can break all encryption methods and systems. Prove it.
> > beaqaaamL6MNs6}utuaaaaiaaaaW{dsG{jC4KzE3hoqb}tWYZ9qT2Fcaaaaaaaaaaaaa
> > aaaaaaaaaaaaaaaaaaaaaaaaa
> > That was a peekboo message using ...
>
> (1) I don't recall David Scott saying any such thing.
> (2) Even if he could, you gave him a *very* short challenge message.
> Not being able to break it wouldn't prove anything.
> (3) Doesn't the sci.crypt FAQ address this issue of unsolicited
> challenges?
But he did mention that all systems not done by him (or he alluded to) are
weak. I want to see if he can extract anything from the peekboo messages.
Ok anyways this thread is getting ot bigtime. It's not a contest. I don't
want to see brute force crackers/etc get setup to find the message. I am
just trying to say to him that maybe not 'every other system using crypto not
blessed by mr scott' is bad. This is not suppose to be a flame, I am not
trying to put down Mr Scott at all. i.e for education purposes only.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Fri, 24 Sep 1999 11:45:35 GMT
In article <7sbckn$e79$[EMAIL PROTECTED]>,
"Rick Braddam" <[EMAIL PROTECTED]> wrote:
> I don't know that you _are_ a jerk, but you sure sound like one. Reminds me of when
>I was 17 years old and knew everything, had all
> the answers, and everything I made was of earth-shattering importance. Now I don't
>know anything, don't have any answers, and my
> most important accomplishments are my three sons; the youngest of which is 5 years
>older than you are.
Well I am not saying I know everything. I am just saying that if this kid
could make this program imagine what a 'crypto god' could do. I personally
admit that I am clueless in numbertheory, I barely even know any good algebra
etc.. I do bad in school as well :) ... anyways
> Now I'll go back to doing something useful and ignoring your flaming. It just got
>really tiresome.
Well I would like to not think of this as a flame. I am trying to make a
point that not everything 'not done by mr scott' is weak. If he can't break
a program using 'short blocks' and 'short keys' and 'three letter NSA modes'
then he should really shut up because I seriously doubt he knows what he is
talking about.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: some information theory (very long plus 72K attchmt)
Date: Fri, 24 Sep 1999 11:53:46 GMT
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.
>
> What "peekboo" does and whether or not D. Scott
> can break "peekboo" have nothing to do with the
> general issue.
>
> Even on high-speed networks, we don't want to
> waste bandwidth unnecessarily, but this actually
> works in *favor* of precompressing for encryption,
> which reduces bandwidth even though that is not
> the primary goal. Data compression of course has
> relevance independently of encryption, but that
> in itself implies nothing about its relevance
> *for* encryption.
Actualy I agree with you here. Maybe I should clear up my position
1) Compression before does make brute force slightly harder
2( It does make the message smaller
However saying (paraphrase) 'it eliminates any bias or correlations' is
completely false. That's like saying the entropy of the contents has changed
yet nothing was added or removed. Just because you change it's shape you
don't change the contents. Of course ASCII text is easier to analyze but
compressed text can be attacked as well. You just have to change what
'grammar' you are looking for,
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Schrodinger's Cat and *really* good compression
Date: Fri, 24 Sep 1999 13:21:39 GMT
In article <7sf7gi$e3n$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Bill Unruh)
wrote:
>In <[EMAIL PROTECTED]> Mok-Kong Shen <[EMAIL PROTECTED]>
> writes:
>>otherwise 'defined' cat) than we know from biology that at any
>>time point it is either alive or dead. Further, a real-life cat also
>
>We know nothng of the sort. What constitutes life and death is a much
>debated point in biiology. There seems no fixed dividing line. ( heart
>stopped?, lack of breath?, ....-- have you ever seen the experiment
>where a goldfish was plunged into liquid nitrogen, and later thawed and
>there it was swimming? Was it alive or dead when frozen?)
I heard of some artic fish with this capability and I knwo that human
embroyes have been presevered this way. There was some court battle in
the US over frozen embroyes but has a common gold fish been preserved
this way. Did they have to give the fish speical chemicals like DMSO to
prevent cell damage?
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] (DJohn37050)
Subject: Re: low diffie-hellman exponent
Date: 24 Sep 1999 12:59:09 GMT
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
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: some information theory (very long plus 72K attchmt)
Date: Fri, 24 Sep 1999 13:15:21 GMT
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.
>
>What "peekboo" does and whether or not D. Scott
>can break "peekboo" have nothing to do with the
>general issue.
>
>Even on high-speed networks, we don't want to
>waste bandwidth unnecessarily, but this actually
>works in *favor* of precompressing for encryption,
>which reduces bandwidth even though that is not
>the primary goal. Data compression of course has
>relevance independently of encryption, but that
>in itself implies nothing about its relevance
>*for* encryption.
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] (Patrick Juola)
Subject: Re: Comments on ECC
Date: 24 Sep 1999 09:23:10 -0400
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Jerry Coffin wrote:
>> If ... somebody proves that P=NP, then being NP-complete
>> doesn't mean much anymore, since it's then proven that all
>> NP problems really have deterministic solutions in polynomial
>> time.
>
>Unless somebody also invents an algorithm for converting
>any NP-complete problem into a P problem, knowing that
>P=NP wouldn't be of any practical use.
>
>> "Lucky guess" and "non-deterministic" basically mean the
>> same thing...
>
>No! In this context, nondeterministic refers to the automaton
>model, which is allowed to occasionally branch "at random"
>rather than according to a preset recipe.
However, the automaton accepts the string (remember that
the automaton model is formally valid only for decision problems)
if any only if *any* computation path results in reaching
an acceptance state.
Hence, if there *is* such a path, the nondeterministic algorithm
is guaranteed to find it (and accept), hence it always guesses
correct, and the relationship is complete.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Comments on ECC
Date: 24 Sep 1999 09:26:15 -0400
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>Jerry Coffin wrote:
>> If ... somebody proves that P=NP, then being NP-complete
>> doesn't mean much anymore, since it's then proven that all
>> NP problems really have deterministic solutions in polynomial
>> time.
>
>Unless somebody also invents an algorithm for converting
>any NP-complete problem into a P problem, knowing that
>P=NP wouldn't be of any practical use.
Cook invented most of such an algorithm in 1971 -- a problem
that is known to be NP-complete can be used to solve ANY problem
in NP by suitable formulation of the inputs, and the process
of proof of NP-completeness gives such an algorithm. All
we lack is the ability to reduce one such program to P.
And I find it unlikely -- possible, I suppose, but highly
unlikely -- that we could prove P = NP without presenting
a polynomial solution to at least one NP-complete problem,
which would in turn give us a solution to *every* NP-complete
problem.
-kitten
------------------------------
From: Peter Gunn <[EMAIL PROTECTED]>
Subject: Composite SNAKE
Date: Fri, 24 Sep 1999 14:35:01 +0100
Ive added a bit to my SNAKE Key Exchange webpage
at http://www.smdp.freeserve.co.uk/snake.html
to cover the possibility of using composite values as
a modulous for the concurrent Diffie-Hellam key exchanges.
Here is an excerpt...
"For instance, if we have a table m of 1024 large safe
prime numbers, we could (as above) define ...
f(k,P,R)=m[H(k,P,R) mod 1024]
and this will produce one possible result for each
entry in the table.... one of 2^10 values.
However, if we define...
f(k,P,R)=m[H(k,P,R) mod 1024]*
m[(H(k,P,R)/1024) mod 1024]
to produce one of approx (1024^2)/2 composite integer
values, and therefore encode upto 19 bits of P..."
Is my maths right here?? its one half of the matrix minus
the diagonal.
ttfn
PG.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Relating cyrptology to factoring?
Date: Fri, 24 Sep 1999 13:04:58 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] () wrote:
> 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.
>
> However, using these algorithms alone, before you can send a secret
> message to someone, you would have to walk to their home and give them
a
> secret key when no one was listening or watching.
>
> A new type of cryptography, called "public-key cryptography", lets
someone
> prepare a key that lets you send them a short message (usually just a
key
> for regular encryption in DES, RC5, etc.) in a way that only they can
> read, with a different key only that person knows. One of the methods
of
> this is called RSA, and *it* is the type of cipher that gets broken by
> factoring, as is obvious from how it works.
Just to be picky I would seriously argue that symmetric ciphers are
younger then their asymmetric counterparts.
Most asymetric systems are broken by solving some systems of equations.
You can break RSA by factoring their modulus and making the privatekey
from their public key. You can break diffie-hellman for example by
solving a discrete logarithm. All these problems in the long run are
very difficult to solve (or more time consuming actually). Some
progress has been made with the Number Field Sieve against factoring
composite integers (RSA-155), but I haven't seen much against discrete
logarithms. I think the Generalized Number Field Sieve is used to solve
discrete logarithms.
Does anybody have papers or source?
Tom
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
******************************
