Cryptography-Digest Digest #124, Volume #10 Sat, 28 Aug 99 01:13:03 EDT
Contents:
Re: Quantum info? (Anton Stiglic)
Re: NEW THREAD on compression (SCOTT19U.ZIP_GUY)
Re: future of RSA and hash algorithms (DJohn37050)
Re: 512 bit number factored (Tom St Denis)
Re: Freeware windows public key encryption DLLs? (David A Molnar)
Re: CryptoAPI (Tom St Denis)
Re: Can we have randomness in the physical world of "Cause and Effect" ? (Kevin
Hartnett)
Re: NEW THREAD on compression (SCOTT19U.ZIP_GUY)
Re: Wrapped PCBC mode (SCOTT19U.ZIP_GUY)
Re: receiving a piece of message (SCOTT19U.ZIP_GUY)
Re:Can americans export crypto when in another country? (Anonymous)
Can I export software that uses encryption as copy protection? ("Timur Tabi")
Re: 512 bit number factored (David A Molnar)
One to One Compression updated (SCOTT19U.ZIP_GUY)
Re: 2 person data exchange - best method? (Wim Lewis)
Re: Help: DES Encryption -> ASCII (Wim Lewis)
----------------------------------------------------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Quantum info?
Date: Fri, 27 Aug 1999 18:56:15 -0400
Go see http://crypto.cs.mcgill.ca
you'll find some links that might be of interest...
as
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: NEW THREAD on compression
Date: Sat, 28 Aug 1999 00:18:36 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>[EMAIL PROTECTED] wrote:
>>
>> Mok-Kong Shen ([EMAIL PROTECTED]) wrote:
>
>> : Yes, this works if the sole purpose is compression/decompression.
>> : But if this stuff is encrypted and decrypted back with a wrong key,
>> : you wouldn't have the proper length information. This, according
>> : to Mr. Scott's reasoning, is bad, because it immediately tells him
>> : that the key he has employed is wrong.
>>
>> At least one has to go through the whole message, from start to finish, to
>> find that the wrongly deciphered message has ended in the middle of a
>> symbol.
>
>No. My understanding of Mr. Scott's idea is as follows: Let Y be the
>ciphertext. The analyst tries a certain key K to decrypt Y to C.
>He then decompresses C to D and compresses D to C1. If C1 is not
>identical to C (this comparison can be done automatically without
>human intervention!), he knows that K is certainly wrong. Note that
>crucial to this matter is the processing at the end of the file.
>That's the main reason of providing the three conventions in my
>proposed scheme.
>
>M. K. Shen
Yes this seems to be on the wave lenght I think in. And I am calling
a compress slash decompression that meets this scheme as "one to one"
of a compress used as this feature it protects the message better. But
a lot of decompression programs barf at a bad file so the analysts knows
immediately if the guessed Key is bad. Another question if you have the
time to think about it. Are all huffman compression ending schemes that
are truly one to one ( no ranom data ) have the same average length.
What I am asking is that if my method is one to one can I change it to
make it shorter?
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: future of RSA and hash algorithms
Date: 27 Aug 1999 23:56:00 GMT
This is similar to the idea of "future resiliency" I present in my presentation
at PKS '99. See www.certicom.com in teh PKS section for my paper and
presentation for my thoughts in this area.
Don Johnson
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: Sat, 28 Aug 1999 00:03:08 GMT
In article <7q64mn$i7i$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Did you look at:
>
> http://www.rsa.com/rsalabs/html/rsa155.html
Interesting stuff.
Can you extrapolate (or guess) for more popular key sizes (768, 1024
and 2048 bits) how much time (in MIPS years) and memory (in the matrix
step) using current sieving and guassian (steps?).
Forgive me about the terminology if I got it wrong... what is the
proper name for an algorithm to solve linear matrices? (like guassian
elimination)?
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: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Freeware windows public key encryption DLLs?
Date: 27 Aug 1999 23:53:11 GMT
[ Dr. Jeff ] <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, matt <[EMAIL PROTECTED]> wrote:
>>Anyone know of any good freeware Dlls/Delphi components which can
>>implement public key encryption, and digital signatures? Any secure
>>algorithms are OK.
> If they're freeware, how can you be assure of their security?
If they happen to be open source, then you can look at it yourself. If
you can verify correctness, anyway. Otherwise the reputation of the author
+ whoever says they've looked at the code. Maybe code maturity comes in,
too -- for example, OpenSSL might reasonably be expected to be more
correct/smart in its implementation than the "RSA in Scheme" I did for a
freshman programming course once and never looked at again.
We can now #include the standard open source / closed source arguments and
save some time. :-)
-David
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: CryptoAPI
Date: Sat, 28 Aug 1999 00:07:22 GMT
In article <7q6cnu$o4v$[EMAIL PROTECTED]>,
Greg <[EMAIL PROTECTED]> wrote:
>
> > Want my opinion? Don't use MS crypto libs...
>
> And for another reason- the crypto API provider DLLs require a
> signature that comes from Redmond. If you look at the signature
> request forms from Microsoft, and the forms for the CryptAPI SDK, you
> will see that they look like gun registration forms. So I think this
> has had a serious impact on the acceptance of using the CryptAPI in
> general. I have my opinion as to why this was done, but the fact is
it
> was done and it looks discouraging to developers.
>
True, but I still think content wise the dlls suck. cryptlib has many
symmetric and a few asymmetric algorithms, is not fixed (i.,e 40 bit
keys and 512-bit keys respectively) and is open source (also I would
trust MS with an OS, but not with crypto)
Plus MS DLL's only have RC4/RC2 as far as I know now ... so what!
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: Kevin Hartnett <[EMAIL PROTECTED]>
Subject: Re: Can we have randomness in the physical world of "Cause and Effect" ?
Date: Sat, 28 Aug 1999 12:34:42 -1200
I believe it has been proven that radioactive decay and the decay of
certain elementary particles are completely random events. I imagine
someone has, or could, figure a way to use particle decay to generate
random numbers. Unfortunately I'm unable to cite any sources for you at
this time.
K. Hartnett
sb5309 wrote:
> I am not a physicist.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: NEW THREAD on compression
Date: Sat, 28 Aug 1999 01:34:48 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(John Savard) wrote:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>
>>He then decompresses C to D and compresses D to C1. If C1 is not
>>identical to C (this comparison can be done automatically without
>>human intervention!), he knows that K is certainly wrong.
>
>Yes, it can be done automatically, even though it involves the whole
>message.
Actually for many compression methods one need only look at the
first few bytes to see if it is a valid compressed file for the compression
being used.
>
>It's a good new idea, perhaps, but I wonder if it can be done without
>compromising the _old_ ideas about how compression should work for
>encryption.
>
>What I was talking about were the old ideas: how compression can be
>designed to frustrate, as well as possible, a ciphertext-only attack
>by removing redundancy.
>
>This new idea of Mr. Scott's, as you describe it, is about how
>compression, plus padding to bring the compressed text to a byte
>boundary, can be prevented from aiding a brute-force search.
>
I would not say that padding is the correct choice for what I meant
what I am looking for is a minmal huffman type of compression that
is "one to one" the concept of padding make it look like something is
being adding arbitraryily when in reality something can just is easily
be deleted as added to.
>I'm not sure this is worth worrying about: about 1/8 of the possible
>decrypts are going to pass this test for a "conventional" system like
>mine, and so an attacker relying on the compression scheme to perform
>a brute-force attack is going to have a nasty surprise.
>
>John Savard ( teneerf<- )
>http://www.ecn.ab.ca/~jsavard/crypto.htm
The point is that you are wasting 3 bits of keyspace. But it is more than
that. because you are telling the attacker this is the wrong key. He does
not have to think they are wrong. At least if you always have a file that
decompresses the attacker does not know for sure that you did not send
a binary file. He needs to use other methods and schemes to rule out the
fact that the file is wrong. You have may have been using another encryption
and the output starring hime in the face is the output of that. The point is
if one can get the 3 bits for free and not give any extra informaion to the
attacker you should take it.
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] (SCOTT19U.ZIP_GUY)
Subject: Re: Wrapped PCBC mode
Date: Sat, 28 Aug 1999 01:41:14 GMT
In article <7q5rtr$c6m$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]> wrote:
>In article <7q4qbg$2qgq$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>> It is the mode I use in my encryption programs. Just look at
>scott19u.zip it
>> is in there. Also if you look at old posts I have descriped it a lot
>in this
>> news group. Maybe David Hamiltion could help you. Put it is like PCBC
>> except you don't have to use XOR for the operations you can use others
>> I replace second wiht addition.
>>
>> Cn = E{ Cn-1 xor Pn xor Pn+1} let Po be the first block C-1 is
>the last
>> block in file.and may not necessarily mesh with any Pn due to file
>size.
>> also the file thought of as in a loop. Also the C's are offset to the
>P's
>> in scott19u the block size is 19 bits the offset is 9. You can look at
>> the code to see. One minor complication. To encryt you go down the
>file
>> in forward diction and "wrap" around to the top. To decrypt unlike
>most
>> methods you have to go in reverse direction from botton to top and
>> wrap around to bottom. The advantage of this over noraml chainning
>> is tremendous. One it can't be decoded by going down the file. The
>> file has to be processed in reverse direction ( this is not ture in
>PCBC)
>> and I doubt if the NSA likes or even bothers to consider this in
>decryption.
>> Also onther plus is the "all ot nothing feature" If you change only
>one bit
>> in the output file. And attempt to decrypt you get totally garbage.
>If you
>> do this with any of the AES mehtods using standard blessed chaining
>> like CBC or your 3 letter one of choice on a small portion of file in
>error.
>> Also with an apporved method an attacker only needs to look at a
>portion
>> of the file to test a break. With my method you need to look at the
>whole
>> file not a small fragment like with any of the AES methods using the
>> weak chaining method od choice.
>
>Since you are now reading my posts...
>
>So you mention that the nice benefit is that an attacker has to read
>the entire file (or decrypt it) to test a key. What if I use RC5 with
>16 rounds and a 160-bit key, in CBC mode. Are you telling me that
>since I used CBC you can perform a brute force search?
>
I am saying if the attacker knows a portion of the plain text
and he needs to only look at the fragment of the file that has
this section encrypted to have enough info to break the message.
That does not mean he is going to do a blind search for the key.
If you use W-pcbc he has to have and use several passed with
the whole file to obatain an equialent amout of information
>Can I tell you some down sides? The file is not really any more
>secure. What if I flip a bit of ciphertext, well the hash will not
>match. What does the attacker learn? Also what if I encrypt a 10mb
>file on disk, that's like encrypting 250 mb with 25 passes that you
>use. That's a lot of disk activity. Now you are going to say so
>what. What if I am encrypting the file over a remote link (which has
>been secured by say a RSA key exchange and a 256-bit RC5 key ...)? Do
>I really want to send 25 times the data? What if I am sending audio,
I am missing somethine w-pcbc does not change the length of file.
>video (closed circuits man) or TTY chat? What do you do then?
>
>Basically w-pcbc maybe good for 1KB messages that are finished only,
>but not much else. If anything the keysize should be the only thing to
>stop a brute force search not the chaining mode.
>
>Tom
I think one should use all he can if one wants secure encryption. But'
hay everybody is different
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] (SCOTT19U.ZIP_GUY)
Subject: Re: receiving a piece of message
Date: Sat, 28 Aug 1999 01:47:11 GMT
In article <7q6j7o$nn2$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Keith A
Monahan) wrote:
>I wrote,
>
>: >Gary,
>: >
>: >So, if its ECB(electronic code book) only mode, he is safe -- because there
>: >is a one to one mapping of plaintext -> ciphertext but any of the other
>: >modes that involve chaining or feedback require the previous ciphertext
>: >block to properly set the IV , in which case, if he does not have
>: >he would be screwed.
>: >
>: >Right?
>: >
>
>dscott wrote,
>
>: No your WRONG. THE IV only effects the next BLOCK in standard encryption.
>: It is designed that way. And most people like you are lead astray. It is very
>: very easy to test this.
>
>When you say standard encryption, are we including CBC in that description?
>Because most of the CBC implementations I have seen look like this for the
>CBC decryption function.
>
>
>oldiv = original first IV
>
>for (length=0 to bufferlength)
>{
>
> newiv = data = srcbuffer // ciphertext
>
> ECB_Decrypt(data, key)
>
> outputbuffer = data xor oldiv // plaintext after xor
>
> oldiv = newiv
>}
>
>So looking at this function, you need to have the ciphertext block prior
>to the current block in order to have the iv to decrypt the current block.
>
>Without the oldiv, the very first(and subsequent) decryption(s) would
>fail.
>
>Keith
>
Could you test this instead of GUESSING.
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
------------------------------
Date: Fri, 27 Aug 1999 15:20:13 +0200 (CEST)
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re:Can americans export crypto when in another country?
Why all the bullshit speculation? Just print the source out, put it in a
removable binder, print "book" on it, when you get to your "relatives" house
in another country, stand there and watch them scan or type it in. Logon to
your U.S. server, and have *them* hit ENTER. It's that simple.
George Gordon
------------------------------
Crossposted-To: misc.legal.computing
From: "Timur Tabi" <[EMAIL PROTECTED]>
Reply-To: "Timur Tabi" <[EMAIL PROTECTED]>
Subject: Can I export software that uses encryption as copy protection?
Date: Sat, 28 Aug 1999 03:27:36 GMT
I'm planning on developing software that decrypts the registration
information that's embedded in the binary. That is, before we ship the
software to the customer, we use a public-key encryption to generate an
encrypted message that contains the user's registration information (name,
etc). This message is then written to the application's binary (.EXE), and
the binary is e-mailed to the user. The application, whenever it's run,
decrypts the message (with the other half of the public-key) and verifies the
contents. If it's invalid, the software terminates.
Is it legal to export the binary outside the US? Keep in mind that it only
does decryption, and only of one thing: the message that's embedded within
itself. I remember reading a blurb somewhere that said what I'm trying to do
is one of the few exceptions to the export restriction laws, but for the life
of me I can't find the official documents on this. I've searched the Dept of
Commerce website high and low, so if someone has a direct URL or a document
name I'd really appreciate it.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: 512 bit number factored
Date: 28 Aug 1999 03:21:47 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Forgive me about the terminology if I got it wrong... what is the
> proper name for an algorithm to solve linear matrices? (like guassian
> elimination)?
Apologies : I misread your question. Thought you were asking whether G.E.
was a good algorithm for solving matrices. :-/
I thought of that as a "row-reduction" algorithm, though it may be better
to write "an algorithm for finding the kernel (aka null space) of a
matrix." There probably is a shorter term.
--- rest of this left in in case it may be interesting ---
It turns out that a slight variant of "normal" gaussian elimination has
been shown to be "P-complete" ; this indicates that it is probably very
hard to parallelize[1]. Other parallel algorithms work in some models, but
are not "numerically stable" in practice[2] - i.e. they produce incorrect
results because of accumulated rounding errors and the like.
So there has been a *lot* of work done on finding better algorithms. So
much so that there are entire books titled _Matrix Computations_. You
might look at the LAPACK library for some implementations; the user's
guide is at http://www.netlib.org/lapack/lug/lapack_lug.html .
It seems that different algorithms work best on different kinds of
matrices. I haven't cataloged which go with which. :-/
This reference from the announcement describes the algorithm used for
several of the previous RSA-XXX projects :
[M95] Peter L. Montgomery, A block Lanczos algorithm for finding
dependencies over GF(2), Proceedings Eurocrypt 1995,
Lecture Notes in Comput. Sci. 921, (1995) 106-120.
It's available online from ftp.cwi.nl in /pub/pmontgom
The time estimate given in the paper is as follows :
let d be average number of non-zero entries in a column of the
matrix. A matrix with low value for d is said to be "sparse",
since there's not much in it besides zeroes.
let N be the word-size of your computer. like 32 or 64.
let n be the dimension of your n x n matrix.
Then the time is given as O(dn^2/N) + O(n^2). Standard Gaussian
elimination is O(n^3). So you can see that how "sparse" the matrix is
makes a difference, because this is only really more efficient if d is not
much bigger than n. :-)
The paper also gives some implementation results from 1994. It's
interesting to note that even though the paper does not really discuss
"how parallelizable" the algorithm is, there's a report on how well it
performed on a MasPar with 16K processors. Plus on first look at the last
part of section 9, it seems most of the steps consist of matrix mults and
additions which might be efficiently parallelizable (in the large,
parallel supercomputer sense).
I guess if you figure out the expected dimensions and d value for the
matrix resulting from sieving for a given size number, you could then get
an estimate of the real time required to apply the algorithm on some
hardware. Then you'd have part of the answer to "how long would it take,
really?"
-David
[1] Problem A.8.4 "Gaussian Elimination with Partial Pivoting" in
Greenlaw, Hoover, and Ruzzo _Limits to Parallel Computation :
P-Completeness Theory_ , which in turn cites
S. Vavasis. Gaussian Elimination with pivoting is P-complete.
SIAM J. Discrete Mathematics, 2(3):412-423, 1989
note page for book at http://www.cs.ualberta.ca/~hoover/P-complete/
[2] In proceedings of SPAA '97 -- ACM Symposium on parallel algorithms +
architectures : On the parallel complexity of matrix factorization
algorithms. Mauro Leoncini, Giovanni Manzini and Luciano Margara
Pages 63-71
on the Web at
http://www.acm.org/pubs/contents/proceedings/spaa/258492/index.html
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: One to One Compression updated
Date: Sat, 28 Aug 1999 05:17:27 GMT
I updated my "one to one" adaptive huffman compression
routines. These are routines that treat any file as a compressed
file or as an uncompressed file there are no headers. Would
be of great use as a first pass before encryption see my
compression page at
http:/members.xoom.com/ecil/compress.htm
Thank You
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] (Wim Lewis)
Subject: Re: 2 person data exchange - best method?
Date: Sat, 28 Aug 1999 03:15:15 +0000
In article <[EMAIL PROTECTED]>,
Terje Mathisen <[EMAIL PROTECTED]> wrote:
>Shaun Wilde wrote:
>> If I have 2 people who wish to exchange information what is the best way to
>> do so assuming that I have no trustee (holder of public keys) and such that
>> I can defeat the Man-In-The-Middle attack.
>>
>> Can I get away with message splitting (interlock-protocol?)? Is there any
>> problems with this? Is there anything better?
>
>If there are just two people involved, I'd just use some secondary form
>of communication to verify the public keys, i.e. send the signature by
>fax and/or read it over the phone.
And if there is no trustable second channel, preexisting shared secret,
or the like, then the problem is impossible --- there's no way to tell,
for example, if the person you're talking to has always been a
man-in-the-middle since day one.
For most purposes, simply using PGP (or something similar) and verifying
key fingerprints by some second channel is good enough, but it assumes
that your communications are not *already* being actively interfered
with.
--
Wim Lewis - [EMAIL PROTECTED], also hhhh.org - Seattle, WA, USA
------------------------------
From: [EMAIL PROTECTED] (Wim Lewis)
Subject: Re: Help: DES Encryption -> ASCII
Date: Sat, 28 Aug 1999 03:30:25 +0000
In article <7puoov$a5s$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>Can I use the DES encryption to generate an ASCII encrypted string so
>that I can save it in a text file?.
Well, the easy way is to take the output of DES (or whatever cipher
you choose) and write it to the file as hexadecimal. This is extremely
easy to code but expands the ciphertext by 2:1.
The next-easiest way is to take ciphertext in 6-bit chunks and map
those 64 values to 64 ASCII characters --- uuencode, base64 (used in
MIME), and PGP's AsciiArmor all work this way. You will, obviously,
get a 4:3 increase in data size.
There is also something called Ascii85 (PostScript Level 2, and probably
PDF, support it as a means of encoding bulk binary data in text streams);
I don't remember the details, but it works on the same principle. It's
a bit more complex than base64 and is slightly more efficient at packing
binary data into printable characters. Adobe's website ought to have a
definition of this format, possibly in an appendix to a document describing
PDF or PSL2.
>Or do I have store the most significat bits of all bytes and append
>some more ASCII bytes containing these bits to the encrypted buffer so
>as to make the whole string ASCII?.
Well, you could do this --- but you'll end up with control characters,
NULs, and the like in your data file, and programs that expect *printable*
ASCII may choke, or even silently corrupt the file.
Personally, I would recommend hexadecimal if the size of your data is
small; or base64 if it's larger. Ascii85, while slightly more compact,
probably isn't worth the trouble.
--
Wim Lewis - [EMAIL PROTECTED], also hhhh.org - Seattle, WA, USA
------------------------------
** 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
******************************
